Topographical Tools for Filtering and Segmentation 2

Flooding and Marker-based Segmentation on Node- or Edge-weighted Graphs

Fernand Meyer

• Éditeur: Wiley-ISTE
• Année: 2019
• ISBN:
  9781119575122
• Édition: 1
• Sujet: Technology & Engineering
• Sous-sujet: Signals & Signal Processing

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 2 proposes two physical models for describing valid flooding on a node- or edge-weighted graph, and establishes how to pass from one to another. Many new flooding algorithms are derived, allowing parallel and local flooding of graphs. Watersheds and flooding are then combined for solving real problems. Their ability to model a real hydrographic basin represented by its digital elevation model constitutes a good validity check of the underlying physical models. The last part of Volume 2 explains why so many different watershed partitions exist for the same graph. Marker-based segmentation is the method of choice for curbing this proliferation. This book proposes new algorithms combining the advantages of the previous methods which treated node- and edge-weighted graphs differently.

PART 1
Flooding

1
Modelling Flooding in Edge- or Node-weighted Graphs

1.1. Summary of the chapter

This chapter opens Volume 2 of Topographical Tools for Filtering and Segmentation, which is, devoted to flooding. In the Introduction we stressed the importance of flooding for filtering and segmenting images. Flooding is the perfect companion for a watershed, as it is able to suppress regional minima by filling them with lakes. The catchment zone of a suppressed regional minimum is entirely absorbed by the catchment basin of a remaining regional minimum [MEY 02].

For the sake of generality, we model topographic surfaces as node- or edge-weighted graphs.

A node-weighted graph may represent a topographic surface at pixel level. The nodes represent the pixels, and the edges link neighboring pixels. The nodes have two weights: the lower weight represents the ground level, and the higher weight represents the flooding level, which cannot be below the ground level. The edges are unweighted.

An edge-weighted graph may represent a flooding at a larger scale. The nodes represent the catchment zones of a topographic surface, and the edges represent the pass points between neighboring basins. The node weights indicate the level of the lake covering the corresponding basin, equal to −∞ if the basin is unflooded. The edge weights represent the altitude of the corresponding pass point.

Thus, we obtain two models of graphs that are able to represent the same flooding of the same topographic surface on two scales: a micro scale with the node-weighted graph and a macro scale with the edge-weighted graph. We will call them, respectively, micro and macro models of flooding.

We then propose two physical models ensuring that a particular flood distribution is in an e...