# American Institute of Mathematical Sciences

February  2011, 5(1): 95-113. doi: 10.3934/ipi.2011.5.95

## Euclidean skeletons using closest points

 1 Department of Mathematics, University of California, Irvine, Irvine, CA 92697-3875, United States, United States 2 Computer Science Department, Stanford University, Stanford, CA 94305, United States

Received  May 2009 Revised  January 2010 Published  February 2011

In this paper, we present an efficient algorithm for computing the Euclidean skeleton of an object directly from a point cloud representation on an underlying grid. The key point of this algorithm is to identify those grid points that are (approximately) on the skeleton using the closest point information of a grid point and its neighbors. The three main ingredients of the algorithm are: (1) computing closest point information efficiently on a grid, (2) identifying possible skeletal points based on the number of closest points of a grid point and its neighbors with smaller distances, (3) applying a distance ordered homotopic thinning process to remove the non-skeletal points while preserving the end points or the edge points of the skeleton. Computational examples in 2D and 3D are presented.
Citation: Songting Luo, Leonidas J. Guibas, Hong-Kai Zhao. Euclidean skeletons using closest points. Inverse Problems & Imaging, 2011, 5 (1) : 95-113. doi: 10.3934/ipi.2011.5.95
##### References:
 [1] N. Amenta, M. Bern and D. Eppstein, The crust and the $\beta$-skeleton: Combinatorial curve reconstruction,, Graphic Models and Image Processing, (1998), 125. Google Scholar [2] N. Amenta, M. Bern and M. Kamvysselis, A new Voronoi-based surface reconstruction algorithm,, Computer Graphic (Proceedings of SIGGRAPH 98), (1998), 415. Google Scholar [3] C. Arcelli and G. S. di Baja, A width-independent fast thinning algorithm,, IEEE Transactions on Pattern Alalysis and Machine Intelligence, 7 (1995), 464. Google Scholar [4] C. Arcelli and G. S. di Baja, Ridge points in euclidean distance maps,, Pattern Recognition Letters, 13 (1982), 237. doi: 10.1016/0167-8655(92)90074-A. Google Scholar [5] D. Attali and J. O. Lachaud, Delaunay conforming iso-surface, skeleton extraction and noise removal,, Computational Geometry: Theory and Applications, 19 (2001), 175. Google Scholar [6] D. Attali and A. Montanvert, Modeling noise for a better simplification of skeletons,, in, 3 (1996), 13. Google Scholar [7] G. Bertrand, A parallel thinning algorithm for medial surfaces,, Pattern Recognition Letters, 16 (1995), 979. doi: 10.1016/0167-8655(95)00034-E. Google Scholar [8] H. Blum, Biological shape and visual science,, Journal of Theoretical Biology, 38 (1973), 205. doi: 10.1016/0022-5193(73)90175-6. Google Scholar [9] G. Borgefors, I. Nystrom and G. S. D. Baja, Computing skeletons in three dimensions,, Pattern Recognition, 32 (1999), 1225. doi: 10.1016/S0031-3203(98)00082-X. Google Scholar [10] L. Calabi, "A Study of the Skeleton of Plane Figures,", Technical Report 60429, (6042). Google Scholar [11] J.-H. Chuang, C.-H. Tsai and M.-C. Ko, Skeletonization of Three-Dimensional Object Using Generalized Potential Field,, IEEE Trans. Patten Anal. Mach. Intell., 22 (2000), 1241. doi: 10.1109/34.888709. Google Scholar [12] N. Cornea, D. Silver, X. Yuan and R. Balasubramanian, Computing hierarchical curve-skeletons of 3d objects,, The Visual Computer, 21 (2005), 945. doi: 10.1007/s00371-005-0308-0. Google Scholar [13] P.-E. Danielsson, Euclidean distance mapping,, Computer Graphics and Image Processing, 14 (1980), 227. doi: 10.1016/0146-664X(80)90054-4. Google Scholar [14] L. C. Evans, "Partial Differential Equations,", Graduate Studies in Mathematics, 19 (1998). Google Scholar [15] J. A. Goldak, X. Yu, A. Knight and L. Dong, Constructing discrete medial axis of 3-D objects,, International Journal of Computational Geometry and Applications, 1 (1991), 327. doi: 10.1142/S0218195991000220. Google Scholar [16] J. Gomez and O. Faugeras, Level sets and distance functions,, in, 1 (2000), 588. Google Scholar [17] M. S. Hassouna and A. A. Farag, On the extraction of curve skeletons using gradient vector flow,, in, (2007), 1. doi: 10.1109/ICCV.2007.4409112. Google Scholar [18] D. G. Kirkpatrick and J. D. Radke, A framework for computational morphology,, in, (1998), 217. Google Scholar [19] T.-C. Lee and R. L. Kashyap, Building skeleton models via 3-D medial surface/axis thinning algorithm,, Graphical Models and Image Processing, 56 (1994), 462. doi: 10.1006/cgip.1994.1042. Google Scholar [20] F. F. Leymarie, "Three-Dimensional Shape Representation Via Shock Flow,", Ph.D dissertation, (2003). Google Scholar [21] F. Leymarie and M. D. Levine, Simulating the grassfire transform using an active contour model,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (1992), 56. doi: 10.1109/34.107013. Google Scholar [22] G. Malandain, G. Bertrand and N. Ayache, Topological segmentation of discrete surfaces,, International Journal of Computer Vision, 10 (1993), 183. doi: 10.1007/BF01420736. Google Scholar [23] G. Malandain and S. Fernandez-Vidal, Euclidean skeletons,, Image and Vison Computing, 16 (1998), 317. doi: 10.1016/S0262-8856(97)00074-7. Google Scholar [24] A. Manzanera, T. M. Bernard, F. Pretrux and B. Longuet, Medial faces from a concise 3D thinnig algorithm,, in, (1999), 337. doi: 10.1109/ICCV.1999.791239. Google Scholar [25] M. Näf, O. Kübler, R. Kikinis, M. E. Shenton and G. Székely, Characterization and recognition of 3D organ shape in medical image analysis using skeletonization,, in, (1996). doi: 10.1109/MMBIA.1996.534066. Google Scholar [26] R. L. Ogniewicz, "Discrete Voronoi Skeletons,", Hartung-Gorre, (1993). Google Scholar [27] C. Pudney, Distance-ordered homotopic thinning: A skeletonizaiton algorithm for 3D digital images,, Computer Vision and Image Understanding, 72 (1998), 404. doi: 10.1006/cviu.1998.0680. Google Scholar [28] M. Schmitt, Some examples of algorithms analysis in computational geometry by means of mathematical morphology techniques,, in, 391 (1989), 225. Google Scholar [29] D. J. Sheehy, C. G. Armstrong and D. J. Robinson, Shape description by medial surface construction,, IEEE Transactions on Visualization and Computer Graphics, 2 (1996), 62. doi: 10.1109/2945.489387. Google Scholar [30] E. C. Sherbrooke, N. Patrikalakis and E. Brisson, An algorithm for the medial axis transform of 3D polyhedrals,, IEEE Transactions on Visualization and Computer Graphics, 2 (1996), 44. doi: 10.1109/2945.489386. Google Scholar [31] K. Siddiqi, S. Bouix, A. Tannenbaum and S. Zucher, Hamilton-Jacobi skeletons,, International Journal of Computer Vision, 48 (2002), 215. doi: 10.1023/A:1016376116653. Google Scholar [32] H. Tek and B. B. Kimia, Symmetry maps of free-form curve segments via wave propagation,, In, (1999), 362. Google Scholar [33] A. Torsello and E. R. Hancock, Correcting curvature-density effects in the Hamilton-Jacobi skeleton,, IEEE Transaction on Image Processing, 15 (2006), 877. doi: 10.1109/TIP.2005.863951. Google Scholar [34] T. Y. Kong and A. Rosenfeld, Digital topology: Introduction and survey,, Computer Vision, 48 (1989), 357. doi: 10.1016/0734-189X(89)90147-3. Google Scholar [35] Y. R. Tsai, Rapid and accurate computation of the distance function using grids,, Journal of Computational Physics, 178 (2002), 175. doi: 10.1006/jcph.2002.7028. Google Scholar [36] H.-K. Zhao, A fast sweeping method for Eikonal equation,, Mathematics of Computation, 74 (2005), 603. doi: 10.1090/S0025-5718-04-01678-3. Google Scholar [37] Y. Zhou, A. Kaufman and A. W. Toga, 3D skeleton and centerline generation based on an approximate minimum distance field,, International Journal of the Visual Computer, 14 (1998), 303. doi: 10.1007/s003710050142. Google Scholar

