Topographical Tools for Filtering and Segmentation 2: Flooding and Marker-based Segmentation on Node- or Edge-weighted Graphs

By Fernand Meyer

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.

• Language: English
• Publisher: Wiley
• Release date: Jan 23, 2019
• ISBN: 9781119575122

Book preview

Notations

Volume 1

Mathematical notions

Weighted graphs

Graphs

Subgraphs

Partial graphs

Paths

Cocycles and neighborhoods

Weight distributions on the nodes or edges of a graph

Erosions and dilations between node and edge weights

Composition of operators

Gradient operators

Subtracting an erosion from a dilation produces various gradient operators:

Binary and equivalence relations

Flowing graphs

The topography of digraphs

and have the same flowing edges and flowing paths.

Measuring the steepness of flowing paths

Pruning a flow digraph

Constructing an ∞− steep digraph by flooding

Creating steep watershed partitions

An historical intermezzo

Encoding the digraph associated with an image

Volume 2

Modeling flooding

Lakes and regional minima

Λλ(nil, η): a partial subgraph of G[nil, η] defined as follows:

– a node p belongs to Λλ(nil, η) if τp=λ;

– an edge epq belongs to Λλ(nil, η) iff τp=τq=λ and

Creations of node flat zones on G(ν, nil):

Among all flooding, choosing one

Flooding and flooding distances

Augmented graph in G(nil, η)

Augmented graph in G(nil, η)

Shortest path algorithms

Graph flooding via dendrograms

Dendrogram structure

Ultrametric distances

Minimum spanning forests and watershed partitions

Marker-based segmentation

Introduction

General organization

This book is divided into two volumes, which are dedicated to morphological segmentation. Morphological segmentation mainly relies on the watershed transform. The contours of an image to be segmented appear as the watershed lines of its gradient image. However, as each regional minimum of the gradient image is surrounded by a watershed line, the image is often oversegmented and the segmentation has to be regularized. Another operator floods the gradient image and allows some regional minima to disappear. The new watershed lines of the flooded surface are less numerous, and if the flooding is appropriate, they will adequately represent the contours of the image. This book analyzes in depth watersheds and the flooding of images, and shows how to combine them in order to produce meaningful segmentations.

Any gray tone image may be considered as a topographic surface, with the altitude at each location of the surface being equal to the gray tone at the same location in the image. The highest points of the surface then correspond to the brightest points in the image. Thanks to this analogy several topographic concepts, such as regional minima and catchment zones, may be transposed to images. Quite similarly to topographic surfaces, images may be flooded.

All concepts and algorithms of this work derive from a physical model for flows and floods on a topographic surface. A drop of water deposited on a surface glides down until reaching a regional minimum and belongs to the catchment zone of this minimum. The physical model enables us to describe the possible trajectories of a drop of water. Similarly, flooding a topographic surface creates lakes, which are flat zones under which the underlying surface characteristics have completely vanished. The topography of a flooded surface thus differs from the initial topography with less minima and fewer catchment zones.

Now, instead of modeling these phenomena on gray tone images, we have chosen the abstract framework of weighted graphs, which open a large field of applications. Comparing and confronting the properties of node-weighted and edge-weighted graphs will be an endless source of inspiration and of new ideas and algorithms.

Each of the two volumes of this book broadly covers one physical model: the first deals with flows, while the second deals with floods.

Topographical Tools for Filtering and Segmentation 1: Watersheds on Node- or Edge-weighted Graphs analyzes the topography of a surface by observing the possible trajectories of a drop of water on the surface. From the observation of flows, it derives the notions of regional minima, catchment zones, upstream and downstream, etc. The volume ends by showing catchment zones that may be used for segmenting images.

Part 1 of Topographical Tools for Filtering and Segmentation 2: Floodings and Marker-based Segmentation on Node- or Edge weighted Graphs analyzes the evolution of a topographic surface when it is flooded. Part 2 of the volume is devoted to real-life applications, involving both flows and floods. The first application explores whether the rather abstract concepts and algorithms developed on graphs successfully describes a real hydrographic basin represented by a digital elevation model. The floods help correct the measurement errors of the model, and the flows enable us to detect and describe the structure of the rivers. The second application deals with marker-based segmentation, which corresponds to the everyday practice of morphological segmentation. Several markers are defined in an image and the associated segmentation creates a partition in which each region contains a marker and corresponds to the catchment basin of a flooded surface.

Let us now give an overview of both volumes.

Outline of volume 1

The Introduction gives an outline of both volumes and is followed by four main parts.

Part 1. Getting started

Part 1 primes the topic incorporating a literature review and some useful mathematical concepts.

