The purpose of this small tutorial is to briefly
explain the philosophy currently used when dealing with image
segmentation problems in mathematical morphology. This methodology is
built around a tool, the watershed transformation.
We shall see first the principle of this
watershed transformation, then one of its major enhancements, the marker-controlled watershed. Next, the general methodology of the watershed segmentation
will be introduced, together with some examples of
applications. Then, some refinements, mainly based on a hierarchical approach, will be introduced. Finally,
recent developments aiming at enhancing the
hierarchical approach will be described.
Any greytone image can be considered as a topographic surface.
If we flood this surface from its minima
and, if we prevent the merging of the waters coming from different
sources, we partition the image into two different sets: the catchment basins and the watershed
lines.
If we apply this transformation to the image gradient, the catchment basins should
theoretically correspond to the homogeneous grey level regions of this
image.
From top to bottom and
from right to left:
Original image.
Gradient image.
Watershed of the
gradient image.
Final contours.
However, in practice, this transform produces an
important over-segmentation due to noise
or local irregularities in the gradient image.
Electrophoresis
gel image and watershed transformation of the
gradient image.
Segmenting an image by the
watershed transformation
is therefore a two-step process:
Finding
the markers and the segmentation criterion (the criterion or function
which will be used to split the regions - it is most often the contrast
or gradient, but not necessarily).
Performing a
marker-controlled
watershed with
these two elements.
In the following examples, we
present the initial
image, the marker set, the image used for the watershed transformation
(criterion) and the final result.
Road segmentation
In
this example, the markers have been introduced by hand. A similar
technique, but with an automatic detection of the markers, is used in
the PROMETHEUS
project.
Coffee beans separation
In this case, the criterion
used is not the
contrast (which is irrelevant) but the distance function of the initial
image.
Traffic monitoring
In order to count the
vehicles
in the different
lanes of the road, even if the video camera is remotely controlled,
an automatic segmentation of the lanes must be performed. Two
images are generated from the scene: an average image (emphasizing the
still regions of the scene) and a differential image (enhancing the
moving parts of the scene).
The
lane markers and the criterion function (made of a combination of a
distance function and of a ground marking extraction) are processed by
watershed.
Cleavage fracture in steel
The
problem here consists in extracting the cleavage facets from a
fractured surface in steel (MEB image). A rather complex combination of
contrast and distance functions is used in this example.
Silver grains on a photographic plate
This example is more
difficult
than the coffee
beans application because the overlapping regions must be segmented too.
The watershed transformation
can also be used to
define a hierarchy among the catchment
basins. Starting from the initial watershed transformation of the
gradient image, a mosaic image can be
defined, and then its associated gradient.
Initial image (left) and initial watershed of the gradient
(right).
From
this image, a new criterion function is built (based on the relative
heights of the walls separating the initial catchment basins). The
watershed transformation applied to this image provides a higher level
of hierarchy in the segmented image (thus suppressing much of the
over-segmentation).
This transformation is named Waterfalls Transformation. Mosaic image (left) and first level of hierarchy (right).
Many other techniques and tools can be used to
define a hierarchy on an image. Most of them are based on a flooding
process.
The Waterfalls
Transformation has two
major drawbacks.
The first one comes from the fact that it is difficult
to find a "good" level of hierarchy. Very often, the first level
of hierarchy dramatically enhances the segmentation by removing lots of
non significant contours, but it is not always sufficient. If the
Waterfalls transform is applied again, the new segmentation may seem
better... or worse...
Successive levels of hierarchy of the gradient watershed of the left image. Does level 2 (third image) seem better?
The second drawback is even more serious. When applying
successive Waterfalls transforms, the intermediary levels of hierarchy
obtained before the process ends with the empty set are often strange
with, indeed, non significant contours which are removed but also, and
it is really annoying, significant ones!
Successive levels of hierarchy produced by successive Waterfalls transformations
This defect is sometimes called the Waterfalls Transformation Short-sightedness.
This two major problems can be solved by applying P algorithm.
This algorithm consists in re-introducing, at each hierarchical step,
contours which have been suppressed according to similarity of contrast
and topological criteria. This algorithm is non parametric and always
ends with a pretty good segmentation of the image as illustrated in the
following examples.
Some examples of segmentation by P Algorithm. Compare
the second example with the result obtained after a first step of
Waterfalls transform (above). This P algorithm works also perfectly on
color images (the last picture comes from the Berkeley Segmentation Dataset and Benchmark).
To learn more about Watershed transformations, Waterfalls Transformations, Hierarchical segmentation and P Algorithm, please go here.
