Topographical Tools for Filtering and Segmentation 1

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.

• Notations xiiiIntroduction xxviiPart 1. Getting Started 1Chapter 1. A Primer to Flooding, Razing and Watersheds 31.1. Topographic reliefs and topographic features 31.1.1. Images seen as topographic reliefs and inversely 31.1.2. Topographic features 51.1.3. Modeling a topographic relief as a weighted graph 81.2. Flooding, razing and morphological filters 101.2.1. The principle of duality 101.2.2. Dominated flooding and razing 101.2.3. Flooding, razing and catchment zones of a topographic relief 161.3. Catchment zones of flooded surfaces 181.3.1. Filtering and segmenting 181.3.2. Reducing the oversegmentation with markers 191.4. The waterfall hierarchy 261.4.1. Overflows between catchment basins 261.5. Size-driven hierarchies 281.6. Separating overlapping particles in n dimensions 311.7. Catchment zones and lakes of region neighborhood graphs 331.8. Conclusion 37Chapter 2. Watersheds and Flooding: a Segmentation Golden Braid 392.1. Watersheds, offsprings and parallel branches 402.2. Flooding and connected operators 432.3. Connected operators and hierarchies 452.4. Hierarchical segmentation: extinction values 47Chapter 3. Mathematical Notions 493.1. Summary of the chapter 493.2. Complete lattices 493.2.1. Partial order and partially ordered sets 493.2.2. Upper and lower bounds 503.2.3. Complete lattices 503.2.4. Dyadic relations on a complete lattice 513.3. Operators between complete lattices 513.3.1. Definition of an operator 513.3.2. Properties of the operators 523.3.3. Erosion and dilation 523.3.4. Opening and closing 533.4. The adjunction: a cornerstone of mathematical morphology 533.4.1. Adjoint erosions and dilations 533.4.2. Increasingness 533.4.3. Unicity 533.4.4. Composition 543.4.5. Dual operators 543.5. Openings and closings 543.5.1. Definitions 543.5.2. Elements with the same erosion or the same dilation 553.5.3. The invariants of an opening or a closing 553.6. Complete lattices of functions 553.6.1. Definitions 553.6.2. Infimum and supremum 56Part 2. The Topography of Weighted Graphs 57Chapter 4. Weighted Graphs 594.1. Summary of the chapter 594.2. Reminders on graphs 604.2.1. Directed and undirected graphs 604.3. Weight distributions on the nodes or edges of a graph 624.3.1. Duality 634.3.2. Erosions and dilations, openings, closings 634.3.3. Labels 664.4. Exploring the topography of graphs by following a drop of water 664.5. Node-weighted graphs 674.5.1. Flat zones and regional minima 674.5.2. Flowing paths and catchment zones 674.6. Edge-weighted graphs 694.6.1. Flat zones and regional minima 694.6.2. Flowing paths and catchment zones 694.6.3. Even zones and regional minima 714.7. Comparing the topography of node-weighted graphs and edge-weighted graphs 72Chapter 5. Flowing Graphs 735.1. Summary of the chapter 735.2. Towards a convergence between node- and edge-weighted graphs 745.2.1. The flowing edges in a node-weighted graph G(ν, nil) 745.2.2. The flowing edges in an edge-weighted graph G(nil, η) 755.2.3. Flowing graphs 765.3. The flowing adjunction 765.4. Flowing edges under closer scrutiny 775.4.1. Relations between the flowing edges of G(ν, nil) and G(nil, δenν) 775.4.2. Relations between the flowing edges of G(nil, η) and G(εneη, nil) 785.4.3. Chaining the inclusions between flowing edges 785.4.4. Criteria characterizing flowing graphs 795.4.5. Transforming a node- or edge-weighted graph into a flowing graph 815.4.6. The invariance domains of γe and ϕn 835.4.7. Particular flowing graphs 875.5. Illustration as a hydrographic model 885.5.1. A hydrographic model of tanks and pipes 885.5.2. Associating an “edge unstable” tank network with an arbitrary node-weighted graph G(ν, nil) 905.5.3. Associating a “node unstable” tank network with an arbitrary edge-weighted graph G(nil, η) 915.5.4. Chaining the operations 92Chapter 6. The Topography of Digraphs 976.1. Summary of the chapter 976.1.1. General digraphs 986.1.2. Digraphs without perpetuum mobile configurations 986.2. Status report 986.2.1. Case of node-weighted graphs 996.2.2. Case of edge-weighted graphs 996.3. The topography of unweighted digraphs 1006.3.1. Notations 1006.3.2. Smooth zones, dead ends, flat zones and black holes of digraphs 1016.4. The topography of gravitational digraphs 1056.4.1. No “perpetuum mobile” 1056.4.2. Defining and propagating labels 1076.4.3. A dead leaves model of catchment zones 1136.4.4. Examples of gravitational graphs 1226.4.5. The topography of weighted graphs interpreted in the light of the derived digraphs 122Part 3. Reducing the Overlapping of Catchment Zones 125Chapter 7. Measuring the Steepness of Flowing Paths 1277.1. Summary of the chapter 1277.2. Why do the catchment zones overlap? 1287.2.1. Relation between the catchment zones and the flowing paths 1287.2.2. Comparing the steepness of flowing paths 1287.2.3. The redundancy between node and edge weights 1297.2.4. General flow digraphs 1307.3. The lexicographic pre-order relation of length k 1317.3.1. Prolonging flowing paths into paths of infinite length 1317.3.2. Comparing the steepness of two flowing paths 1327.3.3. Properties of ∞ − steep paths 134Chapter 8. Pruning a Flow Digraph 1378.1. Summary of the chapter 1378.1.1. Transforming a node- or edge-weighted graph into a node-weighted flowing digraph (reminder) 1378.1.2. Global pruning 1388.1.3. Local pruning 1388.2. The pruning operator 1388.2.1. Two operators on flow digraphs 1398.2.2. Pruning by concatenating both operators 1408.2.3. Properties of pruning 1428.2.4. A variant of pruning 1468.2.5. Local pruning8.3. Evolution of catchment zones with pruning 1478.3.1. Analyzing a digital elevation model 148Chapter 9. Constructing an ∞ - steep Digraph by Flooding 1559.1. Summary of the chapter 1559.2. Characterization of ∞ − steep graphs 1569.3. The core-expanding flooding algorithm 1569.3.1. The first version of the core-expanding algorithm 1579.3.2. The second version of the core-expanding algorithm 1609.3.3. The third version of the core-expanding algorithm 1649.3.4. The last version of the core-expanding algorithm, constructing a partial ∞ − steep flowing graph 167Chapter 10. Creating Steep Watershed Partitions 16910.1. Summary of the chapter 16910.2. Creating watershed partitions with the core-expanding algorithm 16910.2.1. Illustration of the HQ algorithm applied to node-weighted graphs 17110.3. Propagating labels while pruning the digraph 17210.3.1. Constructing a watershed partition during pruning 17310.4. Pruning or flooding: two ways for catchment zones to grow 176Chapter 11. An Historical Intermezzo 17911.1. Watersheds: the early days 17911.1.1. The level-by-level construction of watersheds 18011.1.2. A hierarchical queue watershed algorithm 18111.2. A watershed as the SKIZ for the topographic distance 18111.2.1. The topographic distance 18111.3. Convergence into a unique algorithm of three research streams 18211.3.1. Three formulations of watershed partitions, one algorithm 18211.3.2. Discussion 183Part 4. Segmenting with Dead Leaves Partitions 185Chapter 12. Intermezzo: Encoding the Digraph Associated with an Image 18712.1. Summary of the theoretical developments seen so far 18712.2. Summary of the chapter 18812.3. Representing a node-weighted digraph as two images 18812.3.1. The encoding of the digraph associated with an image 18812.3.2. Operators acting on node-weighted digraphs 19012.4. Defining labels 19212.4.1. Operators on unweighted unlabeled digraphs 19312.4.2. Operators on labeled unweighted digraphs 19412.4.3. Operators on weighted and labeled digraphs 198Chapter 13. Two Paradigms for Creating a Partition or a Partial Partition on a Graph 20313.1. Summary of the chapter 20313.2. Setting up a common stage for node- and edge-weighted graphs 20313.3. A brief tool inventory 20413.3.1. Operators making no use of the node weights 20413.3.2. Operators propagating labels 20413.3.3. Operators making use of the node weights and the graph structure 20513.4. Dead leaves tessellations versus tilings: two paradigms 20513.5. Extracting catchment zones containing a particular node 20613.5.1. Core expansion versus pruning algorithms 20613.5.2. Illustration of the pruning algorithm 20713.6. Catchment zones versus catchment basins 209Chapter 14. Dead Leaves Segmentation 21114.1. Summary of the chapter 21114.2. Segmenting with a watershed 21114.2.1. Segmenting with watershed partitions 21114.2.2. A crossroad of several methods 21314.3. The evolution of a dead leaves tessellation with pruning 21414.4. Local correction of overlapping zones 21714.4.1. Pruning analysis 21714.4.2. Local pruning for reducing overlapping zones 21914.4.3. A local core-expanding algorithm for reducing overlapping zones 22114.5. Local correction of the overlapping zones on a DEM 22114.5.1. Local core-expanding algorithm for reducing overlapping zones 22514.5.2. Advantage of the two-step construction of a dead leaves tessellation 22714.6. Segmentation of some marked regions 23114.6.1. Segmenting the domain and extracting the objects of interest 23214.6.2. Extraction of the marked catchment zones and local correction of errors 233Chapter 15. Propagating Segmentations 24115.1. Summary of the chapter 24115.2. Step-by-step segmentation 24115.2.1. Principle of the method 24115.2.2. Segmentation of blood cells 24215.2.3. Segmentation of an electronic circuit 24315.3. Marker-based segmentation 245Appendix 247References 259Index 267