Chapter 1 presents a primer for non-specialists in mathematical morphology, explaining why watersheds and flooding are so valuable in image processing. Chapter 2 explains how the practice of morphological segmentation progressively emerged and evolved over the last 50 years. Chapter 3 presents several useful mathematical definitions which will be used later. This chapter focuses on the adjunction, which is the cornerstone of mathematical morphology, linking erosion and dilation and generating closings and openings. Throughout the book, we will encounter an adjunction between the node and edge weights on weighted graphs. This adjunction plays a crucial role in proving the equivalence of both types of graphs with respect to watersheds and to some extent with respect to flooding.

Part 2. The topography of weighted graphs

This part contains Chapters 4–6. It describes the topography of graphs and digraphs in relation to the possible trajectories of a drop of water evolving from node to node.

Chapter 4 revises weighted graphs. The keyword of the book is topography. In order to deal with watersheds, we study the topography of a graph in relation to its node or edge weights. In order to deal with flooding, we study the topography at several levels: the topography of the graphs themselves and the topography of flooded graphs in relation to the topography of the graph. More importantly, we study the topography of the highest flooding below a ceiling function, and how it relates to the topography of the graph, on the one hand, and that of the ceiling function, on the other hand. Chapter 4 separately studies the topography of node- and edge-weighted graphs, defining for each the flowing edges, flowing paths, regional minima and catchment zones. It turns out that the behavior of a drop of water is highly similar in both nodeand edge-weighted graphs.

Chapter 5 explores the deep similarities between the two types of graphs with regard to the watersheds. In a node-weighted graph, a flowing edge links each node with its neighbors whose weight is lower or equal. Hence, each edge is the flowing edge of one of its extremities, or of both; it may then unambiguously take the weight of this extremity. The operator that assigns nodes to each edge the weight of its highest extremity is a dilation, which is denoted by δen. The adjunct erosion appears for an edge-weighted graph, in which the nodes are not initially weighted. The flowing edges of a node are its adjacent edges with the smallest weight. Each node has at least one flowing edge, and may be unambiguously assigned the weight of this edge. This second operator is an erosion, which is denoted by εne, between the edge and node weights, with each node being assigned the weight of its lowest edges.

However, in an edge-weighted graph, edges may exist that are not the lowest edge of one of their extremities. Such edges are not flowing edges of the graph and do not belong to the trajectory of a drop of water deposited at one of the nodes. In a node-weighted graph, nodes may exist for which all neighbors have higher weights. Such nodes are isolated regional minima. If we add a self-loop linking an isolated regional minimum with itself, we can produce a graph in which all nodes are the origin of a flowing edge. After such edit operations, we obtain, for both initially node-weighted graphs and initially edge-weighted graphs, a graph in which each node is the origin of a flowing edge and in which each edge is the flowing edge of one of its extremities. Thus, we can obtain a perfect coupling between nodes and edges. The nodes of an edge-weighted graph are then weighted by eroding the edge weights with the erosion εne. Similarly, the edges of a node-weighted graph are then weighted by the dilation δen of its node weights. In both cases, we obtain a node- and edge-weighted graph, in which the nodes are obtained by dilating the edge weights, and simultaneously the edges are obtained by eroding the node weights. Such a graph is called a flowing graph. It has the same flowing paths, regional minima and catchment zones, regardless of whether we consider only the node weights or only the edge weights.

At this stage, we have associated to each node- or edge-weighted graph a node and edge weighted graph, called flowing graph and sharing the same topographical features as the graphs it is derived from: flowing paths, regional minima and catchment zones. We remark that the absolute values of the node or edge weights do not matter at all for determining the direction of the flow in a flowing edge. Only their relative values are taken into account.

We now go one step further and completely drop the node or edge weights. We start from a flowing graph, in which all edges are flowing edges, and substitute to each flowing edge an arc oriented in the direction of the flow. One obtains like that a directed graph or digraph. A flowing path of the initial graph simply becomes a directed path in the digraph.

A flowing path in a weighted graph represents the motion of a drop of water. A drop of water never moves upwards. A flowing path can for this reason never close itself, forming a cycle, except in the case where it belongs to a flat zone. Such a flowing cycle is then bidirectional as a drop of water may move in both directions. This translates to the derived digraph: a directed cycle can only exist if all its arcs are bidirectional. We call such digraphs gravitational digraphs.

Chapter 6 first studies the topography of completely general unweighted digraphs, in which directional cycles are permitted even if they are not bidirectional. It turns out that their topographical features are poorer but not without interest. They may offer an interesting framework for future developments. The remaining part of Chapter 6 analyzes the topography of gravitational digraphs, which is much richer. Weights are indeed not necessary for defining their major topographic structures. In a flat zone any couple of nodes are connected by a bidirectional path. It is impossible to leave a black holes by an outgoing arc, just like the black holes in the universe do not let out light. Finally, catchment zones of a black hole are all nodes at the origin of a directed path leading into this black hole. The chapter concludes by presenting the algorithms able to extract all the these topographical