article

Comparison of curve and surface skeletonization methods for voxel shapes

Authors:

André Sobiecki,

Alexandru TeleaAuthors Info & Claims

Pattern Recognition Letters, Volume 47

Pages 147 - 156

https://doi.org/10.1016/j.patrec.2014.01.012

Published: 01 October 2014 Publication History

Abstract

Surface and curve skeletons are important shape descriptors with applications in shape matching, simplification, retrieval, and animation. In recent years, many surface and curve skeletonization methods for 3D shapes have been proposed. However, practical comparisons of such methods against each other and against given quality criteria are quite limited in the literature. In this paper, we compare 4 surface and 6 recent curve skeletonization methods that operate on voxel shapes. We first compare the selected methods from a global perspective, using the quality criteria established by a reference paper in the field. Next, we propose a detailed comparison that refines the gained insights by highlighting small-scale differences between skeletons obtained by different methods.

References

[1]

Siddiqi, K. and Pizer, S., Medial Representations: Mathematics, Algorithms and Applications. 2009. Springer.

[2]

Pizer, S., Siddiqi, K., Szekely, G., Damon, J. and Zucker, S., Multiscale medial loci and their properties. Int. J. Comput. Vision. v55 i2-3. 155-179.

[3]

Cornea, N., Silver, D. and Min, P., Curve-skeleton properties, applications, and algorithms. IEEE Trans. Visual Comput. Graphics. v13 i3. 87-95.

[4]

Blum, H., Biological shape and visual science. J. Theor. Biol. v38. 205-287.

[5]

Sobiecki, A., Yasan, H., Jalba, A. and Telea, A., Qualitative comparison of contraction-based curve skeletonization methods. In: Proc. International Symposium on Mathematical Morphology, Springer. pp. 425-439.

[6]

Giblin, P. and Kimia, B., A formal classification of 3D medial axis points and their local geometry. IEEE Pattern Anal. Mach. Intell. v26 i2. 238-251.

[7]

Reniers, D., van Wijk, J.J. and Telea, A., Computing multiscale skeletons of genus 0 objects using a global importance measure. IEEE Trans. Visual Comput. Graphics. v14 i2. 355-368.

[8]

Surface and curve skeletonization of large 3D models on the GPU. IEEE Trans. Pattern Anal. Mach. Intell. v35 i6. 1495-1508.

[9]

Damon, J., Global medial structure of regions in R3. Geom. Topol. v10. 2385-2429.

[10]

Leymarie, F. and Kimia, B., The medial scaffold of 3D unorganized point clouds. IEEE Trans. Visual Comput. Graphics. v29 i2. 313-330.

[11]

Chang, M., Leymarie, F. and Kimia, B., Surface reconstruction from point clouds by transforming the medial scaffold. Comput. Vision Image Underst. v113. 1130-1146.

Digital Library

[12]

Dey, T. and Zhao, W., Approximate medial axis as a Voronoi subcomplex. Comput. Aided Des. v36 i2. 195-202.

[13]

N. Amenta, S. Choi, R. Kolluri, The power crust., in: Proc. SMA, 2001, pp. 65-73.

[14]

O. Au, C. Tai, H. Chu, D. Cohen-Or, T. Lee, Skeleton extraction by mesh contraction, in: Proc. ACM SIGGRAPH, 2008, pp. 441-449.

[15]

A. Tagliasacchi, H. Zhang, D. Cohen-Or, Curve skeleton extraction from incomplete point cloud, in: Proc. SIGGRAPH, 2009, pp. 541-550.

[16]

J. Cao, A. Tagliasacchi, M. Olson, H. Zhang, Z. Su, Point cloud skeletons via Laplacian based contraction, in: Proc. SMI, 2010, pp. 187-197.

[17]

X. Li, T. Woon, T. Tan, Z. Huang, Decomposing polygon meshes for interactive applications, in: Proc. I3D Symp., 2001, pp. 35-42.

