An experimental comparison of min-cut/max- flow algorithms for energy minimization in vision
Abstract
After [15], [31], [19], [8], [25], [5], minimum cut/maximum flow algorithms on graphs emerged as an increasingly useful tool for exact or approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push-relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
CRFs have been widely used to enhance segmentation accuracy by introducing spatial consistency.
“Graphical models such as CRFs [22], [42], [43] have been widely used to enhance segmentation accuracy by introducing spatial consistency.”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [42]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
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 · see citing works
Self-citationA 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 · see citing works
Level Set Methods and Dynamic Implicit Surfaces
Osher, S., & Fedkiw, R. P. (2003) · Applied mathematical sciences · doi:10.1007/b98879 · Cited by 4,988 · see citing works
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,080 · see citing works
Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Boykov, Y. Y., & Jolly, M.-P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937505 · Cited by 3,674 · see citing works
Self-citationLevel Set Methods and Fast Marching Methods
Sethian, J. A. (1999) · Medical Entomology and Zoology · Cited by 3,588 · see citing works
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 · see citing works
Self-citation(2003) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812796936_others05 · Cited by 2,493 · see citing works
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,895 · see citing works
Kwatra, V., Schödl, A., Essa, I. A., Turk, G., & Bobick, A. (2003) · ACM SIGGRAPH Conference (SIGGRAPH) · doi:10.1145/1201775.882264 · Cited by 1,216 · see citing works
Level Set Methods and Dynamic Implicit Surfaces
Osher, S., Fedkiw, R. P., & Piechór, K. (2004) · Applied Mechanics Reviews · doi:10.1115/1.1760520 · Cited by 1,205 · see citing works
Wu, Z., & Leahy, R. M. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.244673 · Cited by 1,144 · see citing works
Computing visual correspondence with occlusions using graph cuts
Kolmogorov, V., & Ramin Zabih, A. (2002) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2001.937668 · Cited by 1,128 · see citing works
Self-citationA taxonomy and evaluation of dense two-frame stereo correspondence algorithms
Scharstein, D., Szeliski, R., & Zabih, R. (2002) · doi:10.1109/smbv.2001.988771 · Cited by 1,103 · see citing works
Exact Maximum A Posteriori Estimation for Binary Images
Greig, D. M., Porteous, B. T., & Seheult, A. H. (1989) · Journal of the Royal Statistical Society Series B (Statistical Methodology) · doi:10.1111/j.2517-6161.1989.tb01764.x · Cited by 1,066 · see citing works
Level set methods and dynamic implicit surfaces
(2003) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(03)90179-9 · Cited by 986 · see citing works
Ford, L. R., & Fulkerson, D. R. (1963) · Princeton University Press eBooks · doi:10.1515/9781400875184 · Cited by 890 · see citing works
Geometric Partial Differential Equations and Image Analysis
Sapiro, G. (2001) · Cambridge University Press eBooks · doi:10.1017/cbo9780511626319 · Cited by 847 · see citing works
Geometric Level Set Methods in Imaging, Vision, and Graphics
Osher, S., & Paragios, N. (2003) · Springer eBooks · doi:10.1007/b97541 · Cited by 802 · see citing works
Multi-camera Scene Reconstruction via Graph Cuts
Kolmogorov, V., & Ramin Zabih, A. (2002) · Lecture notes in computer science · doi:10.1007/3-540-47977-5_6 · Cited by 745 · see citing works
Self-citationComputing geodesics and minimal surfaces via graph cuts
Boykov, & Kolmogorov (2003) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2003.1238310 · Cited by 555 · see citing works
A maximum-flow formulation of the N-camera stereo correspondence problem
Roy, S., & Cox, I. J. (2002) · International Conference on Computer Vision · doi:10.1109/iccv.1998.710763 · Cited by 489 · see citing works
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 487 · see citing works
Bobick, A., & Intille, S. S. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008150329890 · Cited by 461 · see citing works
Markov random fields with efficient approximations
Boykov, Y., Veksler, O., & Zabih, R. (2002) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.1998.698673 · Cited by 424 · see citing works
Self-citationFaster Shortest-Path Algorithms for Planar Graphs
Henzinger, M. R., Klein, P. N., Rao, S. S., et al. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1493 · Cited by 409 · see citing works
Algorithm for solution of a problem of maximum flow in networks with power estimation
Dinic, E. A. (1970) · Medical Entomology and Zoology · Cited by 389 · see citing works
On Implementing the Push—Relabel Method for the Maximum Flow Problem
Cherkassky, B. V., & Goldberg, A. V. (1997) · Algorithmica · doi:10.1007/pl00009180 · Cited by 376 · see citing works
(1998) · Choice Reviews Online · doi:10.5860/choice.35-5705 · Cited by 344 · see citing works
An Experimental Comparison of Min-cut/Max-flow Algorithms for Energy Minimization in Vision
Boykov, Y. Y., & Kolmogorov, V. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44745-8_24 · Cited by 322 · see citing works
Self-citationRandom Sampling in Cut, Flow, and Network Design Problems
Karger, D. R. (1999) · Mathematics of Operations Research · doi:10.1287/moor.24.2.383 · Cited by 193 · see citing works
Occlusions, discontinuities, and epipolar lines in stereo
Ishikawa, H., & Geiger, D. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055670 · Cited by 192 · see citing works
Exact voxel occupancy with graph cuts
Snow, D., Viola, P. A., & Zabih, R. (2002) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2000.855839 · Cited by 175 · see citing works
Segmentation by grouping junctions
Ishikawa, H., & Geiger, D. (2002) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.1998.698598 · Cited by 165 · see citing works
An Experimental Comparison of Stereo Algorithms
Szeliski, R., & Zabih, R. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44480-7_1 · Cited by 124 · see citing works
Stereo Without Epipolar Lines: A Maximum-Flow Formulation
Roy, S. (1999) · International Journal of Computer Vision · doi:10.1023/a:1008192004934 · Cited by 104 · see citing works
Image segmentation by nested cuts
Veksler, O. (2002) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2000.855838 · Cited by 82 · see citing works
A new Bayesian framework for object recognition
Boykov, Y., & Huttenlocher, D. P. (2003) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.1999.784730 · Cited by 52 · see citing works
Self-citationFlow in planar graphs with multiple sources and sinks
Miller, G. L., & Naor, J. S. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63464 · Cited by 32 · see citing works
Buehler, C., Gortler, S. J., Cohen, M. F., et al. (2002) · Lecture notes in computer science · doi:10.1007/3-540-47977-5_58 · Cited by 30 · see citing works
Incorporating Spatial Priors into an Information Theoretic Approach for fMRI Data Analysis
Kim, J.-M., Fisher, J. W., Tsai, A., et al. (2000) · Lecture notes in computer science · doi:10.1007/978-3-540-40899-4_7 · Cited by 29 · see citing works
MRF solutions for probabilistic optical flow formulations
Roy, S., & Govindu, V. M. (2002) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.2000.903724 · Cited by 23 · see citing works
Fusion of color, shading and boundary information for factory pipe segmentation
Thirion, B., Bascle, B., Ramesh, V., et al. (2000) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2000.854845 · Cited by 21 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- [22][22] V. Kolmogorov, ' Graph-Based Algorithms for Multi-Camera Reconstruction Problem,' PhD thesis, Computer Science Dept., Cornell Univ., 2003. -
Cited by
Sorted by citations
The multimodal brain tumor image segmentation benchmark (BRATS)
Menze, B. H., Jakab, A., Bauer, S., Kalpathy-Cramer, J., Farahani, K., Kirby, J., Burren, Y., Porz, N., Slotboom, J., Wiest, R., et al. (2015) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2014.2377694 · Cited by 6,781 · see citing works
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 · see citing works
Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images
Boykov, Y. Y., & Jolly, M.-P. (2002) · Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001 · doi:10.1109/iccv.2001.937505 · Cited by 3,674 · see citing works
Self-citationLearning Hierarchical Features for Scene Labeling
Farabet, C., Couprie, C., Najman, L., & LeCun, Y. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.231 · Cited by 2,620 · see citing works
Random Walks for Image Segmentation
Grady, L. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.233 · Cited by 2,624 · see citing works
Making Bertha Drive—An Autonomous Journey on a Historic Route
Ziegler, J., Bender, P., Schreiber, M., Lategahn, H., Strauss, T., Stiller, C., Dang, T., Franke, U., Appenrodt, N., Keller, C. G., et al. (2014) · IEEE Intelligent Transportation Systems Magazine · doi:10.1109/mits.2014.2306552 · Cited by 854 · see citing works
Improved Automatic Detection and Segmentation of Cell Nuclei in Histopathology Images
Al-Kofahi, Y., Lassoued, W., Lee, W., & Roysam, B. (2010) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2009.2035102 · Cited by 681 · see citing works
DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation
Wang, G., Zuluaga, M. A., Li, W., Pratt, R., Patel, P. A., Aertsen, M., Doel, T., David, A. L., Deprest, J., Ourselin, S., et al. (2019) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2840695 · Cited by 502 · see citing works
Deep learning in microscopy image analysis: a survey
Xing, F., Xie, Y., Su, H., Liu, F., & Yang, L. (2018) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2017.2766168 · Cited by 460 · see citing works
Dynamic Adaptive DNN Surgery for Inference Acceleration on the Edge
Hu, C., Bao, W., Wang, D., & Liu, F. (2019) · IEEE INFOCOM 2019 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2019.8737614 · Cited by 416 · see citing works
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 · see citing works
Supervised Learning of Image Restoration with Convolutional Networks
Jain, V., Murray, J. F., Roth, F., Turaga, S., Zhigulin, V., Briggman, K. L., Helmstaedter, M. N., Denk, W., & Seung, H. S. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408909 · Cited by 217 · see citing works
Automatic Liver Segmentation Based on Shape Constraints and Deformable Graph Cut in CT Images
Li, G., Chen, X., Shi, F., Zhu, W., Tian, J., & Xiang, D. (2015) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2481326 · Cited by 185 · see citing works
A Likelihood and Local Constraint Level Set Model for Liver Tumor Segmentation from CT Volumes
Li, C., Wang, X., Eberl, S., Fulham, M., Yin, Y., Chen, J., & Feng, D. D. (2013) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2013.2267212 · Cited by 139 · see citing works
SuRVoS: Super-Region Volume Segmentation workbench
Luengo, I., Darrow, M. C., Spink, M. C., Sun, Y., Dai, W., He, C. Y., Chiu, W., Pridmore, T., Ashton, A. W., Duke, E. M. H., et al. (2017) · Journal of Structural Biology · doi:10.1016/j.jsb.2017.02.007 · Cited by 89 · see citing works
Global registration of dynamic range scans for articulated model reconstruction
Chang, W., & Zwicker, M. (2011) · ACM Transactions on Graphics · doi:10.1145/1966394.1966405 · Cited by 87 · see citing works
Unmanned Aerial Vehicle Video-Based Target Tracking Algorithm Using Sparse Representation
Wan, M., Gu, G., Qian, W., Ren, K., Maldague, X., & Chen, Q. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2930656 · Cited by 62 · see citing works
Real-Time Image Segmentation on a GPU
Abramov, A., Kulvicius, T., Wörgötter, F., & Dellen, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-16233-6_14 · Cited by 34 · see citing works
GPU-friendly multi-view stereo reconstruction using surfel representation and graph cuts
Chang, J. Y., Park, H., Park, I. K., Lee, K. M., & Lee, S. U. (2011) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2010.11.017 · Cited by 24 · see citing works
Qian, C., Yang, H., & Li, J. (2023) · 2023 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · doi:10.1109/smc53992.2023.10393973 · Cited by 1 · see citing works
- Authors
- Boykov, Y., & Kolmogorov, V.
- Affiliations
- Western University (CA)
- Institute of Electrical and Electronics Engineers (US)
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2004-09
- Volume
- 26
- Issue
- 9
- Pages
- 1124-1137
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2113137767
- Cited by
- 4,577
- References
- 43
- Citations by year
- 2026: 30 · 2025: 74 · 2024: 75 · 2023: 113 · 2022: 132 · 2021: 151 · 2020: 177 · 2019: 221 · 2018: 248 · 2017: 284 · 2016: 315 · 2015: 360 · 2014: 354 · 2013: 362 · 2012: 330
- FWCI
- 100.47
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- Funders
- University of Tsukuba
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Medical Image Segmentation Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Vision and Imaging
- Keywords
- energy minimization, graph cuts, augmenting paths, algorithm benchmarking, image restoration, stereo matching, image segmentation, low-level vision, real-time performance
- MeSH terms
- Algorithms, Artificial Intelligence, Energy Transfer, Image Enhancement, Image Interpretation, Computer-Assisted, Pattern Recognition, Automated, Photogrammetry, Photography, Sensitivity and Specificity, Reproducibility of Results, Cluster Analysis, Information Storage and Retrieval, Imaging, Three-Dimensional
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
