Image Anal Stereol 2001;20:137-141 Original Research Paper
GEODESIC RECONSTRUCTION, SADDLE ZONES & HIERARCHICAL SEGMENTATION
Serge Beucher
Centre de Morphologie Mathématique, Ecole des Mines de Paris, 35, Rue Saint-Honoré, 77300, Fontainebleau,
France
e-mail: beucher@cmm.ensmp.fr
(Accepted October 18, 2001)
ABSTRACT
The morphological reconstruction based on geodesic operators, is a powerful tool in mathematical morphology. The general definition of this reconstruction supposes the use of a marker function f which is not necessarily related to the function g to be built. However, this paper deals with operations where the marker function is defined from given characteristic regions of the initial function f, as it is the case, for instance, for the extrema (maxima or minima) but also for the saddle zones. Firstly, we show that the intuitive definition of a saddle zone is not easy to handle, especially when digitised images are involved. However, some of these saddle zones (regional ones also called overflow zones) can be defined, this definition providing a simple algorithm to extract them. The second part of the paper is devoted to the use of these overflow zones as markers in image reconstruction. This reconstruction provides a new function which exhibits a new hierarchy of extrema. This hierarchy is equivalent to the hierarchy produced by the so-called waterfall algorithm. We explain why the waterfall algorithm can be achieved by performing a watershed transform of the function reconstructed by its initial watershed lines. Finally, some examples of use of this hierarchical segmentation are described.
Keywords: geodesic reconstruction, hierarchy, saddles, segmentation, waterfall algorithm, watersheds.
INTRODUCTION                                            PROPERTIES OF THE GEODESIC
RECONSTRUCTION
The geodesic reconstruction is an efficient tool in Mathematical Morphology. In this paper, we shall recall some interesting properties of this transformation and some of its main uses, especially for extracting the extrema of a function. We shall show then how this transformation can be modified to exhibit the saddle zones. Some of these saddle zones, called regional saddle zones or overflow zones, are particularly interesting because they play a major role in the waterfall transformation, a non parametric approach of hierarchical segmentation by watersheds. The reconstruction of a function by its overflow zones produces a so-called hierarchical function, its watersheds corresponding to a higher level of hierarchy. We shall see in this paper how this waterfall transform and the hierarchical function can be produced by means of a geodesic reconstruction of the initial function by its own watershed lines.
For the sake of simplicity, all the notions presented below will be introduced on digitised integer positive and bounded functions (in the range (0,M]).
Given a function f, called marker function, and a function g, such that f < g, the geodesic reconstruction Rg (f) of g by f is defined as follows:
Rg(f) = Dg°°(f)                       (1)
where Dg°°(f) is the infinite iteration of the geodesic dilation Dg(f)= Inf(f 0H,g), where H is the isotropic elementary structuring element (Fig. 1). A dual reconstruction R* (f) based on geodesic erosions can
also be defined. In this case, the f function is always above g (g < f):
R*g(f) = E+g°° (f)                      (2)
Eg00 (f) is the iteration of the geodesic erosion Eg(f) = Sup(fOH, g).
137
Beucher S: Geodesic reconstruction, saddle zones & hierarchical segmentation
Fig. 1. Geodesic reconstructions (by dilation on the left and by erosion on the right).
A well-known use of the reconstruction is the extraction of the function extrema (minima and maxima). If we take g = (f + 1) and if we perform the reconstruction of g by f, the difference g-Rg(f) corresponds to the indicator function of the maxima of f.
Conversely, the differenceR * f (g)-fproduces the indicator function of the minima of f.
An interesting property of the extrema, which will be used later, is the following: if, in the reconstruction of a function g, we replace the function f by another function f defined by:
f (x) = f(x) if x belongs to a maximum of f
f(x) = 0 if not
the reconstruction of g is the same. (f is called valued indicator function of the maxima of f).
In the same way, the dual reconstruction of g by f is unchanged if we replace f by f, valued indicator function of the minima:
f (x) = f(x) if x belongs to a minimum of f
f (x) = M if not (f takes its values in the range [0,M])
Moreover, if we use a subset of the extrema, provided that there exists at least one connected component of this subset included in each connected component of the maxima (resp. minima), the reconstruction will still be the same. These properties can easily be proved when we consider the thresholds of f and g. The reconstruction corresponds to a set reconstruction of the various thresholds of g by the corresponding ones in f. Therefore, sizes and positions of the connected components of the thresholds of the marker function are irrelevant. Only their occurrence is important.
SADDLES
Saddles are other important characteristic features of a function. Defining a saddle is not easy, especially for digitised functions. However, it is possible to exhibit the regions of a function where saddles are, with the help of its thresholds Xi (f) = {x : f (x) < i}.
A saddle corresponds to the configuration illustrated in Fig. 2:
Fig. 2. Saddle configuration and corresponding thresholds.
A simple way to mark this saddle zone consists in a three-step process:
-     computation of the geodesic zones of influence of Xi-1 inside Xi (Fig. 3a).
-     computation of the geodesic zones of influence of (Xi)c inside (Xi-1)c (Fig. 3b).
-     marking (intersection of separation lines, Fig. 3c).
138
Image Anal Stereol 2001;20:137-141
(a)                                          (b)                                               (c)
Fig. 3. Saddle marking by computational geodesic influence zones of three successive thresholds of the function.
This transformation can be performed directly on the function f. In this case, however, as the geodesic zones of influence need to be built, we must replace the erosion and dilation operators in the reconstruction by homotopic thinning and thickening (Serra, 1982):
HRg (f) = Thickg +  (f), Thickg +  (f) iteration of Thickg(f) = Inf (f•[T],g)
HR*g (f) = Thing +  (f), Thing +  (f) iteration of Thing(f) = Sup(f°[T'],g)
(3)
(4)
[T] and [T’] represent the sets of structuring elements used in homotopic thickenings and thinnings respectively.
The indicator function s(f) of the saddle zones is given by:
s(f) = Inf[f-HRf(f-1),HR*f(f + 1)-f]   (5)
SADDLE ZONES, OVERFLOW AND LOWER CATCHMENT BASINS
The interest in the saddle zones, in the watershed transform, results from the fact that merging of two adjacent catchment basins most of the time occurs through some specific saddle zones also called overflow zones (there exists a particular case where there is no saddle, this case is explained later).
A subset of each catchment basin called the lower catchment basin can be defined. It corresponds to the points of the catchment basin which are below the first overflow (Fig. 4).
Each lower catchment basin corresponds at least to one overflow zone. Obviously, this overflow zone is not necessary the same for two adjacent catchment basins. Very often, overflow zones correspond to saddle zones but it is not always the case, mainly for two reasons:
-    an overflow may occur even if there is no saddle configuration. This is the case, for instance, when the whole contour of a catchment basin is at the same altitude;
-    some saddle zones are local saddle zones, which occur inside a catchment basin and even inside a lower catchment basin. Some other saddle zones are not local, they link adjacent catchment basins and correspond in fact to the overflow zones (Fig. 5).
Fig. 4. Lower catchment basins.
Fig. 5. Local (right) and regional (left) saddle zones. The later ones are called overflow zones.
FROM SADDLE ZONES TO OVERFLOW ZONES
Therefore, selecting the overflow zones among the saddles seems to be difficult. But, in fact, except in the first case described above, these overflow zones correspond to minima of the watershed lines. Indeed, each time the water fills in a lower catchment basin and pours into the adjacent one through the overflow zone, an initial watershed line appears. This element of the watershed line is at a minimal altitude.
It may happen, however, as mentioned above, that an overflow does not occur through a minimum watershed line, in particular when a catchment basin is totally surrounded by a watershed line at a constant height and higher than the adjacent watershed lines.
139
Beucher S: Geodesic reconstruction, saddle zones & hierarchical segmentation
But this particular case has no incidence on the next step of the process, the construction of the hierarchical function.
OVERFLOWS, WATERFALLS AND HIERARCHY
A very interesting approach of the hierarchical segmentation by watersheds is available by means of the Waterfall transformation. This transformation allows to reduce the over-segmentation of the watershed transform and to extract homogeneous regions in the image composed of catchment basins sharing similar characteristics. Furthermore, this transformation is non parametric (although some introduction of parameters can be performed during the process) and it can be iterated.
It has been shown by Beucher (1990) that the first hierarchy of segmentation is the result of a watershed transformation applied to a graph defined from the initial watershed and a derived representation called mosaic image. This mosaic image itself is not compulsory if we build from the initial function a new function called the hierarchical function. This hierarchical function is made of the initial function where all the lower catchment basins have been filled (Fig. 6). Filling these lower catchment basins can be achieved by a geodesic dual reconstruction of the
initial image by the valued indicator of the overflow zones (regional saddle zones).
Fig. 6. Building the hierarchical function.
Now, according to the properties of the geodesic reconstruction previously described, this reconstruction is equivalent to the reconstruction of the initial function by the watershed function w (Beucher, 1994):
w(x) = f(x) if x belongs to the watershed of f
w(x) = M if not.
Indeed, overflow zones are marked by the minima of the watershed function. Therefore, it is legitimate to get the hierarchical image by means of a dual reconstruction from the watershed function.
Fig. 7. Example of hierarchical segmentation of a road scene (a). Two successive levels of hierarchy (c & d) can be found from the initial watershed (b).
140
Image Anal Stereol 2001;20:137-141
(a)
(b)
(c)
Fig. 8. Hierarchy of sizes in a foam material [initial image, courtesy of O. Lordereau, Phys. Dpt., Rennes Univ., Fr] (a). Criterion image (sizes) (b), hierarchy of regions of different sizes (c).
The hierarchical segmentation can be iterated to exhibit higher levels of hierarchy. This technique can be used to efficiently segment images according to various criteria: grey values, colour, shape, etc. Fig. 7 above gives an example of such a hierarchy applied to the colour gradient image of a road scene. Fig. 8 below is another example of hierarchy extraction based on sizes of bubbles in a foam material. By labelling each bubble with its size, then by computing the gradient of the labelled image and applying the hierarchical segmentation, a hierarchy appears, made of regions of different bubbles sizes in the image.
CONCLUSION
The geodesic reconstruction has been already a well-known tool in Mathematical Morphology. Its use in hierarchical segmentation proves its efficiency in all the steps of the process, from minima detection
to hierarchical image construction. The role of the overflow zones, a specific subset of the saddle zones, to underline the different levels of hierarchy of the watershed transformation and the importance of some properties of this reconstruction in the design of a simple Waterfall transform algorithm are also emphasized.
REFERENCES
Beucher S (1990). Segmentation d’images et Morphologie Mathématique. Doctorate thesis, Ecole des Mines de Paris, Cahiers du centre de Morphologie Mathématique, Fascicule n° 10, Juin 1990.
Beucher S (1994). Watershed, hierarchical segmentation and waterfall algorithm. In: Jean Serra, Pierre Soille, eds. Proc. Mathematical Morphology and its Applications to Image Processing. Fontainebleau: Kluwer Ac. Publ., 69-76.
Serra J (1982). Image Analysis and Mathematical Morphology. London: Academic Press.
141