[18]

Huang, H., Wu, S., Cohen-Or, D., Gong, M., Zhang, H. and Li, G., l1 Medial skeleton of point cloud. ACM Trans. Graphics. v32 i4. 1-8.

[19]

Miklos, B., Giesen, J. and Pauly, M., Discrete scale axis representations for 3D geometry. ACM Trans. Graphics. v29 i4. 394-493.

[20]

Ma, J., Bae, S.W. and Choi, S., 3D medial axis point approximation using nearest neighbors and the normal field. Visual Comput. v28 i1. 7-19.

[21]

Leymarie, F. and Levine, M., Simulating the grassfire transform using an active contour model. IEEE Trans. Pattern Anal. Mach. Intell. v14 i1. 56-75.

[22]

Kimmel, R., Shaked, D., Kiryati, N. and Bruckstein, A., Skeletonization via Distance Maps and Level Sets. Comput. Vision Image Underst. v62 i3. 382-391.

[23]

Ge, Y. and Fitzpatrick, J., On the generation of skeletons from discrete Euclidean distance maps. IEEE Trans. Pattern Anal. Mach. Intell. v18. 1055-1066.

[24]

M. Wan, F. Dachille, A. Kaufman, Distance-field based skeletons for virtual navigation, In: Proc. IEEE Visualization, 2001, pp. 239-246.

[25]

Siddiqi, K., Bouix, S., Tannenbaum, A. and Zucker, S., Hamilton-Jacobi skeletons. Int. J. Comput. Vision. v48 i3. 215-231.

[26]

Hesselink, W. and Roerdink, J., Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform. IEEE Trans. Pattern Anal. Mach. Intell. v30 i12. 2204-2217.

[27]

A. Sud, M. Foskey, D. Manocha, Homotopy-preserving medial axis simplification, in: Proc. SPM, 2005, pp. 103-110.

[28]

T. Cao, K. Tang, A. Mohamed, T. Tan, Parallel banding algorithm to compute exact distance transform with the GPU, in: Proc. SIGGRAPH I3D, 2010, pp. 134-141.

[29]

Ahuja, N. and Chuang, J., Shape representation using a generalized potential field model. IEEE Trans. Pattern Anal. Mach. Intell. v19 i2. 169-176.

[30]

Cornea, N., Silver, D., Yuan, X. and Balasubramanian, R., Computing hierarchical curve-skeletons of 3D objects. Visual Comput. v21 i11. 945-955.

[31]

Aslan, C., Erdem, A., Erdem, E. and Tari, S., Disconnected skeleton: shape at its absolute scale. IEEE Trans. Pattern Anal. Mach. Intell. v30 i12. 2188-2203.

[32]

Hassouna, M. and Farag, A., Variational curve skeletons using gradient vector flow. IEEE Trans. Pattern Anal. Mach. Intell. v31 i12. 2257-2274.

[33]

M. Foskey, M. Lin, D. Manocha, Efficient computation of a simplified medial axis, in: Proc. SMA, 2003, pp. 135-142.

[34]

T. Dey, J. Sun, Defining and computing curve skeletons with medial geodesic functions, in: Proc. SGP. IEEE, 2006, pp. 143-152.

[35]

Livesu, M., Guggeri, F. and Scateni, R., Reconstructing the curve-skeletons of 3D shapes using the visual hull. IEEE Trans. Visual Comput. Graphics. v18 i11. 1891-1901.

[36]

A. Telea, J.J. van Wijk, An augmented fast marching method for computing skeletons and centerlines, in: Proc. VisSym., 2002, pp. 251-259.

[37]

Palagyi, K. and Kuba, A., Directional 3D thinning using 8 subiterations. In: Lecture Notes in Computer Science, vol. 1568. Springer. pp. 325-336.

Digital Library

[38]

Couprie, M., Coeurjolly, D. and Zrour, R., Discrete bisector function and Euclidean skeleton in 2D and 3D. Image Vision Comput. v25 i10. 1543-1556.

