Topological Grayscale Watershed Transformation
Let us consider a grayscale image as a topographical relief: the gray level of a pixel becomes the elevation of a point, the basins and valleys of the relief correspond to the dark areas, whereas the mountains and crest lines correspond to the light areas. The watershed line may be intuitively introduced as the set of points where a drop of water, falling there, may flow down towards several catchment basins of the relief.
In order to precisely define the notion of watershed, we must introduce some topological notions for graphs and weighted graphs. A binary image may be modelized by a graph (E, N) and a subset X of E representing the ``object''.
We will now introduce the notion of ``simple point'' in a graph. Intuitively, a point of the complement of X is ``simple'' if it may be added to X while preserving the number of connected components of X.
This corresponds to the preservation of a ``one-dimensional'' topology. It is important to note that the usual definition of a simple point in Z2 corresponds to the preservation of a ``two-dimensional'' topology, that is to say, not only the number of connected components of X is preserved, but also the number of connected components of the complement of X.
It may be easily seen that one cannot locally decide whether a point is simple or not.
A grayscale image may be modelized by a weighted graph (E, N, F), where E = Z2, N(x) denotes the set of points adjacent to the point x, and F(x) represents the gray level of the point x.
We denote Fk, the set of points x such that F(x) is greater or equal to k. Fk is called a (cross-)section of F.
A connected component of a section Fk is called a (level k) component of F.
The extention of the notion of simple point to a weighted graph leads to the definition of a constructible point:
The point x is constructible (for F) if x is simple for Fk+1, with k = F(x).
That is to say, each neighbor y of x, such that F(y) > k, belongs to the same level k+1 component of F.
In other words, the value of a constructible point may be raised by one without changing the number of connected components of each cross-section of F.
We say that G is upper-homotopic to F if G may be derived from F by the iterative raising of constructible points.
We say that K is an upper-homotopic kernel of F if K is upper-homotopic to F and K is maximal for this property, that is, all points of E are non-constructible for K.
([Hanusse and Guillataud, 1992]: Dendronic Analysis)
In order to propose an efficient algorithm for computing the upper-homotopic kernel of an image, we must find a way to check efficiently whether a point is constructible or not, and, if it is the case, we must know up to which level it may be raised. The component tree structure will allow us to answer these two questions in constant time.
Suppose that the relief corresponding to F is completely flooded with water. Suppose that we steadily lower the water level. Two kinds of event may occur:
When a new island appears, we create a corresponding leaf of the component tree.
When several islands merge together, we create a node of the component tree which is the father of the nodes associated with the merging islands.
Several indicators may be collected during this process, and associated to the vertices of the component tree: maximal height of an island, surface of the base, volume...
We associate a different label to each vertex of the component tree.
During the component tree construction process, as the water lowers, each emerging point of the image may be labeled in order to create a correspondence with a component tree vertex.
Let x be a pixel, and let k = F(x) be its gray level.
We denote M(x) the set of labels of the points in the neighborhood of x, that are stricly higher than x.
Property: The point x is constructible (for F) if and only if the nearest common ancestor of all the components whose labels are in M(x), has a level equal to or higher than k+1 .
Furthermore, if the value of x is raised up to k', the resulting image is homotopic to F.
Algorithm: Iteratively select a constructible point x and raise it, thanks to the informations in the component tree and using the above property. Update the label of x. This procedure must be repeated until stability.
The components that do not satisfy an increasing criterion may be recursively deleted from the component tree. This "filtering step" gives a result which is equivalent, up to a topological transformation, to an attribute opening, which is a powerful tool developped in the framework of the Mathematical Morphology.
Some basic increasing criteria are:
M. Couprie and G. Bertrand, "Topological Grayscale Watershed Transformation", SPIE Vision Geometry V Proceedings, Vol. 3168, 136-146, 1997.