What energy functions can be minimized via graph cuts?

V. Kolmogorov, R. Zabih, IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004) 147–159.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
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.
Publishing Year
Date Published
2004-02-01
Journal Title
IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume
26
Issue
2
Page
147 - 159
IST-REx-ID

Cite this

Kolmogorov V, Zabih R. What energy functions can be minimized via graph cuts? . IEEE Transactions on Pattern Analysis and Machine Intelligence. 2004;26(2):147-159. doi:10.1109/TPAMI.2004.1262177
Kolmogorov, V., & Zabih, R. (2004). What energy functions can be minimized via graph cuts? . IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2), 147–159. https://doi.org/10.1109/TPAMI.2004.1262177
Kolmogorov, Vladimir, and Ramin Zabih. “What Energy Functions Can Be Minimized via Graph Cuts? .” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 2 (2004): 147–59. https://doi.org/10.1109/TPAMI.2004.1262177.
V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts? ,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 147–159, 2004.
Kolmogorov V, Zabih R. 2004. What energy functions can be minimized via graph cuts? . IEEE Transactions on Pattern Analysis and Machine Intelligence. 26(2), 147–159.
Kolmogorov, Vladimir, and Ramin Zabih. “What Energy Functions Can Be Minimized via Graph Cuts? .” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, IEEE, 2004, pp. 147–59, doi:10.1109/TPAMI.2004.1262177.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar