A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems

By Jörg H. Kappes, Björn Andres, Fred A. Hamprecht, Christoph Schnörr, Sebastian Nowozin, Dhruv Batra, Sungwoong Kim, Bernhard X. Kausler, Thorben Kröger, J. Lellmann and 3 more. 2014

190 citations recorded by the source corpus.

Szeliski et al. published an influential study in 2006 on energy minimization methods for Markov random fields. This study provided valuable insights in choosing the best optimization technique for certain classes of problems. While these insights remain generally useful today, the phenomenal success of random field models means that the kinds of inference problems that have to be solved changed significantly. Specifically, the models today often include higher order interactions, flexible connectivity structures, large label-spaces of different cardinalities, or learned energy tables. To reflect these changes, we provide a modernized and enlarged study. We present an empirical comparison of more than 27 state-of-the-art optimization techniques on a corpus of 2453 energy minimization instances from diverse applications in computer vision. To ensure reproducibility, we evaluate all methods in the OpenGM 2 framework and report extensive results regarding runtime and solution quality. Key insights from our study agree with the results of Szeliski et al. for the types of models they studied. However, on new and challenging types of models our findings disagree and suggest that polyhedral methods and integer programming solvers are competitive in terms of runtime and solution quality over a large range of model types.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

In Probabilistic & Bayesian Methods

Citations in the corpus

InstanceCut: From Edges to Instances with MultiCut (2016, methodology): “Although the problem (3) is NP-hard in general, it can be efficiently (and often exactly) solved for many practical instances appearing in computer vision, see [27] for an overview.”
Joint Graph Decomposition and Node Labeling by Local Search (2016, methodology): “Formally, the minimum cost node labeling lifted multicut problem we propose and refer to as the NL-LMP generalizes theNP-hard unconstrained integer quadratic program, UIQP, that has been studied intensively in the context of graphica l models [10] and also generalizes the NP-hard minimum cost lifted”
Cut, Glue, & Cut: A Fast, Approximate Solver for Multicut Partitioning (2014, methodology): “Therefore, we derive a more comprehensive set of instances with volumes of 30(3) up to 450(3) voxels from the models in [5], available as part of the OpenGM benchmark [12].”
Joint Graph Decomposition & Node Labeling: Problem, Algorithms, Applications (2016, methodology): “This problem that we call the minimum cost node labeling lifted multicut problem, NL-LMP, generalizes the NP-hard unconstrained integer quadratic program, UIQP, that has been studied intensively in the context of graphical models [14], and also generalizes the NP-hard minimum cost lifted multicut pr”
Global Hypothesis Generation for 6D Object Pose Estimation (2016, background): “Although this problem is NP-hard, in general, a number of efficient approximative solvers exist, see [15] for a recent review.”