PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jörg H. Kappes, Bjoern Andres, Fred A. Hamprecht, Christoph Schnörr, Sebastian Nowozin, Dhruv Batra, Sungwoong Kim, Bernhard X. Kausler, Thorben Kröger, Jan Lellmann, Nikos Komodakis, Bogdan Savchynskyy, Carsten Rother

arXiv:1404.0533v1cs.CV

TL;DR

Modern energy-minimization models differ from earlier restricted models through arbitrary structured graphs and higher-order potentials. This study broadens the comparison across inference methods and models, finding that advanced polyhedral and ILP solvers can be competitive while approximate methods are often fast and nearly optimal.

  • Problem

    Modern energy-minimization problems include arbitrary structured graphs and higher-order potentials beyond the restricted models previously studied.

  • Method

    The study compares state-of-the-art inference methods and models implemented within the uniform, multiplatform OpenGM 2 framework.

  • Results

    Advanced polyhedral LP and ILP solvers are competitive across a wide range of problems, while approximative methods often provide nearly optimal solutions very fast.

  • Takeaways & Limitations

    Exact solvers can establish optimality and assess whether approximate methods are suitable, but energy-optimal labelings do not always minimize application-specific loss.

  • Takeaways & Limitations

    No single technique works best for all cases, and differing implementation paradigms make reported relative runtimes difficult to overemphasize.

Abstract

from arXiv · show

Szeliski et al. published an influential study in 2006 on energy minimization methods for Markov Random Fields (MRF). 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 la\-bel-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 32 state-of-the-art optimization techniques on a corpus of 2,453 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.

1 Introduction

Modern computer-vision energy-minimization problems have outgrown the restricted models and methods compared in 2006. This study broadens both the benchmark and the inference-method set, finding that polyhedral solvers are competitive across many model types.

  • Motivation: Modern vision models use arbitrary structured graphs, higher-order potentials, larger datasets, and learned parameters rather than only 4-connected unary-pairwise grids.The study identifies four model changes: higher-order factors, denser or irregular connectivity, superpixel variables, and partitioning without unary terms or a fixed class count.
  • Study expansion: The comparison updates Szeliski et al.’s benchmark by adding recent move-making and local methods, higher-order techniques, and polyhedral methods based on linear or integer programming.The methods and models are implemented within the uniform OpenGM 2 framework.
  • Study expansion: The study addresses reproducibility and fair comparison by making models and inference methods available through a single flexible software framework.Earlier comparisons often covered specialized model classes or lacked publicly available models, methods, or a flexible common framework.
  • Key insights: Advanced polyhedral LP and ILP solvers are competitive across a wide range of computer-vision problems and sometimes achieve global optimality within practical runtimes.They can match or outperform approximative methods on some simple models and solve some large or complex models successfully, but are often weak when many variables combine with loose LP relaxations.
  • Key insights: Primal move-making methods typically perform best when models have many variables and the LP relaxation is not tight, agreeing with earlier findings in that regime.The study proposes exploring compact expressive models and improving ILP and LP solver efficiency as future research directions.
  • Scope: The paper focuses on MAP estimation through energy minimization rather than posterior-distribution inference beyond point estimation.The latter is described as preferable statistically but too expensive for most large-scale computer-vision applications.

2 Graphical Models

The paper formulates discrete energy minimization on finite-label factor graphs, where factors define potentials over connected variables and the objective sums their contributions. OpenGM 2 represents these models and separates modeling from inference.

  • Factor-graph representation: A factor graph G=(V,F,E) contains variable nodes, factor nodes, and edges specifying which variables each factor connects.Each variable has a finite discrete label-space, and each factor maps assignments of its neighboring variables to a real-valued potential.
  • Factor-graph representation: Factor order is the number of neighboring variables, while model order is the maximum factor order.Pairwise factors therefore have order 2.
  • Energy minimization: The energy J(x) is the sum of factor potentials, and minimizing it yields a minimum-energy labeling that is also a MAP solution.The labeling assigns one discrete state to every variable.
  • Factor-graph representation: Factor graphs are used instead of MRFs because they represent the underlying problem structure more precisely and explicitly.
  • OpenGM 2 framework: OpenGM 2 supports arbitrary-order models, arbitrary functions, shared functions, and storage in the HDF5 format while decoupling optimization from modeling.This enables model instances and inference methods to be exchanged without application-specific evaluation code.
  • OpenGM 2 framework: Inference in OpenGM 2 initializes an inference method for a chosen operation, runs infer(), and retrieves the resulting labeling with arg().A visitor can log optimization progress during inference.