[39]

Image Analysis and Mathematical Morphology. 1982. Acad. Press.

[40]

La, Lantuéjoul C., Squelettisation et son Application aux Mesures Topologiques de Mosaiques Polycristallines. 1979. School of Mines, Paris.

[41]

Skeletons and perceptual graphs. Signal Proc. v16 i4. 335-363.

[42]

Beucher, S., Digital skeletons in Euclidean and geodesic spaces. Signal Process. v38 i1. 127-141.

[43]

Pudney, C., Distance-ordered homotopic thinning: a skeletonization algorithm for 3D digital images. Comput. Vision Image Underst. v72 i3. 404-413.

[44]

Reversible surface skeletons of 3D objects by iterative thinning of distance transforms. In: Proc. Discrete Geometry for Computer Imagery, Springer. pp. 400-411.

[45]

Arcelli, C., Sanniti di Baja, G. and Serino, L., Distance-driven skeletonization in voxel images. IEEE Trans. Pattern Anal. Mach. Intell. v33 i4. 709-720.

[46]

Peter, P. and Breu, M., Refined homotopic thinning algorithms and quality measures for skeletonisation methods. In: Innovations for Shape Analysis Mathematics and Visualization, Springer. pp. 77-92.

[47]

Belyaev, A., Yoshizawa, S. and Seidel, H.P., Skeleton-based variational mesh deformations. Comput. Graphics Forum. v26 i3. 255-264.

[48]

Chaussard, J., Couprie, M. and Talbot, H., A discrete lambda-medial axis. In: Proc. Discrete Geometry for Computer Imagery, Springer. pp. 232-243.

[49]

Gagvani, N. and Silver, D., Parameter-controlled volume thinning. Graphical Models Image Process. v61 i3. 149-164.

[50]

Tagliasacchi, A., Alhashim, I., Olson, M. and Zhang, H., Mean curvature skeletons. Comput. Graphics Forum. v31. 1735-1744.

[51]

Liu, L., Chambers, E., Letscher, D. and Ju, T., A simple and robust thinning algorithm on cell complexes. Comput. Graphics Forum. v29 i7. 2253-2260.

[52]

Ju, T., Baker, M. and Chiu, W., Computing a family of skeletons of volumetric models for shape description. Comput. Aided Des. v39 i5. 352-360.

[53]

Bertrand, G., A parallel thinning algorithm for medial surfaces. Pattern Recognit. Lett. v16 i9. 979-986.

[54]

A. Telea, A. Jalba, Computing curve skeletons from medial surfaces of 3D shapes, in: Proc. TPCG, 2012, pp. 137-145.

[55]

Schaap, M., Metz, C., van Walsum, T., van der Giessen, A., Weustinck, A. and Mollet, N., Standardized evaluation methodology and reference database for evaluating coronary artery centerline extraction algorithms. Med. Image Anal. v13 i5. 701-714.

[56]

Mullikin, J. and Verbeek, P., Surface area estimation of digitized planes. Bioimaging. v1. 6-16.

[57]

Torsello, A. and Hancock, E., Correcting curvature-density effects in the Hamilton-Jacobi skeleton. IEEE Trans. Image Process. v15 i4. 877-891.

[58]

Nooruddin, F. and Turk, G., Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visual Comput. Graphics. v9 i2. 191-205.

[59]

A. Sobiecki, A. Jalba, A. Telea, Skeletonization benchmarking resources, 2014. <www.cs.rug.nl/svcg/Shapes/SkelBenchmark>.

Cited By

