158 IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 17, NO. 2, FEBRUARY 1995 Shape Modeling with Front Propagation: A Level Set Approach Ravikanth Malladi. James A Sethian, and Baba C. Vemuri Abstract - Shape modeling is an important constituent of computer vision as well as computer graphics research. Shape models aid the tasks of object representation and recognition. This paper presents a new approach to shape modeling which re- tains some of the attractive features of existing methods and over- comes some of their llmltatlons. Our techniques can be applied to model arbitrarily complex shapes, which include shapes with signiikant protrusions, and to situations where no a priori as- sumption about the object’s topology is made. A single instance of our model, when presented with an image having more than one object of interest, has the ability to split freely to represent each object. This method is based on the ideas developed by Osher and Sethlan to model propagating solid/liquid interfaces with curva- ture-dependent speeds. The interface (front) is a closed, noninter- secting, hypersurface flowing along its gradient field with con- stant speed or a speed that depends on the curvature. It is moved by solving a “Hamilton-Jacobi” type equation written for a func- tion in which the interface is a particular level set. A speed term synthesized from the image is used to stop the interface in the vi- cinity of object boundaries. The resulting equation of motion is solved by employing entropy-satisfying upwind finite difference schemes. We present a variety of ways of computing evolving front, including narrow bands, reinltlalizations, and different stopping criteria. The efficacy of the scheme is demonstrated with numerical experiments on some synthesized images and some low contrast medical images. Index Terms - Shape modeling, shape recovery, interface mo- tion, level sets, hyperbolic conservation laws, Hamilton-Jacobi equation, entropy condition. I. INTRODUCTION I N this paper, we describe a modeling technique based on a level set approach for recovering shapes of objects in two and three dimensions from various types of image data. The modeling technique may be viewed as a form of active model- ing such as “snakes” [15] and deformable surfaces [34] since, the model which consists of a moving front, may be molded into any desired shape by externally applied halting criteria synthesized from the image data. The “snakes” or deformable surfaces may be viewed as Lagrangian geometric formulations Manuscript received May 17, 1993; revised June 21, 1994. R. Malladi’s and J. Sethian’s research supported in part by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, US Dept. of Energy under Contract DE-AC03-76SDOOO98 and by the NSF ARPA under grant DMS-8919074. B. C. Vemuri’s work sponsored in part by NSF grant ECS-9210648. R. Malladi and J. Sethian are with Lawrence Berkeley Laboratory and De- partment of Mathematics, University of California, Berkeley, CA 94720 USA. B. Vemuri is with the Department of Computer and Information Sci- ences, University of Florida, Gainesville, FL 32611 USA. IEEECS Log Number P95015. wherein the boundary of the model is represented in a parametric form. These parameterized boundary representa- tions will encounter difficulties when the dynamic model em- bedded in a noisy data set is expanding/shrinking along its normal field [lo] and sharp corners or cusps develop or pieces of the boundary intersect. By exploiting recent advances in interface techniques, our modeling technique avoids this La- grangian geometric view and instead capitalizes on a related initial value partial differential equation. In this setting, several advantages are apparent, including the ability to evolve the model in the presence of sharp corners, cusps and changes in topology, model shapes with significant protrusions and holes in a seamless fashion, and extension to three dimensions in an extremely straightforward way. A. Background An important goal of computational vision is to recover the shapes of objects in 2D and 3D from various types of visual data. One way to achieve this goal is via model-based tech- niques. Broadly speaking, these techniques involve the use of a model whose boundary representation is matched to the image to recover the object of interest. These models can either be rigid, such as correlation-based template matching techniques, or nonrigid, as those used in dynamic model fitting techniques. Shape recovery from raw data typically precedes its sym- bolic representation, Shape models are expected to aid the re- covery of detailed structure from noisy data using only the weakest of the possible assumptions about the observed shape. To this end, several variational shape reconstruction methods have been proposed and there is abundant literature on the same (see [4], [27], [35], [38], [17] and references therein). Generalized spline models with continuity constraints are well suited for fulfilling the goals of shape recovery (see [6], [331). Generalized splines are the key ingredient of the dynamic shape modeling paradigm introduced to vision literature by Kass et al [ 151. Incorporating dynamics into shape modeling enables the creation of realistic animation for computer graphics applications and for tracking moving objects in com- puter vision. Following the advent of the dynamic shape modeling paradigm [ 151, [34], considerable research followed, with numerous application specific modifications to the model- ing primitives, and external forces derived from data con- straints [39], [18], [ll], [24], [36], [37]. The final recovered shape in these schemes can depend on an initial guess which is reasonably close to the desired shape. One solution to this problem in the one-dimensional case has 0162~8828/95$04OO 0 1995 IEEEMALLADI, SETHIAN, AND VEMURI: SHAPE MODELING WITH FRONT PROPAGATION: A LEVEL SET APPROACH 159 (a) CT image (b) DSA image (c) Shapes