show all references

##### References:
 [1] N. Amenta, M. Bern and D. Eppstein, The crust and the $\beta$-skeleton: Combinatorial curve reconstruction,, Graphic Models and Image Processing, (1998), 125. Google Scholar [2] N. Amenta, M. Bern and M. Kamvysselis, A new Voronoi-based surface reconstruction algorithm,, Computer Graphic (Proceedings of SIGGRAPH 98), (1998), 415. Google Scholar [3] C. Arcelli and G. S. di Baja, A width-independent fast thinning algorithm,, IEEE Transactions on Pattern Alalysis and Machine Intelligence, 7 (1995), 464. Google Scholar [4] C. Arcelli and G. S. di Baja, Ridge points in euclidean distance maps,, Pattern Recognition Letters, 13 (1982), 237. doi: 10.1016/0167-8655(92)90074-A. Google Scholar [5] D. Attali and J. O. Lachaud, Delaunay conforming iso-surface, skeleton extraction and noise removal,, Computational Geometry: Theory and Applications, 19 (2001), 175. Google Scholar [6] D. Attali and A. Montanvert, Modeling noise for a better simplification of skeletons,, in, 3 (1996), 13. Google Scholar [7] G. Bertrand, A parallel thinning algorithm for medial surfaces,, Pattern Recognition Letters, 16 (1995), 979. doi: 10.1016/0167-8655(95)00034-E. Google Scholar [8] H. Blum, Biological shape and visual science,, Journal of Theoretical Biology, 38 (1973), 205. doi: 10.1016/0022-5193(73)90175-6. Google Scholar [9] G. Borgefors, I. Nystrom and G. S. D. Baja, Computing skeletons in three dimensions,, Pattern Recognition, 32 (1999), 1225. doi: 10.1016/S0031-3203(98)00082-X. Google Scholar [10] L. Calabi, "A Study of the Skeleton of Plane Figures,", Technical Report 60429, (6042). Google Scholar [11] J.-H. Chuang, C.-H. Tsai and M.-C. Ko, Skeletonization of Three-Dimensional Object Using Generalized Potential Field,, IEEE Trans. Patten Anal. Mach. Intell., 22 (2000), 1241. doi: 10.1109/34.888709. Google Scholar [12] N. Cornea, D. Silver, X. Yuan and R. Balasubramanian, Computing hierarchical curve-skeletons of 3d objects,, The Visual Computer, 21 (2005), 945. doi: 10.1007/s00371-005-0308-0. Google Scholar [13] P.-E. Danielsson, Euclidean distance mapping,, Computer Graphics and Image Processing, 14 (1980), 227. doi: 10.1016/0146-664X(80)90054-4. Google Scholar [14] L. C. Evans, "Partial Differential Equations,", Graduate Studies in Mathematics, 19 (1998). Google Scholar [15] J. A. Goldak, X. Yu, A. Knight and L. Dong, Constructing discrete medial axis of 3-D objects,, International Journal of Computational Geometry and Applications, 1 (1991), 327. doi: 10.1142/S0218195991000220. Google Scholar [16] J. Gomez and O. Faugeras, Level sets and distance functions,, in, 1 (2000), 588. Google Scholar [17] M. S. Hassouna and A. A. Farag, On the extraction of curve skeletons using gradient vector flow,, in, (2007), 1. doi: 10.1109/ICCV.2007.4409112. Google Scholar [18] D. G. Kirkpatrick and J. D. Radke, A framework for computational morphology,, in, (1998), 217. Google Scholar [19] T.-C. Lee and R. L. Kashyap, Building skeleton models via 3-D medial surface/axis thinning algorithm,, Graphical Models and Image Processing, 56 (1994), 462. doi: 10.1006/cgip.1994.1042. Google Scholar [20] F. F. Leymarie, "Three-Dimensional Shape Representation Via Shock Flow,", Ph.D dissertation, (2003). Google Scholar [21] F. Leymarie and M. D. Levine, Simulating the grassfire transform using an active contour model,, IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (1992), 56. doi: 10.1109/34.107013. Google Scholar [22] G. Malandain, G. Bertrand and N. Ayache, Topological segmentation of discrete surfaces,, International Journal of Computer Vision, 10 (1993), 183. doi: 10.1007/BF01420736. Google Scholar [23] G. Malandain and S. Fernandez-Vidal, Euclidean skeletons,, Image and Vison Computing, 16 (1998), 317. doi: 10.1016/S0262-8856(97)00074-7. Google Scholar [24] A. Manzanera, T. M. Bernard, F. Pretrux and B. Longuet, Medial faces from a concise 3D thinnig algorithm,, in, (1999), 337. doi: 10.1109/ICCV.1999.791239. Google Scholar [25] M. Näf, O. Kübler, R. Kikinis, M. E. Shenton and G. Székely, Characterization and recognition of 3D organ shape in medical image analysis using skeletonization,, in, (1996). doi: 10.1109/MMBIA.1996.534066. Google Scholar [26] R. L. Ogniewicz, "Discrete Voronoi Skeletons,", Hartung-Gorre, (1993). Google Scholar [27] C. Pudney, Distance-ordered homotopic thinning: A skeletonizaiton algorithm for 3D digital images,, Computer Vision and Image Understanding, 72 (1998), 404. doi: 10.1006/cviu.1998.0680. Google Scholar [28] M. Schmitt, Some examples of algorithms analysis in computational geometry by means of mathematical morphology techniques,, in, 391 (1989), 225. Google Scholar [29] D. J. Sheehy, C. G. Armstrong and D. J. Robinson, Shape description by medial surface construction,, IEEE Transactions on Visualization and Computer Graphics, 2 (1996), 62. doi: 10.1109/2945.489387. Google Scholar [30] E. C. Sherbrooke, N. Patrikalakis and E. Brisson, An algorithm for the medial axis transform of 3D polyhedrals,, IEEE Transactions on Visualization and Computer Graphics, 2 (1996), 44. doi: 10.1109/2945.489386. Google Scholar [31] K. Siddiqi, S. Bouix, A. Tannenbaum and S. Zucher, Hamilton-Jacobi skeletons,, International Journal of Computer Vision, 48 (2002), 215. doi: 10.1023/A:1016376116653. Google Scholar [32] H. Tek and B. B. Kimia, Symmetry maps of free-form curve segments via wave propagation,, In, (1999), 362. Google Scholar [33] A. Torsello and E. R. Hancock, Correcting curvature-density effects in the Hamilton-Jacobi skeleton,, IEEE Transaction on Image Processing, 15 (2006), 877. doi: 10.1109/TIP.2005.863951. Google Scholar [34] T. Y. Kong and A. Rosenfeld, Digital topology: Introduction and survey,, Computer Vision, 48 (1989), 357. doi: 10.1016/0734-189X(89)90147-3. Google Scholar [35] Y. R. Tsai, Rapid and accurate computation of the distance function using grids,, Journal of Computational Physics, 178 (2002), 175. doi: 10.1006/jcph.2002.7028. Google Scholar [36] H.-K. Zhao, A fast sweeping method for Eikonal equation,, Mathematics of Computation, 74 (2005), 603. doi: 10.1090/S0025-5718-04-01678-3. Google Scholar [37] Y. Zhou, A. Kaufman and A. W. Toga, 3D skeleton and centerline generation based on an approximate minimum distance field,, International Journal of the Visual Computer, 14 (1998), 303. doi: 10.1007/s003710050142. Google Scholar
 [1] Mark A. Peletier, Marco Veneroni. Stripe patterns and the Eikonal equation. Discrete & Continuous Dynamical Systems - S, 2012, 5 (1) : 183-189. doi: 10.3934/dcdss.2012.5.183 [2] Sobhan Seyfaddini. Unboundedness of the Lagrangian Hofer distance in the Euclidean ball. Electronic Research Announcements, 2014, 21: 1-7. doi: 10.3934/era.2014.21.1 [3] Chadi Nour. Construction of solutions to a global Eikonal equation. Conference Publications, 2007, 2007 (Special) : 779-783. doi: 10.3934/proc.2007.2007.779 [4] Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109 [5] Jaime Cruz-Sampedro. Schrödinger-like operators and the eikonal equation. Communications on Pure & Applied Analysis, 2014, 13 (2) : 495-510. doi: 10.3934/cpaa.2014.13.495 [6] Božidar Jovanović, Vladimir Jovanović. Virtual billiards in pseudo–euclidean spaces: Discrete hamiltonian and contact integrability. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5163-5190. doi: 10.3934/dcds.2017224 [7] Anatoli F. Ivanov. On global dynamics in a multi-dimensional discrete map. Conference Publications, 2015, 2015 (special) : 652-659. doi: 10.3934/proc.2015.0652 [8] Wacław Marzantowicz, Piotr Maciej Przygodzki. Finding periodic points of a map by use of a k-adic expansion. Discrete & Continuous Dynamical Systems - A, 1999, 5 (3) : 495-514. doi: 10.3934/dcds.1999.5.495 [9] Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems - A, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281 [10] Jean-Philippe Lessard, Evelyn Sander, Thomas Wanner. Rigorous continuation of bifurcation points in the diblock copolymer equation. Journal of Computational Dynamics, 2017, 4 (1&2) : 71-118. doi: 10.3934/jcd.2017003 [11] Anne-Sophie de Suzzoni. Consequences of the choice of a particular basis of $L^2(S^3)$ for the cubic wave equation on the sphere and the Euclidean space. Communications on Pure & Applied Analysis, 2014, 13 (3) : 991-1015. doi: 10.3934/cpaa.2014.13.991 [12] Mourad Bellassoued, David Dos Santos Ferreira. Stability estimates for the anisotropic wave equation from the Dirichlet-to-Neumann map. Inverse Problems & Imaging, 2011, 5 (4) : 745-773. doi: 10.3934/ipi.2011.5.745 [13] Hunseok Kang. Dynamics of local map of a discrete Brusselator model: eventually trapping regions and strange attractors. Discrete & Continuous Dynamical Systems - A, 2008, 20 (4) : 939-959. doi: 10.3934/dcds.2008.20.939 [14] Fairouz Tchier. Nondeterministic semantics of compound diagrams. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1357-1371. doi: 10.3934/dcdss.2015.8.1357 [15] Lili Du, Zheng-An Yao. Localization of blow-up points for a nonlinear nonlocal porous medium equation. Communications on Pure & Applied Analysis, 2007, 6 (1) : 183-190. doi: 10.3934/cpaa.2007.6.183 [16] José M. Arrieta, Esperanza Santamaría. Estimates on the distance of inertial manifolds. Discrete & Continuous Dynamical Systems - A, 2014, 34 (10) : 3921-3944. doi: 10.3934/dcds.2014.34.3921 [17] Liliana Trejo-Valencia, Edgardo Ugalde. Projective distance and $g$-measures. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3565-3579. doi: 10.3934/dcdsb.2015.20.3565 [18] Vassilis Rothos. Subharmonic bifurcations of localized solutions of a discrete NLS equation. Conference Publications, 2005, 2005 (Special) : 756-767. doi: 10.3934/proc.2005.2005.756 [19] Alberto Bressan, Massimo Fonte. On the blow-up for a discrete Boltzmann equation in the plane. Discrete & Continuous Dynamical Systems - A, 2005, 13 (1) : 1-12. doi: 10.3934/dcds.2005.13.1 [20] Panayotis Panayotaros. Continuation and bifurcations of breathers in a finite discrete NLS equation. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1227-1245. doi: 10.3934/dcdss.2011.4.1227

2018 Impact Factor: 1.469