Abstract
This paper is concerned with the simulation of the Partial Differential Equation (PDE) driven evolution of a closed surface by means of an implicit representation. In most applications, the natural choice for the implicit representation is the signed distance function to the closed surface. Osher and Sethian propose to evolve the distance function with a Hamilton-Jacobi equation. Unfortunately the solution to this equation is not a distance function. As a consequence, the practical application of the level set method is plagued with such questions as when do we have to “reinitialize” the distance function? How do we “reinitialize” the distance function? Etc... which reveal a disagreement between the theory and its implementation. This paper proposes an alternative to the use of Hamilton-Jacobi equations which eliminates this contradiction: in our method the implicit representation always remains a distance function by construction, and the implementation does not differ from the theory anymore. This is achieved through the introduction of a new equation. Besides its theoretical advantages, the proposed method also has several practical advantages which we demonstrate in three applications: (i) the segmentation of the human cortex surfaces from MRI images using two coupled surfaces [27], (ii) the construction of a hierarchy of Euclidean skeletons of a 3D surface, (iii) the reconstruction of the surface of 3D objects through stereo [13].
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
D. Adalsteinsson and J. A. Sethian. A Fast Level Set Method for Propagating Interfaces. Journal of Computational Physics, 118(2):269–277, 1995.
D. Adalsteinsson and J. A. Sethian. The fast construction of extension velocities in level set methods. Journal of Computational Physics, 1(148):2–22, 1999.
L. Ambrosio and C. Mantegazza. Curvature and distance function from a manifold. J. Geom. Anal., 1996. To appear.
V. I. Arnold. Geometrical Methods in the Theory of Ordinary Differential Equations. Springer-Verlag New York Inc., 1983.
G. Barles, H.M. Soner, and P.E. Souganidis. Front propagation and phase field theory. SIAM J. Control and Optimization, 31(2):439–469, March 1993.
Harry Blum and Roger N. Nagel. Shape description using weighted symmetric axis features. Pattern Recog., 10:167–180, 1978.
V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. In Proceedings of the 5th International Conference on Computer Vision, pages 694–699, Boston, MA, June 1995. IEEE Computer Society Press.
V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. The International Journal of Computer Vision, 22(1):61–79, 1997.
Y.G. Chen, Y. Giga, and S. Goto. Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations. J. Differential Geometry, 33:749–786, 1991.
David L. Chopp. Computing minimal surfaces via level set curvature flow. Journal of Computational Physics, 106:77–91, 1993.
Frédéric Devernay. Vision stéréoscopique et propriétés différentielles des surfaces. PhD thesis, École Polytechnique, Palaiseau, France, February 97.
L.C. Evans and J. Spruck. Motion of level sets by mean curvature: I. Journal of Differential Geometry, 33:635–681, 1991.
O. Faugeras and R. Keriven. Level set methods and the stereo problem. In Bart ter Haar Romeny, Luc Florack, Jan Koenderink, and Max Viergever, editors, Proc. of First International Conference on Scale-Space Theory in Computer Vision, volume 1252 of Lecture Notes in Computer Science, pages 272–283. Springer, 1997.
M. Gage and R.S. Hamilton. The heat equation shrinking convex plane curves. J. of Differential Geometry, 23:69–96, 1986.
M. Grayson. The heat equation shrinks embedded plane curves to round points. J. of Differential Geometry, 26:285–314, 1987.
M. Kass, A. Witkin, and D. Terzopoulos. SNAKES: Active contour models. The International Journal of Computer Vision, 1:321–332, January 1988.
S. Kichenassamy, A. Kumar, P. Olver, A. Tannenbaum, and A. Yezzi. Gradient flows and geometric active contour models. In Proceedings of the 5th International Conference on Computer Vision, Boston, MA, June 1995. IEEE Computer Society Press.
B. Kimia, A. R. Tannenbaum, and S. W. Zucker. Shapes, schoks and deformations i: The components of two-dimensional shape and the reaction-diffusion space. ijcv, 15:189–224, 1995.
G. Malandain and S. Fernández-Vidal. Euclidean skeletons. Image and Vision Computing, 16:317–327, 1998.
R. Malladi, J. A. Sethian, and B.C. Vemuri. Evolutionary fronts for topology-independent shape modeling and recovery. In J-O. Eklundh, editor, Proceedings of the 3rd European Conference on Computer Vision, volume 800 of Lecture Notes in Computer Science, Stockholm, Sweden, May 1994. Springer-Verlag.
R. Malladi, J. A. Sethian, and B.C. Vemuri. Shape modeling with front propagation: A level set approach. PAMI, 17(2):158–175, February 1995.
S. Osher and J. Sethian. Fronts propagating with curvature dependent speed: algorithms based on the Hamilton-Jacobi formulation. Journal of Computational Physics, 79:12–49, 1988.
Jean Serra. Image Analysis and Mathematical Morphology. Academic Press, London, 1982.
J. A. Sethian. Level Set Methods. Cambridge University Press, 1996.
J.A. Sethian and J. Strain. Crystal growth and dendritic solidification. Journal of Computational Physics, 98:231–253, 1992.
C. W. Shu and S. Osher. Efficient implementation of essentially non-oscillatory shock-capturing schemes, ii. Journal of Computational Physics, 83:32–78, 1989.
X. Zeng, L. H. Staib, R. T. Schultz, and J. S. Duncan. Volumetric layer segmentation using coupled surfaces propagation. In Proceedings of the International Conference on Computer Vision and Pattern Recognition, Santa Barbara, California, June 1998. IEEE Computer Society.
Hong-Kai Zhao, T. Chan, B. Merriman, and S. Osher. A variational level set approach to multiphase motion. Journal of Computational Physics, 127(0167):179–195, 1996.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gomes, J., Faugeras, O. (2000). Level Sets and Distance Functions. In: Computer Vision - ECCV 2000. ECCV 2000. Lecture Notes in Computer Science, vol 1842. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45054-8_38
Download citation
DOI: https://doi.org/10.1007/3-540-45054-8_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67685-0
Online ISBN: 978-3-540-45054-2
eBook Packages: Springer Book Archive