Gradient
Flows
and Geometric Active Contour Models
Satyanad Kichenassamy Department of Mathematics University of Minnesota Minneapolis,
MN
55455
Peter Olver Department
of
Mathematics University
of
Minnesota Minneapolis,
MN
55455
Abstract
In this paper, we analyze the geometric active con tour models discussed in
[6
181
rom a curve evo lution point
of
view and propose some modifications based
on
gradient flows relative to certain new feature based Riemannian metrics. This leads
to
a novel snake paradigm in which the feature
of
interest may be con sidered to lie at the bottom
of
a potential well. Thus the snake is attracted very naturally and eficiently to the desired feature. Moreover, we consider some
30
active surface models based on these ideas.
1
Introduction
In the past few years,
a
number of approaches have been proposed for the problem of
snakes
or
active con tours.
The underlying principle in these works is based upon the utilization of deformable contours which con form to various object shapes and motions. Snakes have been used for edge and curve detection, segmen tation, shape modelling, and visual tracking. The re cent book by Blake and Yuille [5] contains an excel lent collection of papers on the theory and practice of deformable contours together with
a
large list of ref erences to which which we refer the interested reader. In most
of
the classical frameworks, one considers energy minimization methods where controlled conti nuity splines are allowed to move under the influence of external image dependent forces, internal forces, and certain contraints set by the user. See [14, 29,
51.
As is wellknown there may be
a
number of problems associated with this approach such
as
initializations, existence of multiple minima, and the selection of the elasticity parameters. In the present paper, we consider
a
method which was strongly influenced by the elegant approaches of
Arun Kumar Department of Aerospace Eng. University
of
Minnesota Minneapolis,
MN
55455
Allen Tannenbaum and Anthony
Yezzi
Department
of
Electrical Eng. University
of
Minnesota Minneapolis,
MN
55455
Caselles
et al.
[6] and Malladi
et al.
[MI.
In these works, a level set curve evolution method is presented to solve the problem. Our idea is simply to note that both these approaches are based on Euclidean curve shortening evolution which in turn defines the gradient direction in which the Euclidean perimeter is shrink ing
as
fast
as
possible. (See Section 2.) Pushing this concept to the next logical step, we can derive new active contour models by multiplying the Euclidean arclength
by
a
function tailored
to
the features of interest to which we want to flow, and then writ ing down the resulting
gradient evolution equations.
Mathematically, this amounts to defining
a
new Rie mannian metric in the plane tailored to the given im age, and then computing the corresponding gradient flow. This leads to some new snake models which effi ciently attract the given active contour to the features of interest (which basically lie at the bottom
of
a
po
tential well).
The method also allows us to naturally write down 3D active surface models
as
well. One can completely justify this method using viscosity theory which is done
in
[15].
Full details
of
these results can be found in
[15].
After this paper was written and submitted for publication, we were informed that
a
similar method has been reported in
[7].
This work was supported in part by grants from the National Science Foundation DMS9204192 and ECS 9122106, by the Air Force Office of Scientific Research F496209410058DEF, by the Army Research Office DAAH0494G0054 and DAAH0493G0332, and by Image Evolutions Limited.
2
Curve Shortening
Flows
The motivation for the equations underlying active geometric contours comes from
Euclidean curve short
810
0818670428/95 4.00
1995
IEEE
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on October 6, 2008 at 21:38 from IEEE Xplore. Restrictions apply.
ening.
Therefore, in this section we will review the relevant curve evolution theory in the plane
R2.
Accordingly, for
K
the curvature, and
l
he inward unit normal, one considers families of plane curves evolving according to the
geometric heat equation
aC
at
KJq
This equation has
a
number of properties which make it very useful in image processing, and in particular, the basis of
a
nonlinear scalespace for shape represen tation
[l,
3, 16, 191.
Indeed,
(1)
is the Euclidean curve shortening flow, in the sense that the Euclidean perimeter shrinks as quickly
as
possible when the curve evolves according to
(1)
[ll,
131.
Since, we will need
a
similar argument for the snake model we discuss in the next section, let us work out the details. Let
C
=
C p,
be
a
smooth family of closed curves where
t
parametrizes the family and
p
the given curve, say
0
5
p
5
1.
(Note we assume that
C 0,t)
=
C(1,t)
and similarly for the first derivatives.) Consider the length functional Then differentiating (taking the “first variation”), and using integration by parts, we see that But observing now that is (Euclidean) arclength, and using the definition of curvature, we see that
(
,
Kfl dS.
LL t)
:
’ t)
=

Thus the direction in which
L t)
is decreasing most rapidly is when
dC
.
at
KN.
Thus
(1)
is precisely
a
gradient flow.
A
much deeper fact
is
that simple closed curves converge to “round” points when evolving according to
(1)
without developing singularities; see
[ll,
131.
This fact is one of the keys for the geometric active contour models considered below.
3
D
Active Contour
Models
In two elegant papers, Caselles
et
al.
[SI
and Mal ladi
e
al.
[18]
propose
a
snake model based on the level
set
formulation of the Euclidean curve shorten ing equation. More precisely, their model is Here the function
4(z,
y)
depends on the given image and is used
as
a
“stopping term.”
For
example, the term 4(z,y) may chosen to be small near an edge, and
so
acts to stop the evolution when the contour gets close to an edge. In
[6, 181,
the term
(3)
is chosen, where
I
is the (greyscale) image and
G,
is
a
Gaussian (smoothing) filter. (In
[SI,
n
=
1,
and in
[18],
n
=
2.)
The function Qf(z,y,t) volves in
(2)
according to the associated level set flow for planar curve evolution in the normal direction with speed
a
function of curvature which was introduced in the fun damental work of OsherSethian
[21, 22,
25,
26, 271.
It is important
to
note that
as
we have seen above, the Euclidean curve shortening part of this evolution, namely
=
IlVQflldiv
a)
s derived
as
a
gra dient flow for shrinking the perimeter
as
quickly
as
possible. As is explained in
[SI,
the constant
inflation term
is added in
(2)
in order
to
keep the evolution moving in the proper direction. Note that we are tak ing to be negative in the interior and positive in the exterior of the zero level set contour. In
[18],
the inflationary constant is considered both with
a
positive sign (inward evolution of the evolution of the contour in the direction of decreasing
\E)
and with
a
negative sign (outward or expanding evolution). (Note the sign convention we have taken for bove.) In the latter case, this can be referred to
as
expand ing “balloons” or “bubbles”
as
in
[28].
For
simplicity, unless stated otherwise explicitly, we will take
0
(inward evolutions) in what follows below. Instead of using
a
Gaussian to smooth the image one may of course use the
a
nonlinear smoothing filter based on the curvature. There are of course many possibilities for
a
stopping term besides intensity: texture, optical flow, stereo disparity, etc. We would like to modify the model
(2)
in
a
manner suggested by the computation in Section
2.
Namely, we will change the ordinary Euclidean arclength func tion along
a
curve
C
=
~ p), p))~
ith parameter
p
given by
ds
=
IlC,lldp
=
zi
+
yi)’/2dp
81
1
to
ds+
=
4ds
=
2;
+
~;)l/~4dp,
where
Q z,
)
is
a
positive differentiable function. We now essentially repeat the computation made in Sec tion
2,
i.e., we want
to
compute the corresponding gradient flow for shortening length relative to the new metric
ds4.
Accordingly set Let denote the unit tangent. Then taking the first vari ation of the modified length function
L4,
and using integration by parts just
as
above, we get that which means that the direction in which the
L,
perimeter is shrinking
as
fast
as
possible is given by
4)
This is precisely the gradient flow corresponding to the miminization of the length functional
L4.
Since the tangential component of equation
4)
may be dropped, this may be simplified to
(5)
The level set version of this is One expects that this evolution should attract the con tour very quickly to the feature which lies at the bot tom of the
potential well
described by the gradient flow
6).
As
in
[6,
181,
we we may also add
a
constant in flation term (which may be interpreted
as
a Lagrange multiplier for
a
constrained version of the given opti mization problem), and
so
derive a modified model
of
(2)
given by
a
VQ
4ll~*ll~~~~
)
U
+
V
.
vq.
(7)
at
IIVQII
Notice that for
4
as
in
(3),
V4
will look like a dou blet near an edge. Of course, one may choose other candidates for in order to pick out other features. We have implemented this snake model based on the algorithms of OsherSethian
[21, 22, 25, 26, 271
and Malladi
et al.
[18].
Some preliminary numerical results with our code will be presented in below. Note that the metric
ds4
has the property that it becomes small where
4
is small and vice versa. Thus
at
such points lengths decrease and
so
one needs less “en ergy” in order to move. Consequently, it seems that such
a
metric is natural for attracting the deformable contour to an edge when
4
has the form
(3).
4
3D
Active Contour
Models
In this section, we will discuss some possible geo metric
3D
contour models based on surface evolution ideas, by modifying the Euclidean area in this case by a function which depends on the salient features which we wish to capture. In order to do this, we will need to set up some notation. Let
S
[O,
11
x
[0,1]
R3
enote a compact em bedded surface with (local) coordinates
U,
.).
Let
H
denote the mean curvature and he inward unit normal. We set
as
s,
=
.
s,
=
dzs
’
aV
Then the infinitesimal area on
S
is
given by
dS
=
I~S,,l~z[~Sv112
S,,S,)2)’/2dudv
Let
4
R
+
R
be a positive differentiable function defined on some open subset of
R3.
The function
4(z, y,
z)
will play the role of the “stopping” function
4
given above in our snake model
(6,
7).
It is a beautiful classical fact that the gradient flow associated to the area functional for surfaces (i.e., the direction in which area is shrinking most rapidly) is given by
dS
Hd.
at
What we propose to do is to replace the Euclidean area by
a
modified area depending on
4
namely,
dS4
=
4dS.
For a family of surfaces (with parameter
t),
onsider the area functional Once again, an integration by parts argument shows that
at
=
4HS
V ,
(9)
8 2
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on October 6, 2008 at 21:38 from IEEE Xplore. Restrictions apply.
gives the direction in which
A+ t)
is shrinking most rapidly. The level set version of
9)
is given in terms of
@(XI
Yl
2,
>
by As before one may add
a
constant inflation term to the mean curvature to derive the model In the context of image processing, the term
q
de pends on the given
3D
image and is exactly analogous to the stopping term in
6,
7).
It is important to note that there is
a
very big difference between the
2D
and 3D models discussed here. Indeed, the geometric heat equation will shrink a simple closed curve to a round point without developing singularities, even if the ini tial curve is
nonconvez.
The geometric model
(2)
is based on this flow.
For
surfaces, it is wellknown that singularities may develop in the mean curvature flow
(8)
nonconvex smooth surfaces
[12].
(The classical ex ample is the dumbbell.) We should note however that the mean curvature flow does indeed shrink smooth compact convex surfaces to round “spherical” points. We should add that because of these problems, sev eral researchers have proposed replacing mean curva ture flow by flows which depend on the Gaussian cur vature
K.
Indeed. define
tc
=
max{K,
0).
Then Caselles and Sbert
[8]
have shown that the
affine invariant
pow
s
=sign(H)tc+ /4
N
at
will (smoothly) shrink rotationally symmetric com pact surfaces to ellipsoidal shaped points. (This has been proven in
[4]
in the convex case. See also
[2].)
Thus one could replace the mean curvature part by sign(H)~:/~ n
(11).
Another possibility would be to use
t i”
as
has been proposed in
[20].
See also
[as].
(Note that Chow
[9]
has shown that convex surfaces flowing under
K’/’
shrink to spherical points.) All these possible evolutions for 3D contours are now be ing explored. See also Section
5
below for a possible aternative related approach to
3D
segmentation.
5
Geodesic
Paths
Given that we are now looking at a Riemannian metric, it becomes natural to investigate its geodesics. It turns out that the geodesics appear
to
have a very concrete interpretation in this problem.
For
back ground on the problem of finding closed geodesics on manifolds in connection with curveshortening,
see
[lo,
11,
131.
It is therefore natural
to
investigate the geodesics of the conformally Euclidian metric considered in this paper; this will lead to an
ordinary differential equa tion
which can be used both for the segmentation and edge detection problem. We work in the plane once again with the stopping function
4
as
discussed in Section
3.
As
before we modify the Euclidean metric by taking
ds
=
4ds.
Indeed, setting
U
=
d2,
we find that the equation of geodesics takes the form
[lo]
1
1
2
,,
$C,,Vu)C,

