ImageAnalStereol2009;28:93-102
OriginalResearchPaper
IMAGESEGMENTATION:A WATERSHEDTRANSFORMATION
ALGORITHM
LAMIAJAAFARBELAID1ANDWALIDMOUROU2
1EcoleNationaled’Ing´ enieursdeTunis& LAMSIN, CampusUni versitaire,BP37,leBelv´ ed` ere,1002,Tunis,
Tunisia;2InstitutNationaldelaStatistiquedeTunis&LAMSIN,70rue Ech-Cham,BP256,2000,Tunis,Tunisia
e-mail: lamia.belaid@esstt.rnu.tn,mourou.walid@lamsi n.rnu.tn
(AcceptedMarch27,2009)
ABSTRACT
Thegoalofthisworkistopresentanewmethodforimagesegme ntationusingmathematicalmorphology.The
approach used is based on the watershed transformation. In o rder to avoid an oversegmentation,we propose
toadaptthetopologicalgradientmethod. Thewatershedtra nsformationcombinedwithafastalgorithmbased
on the topologicalgradientapproachgivesgood results. Th e numericaltests obtainedillustrate the efficiency
ofourapproachforimagesegmentation.
Keywords: image segmentation, mathematical morphology, t opological asymptotic expansion, topological
gradient,watershedtransformation.
INTRODUCTION
Segmentationisoneofthemostimportantproblem
in image processing. It consists of constructing a
symbolic representation of the image: the image
is described as homogeneous areas according to
one or several a priori attributes. In the literature,
we can find various segmentation algorithms. The
first method appeared during the sixties and then
different algorithms have been constantly developed.
The purpose of this work is to adapt a new method
for image segmentationusing the topological gradient
approach (Masmoudi, 2001) and the watershed
transformation (Soille, 1992).
The goal of topological optimization is to find
the optimal decomposition of a given domain in
two parts: the optimal design and its complementary.
Similarly in image processing, the goal is to split
an image into several parts, in particular, in image
restorationthedetectionofedgesmakesthisoperation
straightforward. In Jaafar Belaid et al.(2006), the
authors show that it is possible to solve the image
restoration problem using topological optimization
tools. The basic idea was based on the topological
gradient approach used for crack detection (Amstutz
et al., 2005): an image can be viewed as a piecewise
smooth function and edges can be considered as a
set of singularities. To solve restoration problems,
diffusive methods were associated to the topological
gradientforedgedetection.Moreprecisely,aclassical
way to restore an image ufrom its noisy version vdefined in a domain Ω∈R2is to solve the following
PDEproblem
/braceleftbigg
−div(c∇u)+u=vinΩ,
∂nu=0 on ∂Ω,(1)
wherecis a small positive constant (called the
conductivity), ∂ndenotes the normal derivative and
nis the outward unit normal to ∂Ω. Classical
nonlinear diffusive approaches are based on the fact
thatcis a decreasing function of |∇u|, and takes
its values in the interval ]0,c0[, wherec0is a given
constant depending on the level of noise. Then, in
Jaafar Belaid et al.(2006), the authors propose to
use the topological gradient as a tool for detecting
edges for image restoration by considering only two
values of c:c0in the smooth part of the image
and a small value ε>0 on the edges. For this
reason, classical nonlinear diffusive approaches could
be seen as a relaxation of the topological gradient
method. By enlarging the set of admissible solutions,
relaxation increases the instability of the restoration
process and this could explain why the topological
gradient method is so efficient. Then, using the same
idea, the authors generalize in Auroux et al.(2007)
the topological gradient approach for classification
problemsandproposeanextensiontoanunsupervised
classification. A natural application of this idea is the
problem of segmentation: since the identification of
the main edges of the image allows us to preserve
them and smooth the image outside the edges,
then if the conductivity coutside edges is large
93
JAAFARBELAIDLET AL:Imagesegmentation
enough, the regularized image is piecewise constant
and provides a natural segmentation of the image.
However, this efficient technique introduced by some
of the authors in Jaafar Belaid et al.(2006; 2008),
Auroux and Masmoudi (2006), Auroux et al.(2007),
and Auroux (2008), to solve severalimage processing
problemslikerestoration,classification,segmentation,
inpainting and enhancement or denoising, presents
a major drawback: the identified edges are not
necessarily connected and then the results obtained
for the segmentation problem can be degraded,
particularly for complex images. So, the main
idea of this work is to take advantage of the
topological gradient efficiency, to detect the main
contours with an interesting computational cost (the
topological gradient algorithms require only three
system resolutions) and to overcome the drawback of
the topological gradient approach by using a method
givingclosedcontours.
The watershed transformation is one of the oldest
segmentation techniques which was initially due to
Beucher and Lantu´ ejoul (Beucher and Lantu´ ejoul,
1979; Beucher, 1990). This technique is well known
to be a very powerful segmentation tool. Gray level
images are considered as topographic reliefs, each
relief is flooded from its minima and when two lakes
merge,adamisbuilt:thesetofalldamsdefinetheso-
calledwatershed.Suchrepresentationofthewatershed
simulatesthefloodingprocess.Otherprocessescanbe
foundintheliterature,particularlyefficientalgorithms
for computing watersheds are described in Beucher
(1990) and Soille (1992). One of the advantages
of the watershed transformation is that it always
provides closed contours, which is very useful in
image segmentation. Another advantage is that the
watershed transformation requires low computation
timesincomparisonwithothersegmentationmethods.
However, using a standard morphological watershed
transformationontheoriginalimageoronitsgradient,
we usually obtain an oversegmented image. To
decrease the oversegmentation of watershed based
techniques, several approaches have been proposed
in the literature, we can cite for example techniques
based on markers (Meyer and Beucher, 1990), region
merging methods (Vincent and Soille, 1991), scale
space approaches (Jackway, 1999), methods based
on partial differential equations for image denoising
or edge enhancement (Weickert, 2001), wavelet
techniquescombined with a watershed transformation
(JungandScharcanski,2005),etc.
The goal of this work is to deal with the
oversegmentation problem, by proposing a new
method based on a fast topological gradient algorithm
and a watershed transformation. The structure of thiswork is the following. The next section is devoted
to the two basic methods considered in this paper.
First, we review the topological gradient approach
for edge detection. Then, according to Matheron and
Serra(1998)andSerra(1982;1988),somepreliminary
notions and morphological operators which will
be used in this paper, are described. In section
Results, we propose a watershed algorithm based on
the topological gradient method. Numerical results
are presented and discussed, and some numerical
comparisons with other methods are also given in
this section. We end this paper with some concluding
remarks.
METHODS
THETOPOLOGICALGRADIENT
APPROACH
In this section, we use the topological gradient as
a tool for detecting edges for image restoration. First,
we recall the principle of the topological asymptotic
expansion(Masmoudi,2001;Amstutz etal., 2005).
LetΩbe an open bounded domain of R2and
j(Ω) =J(uΩ)be a cost function to be minimized,
whereuΩis the solution to a given PDE problem
definedin Ω. The initial problem reads as follows: for
agivenfunction vinL2(Ω),wehavetofind u∈H1(Ω)
suchthat/braceleftbigg
−div(c∇u)+u=vinΩ,
∂nu=0 on ∂Ω,(2)
wherecis apositiveconstant.
Forasmall ρ≥0,letΩρ=Ω\σρbetheperturbed
domain by the insertion of a crack σρ=x0+ρσ(n),
wherex0∈Ω,σ(n)is a straight crack, and na unit
vectornormal to the crack.The topologicalsensitivity
theory provides an asymptotic expansion of jwhenρ
tendsto zero.It takesthe generalform
j(Ωρ)−j(Ω) =f(ρ)G(x0,n)+◦(f(ρ)),(3)
wheref(ρ)is an explicit positive function going to
zero with ρandG(x0,n)is called the topological
gradientatpoint x0.
For a given function vinL2(Ω), we consider the
following problem:find uρ∈H1(Ωρ)suchthat
/braceleftbigg
−div/parenleftbig
c∇uρ/parenrightbig
+uρ=vinΩρ,
∂nuρ=0 on ∂Ωρ.(4)
Thebasicideaisasfollows.Ifweinsertacrackinaflat
part of the image, nothing happens. But, if we insert
a crack along an edge (strong gradient), the potential
energydecreases.Then,edgedetectionisequivalentto
94
ImageAnalStereol2009;28:93-102
look for a subdomain of Ωwhere the energy is small.
So our goal is to minimize the energy norm outside
edges
j(ρ) =J(uρ) =/integraldisplay
Ωρ/bardbl∇uρ/bardbl2, (5)
by considering v0, thesolutionto the adjointproblem
/braceleftbigg
−div(c∇v0)+v0=−∂uJ(u)inΩ,
∂nv0=0 on ∂Ω.(6)
We obtain in the case of a crack σρ(n)with a
boundary condition ∂nu=0 on∂σρ(n), the following
topologicalasymptoticexpansion
j(ρ)−j(0) =ρ2G(x0,n)+◦(ρ2),(7)
with
G(x0,n) =−πc(∇u0(x0).n)(∇v0(x0)·n)
−π|∇u0(x0)·n|2.
Thetopologicalgradientcouldbewritten as
G(x,n) =/a\}bracketle{tM(x)n,n/a\}bracketri}ht, (8)
whereM(x)isthe symmetricmatrix definedby
M(x) =−πc∇u0(x)∇v0(x)T+∇v0(x)∇u0(x)T
2
−π∇u0(x)∇u0(x)T.
For a given x,G(x,n)takes its minimal value
whennis the eigenvector associated to the lowest
eigenvalue λminofM. This value will be considered
as the topological gradient associated to the optimal
orientation of the crack σρ(n). We note that from a
numerical point of view, cracks are simulated by a
small value of c. It is more convenient for numerical
implementation. The restoration algorithm consists
in inserting small values of c(cracks) in regions
where the topological gradient is smaller than a given
threshold α<0. These regions are the edges of the
image.Thealgorithm is asfollows.
Topologicalgradientalgorithm
–Initialization : c=c0.
–Calculation of u0andv0the solutionsof the direct
(Eq. 4)andadjoint(Eq.6)problems.
–Computation of the 2 ×2 matrix M and its lowest
eigenvalue λminateachpointofthedomain Ω.
–Set
c1=/braceleftbigg
εifx∈Ω,λmin<α<0,ε>0
c0elsewhere .(9)
–Compute u1,the solutionofEq.2with c=c1.
We refer the reader to Jaafar Belaid et al.(2008),
for some theoretical and numerical comparisons with
conventionalrestorationmethods.THEWATERSHED TRANSFORMATION
One aim of this work is to show how the use of
mathematicalmorphologyoperatorscanbeveryuseful
in image segmentation.Particularly, we show how the
watershed transformation contributes to improve the
numerical results for image segmentation problems.
We describe briefly in this section the basic notions
andoperatorswe use.
Letu(x,y)with(x,y)∈R2, be a scalar function
describing an image I. The morphological gradient of
Iis definedin Beucher etal.(1993)by
δDu= (u⊕D)−(u⊖D), (10)
where (u⊕D)and(u⊖D)are respectively the
elementarydilationanderosionof ubythestructuring
elementD.
ThemorphologicalLaplacianis givenby
ΔDu= (u⊕D)−2u+(u⊖D).(11)
We note here that this morphological Laplacian
allows us to distinguish influence zones of minima
and suprema: regions with ΔDu<0 are considered
as influence zones of suprema, while regions with
ΔDu>0 are influence zones of minima. Then
ΔDu=0allowsustointerpretedgelocations,andwill
represent an essential property for the construction of
morphologicalfilters. The basic idea is to apply either
a dilation or an erosion to the image I, depending on
whether the pixel is located within the influence zone
ofaminimumoramaximum.Foradetailedtreatment
ofthis topic,the readerisreferred to Serra(1988).
The Catchment basin C(M)associated to a
minimum Misthesetofpixels pofΩsuchthatawater
dropfallingat pflowsdownalongtherelief,following
a certain descending path, and eventually reaches M.
Thecatchmentbasinsofanimage Icorrespondthento
the influence zones of its minima, and the watershed
will be defined by the lines that separate adjacent
catchmentbasins.
Several algorithms have been proposed for the
computation of watersheds and the most commonly
used are based on an immersion process analogy.
Let us express this immersion process more formally
according to Soille (1992): we consider hminandhmax
the smallest and the largest values taken by u. Let
Th={p∈Ω,u(p)≤h}be the threshold set of uat
levelh. We define a recursion with the gray level
95
JAAFARBELAIDLET AL:Imagesegmentation
hincreasing from hmintohmax, in which the basins
associated with the minimum of uare successively
expanded.Weconsider Xhtheunionofthesetofbasins
computed at level h. A connected component of the
threshold set Th+1at levelh+1 can be either a new
minimum, or an extension of a basin in Xh. Finally,
by denoting by min hthe union of all regional minima
at levelh, we obtain the following recursion which
definesthewatershedbyimmersion
/braceleftbigg
Xhmin=Thmin,
∀h∈[hmin,hmax−1],Xh+1=minh+1∪IZTh+1(Xh),
withIZTh+1=k/uniondisplay
i=1izTh+1(Xhi), wherekis the number of
minima of I, andizTh+1(Xhi)is definedby
izΩ(Yi) ={z∈Ω,∀k/\e}atio\slash=i,dΩ(z,Yi)≤dΩ(z,Yk)}.
(12)
Thesetofthecatchmentbasinsofagraylevelimage I
is equalto the set Xhmax. At theend ofthis process,the
watershed of the image Iis the complement of Xhmax
inΩ.
It is well known that the main problem of this
method is that the images we consider are often
noisy, which implies that we have a lot of local
minima and this leads to an oversegmentation. We
propose in this paper, a new method for decreasing
the oversegmentation of standard watershed based
techniques. Our method is based on the topological
gradient approach. The topological gradient has here
the interesting property to give more weight to
the main edges, it provides a more global analysis
of the image than the Euclidean gradient or the
morphological gradient, so results are less sensitive
to noise as we show it in the numerical applications
section.
RESULTS
TOPOLOGICALGRADIENTAND EDGE
DETECTION
We consider in this section the problem of
denoising an image and preserving features such
as edges. According to the previous section, the
topological asymptotic analysis provides the location
of the edges as they are precisely defined as the most
negative points of the topological gradient. Fig. 1
shows the results obtained by the topological gradient
algorithm. The image processed given by Fig. 1a is a
256×256 gray level image and represents some rice
grains. Fig. 1b is obtained by adding to the originalimage a Gaussian noise ( σ=20). The reconstructed
image is shown in Fig. 1c: the topological gradient
method for the restoration process was applied with
c0=1,ε=10−3, andα=−70. Finally, we give in
Fig.1d,theedgesofthereconstructedimage.Toobtain
the restored image, the topological gradient algorithm
requires only 3 system resolutions for calculating u0,
v0and the restored image u1given respectively by
Eqs. 4, 6, and 2. For a better edge preservation,
one has to threshold the topological gradient with
a small enough coefficient. In the other case, if
the thresholding coefficient is set to a large value,
then the edges obtained will be thick, leading to
an oversmoothing and a loss of an important edge
information and then a degradation of the restored
image.Finally,tospeedupthecomputations,aspectral
method based on the discrete cosine transform has
been used for the resolution of the direct and adjoint
problems.Sincethecoefficient cis equalto aconstant
c0except on edges, then the discrete cosine transform
is a good preconditioner for the conjugate gradient
method. The complexity of the restoration algorithm
isO(NlogN)whereNis the number of pixels of
the image. Some comparisons about the computation
times with other classical methods are presented in
JaafarBelaid etal.(2008).
SEGMENTATIONUSING ACLASSICAL
WATERSHED TRANSFORMATION
The goal of this section is to present numerical
testsforthesegmentationproblemusingmathematical
morphology tools. The approach used in this work
is based on the watershed transform. One should
remark that we can either define the watershed of the
functionuor of its gradient: the difference between
the two definitions is that in the first case we obtain
the influence zones of the processed image, while
the second case gives the image edges. In both
cases, the watershed gives an oversegmentation and
to avoid this drawback, a markers technique can be
used. We propose in this section to give numerical
results based on this classical method according to
the work of Beucher (1990), in which the author has
proposed to use both influence zones and minima of
the filtered image as marker criteria. Fig. 2 illustrates
this approach. We have considered the same original
image as previously. Fig. 2a shows the watershed of
the image and Fig. 2b shows the watershed of its
gradient. The oversegmentation is clearly seen. We
should mention here, that the numericaltests givenby
Fig. 2b give a segmentedimage with 1905 regions for
a computational time of 550 s. This oversegmentation
can be in a first step corrected by applying a
morphological filter. Fig. 2c shows the watershed of
96
ImageAnalStereol2009;28:93-102
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
(a) ( b) ( c) ( d)
Fig. 1.Restoration and edge detection processes by the topologica l gradient approach: original image (a), (b)
is the noisy image obtained by adding a Gaussian noise ( σ=20), (c) is the restored image, and (d) shows the
detectededges.
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
(a) ( b) ( c) ( d)
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
(e) ( f) ( g) ( h)
Fig. 2.Classical segmentation technique using morphological ope rators: (a) is the watershed of the original
image and (b) is the watershed of its gradient, (c) is the segm entation result of the filtered image, (d) shows the
minima of the original image and (e) are the minima of the filte red image, (f) are the new influence zones, (g)
showstheimage(e)superposedonthe influencezones,andfina lly(h)is thesegmentedimage.
the filtered image: the number of regions segmented
is attenuated (868 regions) for a computational
time of 775 s, but the segmentation result remains
unacceptable.However,astheoversegmentationisdue
to the fact that we obtain a lot of minima, and the
use of morphological filters can only suppress some
of them, then another way to act on these minima
is to apply the swamping approach, by imposing
markers for new minima. Fig. 2d shows the minima
of the original image and Fig. 2e shows the minima
of the filtered one. Clearly, the number of minima is
attenuated. To obtain the wanted final contours which
derived from the watershed of the gradient modulus,
we have to compute the watershed of the swamping
of the gradient modulus of the filtered image. Fig. 2f
showsthe newinfluencezonesobtainedwhich will be
used as markers. For better visualization, we presentin Fig. 2g the new influence zones superimposed on
minima obtained in Fig. 2e. Finally, Fig. 2h shows
the contours obtained after the segmentation process
usingthis approach.Somecriticisms canbeexpressed
according to this approach: one can remark that the
detectionofthericegrainsisnotperfect.Infact,some
of them are badly detected and others are completely
eliminated. These drawbacks can provide either from
the choice of the marker criterion used to detect the
grain contours or the choice of the influence zones
as markers. It can also come from the choice of
the watershed transform. However, some additional
morphological operators can be used for overcoming
such drawbacks, see for example Decenci` ere et al.
(2005).
97
JAAFARBELAIDLET AL:Imagesegmentation
TOPOLOGICALGRADIENTAND
WATERSHED
We propose in this part a new algorithm for the
segmentationproblemwhichcombinesthetopological
gradient approach with a watershed transformation.
Our goal is to improve the segmentation results by
considering the second kind of watershed transforms
(the watershed of the image gradient) previously
defined, using a topological gradient instead of
the morphological gradient classically used with
watersheds. As mentioned previously, the topological
gradient is much less sensitive to noise and small
variations of the image, than the Euclidean and
morphologicalgradients.Thisisduetothefactthatthe
topologicalgradientevaluatesinaglobalwaywhether
a pixel is a part of an edge or not, compared to the
Euclidean gradient which has more local properties.
On the other hand, as the morphological gradient
corresponds in a certain way to the modulus of the
Euclideangradient,thenitwillbeeasytoconcludethat
thetopologicalgradientprovidesthebestidentification
of the main edges of the processed image, and the
oversegmentation obtained in the previous numerical
results, will be clearly attenuated. Fig. 3 shows the
three gradients: Fig. 3a is the topological gradient
and Figs. 3b-c are respectively the Euclidean gradient
and the morphological gradient. The edges defined
by the Euclidean and the morphological gradients are
very accentuated in comparison with those defined
by the topological gradient. This thickness of edges
provides a loss of edge information. This was our first
motivation.
Since the topological gradient is the best tool for
preserving the most important edges and eliminating
all the other insignificant ones, then the first idea
was to replace the morphological gradient by a
topological gradient in order to minimize the set of
minima of I, leading to better segmentation results.
Our algorithm is then composed of two different
and separate steps: the first one consists of detecting
the main edges of the image using the topological
gradient restoration process. Then, the second step
consists of applying the watershed algorithm using
the topological gradient determined in the first step,
instead of the morphological gradient classically
used in watershed algorithms. Fig. 4 illustrates this
segmentation process. The first results obtained are
very promising. Fig. 4a shows the segmented image
obtained with this approach. It should be noted that
we obtain 587 homogeneous regions and that our
new algorithm requires around 1500 CPU seconds.
The computation times are then more or less similar
between the two methods (this is due to the fact that
the computation time may depends of the processedimage). We recall here that the topological gradient
algorithm is solved with a O(NlogN)complexity and
thatthe watershedalgorithm runsin a lineartime with
respectto the number Nofpixelsoftheimage.
Unfortunately,asshowninFig.4a,someunwanted
crest lines remain at the end of the segmentation
process. To better illustrate these unwanted regions,
we give in Fig. 4d the detected contours after
the segmentation process: we have more segmented
regions than what we should obtain. In order to
improveoursegmentationprocessandtoattenuatethe
number of these unwanted crest lines, we propose to
accentuatethesmoothingonbothsidesofanedge.The
idea until now was to choose c≈1, but this choice
is not so appropriate for the segmentation problem.
We propose then, an improvement of the previous
algorithm as follows we considerthe following partial
differentialequation
/braceleftbigg
−div/parenleftbig
c(ε)∇uρ/parenrightbig
+uρ=vinΩρ,
∂nuρ=0 on ∂Ωρ,(13)
withc(ε) =εon the edges and c0/εelsewhere, ε>0
andc0is agivenpositiveconstant.
In comparison with the previous section, the
topological gradient and the general algorithm remain
unchangedsince the new algorithm proposed is based
on the same restoration algorithm but according to
Eq. 13. The edge set is still given by the thresholding
λmin, but from numerical point of view, by choosing
large values of c, our partial differential equation is
nearlyequivalentto Δu=0whichwillprovideareally
smooth image outside edges leading to a considerable
attenuationofsegmentedregions.
The numerical results of this approach are
illustrated in Fig. 4, by considering three values of
the coefficient c. Fig. 4b is obtained with c=25.
It should be noted that we obtain 153 homogeneous
regions and our algorithm requires around 340 CPU
seconds. Fig. 4c is obtained with c=50 and gives
only 120 homogeneous regions with a computational
time of 290 seconds. Finally, for a better illustration
of the segmented regions, we represent in Figs. 4d-f
the detected contours after our segmentation process.
Moreover, to better illustrate the efficiency of our
method, we present other numerical results by
considering more complex images. The two real
imagespresentedinthispaperhavevariousdifficulties
(curves, circles, straight lines, etc.). The first image
is a 302 ×280 fruit-basket gray level image and the
second one is a 399 ×246 gray level image which
represents a road scene. We present in Fig. 5 the two
original images and the reconstructed edges by the
topologicalgradientapproach,afteraddingaGaussian
noise(σ=20)to theoriginalimages.
98
ImageAnalStereol2009;28:93-102
50 100 150 200 25050
100
150
200
250−120−100−80−60−40−200
50 100 150 200 25050
100
150
200
2505101520253035
50 100 150 200 25050
100
150
200
250
0102030405060708090100
(a) ( b) ( c)
Fig. 3.Thetopologicalgradient(a), the Euclideangradient(b), a ndthemorphologicalgradient(c).
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
(a) ( b) ( c)
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
50 100 150 200 25050
100
150
200
250
(d) ( e) ( f)
Fig. 4.Segmentation results using a watershed transformation app lied to the topological gradient: the images
(a), (b)and(c)areobtainedbytheproposedapproachwith c =1,c=25andc=50andtheimages(d),(e)and
(f) showrespectivelythedetectedcontoursafterthe segme ntationprocess.
50 100 150 200 250 30050
100
150
200
250
50 100 150 200 250 30050
100
150
200
250
50 100 150 200 250 300 35050
100
150
200
50 100 150 200 250 300 35050
100
150
200
(a) ( b) ( c) ( d)
Fig. 5.Examples of real images: (a) is a fruit-basket original imag e, (b) shows the detected edges according to
thetopologicalgradientapproach,(c)isaroadsceneorigi nalimage,and(d)showsthedetectededgesusingthe
topologicalgradientapproach.
99
JAAFARBELAIDLET AL:Imagesegmentation
50 100 150 200 250 30050
100
150
200
250
50 100 150 200 250 30050
100
150
200
250
50 100 150 200 250 300 35050
100
150
200
50 100 150 200 250 300 35050
100
150
200
(a) ( b) ( c) ( d)
Fig. 6.Segmentation results using a watershed algorithm combined with the topological gradient approach:(a)
isthesegmentedfruit-basketimagewithc =1,(b)isthesamesegmentedimagewithc =50,(c)isthesegmented
roadsceneimagewith c =1,and(d)isthe samesegmentedimagewith c =50.
Fig. 6 shows the segmentation result of the two
previous images, according to our new algorithm: a
coupled method for image segmentation based on
a watershed algorithm and the topological gradient
approach. The results obtained show clearly the
efficiency of the topological gradient for extracting
features from complex images and for reducing
drasticallythe oversegmentation.
The results shown in Figs. 6a-c are obtained with
c=1, we can attenuate the number of identified
regions after the segmentation process by choosing
larger values of the coefficient c, but this will depend
of what we want to segment and what we want to
obtain at the end of the segmentation process: if one
would obtain a maximum of details then it suffices
to takec=1, otherwise, one should consider larger
values of cwhich gives a considerable attenuation of
the segmented regions. Figs. 6b-d show the numerical
results of the segmentation process with c=50. We
can clearly observe an attenuation of the segmented
regionssuchthatthemainedgesofthetwoimagesare
conserved.
COMPARISONWITH AN ACTIVE
CONTOURSMODEL
Finally, due to a large number of approaches
used for the segmentation problem, it clearly appears
that it is important to compare our experimental
resultswithmethodsalreadyproposedintheliterature.
Particularly, we propose to compare our method
with an active contour model based on the level set
approach, which is well known to be an efficient
method,extensivelyusedinmanyapplicationsoverthe
lastdecade.Thebasicidea in activecontourmodelsis
to evolve a curve subject to constraints from a given
image,inordertodetectdifferentobjectsinthatimage.
To achieve this goal, we start with a curve around
the object to be detected, the curve moves toward its
interior normal and has to stop on the boundaryof theobject. This was the first idea of classical snakes and
active contourmodels proposedby Kass et al.(1987).
Our numerical tests are based on a level set method
proposed by Caselles et al.(1997) and given by the
following evolutionequation
∂u
∂t=g(|∇I|)/parenleftbigg
div/parenleftbigg∇u
|∇u|/parenrightbigg
+α/parenrightbigg
|∇u|
+/a\}bracketle{t∇g,∇u/a\}bracketri}ht,in(0,∞)×Ω,
withboundaryandinitialconditionsgivenby ∂u/∂n=0
on(0,∞)×∂ΩandΦ(0,x,y) =Φ0(x,y)inΩ,α≥
0 is a positive given coefficient, g(|∇I|)is an edge
detector function defined in our numerical tests by
g(s) =1/(1+s2),andφ0representstheinitiallevelset
function.WereferthereadertoAubertandKornprobst
(2001)formoredetailsaboutgeodesicactivecontours
and level set methods. Fig. 7 shows the numerical
results obtained. We should mention that in order
to obtain the final contour illustrated in Fig. 7e, the
algorithm requires 500 iterations and a computational
timeof78seconds.WepresentinFig.7somesolutions
as time evolves: during the evolution, the initial curve
is shrinking and stopping as soon as it is close to an
object boundary and spilling in order to detect the
othersobjects.
One can easily detect some drawbacks of this
method. Fig. 7e shows that the interior of the disk is
not segmented:once the curve has detected a contour,
it stops. We represent in Fig. 7f, the same image
segmented using our new approach. Our algorithm
requires38CPUsecondsandthedrawbackseenbefore
is overcome. We also tested this method on a real
151×151 gray level image. Fig. 8 shows the ability
of the model to capture the main object of the image,
whichcanbeimportantforobjecttrackingapplications
for example. On the other case, Fig. 8f is the result
of the segmentation process by our algorithm, and
shows more homogeneous regions detected. This can
be interpreted by an oversegmentation in comparison
100
ImageAnalStereol2009;28:93-102
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
(a) ( b) ( c)
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
20 40 60 80100 120 140 160 180 20020
40
60
80
100
120
140
160
180
200
(d) ( e) ( f)
Fig.7.Segmentationresultsofasyntheticimageusinganactiveco ntourmodel:differentiterationsaredisplayed
from (b)to (e), and(f) isthe segmentedimage usingournewap proach.
with active contours model to capture an object, but
ontheotherhand,thesedifferentregionsextractedcan
beparticularlyhelpfulforcolorprocessingexploration
forexample.Wecanconcludethattheresultsobtained
bythetwomethodsarejustdifferentanddependofthe
objects we want to detect and the kind of applications
we wantto explore.
CONCLUSION
We have presented in this work a new approach
for the segmentation problem taking advantage of
the topological gradient approach and the watershed
transformation. The numerical results obtained are
very promising and the proposed algorithm has many
advantages:
–First, the algorithm costisinteresting.
–Second, as the topological gradient provides a
global analysis of the image then the almost
unwanted contours due to the noise added to a
given image can be significantly reduced by our
approach.
–Third, the experimental results show that the
oversegmentationproblem, which usually appears
with the watershed technique, can be attenuated,
and the segmentation results can be performed
usingthetopologicalgradientapproach.
–Another advantage of this method is that it splits
the segmentation process into two separate steps:
first we detect the main edges of the image
processed, and then we compute the watershed of
the gradientdetected.This methodologyhasmany
advantages, particularly in real life applications.Inspired by the work of Meyer and Beucher
(1990), we propose in a forthcoming paper
to perform our results using marker criteria.
More precisely, as the edges are detected in
regions where the topological gradient is the most
negative, then it suffices to extract some points
which belong to the edge set and then use these
points as a selected marker set. We also intend to
extend this work to color image segmentation and
threedimensionalsegmentation.
ACKNOWLEDGMENTS
We are grateful to the unknown reviewers for
theirvaluablecomments.WealsothankProfessorJean
Serra forhishelpfulsuggestions.
REFERENCES
Amstutz S, Horchani I, Masmoudi M (2005). Crack
detection by the topological gradient method. Control
Cybern34:119-38.
Aubert G, Kornprobst P (2001). Mathematical problems in
imageprocessing.New York:Springer-Verlag.
Auroux D, Masmoudi M (2006). A one-shot inpainting
algorithmbasedonthetopologicalasymptoticanalysis.
ComputApplMath25:1-17.
Auroux D, Jaafar Belaid L, Masmoudi M (2007). A
topological asymptotic analysis for the regularized
gray-level image classification problem. Math Model
NumAnal41:607-25.
Auroux D (2008).From restoration by topological gradient
to medical image segmentation via an asymptotic
expansion.MathComputModel49:2191-205.
101
JAAFARBELAIDLET AL:Imagesegmentation
20 40 60 80 100 120 14020
40
60
80
100
120
140
20 40 60 80 100 120 14020
40
60
80
100
120
140
20 40 60 80 100 120 14020
40
60
80
100
120
140
(a) ( b) ( c)
20 40 60 80 100 120 14020
40
60
80
100
120
140
20 40 60 80 100 120 14020
40
60
80
100
120
140
20 40 60 80 100 120 14020
40
60
80
100
120
140
(d) ( e) ( f)
Fig.8.Segmentationresultsofawaterlilyimageusinganactiveco ntourmodel:differentiterationsaredisplayed
from(b) to (e), and(f) is the segmentedimageusingournewap proach.
Beucher S (1990). Segmentation d’image et Morphologie
math´ ematique. Th` ese de Doctorat, Ecole Nationale
Sup´ erieuredesMinesdeParis.
Beucher S, Rivest J.F, Soille P (1993). Morphological
gradients.JElectronImaging2:326-36.
Beucher S, Lantu´ ejoul C (1979). Use of watersheds in
contour detection. In: Proc Int Worksh Image Process,
Real-TimeEdgeMotionDetection/Estimation,Rennes,
France.Sept 17-21,1979.
Caselles V, Kimmel R, Sapiro G (1997). Geodesic active
contours.IntJComputVision,22:61-79.
Decenci` ere E, Najman L, Ronse C, eds. (2005).
Mathematical morphology: 40 years on. Proc 7th
Int Symp Math Morphol, April 18-20, 2005. Berlin:
Springer-Verlag.
Jaafar Belaid L, Jaoua M, Masmoudi M, Siala L (2006).
Image restoration and edge detection by topological
asymptotic expansion. Compt Rend Acad Sci 342:313-
8.
Jaafar Belaid L, Jaoua M, Masmoudi M, Siala L (2008).
Application of the topological gradient to image
restoration and edge detection. Eng Anal Bound Elem
32:891-9.
Jackway PT (1999). Gradient watersheds in morphological
scale space.IEEETransImageProc5:913-21.
Jung C.R, Scharcanski J (2005). Robust watershed
segmentation using wavelets. Image Vision Comput
23:661-69.
KassM,WitkinA,TerzopoulosD(1987).Snakes:anactivecontourmodels.IntJComputVision1:133-44.
Masmoudi M (2001). The topological asymptotic.
In: Glowinski R, Kawarada H, P´ eriaux J, eds.
Computational methods for control applications.
GakutoIntSeriesMathSci Appl,vol16.Tokyo,53-72.
Matheron G, Serra J (1998). The birth of mathematical
morphology. Centre de Morphologie Mathmatique,
EcoledesMinesdeParis.
MeyerF, Beucher S (1990).Morphologicalsegmentation.J
VisCommunImageRepr1:21-46.
Mumford D, Shah J (1989). Optimal approximations by
piecewise smooth functions and associated variational
problems.CommPureApplMath42:577-685.
Serra J (1982). Image Analysis and Mathematical
Morphology,Vol1.London:AcademicPress.
Serra J (1988). Image Analysis and Mathematical
Morphology, Vol 2: Theoretical Advances. London:
AcademicPress.
Soille P (1992). Morphologie math´ ematique: Du relief ` a
la dimensionnalit´ e, Algorithmes et m´ ethodes. Th` ese
de Doctorat, Facult´ e des Sciences Agronomiques de
l’Universit´ eCatholiquedeLouvrain.
Vincent L, Soille P (1991). Watersheds in digital spaces:
an efficient algorithm based on immersion simulations.
IEEETransPatternAnal13:583-9.
Weickert J (2001). Efficient image segmentation using
partial differential equations and morphology. Pattern
Recogn34:1813-24.
102