Abstract
The eikonal equation and variants of it are of significant interest for problems in computer vision and image processing. It is the basis for continuous versions of mathematical morphology, stereo, shape-from-shading and for recent dynamic theories of shape. Its numerical simulation can be delicate, owing to the formation of singularities in the evolving front and is typically based on level set methods. However, there are more classical approaches rooted in Hamiltonian physics which have yet to be widely used by the computer vision community. In this paper we review the Hamiltonian formulation, which offers specific advantages when it comes to the detection of singularities or shocks. We specialize to the case of Blum's grassfire flow and measure the average outward flux of the vector field that underlies the Hamiltonian system. This measure has very different limiting behaviors depending upon whether the region over which it is computed shrinks to a singular point or a non-singular one. Hence, it is an effective way to distinguish between these two cases. We combine the flux measurement with a homotopy preserving thinning process applied in a discrete lattice. This leads to a robust and accurate algorithm for computing skeletons in 2D as well as 3D, which has low computational complexity. We illustrate the approach with several computational examples.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Arcelli, C. and diBaja, G.S. 1985. Awidth-independent fast thinning algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 7(4):463–474.
Arcelli, C. and di Baja, G.S. 1992. Ridge points in euclidean distance maps. Pattern Recognition Letters, 13(4):237–243.
Arnold, V.I. 1989. Mathematical Methods of Classical Mechanics, 2nd edn. Springer-Verlag: Berlin.
Bertrand, G. 1995. A parallel thinning algorithm for medial surfaces. Pattern Recognition Letters, 16:979–986.
Blum, H. 1973. Biological shape and visual science. Journal of Theoretical Biology, 38:205–287.
Borgefors, G. 1984. Distance transformations in arbitrary dimensions. Computer Vision Graphics and Image Processing, 27:321–345.
Borgefors, G., Nystrom, I., and Baja, G.S.D. 1998. Skeletonizing volume objects part II: From surface to curve skeleton. In International Workshop on Syntatical and Structural Pattern Recognition, pp. 220–229.
Borgefors, G., Nystrom, I., and Baja, G.S.D. 1999. Computing skeletons in three dimensions. Pattern Recognition, 32:1225–1236.
Brockett, R. and Maragos, P. 1992. Evolution equations for continuous-scale morphology. In Proceedings of the IEEE Conference on Acoustics, Speech and Signal Processing, San Francisco, CA.
Bruss, A.R. 1989. The eikonal equation: Some results applicable to computer vision. In Shape From Shading, B.K.P. Horn and M.J. Brooks (Eds.). MIT Press: Cambridge, MA, pp. 69–87.
Caselles, V., Morel, J.-M., Sapiro, G., and Tannenbaum, A. (Eds.). 1998. IEEE Transactions on Image Processing, Special Issue on PDEs and Geometry-Driven Diffusion in Image Processing and Analysis.
Crandall, M.G., Ishii, H., and Lions, P.-L. 1992. User' guide to viscosity solutions of second order partial differential equations. Bulletin of the American Mathematical Society, 27(1):1–67.
Cross, A.D.J. and Hancock, E.R. 1997. Scale-space vector fields for feature analysis. In Conference on Computer Vision and Pattern Recognition, pp. 738–743.
Dimitrov, P., Phillips, C., and Siddiqi, K. 2000. Robust and efficient skeletal graphs. In Conference on Computer Vision and Pattern Recognition, Hilton Head, South Carolina, pp. 417–423.
Faugeras, O. and Keriven, R. 1998. Complete dense stereovision using level set methods. In European Conference on Computer Vision, vol. 1, pp. 379–393.
Furst, J.D. and Pizer, S.M. 1998. Marching optimal parameter ridges: An algorithm to extract shape loci in 3D images. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 780–787.
Ge, Y., Stelts, D.R., Zha, X., Vining, D., and Wang, J. 1998. Computing the central path of the colon from CT images. In SPIE International Symposium on Medical Imaging, San Francisco, vol. 3338(1), pp. 702–713.
Goldak, J.A., Yu, X., Knight, A., and Dong, L. 1991. Con-structing discrete medial axis of 3-D objects. International Journal of Computational Geometry and Applications, 1(3):327–339.
Gomez, J. and Faugeras, O. 2000. Level sets and distance functions. In European Conference on Computer Vision, Dublin, Ireland, vol. 1, pp. 588–602.
Horn, B.K.P. and Brooks, M.J. (Eds.). 1989. Shape From Shading. MIT Press: Cambridge, MA.
Kalitzin, S.N., ter Haar Romeny, B.M., Salden, A.H., Nacken, P.F.M., and Viergever, M.A. 1998. Topological numbers and singularities in scalar images. Journal of Mathematical Imaging and Vision, 9(3):253–269.
Kimia, B.B., Tannenbaum, A., and Zucker, S.W. 1994. On optimal control methods in computer vision and image processing. In Geometry-Driven Diffusion in Computer Vision, B. ter Haar Romeny (Ed.). Kluwer: Norwell, MA, pp. 307–338.
Kimia, B.B., Tannenbaum, A., and Zucker, S.W. 1995. Shape, shocks, and deformations I: The components of two-dimensional shape and the reaction-diffusion space. International Journal of Computer Vision, 15:189–224.
Kimmel, R., Shaked, D., and Kiryati, N. 1995a. Skeletonization via distance maps and level sets. Computer Vision and Image Understanding, 62(3):382–391.
Kimmel, R., Siddiqi, K., Kimia, B.B., and Bruckstein, A. 1995b. Shape from shading: Level set propagation and viscosity solutions. International Journal of Computer Vision, 16(2):107–133.
Kong, T.Y. and Rosenfeld, A. 1989. Digital topology: Introduction and survey. Computer Vision Graphics and Image Processing, 48(3):357–393.
Lanczos, C. 1986. The Variational Principles of Mechanics. Dover: New York.
Lee, T.-C. and Kashyap, R.L. 1994. Building skeleton models via 3-D medial surface/axis thinning algorithm. Graphical Models and Image Processing, 56(6):462–478.
Leymarie, F. and Levine, M.D. 1992. Simulating the grassfire transform using an active contour model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(1):56–75.
Liu, A., Bullitt, E., and Pizer, S.M. 1998a. 3D/2D registration via skeletal near projective invariance in tubular objects. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 952–963.
Liu, T.-L. and Geiger, D. 1999. Approximate tree matching and shape similarity. In International Conference on Computer Vision, Kerkyra, Greece, pp. 456–461.
Liu, T.-L., Geiger, D., and Kohn, R.V. 1998b. Representation and self-similarity of shapes. In International Conference on Computer Vision.
Malandain, G., Bertrand, G., and Ayache, N. 1993. Topological segmentation of discrete surfaces. International Journal of Computer Vision, 10(2):183–197.
Malandain, G. and Fernandez-Vidal, S. 1998. Euclidean skeletons. Image and Vision Computing, 16:317–327.
Manzanera, A., Bernard, T.M., Preteux, F., and Longuet, B. 1999. Medial faces from a concise 3D thinning algorithm. In International Conference on Computer Vision, Kerkyra, Greece, pp. 337–343.
Miller, D. and Zucker, S.W. 1999. Computing with self-excitatory cliques. Neural Computation, 11(1):21–66.
Näf, M., Kübler, O., Kikinis, R., Shenton, M.E., and Székely, G. 1996. Characterization and recognition of 3D organ shape in medical image analysis using skeletonization. In IEEE Workshop on Mathematical Methods in Biomedical Image Analysis.
Ogniewicz, R.L. 1993. Discrete Voronoi Skeletons. Hartung-Gorre.
Oliensis, J. and Dupuis, P. 1994. An optimal control formulation and related numerical methods for a problem in shape construction. Annals of Applied Probability, 4(2):287–346.
Osher, S. and Shu, C.-W. 1991. High-order essentially non-oscillatory schemes for Hamilton-Jacobi equations. SIAM Journal of Numerical Analysis, 28:907–922.
Osher, S.J. and Sethian, J.A. 1988. Fronts propagating with curvature dependent speed: Algorithms based on Hamilton-Jacobi formulations. Journal of Computational Physics, 79:12–49.
Pizer, S.M., Joshi, S., Fletcher, P., Styner, M., Tracton, G., and Chen, Z. 2001. Segmentation of single-figure objects by deformable M-reps. In Medical Image Computing and Computer-Assisted Intervention, W.J Niessen and M.A. Viergever (Eds.). vol. 2208 of Lecture Notes in Computer Science. Springer: Berlin, pp. 862–871.
Pudney, C. 1998. Distance-ordered homotopic thinning: A skeletonization algorithm for 3D digital images. Computer Vision and Image Understanding, 72(3):404–413.
Rouy, E. and Tourin, A. 1992. A viscosity solutions approach to shape-from-shading. SIAM Journal of Numerical Analysis, 29(3):867–884.
Sapiro, G., Kimia, B.B., Kimmel, R., Shaked, D., and Bruckstein, A. 1992. Implementing continuous-scale morphology. Pattern Recognition, 26(9).
Schmitt, M. 1989. Some examples of algorithms analysis in computational geometry by means of mathematical morphology techniques. In Lecture Notes in Computer Science, Geometry and Robotics,vol. 391, J. Boissonnat and J. Laumond (Eds.). Springer-Verlag: Berlin, pp. 225–246.
Sebastian, T.B., Tek, H., Crisco, J.J., Wolfe, S.W., and Kimia, B.B. 1998. Segmentation of carpal bones from 3D CT images using skeletally coupled deformable models. In International Conference on Medical Image Computing and Computer-Assisted Inter-vention, pp. 1184–1194.
Sethian, J. 1996a. Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision, and Materials Science. Cambridge University Press: Cambridge.
Sethian, J.A. 1996b. A fast marching level set method for monotonically advancing fronts. In Proceedings of the National Academy of Sciences, USA, 93:1591–1595.
Shah, J. 1996. A common framework for curve evolution, segmentation and anisotropic diffusion. In Conference on Computer Vision and Pattern Recognition, pp. 136–142.
Shankar, R. 1994. Principles of Quantum Mechanics. Plenum Press: New York.
Sharvit, D., Chan, J., Tek, H., and Kimia, B.B. 1998. Symmetry-based indexing of image databases. In IEEE Workshop on Content-Based Access of Image and Video Libraries.
Sheehy, D.J., Armstrong, C.G., and Robinson, D.J. 1996. Shape description by medial surface construction. IEEE Transactions on Visualization and Computer Graphics, 2(1):62–72.
Sherbrooke, E.C., Patrikalakis, N., and Brisson, E. 1996. An algorithm for the medial axis transform of 3D polyhedral solids. IEEE Transactions on Visualization and Computer Graphics, 2(1):44–61.
Siddiqi, K., Bouix, S., Tannenbaum, A., and Zucker, S.W. 1999a. The Hamilton-Jacobi Skeleton. In International Conference on Computer Vision, Kerkyra, Greece, pp. 828–834.
Siddiqi, K., Kimia, B.B., and Shu, C. 1997. Geometric shock-capturing eno schemes for subpixel interpolation, computation and curve evolution. Graphical Models and Image Processing, 59(5):278–301.
Siddiqi, K., Shokoufandeh, A., Dickinson, S.J., and Zucker, S.W. 1999b. Shock graphs and shape matching. International Journal of Computer Vision, 35(1):13–32.
Stetten, G.D., and Pizer, S.M. 1999. Automated identification and measurement of objects via populations of medial primitives, with application to real time 3D echocardiography. In International Conference on Information Processing in Medical Imaging, pp. 84–97.
Sussman, M., Smereka, P., and Osher, S. 1994. A level set approach for computing solutions to incompressible two-phase flow. Journal of Computational Physics, 114:146–154.
Tari, S. and Shah, J. 1998. Local symmetries of shapes in arbitrary dimension. In International Conference on Computer Vision, Bombay, India.
Tari, Z.S.G., Shah, J., and Pien, H. 1997. Extraction of shape skeletons from grayscale images. Computer Vision and Image Understanding, 66:133–146.
Teichmann, M. and Teller, S. 1998. Assisted articulation of closed polygonal models. In 9th Eurographics Workshop on Animation and Simulation.
Tek, H. and Kimia, B.B. 1999. Symmetry maps of free-form curve segments via wave propagation. In International Conference on Computer Vision, Kerkyra, Greece, pp. 362–369.
van den Boomgaard, R. and Smeulders, A. 1994. The morphological structure of images: The differential equations of morphological scale-space. IEEE Transactions on Pattern Analysis and Machine intelligence, 16(11):1101–1113.
Zhou, Y., Kaufman, A., and Toga, A.W. 1998. 3D skeleton and centerline generation based on an approximate minimum distance field. International Journal of the Visual Computer, 14(7):303–314.
Zhu, S. and Yuille, A.L. 1996. FORMS: Aflexible object recognition and modeling system. International Journal of Computer Vision, 20(3):187–212.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Siddiqi, K., Bouix, S., Tannenbaum, A. et al. Hamilton-Jacobi Skeletons. International Journal of Computer Vision 48, 215–231 (2002). https://doi.org/10.1023/A:1016376116653
Issue Date:
DOI: https://doi.org/10.1023/A:1016376116653