Planar Ultrametric Rounding for Image Segmentation

Charless Fowlkes, Julian YarkonyarXiv 2015 · arXiv

Abstract

This paper introduces a principled framework for hierarchical image segmentation by formulating it as an "ultrametric rounding" problem on planar graphs. By leveraging a dual cutting plane algorithm and the unique properties of planar graphs, the authors provide an efficient solver that produces high-quality, globally consistent hierarchies with strong optimality guarantees. The approach transforms the NP-hard multicut problem into a solvable Linear Program (LP) using Minimum Cost Perfect Matching, offering a mathematically rigorous alternative to traditional greedy agglomerative methods.

Introduction

Image segmentation—the process of partitioning an image into semantically meaningful regions—is a fundamental task in computer vision. Hierarchical segmentation extends this by creating a nested "tree" of partitions, capturing details from fine textures to coarse objects. Mathematically, such a hierarchy is represented as an ultrametric, a distance metric satisfying a strict version of the triangle inequality.

However, finding an optimal ultrametric that fits noisy image data is computationally intensive. While the "multicut" problem offers a powerful partitioning framework, it is generally NP-hard. Furthermore, ensuring that partitions at different hierarchical levels remain "nested" (consistent) adds significant complexity. This paper addresses these challenges by focusing on planar graphs, which naturally represent 2D image structures.

Methodology

The core of the proposed method is the formulation of hierarchical segmentation as an Integer Linear Program (ILP), which is subsequently relaxed into a manageable Linear Program (LP).

The Planar Advantage

For planar graphs, where pixels or superpixels connect only to immediate neighbors, the problem of identifying violated constraints in the model reduces to a Minimum Cost Perfect Matching (MCPM) problem. Unlike general multicuts, MCPM can be solved exactly in polynomial time using algorithms such as Blossom V.

Dual Cutting Plane Scheme

To handle the exponential number of potential constraints, the authors employ a dual cutting plane scheme. The algorithm starts with a minimal set of constraints and iteratively adds only the most "violated" ones. This process is augmented by clever slack variables ($\alpha$ and $\beta$) that allow the solver to explore the partition space more flexibly, accelerating convergence.

Linear combination of cut vectors and matrix formulation

Hierarchical Consistency and Ultrametrics

A key contribution is the enforcement of hierarchical consistency. Solving for each level of a hierarchy independently often results in "broken" hierarchies where boundaries appear and disappear inconsistently across scales. By enforcing the ultrametric constraint, the authors ensure that partitions are strictly nested.

Hierarchical decomposition of cuts into nested partitions

The LP relaxation used is remarkably "tight," with the gap between the approximate solution and the true mathematical optimum typically remaining below 0.1%. This provides a level of mathematical rigor often absent in heuristic segmentation methods.

Experimental Results

The algorithm was evaluated on the Berkeley Segmentation Data Set (BSDS). Superpixels were generated using the oriented watershed transform on gPb edge detector outputs.

  • Accuracy: The proposed "UM" (Ultrametric) rounding performs comparably to the state-of-the-art Ultrametric Contour Map (UCM) algorithm in precision-recall, with notable improvements in high-precision (coarser) segmentations.
  • Optimality and Speed: In tests across 2200 multicut instances, the solver consistently produced solutions equal to or better than independent layer solvers while maintaining perfect consistency. Most instances converged in fewer than 100 iterations, typically under 10 seconds.
  • Qualitative Performance: Visual analysis confirms that the method preserves semantic object parts (e.g., bird wings or leaf structures) across levels, whereas independent clustering often merges foreground objects into background clutter prematurely.

Conclusion

The planar ultrametric rounding framework demonstrates that planarity is a "superpower" in image processing, turning theoretically impossible tasks into efficient combinatorial problems. While currently limited to 2D planar graphs, the method sets a high bar for hierarchical consistency and optimality. Future work may involve extending these principles to 3D volumes or non-grid data, particularly in domains like biological imaging where noise levels are high and under-segmentation is costly.

Summary updated

BibTeX
@misc{fowlkes2015planar,
  author = {Charless Fowlkes and Julian Yarkony},
  title = {{Planar Ultrametric Rounding for Image Segmentation}},
  year = {2015},
  eprint = {1507.02407},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.02407},
}
Figure