IlCpll2Vu]
=
0.
(13)
Note that the tangential term
(C,,Vu)C,
can be re moved by change
of
parametrization. Define the “potential function”
42
V(C)
=
E

n,
where
E
is a certain constant which we describe below. Given this we claim that solutions
of
the oscillator type equation
c,,
+
VV(C)
=
0
(14)
can be reparametrized to give geodesics of the line element
Hs+.
This may be seen from the following calculation. Start with the equation
(13).
S‘
nce we have the first integral equation
(14)
can be written
as
which is precisely
(13)
up to tangential term. In terms of the image, what we want is to lo cate a potential valley. Therefore, an algorithm
us
ing geodesics might be
as
follows: run
a
geodesic with zero initial speed, and stop when its velocity starts to decrease. This should approximately give
a
point on the desired contour.
Of
course, one may want to add
a
stopping term too. Also, such a geodesic, if launched in the correct direction, should tend to
go
around
the desired objectthis might be useful to get an initial guess, and for segmentation.
8
13
Authorzedcensedusemtedto:GeoraInsttuteofTechnoo.DownoadedonOctober62008at21:38fromIEEEXore.Restrctonsa.
We should note that the above computation re mains valid in any number of space dimensions.
For
surfaces, these curves would swirl about the desired object. Since the equations are conservative, we are guaranteed that the curves will not wander too far away. Numerical calculations using this idea will be reported elsewhere.
6 Numerical Experiments
The implementations we have used in this paper are based on the level set evolution methods developed by OsherSethian
[21, 22, 25, 26, 273,
and the techniques in
1181.
We have been applying our methods to a number of medical images.
For
purposes of illustration, we will present two such images here. The first is an MRI noisy myocardial image. We have captured the chambers using an outward evolution (the “balloon” or “bubble” technique). The second image is an ul trasound image
of
a breast cyst whose contour we also find using our curve evolution methods.
7
Conclusions
In this paper, we presented
a
new snake methodol ogy derived by considering the curve shortening evolu tion relative to a conformally Euclidean metric. Thus the evolution is based on a “natural” energy function which is intimately related to the geometry of the im age. We are now in the process
of
extending these re sults in order to develop
3D
segmentation algorithms.
Acknowledgements
We would like to thank Todd Parrish of the Ra diology Department of the University of Minnesota for providing us with the MRI heart image, and Dr. James Greenleaf of the Mayo Clinic
for
providing us with the breast ultrasound image.
References
[l]
L. Alvarez,
F.
Guichard, P. L. Lions, and J. M. Morel, “Axiomes et equations fondamentales du traitement d‘images,”
C. R. Acad. Sci. Paris
315
p.
135138, 1992. [2]
L. Alvarez,
F.
Guichard,
P.
L. Lions, and J.
M.
Morel, “Axioms and fundamental equations
of
image processing,” Report
9216,
CEREMADE, Universiti Paris Dauphine,
1992. [3]
L.
Alvarez,
F.
Guichard, P.
L.
Lions, and J. M. Morel, “Axiomatisation et nouveaux operateurs de la morphologie mathematique,”
C. R. Acad. Sci. Paris
315
p.
265268, 1992.
[4]
B.
Andrews, “Contraction of convex hypersur faces by their affine normal,” submitted
for
pub lication,
1994. [5]
A.
Blake and A. Yuille,
Active Vision,
MIT Press, Cambridge, Mass.,
1992. [6]
V. Caselles,
F.
Catte,
T.
Coll, and
F.
Dibos, “A geometric model
for
active contours in image pro cessing,” Technical Report
92 10,
CEREM ADE, UniversitC Paris Dauphine,
1992. [7]
V.
Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,”
Proceeding
of
the
1995
ICCV.
[8]
V. Caselles and C. Sbert, “What is the best causal scalespace for
3D
images?,” Technical Report, Department of Math. and Comp. Sciences, Uni versity of Illes Balears,
07071
Palma de Mallorca, Spain, March
1994. [9]
B. Chow, “Deforming convex hypersurfaces by the nth root of the Gaussian curvature,”
J.
Dif
ferential Geometry
22,
pp.
117138, 1985.
[lo]
M.
P.
Do
Carmo,
Riemannian Geometry,
PrenticeHall, Inc. New Jersey,
1992.
1111
M. Gage and R.
S.
Hamilton, “The heat equation
J.
Differential
hrinking convex plane curves,”
Geometry
23,
pp.
6996, 1986. [12]
M. Grayson,
“A
short note on the evolution of
Duke Math.
surface by its mean curvature,”
Journal
58
p.
555558, 1989. [13]
M.
Grayson, “The heat equation shrinks embed ded plane curves to round points,’’
J.
Diflerential Geometry
26,
pp.
285314, 1987.
[14]
M.
Kass,
A.
Witkin, and D. Terzopoulos, “Snakes: active contour models,”
Ini. Journal
of
Computer Vision
1
p.
321331, 1987. [15]
S.
Kichenassamy, A. Kumar, P. Olver, A. Tan nenbaum, A. Yezzi, “Conformal curvature flows: from phase transitions to active vision,” to ap pear in
Archive
of
Rational Mechanics and Anal ysis,
1995. [16]
B.
B.
Kimia, A. Tannenbaum, and
S.
W.
Zucker, “Toward a computational theory of shape: An overview”,
Lecture Notes in Computer Science
427,
pp.
402407,
SpringerVerlag, New York,
1990.
8
14
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on October 6, 2008 at 21:38 from IEEE Xplore. Restrictions apply.