A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors
Top Cited Papers
- 18 April 2008
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Ieee Transactions On Pattern Analysis and Machine Intelligence
- Vol. 30 (6), 1068-1080
- https://doi.org/10.1109/tpami.2007.70844
Abstract
Among the most exciting advances in early vision has been the development of efficient energy minimization algorithms for pixel-labeling tasks such as depth or texture computation. It has been known for decades that such problems can be elegantly expressed as Markov random fields, yet the resulting energy minimization problems have been widely viewed as intractable. 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. However, the trade-offs among different energy minimization algorithms are still not well understood. In this paper, we describe a set of energy minimization benchmarks and use them to compare the solution quality and runtime of several common energy minimization algorithms. We investigate three promising methods-graph cuts, LBP, and tree-reweighted message passing-in addition to the well-known older iterated conditional mode (ICM) algorithm. Our benchmark problems are drawn from published energy functions used for stereo, image stitching, interactive segmentation, and denoising. We also provide a general-purpose software interface that allows vision researchers to easily switch between optimization methods. The benchmarks, code, images, and results are available at http://vision.middlebury.edu/MRF/.Keywords
This publication has 42 references indexed in Scilit:
- "GrabCut"ACM Transactions on Graphics, 2004
- Interactive digital photomontageACM Transactions on Graphics, 2004
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIeee Transactions On Pattern Analysis and Machine Intelligence, 2004
- What energy functions can be minimized via graph cuts?Ieee Transactions On Pattern Analysis and Machine Intelligence, 2004
- Surfaces with occlusions from layered stereoIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Exact optimization for markov random fields with convex priorsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Fast approximate energy minimization via graph cutsIeee Transactions On Pattern Analysis and Machine Intelligence, 2001
- An efficient algorithm for image segmentation, Markov random fields and related problemsJournal of the ACM, 2001
- On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphsIEEE Transactions on Information Theory, 2001
- A pixel dissimilarity measure that is insensitive to image samplingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1998