SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Research

Fast two-phase image segmentation based on diffusion equations and gray level sets

Boying Wu, Xiaoping Ji and Dazhi Zhang*

Author Affiliations

Department of Mathematics, Harbin Institute of Technology, Harbin, 150001, China

For all author emails, please log on.

Boundary Value Problems 2014, 2014:11  doi:10.1186/1687-2770-2014-11

The electronic version of this article is the complete one and can be found online at: http://www.boundaryvalueproblems.com/content/2014/1/11


Received:22 August 2013
Accepted:5 December 2013
Published:9 January 2014

© 2014 Wu et al.; licensee Springer.

This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

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 non-convex 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 re-initialize parameters, which deduces the complexity of our algorithm to <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1">View MathML</a> (N is the number of pixels) and provides significant efficiency improvement when dealing with large-scale images. The obtained numerical results of segmentation on synthetic images and real world images both clearly outperform the main alternative methods especially for images contaminated by noise.

Keywords:
two-phase segmentation; discrete gray level set; forward-backward diffusion; non-convex functional; Chan-Vese minimal variance

1 Introduction

Images are the proper 2-D projections of the 3-D world containing various objects. To reconstruct the 3-D world perfectly, at least approximately, the first crucial step is to identify the regions in images that correspond to individual objects. This is the well-known 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 well-established 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 Euler-Lagrange equations. The existing active contour models can be roughly categorized into two classes: region-based models [1-9] and edges-based models [10-14]. A literature review of major active contour models can be found in [15-17].

Based on image gradient information, edges-based models drive one or more initial curve(s) to the boundaries of objects in the image. However, edges-based models are usually sensitive to noise and weak edges information [2]. Instead of utilizing image gradient information, region-based 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 region-based 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, region-based models are less sensitive to the initial contour locations than edge-based models. For instance, Chan and Vese [1] developed an active contour without edge model to deal with image segmentation by using the level-set 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 level-set 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 level-set function. Finally, this level-set framework can be extended and applied in any dimension.

However, these active contour methods based on level-set framework have some drawbacks. Firstly, most of these methods have initialization problems: different initial curves produce different segmentations because of the non-convexity of Chan-Vese 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, Chan-Vese models become severely inefficient due to the signed distance re-initialization procedure for stability reason. Recently, some researchers developed fast algorithms [18-23] to the Chan-Vese image segmentation model to avoid these drawbacks above. In [18-21], the authors developed fast algorithms based on calculating the variational energy of the Chan-Vese model directly without the length term. In [18], the authors proposed a fast method for image segmentation without solving the Euler-Lagrange 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 two-phase image segmentation model. In the first phase, we propose a new non-convex 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 non-convex functional above. Noted that this purpose may be accomplished by other smoothing filters, for example, the Gaussian low-pass 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 [18-20], 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 large-scale images because of the following reasons. Firstly, we do not need the initial conditions and the procedure of re-initiation as we directly calculate the minimizer on the discrete gray level sets rather than solving the Euler-Lagrange 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 <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1">View MathML</a>.

This paper is organized as follows. In Section 2, we propose two-phase segmentation model. Experimental results are given in Section 3, and the final section is our conclusion.

2 Two-phase segmentation model

In this section, we show a two-stage 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 Chan-Vese 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 two-phase segmentation model based on gray level sets to propose the associated discrete model and then obtain a new algorithm.

2.1 The non-convex functional for Gaussian noise removal

In our two-phase 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 edge-preserving denoising models for various types of noise.

According to conclusions in [24], the non-convex functional may provide better or sharper edges than the convex functional does. In the smoothing phase of our method, the following edge-preserving denoising model is considered

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M3">View MathML</a>

(2.1)

where <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M4">View MathML</a>. Note that for <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M5','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M5">View MathML</a>, the model is non-convex, so the edges will be protected and even enhanced. However, the model above is an ill-posed problem. According to the proof given by Chipot et al.[25], we have the following theorem.

Theorem 2.1If<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M6','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M6">View MathML</a>is not a constant and<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M7','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M7">View MathML</a>, the function<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8">View MathML</a>has no minimizer in<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M9">View MathML</a>and<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M10','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M10">View MathML</a>.

