Skip to main content

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

E-Book

$124.99

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

Fernand Meyer

ISBN: 978-1-119-57954-0 January 2019 Wiley-ISTE 314 Pages

Description

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.

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