A Comparative Study of Energy Minimization Methods for Markov Random Fields

  • Carsten Rother
  • Ramin Zabih
  • Daniel Scharstein
  • Olga Veksler
  • Vladimir Kolmogorov
  • Aseem Agarwala
  • Marshall Tappen
  • Carsten Rother

Proc. European Conference in Computer Vision (ECCV) |

Published by Springer-Verlag

View Publication

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 these 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 trade-offs among different energy minimization algorithms are not well understood. In this paper we address this problem by constructing a set of energy minimization benchmarks, which we use to experimentally compare several common energy minimization algorithms both in terms of solution quality and running time. 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. Code for nearly all of the algorithms and benchmark problems were contributed by their original developers. We also describe 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.