# Image segmentation: a watershed transformation algorithm.

INTRODUCTION

Segmentation is one of the most important problem 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 segmentation using 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 restoration the detection of edges makes this operation 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 gradient for edge detection. More precisely, a classical way to restore an image u from its noisy version v defined in a domain S2 E R2 is to solve the following PDE problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

where c is a small positive constant (called the conductivity), [[DELTA].sub.n] denotes the normal derivative and n is the outward unit normal to [DELTA][OMEGA]. Classical nonlinear diffusive approaches are based on the fact that c is a decreasing function of [absolute value of [nabla]u], and takes its values in the interval ]0, [c.sub.0] [, where [c.sub.0] is 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: [c.sub.0] in the smooth part of the image and a small value [epsilon] > 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 problems and propose an extension to an unsupervised 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 c outside edges is large 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 several image processing problems like restoration, 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 giving closed contours.

The watershed transformation is one of the oldest segmentation techniques which was initially due to Beucher and Lantuejoul (Beucher and Lantuejoul, 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, a dam is built: the set of all dams define the so-called watershed. Such representation of the watershed simulates the flooding process. Other processes can be found in the literature, particularly efficient algorithms 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 times in comparison with other segmentation methods. However, using a standard morphological watershed transformation on the original image or on its gradient, 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 techniques combined with a watershed transformation (Jung and Scharcanski, 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 this work 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) and Serra (1982; 1988), some preliminary 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

THE TOPOLOGICAL GRADIENT 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 et al., 2005).

Let [OMEGA] be an open bounded domain of [R.sup.2] and j([OMEGA]) = J([u.sub.[OMEGA]]) be a cost function to be minimized, where [u.sub.[OMEGA]] is the solution to a given PDE problem defined in [OMEGA]. The initial problem reads as follows: for a given function v in [L.sup.2] ([OMEGA]), we have to find u [member of] [H.sup.1]([OMEGA]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

where c is a positive constant.

For a small [rho] [greater than or equal to] 0, let [[OMEGA].sub.[rho]] = [OMEGA]\ [[sigma].sub.[rho]] be the perturbed domain by the insertion of a crack [[sigma].sub.[rho]] = [x.sub.0] + [rho][sigma]](n), where [x.sub.0] [member of] [OMEGA], [sigma](n) is a straight crack, and n a unit vector normal to the crack. The topological sensitivity theory provides an asymptotic expansion of j when [rho] tends to zero. It takes the general form

j([[OMEGA].sub.[rho]]) -j([OMEGA]) = f([rho])G([x.sub.0],u) + o(f([rho])), (3)

where f ([rho]) is an explicit positive function going to zero with p and G([x.sub.0], n) is called the topological gradient at point [x.sub.0].

For a given function v in [L.sup.2]([OMEGA]), we consider the following problem: find [u.sub.[rho]] [member of] [H.sup.1]([[OMEGA].sub.[rho]]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

The basic idea is as follows. If we insert a crack in a flat part of the image, nothing happens. But, if we insert a crack along an edge (strong gradient), the potential energy decreases. Then, edge detection is equivalent to look for a subdomain of S2 where the energy is small. So our goal is to minimize the energy norm outside edges

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

by considering vo, the solution to the adjoint problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

We obtain in the case of a crack [[sigma].sub.[rho]](n) with a boundary condition [[DELTA].sub.nu] = 0 on [DELTA][[sigma].sub.[rho]](n), the following topological asymptotic expansion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The topological gradient could be written as

G(x, n) = <M(x)n, n>, (8)

where M(x) is the symmetric matrix defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For a given x, G(x, n) takes its minimal value when n is the eigenvector associated to the lowest eigenvalue [[lambda].sub.min] of M. This value will be considered as the topological gradient associated to the optimal orientation of the crack [[sigma].sub.[rho]](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 [alpha] < 0. These regions are the edges of the image. The algorithm is as follows.

Topological gradient algorithm

-- Initialization : c = [c.sub.0].

-- Calculation of [u.sub.0] and [v.sub.0] the solutions of the direct (Eq. 4) and adjoint (Eq. 6) problems.

-- Computation of the 2 x 2 matrix M and its lowest eigenvalue [[lambda].sub.min] at each point of the domain [OMEGA].

-- Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

-- Compute [u.sub.1], the solution of Eq. 2 with c = [c.sub.1].

We refer the reader to Jaafar Belaid et al. (2008), for some theoretical and numerical comparisons with conventional restoration methods.

THE WATERSHED TRANSFORMATION

One aim of this work is to show how the use of mathematical morphology operators can be very useful 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 and operators we use.

Let u(x,y) with (x,y) [member of] [R.sup.2], be a scalar function describing an image I. The morphological gradient of I is defined in Beucher et al. (1993) by

[[delta].sub.D]u = (u [??] D) - (u [??] D), (10)

where (u [??] D) and (u [??] D) are respectively the elementary dilation and erosion of u by the structuring element D.

The morphological Laplacian is given by

[[DELTA].sub.D]u = (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 [[DELTA].sub.D]u < 0 are considered as influence zones of suprema, while regions with [[DELTA].sub.D]u > 0 are influence zones of minima. Then [[DELTA].sub.D]u = 0 allows us to interpret edge locations, and will represent an essential property for the construction of morphological filters. 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 of a minimum or a maximum. For a detailed treatment of this topic, the reader is referred to Serra (1988).

The Catchment basin C(M) associated to a minimum M is the set of pixels p of [OMEGA] such that a water drop falling at p flows down along the relief, following a certain descending path, and eventually reaches M. The catchment basins of an image I correspond then to the influence zones of its minima, and the watershed will be defined by the lines that separate adjacent catchment basins.

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 [h.sub.min] and [h.sub.max] the smallest and the largest values taken by u. Let [T.sub.h] = {p [member of] [OMEGA],u(p) [less than or equal to] h} be the threshold set of u at level h. We define a recursion with the gray level h increasing from [h.sub.min] to [h.sub.max], in which the basins associated with the minimum of u are successively expanded. We consider Xh the union of the set of basins computed at level h. A connected component of the threshold set [T.sub.h+1] at level h + 1 can be either a new minimum, or an extension of a basin in [X.sub.h]. Finally, by denoting by minh the union of all regional minima at level h, we obtain the following recursion which defines the watershed by immersion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

The set of the catchment basins of a gray level image I is equal to the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. At the end of this process, the watershed of the image I is the complement of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. in [OMEGA].

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

TOPOLOGICAL GRADIENT AND 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 x 256 gray level image and represents some rice grains. Fig. 1b is obtained by adding to the original image a Gaussian noise ([sigma] = 20). The reconstructed image is shown in Fig. 1c: the topological gradient method for the restoration process was applied with [c.sub.0] = 1, [epsilon] = [10.sup.-3], and [alpha] = -70. Finally, we give in Fig. Id, the edges of the reconstructed image. To obtain the restored image, the topological gradient algorithm requires only 3 system resolutions for calculating [u.sub.0], vo and the restored image [u.sub.1] given 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, to speed up the computations, a spectral method based on the discrete cosine transform has been used for the resolution of the direct and adjoint problems. Since the coefficient c is equal to a constant co except on edges, then the discrete cosine transform is a good preconditioner for the conjugate gradient method. The complexity of the restoration algorithm is O(N1ogN) where N is the number of pixels of the image. Some comparisons about the computation times with other classical methods are presented in Jaafar Belaid et al. (2008).

SEGMENTATION USING A CLASSICAL WATERSHED TRANSFORMATION

The goal of this section is to present numerical tests for the segmentation problem using mathematical 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 function u or 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 numerical tests given by Fig. 2b give a segmented image 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 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, as the oversegmentation is due 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 shows the new influence zones obtained which will be used as markers. For better visualization, we present in Fig. 2g the new influence zones superimposed on minima obtained in Fig. 2e. Finally, Fig. 2h shows the contours obtained after the segmentation process using this approach. Some criticisms can be expressed according to this approach: one can remark that the detection of the rice grains is not perfect. In fact, 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 Decenciere et al. (2005).

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

TOPOLOGICAL GRADIENT AND WATERSHED

We propose in this part a new algorithm for the segmentation problem which combines the topological 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 morphological gradients. This is due to the fact that the topological gradient evaluates in a global way whether 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 Euclidean gradient, then it will be easy to conclude that the topological gradient provides the best identification 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 processed image). We recall here that the topological gradient algorithm is solved with a O(N1ogN) complexity and that the watershed algorithm runs in a linear time with respect to the number N of pixels of the image.

Unfortunately, as shown in Fig. 4a, some unwanted 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 improve our segmentation process and to attenuate the number of these unwanted crest lines, we propose to accentuate the smoothing on both sides of an edge. The idea until now was to choose c [approximately equal to] 1, but this choice is not so appropriate for the segmentation problem. We propose then, an improvement of the previous algorithm as follows we consider the following partial differential equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

with c([epsilon]) = e on the edges and [c.sub.0]/[epsilon] elsewhere, [epsilon] > 0 and co is a given positive constant.

In comparison with the previous section, the topological gradient and the general algorithm remain unchanged since 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 [[lambda].sub.mib] but from numerical point of view, by choosing large values of c, our partial differential equation is nearly equivalent to [DELTA]u = 0 which will provide a really smooth image outside edges leading to a considerable attenuation of segmented regions.

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 images presented in this paper have various difficulties (curves, circles, straight lines, etc.). The first image is a 302 x 280 fruit-basket gray level image and the second one is a 399 x 246 gray level image which represents a road scene. We present in Fig. 5 the two original images and the reconstructed edges by the topological gradient approach, after adding a Gaussian noise ([sigma] = 20) to the original images.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

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 drastically the 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 take c = 1, otherwise, one should consider larger values of c which 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 regions such that the main edges of the two images are conserved.

COMPARISON WITH AN ACTIVE CONTOURS MODEL

Finally, due to a large number of approaches used for the segmentation problem, it clearly appears that it is important to compare our experimental results with methods already proposed in the literature. 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, extensively used in many applications over the last decade. The basic idea in active contour models is to evolve a curve subject to constraints from a given image, in order to detect different objects in that image. 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 boundary of the object. This was the first idea of classical snakes and active contour models proposed by 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 evolution equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

with boundary and initial conditions given by au/an = 0 on (0,[infinty]) x [DELTA][OMEGA] and [PHI](O,x,y) = [[PHI].sub.0](x,y) in [OMEGA], [alpha] [greater than or equal to] 0 is a positive given coefficient, g (I VII) is an edge detector function defined in our numerical tests by g(s) = 1/(1 + [s.sup.2]), and oo represents the initial level set function. We refer the reader to Aubert and Kornprobst (2001) for more details about geodesic active contours 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 time of 78 seconds. We present in Fig. 7 some solutions 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 others objects.

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 requires 38 CPU seconds and the drawback seen before is overcome. We also tested this method on a real 151 x 151 gray level image. Fig. 8 shows the ability of the model to capture the main object of the image, which can be important for object tracking applications 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 with active contours model to capture an object, but on the other hand, these different regions extracted can be particularly helpful for color processing exploration for example. We can conclude that the results obtained by the two methods are just different and depend of the objects we want to detect and the kind of applications we want to explore.

[FIGURE 7 OMITTED]

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 cost is interesting.

-- 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 oversegmentation problem, which usually appears with the watershed technique, can be attenuated, and the segmentation results can be performed using the topological gradient approach.

-- 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 gradient detected. This methodology has many 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 three dimensional segmentation.

[FIGURE 8 OMITTED]

ACKNOWLEDGMENTS

We are grateful to the unknown reviewers for their valuable comments. We also thank Professor Jean Serra for his helpful suggestions.

(Accepted March 27, 2009)

REFERENCES

Amstutz S, Horchani 1, Masmoudi M (2005). Crack detection by the topological gradient method. Control Cybern 34:119-38.

Aubert G, Kornprobst P (2001). Mathematical problems in image processing. New York: Springer-Verlag.

Auroux D, Masmoudi M (2006). A one-shot inpainting algorithm based on the topological asymptotic analysis. ComputAppl Math 25:1-17.

Auroux D, Jaafar Belaid L, Masmoudi M (2007). A topological asymptotic analysis for the regularized gray-level image classification problem. Math Model Num Anal 41:607-25.

Auroux D (2008). From restoration by topological gradient to medical image segmentation via an asymptotic expansion. Math Comput Model 49:2191-205.

Beucher S (1990). Segmentation d'image et Morphologie mathematique. These de Doctoral, Ecole Nationale Superieure des Mines de Paris.

Beucher S, Rivest J.F, Soille P (1993). Morphological gradients. J Electron Imaging 2:326-36.

Beucher S, Lantuejoul C (1979). Use of watersheds in contour detection. In: Proc Int Worksh Image Process, Real-Time Edge Motion Detection/Estimation, Rennes, France. Sept 17-21, 1979.

Caselles V, Kimmel R, Sapiro G (1997). Geodesic active contours. Int J Comput Vision, 22:61-79.

Decenciere 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:3138.

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. IEEE Trans Image Proc 5:913-21.

Jung C.R, Scharcanski J (2005). Robust watershed segmentation using wavelets. Image Vision Comput 23:661-69.

Kass M, Witkin A, Terzopoulos D (1987). Snakes: an active contour models. Int J Comput Vision 1:133-44.

Masmoudi M (2001). The topological asymptotic. In: Glowinski R, Kawarada H, Periaux J, eds. Computational methods for control applications. Gakuto Int Series Math Sci Appl, vol 16. Tokyo, 53-72.

Matheron G, Serra J (1998). The birth of mathematical morphology. Centre de Morphologie Mathmatique, Ecole des Mines de Paris.

Meyer F, Beucher S (1990). Morphological segmentation. J Vis Commun Image Repr 1:21-46.

Mumford D, Shah J (1989). Optimal approximations by piecewise smooth functions and associated variational problems. Comm Pure Appl Math 42:577-685.

Serra J (1982). Image Analysis and Mathematical Morphology, Vol 1. London: Academic Press.

Serra J (1988). Image Analysis and Mathematical Morphology, Vol 2: Theoretical Advances. London: Academic Press.

Soille P (1992). Morphologie mathematique: Du relief la dimensionnalite, Algorithmes et methodes. These de Doctorat, Faculte des Sciences Agronomiques de l' Universite Catholique de Louvrain.

Vincent L, Soille P (1991). Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Trans Pattern Anal 13:583-9.

Weickert J (2001). Efficient image segmentation using partial differential equations and morphology. Pattern Recogn 34:1813-24.

LAMIA JAAFAR BELAID (1) AND WALID MOUROU (2)

(1) Ecole Nationale d'Ingenieurs de Tunis & LAMSIN, Campus Universitaire, BP37, le Belvedere, 1002, Tunis, Tunisia; (2) Institut National de la Statistique de Tunis & LAMSIN, 70 rue Ech-Cham, BP256, 2000, Tunis, Tunisia e-mail: lamia.belaid@esstt.rnu.tn, mourou.walid@lamsin.rnu.tn

Segmentation is one of the most important problem 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 segmentation using 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 restoration the detection of edges makes this operation 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 gradient for edge detection. More precisely, a classical way to restore an image u from its noisy version v defined in a domain S2 E R2 is to solve the following PDE problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (1)

where c is a small positive constant (called the conductivity), [[DELTA].sub.n] denotes the normal derivative and n is the outward unit normal to [DELTA][OMEGA]. Classical nonlinear diffusive approaches are based on the fact that c is a decreasing function of [absolute value of [nabla]u], and takes its values in the interval ]0, [c.sub.0] [, where [c.sub.0] is 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: [c.sub.0] in the smooth part of the image and a small value [epsilon] > 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 problems and propose an extension to an unsupervised 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 c outside edges is large 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 several image processing problems like restoration, 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 giving closed contours.

The watershed transformation is one of the oldest segmentation techniques which was initially due to Beucher and Lantuejoul (Beucher and Lantuejoul, 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, a dam is built: the set of all dams define the so-called watershed. Such representation of the watershed simulates the flooding process. Other processes can be found in the literature, particularly efficient algorithms 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 times in comparison with other segmentation methods. However, using a standard morphological watershed transformation on the original image or on its gradient, 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 techniques combined with a watershed transformation (Jung and Scharcanski, 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 this work 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) and Serra (1982; 1988), some preliminary 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

THE TOPOLOGICAL GRADIENT 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 et al., 2005).

Let [OMEGA] be an open bounded domain of [R.sup.2] and j([OMEGA]) = J([u.sub.[OMEGA]]) be a cost function to be minimized, where [u.sub.[OMEGA]] is the solution to a given PDE problem defined in [OMEGA]. The initial problem reads as follows: for a given function v in [L.sup.2] ([OMEGA]), we have to find u [member of] [H.sup.1]([OMEGA]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (2)

where c is a positive constant.

For a small [rho] [greater than or equal to] 0, let [[OMEGA].sub.[rho]] = [OMEGA]\ [[sigma].sub.[rho]] be the perturbed domain by the insertion of a crack [[sigma].sub.[rho]] = [x.sub.0] + [rho][sigma]](n), where [x.sub.0] [member of] [OMEGA], [sigma](n) is a straight crack, and n a unit vector normal to the crack. The topological sensitivity theory provides an asymptotic expansion of j when [rho] tends to zero. It takes the general form

j([[OMEGA].sub.[rho]]) -j([OMEGA]) = f([rho])G([x.sub.0],u) + o(f([rho])), (3)

where f ([rho]) is an explicit positive function going to zero with p and G([x.sub.0], n) is called the topological gradient at point [x.sub.0].

For a given function v in [L.sup.2]([OMEGA]), we consider the following problem: find [u.sub.[rho]] [member of] [H.sup.1]([[OMEGA].sub.[rho]]) such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (4)

The basic idea is as follows. If we insert a crack in a flat part of the image, nothing happens. But, if we insert a crack along an edge (strong gradient), the potential energy decreases. Then, edge detection is equivalent to look for a subdomain of S2 where the energy is small. So our goal is to minimize the energy norm outside edges

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (5)

by considering vo, the solution to the adjoint problem

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (6)

We obtain in the case of a crack [[sigma].sub.[rho]](n) with a boundary condition [[DELTA].sub.nu] = 0 on [DELTA][[sigma].sub.[rho]](n), the following topological asymptotic expansion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (7)

with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

The topological gradient could be written as

G(x, n) = <M(x)n, n>, (8)

where M(x) is the symmetric matrix defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

For a given x, G(x, n) takes its minimal value when n is the eigenvector associated to the lowest eigenvalue [[lambda].sub.min] of M. This value will be considered as the topological gradient associated to the optimal orientation of the crack [[sigma].sub.[rho]](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 [alpha] < 0. These regions are the edges of the image. The algorithm is as follows.

Topological gradient algorithm

-- Initialization : c = [c.sub.0].

-- Calculation of [u.sub.0] and [v.sub.0] the solutions of the direct (Eq. 4) and adjoint (Eq. 6) problems.

-- Computation of the 2 x 2 matrix M and its lowest eigenvalue [[lambda].sub.min] at each point of the domain [OMEGA].

-- Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (9)

-- Compute [u.sub.1], the solution of Eq. 2 with c = [c.sub.1].

We refer the reader to Jaafar Belaid et al. (2008), for some theoretical and numerical comparisons with conventional restoration methods.

THE WATERSHED TRANSFORMATION

One aim of this work is to show how the use of mathematical morphology operators can be very useful 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 and operators we use.

Let u(x,y) with (x,y) [member of] [R.sup.2], be a scalar function describing an image I. The morphological gradient of I is defined in Beucher et al. (1993) by

[[delta].sub.D]u = (u [??] D) - (u [??] D), (10)

where (u [??] D) and (u [??] D) are respectively the elementary dilation and erosion of u by the structuring element D.

The morphological Laplacian is given by

[[DELTA].sub.D]u = (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 [[DELTA].sub.D]u < 0 are considered as influence zones of suprema, while regions with [[DELTA].sub.D]u > 0 are influence zones of minima. Then [[DELTA].sub.D]u = 0 allows us to interpret edge locations, and will represent an essential property for the construction of morphological filters. 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 of a minimum or a maximum. For a detailed treatment of this topic, the reader is referred to Serra (1988).

The Catchment basin C(M) associated to a minimum M is the set of pixels p of [OMEGA] such that a water drop falling at p flows down along the relief, following a certain descending path, and eventually reaches M. The catchment basins of an image I correspond then to the influence zones of its minima, and the watershed will be defined by the lines that separate adjacent catchment basins.

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 [h.sub.min] and [h.sub.max] the smallest and the largest values taken by u. Let [T.sub.h] = {p [member of] [OMEGA],u(p) [less than or equal to] h} be the threshold set of u at level h. We define a recursion with the gray level h increasing from [h.sub.min] to [h.sub.max], in which the basins associated with the minimum of u are successively expanded. We consider Xh the union of the set of basins computed at level h. A connected component of the threshold set [T.sub.h+1] at level h + 1 can be either a new minimum, or an extension of a basin in [X.sub.h]. Finally, by denoting by minh the union of all regional minima at level h, we obtain the following recursion which defines the watershed by immersion

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (12)

The set of the catchment basins of a gray level image I is equal to the set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. At the end of this process, the watershed of the image I is the complement of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. in [OMEGA].

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

TOPOLOGICAL GRADIENT AND 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 x 256 gray level image and represents some rice grains. Fig. 1b is obtained by adding to the original image a Gaussian noise ([sigma] = 20). The reconstructed image is shown in Fig. 1c: the topological gradient method for the restoration process was applied with [c.sub.0] = 1, [epsilon] = [10.sup.-3], and [alpha] = -70. Finally, we give in Fig. Id, the edges of the reconstructed image. To obtain the restored image, the topological gradient algorithm requires only 3 system resolutions for calculating [u.sub.0], vo and the restored image [u.sub.1] given 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, to speed up the computations, a spectral method based on the discrete cosine transform has been used for the resolution of the direct and adjoint problems. Since the coefficient c is equal to a constant co except on edges, then the discrete cosine transform is a good preconditioner for the conjugate gradient method. The complexity of the restoration algorithm is O(N1ogN) where N is the number of pixels of the image. Some comparisons about the computation times with other classical methods are presented in Jaafar Belaid et al. (2008).

SEGMENTATION USING A CLASSICAL WATERSHED TRANSFORMATION

The goal of this section is to present numerical tests for the segmentation problem using mathematical 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 function u or 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 numerical tests given by Fig. 2b give a segmented image 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 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, as the oversegmentation is due 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 shows the new influence zones obtained which will be used as markers. For better visualization, we present in Fig. 2g the new influence zones superimposed on minima obtained in Fig. 2e. Finally, Fig. 2h shows the contours obtained after the segmentation process using this approach. Some criticisms can be expressed according to this approach: one can remark that the detection of the rice grains is not perfect. In fact, 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 Decenciere et al. (2005).

[FIGURE 1 OMITTED]

[FIGURE 2 OMITTED]

TOPOLOGICAL GRADIENT AND WATERSHED

We propose in this part a new algorithm for the segmentation problem which combines the topological 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 morphological gradients. This is due to the fact that the topological gradient evaluates in a global way whether 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 Euclidean gradient, then it will be easy to conclude that the topological gradient provides the best identification 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 processed image). We recall here that the topological gradient algorithm is solved with a O(N1ogN) complexity and that the watershed algorithm runs in a linear time with respect to the number N of pixels of the image.

Unfortunately, as shown in Fig. 4a, some unwanted 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 improve our segmentation process and to attenuate the number of these unwanted crest lines, we propose to accentuate the smoothing on both sides of an edge. The idea until now was to choose c [approximately equal to] 1, but this choice is not so appropriate for the segmentation problem. We propose then, an improvement of the previous algorithm as follows we consider the following partial differential equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] (13)

with c([epsilon]) = e on the edges and [c.sub.0]/[epsilon] elsewhere, [epsilon] > 0 and co is a given positive constant.

In comparison with the previous section, the topological gradient and the general algorithm remain unchanged since 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 [[lambda].sub.mib] but from numerical point of view, by choosing large values of c, our partial differential equation is nearly equivalent to [DELTA]u = 0 which will provide a really smooth image outside edges leading to a considerable attenuation of segmented regions.

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 images presented in this paper have various difficulties (curves, circles, straight lines, etc.). The first image is a 302 x 280 fruit-basket gray level image and the second one is a 399 x 246 gray level image which represents a road scene. We present in Fig. 5 the two original images and the reconstructed edges by the topological gradient approach, after adding a Gaussian noise ([sigma] = 20) to the original images.

[FIGURE 3 OMITTED]

[FIGURE 4 OMITTED]

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

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 drastically the 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 take c = 1, otherwise, one should consider larger values of c which 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 regions such that the main edges of the two images are conserved.

COMPARISON WITH AN ACTIVE CONTOURS MODEL

Finally, due to a large number of approaches used for the segmentation problem, it clearly appears that it is important to compare our experimental results with methods already proposed in the literature. 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, extensively used in many applications over the last decade. The basic idea in active contour models is to evolve a curve subject to constraints from a given image, in order to detect different objects in that image. 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 boundary of the object. This was the first idea of classical snakes and active contour models proposed by 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 evolution equation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

with boundary and initial conditions given by au/an = 0 on (0,[infinty]) x [DELTA][OMEGA] and [PHI](O,x,y) = [[PHI].sub.0](x,y) in [OMEGA], [alpha] [greater than or equal to] 0 is a positive given coefficient, g (I VII) is an edge detector function defined in our numerical tests by g(s) = 1/(1 + [s.sup.2]), and oo represents the initial level set function. We refer the reader to Aubert and Kornprobst (2001) for more details about geodesic active contours 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 time of 78 seconds. We present in Fig. 7 some solutions 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 others objects.

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 requires 38 CPU seconds and the drawback seen before is overcome. We also tested this method on a real 151 x 151 gray level image. Fig. 8 shows the ability of the model to capture the main object of the image, which can be important for object tracking applications 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 with active contours model to capture an object, but on the other hand, these different regions extracted can be particularly helpful for color processing exploration for example. We can conclude that the results obtained by the two methods are just different and depend of the objects we want to detect and the kind of applications we want to explore.

[FIGURE 7 OMITTED]

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 cost is interesting.

-- 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 oversegmentation problem, which usually appears with the watershed technique, can be attenuated, and the segmentation results can be performed using the topological gradient approach.

-- 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 gradient detected. This methodology has many 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 three dimensional segmentation.

[FIGURE 8 OMITTED]

ACKNOWLEDGMENTS

We are grateful to the unknown reviewers for their valuable comments. We also thank Professor Jean Serra for his helpful suggestions.

(Accepted March 27, 2009)

REFERENCES

Amstutz S, Horchani 1, Masmoudi M (2005). Crack detection by the topological gradient method. Control Cybern 34:119-38.

Aubert G, Kornprobst P (2001). Mathematical problems in image processing. New York: Springer-Verlag.

Auroux D, Masmoudi M (2006). A one-shot inpainting algorithm based on the topological asymptotic analysis. ComputAppl Math 25:1-17.

Auroux D, Jaafar Belaid L, Masmoudi M (2007). A topological asymptotic analysis for the regularized gray-level image classification problem. Math Model Num Anal 41:607-25.

Auroux D (2008). From restoration by topological gradient to medical image segmentation via an asymptotic expansion. Math Comput Model 49:2191-205.

Beucher S (1990). Segmentation d'image et Morphologie mathematique. These de Doctoral, Ecole Nationale Superieure des Mines de Paris.

Beucher S, Rivest J.F, Soille P (1993). Morphological gradients. J Electron Imaging 2:326-36.

Beucher S, Lantuejoul C (1979). Use of watersheds in contour detection. In: Proc Int Worksh Image Process, Real-Time Edge Motion Detection/Estimation, Rennes, France. Sept 17-21, 1979.

Caselles V, Kimmel R, Sapiro G (1997). Geodesic active contours. Int J Comput Vision, 22:61-79.

Decenciere 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:3138.

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. IEEE Trans Image Proc 5:913-21.

Jung C.R, Scharcanski J (2005). Robust watershed segmentation using wavelets. Image Vision Comput 23:661-69.

Kass M, Witkin A, Terzopoulos D (1987). Snakes: an active contour models. Int J Comput Vision 1:133-44.

Masmoudi M (2001). The topological asymptotic. In: Glowinski R, Kawarada H, Periaux J, eds. Computational methods for control applications. Gakuto Int Series Math Sci Appl, vol 16. Tokyo, 53-72.

Matheron G, Serra J (1998). The birth of mathematical morphology. Centre de Morphologie Mathmatique, Ecole des Mines de Paris.

Meyer F, Beucher S (1990). Morphological segmentation. J Vis Commun Image Repr 1:21-46.

Mumford D, Shah J (1989). Optimal approximations by piecewise smooth functions and associated variational problems. Comm Pure Appl Math 42:577-685.

Serra J (1982). Image Analysis and Mathematical Morphology, Vol 1. London: Academic Press.

Serra J (1988). Image Analysis and Mathematical Morphology, Vol 2: Theoretical Advances. London: Academic Press.

Soille P (1992). Morphologie mathematique: Du relief la dimensionnalite, Algorithmes et methodes. These de Doctorat, Faculte des Sciences Agronomiques de l' Universite Catholique de Louvrain.

Vincent L, Soille P (1991). Watersheds in digital spaces: an efficient algorithm based on immersion simulations. IEEE Trans Pattern Anal 13:583-9.

Weickert J (2001). Efficient image segmentation using partial differential equations and morphology. Pattern Recogn 34:1813-24.

LAMIA JAAFAR BELAID (1) AND WALID MOUROU (2)

(1) Ecole Nationale d'Ingenieurs de Tunis & LAMSIN, Campus Universitaire, BP37, le Belvedere, 1002, Tunis, Tunisia; (2) Institut National de la Statistique de Tunis & LAMSIN, 70 rue Ech-Cham, BP256, 2000, Tunis, Tunisia e-mail: lamia.belaid@esstt.rnu.tn, mourou.walid@lamsin.rnu.tn

Printer friendly Cite/link Email Feedback | |

Author: | Belaid, Lamia Jaafar; Mourou, Walid |
---|---|

Publication: | Image Analysis and Stereology |

Article Type: | Technical report |

Geographic Code: | 1USA |

Date: | Jun 1, 2009 |

Words: | 5476 |

Previous Article: | Miles formulae for Boolean models observed on lattices. |

Next Article: | Microct and preparation of [beta]-TCP granular material by the polyurethane foam method. |

Topics: |