3 Benchmark Models

The benchmark spans classical pixel models and newer settings with denser or irregular connectivity, higher-order factors, superpixels, learned potentials, and variable label spaces. These models cover diverse computer-vision tasks and include both standard and specialized objective properties.

  • Pixel-based models: Classical pixel-based models associate variables with image pixels and commonly use four-neighbor pairwise grids, while denser neighborhoods and higher-order structures extend this setting.The study includes 4-connected models and models using 8- or 6-neighborhoods, remote couplings, and higher-order terms.
  • Benchmark overview: The benchmark catalogs datasets by instance count, variables, labels, factor order, graph structure, function properties, and available application-specific loss functions.Listed losses include pixel accuracy, color error, variation of information, and geometric error; some models lack ground truth or a loss function.
  • Pixel-based models: Learned decision-tree-field potentials can create highly connected, non-sub-modular binary problems, exemplified by variables linked to 27 others within a 17 × 17 window.The dtf-chinesechar model has only two labels per variable but uses discriminative learned pairwise potentials.
  • Pixel-based models: Pixel-based higher-order modeling is often made tractable by reducing terms such as labeling costs and Pn-Potts to second-order models with auxiliary variables.The benchmark includes an inclusion model with a fourth-order term, while systematic higher-order enrichment is difficult for large pixel graphs.
  • Superpixel-based models: Superpixel models constrain all pixels in a superpixel to share one label, reducing variables and enabling more complex factors, but making grouping decisions irreversible.Their graphs are generally no longer regular, and the benchmark includes pairwise and third-order superpixel models.
  • Other models: The benchmark also covers unsupervised image partitioning, hyper-graph segmentation, network clustering, keypoint matching without unary terms, and cell tracking with higher-order events.Partitioning models may use positive or negative couplings, higher-order junction or similarity terms, and label spaces tied to the number of variables.

4 Inference Methods

The study compares four broad inference families: combinatorial optimization, LP-relaxation methods, move-making, and message passing. Its polyhedral-method discussion emphasizes bounds, relaxation quality, dual optimization, and convergence behavior.

  • Method families: The benchmark groups methods into combinatorial optimization, linear-programming relaxations, move-making, and message passing, with some methods leveraging max-flow subproblems.Monte Carlo methods are generally excluded because they converge slowly, require parameter tuning, and are uncommon in computer vision.
  • Polyhedral methods: LP-relaxation methods provide lower bounds but may return non-integer solutions that require rounding to obtain a discrete labeling.This creates a trade-off between certification information and the need to recover an integer solution.
  • Polyhedral methods: The local-polytope LP relaxation is common; TRWS optimizes a dual formulation for large problems but can become stuck at suboptimal fixed points.Small instances can be handled with off-the-shelf LP solvers, whereas large problems motivate specialized dual solvers.
  • Dual decomposition: Adaptive subgradient and bundle variants are guaranteed to converge to the relaxed dual optimum, while their performance depends on the chosen stepsize rule.Primal integer solutions are reconstructed from subgradients, and multiple stepsize rules are evaluated.
  • Dual decomposition: Other dual-decomposition approaches include AD3, ADSAL, MPLP, and MPLP-C, with MPLP-C tightening the local-polytope relaxation by adding violated short-cycle constraints.ADSAL smooths the dual problem to avoid local suboptimal fixed points.
  • Dual decomposition: Dual decomposition splits the problem into tractable subproblems, updates Lagrange multipliers from subproblem solutions, and projects multipliers back into the feasible set when necessary.The algorithm alternates decomposition, subproblem optimization, dual updates, projection, and a stopping test.

4.2 Combinatorial Methods

