Ultrametric watersheds: a bijection theorem for hierarchical edge-segmentation

Laurent Najman

Abstract

This paper establishes a formal mathematical bridge between hierarchical image segmentation and "ultrametric watersheds." By proving a bijection (a perfect one-to-one correspondence) between these two concepts, the author shows that any complex hierarchy of regions can be represented as a single edge-weighted graph. This theoretical breakthrough enables more efficient algorithms and a unified framework for multi-scale image analysis.

Introduction

Image segmentation is the process of partitioning an image into meaningful regions. However, a single partition is rarely sufficient for complex scenes; researchers often require a hierarchical segmentation—a nested set of partitions representing the image at different levels of detail, from fine textures to large objects.

Historically, a disconnect has existed between the "spatial" view of segmentation (maps of regions) and the "hierarchical" view (dendrograms or trees). This heterogeneity makes it difficult to compare different hierarchies or apply standard image-processing filters to the hierarchy itself. This paper seeks to make the problem "homogeneous" by representing an entire hierarchy as a specific type of image—an edge-weighted graph—without losing any information.

The Mathematical Bridge: Ultrametric Watersheds

The core contribution of this work is the Bijection Theorem (Theorem 13). It operates within the framework of edge-weighted graphs, where pixels are nodes and the "cost" of crossing between pixels is stored on the edges.

The hierarchical segmentation pipeline: (a) Original medical image, (b) the resulting dendrogram, (c) a specific segmentation level, and (d) the ultrametric watershed (saliency map) representing the entire hierarchy.

The author defines ultrametric watersheds as a specific subclass of topological watersheds where the weights on the "minima" (the core of the regions) are zero. Theorem 13 proves that the set of all possible indexed hierarchical segmentations is mathematically equivalent to the set of all ultrametric watersheds.

As shown in the figure above, this means that a "saliency map" (d)—often used just for visualization—is actually a complete mathematical representation of the hierarchy. The dendrogram (b) and any specific segmentation level (c) can be directly derived from this single edge-weighted graph.

Key Insights and Algorithmic Efficiency

  • Homogeneity: By representing a hierarchy as an edge-weighted graph, "hierarchy-finding" becomes a graph-weighting problem. This allows for the application of rigorous distance metrics to compare different hierarchical models.
  • Reversing the Workflow: Traditionally, one computes a hierarchy and then derives a map. This theorem implies one can compute the map (the ultrametric watershed) directly, extracting the dendrogram only if needed.
  • Quasi-Linear Performance: To demonstrate the power of this theory, the author revisits "constrained connectivity." By using the ultrametric watershed framework and component trees, the entire hierarchy can be computed in quasi-linear time. This is a significant improvement over previous methods that required computing each level of the hierarchy sequentially.

Conclusion

By proving the bijection between hierarchies and ultrametric watersheds, this paper provides a robust theoretical foundation for multi-scale morphological image processing. It corrects existing misconceptions in the literature regarding saliency maps and offers a path toward more efficient, scale-aware segmentation algorithms. Future work will explore extending this framework to optimize specific energy functions and investigating non-nested, overlapping region hierarchies.

Summary updated

Abstract

We study hierarchical segmentation in the framework of edge-weighted graphs. We define ultrametric watersheds as topological watersheds null on the minima. We prove that there exists a bijection between the set of ultrametric watersheds and the set of hierarchical segmentations. We end this paper by showing how to use the proposed framework in practice in the example of constrained connectivity; in particular it allows to compute such a hierarchy following a classical watershed-based morphological scheme, which provides an efficient algorithm to compute the whole hierarchy.
BibTeX
@article{najman2011ultrametric,
  author = {Laurent Najman},
  title = {{Ultrametric watersheds: a bijection theorem for hierarchical edge-segmentation}},
  journal = {J. Math. Imaging Vis.},
  year = {2011},
  url = {https://openreview.net/forum?id=hOCJRaU54iU},
}
Figure