Proof We only prove the one-dimensional case <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M11','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M11">View MathML</a>, and the same proof goes for <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M12','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M12">View MathML</a>.

By density, we may always find a sequence of step functions <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M13">View MathML</a> such that

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M14','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M14">View MathML</a>

In fact, we can find a partition <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M15','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M15">View MathML</a> such that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M13','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M13">View MathML</a> is the constant <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M17','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M17">View MathML</a> on each interval <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M18','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M18">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M19','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M19">View MathML</a> with <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M20','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M20">View MathML</a>. Let us set <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M21','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M21">View MathML</a>. Next, we define a sequence of continuous functions <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M22','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M22">View MathML</a> by

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M23','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M23">View MathML</a>

Note that

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M24','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M24">View MathML</a>

and therefore,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M25','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M25">View MathML</a>

Since

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M26','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M26">View MathML</a>

and then taking the limit on both sides yields

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M27','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M27">View MathML</a>

Moreover,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M28','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M28">View MathML</a>

Thus

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M29','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M29">View MathML</a>

and finally,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M30','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M30">View MathML</a>

i.e.,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M31','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M31">View MathML</a>

Now, if there exists a minimizer <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M32','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M32">View MathML</a>, then necessarily <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M33','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M33">View MathML</a>, which implies

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M34','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M34">View MathML</a>

The first equality is possible only if <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M35','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M35">View MathML</a>, and in this case the second equality implies <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M36','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M36">View MathML</a>, which is possible only if f is a constant. Therefore, excluding this trivial case, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8">View MathML</a> has no minimizer in <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M9','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M9">View MathML</a>. □

Remark 2.1 As we all know, if the region Ω is bounded,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M39','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M39">View MathML</a>

then

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M40','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M40">View MathML</a>

Note that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M41','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M41">View MathML</a>, and therefore

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M42','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M42">View MathML</a>

However, we cannot obtain any information about the minimizer of <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M8">View MathML</a> in <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M44','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M44">View MathML</a>.

From the Euler-Lagrange equation for (2.1), we can obtain the following diffusion equation:

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M45','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M45">View MathML</a>

(2.2)

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M46','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M46">View MathML</a>

(2.3)

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M47','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M47">View MathML</a>

(2.4)

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 lower-pass filter, the new non-convex functional (2.1), the TV method (total variation model) [26], the PM method (Perona-Malik 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 (Shi-Osher Model), which is an effective multiplicative noise removal model [29], can be used to denoise the original image.

2.2 Chan-Vese minimal variance criterion based on gray level sets

First let us review the following Chan-Vese minimal variance criterion

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M48','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M48">View MathML</a>

(2.5)

Assume that the smooth image u is the solution from diffusion equations (2.2)-(2.4). Let <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M49','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M49">View MathML</a> be the K-level set of u. It is clear that for the noise image, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50">View MathML</a> is disorderly and irregular; while for the smooth image, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50">View MathML</a> is smooth and regular. These basic facts are illustrated in Figure 1, where some <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M50">View MathML</a> are very close to the real edges of the original image.

thumbnailFigure 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 low-pass filter with <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M53">View MathML</a>. (c)-(g) The level lines of the noise image at the gray level 60, 80, 120, 180, and 200. (h)-(l) The level lines of the smooth image at the gray level 60, 80, 120, 180, and 200.

Hence, the level-set function can be replaced by the image gray function u in the Chan-Vese minimal variance criterion [2], and the new model is as follows:

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M54','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M54">View MathML</a>

(2.6)

where

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M55','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M55">View MathML</a>

(2.7)

and the Heaviside function H

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M56','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M56">View MathML</a>

Minimizing the function above, the best threshold is obtained, and then the image is segmented into two subregions <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M57','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M57">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M58','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M58">View MathML</a>.

Notice that

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M59','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M59">View MathML</a>

(2.8)

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M60','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M60">View MathML</a>

(2.9)

for <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M61','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M61">View MathML</a>,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M62','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M62">View MathML</a>

and for <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M63','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M63">View MathML</a>,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M64','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M64">View MathML</a>

Theorem 2.2Assume<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M65">View MathML</a>, and then there exists the minimizer<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M66','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M66">View MathML</a>of<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M67">View MathML</a>. Furthermore, iffis not a constant function, then the minimizer is the minimum point with<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M68">View MathML</a>.

Proof If <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M65','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M65">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M70','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M70">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M71','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M71">View MathML</a>, there exists the minimizer <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M72','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M72">View MathML</a> of <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M67','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M67">View MathML</a>. Noted that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M74','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M74">View MathML</a> get the minimal at <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M75','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M75">View MathML</a>, and then

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M76','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M76">View MathML</a>

Hence

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M77','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M77">View MathML</a>

which implies that the minimizer is the minimum point. By the Fermat theorem, we obtain that there exists <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M78','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M78">View MathML</a> such that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M68','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M68">View MathML</a>. □

For any images we can always obtain the function <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80">View MathML</a>. Figure 2(d) shows the function <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80">View MathML</a> for the image in Figure 2(a). From the figure, we can see that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80">View MathML</a> has the global minimizer and has several local minimizers.

thumbnailFigure 2. Segmentation results by Algorithm 2.1.(a) The noise image. (b) The smooth image by Gaussian low-pass filter with <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M83','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M83">View MathML</a>. (c) The segmentation result (<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M84','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M84">View MathML</a>). (d) The function <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M80">View MathML</a>.

