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 retains some of the attractive features of existing methods, and overcomes some of their limitations. Our technique can be applied to model arbitrarily complex shapes, which include shapes with significant protrusions, and to situations where no a priori assumption 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 Sethian to model propagating solid/liquid interfaces with curvature-dependent speeds. The interface (front) is a closed, nonintersecting, hypersurface flowing along its gradient field with constant speed or a speed that depends on the curvature. It is moved by solving a “Hamilton-Jacobi” type equation written for a function in which the interface is a particular level set. A speed term synthesized from the image is used to stop the interface in the vicinity of object boundaries. The resulting equation of motion is solved by employing entropy-satisfying upwind finite difference schemes. We also introduce a new algorithm for rapid advancement of the front using what we call a narrow-band update scheme. The efficacy of the scheme is demonstrated with numerical experiments on low contrast medical images.
Similar content being viewed by others
References
D. Adalsteinsson and J.A. Sethian, “A fast level set method for propagating interfaces”, to appear in Journal of Computational Physics, 1994.
A.A. Amini, T.E. Weymouth, and R.C. Jain, “Using dynamic programming for solving variational problems in vision,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 12, No. 9, pp. 855–867, 1990.
R.M. Bolle and B.C. Vemuri, “On three-dimensional surface reconstruction methods,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI 13, No. 1, pp. 1–13, 1991.
T.E. Boult and J.R. Kender, “Visual surface reconstruction using sparse depth data,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, June 1986, pp. 68–76.
A. Blake and A. Zisserman, Visual Reconstruction, MIT Press: Cambridge, MA.
H. Blum, “transformation for extracting new descriptors of shape,” Models for the Perception of Speech and Visual Form W. Wathen-Dunn (Ed.), MIT Press: Cambridge, MA, 1967.
V. Caselles, F. Catte, T. Coll, and F. Dibos, “A geometric model for active contours in image processing,” Internal report no. 9210, CEREMADE. Université de Paris-Dauphine, France.
D.L. Chopp, “Computing minimal surfaces via level set curvature flow,” Journal of Computational Physics, Vol. 106, pp. 77–91, 1993.
L.D. Cohen, “On active contour models and balloons,” Computer Vision, Graphics, and Image Processing, Vol. 53, No. 2, pp. 211–218, 1991.
H. Delingette, M. Hebert, and K. Ikeuchi, “Shape representation and image segmentation using deformable models,” in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, Maui Hawaii, June 1991, pp. 467–472.
W.T. Freeman and E.H. Adelson, “Steerable filters for early vision, image analysis, and wavelet decomposition,” in Proceedings of ICCV, Osaka, Japan, 1990, pp. 406–415.
M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, pp. 321–331, 1988.
B.B. Kimia, A.R. Tannenbaum, and S.W. Zucker, “Toward a computational theory of shape: An overview,” in Proceedings of ECCV, Antibes, France, 1990.
B.B. Kimia, A.R. Tannenbaum, and S.W. Zucker, “Shapes, shocks, and deformations I: The components of shape and reaction-diffusion space,” to appear in International Journal of Computer Vision, 1992.
D.T. Lee, “Medial axis transformation of a planar shape,” IEEE Trans. Patt. Anal. Machine Intell. Vol. PAMI-4, No. 4, pp. 363–369, 1982.
D. Lee and T. Pavlidis, “One-dimensional regularization with discontinuities,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-10, pp. 822–829, 1986.
F. Leymarie and M.D. Levine, “Simulating the grass-fire transform using an active contour model,” IEEE Trans. Patt. Anal. Machine Intell., Vol. PAMI-14, No. 1, pp. 56–75, 1992.
R. Malladi, “A Topology-independent shape modeling scheme,” Doctoral Dissertation, Dept. of CIS, University of Florida, Gainesville, December 1993.
R. Malladi and J.A. Sethian, “A unifiedframework for shape segmentation, representation, and recognition,” Report LBL-36069, Lawrence Berkeley Laboratory, University of California, Berkeley, Aug. 1994, submitted for publication CVGIP—Image Understanding.
R. Malladi, J.A.. Sethian, and B.C. Vemuri, “Evolutionary fronts for topology-independent shape modeling and recovery,” in Proceedings of Third European Conference on Computer Vision, Stockholm, Sweden, May 1994, LNCS Vol. 800, pp. 3–13.
R. Malladi, J.A. Sethian, and B.C. Vemuri, “Shape modeling with front propagation: A level set approach,” Center for Pure and Applied Mathematics, Report PAM-589, Univ. of California, Berkeley, August 1993, to appear in IEEE Trans. PAMI.
N. Mayya and V.T. Rajan, “An efficient shape representation scheme using voronoi skeletons,” IBM Research Report, RC 19161 (83458), Sept. 1993.
S. Osher and J.A. Sethian, “Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulation,” Journal of Computational Physics, Vol. 79, pp. 12–49, 1988.
R. Samadani, “Changes in connectivity in active contour Models,” Proceedings of the Workshop on Visual Motion, Irvine, California, 1989, pp. 337–343.
L.L. Schumaker, “Fitting surfaces to scattered data,” in Approximation Theory II, G.G. Lorentz, C.K. Chui, and L.L. Schumaker (Eds.), Academic Press: New York, pp. 203–267, 1976.
J.A. Sethian, “Curvature and the evolution of fronts,” Commun. in Mathematical Physics, Vol. 101, pp. 487–499, 1985.
J.A. Sethian, “Numerical algorithms for propagating interfaces: Hamilton-Jacobi equations and conservation laws,” Journal of Differential Geometry, Vol. 31, pp. 131–161, 1990.
J.A. Sethian and J. Strain, “Crystal growth and dendritic solidification,” Journal of Computational Physics, Vol. 98, pp. 231–253, 1992.
M. Sussman, P. Smereka, and S. Osher, “A level set approach for computing solutions to incompressible two-phase flow,” UCLA CAM Report 93-18, 1993.
R. Szeliski and D. Tonnesen, “Surface modeling with oriented particle systems,” Computer Graphics SIGGRAPH, Vol. 26, No. 2, pp. 185–194, 1992.
D. Terzopoulos, “Regularization of inverse visual problems involving discontinuities,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No. 2, pp. 413–424, 1986.
D. Terzopoulos, A. Witkin, and M. Kass, “Constraints on deformable models: Recovering 3D shape and nonrigid motion,” Artificial Intelligence, Vol. 36, pp. 91–123, 1988.
D. Terzopoulos, “The computation of visible surface representations,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, Vol. 10, pp. 417–438, 1988.
B.C. Vemuri and R. Malladi, “Surface griding with intrinsic parameters,” Pattern Recognition Letters, Vol. 13, No. 11, pp. 805–812, 1992.
B.C. Vemuri and R. Malladi, “Constructing intrinsic parameters with active models for invariant surface reconstruction,” IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 15, No. 7, pp. 668–681, 1993.
B.C. Vemuri, A. Mitiche, and J.K. Aggarwal, “Curvature-based representation of objects from range data,” Int. Journal of Image and Vision Computing, Vol. 4, pp. 107–114, 1986.
Y.F. Wang and J.F. Wang, “Surface reconstruction using deformable models with interior and boundary constraints,” in Proceedings of ICCV, Osaka, Japan, 1990, pp. 300–303.
Author information
Authors and Affiliations
Additional information
Supported in part by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, U.S. Dept. of Energy under Contract DE-AC03-76SD00098 and by the NSF ARPA under grant DMS-8919074.
Supported in part by NSF grant ECS-9210648.
Rights and permissions
About this article
Cite this article
Malladi, R., Sethian, J.A. & Vemuri, B.C. A fast level set based algorithm for topology-independent shape modeling. J Math Imaging Vis 6, 269–289 (1996). https://doi.org/10.1007/BF00119843
Issue Date:
DOI: https://doi.org/10.1007/BF00119843