Skip to main content
SpringerLink
Log in

A fast level set based algorithm for topology-independent shape modeling

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. D. Adalsteinsson and J.A. Sethian, “A fast level set method for propagating interfaces”, to appear in Journal of Computational Physics, 1994.

  2. 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.

    Google Scholar 

  3. 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.

    Google Scholar 

  4. 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.

  5. A. Blake and A. Zisserman, Visual Reconstruction, MIT Press: Cambridge, MA.

  6. 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.

    Google Scholar 

  7. 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.

  8. D.L. Chopp, “Computing minimal surfaces via level set curvature flow,” Journal of Computational Physics, Vol. 106, pp. 77–91, 1993.

    Google Scholar 

  9. L.D. Cohen, “On active contour models and balloons,” Computer Vision, Graphics, and Image Processing, Vol. 53, No. 2, pp. 211–218, 1991.

    Google Scholar 

  10. 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.

  11. 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.

  12. M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, pp. 321–331, 1988.

  13. 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.

  14. 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.

  15. 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.

    Google Scholar 

  16. 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.

    Google Scholar 

  17. 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.

    Google Scholar 

  18. R. Malladi, “A Topology-independent shape modeling scheme,” Doctoral Dissertation, Dept. of CIS, University of Florida, Gainesville, December 1993.

  19. 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.

    Google Scholar 

  20. 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.

  21. 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.

    Google Scholar 

  22. N. Mayya and V.T. Rajan, “An efficient shape representation scheme using voronoi skeletons,” IBM Research Report, RC 19161 (83458), Sept. 1993.

  23. 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.

    Google Scholar 

  24. R. Samadani, “Changes in connectivity in active contour Models,” Proceedings of the Workshop on Visual Motion, Irvine, California, 1989, pp. 337–343.

  25. 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.

    Google Scholar 

  26. J.A. Sethian, “Curvature and the evolution of fronts,” Commun. in Mathematical Physics, Vol. 101, pp. 487–499, 1985.

    Google Scholar 

  27. J.A. Sethian, “Numerical algorithms for propagating interfaces: Hamilton-Jacobi equations and conservation laws,” Journal of Differential Geometry, Vol. 31, pp. 131–161, 1990.

    Google Scholar 

  28. J.A. Sethian and J. Strain, “Crystal growth and dendritic solidification,” Journal of Computational Physics, Vol. 98, pp. 231–253, 1992.

    Google Scholar 

  29. 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.

  30. R. Szeliski and D. Tonnesen, “Surface modeling with oriented particle systems,” Computer Graphics SIGGRAPH, Vol. 26, No. 2, pp. 185–194, 1992.

    Google Scholar 

  31. 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.

    Google Scholar 

  32. 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.

    Google Scholar 

  33. 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.

    Google Scholar 

  34. B.C. Vemuri and R. Malladi, “Surface griding with intrinsic parameters,” Pattern Recognition Letters, Vol. 13, No. 11, pp. 805–812, 1992.

    Google Scholar 

  35. 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.

    Google Scholar 

  36. 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.

    Google Scholar 

  37. 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.

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of California, 94720, Berkeley, CA

    Ravikanth Malladi & James A. Sethian

  2. Department of Computer & Information Sciences, University of Florida, 32611, Gainesville, FL

    Baba C. Vemuri

Authors
  1. Ravikanth Malladi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. James A. Sethian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Baba C. Vemuri
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Reprints 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

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00119843

Keywords

Search

Navigation