Combinatorial and integer-programming methods target globally optimal discrete solutions through integer constraints, cutting planes, branching, and specialized solvers. The section also describes memory-saving and problem-specific variants.

  • Integer programming: ILPs add integer constraints and guarantee global optimality, unlike LP-relaxation methods that may be optimal only in some cases.ILP solutions are obtained through sequences of LPs combined with cutting-plane or branching strategies.
  • Cutting planes: Cutting-plane optimization repeatedly solves the current relaxation and adds constraints violated by its solution until no violated constraints remain.The method progressively tightens the feasible polytope around the optimum.
  • Branch and bound: Branch-and-bound partitions the candidate set into subproblems, selects branch nodes, and computes the best feasible solution within each selected subset.The algorithm begins with the full candidate set and maintains a collection of branched subsets.
  • Solver implementations: The study evaluates ILP through OpenGM 2 and reports three BRAOBB variants after excluding that solver’s invalid optimality bounds.The authors state that the BRAOBB authors confirmed the invalid-bound observations.
  • Hybrid methods: CombiLP exploits near-integral LP solutions by applying combinatorial optimization mainly to the small non-integral portion of the graphical model.If LP and ILP solutions cannot be made consistent, the non-integral subproblem is enlarged and the procedure repeats.
  • Specialized solvers: The integer multicut solver MCI reduces memory requirements but applies only to functions with permutation-invariant or first-order terms.Its integer solutions also enable more efficient shortest-path procedures.
  • Specialized solvers: MCBC is a max-cut branch-and-cut solver restricted to pairwise binary problems and was unavailable publicly because of license restrictions.

4.3 Message-Passing Methods

Message-passing methods iteratively re-parameterize a graphical model through local or regional messages and then decode a labeling. Their practical appeal includes simple implementation and parallelizable updates, but convergence guarantees vary by algorithm and model.

  • Core procedure: Message passing can be understood as re-parameterizing the model so that local optimization becomes globally consistent.
  • Practical properties: Message-passing methods are popular because they are simple to implement and easy to parallelize, with further speedups available for special message-update cases such as distance transforms.
  • Core procedure: Message passing initializes messages, repeatedly updates them using other messages, and decodes a state locally or greedily after the updates stabilize.Messages may be defined on edges or between larger regions.
  • Algorithmic behavior: TRBP supports higher-order models but lacks convergence guarantees and works practically when sufficient message damping is used.
  • Algorithmic behavior: LBP converges to the global optimum for acyclic models, whereas the cited discussion indicates weaker guarantees beyond that setting.

4.4 Move-Making Methods

Move-making methods iteratively optimize tractable subsets of the label space, including binary label moves, generalized fusion moves, and local variable updates.

  • α-β-Swap restricts moves to variables labeled α or β, allowing them to retain or exchange those labels.Under technical conditions, its binary auxiliary problems are submodular and solvable by max-flow.
  • Move-making methods initialize a labeling and repeatedly minimize over label subsets that contain the current labeling.The process stops when no further progress is possible.
  • α-Expansion lets every variable retain its label or switch to a selected label α, with one pass over all possible labels.The auxiliary problem can be reduced to max-flow under technical conditions.
  • ICM greedily improves a labeling by optimizing one variable at a time while keeping all others fixed.An extension searches exhaustively over variable subsets of a specified size k.
  • α-Fusion generalizes α-Expansion to general problems and higher-order factors using proposal labelings and QPBO-based auxiliary optimization.Non-integer QPBO variables remain unchanged, and higher-order auxiliary problems use reduction techniques.
  • Kernighan-Lin specializes to partition problems by iteratively merging and splitting regions to improve the energy.

4.5 Rounding

Rounding converts fractional or pseudo-marginal outputs into feasible integer labelings, but the chosen procedure can substantially affect solution quality and may be brittle.

  • Rounding transforms fractional indicator vectors or pseudo-min-marginals from LP and message-passing methods into feasible integer solutions.The final integer-solution quality depends on the rounding procedure.
  • Per-variable rounding is efficient but brittle and can fail even on tree-structured models by mixing two modes.A more informed option conditions equation (2) on variables that have already been rounded.
  • Because rounding can be as hard as the original NP-hard problem, no rounding method uniformly outperforms all others.MCR uses derandomization, while MPLP runs multiple rounding schemes and selects the best result.

4.6 Post- and Pre-Processing

