Rights Contact Login For More Details
More About This Title Topographical Tools for Filtering and Segmentation 1 - Watersheds on Node- or Edge-weighted Graphs
English
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.
English
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.
English
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
