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.
The Introduction gives an outline of both volumes and is followed by four main parts.
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.
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 node-and 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 features from an unweighted gravitational digraph.
This part contains Chapters 7–11. It plays a very important role in the applicability of the whole theory. Indeed, a node may be linked by a flowing path with several regional minima. It then belongs to several catchment zones. To avoid any arbitrary assignment to one of these catchment zones rather than to another, we have to find objective criteria for comparing flowing paths with the same origin in order to keep, as often as possible, only one of them. Thus, we reduce or, in some cases, completely suppress the overlapping of catchment zones.
Chapter 7 explains how to measure and compare the steepness of flowing paths.
Chapter 8 presents a method for pruning node-weighted digraphs. Two simple neighborhood operators are applied in sequence. At each new iteration, the steepness of the remaining flowing paths increases by one. At convergence, only ∞ – steep flowing paths remain.
Chapter 9 presents an alternative method for selecting the ∞ – steep flowing paths in a node-weighted graph or digraph. This algorithm floods the topographic surface, starting from the minima, and propagates the flooding along the ∞ – steep flowing paths. We owe this nice feature to the hierarchical queue structure that schedules the flooding.
A node-weighted digraph is called ∞ – steep if all its flowing paths are ∞ – steep. The overlapping of the catchment zones in such a digraph is minimal: a node belongs to two distinct catchment zones if it is linked with the corresponding regional minima by two flowing paths whose weights are node for node identical. Such events may be extremely rare; nevertheless, they may happen, especially for small catchment zones. If such an event happens, we still have to resort to some kind of arbitrary choice for affecting the nodes belonging to two catchment zones or one of them. However, constructing the catchment zones of such an ∞ – steep digraph yields the best possible watershed segmentation. Chapter 10 explains how pruning or flooding may be done at the same time as the labels of the regional minima are propagated inside their catchment zones. It compares the progression modes of the labels for both methods, either pruning or flooding. In any case, we construct a dead leaves tessellation of catchment zones. A label is assigned to each regional minimum and priorities between labels are defined. In the case of conflict between two labels to be assigned to a particular node, it is always the label with the highest priority that wins. Thus, we obtain a dead leaves tessellation, in which the catchment zones whose labels have the highest priority lie on top of others with lower priorities, partially covering them. However, regardless of the degree of steepness of the graph, the regional minima always appear in the dead leaves tessellation. With increasing degrees of pruning, the dead leaves tessellation converges towards a watershed partition in which the remaining overlapping is either non-existent or minimal.
Chapter 11 entitled “An Historical Intermezzo” explains how the hierarchical queue driven algorithm progressively unveils its full potential. It was introduced in 1991 for dealing with the presence of plateaus, as it always makes it possible to flood higher nodes after lower nodes; while at the same time, flooding the nodes inside plateaus in an order proportional to their distance to the lower border of the plateaus. Later, when the watershed partition is defined as a Voronoï tessellation for the topographic distance, the same algorithm performs the job nicely. Finally, it appears that the flooding follows ∞ – steep flowing paths when it is scheduled by this algorithm.
Finally, Part 4, which consists of Chapters 12–15, deals with the first applications of the watershed theory.
As many watershed applications deal with images, i.e. node-weighted graphs, it seemed worthwhile in Chapter 12 to propose an economical method for encoding node-weighted digraphs representing images. At the same time, we revisit the various operators defined for node-weighted or -unweighted digraphs using this particular representation of the digraphs.
Chapter 13 emphasizes the difference between constructing a dead leaves tessellation of catchment zones or watershed partitions, which can only be obtained at the expense of some arbitrary choices. Part 4 mainly deals with dead leaves tessellations of catchment zones, which open brand new segmentation methods. However, the watershed partitions for which arbitrary choices have to be made are also dealt with.
Chapter 14 outlines the full potential of our choice to favor the dead leaves tessellation of catchment zones, rather than watershed partitions. Each catchment zone in a dead leaves tessellation may be singled out and constructed independently of the others. It is possible to extract one or several catchment zones. These operations are local, only involving the portion of the domain covered by the catchment zones and may be done in parallel.
On the contrary, constructing watershed partitions relies on the best assignment of overlapping catchment zones, which requires a global flooding of the domain. A node is assigned to a particular label if it is the first node reached by the flood.
The drawback of the dead leaves tessellation is that the overlapping of catchment zones is still present, hidden by the dead leaves. However, as we develop methods for pruning the node-weighted digraphs, we may substitute a pruned digraph into the initial graph and obtain a dead leaves tessellation that is very close to a watershed partition. In the first part of the chapter, we study the possibility of obtaining acceptable segmentation by substituting a dead leaves tessellation of a weakly pruned digraph into a watershed partition whose construction is more expansive.
We remark that after a weak degree of pruning, the remaining overlapping zones are few and small. We then present a method for suppressing such overlapping zones. It suffices to construct a limited downstream of the overlapping zone and perform the correction within this restricted domain, either by pruning or by flooding. Thus, we are able to correct all the errors that we chose to correct in parallel, involving only a small fraction of the whole domain.
Chapter 15 concludes Topographical Tools for Filtering and Segmentation 1. It shows how the catchment zones may be flooded one after another. When a number of catchment zones have already been labeled, we consider the pass points linking labeled and unlabeled catchment zones. We select the pass points with the lowest altitude and label the adjacent catchment zones, either with a new label or with the same label. We present two examples of this step-by-step segmentation. This chapter concludes with a first approach to marker based segmentation, where the marked catchment zones are to be labeled. Their labels are then propagated to neighboring unlabeled catchment zones with the same selection process of the next catchment zone to label.
The first part of Topographical Tools for Filtering and Segmentation 2, which comprises of Chapters 1–5, deals with flooding.
Chapter 1 separately defines the flooding of a node and of an edge-weighted graph. In the case of node-weighted graphs, the node weights act as a ground level, covered or not by a flood. In the case of edge-weighted graphs, there is no ground level, but the edges connecting adjacent nodes are weighted.
Not all of the flood distribution on the nodes of the graph represents a valid flooding. Hence, we model the equilibrium states of a valid flooding for both the nodes and for the edge-weighted graphs. From each hydrostatic model, it is then possible to derive criteria for recognizing valid flooding.
The same flooding of a topographic surface may be observed at two scales. The scale of pixels may be modeled as a node-weighted graph, with neighboring pixels forming the nodes of the graph. The scale of catchment zones may be modeled as an edge-weighted graph, with the catchment zones being the nodes. Neighboring catchment zones are linked by edges, whose weight is equal to the level of the pass point between the two regions.
Thus, we obtain two representations of the same phenomenon: one as a node-weighted graph, and the other as an edge-weighted graph. Furthermore, each of them is modeled with a different physical model. Fortunately, both models represent the same phenomenon, which is expressed in the form of a theorem: a function τ ≥ ν defined on the nodes of a graph is a valid flooding of a node-weighted graph, above ground level ν if and only if it is a valid flooding of the edge-weighted graph with edge weights equal to δenν.
Chapter 2 studies the lakes of a valid flooding, separating regional minima lakes and full lakes.
Chapter 3 explains how, from amongst the various ways of flooding a graph, it is possible to choose and construct a particular graph: it is the highest flooding of the graph below a ceiling function, which we call dominated flooding under the ceiling function. Only a subset of the nodes of a ceiling function play an active role in determining the levels of the highest flooding below it. Another theorem is established with important consequences. If the ceiling function ω is higher than or equal to the ceiling function ν then the highest flooding of the node-weighted graph with node weights ν is also the highest flooding of the edge-weighted graph with edge weights δenν. This property will enable us to construct the highest flooding of node-weighted graphs on their equivalent edge-weighted graphs.
Chapter 4 defines flooding distances between nodes as the lowest level of a uniform flooding for which both nodes belong to a lake. It then shows that the shortest flooding distance to a node of a graph constitutes a valid flooding of this graph. Conversely, it shows how each dominated flooding may be constructed as the shortest flooding distance to an augmented graph, obtained by adding dummy nodes and dummy edges encoding the ceiling function.
This analysis has a beneficial impact as it opens the scope of algorithms to construct dominated flooding with all shortest-distance algorithms, expressed in the (min, max) algebra.
Finally, Chapter 5 deals with the dominated flooding of edge-weighted graphs. A node-weighted graph with a ground level ν is previously transformed into an edge-weighted graph with edge weights δenν. The edge-weighted graph may be represented by a dendrogram, in which the nodes represent closed balls for the flooding distance. To flood the graph, we determine the maximal closed balls covered by a lake, together with the level of this lake. This approach enables massive parallel treatments of subdendrograms that are independent from each other.
Chapter 6 deals with a real topographic surface in the form of a digital elevation model. Throughout this book, we have considered gray tone images and even graphs as topographic surfaces in order to develop some intuitive understanding of the abstract and mathematical tools that are developed. In this chapter, we consider the digital elevation model of a real landscape crossed by real rivers, possessing sources and mouths, catchment zones and crest lines. It appears that all the tools developed for node-weighted graph or digraphs perform extremely well for extracting all substructures of interest for hydrologists.
The third part constitutes a convergence point for the two preceding parts. Consisting of Chapters 7 and 8, this part analyzes the everyday practice of watershed segmentation, aiming to produce non-biased watershed partitions. We define a catchment basin as a set of nodes linked by a flowing path with a regional minimum; a watershed partition of a weighted graph is then a partition of the nodes, in which each tile is a catchment basin.
We have seen that it is impossible to construct a totally unbiased watershed partition as there may exist nodes that are at the same infinite lexicographic distance of two regional minima. In the absence of supplementary criteria, it is impossible to affect such nodes to one minimum or another. Nevertheless, constructing (more or less biased) watershed partitions is at the core of morphological segmentation.
Chapter 7 reviews some results on the ultrametric flooding distance and the associated minimum spanning tree. A generic method is presented to construct a minimum spanning forest in which each tree is rooted in a so-called marker node chosen a priori. We then consider the particular case where the nodes belonging to the regional minima of the graph are chosen as marker nodes. A one-to-one correspondence is established between watershed partitions and the minimum spanning forests rooted in the minima. This explains why so many distinct watershed partitions exist: a watershed partition corresponds to each particular choice of an MST and within this MST of an MSF. In an ideal watershed partition, each node would belong to the catchment basin of the closest regional minimum for the lexicographic flowing distance. In order to approach such an ideal watershed partition, the number of flowing paths has to be reduced either by pruning or by using the core-expanding flooding algorithm presented in Part 3 of Volume 1 entitled “Reducing the Overlapping of Catchment Zones”.
A watershed partition of a topographic surface (represented either by a node- or an edge-weighted graph) contains as many regions as there are regional minima, each region containing one regional minimum. Marker based segmentation on the contrary constructs a partition in which each region contains one marker. The exact position and shape of the markers inside the regions to segment has no importance, provided a marker has been detected or placed in each region of interest. This makes marker based segmentation an extremely powerful and versatile segmentation method. Two methods have been published in the literature, the first based on flooding adapted to images and node-weighted graphs, the second adapted to region adjacency graphs and edge-weighted graphs. We have extended both methods to make them applicable to node or edge weighted graphs.
The first method modifies the topography of the graph by flooding it. It imposes regional minima at the positions of the markers and only at these positions. This is done by constructing the highest flooding τω of the graph under a ceiling function equal to ∞ on all nodes except at the marker positions (equal to the node weights for a node-weighted graph or to –1 for an edge-weighted graph). If the initial graph is a node-weighted graph G(ν, nil), we obtain a node-weighted graph G(τω, nil) on which any method described in Chapter 7 may be used to construct a watershed partition (for instance the core expanding algorithm). If the initial graph is an edge-weighted graph G(nil, η), we obtain a node- and edge-weighted graph G(τω, η) in which the edges which do not belong to the geodesics of the flooding distance have to be suppressed. This is the case when the weight ηpq of an edge epq does not verify one of the relations τω(p) = τω(q) ∨ ηpq or τω(q) = τω(p) ∨ ηpq. After pruning the graph G(τω, η) by suppressing such edges, we obtain a node-weighted graph G′(τω, nil) on which any method described in Chapter 7 may be used to construct a watershed partition
The second method was published for edge-weighted graphs and consists of constructing a minimum spanning forest rooted in the markers. Because of a relative myopia of the flooding distance there is again a proliferation of many possible minimum spanning forests. In order to curb this proliferation an improved PRIM algorithm is presented which does a better and more focused choice of a MSF. This method is easily extended to node-weighted graphs G(ν, nil), by applying them to the derived edge-weighted graph G(nil, δenν).
Another means to curb the proliferation of solutions is to replace the ultrametric flooding distance with a more selective lexicographic distance.
Finally it is shown how the waterfall hierarchy may be combined with marker based segmentation. One chooses a level of the waterfall hierarchy which will be marker segmented. A marker is assigned to a node of this hierarchy if the underlying region contains at least one marker.
The conclusion draws a close to the two volumes of Topographical Tools for Filtering and Segmentation, while opening a discussion on some perspectives for future research.
The Appendix recalls the main mathematical notions that are developed in the two volumes, together with the notations that are introduced throughout.