The DOI matches its Crossref record; 6 of the 6 references it cites were found in a registry or an index.
A maximum-flow formulation of the N-camera stereo correspondence problem
Abstract
This paper describes a new algorithm for solving the N-camera stereo correspondence problem by transforming it into a maximum-flow problem. Once solved, the minimum-cut associated to the maximum-flow yields a disparity surface for the whole image at once. This global approach to stereo analysis provides a more accurate and coherent depth map than the traditional line-by-line stereo. Moreover, the optimality of the depth surface is guaranteed and can be shown to be a generalization of the dynamic programming approach that is widely used in standard stereo. Results show improved depth estimation as well as better handling of depth discontinuities. While the worst case running time is O(n/sup 2/d/sup 2/log(nd)), the observed average running time is O(n/sup 1.2/ d/sup 1.3/) for an image size of n pixels and depth resolution d.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming
Ohta, Y., & Kanade, T. (1985) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1985.4767639 · Cited by 932
A Maximum Likelihood Stereo Algorithm
Cox, I. J., Hingorani, S. L., Rao, S. B., & Maggs, B. M. (1996) · Computer Vision and Image Understanding · doi:10.1006/cviu.1996.0040 · Cited by 470
Self-citationDepth from edge and intensity based stereo
Baker, H. H., & Binford, T. O. (1981) · Masters Thesis · Cited by 408
A stereo machine for video-rate dense depth mapping and its new applications
Kanade, T., Yoshida, A., Oda, K., Kano, H., & Tanaka, M. (1996) · Proceedings CVPR IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1996.517074 · Cited by 356
A Bayesian approach to binocular steropsis
Belhumeur, P. N. (1996) · International Journal of Computer Vision · doi:10.1007/bf00055146 · Cited by 239
Cited by
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms
Scharstein, D., & Szeliski, R. (2002) · International Journal of Computer Vision · doi:10.1023/a:1014573219977 · Cited by 6,740
“More recently, max-flow and graph-cut methods have been proposed to solve a special class of global optimization problems [59, 36, 18, 77, 44].”
MethodAn experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Boykov, Y., & Kolmogorov, V. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.60 · Cited by 4,577
Bundle Adjustment — A Modern Synthesis
Triggs, B., McLauchlan, P. F., Hartley, R. I., & Fitzgibbon, A. W. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44480-7_21 · Cited by 3,988
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127
A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms
Seitz, S. M., Curless, B., Diebel, J., Scharstein, D., & Szeliski, R. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR'06) · doi:10.1109/cvpr.2006.19 · Cited by 2,457
Graph Cuts and Efficient N-D Image Segmentation
Boykov, Y., & Funka-Lea, G. (2006) · International Journal of Computer Vision · doi:10.1007/s11263-006-7934-5 · Cited by 1,910
DAISY: An Efficient Dense Descriptor Applied to Wide-Baseline Stereo
Tola, E., Lepetit, V., & Fua, P. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.77 · Cited by 1,405
A Theory of Shape by Space Carving
Kutulakos, K. N., & Seitz, S. M. (2000) · International Journal of Computer Vision · doi:10.1023/a:1008191222954 · Cited by 1,254
Advances in computational stereo
Brown, M. Z., Burschka, D., & Hager, G. D. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1217603 · Cited by 1,132
A taxonomy and evaluation of dense two-frame stereo correspondence algorithms
Scharstein, D., Szeliski, R., & Zabih, R. (2002) · Proceedings IEEE Workshop on Stereo and Multi-Baseline Vision (SMBV 2001) · doi:10.1109/smbv.2001.988771 · Cited by 1,084
Multi-camera Scene Reconstruction via Graph Cuts
Kolmogorov, V., & Zabih, R. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-47977-5_6 · Cited by 739
State of the art in high density image matching
Remondino, F., Spera, M. G., Nocerino, E., Menna, F., & Nex, F. (2014) · The Photogrammetric Record · doi:10.1111/phor.12063 · Cited by 628
Furukawa, Y., & Hernández, C. (2015) · Foundations and Trends in Computer Graphics and Vision · doi:10.1561/0600000052 · Cited by 598
Photorealistic scene reconstruction by voxel coloring
Seitz, S. M., & Dyer, C. R. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609462 · Cited by 543
Photorealistic Scene Reconstruction by Voxel Coloring
Seitz, S. M., & Dyer, C. R. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008176507526 · Cited by 492
Exact optimization for markov random fields with convex priors
Ishikawa, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233908 · Cited by 486
A fast local descriptor for dense matching
Tola, E., Lepetit, V., & Fua, P. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587673 · Cited by 480
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.791245 · Cited by 470
Markov random fields with efficient approximations
Boykov, Y., Veksler, O., & Zabih, R. (2002) · Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231) · doi:10.1109/cvpr.1998.698673 · Cited by 422
Kleinberg, J., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/585265.585268 · Cited by 400
Lisein, J., Pierrot-Deseilligny, M., Bonnet, S., & Lejeune, P. (2013) · Forests · doi:10.3390/f4040922 · Cited by 392
MicMac – a free, open-source solution for photogrammetry
Rupnik, E., Daakir, M., & Pierrot Deseilligny, M. (2017) · Open Geospatial Data, Software and Standards · doi:10.1186/s40965-017-0027-2 · Cited by 392
A survey of graph theoretical approaches to image segmentation
Peng, B., Zhang, L., & Zhang, D. (2013) · Pattern Recognition · doi:10.1016/j.patcog.2012.09.015 · Cited by 390
A theory of shape by space carving
Kutulakos, K. N., & Seitz, S. M. (1999) · Proceedings of the Seventh IEEE International Conference on Computer Vision · doi:10.1109/iccv.1999.791235 · Cited by 372
Handling occlusions in dense multi-view stereo
Kang, S. B., Szeliski, R., & Chai, J. (2005) · Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001 · doi:10.1109/cvpr.2001.990462 · Cited by 353
Total Variation Minimization and a Class of Binary MRF Models
Chambolle, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/11585978_10 · Cited by 324
An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision
Boykov, Y., & Kolmogorov, V. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44745-8_24 · Cited by 320
Automatic breast ultrasound image segmentation: a survey
Xian, M., Zhang, Y., Cheng, H. D., Xu, F., Zhang, B., & Ding, J. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2018.02.012 · Cited by 284
“It was then improved to solve the general (color image segmentation) and multi-label problem [17, 18].”
BackgroundMultiview Stereo via Volumetric Graph-Cuts and Occlusion Robust Photo-Consistency
Vogiatzis, G., Hernandez Esteban, C., Torr, P. H. S., & Cipolla, R. (2007) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2007.70712 · Cited by 284
Multi-View Stereo via Volumetric Graph-Cuts
Vogiatzis, G., Torr, P. H. S., & Cipolla, R. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.238 · Cited by 275
A global matching framework for stereo computation
Tao, H., Sawhney, H. S., & Kumar, R. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937562 · Cited by 268
Furukawa, Y., & Hernández, C. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781601988379 · Cited by 268
Multimodal Style Transfer via Graph Cuts
Zhang, Y., Fang, C., Wang, Y., Wang, Z., Lin, Z., Fu, Y., & Yang, J. (2019) · 2019 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2019.00604 · Cited by 98
Metadata
- Authors
- Roy, S., & Cox, I. J.
- Venue
- Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271)
- Publisher
- Narosa Publishing House
- Published
- 2002-11-27
- Pages
- 492-499
- OpenAlex
- W1649464328
- Cited by
- 485
- References
- 6
- FWCI
- 29.16
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.