What energy functions can be minimized via graph cuts?
Abstract
In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.
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?
Graph Cuts can be used to minimize Eq. (6) when the pairwise potential is submodular, such as when the segmentation is binary with the compatibility being the delta function and the pairwise function being positive.
“Graph Cuts [8], [46] can be used to minimize Eq. (6) when”
From DeepIGeoS: A Deep Interactive Geodesic Framework for Medical Image Segmentation (2019) · cites this paper as [56]
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
Flagged first, then by citations
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
GrabCut: Interactive foreground extraction using iterated graph cuts
Rother, C., Kolmogorov, V., & Blake, A. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015720 · Cited by 5,703 · see citing works
Self-citationAn 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 · see citing works
Self-citationDeformable medical image registration: a survey
Sotiras, A., Davatzikos, C., & Paragios, N. (2013) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2013.2265603 · Cited by 1,587 · 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
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
GeoS: Geodesic Image Segmentation
Criminisi, A., Sharp, T., & Blake, A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_9 · Cited by 277 · see citing works
Energy Minimization via Graph Cuts: Settling What is Possible
Freedman, D., & Drineas, P. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.143 · Cited by 173 · see citing works
Transformation of General Binary MRF Minimization to the First-Order Case
Ishikawa, H. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.91 · Cited by 144 · see citing works
Visual Tracking via Probability Continuous Outlier Model
Wang, D., & Lu, H. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.445 · Cited by 113 · see citing works
Generalized Gradients: Priors on Minimization Flows
Charpiat, G., Maurel, P., Pons, J.-P., Keriven, R., & Faugeras, O. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-9966-2 · Cited by 91
High-throughput histopathological image analysis via robust cell segmentation and hashing
Zhang, X., Xing, F., Su, H., Yang, L., & Zhang, S. (2015) · Medical Image Analysis · doi:10.1016/j.media.2015.10.005 · Cited by 87 · 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
Optical flow estimation with uncertainties through dynamic MRFs
Glocker, B., Paragios, N., Komodakis, N., Tziritas, G., & Navab, N. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587562 · Cited by 69 · 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
Automatic Visual Defect Detection Using Texture Prior and Low-Rank Representation
Huangpeng, Q., Zhang, H., Zeng, X., & Huang, W. (2018) · IEEE Access · doi:10.1109/access.2018.2852663 · Cited by 53 · see citing works
So, R. W. K., & Chung, A. C. S. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2016.09.004 · Cited by 36 · see citing works
Quadratization of symmetric pseudo-Boolean functions
Anthony, M., Boros, E., Crama, Y., & Gruber, A. (2016) · Discrete Applied Mathematics · doi:10.1016/j.dam.2016.01.001 · Cited by 26 · see citing works
- Authors
- Kolmogorov, V., & Zabih, R.
- Affiliations
- Cornell University (US)
- ORCID
- Kolmogorov, V.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2004-02
- Volume
- 26
- Issue
- 2
- Pages
- 147-159
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2101309634
- Cited by
- 3,127
- References
- 1
- Citations by year
- 2026: 18 · 2025: 32 · 2024: 36 · 2023: 43 · 2022: 39 · 2021: 75 · 2020: 92 · 2019: 115 · 2018: 138 · 2017: 196 · 2016: 218 · 2015: 227 · 2014: 256 · 2013: 230 · 2012: 235
- FWCI
- 109.75
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- eCommons (Cornell University) (submittedVersion)
- UCL Discovery (University College London) (submittedVersion)
- Funders
- National Science Foundation
- Topics
- 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
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
- Keywords
- graph cuts, energy minimization, binary optimization, graph construction, minimum cut, combinatorial optimization, computer vision, stereo matching, image restoration, scene reconstruction, necessary conditions
- MeSH terms
- Algorithms, Artificial Intelligence, Computer Graphics, Image Enhancement, Image Interpretation, Computer-Assisted, Numerical Analysis, Computer-Assisted, Pattern Recognition, Automated, Sensitivity and Specificity, Signal Processing, Computer-Assisted, Subtraction Technique, User-Computer Interface, Reproducibility of Results, 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
