Topographical Tools for Filtering and Segmentation 1

Watersheds on Node- or Edge-weighted Graphs

Topographical Tools for Filtering and Segmentation 1

Fernand Meyer, MINES ParisTech, France

ISBN : 9781786301574

Publication Date : January 2019

Hardcover 314 pp

155.00 USD



Mathematical morphology has developed a powerful methodology for segmenting images, based on connected filters and watersheds. We have chosen the abstract framework of node- or edge-weighted graphs for an extensive mathematical and algorithmic description of these tools.

Volume 1 is devoted to watersheds. The topography of a graph appears by observing the evolution of a drop of water moving from node to node on a weighted graph, along flowing paths, until it reaches regional minima. The upstream nodes of a regional minimum constitute its catchment zone.

The catchment zones may be constructed independently of each other and locally, in contrast with the traditional approach where the catchment basins have to be constructed all at the same time. Catchment zones may overlap, and thus, a new segmentation paradigm is proposed in which catchment zones cover each other according to a priority order. The resulting partition may then be corrected, by local and parallel treatments, in order to achieve the desired precision.


Part 1. Getting Started
1. A Primer to Flooding, Razing and Watersheds.
2. Watersheds and Flooding: a Segmentation Golden Braid.
3. Mathematical Notions.

Part 2. The Topography of Weighted Graphs
4. Weighted Graphs.
5. Flowing Graphs.
6. The Topography of Digraphs.

Part 3. Reducing the Overlapping of Catchment Zones
7. Measuring the Steepness of Flowing Paths.
8. Pruning a Flow Digraph.
9. Constructing an infinity-steep Digraph by Flooding.
10. Creating Steep Watershed Partitions.
11. An Historical Intermezzo.

Part 4. Segmenting with Dead Leaves Partitions
12. Intermezzo: Encoding the Digraph Associated with an Image.
13. Two Paradigms for Creating a Partition or a Partial Partition on a Graph.
14. Dead Leaves Segmentation.
15. Propagating Segmentations.

About the authors

Fernand Meyer has been working at the Center for Mathematical Morphology of MINES ParisTech since 1975. He participated actively in the development of mathematical morphology, particularly in the field of segmentation and filtering.