What energy functions can be minimized via graph cuts?
- PMID: 15376891
- DOI: 10.1109/TPAMI.2004.1262177
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.
Similar articles
-
Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities.IEEE Trans Pattern Anal Mach Intell. 2005 Aug;27(8):1239-53. doi: 10.1109/TPAMI.2005.161. IEEE Trans Pattern Anal Mach Intell. 2005. PMID: 16119263
-
Minimizing nonsubmodular functions with graph cuts - a review.IEEE Trans Pattern Anal Mach Intell. 2007 Jul;29(7):1274-9. doi: 10.1109/TPAMI.2007.1031. IEEE Trans Pattern Anal Mach Intell. 2007. PMID: 17496384 Review.
-
Nonparametric multiscale energy-based model and its application in some imagery problems.IEEE Trans Pattern Anal Mach Intell. 2004 Feb;26(2):184-97. doi: 10.1109/TPAMI.2004.1262180. IEEE Trans Pattern Anal Mach Intell. 2004. PMID: 15376894
-
Automatic construction of active appearance models as an image coding problem.IEEE Trans Pattern Anal Mach Intell. 2004 Oct;26(10):1380-4. doi: 10.1109/TPAMI.2004.77. IEEE Trans Pattern Anal Mach Intell. 2004. PMID: 15641725
-
Multivariate image analysis in biomedicine.J Biomed Inform. 2004 Oct;37(5):380-91. doi: 10.1016/j.jbi.2004.07.010. J Biomed Inform. 2004. PMID: 15488751 Review.
Cited by
-
High-Dimensional Structured Feature Screening Using Binary Markov Random Fields.JMLR Workshop Conf Proc. 2012;22:712-721. JMLR Workshop Conf Proc. 2012. PMID: 23606924 Free PMC article.
-
A fully-automatic caudate nucleus segmentation of brain MRI: application in volumetric analysis of pediatric attention-deficit/hyperactivity disorder.Biomed Eng Online. 2011 Dec 5;10:105. doi: 10.1186/1475-925X-10-105. Biomed Eng Online. 2011. PMID: 22141926 Free PMC article.
-
Greedy parameter optimization for diabatic quantum annealing.Philos Trans A Math Phys Eng Sci. 2023 Jan 23;381(2241):20210416. doi: 10.1098/rsta.2021.0416. Epub 2022 Dec 5. Philos Trans A Math Phys Eng Sci. 2023. PMID: 36463922 Free PMC article.
-
Augmenting an electronic Ising machine to effectively solve boolean satisfiability.Sci Rep. 2023 Dec 21;13(1):22858. doi: 10.1038/s41598-023-49966-6. Sci Rep. 2023. PMID: 38129549 Free PMC article.
-
Dynamic programming and graph algorithms in computer vision.IEEE Trans Pattern Anal Mach Intell. 2011 Apr;33(4):721-40. doi: 10.1109/TPAMI.2010.135. IEEE Trans Pattern Anal Mach Intell. 2011. PMID: 20660950 Free PMC article. Review.
Publication types
MeSH terms
LinkOut - more resources
Full Text Sources
Other Literature Sources
