| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
What Energy Functions Can Be Minimizedvia Graph Cuts?
February 2004 (vol. 26 no. 2)
pp. 147-159
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.
[1] 147 R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.[2] A.A. Amini,T.E. Weymouth,, and R.C. Jain,“Using dynamic programming for solving variational problems in vision,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 12, no. 9, pp. 855-867, 1990.[3] S. Barnard, Stochastic Stereo Matching Over Scale Int'l J. Computer Vision, vol. 3, no. 1, pp. 17-32, 1989.[4] S. Birchfield and C. Tomasi, Multiway Cut for Stereo and Motion with Slanted Surfaces Proc. Int'l Conf. Computer Vision, pp. 489-495, 1999.[5] Y. Boykov and M.-P. Jolly, Interactive Organ Segmentation Using Graph Cuts Proc. Medical Image Computing and Computer-Assisted Intervention, pp. 276-286, 2000.[6] Y. Boykov and M.-P. Jolly, Interactive Graph Cutsfor Optimal Boundary&Region Segmentation of Objects in N-D Images Proc. Int'l Conf. Computer Vision, vol. I, pp. 105-112, July 2001.[7] Y. Boykov and V. Kolmogorov, An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Computer Vision Proc. Int'l Workshop Energy Minimization Methods in Computer Vision and Pattern Recognition, Lecture Notes in Computer Science, pp. 359-374, Springer-Verlag, Sept. 2001.[8] Y. Boykov and V. Kolmogorov, Computing Geodesics and Minimal Surfaces via Graph Cuts Proc. Int'l Conf. Computer Vision, vol. I, pp. 26-33, 2003.[9] Y. Boykov, O. Veksler, and R. Zabih, Markov Random Fields with Efficient Approximations Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 648-655, 1998.[10] Y. Boykov, O. Veksler, and R. Zabih, Fast Approximate Energy Minimization via Graph Cuts IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 11, pp. 1222-1239, Nov. 2001.[11] W.H. Cunningham, Minimum Cuts, Modular Functions, and Matroid Polyhedra Networks, vol. 15, pp. 205-215, 1985.[12] E. Dahlhaus, D.S. Johnson, C.H. Papadimitriou, P.D. Seymour, and M. Yannakakis, The Complexity of Multiway Cuts Proc. ACM Symp. Theory of Computing, pp. 241-251, 1992.[13] J. Dias and J. Leitao, The${\cal Z}\pi M$Algorithm: A Method for Interferometric Image Reconstruction in SAR/SAS IEEE Trans. Image Processing, vol. 11, no. 4, pp. 408-422, Apr. 2002.[14] L. Ford and D. Fulkerson, Flows in Networks. Princeton Univ. Press, 1962.[15] S. Fujishige, Submodular Functions and Optimization vol. 47, Annals of Discrete Math., North Holland, 1990.[16] S. Geman and D. Geman, Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 6, pp. 721-741, 1984.[17] A. Goldberg and R. Tarjan, A New Approach to the Maximum Flow Problem J. ACM, vol. 35, no. 4, pp. 921-940, Oct. 1988.[18] D. Greig, B. Porteous, and A. Seheult, Exact Maximum A Posteriori Estimation for Binary Images J. Royal Statistical Soc., Series B, vol. 51, no. 2, pp. 271-279, 1989.[19] M. Grötschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988.[20] H. Ishikawa and D. Geiger, Occlusions, Discontinuities, and Epipolar Lines in Stereo Proc. European Conf. Computer Vision, pp. 232-248, 1998.[21] H. Ishikawa and D. Geiger, Segmentation by Grouping Junctions Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 125-131, 1998.[22] H. Ishikawa, Exact Optimization for Markov Random Fields with ConvexPriors IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 10, pp. 1333-1336, Oct. 2003.[23] S. Iwata, L. Fleischer, and S. Fujishige, A Combinatorial, Strongly Polynomial Algorithm for Minimizing Submodular Functions J. ACM, vol. 48, no. 4, pp. 761-777, July 2001.[24] J. Kim, V. Kolmogorov, and R. Zabih, Visual Correspondence Using Energy Minimization and Mutual Information Proc. Int'l Conf. Computer Vision, pp. 1033-1040, 2003.[25] J. Kim and R. Zabih, Automatic Segmentation of Contrast-Enhanced Image Sequences Proc. Int'l Conf. Computer Vision, pp. 502-509, 2003.[26] J. Kim, J. Fisher, A. Tsai, C. Wible, A. Willsky, and W. Wells, Incorporating Spatial Priors into an Information Theoretic Approach for FMRI Data Analysis Proc. Medical Image Computing and Computer-Assisted Intervention, pp. 62-71, 2000.[27] V. Kolmogorov and R. Zabih, Visual Correspondence with Occlusions Using Graph Cuts Proc. Int'l Conf. Computer Vision, pp. 508-515, 2001.[28] V. Kolmogorov and R. Zabih, Multi-Camera Scene Reconstruction via Graph Cuts Proc. European Conf. Computer Vision, vol. 3, pp. 82-96, 2002.[29] V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick, Graphcut Textures: Image and Video Synthesis Using Graph Cuts ACM Trans. Graphics, Proc. SIGGRAPH 2003, July 2003.[30] C.-H. Lee, D. Lee, and M. Kim, "Optimal Task Assignment in Linear Array Networks," IEEE Trans. Computers, vol. 41, no. 7, pp. 877-880, July 1992.[31] S. Li, Markov Random Field Modeling in Computer Vision. Springer-Verlag, 1995.[32] M.H. Lin, Surfaces with Occlusions from Layered Stereo PhD thesis, Stanford Univ., Dec. 2002.[33] I. Milis, Task Assignment in Distributed Systems Using Network Flow Methods Proc. Combinatorics and Computer Science, Lecture Notes in Computer Science, pp. 396-405, Springer-Verlag, 1996.[34] T. Poggio, V. Torre, and C. Koch, Computational Vision and Regularization Theory Nature, vol. 317, pp. 314-319, 1985.[35] S. Roy, Stereo without Epipolar Lines: A Maximum Flow Formulation Int'l J. Computer Vision, vol. 1, no. 2, pp. 1-15, 1999.[36] S. Roy and I. Cox, A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem IEEE Proc. Int'l Conf. Computer Vision, pp. 492-499, 1998.[37] D. Scharstein and R. Szeliski, A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms Int'l J. Computer Vision, vol. 47, pp. 7-42, Apr. 2002.[38] A. Schrijver, A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time J. Combinatorial Theory, vol. B 80, pp. 346-355, 2000.[39] D. Snow, P. Viola, and R. Zabih, Exact Voxel Occupancy with Graph Cuts Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 345-352, 2000.[40] H.S. Stone, Multiprocessor Scheduling with the Aid of Network Flow Algorithms IEEE Trans. Software Eng., pp. 85-93, 1977.[41] R. Szeliski and R. Zabih, An Experimental Comparison of Stereo Algorithms Proc. Vision Algorithms: Theory and Practice, Lecture Notes in Computer Science, B. Triggs, A. Zisserman, and R. Szeliski, eds., vol. 1883, pp. 1-19, Springer-Verlag, Sept. 1999.
Index Terms:
Energy minimization, optimization, graph algorithms, minimum cut, maximum flow, Markov Random Fields.
Citation:
Vladimir Kolmogorov, Ramin Zabih, "What Energy Functions Can Be Minimizedvia Graph Cuts?," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 147-159, Jan. 2004, doi:10.1109/TPAMI.2004.1262177
