On morphological hierarchical representations for image processing and spatial data clustering

Pierre Soille, Laurent Najman

Abstract: Hierarchical data representations in the context of classification and data clustering were put forward during the fifties. Recently, hierarchical image representations have gained renewed interest for segmentation purposes. In this paper, we briefly survey fundamental results on hierarchical clustering and then detail recent paradigms developed for the hierarchical representation of images in the framework of mathematical morphology: constrained connectivity and ultrametric watersheds. Constrained connectivity can be viewed as a way to constrain an initial hierarchy in such a way that a set of desired constraints are satisfied. The framework of ultrametric watersheds provides a generic scheme for computing any hierarchical connected clustering, in particular when such a hierarchy is constrained. The suitability of this framework for solving practical problems is illustrated with applications in remote sensing.

Introduction

Published in 2012 by Pierre Soille and Laurent Najman, this work serves as a formal bridge between classical hierarchical clustering and mathematical morphology (MM). It addresses the challenge of representing images as hierarchies to facilitate multi-scale segmentation, introducing tools like "constrained connectivity" and "ultrametric watersheds" to solve long-standing issues such as the "chaining effect."

The Problem: Scale and the Chaining Effect

In image processing, segmentation depends heavily on scale; a single leaf may be a segment at one resolution, while an entire forest is the segment at another. Hierarchical representations, such as trees, are ideal for capturing this multi-scale nature. However, they face two major hurdles:

  1. The Chaining Effect: In standard hierarchical clustering (like single-linkage), two distinct regions can be merged prematurely if a thin "bridge" of noise or a gradual ramp of intermediate pixels exists between them.
  2. Visualization and Filtering: While a tree structure is mathematically sound, it is difficult to interpret spatially. Applying filters to these abstract structures can also be computationally intensive.

Hierarchical Framework and Connectivity

The authors build their framework on graph theory, where pixels are nodes and edges represent dissimilarity.

  • $\alpha$-connectivity: This is the image-processing equivalent of single-linkage clustering. Pixels are grouped if they can be reached via a path where every step has a dissimilarity $\le \alpha$.
  • Constrained Connectivity: To combat the chaining effect, the authors introduce a global range constraint ($\omega$). A component is only formed if the total variation within it does not exceed $\omega$, preventing "leaks" across gradual transitions.
  • $\alpha_n$-connectivity: A more restrictive rule requiring a pixel to have at least $n$ neighbors within the $\alpha$ threshold before merging, effectively ignoring thin, noisy bridges.
A dendrogram representing a hierarchical clustering where the vertical axis denotes the level $\lambda$ of merging.

Ultrametric Watersheds and Saliency Maps

A key contribution of the paper is the concept of ultrametric watersheds. Instead of relying solely on abstract dendrograms, the authors propose stacking the contours of every level of the hierarchy into a single image. The "higher" or more persistent a boundary is within the hierarchy, the brighter it appears in this "saliency map."

This transformation allows a hierarchy to be treated as an image where pixel values indicate boundary importance. The paper explains that any hierarchical clustering defines an "ultrametric distance" between points, a mathematical property that allows the hierarchy to be viewed as a series of nested partitions.

Key Insights and Results

  • Hierarchy as an Image: By using ultrametric watersheds, a hierarchy becomes a spatial saliency map, making it intuitive for human interpretation and easier to process with standard image filters.
  • Mathematical Equivalence: The paper proves that dendrograms, minimum spanning trees (MSTs), and saliency maps are theoretically equivalent ways to handle hierarchical connected clustering.
  • Remote Sensing Applications: The framework was tested on high-resolution Quickbird imagery. The results demonstrated that the hierarchy could successfully segment complex urban environments, distinguishing individual buildings from larger city blocks while remaining robust to noise through $\alpha_n$-connectivity.

Conclusion

Soille and Najman provide a robust mathematical foundation for hierarchical image representation. By linking ultrametrics to morphological watersheds, they offer a way to navigate the scale-space of an image efficiently. While challenges remain in perfectly identifying transition pixels in low-contrast images, the introduction of alpha-trees and union-find algorithms provides a promising path for processing massive spatial datasets.

Summary updated

Abstract

Hierarchical data representations in the context of classi cation and data clustering were put forward during the fties. Recently, hierarchical image representations have gained renewed interest for segmentation purposes. In this paper, we briefly survey fundamental results on hierarchical clustering and then detail recent paradigms developed for the hierarchical representation of images in the framework of mathematical morphology: constrained connectivity and ultrametric watersheds. Constrained connectivity can be viewed as a way to constrain an initial hierarchy in such a way that a set of desired constraints are satis ed. The framework of ultrametric watersheds provides a generic scheme for computing any hierarchical connected clustering, in particular when such a hierarchy is constrained. The suitability of this framework for solving practical problems is illustrated with applications in remote sensing.
BibTeX
@inproceedings{soille2010morphological,
  author = {Pierre Soille and Laurent Najman},
  title = {{On morphological hierarchical representations for image processing and spatial data clustering}},
  booktitle = {WADGMM},
  year = {2010},
  url = {https://openreview.net/forum?id=XKkZ-SUxo_},
}
Figure