Karai GKardos PPalágyi K(2024)Sufficient Conditions for Topology-Preserving Parallel Reductions on the Face-Centered Cubic GridJournal of Mathematical Imaging and Vision10.1007/s10851-024-01177-y66:3(271-292)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10851-024-01177-y
Wang NWang BWang WGuo X(2022)Computing Medial Axis Transform with Feature Preservation via Restricted Power DiagramACM Transactions on Graphics10.1145/3550454.355546541:6(1-18)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555465
Karai G(2022)Distance-Driven Curve-Thinning on the Face-Centered Cubic GridDiscrete Geometry and Mathematical Morphology10.1007/978-3-031-19897-7_28(354-365)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-19897-7_28
Show More Cited By

Comparison of curve and surface skeletonization methods for voxel shapes
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation

Recommendations

Surface and Curve Skeletonization of Large 3D Models on the GPU

We present a GPU-based framework for extracting surface and curve skeletons of 3D shapes represented as large polygonal meshes. We use an efficient parallel search strategy to compute point-cloud skeletons and their distance and feature transforms (FTs) ...
Curve Skeletonization by Junction Detection in Surface Skeletons
IWVF-4: Proceedings of the 4th International Workshop on Visual Form

We present an algorithm that, starting from the surface skeleton of a 3D solid object, computes the curve skeleton. The algorithm is based on the detection of curves and junctions in the surface skeleton. It can be applied to any surface skeleton, ...
Distance-Driven Skeletonization in Voxel Images

A distance-driven method to compute the surface and curve skeletons of 3D objects in voxel images is described. The method is based on the use of the <3,4,5> weighted distance transform, on the detection of anchor points, and on the application of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier B.V. © 2014.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 October 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Karai GKardos PPalágyi K(2024)Sufficient Conditions for Topology-Preserving Parallel Reductions on the Face-Centered Cubic GridJournal of Mathematical Imaging and Vision10.1007/s10851-024-01177-y66:3(271-292)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s10851-024-01177-y
Wang NWang BWang WGuo X(2022)Computing Medial Axis Transform with Feature Preservation via Restricted Power DiagramACM Transactions on Graphics10.1145/3550454.355546541:6(1-18)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555465
Karai G(2022)Distance-Driven Curve-Thinning on the Face-Centered Cubic GridDiscrete Geometry and Mathematical Morphology10.1007/978-3-031-19897-7_28(354-365)Online publication date: 24-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-19897-7_28
Palágyi KNémeth G(2019)Centerline Extraction from 3D Airway Trees Using Anchored ShrinkingAdvances in Visual Computing10.1007/978-3-030-33723-0_34(419-430)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1007/978-3-030-33723-0_34
Yan YLetscher DJu T(2018)Voxel coresACM Transactions on Graphics10.1145/3197517.320139637:4(1-13)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201396
Liu MZhang YBai JCao YAlperovich JRamani KMark GFussell SLampe Cschraefel mHourcade JAppert CWigdor D(2017)WireFabProceedings of the 2017 CHI Conference on Human Factors in Computing Systems10.1145/3025453.3025619(965-976)Online publication date: 2-May-2017
https://dl.acm.org/doi/10.1145/3025453.3025619
Tagliasacchi ADelame TSpagnuolo MAmenta NTelea AMadeira JPatow G(2016)3D skeletonsProceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports10.5555/3059330.3059333(573-597)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059330.3059333
Sobiecki AJalba ATelea ASantos LBashford-Rogers T(2016)Robust gap removal from binary volumesProceedings of the 37th Annual Conference of the European Association for Computer Graphics: Short Papers10.5555/3059107.3059114(17-20)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059107.3059114
Delame TKustra JTelea AGuthe MHullin MStamminger MWeinkauf T(2016)Structuring 3D medial skeletonsProceedings of the Conference on Vision, Modeling and Visualization10.5555/3056901.3056903(1-8)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.5555/3056901.3056903
Feng CJalba ATelea AFerreira AGiachetti AGiorgi D(2016)A descriptor for voxel shapes based on the skeleton cut spaceProceedings of the Eurographics 2016 Workshop on 3D Object Retrieval10.5555/3056462.3056468(13-20)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3056462.3056468
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents