Abstract
One of the most exciting advances in early vision has been the development of efficient energy minimization algorithms. Many early vision tasks require labeling each pixel with some quantity such as depth or texture. While many such problems can be elegantly expressed in the language of Markov Random Fields (MRF’s), the resulting energy minimization problems were widely viewed as intractable. Recently, algorithms such as graph cuts and loopy belief propagation (LBP) have proven to be very powerful: for example, such methods form the basis for almost all the top-performing stereo methods. Unfortunately, most papers define their own energy function, which is minimized with a specific algorithm of their choice. As a result, the tradeoffs among different energy minimization algorithms are not well understood. In this paper we describe a set of energy minimization benchmarks, which we use to compare the solution quality and running time of several common energy minimization algorithms. We investigate three promising recent methods—graph cuts, LBP, and tree-reweighted message passing—as well as the well-known older iterated conditional modes (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching and interactive segmentation. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods with minimal overhead. We expect that the availability of our benchmarks and interface will make it significantly easier for vision researchers to adopt the best method for their specific problems. Benchmarks, code, results and images are available at http://vision.middlebury.edu/MRF.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Besag, J.: On the statistical analysis of dirty pictures (with discussion). Journal of the Royal Statistical Society, Series B 48, 259–302 (1986)
Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans Pattern Anal Mach Intell 6, 721–741 (1984)
Barnard, S.: Stochastic stereo matching over scale. Intern Journ Comp Vis 3, 17–32 (1989)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. IEEE Trans Pattern Anal Mach Intell 23, 1222–1239 (2001)
Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? IEEE Trans Pattern Anal Mach Intell 26, 147–159 (2004)
Yedidia, J.S., Freeman, W.T., Weiss, Y.: Generalized belief propagation. In: NIPS, pp. 689–695 (2000)
Scharstein, D., Szeliski, R.: A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. Intern Journ Comp Vis 47, 7–42 (2002)
Geman, S., Graffigne, C.: Markov Random Field image models and their applications to computer vision. In: Intern Cong of Mathematicians, pp. 1496–1517 (1986)
Chou, P.B., Brown, C.M.: The theory and practice of Bayesian image labeling. Intern Journ Comp Vis 4, 185–210 (1990)
Boykov, Y., Jolly, M.P.: Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images. In: ICCV, pp. I:105–112 (2001)
Rother, C., Kolmogorov, V., Blake, A.: “GrabCut” - interactive foreground extraction using iterated graph cuts. SIGGRAPH 23, 309–314 (2004)
Agarwala, A., et al.: Interactive digital photomontage. SIGGRAPH 23, 292–300 (2004)
Tappen, M.F., Freeman, W.T.: Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters. In: ICCV, pp. 900–907 (2003)
Boykov, Y., Kolmogorov, V.: An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal Mach Intell 26, 1124–1137 (2004)
Kolmogorov, V., Rother, C.: Comparison of energy minimization algorithms for highly connected graphs. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3952, pp. 1–15. Springer, Heidelberg (2006)
Li, S.: Markov Random Field Modeling in Computer Vision. Springer, Heidelberg (1995)
Efros, A.A., Freeman, W.T.: Image quilting for texture synthesis and transfer. SIGGRAPH, 341–346 (2001)
Kwatra, V., Schodl, A., Essa, I., Turk, G., Bobick, A.: Graphcut textures: Image and video synthesis using graph cuts. SIGGRAPH (2003)
Greig, D., Porteous, B., Seheult, A.: Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society, Series B 51, 271–279 (1989)
Ishikawa, H.: Exact optimization for Markov Random Fields with convex priors. IEEE Trans Pattern Anal Mach Intell 25, 1333–1336 (2003)
Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov Random Fields and related problems. Journal of the ACM (JACM) 48, 686–701 (2001)
Felzenszwalb, P.F., Huttenlocher, D.P.: Efficient belief propagation for early vision. In: CVPR, pp. 261–268 (2004)
Kolmogorov, V.: Convergent tree-reweighted message passing for energy minimization. In: AISTATS (2005)
Rother, C., Kumar, S., Kolmogorov, V., Blake, A.: Digital tapestry. In: CVPR (2005)
Pearl, J.: Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, San Francisco (1988)
Agarwala, A., et al.: Panoramic video textures. SIGGRAPH 24, 821–827 (2005)
Snow, D., Viola, P., Zabih, R.: Exact voxel occupancy with graph cuts. In: CVPR, pp. 345–352 (2000)
Buehler, C., Gortler, S.J., Cohen, M.F., McMillan, L.: Minimal surfaces for stereo. In: Heyden, A., Sparr, G., Nielsen, M., Johansen, P. (eds.) ECCV 2002. LNCS, vol. 2352, pp. 885–899. Springer, Heidelberg (2002)
Kolmogorov, V., Criminisi, A., Blake, A., Cross, G., Rother, C.: Bi-layer segmentation of binocular stereo video. In: CVPR, pp. 407–414 (2005)
Wainwright, M.J., Jaakkola, T.S., Willsky, A.S.: MAP estimation via agreement on (hyper)trees: Message-passing and linear-programming approaches. IEEE Trans Info Theory 51 (2005)
Meltzer, T., Yanover, C., Weiss, Y.: Globally optimal solutions for energy minimization in stereo vision using reweighted belief propagation. In: ICCV (2005)
Komodakis, N., Tziritas, G.: A new framework for approximate labeling via graph cuts. In: ICCV (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Szeliski, R. et al. (2006). A Comparative Study of Energy Minimization Methods for Markov Random Fields. In: Leonardis, A., Bischof, H., Pinz, A. (eds) Computer Vision – ECCV 2006. ECCV 2006. Lecture Notes in Computer Science, vol 3952. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11744047_2
Download citation
DOI: https://doi.org/10.1007/11744047_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33834-5
Online ISBN: 978-3-540-33835-2
eBook Packages: Computer ScienceComputer Science (R0)