Topographical Tools for Filtering and Segmentation 2

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 xiIntroduction xxvPart 1. Flooding 1Chapter 1. Modelling Flooding in Edgeor Node-weighted Graphs 31.1. Summary of the chapter 31.2. The importance of flooding 41.2.1. Flooding creates lakes 41.2.2. Flooding for controlling watershed segmentation 41.2.3. Flooding, razing, leveling and flattening 51.3. Description of the flood covering a topographic surface 61.3.1. Observing the same flooding on two levels of abstraction 61.3.2. Modeling the two scales of flooding: at the pixel level or at the region level 71.3.3. Modeling a flooded topographic surface as a node-weighted graph 81.3.4. Modeling an edge-weighted graph as a tank network 151.4. The relations between n-floodings and e-floodings 191.4.1. Modeling flooding on two scales: the equivalence of both models 191.5. Flooding a flowing graph 211.5.1. Flowing graphs: reminder 211.5.2. Starting from an edge-weighted graph G[nil, η] 221.5.3. Starting from a node-weighted graph G[ν, nil] 241.5.4. Summarizing 24Chapter 2. Lakes and Regional Minima 272.1. Summary of the chapter 272.2. Lakes from e-floodings and n-floodings 272.2.1. e-flooding of graphs G[nil, η] 272.2.2. n-flooding of graphs G[ν, nil] 282.3. Regional minimum lakes and full lakes 292.3.1. e-floodings of graphs G[nil, η] 292.3.2. n-floodings of graphs G[ν, nil] 302.4. Coherence between the definitions of lakes in G[ν, nil] and in G[nil, δenν] 31Chapter 3. Among all Possible Floodings, Choosing One 333.1. Summary of the chapter 333.2. Various mechanisms for selecting a particular flooding 343.2.1. Dominated flooding in node- and edge-weighted graphs 343.2.2. Dominated flooding in node- and edge-weighted graphs 363.2.3. Dominated flooding as a function of the ceiling function 373.3. The topography of dominated flooding 373.3.1. The regional minima of dominated flooding in an edge-weighted graph G[nil, η] 383.3.2. The regional minima of dominated n-flooding in node-weighted graphs G[ν, nil] 393.3.3. Algorithmic consequences 413.4. Computing dominated flooding by local adjustments 433.4.1. The case of edge-weighted graphs G[nil, η] 433.4.2. The case of node-weighted graphs G[ν, nil] 443.4.3. Software or hardware implementation of Berge’s algorithm 45Chapter 4. Flooding and Flooding Distances 494.1. Summary of the chapter 494.2. Flooding distances 494.2.1. The flooding distance associated with the lakes of node- or edge-weighted graphs 494.2.2. Characterization of the flooding distance 504.2.3. Flooding distances on a graph or a tree 524.2.4. The shortest flooding distances 534.2.5. Dominated flooding and flooding distances 564.3. The shortest path algorithms for computing dominated flooding 664.3.1. Computing the shortest flooding distance with the Moore–Dijkstra algorithm 664.4. The flooding core-expanding algorithm 754.4.1. The first version of the core-expanding algorithm applied to the augmented graph GÂ 764.4.2. The second version of the core-expanding algorithm applied to the initial graph G 784.4.3. The third version of the core-expanding algorithm applied to the initial graph G 794.5. Marker-based segmentation 814.5.1. The case of a node-weighted graph G(ν, nil) 81Chapter 5. Graph Flooding via Dendrograms 835.1. Summary of the chapter 835.2. Introduction 845.3. Dendrograms: reminder 865.3.1. The structure associated with an order relation 865.3.2. Dendrograms 875.3.3. Stratification index and partial ultrametric distances (PUD) 885.4. The hierarchy of lake zones 895.4.1. The lake zones of an edge-weighted graph G(nil, η) 895.4.2. The hierarchy of lake zones, i.e. the closed balls of χ 925.4.3. Representing of hierarchy of lake zones 945.5. The law of communicating vessels 985.5.1. The flooding levels in connected subgraphs and closed balls 995.6. Dominated flooding on the dendrogram of lake zones 1005.6.1. Notations 1005.6.2. Incidence of the ceiling function on the dendrogram flooding levels 1005.6.3. Finding the flooding level of a leaf 1025.6.4. Parallel processing for flooding the dendrogram 1055.6.5. Strategies for flooding the dendrogram of lake zones 1065.7. Constructing and flooding a binary dendrogram 1115.7.1. Two dendrograms representing the same hierarchy 1115.7.2. Constructing a binary dendrogram representing a hierarchy 1125.7.3. Flooding a binary dendrogram 1135.8. A derived algorithm for dominated flooding 1135.8.1. Algorithm “ancestor-flood without constructing the dendrogram” 1175.8.2. Illustration 117Part 2. Modeling a Real Hydrographic Basin 119Chapter 6. The Hydrographic Basin of a Digital Elevation Model 1216.1. Summary of the chapter 1216.2. Preprocessing the digital elevation model 1216.2.1. Suppressing the spurious regional minima 1216.2.2. Creating an ∞ − steep digraph 1236.2.3. Local pruning for extracting marked rivers 1266.2.4. Extracting all rivers 1286.2.5. Labeling sources and rivers 1296.2.6. Detection of crest lines 1316.2.7. Detecting the upstream of sources 1326.2.8. Analyzing the tree structure of rivers 1336.2.9. Constructing the catchment zones of riverlets 137Part 3. Watershed Partitions 139Chapter 7. Minimum Spanning Forests and Watershed Partitions 1417.1. Summary of the chapter 1417.2. Flooding distance, minimum spanning trees and forests 1427.2.1. Flooding distances 1427.2.2. Flooding distance on the minimum spanning tree of the graph G(nil, η) 1437.2.3. Characterizing the MST 1457.3. Minimum spanning forests rooted in markers 1467.3.1. Constructing the minimum spanning forest 1477.3.2. Converting the minimum spanning forest into a minimum spanning tree 1497.4. Watershed partitions of weighted graphs 1507.4.1. Catchment basins and watershed partitions 1507.4.2. Flowing paths and catchment basins 1517.5. Minimum spanning forests rooted in the regional minima 1517.5.1. A minimum spanning forest corresponds to each watershed partition 1517.5.2. Inversely, each watershed partition spans a minimum spanning forest 1547.5.3. A rather unexpected watershed partition 1567.6. A manifold of different watershed partitions 1597.6.1. Catchment zones and catchment basins 1597.7. Reducing the number of watershed partitions 1607.7.1. Minimum spanning forests of k – steep or ∞ − steep graphs 1637.7.2. The waterfall hierarchy 1687.7.3. Usefulness of the waterfall hierarchy 171Chapter 8. Marker-based Segmentation 1758.1. Dominated flooding and minimum spanning forests 1778.1.1. Dominated flooding 1778.1.2. Minimum spanning forests 1778.1.3. Illustration 1788.1.4. Minimum spanning forests and dominated flooding 1798.2. Constructing a minimum spanning forest rooted in the markers 1838.2.1. Algorithms for constructing a minimum spanning forest 1838.2.2. Increasing the selectiveness of Prim’s algorithm 1868.2.3. Marker-based segmentation of node-weighted graphs 1878.2.4. Derived algorithms 1908.3. Marker-based segmentation after flooding the graph 1948.3.1. Segmenting the dominated flooding of a graph 1948.3.2. The case of an edge-weighted graph 1948.3.3. Constructing a k – steep or ∞ − steep watershed partition for a node-weighted graph G(ν, nil) 2008.4. Directly constructing a marker-based ∞ − steep watershed partition with the core expanding algorithm 2018.5. The early days of marker-based segmentation 2028.5.1. The level-by-level construction of a watershed 2038.6. A two scale marker-based segmentation 2058.7. Instant marker-based segmentation 2058.7.1. Why and when we need instant marker-based segmentation 2058.7.2. The reef and cascade distance 2068.7.3. Computing the reef and cascade distance for all pairs of nodes in G(nil, η) 2098.7.4. Computing the smallest reef and cascade distances between all couples of nodes in a graph 212Conclusion 217Appendix 227References 239Index 241