Preprocessing and post-processing reduce problem difficulty or improve an initial solution, but some reductions alter modeling fidelity and solver performance depends on implementation choices.

  • CombiLP combines TRWS with ILP as a meta-solver.
  • Preprocessing can solve subsets of variables or separate acyclic substructures and connected components before applying more involved solvers.These procedures were proposed to reduce runtime and can make combinatorial methods as efficient as approximate methods.
  • Grouping variables by the energy function reduces problem size, but is not invariant to reparameterization and produces an approximation.
  • InfAndFlip first obtains a good starting labeling and then applies Lazy Flipping, which never increases the energy but depends heavily on initialization.The suffix -LFk denotes Lazy Flipping post-processing with search depth k.
  • Distance transforms speed up TRWS for Potts models, with grid-specialized mrf-TRWS fastest among the implementations shown.The original TRWS follows, then ogm-TRWS; the plot compares six implementations on one instance.

4.7 Comparability of Algorithms and their Implementations

Algorithm comparisons measure particular implementations rather than abstract algorithms, creating a trade-off between specialized speed and general flexibility and making scheduling choices consequential.

  • Specialized implementations can be much faster than general ones because they exploit efficient data structures, simplified interfaces, and compiler optimizations.The study estimates that some specialized implementations may achieve speedups of approximately 100×.
  • The study contrasts fast, less-flexible specialized solvers with slower, highly flexible OpenGM 2 implementations.Examples include specialized TRWS, BPS, and FastPD versus general Dual Decomposition and LBP implementations.
  • Specialized solvers support designed-for model classes efficiently but restrict modeling freedom, whereas general solvers handle arbitrary functions and orders more slowly.
  • 4.8 Algorithmic Scheduling: Move ordering affects both solution quality and runtime for α-Expansion, αβ-Swap, ICM, and Lazy-Flipper.Optimized ordering can often improve results, but no theoretical guarantee makes it strictly better than the default.
  • 4.8 Algorithmic Scheduling: Sequential message passing often performs better empirically than parallel methods but is harder to parallelize because it depends on message ordering.Parallel methods typically underperform asynchronous methods and may require damping for convergence.
  • 4.8 Algorithmic Scheduling: Cutting-plane scheduling and branch-selection strategies add further implementation degrees of freedom, for which the experiments use default options.

4.9 Stopping Condition

The study combines time, optimality-gap, and numerical-change criteria to stop inference methods, reflecting differences between primal, dual, and rounded solutions.

  • Move-making methods stop when no available move improves the current feasible labeling, provided the move set can be optimized exactly.The stopping rule is practical only when the considered move set is manageable.
  • LP methods may have matching primal and dual optimum values while still producing non-integral solutions whose rounding introduces an integrality gap.Extracting a primal solution from a dual is non-trivial, so duality does not by itself guarantee an integral labeling.
  • The study sets LP precision to 10^-7 because higher precision increases runtime without necessarily changing the rounded integer solution.LP approaches often solve only up to a specified floating-point precision.
  • The evaluation uses a total gap combining integrality and duality gaps because reliable primal-dual-gap estimates are not available for all algorithms.Small changes in the primal-dual gap can theoretically have a large impact on the integrality gap.
  • Numerically small message or dual improvements can indicate that further iterations are more likely to encounter numerical problems than improve the solution.The examples use message changes below 10^-5 for LBP and very small dual improvements for TRWS.
  • Additional stopping rules terminate every algorithm after 1 hour, below a 10^-5 integer-solution-to-lower-bound gap, or below 10^-7 numerical changes.These criteria supplement algorithm-specific stopping conditions.
  • The added stopping condition improves runtime for methods such as TRWS and LBP without worsening their other results.These methods suffer when iteration count is used as the only stopping condition.

5 Experimental Setup

The experiments standardize hardware, software, and runtime accounting while acknowledging that algorithm implementations differ in optimization and model applicability.

  • Experiments run on an Intel Core i7-2600K CPU with 16 GB RAM, using three cores without multithreading or hyper-threading.Parallelizability and parallel implementation runtime are outside the study’s scope.
  • OpenGM 2.3.1 provides unrestricted graph and function structures, state-of-the-art algorithms, custom implementations, and wrappers for publicly available code.Implementation prefixes identify whether code originates from OpenGM or the earlier MRF framework.
  • Runtime measurements exclude model-copying time, initialization memory allocation, and tracking overhead for current integer solutions and lower bounds.These exclusions are intended to make runtime comparisons comparable.
  • The benchmark compares highly optimized algorithms restricted to specific model classes with less optimized research code applicable across broader model classes.This implementation heterogeneity must be considered when interpreting the comparison.

