The Vector Distance Functions | International Journal of Computer Vision Skip to main content
Springer Nature Link
Log in

The Vector Distance Functions

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

We present a novel method for representing and evolving objects of arbitrary dimension. The method, called the Vector Distance Function (VDF) method, uses the vector that connects any point in space to its closest point on the object. It can deal with smooth manifolds with and without boundaries and with shapes of different dimensions. It can be used to evolve such objects according to a variety of motions, including mean curvature. If discontinuous velocity fields are allowed the dimension of the objects can change. The evolution method that we propose guarantees that we stay in the class of VDF's and therefore that the intrinsic properties of the underlying shapes such as their dimension, curvatures can be read off easily from the VDF and its spatial derivatives at each time instant. The main disadvantage of the method is its redundancy: the size of the representation is always that of the ambient space even though the object we are representing may be of a much lower dimension. This disadvantage is also one of its strengths since it buys us flexibility.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Adalsteinsson, D. and Sethian, J.A. 1995. A fast level set method for propagating interfaces. Journal of Computational Physics, 118(2):269–277.

    Google Scholar 

  • Adalsteinsson, D. and Sethian, J.A. 1999. The fast construction of extension velocities in level set methods. Journal of Computational Physics, 1(148):2–22.

    Google Scholar 

  • Ambrosio, L. and Mantegazza, C. 1996. Curvature and distance function from a manifold. J. Geom. Anal., to appear.

  • Ambrosio, L. and Soner, H.M. 1996. Level set approach to mean curvature flowin arbitrary codimension. J. of Diff. Geom., 43:693– 737.

    Google Scholar 

  • Arnold, V. 1973. Ordinary Differential Equations. MIT Press.

  • Arnold, V.I. 1983. Geometrical Methods in the Theory of Ordinary Differential Equations. Springer-Verlag: New York.

    Google Scholar 

  • Barles, G. 1994. DeSolutions de viscosit´e des ´equations de Hamilton-Jacobi. Springer-Verlag: Berlin.

    Google Scholar 

  • Barles, G., Soner, H., and Souganidis, P. 1993. Front propagation and phase field theory. SIAM J. Control and Optimization, 31(2):439– 469.

    Google Scholar 

  • Bertalmio, M., Sapiro, G., and Randall, G. 1999. Region tacking on surfaces deforming via level-sets methods. In Scale-Space Theories in Computer Vision,M. Nielsen, P. Johansen, O. Olsen, and J. Weickert (Eds.),: vol. 1682 of Lecture Notes in Computer Science. Springer: Berlin, pp. 58–69.

    Google Scholar 

  • Blake, A. and Isard, M. 1998. Active Contours. Springer-Verlag.

  • Burchard, P., Cheng, L.-T., Merriman, B., and Osher, S. 2000. Motion of curves in three spatial dimensions using a level set approach. Technical Report, Department of Mathematics, University of California Los Angeles.

  • Caselles, V. and Coll, B. 1996. Snakes in movement. SIAM Journal on Numerical Analysis, 33:2445–2456.

    Google Scholar 

  • Caselles, V., Kimmel, R., and Sapiro, G. 1995. Geodesic active contours. In Proceedings of the 5th International Conference on Computer Vision, Boston, MA, I.C.S. Press (Ed.), pp. 694–699.

  • Caselles, V., Kimmel, R., and Sapiro, G. 1997a. Geodesic active contours. IJCV, 22(1):61–79.

    Google Scholar 

  • Caselles, V., Kimmel, R., Sapiro, G., and Sbert, C. 1996. 3D active contours. In Images,Wavelets and PDEs, M.-O. Berger, R. Deriche, I. Herlin, J. Jaffre, and J.-M. Morel (Eds.), vol. 219 of Lecture Notes in Control and Information Sciences. Springer: Berlin, pp. 43–49.

    Google Scholar 

  • Caselles, V., Kimmel, R., Sapiro, G., and Sbert, C. 1997b. Minimal surfaces based object segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9(4):394–398.

    Google Scholar 

  • Chen, Y., Giga, Y., and Goto, S. 1991. Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations. J. Differential Geometry, 33:749–786.

    Google Scholar 

  • Chopp, D.L. 1993. Computing minimal surfaces via level set curvature flow. Journal of Computational Physics, 106:77–91.

    Google Scholar 

  • Cipolla, R. and Giblin, P. 2000. Visual Motion of Curves and Surfaces. Cambridge University Press: Cambridge, UK.

    Google Scholar 

  • Crandall, M., Ishii, H., and Lions, P. 1992. User's guide to viscosity solutions of second order partial differential equations. Bull. Amer. Soc., 27:1–67.

    Google Scholar 

  • DoCarmo, M.P. 1976. Differential Geometry of Curves and Surfaces. Prentice-Hall: Englewood cliffs, NJ.

    Google Scholar 

  • DoCarmo, M.P. 1992. Riemannian Geometry. Birkhäuser: Boston, MA.

    Google Scholar 

  • Epstein, C. and Gage, M. 1987. The curve shortening flow. In Wave Motion: Theory, Modelling and Computation, A. Chorin, A. Majda, and P. Lax (Eds.), Springer-Verlag.

  • Evans, L. 1998. Partial Differential Equations, vol. 19 of Graduate Studies in Mathematics. American Mathematical Society: Providence, RI.

  • Evans, L. and Spruck, J. 1991. Motion of level sets by mean curvature: I. Journal of Differential Geometry, 33:635–681.

    Google Scholar 

  • Faugeras, O. and Keriven, R. 1998. Variational principles, surface evolution, PDE's, level set methods and the stereo problem. IEEE Transactions on Image Processing, 7(3):336–344.

    Google Scholar 

  • Gage, M. 1984. Curve shortening makes convex curves circular. Invent. Math., 76:357–364.

    Google Scholar 

  • Gage, M. and Hamilton, R. 1986. The heat equation shrinking convex plane curves. J. of Differential Geometry, 23:69–96.

    Google Scholar 

  • Gomes, J. and Faugeras, O. 1999. Reconciling distance functions and level sets. In Scale-Space Theories in Computer Vision, M. Nielsen, P. Johansen, O. Olsen, and J. Weickert (Eds.), vol. 1682 of Lecture Notes in Computer Science. Springer Verlag: Berlin, pp. 70–81.

  • Gomes, J. and Faugeras, O. 2000a. Reconciling distance functions and level sets. Journal of Visual Communication and Image Representation, 11:209–223.

    Google Scholar 

  • Gomes, J. and Faugeras, O. 2000b. Shape representation as the intersection of n?k hypersurfaces. Technical Report 4011, INRIA.

  • Grayson, M. 1987. The heat equation shrinks embedded plane curves to round points. J. of Differential Geometry, 26:285–314.

    Google Scholar 

  • Grayson, M. 1989.Ashort note on the evolution of surfaces via mean curvature. Duke Math J., pp. 555–558. Proof that the dumbell can split in 2 under mean curvature motion.

  • Kass, M., Witkin, A., and Terzopoulos, D. 1988. SNAKES: Active contour models. The International Journal of Computer Vision, 1:321–332.

    Google Scholar 

  • Kichenassamy, S., Kumar, A., Olver, P., Tannenbaum, A., and Yezzi, A. 1995. Gradient flows and geometric active contour models. In Proceedings of the 5th International Conference on Computer Vision, Boston, MA, I.C.S. Press (Ed.).

  • Kimia, B., Tannenbaum, A.R., and Zucker, S.W. 1995. Shapes, schoks and deformations I: The components of two-dimensional shape and the reaction-diffusion space. ijcv, 15:189–224.

    Google Scholar 

  • Kimmel, R. 1997. The geodesic curvature flow. Graphical Models and Image Processing, 60(2):112–124.

    Google Scholar 

  • Koenderink, J.J. 1990. Solid Shape. MIT Press: Cambridge, MA.

    Google Scholar 

  • Lorigo, L., Faugeras, O., Grimson, W., Keriven, R., Kikinis, R., and Westin, C.-F. 1999. Co-dimension 2 geodesic active contours for MRA segmentation. In Proc. Int'l Conf. Information Processing in Medical Imaging, pp. 126–139.

  • Malladi, R., Sethian, J.A., and Vemuri, B. 1994. Evolutionary fronts for topology-independent shape modeling and recovery. In Proceedings of the 3rd European Conference on Computer Vision. J.-O. Eklundh (Ed.), vol. 800 of Lecture Notes in Computer Science, Stockholm, Sweden. Springer-Verlag: Berlin.

  • Montagnat, J., Delingette, H., Scapel, N., and Ayache, N. 2000. Representation, shape, topology and evolution of deformable surfaces. Application to 3D medical image segmentation. Technical Report 3954, INRIA.

  • Osher, S. and Sethian, J. 1988. Fronts propagating with curvature dependent speed: Algorithms based on the Hamilton-Jacobi formulation. Journal of Computational Physics, 79:12–49.

    Google Scholar 

  • Paragios, N. and Deriche, R. 2000. Geodesic active contours and level sets for the detection and tracking of moving objects. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22:266– 280.

    Google Scholar 

  • Press, I.C.S. (Ed.). 1995. Proceedings of the 5th International Conference on Computer Vision, Boston, MA.

  • Ruuth, S., Merriman, B., and Osher, S. 1999. A fixed grid method for capturing the motion of self-intersecting interfaces and related PDEs. Technical Report 99-22, UCLA Computational and Applied Mathematics Reports.

  • Ruuth, S.J., Merriman, B., Xin, J., and Osher, S. 1998. Diffusiongenerated motion by mean curvature for filaments. Technical Report 98-47, UCLA Computational and Applied Mathematics Reports.

  • Sapiro, G. and Tannenbaum, A. 1994. On affine plane curve evolution. Journal of Functional Analysis, 119(1):79–120.

    Google Scholar 

  • Sethian, J. 1990. Recent numerical algorithms for hypersurfaces moving with curvature-dependent speed: Hamilton-Jacobi equations and conservation laws. J. Differential Geometry, 31:131–136.

    Google Scholar 

  • Sethian, J.A. 1996. A fast marching level set method for monotonically advancing fronts. Proc. Nat. Ac. Science, 93:1591– 1694.

    Google Scholar 

  • Siddiqi, K., Shokoufandeh, A., Dickinson, S.J., and Zucker, S.W. 1999. Shock graphs and shape matching. The International Journal of Computer Vision, 35(1):13–32.

    Google Scholar 

  • Sochen, N., Kimmel, R., and Malladi, R. 1998. A geometrical framework for low level vision. IEEE Trans. on Image Processing, Special Issue on PDE based Image Processing, 7(3):310–318.

    Google Scholar 

  • Spivak, M. 1979. A Comprehensive Introduction to Differential Geometry, vols. I–V, 2nd edn. Publish or Perish: Berkeley, CA.

  • Steinhoff, J., Fan, M., and Wang, L. 2000.AnewEulerian method for the computation of propagating short acoustic and electromagnetic pulses. Journal of Computational Physics, 157:683–706.

    Google Scholar 

  • Tek, H. and Kimia, B.B. 1995. Image segmentation by reactiondiffusion bubbles. In Proceedings of the 5th International Conference of Computer Vision, Boston, MA, I.C.S. Press (Ed.).

  • Terzopoulos, D., Witkin, A., and Kass, M. 1988. Constraints on deformable models: Recovering 3D shape and nonrigid motion. Artificial Intelligence, 36(1):91–123.

    Google Scholar 

  • Tsitsiklis, J.N. 1995. Efficient algorithms for globally optimal trajectories. IEEE Transactions on Automatic Control, 40(9):1528– 1538.

    Google Scholar 

  • Zhao, H.-K., Chan, T., Merriman, B., and Osher, S. 1996. A variational level set approach to multiphase motion. Journal of Computational Physics, 127(0167):179–195.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. I.B.M. Watson Research Center, New York, USA

    José Gomes

  2. I.N.R.I.A. Sophia Antipolis, France, M.I.T., Cambridge, MA, USA

    Olivier Faugeras

Authors
  1. José Gomes
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Olivier Faugeras
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gomes, J., Faugeras, O. The Vector Distance Functions. International Journal of Computer Vision 52, 161–187 (2003). https://doi.org/10.1023/A:1022956108418

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022956108418

Search

Navigation