Topographical Tools for Filtering and Segmentation 1

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.

Auteur

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.

Contenu

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&...