# 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-135. 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-421. 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-474. Google Scholar [4] C. Arcelli and G. S. di Baja, Ridge points in euclidean distance maps, Pattern Recognition Letters, 13 (1982), 237-243. 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-189.  Google Scholar [6] D. Attali and A. Montanvert, Modeling noise for a better simplification of skeletons, in "Proceeding of International Conference on Image Processing," 3 (1996), 13-16. Google Scholar [7] G. Bertrand, A parallel thinning algorithm for medial surfaces, Pattern Recognition Letters, 16 (1995), 979-986. 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-287. 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-1236. doi: 10.1016/S0031-3203(98)00082-X.  Google Scholar [10] L. Calabi, "A Study of the Skeleton of Plane Figures," Technical Report 60429, sr-2, Parke Mathematical Laboratories, December 1965. 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-1251. 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-955. doi: 10.1007/s00371-005-0308-0.  Google Scholar [13] P.-E. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing, 14 (1980), 227-248. doi: 10.1016/0146-664X(80)90054-4.  Google Scholar [14] L. C. Evans, "Partial Differential Equations," Graduate Studies in Mathematics, 19, American Society of Mathematics, 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-329. doi: 10.1142/S0218195991000220.  Google Scholar [16] J. Gomez and O. Faugeras, Level sets and distance functions, in "European Conference on Computer Vision," Dublin, Ireland, 1 (2000), 588-602. Google Scholar [17] M. S. Hassouna and A. A. Farag, On the extraction of curve skeletons using gradient vector flow, in "11th International Conference on Computer Vision (ICCV)," (2007), 1-8. doi: 10.1109/ICCV.2007.4409112.  Google Scholar [18] D. G. Kirkpatrick and J. D. Radke, A framework for computational morphology, in "Computational Geometry" (ed. G. Toussaint), North-Holland, (1998), 217-248. 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-478. doi: 10.1006/cgip.1994.1042.  Google Scholar [20] F. F. Leymarie, "Three-Dimensional Shape Representation Via Shock Flow," Ph.D dissertation, Brown University, 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-75. 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-197. doi: 10.1007/BF01420736.  Google Scholar [23] G. Malandain and S. Fernandez-Vidal, Euclidean skeletons, Image and Vison Computing, 16 (1998), 317-327. 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 "International Conference on Computer Vision," Kerkyra, Greece, (1999), 337-343. 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 "IEEE Workshop on Mathematical Methods in Biomedical Image Analysis," 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-413. 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 "Lecture Notes in Computer Science, Geometry and Robotics" (eds. J. Boissonnat and J. Laumond), 391, Springer-Verlag: Berlin, (1989), 225-246. 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-72. 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-61. 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-221. 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 "International Conference on Computer Vision," Kerkyra, Greece, (1999), 362-369. 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-891. doi: 10.1109/TIP.2005.863951.  Google Scholar [34] T. Y. Kong and A. Rosenfeld, Digital topology: Introduction and survey, Computer Vision, Graphics, and Image Processing, 48 (1989), 357-393. 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-195. 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-627. 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-314. 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-135. 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-421. 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-474. Google Scholar [4] C. Arcelli and G. S. di Baja, Ridge points in euclidean distance maps, Pattern Recognition Letters, 13 (1982), 237-243. 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-189.  Google Scholar [6] D. Attali and A. Montanvert, Modeling noise for a better simplification of skeletons, in "Proceeding of International Conference on Image Processing," 3 (1996), 13-16. Google Scholar [7] G. Bertrand, A parallel thinning algorithm for medial surfaces, Pattern Recognition Letters, 16 (1995), 979-986. 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-287. 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-1236. doi: 10.1016/S0031-3203(98)00082-X.  Google Scholar [10] L. Calabi, "A Study of the Skeleton of Plane Figures," Technical Report 60429, sr-2, Parke Mathematical Laboratories, December 1965. 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-1251. 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-955. doi: 10.1007/s00371-005-0308-0.  Google Scholar [13] P.-E. Danielsson, Euclidean distance mapping, Computer Graphics and Image Processing, 14 (1980), 227-248. doi: 10.1016/0146-664X(80)90054-4.  Google Scholar [14] L. C. Evans, "Partial Differential Equations," Graduate Studies in Mathematics, 19, American Society of Mathematics, 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-329. doi: 10.1142/S0218195991000220.  Google Scholar [16] J. Gomez and O. Faugeras, Level sets and distance functions, in "European Conference on Computer Vision," Dublin, Ireland, 1 (2000), 588-602. Google Scholar [17] M. S. Hassouna and A. A. Farag, On the extraction of curve skeletons using gradient vector flow, in "11th International Conference on Computer Vision (ICCV)," (2007), 1-8. doi: 10.1109/ICCV.2007.4409112.  Google Scholar [18] D. G. Kirkpatrick and J. D. Radke, A framework for computational morphology, in "Computational Geometry" (ed. G. Toussaint), North-Holland, (1998), 217-248. 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-478. doi: 10.1006/cgip.1994.1042.  Google Scholar [20] F. F. Leymarie, "Three-Dimensional Shape Representation Via Shock Flow," Ph.D dissertation, Brown University, 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-75. 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-197. doi: 10.1007/BF01420736.  Google Scholar [23] G. Malandain and S. Fernandez-Vidal, Euclidean skeletons, Image and Vison Computing, 16 (1998), 317-327. 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 "International Conference on Computer Vision," Kerkyra, Greece, (1999), 337-343. 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 "IEEE Workshop on Mathematical Methods in Biomedical Image Analysis," 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-413. 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 "Lecture Notes in Computer Science, Geometry and Robotics" (eds. J. Boissonnat and J. Laumond), 391, Springer-Verlag: Berlin, (1989), 225-246. 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-72. 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-61. 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-221. 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 "International Conference on Computer Vision," Kerkyra, Greece, (1999), 362-369. 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-891. doi: 10.1109/TIP.2005.863951.  Google Scholar [34] T. Y. Kong and A. Rosenfeld, Digital topology: Introduction and survey, Computer Vision, Graphics, and Image Processing, 48 (1989), 357-393. 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-195. 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-627. 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-314. 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, 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, 1999, 5 (3) : 495-514. doi: 10.3934/dcds.1999.5.495 [9] Kin Ming Hui, Jinwan Park. Asymptotic behaviour of singular solution of the fast diffusion equation in the punctured euclidean space. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5473-5508. doi: 10.3934/dcds.2021085 [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] Brigitte Vallée. Euclidean dynamics. Discrete & Continuous Dynamical Systems, 2006, 15 (1) : 281-352. doi: 10.3934/dcds.2006.15.281 [12] Sami Aouaoui, Rahma Jlel. On some elliptic equation in the whole euclidean space $\mathbb{R}^2$ with nonlinearities having new exponential growth condition. Communications on Pure & Applied Analysis, 2020, 19 (10) : 4771-4796. doi: 10.3934/cpaa.2020211 [13] 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 [14] 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 [15] Hunseok Kang. Dynamics of local map of a discrete Brusselator model: eventually trapping regions and strange attractors. Discrete & Continuous Dynamical Systems, 2008, 20 (4) : 939-959. doi: 10.3934/dcds.2008.20.939 [16] Mario Bukal. Well-posedness and convergence of a numerical scheme for the corrected Derrida-Lebowitz-Speer-Spohn equation using the Hellinger distance. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3389-3414. doi: 10.3934/dcds.2021001 [17] Fairouz Tchier. Nondeterministic semantics of compound diagrams. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1357-1371. doi: 10.3934/dcdss.2015.8.1357 [18] Ahmad El Hajj, Aya Oussaily. Continuous solution for a non-linear eikonal system. Communications on Pure & Applied Analysis, 2021, 20 (11) : 3795-3823. doi: 10.3934/cpaa.2021131 [19] 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 [20] Zimo Zhu, Gang Chen, Xiaoping Xie. Semi-discrete and fully discrete HDG methods for Burgers' equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021132

2020 Impact Factor: 1.639