MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts

M. Pawan Kumar, Daphne Koller

Abstract

We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.

Introduction

Maximum a posteriori (MAP) estimation in Markov Random Fields (MRFs) is a foundational problem in computer vision, underlying tasks such as stereo reconstruction, image denoising, and scene registration. The challenge lies in minimizing an energy function composed of unary potentials (label fitness) and pairwise potentials (neighboring label relationships). When these pairwise potentials are semi-metrics—symmetric distance functions that may violate the triangle inequality—the optimization problem becomes NP-hard.

Historically, researchers have chosen between two suboptimal paths: fast move-making algorithms like $\alpha$-expansion, which often lack strong theoretical guarantees for non-metric potentials, or accurate but computationally prohibitive Linear Programming (LP) solvers like TRW-S. This paper introduces a hierarchical move-making approach that bridges this gap, offering the speed of graph cuts with the theoretical rigor of LP relaxations.

Hierarchical Move-Making via r-HSTs

The proposed method relies on approximating complex semi-metric distance functions using a mixture of $r$-Hierarchically Well-Separated Trees ($r$-HSTs).

r-HST structure for hierarchical move-making

An $r$-HST is a rooted tree where the leaves represent the set of possible labels. The distance between any two labels is defined by the path length between their corresponding leaves. A key property of $r$-HSTs is that edge lengths decrease geometrically by a factor of $r$ as one moves from the root toward the leaves, allowing for a divide-and-conquer optimization strategy.

The algorithm proceeds through several key stages:

  1. Metric Approximation: The complex semi-metric is approximated as a mixture of $T$ different $r$-HSTs.
  2. Hierarchical Moves: Optimization is performed through the tree structure. By solving subproblems at lower levels and propagating solutions upward, the algorithm ensures that each move is submodular and can be solved exactly using the efficient $st$-MINCUT algorithm.
  3. Hard EM Refinement: To further improve accuracy, an iterative refinement step learns new $r$-HSTs specifically tailored to the current best labeling.

Experimental Evaluation

The authors evaluated the proposed method ("Our") against standard baselines, including $\alpha$-expansion, $\alpha\beta$-swap, and TRW-S, across synthetic and real-world datasets.

Denoising results on House and Penguin images

In image denoising experiments, the method consistently achieved lower energy states than standard move-making baselines while remaining significantly faster than message-passing alternatives. In synthetic tests, the algorithm was 10x to 70x faster than TRW-S while maintaining nearly identical energy levels. For semi-metric problems, such as those involving truncated quadratic potentials, the hierarchical approach significantly outperformed $\alpha$-expansion in finding more likely global solutions.

Conclusion

This work presents a novel framework for MAP estimation that leverages the tractability of tree-structured metrics. By embedding semi-metric MRFs into $r$-HST spaces, the authors achieve the approximation guarantees of LP relaxations using only efficient graph cut operations. While slightly slower than basic $\alpha$-expansion due to the multi-tree approach, the significant gain in accuracy and theoretical robustness makes it a powerful tool for complex vision tasks. Future work includes extending this hierarchical strategy to higher-order potentials beyond pairwise interactions.

Summary updated

Abstract

We consider the task of obtaining the maximum a posteriori estimate of discrete pairwise random fields with arbitrary unary potentials and semimetric pairwise potentials. For this problem, we propose an accurate hierarchical move making strategy where each move is computed efficiently by solving an st-MINCUT problem. Unlike previous move making approaches, e.g. the widely used a-expansion algorithm, our method obtains the guarantees of the standard linear programming (LP) relaxation for the important special case of metric labeling. Unlike the existing LP relaxation solvers, e.g. interior-point algorithms or tree-reweighted message passing, our method is significantly faster as it uses only the efficient st-MINCUT algorithm in its design. Using both synthetic and real data experiments, we show that our technique outperforms several commonly used algorithms.
BibTeX
@inproceedings{kumar2009map,
  author = {M. Pawan Kumar and Daphne Koller},
  title = {{MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=ENOSN4vxjr},
}
Figure