11801nam 2200529 450 991082981980332120240219171218.01-119-57955-41-119-57951-11-119-57954-610.1002/9781119579519(CKB)4100000007586972(MiAaPQ)EBC5649556(CaBNVSL)mat08654026(IDAMS)0b00006488baa875(IEEE)8654026(EXLCZ)99410000000758697220190417d2019 uy engur|n|||||||||txtrdacontentcrdamediacrrdacarrierTopographical tools for filtering and segmentation.1Watersheds on node- or edge-weighted graphs /Fernand MeyerLondon, United Kingdom :ISTE, Ltd.,[2019]1 online resource1-78630-157-1 Includes bibliographical references and index.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.Relief modelsTopographical drawingRelief models.Topographical drawing.551.41Meyer Fernand1952-1665886CaBNVSLCaBNVSLCaBNVSLBOOK9910829819803321Topographical tools for filtering and segmentation4024801UNINA