6 Evaluation

The evaluation shows that solver performance depends strongly on model structure, relaxation tightness, scale, and the quality of rounded or feasible solutions.

  • 60 labels prevented verified optimality for the teddy instance, while faster suboptimal solutions were not significantly worse in PA2 on two optimally solved instances.BPS solutions averaged 2% better PA2 than solutions with smaller objective values.
  • Move-making algorithms outperform LP-relaxation methods on photomontage because discriminative second-order factors make the LP relaxation loose and rounding difficult.The comparison covers two photomontage instances.
  • All nine Potts color-segmentation instances were solved optimally by multicut and CombiLP, while local-polytope relaxations were tight for seven instances.The instances contain 76,800 variables and use few labels on 4-connected or 8-connected grids.
  • Approximate solutions for the hardest instance remained reasonable but multiway-cut algorithms did not find a solution within one hour.Approximation differences were especially visible around the yellow feathers near the neck.
  • Color-segmentation instances had tight local-polytope relaxations, with approximate methods reaching optimality on two instances and near-optimality on one.Kovtun preprocessing can reduce the problem size before applying more involved solvers.
  • FastPD was 10 times faster than TRWS on object segmentation and was only marginally worse in objective value for one instance.FastPD and α-expansion achieved slightly better pixel accuracy than optimal solutions.
  • Potts models can still be hard when first-order factors do not discriminate well between labels.The result concerns 8-connected grid graphs with strong and inverse first-order factors.
  • For brain segmentation with 10^5–10^6 variables, MCI-ptc alone solved all instances within one hour, while FastPD finished in one-tenth the runtime with worse objective values.TRWS produced tight lower bounds but suboptimal approximate solutions, showing that rounding remained difficult.

7 Discussion and Conclusions

The study finds that no inference technique is best across all models and objectives. Approximative methods are often fast and nearly optimal, while exact, combinatorial, polyhedral, and integer-programming methods can be competitive or necessary for difficult and complex models.

  • Overall comparison: No single technique works best across all cases because models and objectives differ, while implementation paradigms also affect runtime comparisons.A single instance can lower a method’s average score, so reported rankings should not be overemphasized.
  • Approximate inference: Approximative methods provide nearly optimal solutions very fast for most models, but methods supporting higher-order terms become useful when second-order methods no longer apply.TRWS performs well where applicable, whereas FastPD and α-expansion offer deterministic stopping and greater robustness when local-polytope relaxations are loose.
  • Exact and combinatorial methods: Exact solutions are significantly better than approximate ones for difficult models such as dtf-chinesechar and matching, while easier models allow exact methods to assess approximation error.Exact methods can solve some instances within one hour and provide reference solutions for evaluating sub-optimality.
  • Exact and combinatorial methods: Combinatorial optimization methods are faster than reported state-of-the-art methods for some models, although larger problems may require reduction by partial optimality.Their exact solutions also support evaluation of sub-optimal approximate solutions.
  • Energy versus application loss: The energy-optimal labeling is not always best under application-specific loss functions, because approximate methods may avoid isolated high-energy alternatives and favor more consistent modes.The relationship between energy and loss varies across applications, although it correlates well for many models.
  • Polyhedral methods: Local-polytope LP methods often produce good solutions across broad model classes but are generally not the fastest; tightening the relaxation can substantially help when it is weak.The study highlights multicuts for Potts models and MPLP-C for matching instances as examples.
  • Scope and future research: The study’s broad model coverage is not all-embracing, and available effective solvers may have biased which models received research attention.The authors nevertheless include higher-order and densely structured models such as dtf-chinesechar, matching, and protein-prediction.
  • Scope and future research: More general optimization methods may encourage use of complex discrete models and motivate efficient approximative methods for real-world time constraints.This is presented as a direction for future research rather than as an evaluated result.
Loading 1404.0533v1…