Gradient Flows and Geometric Active Contour Models


of 6
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Gradient Flows and Geometric Active Contour Models
  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 3-0 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 well-known 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 arc-length 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 3-D 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 DMS-9204192 and ECS- 9122106, by the Air Force Office of Scientific Research F49620-94-1-0058DEF, by the Army Research Office DAAH04-94-G-0054 and DAAH04-93-G-0332, and by Image Evolutions Limited. 2 Curve Shortening Flows The motivation for the equations underlying active geometric contours comes from Euclidean curve short- 810 0-8186-7042-8/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 scale-space 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) arc-length, 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 (grey-scale) 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 Osher-Sethian [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 arc-length 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 Osher-Sethian [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 3-D Active Contour Models In this section, we will discuss some possible geo- metric 3-D 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 3-D 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 2-D and 3-D 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 well-known that singularities may develop in the mean curvature flow (8) non-convex 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 3-D 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 curve-shortening, 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 object-this 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 Osher-Sethian [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. 135-138, 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. 265-268, 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 scale-space 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. 117-138, 1985. [lo] M. P. Do Carmo, Riemannian Geometry, Prentice-Hall, Inc. New Jersey, 1992. 1111 M. Gage and R. S. Hamilton, “The heat equation J. Differential hrinking convex plane curves,” Geometry 23, pp. 69-96, 1986. [12] M. Grayson, “A short note on the evolution of Duke Math. surface by its mean curvature,” Journal 58 p. 555-558, 1989. [13] M. Grayson, “The heat equation shrinks embed- ded plane curves to round points,’’ J. Diflerential Geometry 26, pp. 285-314, 1987. [14] M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: active contour models,” Ini. Journal of Computer Vision 1 p. 321-331, 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. 402-407, Springer-Verlag, 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.
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks