MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts

M. Pawan Kumar, Daphne Koller

Abstract

Maximum A Posteriori (MAP) estimation in Markov Random Fields (MRFs) with semi-metric pairwise potentials is a fundamental but computationally challenging problem in computer vision. This paper introduces a novel hierarchical move-making algorithm that bridges the gap between fast move-making methods and accurate but slow Linear Programming (LP) relaxations. By approximating semi-metric distance functions as a mixture of $r$-hierarchically well-separated trees ($r$-HSTs), the proposed method leverages efficient $st$-MINCUT operations to achieve energy levels comparable to state-of-the-art LP solvers like TRW-S while being significantly faster.

Introduction

Markov Random Fields (MRFs) are widely used to model problems such as image denoising, stereo reconstruction, and scene segmentation. The core task is to find a labeling that minimizes a global energy function consisting of unary and pairwise potentials. When pairwise potentials follow a semi-metric—a symmetric distance function that may violate the triangle inequality—the optimization becomes NP-hard.

Existing approaches typically offer a trade-off: move-making algorithms (e.g., $\alpha$-expansion) are efficient but prone to local minima in non-metric spaces, whereas message-passing or LP-based solvers (e.g., TRW-S) provide strong theoretical guarantees at a high computational cost. This work proposes a method that combines the speed of graph cuts with the accuracy of LP relaxations.

Methodology

The proposed approach centers on the hierarchical decomposition of the label space using $r$-Hierarchically Well-Separated Trees ($r$-HSTs).

Metric Approximation

A complex semi-metric distance function is approximated using a mixture of $r$-HSTs. In an $r$-HST, labels are represented as leaves, and the distance between any two labels is defined by the length of the unique path connecting them in the tree. This structure transforms a flat label space into a manageable hierarchy.

Figure 1: An example of an r-HST structure used to approximate label distances.

Hierarchical Move-Making

The algorithm proceeds through the levels of the tree. It solves subproblems at the leaf level and moves upward toward the root. Each "move" in this hierarchy is formulated as an $st$-MINCUT problem, allowing for extremely efficient computation. To handle non-submodular moves inherent in semi-metrics, the authors employ a primal-dual scheme within the move-making framework, ensuring that the global energy never increases.

Mixture of Trees and Refinement

To improve the approximation quality, the method learns a distribution over multiple trees. A "Hard EM" refinement step is also introduced to iteratively adjust tree metrics based on current labelings, further narrowing the gap to the optimal solution.

Experimental Results

The algorithm was evaluated on synthetic grid MRFs and real-world tasks including scene registration, stereo reconstruction, and image denoising.

Performance and Efficiency

Quantitative results demonstrate that the proposed method consistently outperforms standard move-making techniques like $\alpha$-expansion and $\alpha\beta$-swap in terms of final energy. Crucially, it achieves energy levels nearly identical to TRW-S while being approximately 60-70 times faster on synthetic benchmarks.

Figure 5: Quantitative comparison of energy and timing across various algorithms.

Real-World Applications

In stereo and denoising tasks, the hierarchical approach produced lower-energy solutions than traditional graph-cut methods. While TRW-S occasionally found slightly lower energies in specific denoising scenarios, the computational overhead of TRW-S makes it less practical for large-scale applications compared to the proposed hierarchical graph-cut framework.

Conclusion

This paper presents a fast and accurate framework for MAP estimation in semi-metric MRFs. By utilizing $r$-HSTs and hierarchical graph cuts, the method provides a scalable alternative to general-purpose LP solvers without sacrificing solution quality. Future work includes extending this approach to higher-order potentials and exploring more sophisticated tree-learning techniques.

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