Based on the new model (2.6), the two-phase 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<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M86','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M86">View MathML</a>, and then obtain the minimizerwith<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M88','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M88">View MathML</a>. The segmentation results are<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M89','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M89">View MathML</a>and<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M90','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M90">View MathML</a>.

2.3 Discrete version of model (2.6)

Let <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M91">View MathML</a>, for <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M92','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M92">View MathML</a>, be the gray level of a true M-by-N image u at pixel location <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93">View MathML</a>, and let <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M94','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M94">View MathML</a> be the range of the smooth image u, i.e., <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M95','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M95">View MathML</a>. Let <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M96','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M96">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M97','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M97">View MathML</a>, and then the image u is divided into two regions. Instead <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M98','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M98">View MathML</a> by <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99">View MathML</a>, and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M100','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M100">View MathML</a> by <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101">View MathML</a>, respectively. Then minimizing the energy (2.5) is changed into minimize

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M102','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M102">View MathML</a>

(2.10)

with

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M103','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M103">View MathML</a>

(2.11)

where <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M104','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M104">View MathML</a> is the number of pixels in <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99">View MathML</a>, and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M106','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M106">View MathML</a> is the number of pixels in <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101">View MathML</a>. If the energy F reaches a minimum, the best segmentation results are obtained, i.e., the subregion <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99">View MathML</a> and subregion <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101">View MathML</a>.

It is noticed that since the selection of <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M99">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M101">View MathML</a> is arbitrary, there are lots of pairs <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M112','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M112">View MathML</a>, so minimizing the energy F is difficult. Now, we introduce the following definition, which contains a limited number of elements.

Definition 2.1 (Discrete gray level set)

The K-discrete gray level set <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M113','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M113">View MathML</a>, which is the set of pixel location <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93">View MathML</a>, is defined as follows

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M115','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M115">View MathML</a>

where <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M91','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M91">View MathML</a> is the gray level of the image u at pixel location <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M93">View MathML</a>.

For any <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M118','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M118">View MathML</a>, the image u is divided into two subregions, i.e., <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M119','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M119">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M120','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M120">View MathML</a>. Then <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M121','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M121">View MathML</a>. Let <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M122','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M122">View MathML</a>, and then the element number <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M123','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M123">View MathML</a> of the set is <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M125','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M125">View MathML</a> which is less than 256 in general. Then minimizing the energy (2.6) is changed into minimize

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M126','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M126">View MathML</a>

(2.12)

with

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M127','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M127">View MathML</a>

(2.13)

Theorem 2.3

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M128','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M128">View MathML</a>

(2.14)

Proof It is clear that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M129','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M129">View MathML</a>. We only need to prove <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M130','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M130">View MathML</a>.

