Abstract
In this paper we propose a new scheme for image segmentation composed of two stages:
in the first phase, we smooth the original image by some filters associated with noise
types, such as Gaussian filters for Gaussian white noise and so on. Indeed, we propose
a novel diffusion equations scheme derived from a nonconvex functional for Gaussian
noise removal in this paper. In the second phase, we apply a variational method for
segmentation in the smoothed image domain obtained in the first phase, where we directly
calculate the minimizer on the discrete gray level sets. In contrast to other image
segmentation methods, there is no need for us to reinitialize parameters, which deduces
the complexity of our algorithm to
Keywords:
twophase segmentation; discrete gray level set; forwardbackward diffusion; nonconvex functional; ChanVese minimal variance1 Introduction
Images are the proper 2D projections of the 3D world containing various objects. To reconstruct the 3D world perfectly, at least approximately, the first crucial step is to identify the regions in images that correspond to individual objects. This is the wellknown problem as image segmentation which has broad applications in a variety of important fields such as computer vision and medical image processing.
Image segmentation has been studied extensively in the past decades. A wellestablished class of methods consists of active contour models, which have been widely used in image segmentation with promising results. In general, these models apply variational methods where they minimize some energy functionals depending on the features of the image. Classical ways to solve such problems are to solve the corresponding EulerLagrange equations. The existing active contour models can be roughly categorized into two classes: regionbased models [19] and edgesbased models [1014]. A literature review of major active contour models can be found in [1517].
Based on image gradient information, edgesbased models drive one or more initial curve(s) to the boundaries of objects in the image. However, edgesbased models are usually sensitive to noise and weak edges information [2]. Instead of utilizing image gradient information, regionbased models typically aim to identify each region of interest by using a certain region descriptor, such as intensity, color, texture, to guide the motion of the contour [17]. Therefore regionbased models tend to rely on global information to steer contour evolution, which increase the chance to have better performance in the presence of image noise and weak object boundaries. In addition, regionbased models are less sensitive to the initial contour locations than edgebased models. For instance, Chan and Vese [1] developed an active contour without edge model to deal with image segmentation by using the levelset framework introduced by Osher and Sethian [15], which is similar to the segmentation method independently proposed by Tsai et al.[3]. The active contour methods based on levelset framework have several following advantages. Firstly, they can deal with topological changes such as breaking and merging. Secondly, intrinsic geometric elements such as the normal vector and the curvature can be easily interpreted with respect to the levelset function. Finally, this levelset framework can be extended and applied in any dimension.
However, these active contour methods based on levelset framework have some drawbacks. Firstly, most of these methods have initialization problems: different initial curves produce different segmentations because of the nonconvexity of ChanVese models [4]. Secondly, these methods are usually implemented by solving corresponding evolution equations that suffer from severe numerical stability constrains which render them inefficient. For instance, ChanVese models become severely inefficient due to the signed distance reinitialization procedure for stability reason. Recently, some researchers developed fast algorithms [1823] to the ChanVese image segmentation model to avoid these drawbacks above. In [1821], the authors developed fast algorithms based on calculating the variational energy of the ChanVese model directly without the length term. In [18], the authors proposed a fast method for image segmentation without solving the EulerLagrange equation of the underlying variational problem proposed by Chan and Vese, therefore they calculated the energy directly and checked if the energy is decreased when they change a point inside the level set to outside or vice versa.
In this paper we develop a twophase image segmentation model. In the first phase,
we propose a new nonconvex functional to get the smoothing image of the original
image for noise removal, resulting in the sharpened edge. We also prove the nonexistence
of the minimizer of the nonconvex functional above. Noted that this purpose may be
accomplished by other smoothing filters, for example, the Gaussian lowpass filter
in the general case. In the second phase, a new functional based on gray level sets
is firstly proposed, and then the associated discrete model based on the discrete
gray level sets is discussed, which educes the new segmentation algorithm to obtain
the segmentation results. Each stage is independent and thus the method at each stage
is flexible. Although the new methods share some similarities to those in [1820], it is a new framework that we calculate the energy directly on discrete gray level
sets. Furthermore, we discuss other complicated issues which are not considered in
[18], such as sensitivity to noise. Last but not least, our segmentation method can also
deal with largescale images because of the following reasons. Firstly, we do not
need the initial conditions and the procedure of reinitiation as we directly calculate
the minimizer on the discrete gray level sets rather than solving the EulerLagrange
equation of the underlying variational problem. Secondly, in the second stage of our
algorithm, the main computation process, which is adding operators and logical operators
which cost little CPU time, deduces the complexity of the algorithm to
This paper is organized as follows. In Section 2, we propose twophase segmentation model. Experimental results are given in Section 3, and the final section is our conclusion.
2 Twophase segmentation model
In this section, we show a twostage scheme for implementation of the piecewise constant segmentation model. More precisely, the smoother version of the original image is first obtained by some smooth filter, and then, minimizing the ChanVese minimal variance criterion on the gray level sets, the image is divided into two subregions. Based on the idea above, we deal with the problem in two phases, respectively. Firstly, we propose a new denoising functional to obtain smoothing images. Secondly, we consider the continuous model of the new twophase segmentation model based on gray level sets to propose the associated discrete model and then obtain a new algorithm.
2.1 The nonconvex functional for Gaussian noise removal
In our twophase algorithm, the second phase is fixed and can be easily performed and the new method depends in a large part on the smooth version u of the original image. So it is better to use different edgepreserving denoising models for various types of noise.
According to conclusions in [24], the nonconvex functional may provide better or sharper edges than the convex functional does. In the smoothing phase of our method, the following edgepreserving denoising model is considered
where
Theorem 2.1If
Proof We only prove the onedimensional case
By density, we may always find a sequence of step functions
In fact, we can find a partition
Note that
and therefore,
Since
and then taking the limit on both sides yields
Moreover,
Thus
and finally,
i.e.,
Now, if there exists a minimizer
The first equality is possible only if
Remark 2.1 As we all know, if the region Ω is bounded,
then
Note that
However, we cannot obtain any information about the minimizer of
From the EulerLagrange equation for (2.1), we can obtain the following diffusion equation:
Remark 2.2 (Segmentation for various types of noisy image)
There are lots of methods to obtain the smooth image in the first phase of the new method.
• If the type of noise is ‘salt and pepper’, for example, the AMF (adaptive median filter) can be selected;
• If the noise is ‘addition Gaussian noise’, for example, the Gaussian lowerpass filter, the new nonconvex functional (2.1), the TV method (total variation model) [26], the PM method (PeronaMalik model) [27], and other anisotropic diffusion [28] methods can be used to smooth the original image;
• If the noise is ‘multiplication noise’, for example, the SO method (ShiOsher Model), which is an effective multiplicative noise removal model [29], can be used to denoise the original image.
2.2 ChanVese minimal variance criterion based on gray level sets
First let us review the following ChanVese minimal variance criterion
Assume that the smooth image u is the solution from diffusion equations (2.2)(2.4). Let
Figure 1. The level lines at different gray levels.(a) The noise image with Gaussian white noise of mean 0 and variance 0.2. (b) The smooth image by Gaussian lowpass filter with
Hence, the levelset function can be replaced by the image gray function u in the ChanVese minimal variance criterion [2], and the new model is as follows:
where
and the Heaviside function H
Minimizing the function above, the best threshold is obtained, and then the image
is segmented into two subregions
Notice that
for
and for
Theorem 2.2Assume
Proof If
Hence
which implies that the minimizer is the minimum point. By the Fermat theorem, we
obtain that there exists
For any images we can always obtain the function
Figure 2. Segmentation results by Algorithm 2.1.(a) The noise image. (b) The smooth image by Gaussian lowpass filter with
Based on the new model (2.6), the twophase algorithm is sketched below.
Algorithm 2.1
1. (Smoothing) By (2.2)(2.4) obtain some appropriate smooth versionuof the noise imagef.
2. (Minimal variance) Calculate the new model (2.6) for each
2.3 Discrete version of model (2.6)
Let
with
where
It is noticed that since the selection of
Definition 2.1 (Discrete gray level set)
The Kdiscrete gray level set
where
For any
with
Theorem 2.3
Proof It is clear that
From Theorem 2.2, there exist two subdomains
Without loss of generality, assume
Having compared the energy
Since
So we get
Since
From (2.8) and (2.9), we can easily see that
Hence we have the following.
Theorem 2.4
where
Now, if the energy functional E reaches a maximum, the best segmentation results are obtained, i.e., the subregion
Algorithm 2.2The method of maximizing the following functionalE
1. Sweep the imageuonce, record the number of all pixels at every gray level of the imageuwhich range from
2. Calculate the energy
3. The imageuis divided into two subregions, i.e.,
Based on Algorithm 2.2, the following is the new twophase scheme for image segmentation.
Algorithm 2.3
• (Smoothing) For the input noise imagef, use the Gaussian smooth filter or diffusion equations (2.2)(2.4) to obtain the smooth imageu (if the input image is noiseless, this step is optional).
• (Minimal variance) Use Algorithm 2.2 to obtain the segmentation results for the smooth imageu.
3 Simulations
In this section, numerical examples on some synthetic and real world images are presented to illustrate the efficiency and effectiveness of our new twophase scheme. The simulations are performed in Matlab R2007b on a 2.8 GHz Pentium 4 processor. For comparison purpose, the ChanVese method (CVM) [2] is also tested. We utilize a locally onedimensional (LOD) scheme adopted for CVM, which is an unconditional scheme [8].
3.1 Configuration of smoothing filter
In the new algorithm, the first stage is smoothing the original image. The lowpass filtering is generally made by convolution with Gaussian of an increasing variance. Koenderink [30] noticed that the convolution of signal with Gaussian at each scale was equivalent to the solution of the heat equation with the signal as initial datum f, i.e.,
FFT (fast Fourier transform algorithm), the classical fivepoint explicit numerical schemes and the additive operator splitting (AOS) schemes can be used for the heat equation. In our experiment, we will use the Gaussian lowpass filter as one smoothing method in the first phase. For simplicity, we refer to the method as GLFGLS (Gaussian lowpass filtergray level set).
On the other hand, using the scheme in [31], problems (2.2)(2.4) can be discretized as
where
and
where
where
3.2 Segmentation performance
In Figure 3, we illustrate the performance of CVM, GLFGLS and DEGLS on the synthetic noise
Test01 image (size:
Figure 3. Segmentations for the noiseTest01image (size:
Table 1. Comparison of CPU time in seconds and iterate step
In Figures 4 and 5, we illustrate the results of GLFGLS and DEGLS about the real brain and ultrasound image. Few differences between the segmented images are observed, but our method works much faster than CVM (Table 1).
Figure 4. Segmentations for the noiseultrasoundimage (size:
Figure 5. Segmentations for the noisebrainimage (size:
3.3 Computational complexity
We end this section by considering the complexity of our algorithm. Our algorithm
requires two phases: smoothing the original image and segmentation. Smoothing the
original image is done by the AOS scheme, which is very efficient, and the complexity
of this stage is
4 Summary
In this paper, we have proposed and implemented a novel image segmentation algorithm based on the ChanVese active contour model. The discrete gray levelset method is employed in our numerical implementation. This algorithm works in two steps, we first smooth the noisy image by using the heat equation filter method, and then we utilize the new discrete gray levelset method to segment the region of the original image. The proposed new segmentation algorithm does not require the initialization of the levelset functions, which is a difficult problem in the ChanVese segmentation algorithm. Each step of the proposed new segmentation algorithm is simple and easily implemented. In the first step, there are a lot of algorithms to get the smoothing version of the original image, and in the second step, we only sweep the image once and calculate (2.16) at every gray level (in fact, only 256 gray level sets) and find the optimal gray level. In Table 1, we show the CPU time of the ChanVese method and our proposed method. Obviously, our method is much more efficient than the ChanVese method.
Competing interests
The authors declare that they have no competing interests.
Authors’ contributions
XJ and BW carried out the proof of the main part of this article, DZ corrected the manuscript, and participated in its design and coordination. All authors have read and approved the final manuscript.
Acknowledgements
This work is partially supported by the National Science Foundation of China (11271100, 11301113, 71303067), China Postdoctoral Science Foundation funded project (Grant No. 2012M510933, Grant No. 2013M541400).
References

Mumford, D, Shah, J: Optimal approximation by piecewise smooth functions and associated variational problems. Commun. Pure Appl. Math.. 42, 577–685 (1989). Publisher Full Text

Chan, TF, Vese, LA: Active contours without edges. IEEE Trans. Image Process.. 10(2), 266–277 (2001). PubMed Abstract  Publisher Full Text

Tsai, A, Yezzi, A, Willsky, AS: Curve evolution implementation of the MumfordShah functional for image segmentation, denoising, interpolation, and magnification. IEEE Trans. Image Process.. 10(8), 1169–1186 (2001). PubMed Abstract  Publisher Full Text

Gao, S, Bui, T: Image segmentation and selective smoothing by using MumfordShah model. IEEE Trans. Image Process.. 14(10), 1537–1549 (2005). PubMed Abstract

Vese, L, Chan, TF: A multiphase level set framework for image segmentation using the Mumford and Shah model. Int. J. Comput. Vis.. 50(3), 271–293 (2002). Publisher Full Text

Chan, TF, Yezrielev Sandberg, B, Vese, LA: Active contours without edges for vectorvalued images. J. Vis. Commun. Image Represent.. 2(11), 130–141 (2000)

Paragios, N, Deriche, R: Geodesic active regions and level set methods for supervised texture segmentation. Int. J. Comput. Vis.. 46(3), 223–247 (2002). Publisher Full Text

Kimmel, R: Fast edge integration. Level Set Methods and Their Applications in Computer Vision, Springer, New York (2003)

Li, C, Huang, R, Ding, Z, Gatenby, C, Metaxas, D, Gore, J: A variational level set approach to segmentation and bias correction of medical images with intensity inhomogeneity. Proceedings of Medical Image Computing and Computer Aided Intervention (MICCAI). Part II, pp. 1083–1091. Springer, Berlin (2008)

Kass, M, Witkin, A, Terzopoulos, D: Snakes: active contour models. Int. J. Comput. Vis.. 1(4), 321–331 (1987)

Caselles, V, Catte, F, Coll, T, Dibos, F: A geometric model for active contours. Numer. Math.. 66, 1–31 (1993). Publisher Full Text

Malladi, R, Sethian, JA, Vemuri, BC: Shape modeling with front propagation: a level set approach. IEEE Trans. Pattern Anal. Mach. Intell.. 17(2), 158–175 (1995). Publisher Full Text

Xu, C, Prince, J: Generalized gradient vector flow external forces for active contours. Signal Process.. 71(2), 131–139 (1998). Publisher Full Text

Li, C, Xu, C, Gui, C, Fox, MD: Level set evolution without reinitialization: a new variational formulation. Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 430–436 (2005)

Osher, S, Paragios, N: Geometric Level Set Methods in Imaging, Vision, and Graphics, Springer, New York (2003)

Jain, AK, Zhong, Y, DubuissonJolly, M: Deformable template models: a review. Signal Process.. 71(2), 109–129 (1998). Publisher Full Text

Cremers, D, Rousson, M, Deriche, R: A review of statistical approaches to level set segmentation: integrating color, texture, motion and shape. Int. J. Comput. Vis.. 72(2), 195–215 (2007). Publisher Full Text

Shi, Y, Karl, W: A fast level set method without solving pdes. (2005)

Song, B, Chan, T: A fast algorithm for level set based optimization. Tech. Rep. CAM0268, UCLA Dept. Math. (2002)

Pan, Y, Birdwell, JD, Djouadi, SM: Efficient implementation of the ChanVese models without solving PDEs. Victoria, BC, Canada, Oct. 0306. (2006)

He, L, Osher, SJ: Solving the ChanVese model by a multiphase level set algorithm based on the topological derivative. Proceedings of the 1st International Conference on ScaleSpace Variational Methods in Computer Vision (2007)

Pan, Y, Birdwell, DJ, Seddik, DM: An efficient bottomup image segmentation method based on region growing, region competition and the Mumford Shah functional. Victoria, BC, Canada, Oct. 0306. (2006)

Wang, X, Huang, D, Xu, H: An efficient local ChanVese model for image segmentation. Pattern Recognit.. 43, 603–618 (2010). Publisher Full Text

Aubert, G, Kornprobst, P: Mathematical Problems in Image Processing: PDE’s and the Calculus of Variations, Springer, Berlin (2002).

Chipot, M, March, R, Rosati, M, Vergara Caffarelli, G: Analysis of a nonconvex problem related to signal selective smoothing. Math. Models Methods Appl. Sci.. 7(3), 313–328 (1997). Publisher Full Text

Rudin, L, Osher, S, Fatemi, E: Nonlinear total variation based noise removal algorithms. Physica D. 60, 259–268 (1992). Publisher Full Text

Perona, P, Malik, J: Scalespace and edge detection using anisotropic diffusion. IEEE Trans. Pattern Anal. Mach. Intell.. 12(7), 629–639 (1990). Publisher Full Text

Weickert, J: Applications of nonlinear diffusion in image processing and computer vision. Acta Math. Univ. Comen.. 70(1), 33–50 (2000)

Shi, J, Osher, S: A nonlinear inverse scale space method for a convex multiplicative noise model. SIAM J. Imaging Sci.. 1(3), 294–321 (2008). Publisher Full Text

Koenderink, JJ: The structure of image. Biol. Cybern.. 50, 363–370 (1984). PubMed Abstract  Publisher Full Text

Weickert, J, Romeny, B, Viergever, M: Efficient and reliable scheme for nonlinear diffusion filtering. IEEE Trans. Image Process.. 7(3), 398–410 (1998). PubMed Abstract  Publisher Full Text