International Journal of Computer Vision22(1),61–79(1997)
c 1997Kluwer Academic Publishers.Manufacture
d in Th
e Netherlands.
Geodesic Active Contours
VICENT CASELLES
Department of Mathematics and Informatics,University of Illes Balears,07071Palma de Mallorca,Spain
dmivca0@ps.uib.es
RON KIMMEL
Department of Electrical Engineering,Technion,I.I.T.,Haifa32000,Israel
hnion.ac.il
GUILLERMO SAPIRO
Hewlett-Packard Labs,1501Page Mill Road,Palo Alto,CA94304
guille@hpl.hp
Received October17,1994;Revised February13,1995;Accepted July5,1995
Abstract.A novel scheme for the detection of object boundaries is presented.The technique is based on active contours evolving in time according to intrinsic geometric measures of the image.The evolving contours naturally split and merge,allowing the simultaneous detection of several objects and both interior and exterior boundaries. The proposed approach is based on the relation between active contours and the computation of geodesics or minimal distance curves.The minimal distance curve lays in a Riemannian space whose metric is defined by the image content.This geodesic approach for object segmentation allows to connect classical“snakes”based on energy minimization and geometric active contours based on the theory of curve evolution.Previous models of geometric active contours are improved,allowing stable boundary detection when their gradients suffer from large variations, including gaps.Formal results concerning existence,uniqueness,stability,and correctness of the evolution are presented as well.The scheme was implemented using an efficient algorithm for curve ev
olution.Experimental results of applying the scheme to real images including objects with holes and medical data imagery demonstrate its power.The results may be extended to3D object segmentation as well.
Keywords:dynamic contours,variational problems,differential geometry,Riemannian geometry,geodesics, curve evolution,topology free boundary detection
1.Introduction
Since original work by Kass et al.(1988),extensive research was done on“snakes”or active contour mo-dels for boundary detection.The classical approach is based on deforming an initial contour C0towards the boundary of the object to be detected.The deformation is obtained by trying to minimize a functional designed so that its(local)minimum is obtained at the boundary of the object.These active contours are examples of the general technique of matching deformable models to image data by means of energy minimization(Blake and Zisserman,1987;Terzopoulos et al.,1988).The energy functional is basically composed of two com-ponents,one controls the smoothness of the curve and another attracts the curve towards the boundary.This energy model is not capable of handling changes in the topology of the evolving contour when direct im-plementations are performed.Therefore,the topology of thefinal curve will be as the one of C0(the initial
62Caselles,Kimmel and Sapiro
curve),unless special procedures,many times heuris-tic,are implemented for detecting possible splitting and merging(Leitner and Cinquin,1991;McInerney and Terzopoulos,1995;Szeliski et al.,1993).This is a problem when an un-known number of objects must be simultaneously detected.This approach is also non-intrinsic,since the energy depends on the parametriza-tion of the curve and is not directly related to the objects geometry.As we show in this paper,a kind of“re-interpretation”of this model solves these problems. See for example(Malladi et al.,1995)for comments on other advantages and disadvantages of energy ap-proaches of deforming contours,as well as an extended literature on snakes.
Recently,novel geometric models of active contours were simultaneously proposed by Caselles et al.(1993) and by Malladi et al.(1994,1995,—).These models are based on the theory of curve evolution and geo-metricflows,which has received a large amount of attention from the image analysis community in recent years(Faugeras,1993;Kimia et al.,—;Kimmel and Bruckstein,1995;Kimmel et al.,1995,—;Kimmel and Sapiro,1995;Niessen et al.,1993;Romeny,1994; Sapiro et al.,1993,Sapiro and Tannenbaum,1993a,b, 1994a,b,1995).In these active contours models,the curve is propagating(deforming)by means of a ve-locity that contains two terms as well,one related to the regul
arity of the curve and the other shrinks or ex-pands it towards the boundary.The model is given by a geometricflow(PDE),based on mean curvature motion.This model is motivated by a curve evolution approach and not an energy minimization one.It allows automatic changes in the topology when implemented using the level-sets based numerical algorithm(Osher and Sethian,1988).Thereby,several objects can be detected simultaneously without previous knowledge of their exact number in the scene and without using special tracking procedures.
In this paper a particular case of the classical en-ergy snakes model is proved to be equivalent tofind-ing a geodesic curve in a Riemannian space with a metric derived from the image content.This means that in a certain framework,boundary detection can be considered equivalent tofinding a curve of mini-mal weighted length.This interpretation gives a new approach for boundary detection via active contours, based on geodesic or local minimal distance computa-tions.Then,assuming that this geodesic active contour is represented as the zero level-set of a3D function,the geodesic curve computation is reduced to a geometric flow that is similar to the one obtained in the curve evolution approaches mentioned above.However,this geodesicflow includes a new component in the curve velocity,based on image information,that improves those models.1The new velocity component allows us to accurately track boundaries with high variation in their gradient,including small gaps,a task that w
as dif-ficult to accomplish with the previous curve evolution models.We also show that the solution to the geodesic flow exists in the viscosity framework,and is unique and stable.Consistency of the model is presented as well,showing that the geodesic curve converges to the right solution in the case of ideal objects.A number of examples of real images,showing the above properties, are presented.
The approach here presented has the following main properties:1)Describes the connection between en-ergy and curve evolution approaches of active contours.
2)Presents active contours for object detection as a geodesic computation approach.3)Improves existing curve evolution models as a result of the geodesic for-mulation.4)Allows simultaneous detection of interior and exterior boundaries in several objects without spe-cial contour tracking procedures.5)Holds formal ex-istence,uniqueness,stability,and consistency results.
6)Does not require special stopping conditions.
In Section2we present the main result of the paper, the geodesic active contours.This section is divided in four parts:First,classical energy based snakes are revisited and commented.A particular case which will be helpful later is derived and justified.Then,the rela-tion between this energy snakes and geodesic curves is shown and the basics of the proposed active contours approach for boundary
detection is presented.In the third part,the level-sets technique for curve evolution is described,and the geodesic curveflow is incorpo-rated to this framework.The last part,2.4,presents further interpretation of the geodesic active contours approach from the boundary detection perspective and shows its relation to previous deformable models based on curve evolution.After the model description,the-oretical results concerning the proposed geodesicflow are given in Section3.Experimental results with the proposed approach are given in Section4followed by concluding remarks in Section5.
2.Geodesic Active Contours
In this section we discuss the connection between energy based active contours(snakes)and the com-putation of geodesics or minimal distance curves in a
Geodesic Active Contours65 of this minimization problem.The Maupertuis Princi-
ple of least action used to derive(5)presents a purely
geometric principle describing the orbits of the mini-
mizing paths(Born and Wolf,1986).In other words,
it is possible using the above theorem tofind the pro-
jection of the minimizing path of(2)in the(x,y,q)
space onto the(x,y)plane by solving an intrinsic prob-
lem.Observe that the parametrization along the path
is yet to be determined after its orbit is tracked.The
intrinsic problem offinding the projection of the mini-
mizing path depends on a single free parameter E0
incorporating the parametrization as well asλandα
(E0=E int−E ext=α|C (q)|2−λg(C(q))2).
The question to be asked is whether the problem
in hand should be regarded as the behavior of springs
and mass points leading to the non-intrinsic model(2).
We shall take one step further,moving from springs to
light rays,and use the following result from optics to
motivate the proposed model(Born and Wolf,1986;
Dubrovin et al.,1984):
Theorem2(Fermat’s Principle).In an isotropic
medium the paths taken by light rays in passing from a
point A to a point B are extrema corresponding to the
active下载traversal-time(as action).Such paths are geodesics
with respect to the new metric(i,j=1,2)
g i j=
1
c2
δi j.
c(X)in the above equation corresponds to the speed of light at X.Fermat’s Principle defines the Riemannian metric for light waves.We define c(X)=1/g(X) where“high speed of light”corresponds to the presence of an edge,while“low speed of light”corresponds to a non-edge area.The result is equivalent then to minimizing the intrinsic problem
1
g(|∇I(C(q))|)|C (q)|dq,(6)
which is the same formulation as in(5),having selected E0=0.
We shall return for a while to the energy model(2) to further explain the selection of E0=0from the point of view of object detection.As was explained before,in order to have a completely closed form for boundary detection via(5),we have to select E0.It was shown that selecting E0is equivalent tofixing the free parameters in(2)(i.e.,the parametrization andλ/α). Note that by Theorem1,the interpretation of the snakes model(2)for object detection as a geodesic computa-
tion is valid for any value of E0.The value of E0is
selected to be zero from now on,which means that
E int=E ext in(2).This selection simplifies the no-tation(see Appendix A),and clarifies the relation of
Theorem1and energy-snakes with(geometric)curve
evolution active contours that results form theorems
1and2.At an ideal edge,E ext in(2)is expected
to be zero,since|∇I|=∞and g(r)→0as r→∞.
Then,the ideal goal is to send the edges to the zeros
of g.Ideally we should try as well to send the inter-
nal energy to zero.Since images are not formed by
ideal edges,we choose to make equal contributions
of both energy components.This choice,which co-
incides with the one obtained from Fermat’s Principle
and as said before allows to show the connection with
curve evolution active contours,is also consistent with
the fact that when looking for an edge,we may travel
along the curve with arbitrarily slow velocity(given by
the parametrization q,see equations obtained with the
above change of parametrization).More comments on
different selections of E0,as well as formulas corre-
sponding to E0=0,are given in Appendix A. Therefore,with E0=0,and g i j=2mλg(|∇I(C)|)2δi j,Eq.(4)becomes
Min
1
√
2mλg(|∇I(C(q)|)|C (q)|dq.(7)
Since the parameters above are constants,without loss of generality we can set now2λm=1to obtain
Min
1
g(|∇I(C(q)|)|C (q)|dq.(8)
We have transformed the problem of minimizing (2)into a problem of geodesic computation in a Riemannian space,according to a new metric.
Let us,based on the above theory,give the above expression a further geodesic curve interpretation from a slightly different perspective.The Euclidean length of the curve C is given by
L:=
|C (q)|dq=
ds,(9)
where ds is the Euclidean arc-length(or Euclidean met-ric).It is easy to prove that theflow
C t=κ N(10)

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。