From Theorem 2.2, there exist two subdomains <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M131','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M131">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M132','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M132">View MathML</a> such that

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M133','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M133">View MathML</a>

Without loss of generality, assume <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M134','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M134">View MathML</a> and there exist <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M135','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M135">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M136','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M136">View MathML</a> such that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M137','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M137">View MathML</a>. Denote <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M138','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M138">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M139','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M139">View MathML</a>. Note that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M140','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M140">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M141','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M141">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M142','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M142">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M143','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M143">View MathML</a>.

Having compared the energy <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M144','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M144">View MathML</a> and <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M145','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M145">View MathML</a>, we get

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M146','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M146">View MathML</a>

Since <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M147','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M147">View MathML</a>, we have

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M148','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M148">View MathML</a>

So we get

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M149','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M149">View MathML</a>

Since <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M150','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M150">View MathML</a>, it is a contradiction. Therefore, for any <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M151','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M151">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M152','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M152">View MathML</a>, we have <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M153','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M153">View MathML</a>. Hence there exists <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M154','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M154">View MathML</a> such that <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M155','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M155">View MathML</a>, i.e., <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M156','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M156">View MathML</a>. We complete the proof of the theorem. □

From (2.8) and (2.9), we can easily see that

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M157','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M157">View MathML</a>

(2.15)

Hence we have the following.

Theorem 2.4<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M158','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M158">View MathML</a>is equivalent to

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M159','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M159">View MathML</a>

(2.16)

where<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M160','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M160">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M161','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M161">View MathML</a>and<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M162','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M162">View MathML</a>is defined as (2.11).

Now, if the energy functional E reaches a maximum, the best segmentation results are obtained, i.e., the subregion <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M163','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M163">View MathML</a> and subregion <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M164','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M164">View MathML</a>. Since <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M165','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M165">View MathML</a>, the energy functional E has <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M166','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M166">View MathML</a> cases, and then the maximum of E is easily found. The algorithm in the second phase is sketched below.

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<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M167','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M167">View MathML</a>to<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M168','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M168">View MathML</a>.

2. Calculate the energy<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M169','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M169">View MathML</a>by (2.16) for<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M170','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M170">View MathML</a>, and find the maximizer.

3. The imageuis divided into two subregions, i.e., <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M172','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M172">View MathML</a>and<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M173','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M173">View MathML</a>.

