Topographical Tools for Filtering and Segmentation 1: Watersheds on Node- or Edge-weighted Graphs

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.

Table of Contents:
Notations xiii Introduction xxvii Part 1. Getting Started 1 Chapter 1. A Primer to Flooding, Razing and Watersheds 3 1.1. Topographic reliefs and topographic features 3 1.1.1. Images seen as topographic reliefs and inversely 3 1.1.2. Topographic features 5 1.1.3. Modeling a topographic relief as a weighted graph 8 1.2. Flooding, razing and morphological filters 10 1.2.1. The principle of duality 10 1.2.2. Dominated flooding and razing 10 1.2.3. Flooding, razing and catchment zones of a topographic relief 16 1.3. Catchment zones of flooded surfaces 18 1.3.1. Filtering and segmenting 18 1.3.2. Reducing the oversegmentation with markers 19 1.4. The waterfall hierarchy 26 1.4.1. Overflows between catchment basins 26 1.5. Size-driven hierarchies 28 1.6. Separating overlapping particles in n dimensions 31 1.7. Catchment zones and lakes of region neighborhood graphs 33 1.8. Conclusion 37 Chapter 2. Watersheds and Flooding: a Segmentation Golden Braid 39 2.1. Watersheds, offsprings and parallel branches 40 2.2. Flooding and connected operators 43 2.3. Connected operators and hierarchies 45 2.4. Hierarchical segmentation: extinction values 47 Chapter 3. Mathematical Notions 49 3.1. Summary of the chapter 49 3.2. Complete lattices 49 3.2.1. Partial order and partially ordered sets 49 3.2.2. Upper and lower bounds 50 3.2.3. Complete lattices 50 3.2.4. Dyadic relations on a complete lattice 51 3.3. Operators between complete lattices 51 3.3.1. Definition of an operator 51 3.3.2. Properties of the operators 52 3.3.3. Erosion and dilation 52 3.3.4. Opening and closing 53 3.4. The adjunction: a cornerstone of mathematical morphology 53 3.4.1. Adjoint erosions and dilations 53 3.4.2. Increasingness 53 3.4.3. Unicity 53 3.4.4. Composition 54 3.4.5. Dual operators 54 3.5. Openings and closings 54 3.5.1. Definitions 54 3.5.2. Elements with the same erosion or the same dilation 55 3.5.3. The invariants of an opening or a closing 55 3.6. Complete lattices of functions 55 3.6.1. Definitions 55 3.6.2. Infimum and supremum 56 Part 2. The Topography of Weighted Graphs 57 Chapter 4. Weighted Graphs 59 4.1. Summary of the chapter 59 4.2. Reminders on graphs 60 4.2.1. Directed and undirected graphs 60 4.3. Weight distributions on the nodes or edges of a graph 62 4.3.1. Duality 63 4.3.2. Erosions and dilations, openings, closings 63 4.3.3. Labels 66 4.4. Exploring the topography of graphs by following a drop of water 66 4.5. Node-weighted graphs 67 4.5.1. Flat zones and regional minima 67 4.5.2. Flowing paths and catchment zones 67 4.6. Edge-weighted graphs 69 4.6.1. Flat zones and regional minima 69 4.6.2. Flowing paths and catchment zones 69 4.6.3. Even zones and regional minima 71 4.7. Comparing the topography of node-weighted graphs and edge-weighted graphs 72 Chapter 5. Flowing Graphs 73 5.1. Summary of the chapter 73 5.2. Towards a convergence between node- and edge-weighted graphs 74 5.2.1. The flowing edges in a node-weighted graph G(ν, nil) 74 5.2.2. The flowing edges in an edge-weighted graph G(nil, η) 75 5.2.3. Flowing graphs 76 5.3. The flowing adjunction 76 5.4. Flowing edges under closer scrutiny 77 5.4.1. Relations between the flowing edges of G(ν, nil) and G(nil, δenν) 77 5.4.2. Relations between the flowing edges of G(nil, η) and G(εneη, nil) 78 5.4.3. Chaining the inclusions between flowing edges 78 5.4.4. Criteria characterizing flowing graphs 79 5.4.5. Transforming a node- or edge-weighted graph into a flowing graph 81 5.4.6. The invariance domains of γe and ϕn 83 5.4.7. Particular flowing graphs 87 5.5. Illustration as a hydrographic model 88 5.5.1. A hydrographic model of tanks and pipes 88 5.5.2. Associating an “edge unstable” tank network with an arbitrary node-weighted graph G(ν, nil) 90 5.5.3. Associating a “node unstable” tank network with an arbitrary edge-weighted graph G(nil, η) 91 5.5.4. Chaining the operations 92 Chapter 6. The Topography of Digraphs 97 6.1. Summary of the chapter 97 6.1.1. General digraphs 98 6.1.2. Digraphs without perpetuum mobile configurations 98 6.2. Status report 98 6.2.1. Case of node-weighted graphs 99 6.2.2. Case of edge-weighted graphs 99 6.3. The topography of unweighted digraphs 100 6.3.1. Notations 100 6.3.2. Smooth zones, dead ends, flat zones and black holes of digraphs 101 6.4. The topography of gravitational digraphs 105 6.4.1. No “perpetuum mobile” 105 6.4.2. Defining and propagating labels 107 6.4.3. A dead leaves model of catchment zones 113 6.4.4. Examples of gravitational graphs 122 6.4.5. The topography of weighted graphs interpreted in the light of the derived digraphs 122 Part 3. Reducing the Overlapping of Catchment Zones 125 Chapter 7. Measuring the Steepness of Flowing Paths 127 7.1. Summary of the chapter 127 7.2. Why do the catchment zones overlap? 128 7.2.1. Relation between the catchment zones and the flowing paths 128 7.2.2. Comparing the steepness of flowing paths 128 7.2.3. The redundancy between node and edge weights 129 7.2.4. General flow digraphs 130 7.3. The lexicographic pre-order relation of length k 131 7.3.1. Prolonging flowing paths into paths of infinite length 131 7.3.2. Comparing the steepness of two flowing paths 132 7.3.3. Properties of ∞ − steep paths 134 Chapter 8. Pruning a Flow Digraph 137 8.1. Summary of the chapter 137 8.1.1. Transforming a node- or edge-weighted graph into a node-weighted flowing digraph (reminder) 137 8.1.2. Global pruning 138 8.1.3. Local pruning 138 8.2. The pruning operator 138 8.2.1. Two operators on flow digraphs 139 8.2.2. Pruning by concatenating both operators 140 8.2.3. Properties of pruning 142 8.2.4. A variant of pruning 146 8.2.5. Local pruning 8.3. Evolution of catchment zones with pruning 147 8.3.1. Analyzing a digital elevation model 148 Chapter 9. Constructing an ∞ - steep Digraph by Flooding 155 9.1. Summary of the chapter 155 9.2. Characterization of ∞ − steep graphs 156 9.3. The core-expanding flooding algorithm 156 9.3.1. The first version of the core-expanding algorithm 157 9.3.2. The second version of the core-expanding algorithm 160 9.3.3. The third version of the core-expanding algorithm 164 9.3.4. The last version of the core-expanding algorithm, constructing a partial ∞ − steep flowing graph 167 Chapter 10. Creating Steep Watershed Partitions 169 10.1. Summary of the chapter 169 10.2. Creating watershed partitions with the core-expanding algorithm 169 10.2.1. Illustration of the HQ algorithm applied to node-weighted graphs 171 10.3. Propagating labels while pruning the digraph 172 10.3.1. Constructing a watershed partition during pruning 173 10.4. Pruning or flooding: two ways for catchment zones to grow 176 Chapter 11. An Historical Intermezzo 179 11.1. Watersheds: the early days 179 11.1.1. The level-by-level construction of watersheds 180 11.1.2. A hierarchical queue watershed algorithm 181 11.2. A watershed as the SKIZ for the topographic distance 181 11.2.1. The topographic distance 181 11.3. Convergence into a unique algorithm of three research streams 182 11.3.1. Three formulations of watershed partitions, one algorithm 182 11.3.2. Discussion 183 Part 4. Segmenting with Dead Leaves Partitions 185 Chapter 12. Intermezzo: Encoding the Digraph Associated with an Image 187 12.1. Summary of the theoretical developments seen so far 187 12.2. Summary of the chapter 188 12.3. Representing a node-weighted digraph as two images 188 12.3.1. The encoding of the digraph associated with an image 188 12.3.2. Operators acting on node-weighted digraphs 190 12.4. Defining labels 192 12.4.1. Operators on unweighted unlabeled digraphs 193 12.4.2. Operators on labeled unweighted digraphs 194 12.4.3. Operators on weighted and labeled digraphs 198 Chapter 13. Two Paradigms for Creating a Partition or a Partial Partition on a Graph 203 13.1. Summary of the chapter 203 13.2. Setting up a common stage for node- and edge-weighted graphs 203 13.3. A brief tool inventory 204 13.3.1. Operators making no use of the node weights 204 13.3.2. Operators propagating labels 204 13.3.3. Operators making use of the node weights and the graph structure 205 13.4. Dead leaves tessellations versus tilings: two paradigms 205 13.5. Extracting catchment zones containing a particular node 206 13.5.1. Core expansion versus pruning algorithms 206 13.5.2. Illustration of the pruning algorithm 207 13.6. Catchment zones versus catchment basins 209 Chapter 14. Dead Leaves Segmentation 211 14.1. Summary of the chapter 211 14.2. Segmenting with a watershed 211 14.2.1. Segmenting with watershed partitions 211 14.2.2. A crossroad of several methods 213 14.3. The evolution of a dead leaves tessellation with pruning 214 14.4. Local correction of overlapping zones 217 14.4.1. Pruning analysis 217 14.4.2. Local pruning for reducing overlapping zones 219 14.4.3. A local core-expanding algorithm for reducing overlapping zones 221 14.5. Local correction of the overlapping zones on a DEM 221 14.5.1. Local core-expanding algorithm for reducing overlapping zones 225 14.5.2. Advantage of the two-step construction of a dead leaves tessellation 227 14.6. Segmentation of some marked regions 231 14.6.1. Segmenting the domain and extracting the objects of interest 232 14.6.2. Extraction of the marked catchment zones and local correction of errors 233 Chapter 15. Propagating Segmentations 241 15.1. Summary of the chapter 241 15.2. Step-by-step segmentation 241 15.2.1. Principle of the method 241 15.2.2. Segmentation of blood cells 242 15.2.3. Segmentation of an electronic circuit 243 15.3. Marker-based segmentation 245 Appendix 247 References 259 Index 267

About the Author :
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.