A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model.
We propose a new multiphase level set framework for image segmentation using the Mumford and Shah model, for piecewise constant and piecewise smooth optimal approximations. The proposed method is also a generalization of an active contour model without edges based 2-phase segmentation, developed by the authors earlier in T. Chan and L. Vese (1999. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141151) and T. Chan and L. Vese (2001. IEEE-IP, 10(2):266277). The multiphase level set formulation is new and of interest on its own: by construction, it automatically avoids the problems of vacuum and overlap&semi; it needs only log n level set functions for n phases in the piecewise constant case&semi; it can represent boundaries with complex topologies, including triple junctions&semi; in the piecewise smooth case, only two level set functions formally suffice to represent any partition, based on The Four-Color Theorem. Finally, we validate the proposed models by numerical results for signal and image denoising and segmentation, implemented using the Osher and Sethian level set method.
partition problem of (Mumford and Shah 1989) for segmentation of images. For the implementation of
the active contour model from (Chan and Vese 1999), (Chan and Vese 2001), the level set method of
(Osher and Sethian 1988) was successfully used, together with a particular numerical approximation,
which allowed to automatically detect interior contours. The method was then easily extended to
vector-valued images (Chan, Sandberg and Vese 2000), and is robust with respect to noise.
In this paper, we generalize further this active contour model (based binary segmentation), to
segment images with more than two regions, by proposing a new multiphase level set framework for
the (Mumford and Shah 1989) problem. We will show that, with a reduced number of level set
functions, triple junctions and complex topologies can be represented. In addition, the phases used in
the partition do not produce \vacuum" and \overlap". Finally, in the piecewise smooth case, based on
The Four-Color Theorem, we show that only two level set functions formally should su-ce to represent
any partition.
The outline of the paper is as follows: in this Introduction, we give the necessary background on
the main two ingredients of the method: the Mumford and Shah model and variational level sets; then,
we shortly describe the most related relevant work. In Section 2, we present the proposed model in the
piecewise constant case in two dimensions, while in Section 3 we consider the piecewise smooth version
of the model, in one and two dimensions. Finally, in Section 4 we present numerical results for signal
and image denoising and segmentation, using the proposed models, and we end the paper by a short
concluding section and an appendix, with the details of the numerical algorithms.
The Mumford and Shah problem
Let
be open and bounded. For the purpose of illus-
tration, we consider for the moment the two-dimensional case, but any dimension could be considered.
For instance, we will also treat the one-dimensional case in Section 3. Let C be a closed subset in
made up of a nite set of smooth curves. The connected components
of
n C are denoted
by
i , such
that
We also denote by jCj the length of curves making up C. Let u 0
! IR be a
given bounded image-function.
The segmentation problem in computer vision, as formulated by (Mumford and Shah 1989), can
be dened as follows: given an observed image u 0 , nd a
decomposition
of
and an optimal
piecewise smooth approximation u of u 0 , such that u varies smoothly within
each
rapidly or
discontinuously across the boundaries
of
To solve this problem, (Mumford and Shah 1989) proposed the following minimization problem:
F MS (u;
Z
Z
are xed parameters, to weight the dierent terms in the energy. For (u; C) a minimizer
of the above energy, u is an \optimal" piecewise smooth approximation of the initial, possibly noisy,
image u 0 , and C has the role of approximating the edges of u will be smooth only outside C, i.e. on
Theoretical results of existence and regularity of minimizers of (1) can be found for example in
(Mumford and Shah 1989), (Morel and Solimini 1988), (Morel and Solimini 1989), (De Giorgi, Carriero,
Leaci 1989), (Morel and Solimini 1994).
A reduced case of the above model is obtained by restricting the segmented image u to piecewise
constant functions, i.e. inside each connected
component
. Then the problem is
often called the \minimal partition problem", and in order to solve it, in (Mumford and Shah 1989) it
is proposed to minimize the following functional:
MS (u;
Z
It is easy to see that, for a xed C, the energy from (2) is minimized in the variables c i by setting
in
Theoretical results for existence and regularity of minimizers of (2) can be found
for example in (Mumford and Shah 1989), (Massari and Tamanini 1993), (Tamanini 1996), (Tamanini
and Congedo 1996), (Leonardi and Tamanini 1998).
It is not easy to minimize in practice the functionals (1) and (2), because of the unknown set C of
lower dimension, and also because the problems are not convex. After giving the necessary background
on the level set method, we will review some alternative solutions to this problem, and other related
relevant models for image segmentation, before presenting the proposed level set formulations.
The level set method and variational level sets (Osher and Sethian 1988) proposed an eective
implicit representation for evolving curves and surfaces, which has found many applications, because it
allows for automatic change of topology, such as merging and breaking, and the calculations are made
on a xed rectangular grid.
W-w

Figure

1: A curve, given by the zero level set of the function , is the boundary between the regions:
A given curve C (the boundary of an open set ! 2
i.e. represented implicitly, as the
zero level set of a scalar Lipschitz continuous function
(called level set function), such that
(see Fig. 1):
in
A typical example of level set function is given by the signed distance function to the curve. Using
this representation, geometrical quantities, properties and motions can be expressed. Indeed, using the
Heaviside function H(z), equal with 1 if z  0 and with 0 if z < 0, the length of C and the area of !
can be expressed respectively by (Evans and Gariepy 1992):
Z
Z
H()dxdy (3)
(we mention that the rst integral is in the sense of measures).
Considering any C 1 (IR) approximation and regularization H " of the Heaviside function as " ! 0,
and denoting by
" (an approximation to the one-dimensional Dirac delta function - 0 ), we can
approximate the length functional by L "
R
R
()jrjdxdy, and the area
functional by A "
R
Then we can formally write the associated Euler-Lagrange equations, obtained by minimizing the
above functionals with respect to , and parameterizing the descent directions by an articial time t,
respectively (with associated initial
@
@t
r
or @
@t
A standard rescaling can be made, as in (Zhao et al. 1996), by replacing - " () by jrj, giving
the following equations, already introduced in (Osher and Sethian 1988) in the context of the level set
theory:
@
@t
r
or @
@t
(motion by mean curvature minimizing the length, and motion with constant speed minimizing the
area). Here, r
jrj represents the unit normal to a level curve of  at every point, and div
r
represents the curvature of the level curve.
For more recent and general expositions on the level set method and applications, we refer the
reader to (Sethian 1999) and (Osher and Fedkiw 2001), (Osher and Fedkiw, to appear). Theoretical
results of existence, uniqueness, and regularity of the front for the equations from (4), in the sense of
viscosity solutions, can be found in many papers, for instance in (Barles 1994) for Hamilton-Jacobi
equations, and in (Evans and Spruck 1991), (Chen, Giga and Goto 1991), (Crandall, Ishii and Lions
1992), or more recently in (Barles and Souganidis 1998), for generalized mean curvature
ow equations
and evolution of fronts.
Related relevant work for image segmentation We brie
y mention here some of the most related
relevant works, and we discuss their connections or dierences with our approach.
The weak formulation of the Mumford and Shah problem and approximations A weak
formulation of (1) has been proposed in (De Giorgi and Ambrosio 1988), and studied in (Dal Maso,
Morel and Solimini 1992), where C is replaced by the set J u of jumps of u, in order to prove the
existence of minimizers (it is known that a global minimizer of (1), or of the weak formulation, is not
unique in general). In (Morel and Solimini 1988), (Morel and Solimini 1989), the authors proposed a
constructive existence result in the piecewise-constant case, and in (Koep
er, Lopez and Morel 1994),
a practical multi-scale algorithm based on regions growing and merging is proposed for this case. For
a general exposition of the segmentation problem by variational methods, both in theory and practice,
we refer the reader to (Morel and Solimini 1994). We also refer to (Ambrosio 1989) for theoretical
results on functionals dened on the appropriate space for image segmentation: the
space of
special functions of bounded variation.
Two elliptic approximations by -convergence to the weak formulation of the Mumford-Shah functional
have been proposed in (Ambrosio and Tortorelli 1990), (Ambrosio and Tortorelli 1992). They
approximated a minimizer (u; J u ) of F MS (u; J u ), by two smooth functions (u
in the L
1264 ology, and v  is dierent from 1 only in a small neighborhood of
J u , which shrinks as  ! 0. The elliptic approximations lead to a coupled system of two equations in
the unknowns u  and v  , to which standard PDE numerical methods can be applied.
Related approximations and numerical results can be found in (March 1992), (Chambolle 1992),
(Chambolle 1995), (Chambolle 1999), (Bourdin and Chambolle 2000), (Bourdin 1999). Also, in (Cham-
bolle and Dal Maso 1999), the authors provide an approximation by convergence based on the
nite element method, to the weak formulation.
Note that, most of the methods solving the weak formulation, do not explicitly compute the partition
of the image and the set of curves C. In general (see for instance (Ambrosio and Tortorelli 1990),
(Ambrosio and Tortorelli 1992), only an approximation to C is obtained, by a sequence of regions
enclosing C, but converging in the limit to the empty set.
Active contours without edges We recall now the authors's active contour model without edges
from (Chan and Vese 1999), (Chan and Vese 2001), which is a particular case and the motivation of
the proposed models from the present paper. Given the curve
an open subset,
and two unknown constants c 1 and c 2 ,
denoting
n !, we have proposed to minimize
the following energy with respect to c 1 ; c 2 and C:
Z
Z
or in the level set formulation, with
Z
Z
Z
Considering H " and - " any C 1 approximations and regularizations of the Heaviside function H and
minimizing the energy, we obtain: (0; x;
R
R
R
dxdy
R
dxdy
@
@t
div
r
This model performs active contours, looking for a 2-phase segmentation of the image, given by
y))). The main advantages, by comparison with other active
contour models, are: it automatically detects interior contours, the initial curve can be placed
anywhere in the image, and it detects both contours with, or without gradient (called cognitive con-
tours, following (Kanizsa 1997)). Natural generalizations are presented in this paper, in Sections 2 and
3, for image segmentation, where more than two segments and non-constant regions can be represented,
using a new multi-phase level set approach.
Inward and outward curve evolution using level set method A similar model with (Chan
and Vese 1999), (Chan and Vese 2001) was proposed in (Amadieu et al. 1999). Again, this model is
limited to object detection and two-phase segmentation, and it cannot segment images with more than
two segments and with triple junctions, for instance. We will not give here the details of the model
from (Amadieu et al. 1999), being similar with that one from (Chan and Vese 1999), (Chan and Vese
2001).
The previous two models already discussed above, (Chan and Vese 1999)-(Chan and Vese 2001)
and (Amadieu et al. 1999), cannot detect more than two segments and triple junctions. When working
with level sets to represent triple junctions and more than two segments, the general idea is to use
more then one level set function. Related relevant work is presented next, and this is the idea used in
the proposed approach, but in a dierent way.
A variational level set approach to multiphase motion The work from (Zhao et al. 1996) is
devoted to motion of junctions and boundaries of multiple phases, in a variational level set approach.
Each
phase
i is represented via a level set function  i , such
that
0g. The total
length of boundaries between phases is computed as 1P
R
In order to keep the phases
disjoint (no overlap) and their union the
domain
(no vacuum), the authors in (Zhao et al. 1996)
have added an additional term to the energy which is minimized, in the form
R
dxdy.
The Lagrange multiplier  is updated at each time step, to keep the constraint
points satised. Motions of triple junctions are then obtained.
A level set model for image classication In (Samson et al. 1999), (Samson et al. 2000),
the authors have applied the multi-phase level set representation from (Zhao et al. 1996) to the
reduced model of Mumford and Shah, for piecewise constant image segmentation. The problem is
called classication, because the mean intensities c i of classes are assumed to be known a-priori, and
only the set of boundaries C is unknown.
A statistical approach to snakes for bimodal and trimodal imagery In (Yezzi, Tsai and
1999), the authors are again using the idea of combining several level set functions, to represent
more than two segments in an image. They are showing numerical results with binary
ows (related with
the models (Chan and Vese 1999), (Chan and Vese 2001), (Amadieu et al. 1999)), but with additional
choices for the segmentation criteria (instead of
R
ju propose other choices, with
dierent statistical meanings). They also propose interesting ternary
ows, where two evolving curves
segment an image into three regions (two foreground regions and one background region).
Coupled geodesic active regions for image segmentation: a level set approach In (Para-
gios and Deriche 2000), the authors are using again multiple level set functions for image segmentation,
in a probabilistic framework. As in (Zhao et al. 1996), (Samson et al. 1999), (Samson et al. 2000),
each region is associated with one level set function. So, if N regions need to be segmented, then N
level set functions are needed. Results of coupled curve evolution are obtained, to segment images with
up to ve dierent regions.
As we have seen, there are several choices for the representation of the dierent phases and their
boundaries by level sets. As mentioned above, a rst idea was proposed in (Zhao et al. 1996), and
then applied in (Samson et al. 1999), (Samson et al. 2000): a level set function is associated to each
phase or each connected
component
i (this is also used in (Paragios and Deriche 2000)). But then
natural problems of vacuum and overlap appear, and these have been solved by adding additional
constraints into the above mentioned models. An interesting idea, but dierent than ours, to remove
the problems of vacuum and overlap, has been used in (Merriman, Bence and Osher 1994), but it is
not clear how to incorporate this formulation into a variational framework. Their idea was that, at
each step, after computing the characteristic functions  i , associated with each
phase
i , to re-dene
these characteristic functions by:  i (x; number of phasesg, to avoid the
problems of vacuum and overlap. For another work on partitions, we also refer the reader to (Ei, Ikota
and Mimura 1999). Finally, we would also like to refer to a projection method for motion of triple
junctions by level sets (Smith, Solis and Chopp 2002).
In this paper, we propose a dierent multi-phase level set representation, and by construction,
the distinct phases are disjoint (no overlap) and their union is the
domain
(no vacuum); also, we
need fewer level set functions to represent the same number of phases. Finally, we will see that triple
junctions and other complex topologies can be detected and represented by the proposed multi-phase
level set representation. Based on these characteristics, we think that the proposed approach is new
and dierent than the existing related models. The applications of the proposed multi-phase level set
formulation are devoted in this paper to image segmentation, via (Mumford and Shah 1989).
Many other authors have studied the minimization of the Mumford-Shah functional and related
problems for segmentation, both in theory and in practice, and it is impossible to mention all of them.
However, we would like to mention (Zhu, Lee and Yuille 1995), (Zhu and Yuille 1996), (Shah 1996),
(Shah 1999), (Shi and Malik 2000), (Sharon, Brandt and Basri 2000).
An interesting application of the level set method and energy minimization to segmentation of three-dimensional
structures has been proposed in (Lorigo et al. 1999), to extract complicated curve-like
structures, such as blood vessels.
For general expositions on segmentation of images by variational methods, both in theory and
algorithms, we refer the reader to (Mumford, Nitzberg and Shiota 1993) and (Morel and Solimini
1994). Also, for recent expositions of geometric PDE's, variational problems and image processing
(including snakes, active contours, curve evolution problems), we refer the reader to (Sapiro 2001),
(Aubert and Kornprobst 2001), (Guichard and Morel, to appear).
To summarize, in this paper we propose: an extension and generalization of the active contour
model without edges from (Chan and Vese 1999), (Chan and Vese 2001), to the general Mumford and
Shah model, in two cases: the piecewise constant case (2), and the piecewise smooth case (1). The
proposed models can identify individual segments in images with multiple segments and junctions, as
compared with the initial model (Chan and Vese 1999), (Chan and Vese 2001), where the detected
objects were belonging to the same segment. We also propose a new representation for multiphase
motion by level sets (requiring only log 2 n level set functions for n segments or phases in the piecewise
constant case), allowing for triple junctions, for example, without vacuum or overlap between phases.
In the piecewise smooth case, based on The Four-Color Theorem, we show that only two level set
functions su-ce for image segmentation. Finally, the proposed models inherit all the advantages of our
active contour model without edges: detection of edges with or without gradient, detection of interior
contours, automatic change of topology, robustness with respect to noise. The models can perform in
parallel active contours, segmentation, denoising, object and edge detection.
2 Description of the model in the piecewise-constant case
In this section, we show how we can generalize the 2-phase piecewise constant active contour model
without edges (Chan and Vese 1999), (Chan and Vese 2001), to piecewise constant segmentation of
images with more than two segments and junctions, using (2).
We note again that, using only one level set function, we can represent only two phases or segments
in the image. Also, other geometrical features, such as triple junctions, cannot be represented using
only one level set function. Our goal is to look for a new multiphase level set model with which we
can represent more than two segments or phases, triple junctions and other complex topologies, in
an e-cient way. We will need only log 2 n level set functions to represent n phases or segments with
complex topologies, such as triple junctions. In addition, our formulation automatically removes the
problems of vacuum and overlap, because our partition is a disjoint decomposition and covering of the
domain
by denition. This is explained next.
Let us consider level set functions  i
IR. The union of the zero-level sets of  i
will represent the edges in the segmented image. We also introduce the \vector level set function"
and the \vector Heaviside function"
are only 1 or 0. We can now dene the segments or phases in the
domain
in the following way: two
pixels
in
will belong to the same phase or class, if and only if
In other words, the classes or phases are given by the level sets of the function H(),
i.e. one class is formed by the set
(one phase or class contains those pixels (x; y)
of
having the same value H((x; y))).
There are up to possibilities for the vector-values in the image of H(). In this way, we
can dene up to phases or classes in the domain of
denition
The classes dened in this
way form a disjoint decomposition and covering of
Therefore, each pixel (x; y)will belong to
one, and only one class, by denition, and there is no vacuum or overlap among the phases. This is an
important advantage, comparing with the classical multiphase representation introduced in (Zhao et
al. 1996), and used in (Samson et al. 1999), (Samson et al. 2000). The set of curves C is represented
by the union of the zero level sets of the functions  i .
We label the classes by I, with 1  I  us introduce a constant vector of averages
in the class I, and the characteristic function  I for each class I.
Then the reduced Mumford-Shah energy (2) can be written as:
F MS
Z
Z
jr I j: (6)
In order to simplify the model, we will replace the length term by
R
(i.e. the sum of
the length of the zero-level sets of  i ). Thus, in some cases, some parts of the curves will count more
than once in the total length term, or in other words, some edges will have a dierent weight in the
total length term. We will see that with this slight modication and simplication, we still obtain very
results (it may have only a very small eect in most of the cases, because the tting term
is dominant).
Therefore, the energy that we will minimize is given by:
Z
Z
Clearly, for we obtain the 2-phase energy (5) considered in our active
contour model without edges. For the purpose of illustration, let us write the above energy for
phases or classes (and therefore using Fig. 2 left):
Z
Z
Z
Z
Z
Z
With these notations, we can express the image-function u as:

Figure

2: Left: 2 curves f partition the domain into 4 regions: f 1 > 0;  2 > 0g,
partition the domain into 8 regions:
The Euler-Lagrange equations obtained by minimizing (8) with respect to c and , embedded in a
dynamical scheme, are: given  1 (0; x;
@t
div
io
@t
div
io
We note that the equations in are governed by both mean curvature and jump of the data
energy terms across the boundary.
We show in Fig. 2 right, the partition of the
domain
into eight regions, using three level set
functions.
It is easy to extend the proposed model to vector-valued functions, such as color images, following
for instance (Chan, Sandberg and Vese 2000). In this case, u is the initial data, with
images), and for each channel we have the constants
In this case, the model for multichannel segmentation will be:
Z
Z
Note that, even if we work with vector-valued images, the level set functions are the same for all channels
(i.e. we do not need additional level set functions for each channel). The associated Euler-Lagrange
equations can easily be deduced.
3 Description of the model in the piecewise-smooth case
In this section, we propose a multi-phase level set formulation and algorithm for the general problem
of (Mumford and Shah 1989) in image processing (1), to compute piecewise smooth optimal approximations
of a given image. We consider the cases:
In one dimension: for signal segmentation and denoising, we show that, using only one level set
function, we can represent any signal with any number of segments in the partition.
In two dimensions:
(i) we generalize the 2-phase piecewise-constant model from (Chan and Vese 1999), (Chan and Vese
2001), to piecewise-smooth optimal approximations using only one level set function: dierent regions
of distinct intensities can be represented and detected with the correct intensities.
(ii) following the idea of the multi-phase level set partition from the previous section, we show
that, in the piecewise-smooth case, using only two level set functions, producing up to four phases, any
general case can be considered and represented by the proposed formulation. Our main idea is based
on The Four-Color Theorem.
The one-dimensional case: signal denoising and segmentation In many applications, we deal
with a source signal u
on
b). The problem of reconstructing u from a disturbed input u 0
deriving from a distorted transmission, can be modeled as nding the minimum
min
Z
(a;b)nC
a
ju
where C denotes the set of discontinuity points of u, and #(C) denotes the cardinal of C (the counting
measure).
We let
, with  being a one dimensional level set function, and we
introduce two functions u and u , such that
. These
two functions replace the two unknown constants used in (Chan and Vese 1999), (Chan and Vese 2001),
and are such that u 0g). Then the energy (9) can be written in
the level set formulation as:
min
a
a
a
a
ju
a
Minimizing this energy with respect to u we obtain the associated Euler-Lagrange equa-
tions, embedded in a dynamical scheme:
@
@t
Note that, in one dimension for signal segmentation, only one level set function su-ces to represent
a piecewise smooth function u, together with its set of jumps.
u=u-
u=u-
u=u-
u=u-
u=u+-
u=u+-
u=u+-
u=u+-

Figure

3: Left: example of partition of the image u in regions with boundaries represented via a single
level set function f = 0g, and with smooth value-functions u , u on each side of the curve. Right:
example of partition of the image u in regions with boundaries represented via two level set functions
and with smooth value-functions u ++ , all sides of the
curves.
The two-dimensional case: two-phase model We consider the corresponding two-dimensional
case, under the assumption that the edges (denoted by C) in the image can be represented by one level
set function , i.e. 0g. The most general case, allowing for any type of edges,
including triple junctions, will also be considered.
As in the 1-dimensional case, the link between the unknowns u and  can be expressed by introducing
two functions u and u , such that
We assume that u + and u are C 1 functions on   0 and on   0 respectively (and therefore with
continuous derivatives up to all boundary points, i.e. up to the boundary We illustrate our
formulation in Fig. 3 (left).
Then we obtain the following minimization problem from (1):
Z
Z
ju
Z
Z
Z
Minimizing F respect to u we obtain the following Euler-Lagrange
equations (embedded in a dynamical scheme for
@~n
@
@~n
@
@
@t
r
r
where @=@~n denotes the partial derivative in the normal direction ~n at the corresponding boundary.
We also associate the boundary condition @
@
to equation (12).
The equations for u and u will have a smoothing and denoising eect on the image u 0 , but only
inside homogeneous regions, and not across edges.
We would like to mention that ideas very similar with those from the above case, have been also
developed by (Tsai, Yezzi and Willsky 2001), independently and contemporaneously.
The two-dimensional case: four-phase model In the previous two cases, we have shown how
we can minimize the general Mumford-Shah functional for segmentation in the case where the set of
contours C can be represented by a single level set function, i.e. and  has opposite signs
on each side of C. By this method, we can already detect several objects of distinct gray-levels, but
we have a constraint on the type of edges. There are cases where the boundaries of regions forming
a partition of the image could not be represented in this way (i.e. using a single level set function).
Again, the natural idea is to use more than one level set function, as in Section 2.
We show that in the general case, the problem can be solved using only two level set functions, and
we do not have to know a-priori how many gray-levels the image has (or how many segments). The
idea is based on The Four-Color Theorem and is as follows.
Based on this observation, we can \color" all the regions in a partition using only four \colors",
such that any two adjacent regions have dierent \colors". Therefore, using two level set functions,
we can identify the four \colors" by the following
0g. The boundaries of the regions forming the partition will be given
by 0g, and this will be the set of curves C. Again, in our particular multiphase
formulation of the problem, we do not have the problems of \overlapping" or \vacuum", (i.e. the
phases are disjoint, and their union is the entire
domain
As in the previous case, the link between the function u and the four regions can be made by
introducing four functions u which are in fact the restrictions of u to each of the
four phases, as follows:
These notations are illustrated in Fig. 3 (right).
Again, using the Heaviside function, the relation between u, the four functions u
u , and the level set functions  1 and  2 can be expressed by:
Using the notation introduce an energy in level set formulation, based on the
Mumford-Shah functional (1):
Z
Z
Z
Z
Z
Z
Z
ju
Z
Z
Z
As in Section 2, we note that the expression
R
R
)j is not exactly the length
term of C, it is just an approximation and simplication. In practice, we have obtained satisfactory
results using the above formula, and the associated Euler-Lagrange equations are simplied.
We obtain the associated Euler-Lagrange equations as in the previous cases, embedded in a dynamic
scheme, assuming (t; x; y) 7!  i (t; x; y): minimizing the energy with respect to the functions u
we have, for each xed t:
@~n
@~n
@~n
@~n
The Euler-Lagrange equations evolving  1 and  2 , embedded in a dynamic scheme, formally are:
@t
r
@t
r
We have mentioned in the introduction existence results for the Mumford-Shah minimization prob-
lem. The global minimizer is not unique in general. We can also show, by standard techniques of the
calculus of variations on the spaces
and
(functions of bounded variation and special
functions of bounded variation respectively), and a compactness result due to (Ambrosio 1989), that
the proposed minimization problems from this paper, in the level set formulation, have a minimizer.
Finally, because there is no uniqueness among minimizers, and because the problems are non-convex,
the numerical results may depend on the initial choice of the curves, and we may compute a local
minimum only. We think that, using the seed initialization (see Section 4), the algorithms have the
tendency of computing a global minimum.
4 Numerical results
We x the space steps
Numerical results in the piecewise-constant case (2D) We show now numerical results using
the models from Section 2, and in particular using the four-phase (with two level set functions) and the
eight-phase (with three level set functions) models. The only varying parameter is , the coe-cient of
the length term. We give the cpu time in seconds for our calculations, performed on a 140MHz Sun
Ultra 1 with 256MB of RAM. In our numerical algorithm, we rst initialize the level set functions by
, then we compute the averages c I , and we solve one step of the PDE's in  i . Then we iterate these
last two steps.
We show in particular that triple junctions can be represented and detected using only two level
set functions, that interior contours are automatically detected and also that the model is robust in
the presence of noise and complex topologies.
We begin with a noisy synthetic image with four regions (Fig. 4, 5 and 6), and we consider several
dierent initial conditions. For the initial conditions (a), (b), (c) we use the four-phase piecewise
(a) (b) (c) (d)
ITERATIONS
ENERGY/ITERATION
(a)
(b)
(c)
(d)

Figure

4: Four dierent initial conditions and the energies versus iterations.
constant model, while for (d) we use the eight-phase piecewise constant model. The energy decrease
is shown in Fig. 4 bottom for the initial conditions (a)-(d). The image contains three objects of
distinct intensities, all correctly detected and segmented for initial conditions (a), (c), (d). This is
an improvement of the authors previous 2-phase active contour model (Chan and Vese 1999), (Chan
and Vese 2001), with which all three objects would have the same intensity in the segmented image,
belonging to the same segment or phase.
Because the energy which is minimized is not convex, and also that there is no uniqueness for the
minimizers, the algorithm may not converge to a global minimizer for a given initial condition. It
is then natural to consider dierent initial conditions for the same image with the same parameters,
and to compare the steady-state solutions from our numerical algorithm. For (c), we seed with small
initial curves. Only using the initial conditions (a), (c), (d) do we compute a global minimizer for
this image. For (b), the algorithm is trapped in a local minimum. In general, for real images with
more complicated features, we think that initial conditions of the types (c), (d) should be used, which
have the tendency to converge to a global minimizer. This type of initial condition is also related to
the region growing algorithm (Koep
er, Lopez and Morel 1994). We also note that using the initial
condition (c), the algorithm is much faster (see Fig. 6 left). In Fig. 6 right, we show a numerical result
on the same image with four segments, but using the 8-phase model with 3 level set functions. The
correct segmentation is obtained, and four nal segments are empty.

Figure

5: Segmentation of a noisy synthetic image, using the 4-phase piecewise constant model. First
and 3rd columns: the evolving contours overlay on the original image; 2nd and 4th columns: computed
averages of the four segments c 11
Right: (b) (the algorithm computes only a local minimum
in this case).
(c) (d)

Figure

(very fast). Right: (d) three-level
sets evolution with up to 8 phases (at steady state the correct segmentation is obtained, with four
segments, while the other four segments are empty).

Figure

7: Results on a synthetic image, with a triple junction, using the 4-phase piecewise constant
model with 2 level set functions. We also show the zero level sets of  1 and  2 .
In Fig. 7 we show a noisy synthetic image with a triple junction. Using only one level set function,
the triple junction cannot be represented. Most of the models need three level set functions, as in
(Zhao et al. 1996) and (Samson et al. 1999), (Samson et al. 2000). Here, we need only two level set
functions to represent the triple junction. We show their zero level sets, which have to overlap on a
segment of the triple junction.
We show next numerical results on two real pictures (an MRI brain image and a house), in Figures
8-9 and 10. We use here two level set functions, detecting four phases. We also show the nal four
segments detected by the algorithm. We see how the model can handle complex topologies, and also
that the four phases in Fig. 9 identify quite well the gray matter, the white matter, etc.
In Fig. 11 we show an example of a color RGB image (three channels) with contours without
gradient (cognitive contours following (Kanizsa 1997)). We also see that this result is an improvement
of the result on the same picture from (Chan, Sandberg and Vese 2000), where the three objects had
the same intensity in the end. Here, the correct intensities are detected, for each object. Again, this
generalized model can detect \contours without edges".
In Fig. 12 we show how the model works on another color RGB image, where we use three level
set functions  representing up to eight phases or colors. The algorithm detects six segments
and junctions. In the classical approaches, it would have been necessarily to consider at least six level
set functions (here, 2 of the nal 8 segments are empty).
Numerical results in the piecewise-smooth case (1D & 2D) We begin this part by an
experimental result for signal denoising and segmentation. We show in Fig. 13 left an original signal
and its noisy version, together with two points, where at the initial time. In Fig. 13 right, we
show the segmented signal, and the detected set of jumps given by at the steady state, using the
proposed level set algorithm in dimension 1, from Section 3. Note that piecewise-smooth regions are
very well reconstructed by the model, and that the jumps are well located and without smearing.
We show in Figures 14 and 15 two numerical results using the 2-phase algorithm from Section 3:
the evolving curves are superposed over the initial noisy image u 0 , and the denoised versions u of u 0
are also shown. In Figure 14, we see that the model performs as active contours, denoising and edge-
detection, and several objects of distinct intensities can be correctly segmented with only one level set
function. In Figure 15, we apply the model to a real piecewise-smooth image. As we have already
mentioned, similar results with those from Figures 14 and 15 have been obtained independently and
contemporaneously by (Tsai, Yezzi and Willsky 2001).
Finally, we show in Figure 16 numerical results on a real noisy image, using the four-phase model
from Section 3. At the initial time, the two curves given by f are shown in
dierent colors (we use again the seed initialization).

Figure

8: Segmentation of an MRI brain image, using two level set functions and four constant phases.

Figure

9: The algorithm depicts quite well the nal four segments from the previous result (white
matter, gray matter, etc. the nal averages are c
Initial Image u 0
Evolving contours over u 0
Evolving segments (averages)
Final four segments

Figure

10: Segmentation of a real outdoor picture, using two level set functions and four constant
phases. In the bottom row, we show the nal four segments obtained. The nal averages are: c

Figure

11: Numerical results on a synthetic color picture. We show in particular that contours not
dened by gradient can be detected. These are called cognitive contours (Kanizsa, 1997).

Figure

12: Color noisy picture with junctions. We use three level set functions representing up to
eight constant regions. Here six segments are detected. We show the nal zero-level sets of
Original Signal
Noisy Signal
Initial phi=0
Reconstructed Signal
Noisy Signal
Final phi=0

Figure

13: Left: original and noisy signal, together with the set of points where at the initial
time, represented by squares on the x axis. Right: reconstructed signal, noisy signal, and the set of
points where at the steady state (the jumps).

Figure

14: Results on a noisy image, using the 2-phase level set algorithm for the piecewise smooth
Mumford-Shah model. The algorithm performs as active contours, denoising and edge detection.

Figure

15: Numerical result using the 2-phase piecewise-smooth Mumford-Shah level set algorithm, on
a piecewise-smooth real image.

Figure

First row: original and noisy image. 2nd-5th rows: curves over u 0 , denoised u and the
four articial phases for increasing times, by the 4-phase piecewise-smooth model from Section 3.
with re-initialization to the distance function.
5 Conclusion
In this paper, we have introduced a new multiphase model for Mumford-Shah image segmentation, by
level sets. The proposed model is a common framework to perform active contours, denoising, segmen-
tation, and edge detection. The multiphase formulation is dierent than the classical approaches, and
has the advantages that the phases cannot produce vacuum or overlap, by construction (there is no
additional constraint to prevent vacuum or overlap), and it minimizes as much as possible the computational
cost, considerably reducing the number of level set functions. We show in particular that triple
junctions can be represented and detected using only two level set functions. In the piecewise-constant
case, we only need to know an upper bound of the segments, while in the four-phase piecewise-smooth
case, we do not need to know a-priori how many segments the image has. These models can be applied
to other problems, such as texture segmentation and discrimination. Finally, we validated the proposed
models by various numerical results in one and two dimensions.


Appendix

: The description of the numerical algorithms
4y be the space steps, 4t be the time be the discrete
points, for 1
arctan
The piecewise constant case For the purpose of illustration, we give the details of the numerical
algorithm for the four-phase model from Section 2, by solving the equations:
R
R
R
R
R
R
R
R
@t
div
io
@t
div
io
1;i;j and  0
2;i;j given (the initial set of curves). For each n > 0 until steady state:
compute by the above formulas the averages c n
00 .
as follows (using a semi-implicit nite dierences scheme): let
r   n
n
r   n
n
r   n
n
r   n
n
Similarly, let
r   n
n
r   n
n
n
n
The piecewise smooth case We give here the details of the numerical algorithm for solving the
following equations from Section 3, written in the form:
@
@t
r
r
i;j given (the initial curve). For each n > 0 until steady state:
compute u n;+
i;j and u n;
compute a C 1 extension of u n;+
i;j to f n
i;j  0g and a C 1 extension of u n;
i;j to f n
i;j , as follows:
c
d
r   n i+1;j  n i;j
r   n i;j  n i 1;j
n
n
grad n;+
u n;+
u n;+
u n;
u n;
We need the extension from step 2) above, to compute the jumps
along the curve. For instance, to extend u + to the region f  0g, we solve 4u
on f  0g, with given prescribed values on f > 0g. This can be done by iterating the scheme:
(n is xed for varying k). Other
possibilities for the extension step can be found in: (Zhao et al. 1996), (Chen et al. 1997), (Fedkiw et
al. 1999), (Fedkiw 1999); (Jensen 1993), (Caselles, Morel and Sbert 1997).
A usual procedure, when working with level set functions, is reinitialization to the distance function.
We have used this procedure only in the last numerical result from Fig. 16. For details, we refer to
(Sussman, Smereka and Osher 1994).

Acknowledgments

The rst author thanks to P. Burchard and R. March for their useful remarks and suggestions, and
also to G.P. Leonardi, for pointing out to us interesting references on minimal partition problems.
Both authors thank the unknown referees from IJCV and VLSM, for their very interesting remarks
and suggestions, which helped enormously to improve the presentation of this paper, and also the
organizing committee of VLSM, the Guest Editors O. Faugeras and N. Paragios. This work has been
supported in part by grants NSF/DMS-9973341, NSF/ITR-0113439, ONR N00014-96-1-0277, and NIH
P20MH65166.



--R

Inward and Outward Curve Evolution Using Level Set Method.
A compactness theorem for a special class of functions of bounded variation.

Approximation of functionals depending on jumps by elliptic functionals via convergence.
On the Approximation of Free Discontinuity Problems.

Mathematical Problems in Image Processing.
Solutions de viscosit
A new approach to front propagation problems: theory and applications.
Image segmentation with a
Implementation of a


Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations.

Discrete approximation of the Mumford-Shah functional in dimension two
An active contour model without edges.
Active contours without edges.
Active Contours without Edges for Vector-Valued Images
Uniqueness and Existence of Viscosity Solutions of Generalized Mean Curvature Flow Equations.
A simple level set method for solving Stefan problems.
User's guide to viscosity solutions of second order partial di
A variational method in image segmentation: existence and approximation results.
Existence theorem for a minimum problem with free discontinuity set.
New functionals in the calculus of variations.

Segregating partition problem in competition-diusion systems
Measure Theory and Fine Properties of Functions.
Motion of level sets by mean curvature.
The Ghost Fluid Method for Discontinuities and Interfaces.


Uniqueness of Lipschitz extensions: Minimizing the Sup Norm of the Gradient.

La grammaire du voir.
A multiscale algorithm for image segmentation by variational method.
On Minimizing Partitions with In



On the Finiteness of Optimal Partitions.
Motion of Multiple Junctions: A Level Set Approach.
Segmentation of images by variational methods: a constructive approach.
Segmentation d'images par m
Variational Methods in Image Segmentation.
Optimal approximation by piecewise smooth functions and associated variational problems.

Level set methods: An overview and some recent results.
To appear.
Fronts Propagating with Curvature-Dependent Speed: Algorithms Based on Hamilton-Jacobi Formulation
Coupled Geodesic Active Regions for image segmentation: A Level Set Approach.


Geometric Partial Di
Fast Marching Methods and Level Set Methods: Evolving Interfaces in Computational Geometry
A common framework for curve evolution

Riemannian Drums
Fast Multiscale Image Segmentation.
Normalized cuts and image segmentation.
A projection method for motion of triple junctions by level sets.
A level set approach for computing solutions to incompressible two-phase ows
Optimal Approximation by Piecewise Constant Functions.
Optimal Segmentation of Unbounded Functions.

A statistical approach to snakes for bimodal and trimodal imagery
Curve evolution implementation of the Mumford- Shah functional for image segmentation
A Variational Level Set Approach to Multiphase Motion.
Region competition: Unifying snakes
Region competition: Unifying snakes
--TR

--CTR
Chen , Yue Zhou , Yonggang Wang , Jie Yang, Rapid and Brief Communication: GACV: Geodesic-Aided C-V method, Pattern Recognition, v.39 n.7, p.1391-1395, July, 2006
Tariq D. Aslam, A partial differential equation approach to multidimensional extrapolation, Journal of Computational Physics, v.193 n.1, p.349-355, January 2004
Yingjie Zhang, An improved algorithm for the piecewise-smooth Mumford and Shah model in image segmentation, EURASIP Journal on Bioinformatics and Systems Biology, v.2006 n.1, p.5-5, January 2006
Ronny Ramlau , Wolfgang Ring, A Mumford-Shah level-set approach for the inversion and segmentation of X-ray tomography data, Journal of Computational Physics, v.221 n.2, p.539-557, February, 2007
S. Y. Wang , K. M. Lim , B. C. Khoo , M. Y. Wang, An extended level set method for shape and topology optimization, Journal of Computational Physics, v.221 n.1, p.395-421, January, 2007
Sasan Mahmoodi , Bayan S. Sharif, A nonlinear variational method for signal segmentation and reconstruction using level set algorithm, Signal Processing, v.86 n.11, p.3496-3504, November 2006
J. R. Rommelse , H. X. Lin , T. F. Chan, Efficient active contour and K-means algorithms in image segmentation, Scientific Programming, v.12 n.2, p.101-120, April 2004
Christophe Zimmer , J. -C. Olivo-Marin, Coupled Parametric Active Contours, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1838-1842, November 2005
Michael Hintermller , Wolfgang Ring, An Inexact Newton-CG-Type Active Contour Approach for the Minimization of the Mumford-Shah Functional, Journal of Mathematical Imaging and Vision, v.20 n.1-2, p.19-42, January-March 2004
Yang Xiang , Albert C. S. Chung , Jian Ye, An active contour model for image segmentation based on elastic interaction, Journal of Computational Physics, v.219 n.1, p.455-476, 20 November 2006
Abdol-Reza Mansouri , Amar Mitiche , Carlos Vzquez, Multiregion competition: a level set extension of region competition to multiple region image partitioning, Computer Vision and Image Understanding, v.101 n.3, p.137-150, March 2006
Cheng Bing , Wang Ying , Zheng Nanning , Bian Zhengzhong, Object based segmentation of video using variational level sets, Machine Graphics & Vision International Journal, v.14 n.2, p.145-157, January 2005
S. Drapaca , Valerie Cardenas , Colin Studholme, Segmentation of tissue boundary evolution from brain MR image sequences using multi-phase level sets, Computer Vision and Image Understanding, v.100 n.3, p.312-329, December 2005
Hailin Jin , Anthony J. Yezzi , Stefano Soatto, Mumford-Shah on the Move: Region-Based Segmentation on Deforming Manifolds with Application to 3-D Reconstruction of Shape and Appearance from Multi-View Images, Journal of Mathematical Imaging and Vision, v.29 n.2-3, p.219-234, November  2007
Payel Ghosh , Melanie Mitchell, Segmentation of medical images using a genetic algorithm, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA
Lin He , Chiu-Yen Kao , Stanley Osher, Incorporating topological derivatives into shape derivatives based level set methods, Journal of Computational Physics, v.225 n.1, p.891-909, July, 2007
Thomas Cecil, A numerical method for computing minimal surfaces in arbitrary dimension, Journal of Computational Physics, v.206 n.2, p.650-660, 1 July 2005
T. Amiaz , N. Kiryati, Piecewise-Smooth Dense Optical Flow via Level Sets, International Journal of Computer Vision, v.68 n.2, p.111-124, June 2006
Qiang Du , Max Gunzburger , Lili Ju , Xiaoqiang Wang, Centroidal Voronoi Tessellation Algorithms for Image Compression, Segmentation, and Multichannel Restoration, Journal of Mathematical Imaging and Vision, v.24 n.2, p.177-194, March     2006
Threshold dynamics for the piecewise constant Mumford-Shah functional, Journal of Computational Physics, v.211 n.1, p.367-384, 1 January 2006
Xavier Bresson , Selim Esedoglu , Pierre Vandergheynst , Jean-Philippe Thiran , Stanley Osher, Fast Global Minimization of the Active Contour/Snake Model, Journal of Mathematical Imaging and Vision, v.28 n.2, p.151-167, June      2007
Nikolay M. Sirakov, A New Active Convex Hull Model for Image Regions, Journal of Mathematical Imaging and Vision, v.26 n.3, p.309-325, December  2006
Xue-Cheng Tai , Oddvar Christiansen , Ping Lin , Inge Skjlaaen, Image Segmentation Using Some Piecewise Constant Level Set Methods with MBO Type of Projection, International Journal of Computer Vision, v.73 n.1, p.61-76, June      2007
Olivier Juan , Renaud Keriven , Gheorghe Postelnicu, Stochastic Motion and the Level Set Method in Computer Vision: Stochastic Active Contours, International Journal of Computer Vision, v.69 n.1, p.7-25, August    2006
Daniel Cremers , Nir Sochen , Christoph Schnrr, A Multiphase Dynamic Labeling Model for Variational Recognition-driven Image Segmentation, International Journal of Computer Vision, v.66 n.1, p.67-81, January   2006
Xavier Bresson , Pierre Vandergheynst , Jean-Philippe Thiran, A Variational Model for Object Segmentation Using Boundary Information and Shape Prior Driven by the Mumford-Shah Functional, International Journal of Computer Vision, v.68 n.2, p.145-162, June 2006
Ganesh Sundaramoorthi , Anthony Yezzi , Andrea C. Mennucci, Sobolev Active Contours, International Journal of Computer Vision, v.73 n.3, p.345-366, July      2007
Tammy Riklin-Raviv , Nahum Kiryati , Nir Sochen, Prior-based Segmentation and Shape Registration in the Presence of Perspective Distortion, International Journal of Computer Vision, v.72 n.3, p.309-328, May       2007
Matthias Heiler , Christoph Schnrr, Natural Image Statistics for Natural Image Segmentation, International Journal of Computer Vision, v.63 n.1, p.5-19, June      2005
Tony F. Chan , Xue-Cheng Tai, Level set and total variation regularization for elliptic inverse problems with discontinuous coefficients, Journal of Computational Physics, v.193 n.1, p.40-66, January 2004
Frank Losasso , Tamar Shinar , Andrew Selle , Ronald Fedkiw, Multiple interacting liquids, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
Qiang Chen , Jian Luo , Pheng Ann Heng , Xia De-shen, Fast and active texture segmentation based on orientation and local variance, Journal of Visual Communication and Image Representation, v.18 n.2, p.119-129, April, 2007
Nikos Paragios , Rachid Deriche, Geodesic active regions and level set methods for motion estimation and tracking, Computer Vision and Image Understanding, v.97 n.3, p.259-282, March 2005
Qi Xia , Michael Y. Wang, Level set based method for simultaneous optimization of material property and topology of functionally graded structures, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
Bodo Rosenhahn , Thomas Brox , Joachim Weickert, Three-Dimensional Shape Knowledge for Joint Image Segmentation and Pose Tracking, International Journal of Computer Vision, v.73 n.3, p.243-262, July      2007
Daniel Cremers , Mikael Rousson , Rachid Deriche, A Review of Statistical Approaches to Level Set Segmentation: Integrating Color, Texture, Motion and Shape, International Journal of Computer Vision, v.72 n.2, p.195-215, April 2007
Ronald P. Fedkiw , Guillermo Sapiro , Chi-Wang Shu, Shock capturing, level sets, and PDE based methods in computer vision and image processing: a review of Osher's contributions, Journal of Computational Physics, v.185 n.2, p.309-341, March
energy minimization;level sets;image segmentation;edge detection;active contours;curvature;denoising;multi-phase motion;PDE's