Based on Algorithm 2.2, the following is the new two-phase 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 two-phase scheme. The simulations are performed in Matlab R2007b on a 2.8 GHz Pentium 4 processor. For comparison purpose, the Chan-Vese method (CVM) [2] is also tested. We utilize a locally one-dimensional (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 low-pass 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.,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M174','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M174">View MathML</a>

(3.1)

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M175','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M175">View MathML</a>

(3.2)

FFT (fast Fourier transform algorithm), the classical five-point 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 low-pass filter as one smoothing method in the first phase. For simplicity, we refer to the method as GLF-GLS (Gaussian low-pass filter-gray level set).

On the other hand, using the scheme in [31], problems (2.2)-(2.4) can be discretized as

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M176','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M176">View MathML</a>

where <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M177','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M177">View MathML</a>,

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M178','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M178">View MathML</a>

and

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M179','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M179">View MathML</a>

where

<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M180','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M180">View MathML</a>

where <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M181','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M181">View MathML</a> is the set of the two neighbors of pixel i (boundary pixels have only one neighbor). AOS schemes with large time steps still reveal average grey value invariance, stability based on extremum principle, Lyapunov functionals, and convergence to a constant steady-state [31]. The AOS scheme is less than twice the typical effort needed for the PM scheme, a rather low price for gaining absolute stability [31]. Hence, in our numerical experiments, the AOS scheme is considered as the other smoothing method in the first phase. For simplicity, we refer to the two-phase method with the smoothing method as DE-GLS (diffusion equation-gray level set).

3.2 Segmentation performance

In Figure 3, we illustrate the performance of CVM, GLF-GLS and DE-GLS on the synthetic noise Test01 image (size: <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M182','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M182">View MathML</a>). Among the segmentations, all algorithms give similar and good performances. For CVM (the Chan-Vese method), utilizing the unconditional LOD scheme, the time step size can be sufficiently large to reduce the iteration steps (only 5/12 steps in Table 1). However, re-initializing the level-set function costs a lot of CPU time (Table 1). In the new method, GLF-GLS cost very little time (Table 1) and for DE-GLS, it not only costs little time, but also has a very good segmentation result, especially for some singular information, such as corners and edges of the image.

thumbnailFigure 3. Segmentations for the noiseTest01image (size:<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M183','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M183">View MathML</a>). (a) The original image. (b) Corrupted Test01 image with Gaussian noise (<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M184','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M184">View MathML</a>). (c) Smoothed Test01 image with the AOS scheme (<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M185','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M185">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M186','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M186">View MathML</a>, twice iterations). (d) Algorithm DE-GLS. (e) Algorithm GLF-GLS. (f) CVM. (g)-(i) The segmentation counter of Algorithm DE-GLS, Algorithm GLF-GLS and CVM, respectively.

Table 1. Comparison of CPU time in seconds and iterate step

In Figures 4 and 5, we illustrate the results of GLF-GLS and DE-GLS 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).

thumbnailFigure 4. Segmentations for the noiseultrasoundimage (size:<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M187','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M187">View MathML</a>).(a) The original image. (b) The smooth image by Gaussian low-pass filter with <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M53','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M53">View MathML</a>. (c) Smoothed ultrasound image with the AOS scheme (<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M189','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M189">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M190','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M190">View MathML</a>, twice iterations). (d) Algorithm DE-GLS. (e) Algorithm GLF-GLS. (f) CVM. (g)-(i) The segmentation counter of Algorithm DE-GLS, Algorithm GLF-GLS and CVM, respectively.

thumbnailFigure 5. Segmentations for the noisebrainimage (size:<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M191','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M191">View MathML</a>).(a) The original image. (b) The smooth image by Gaussian low-pass filter with <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M192','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M192">View MathML</a>. (c) Smoothed brain image with the AOS scheme (<a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M193','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M193">View MathML</a>, <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M194','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M194">View MathML</a>, twice iterations). (d) Algorithm DE-GLS. (e) Algorithm GLF-GLS. (f) CVM. (g)-(i) The segmentation counter of Algorithm DE-GLS, Algorithm GLF-GLS and CVM, respectively.

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 <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1">View MathML</a>, where N is the number of pixels in the image [31] and so is the Gaussian low-pass filter. In the second segmentation stage, our algorithm only sweeps the image once, so the complexity of the stage is no more than <a onClick="popup('http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.boundaryvalueproblems.com/content/2014/1/11/mathml/M1">View MathML</a>. In Table 1, we compare the CPU time needed for all three algorithms. Especially, we see that our algorithm GLF-GLS is about 0.01-0.08 seconds and is the fastest out of the three algorithms.

4 Summary

In this paper, we have proposed and implemented a novel image segmentation algorithm based on the Chan-Vese active contour model. The discrete gray level-set 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 level-set method to segment the region of the original image. The proposed new segmentation algorithm does not require the initialization of the level-set functions, which is a difficult problem in the Chan-Vese 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 Chan-Vese method and our proposed method. Obviously, our method is much more efficient than the Chan-Vese 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

  1. 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 OpenURL

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

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

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

  5. 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 OpenURL

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

  7. 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 OpenURL

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

  9. 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)

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

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

  12. 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 OpenURL

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

  14. 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)

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

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

  17. 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 OpenURL

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

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

  20. Pan, Y, Birdwell, JD, Djouadi, SM: Efficient implementation of the Chan-Vese models without solving PDEs. Victoria, BC, Canada, Oct. 03-06. (2006)

  21. He, L, Osher, SJ: Solving the Chan-Vese 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)

  22. Pan, Y, Birdwell, DJ, Seddik, DM: An efficient bottom-up image segmentation method based on region growing, region competition and the Mumford Shah functional. Victoria, BC, Canada, Oct. 03-06. (2006)

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

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

  25. 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 OpenURL

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

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

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

  29. 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 OpenURL

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

  31. 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 OpenURL