More Web Proxy on the site http://driver.im/

research-article

Curve-Skeleton Properties, Applications, and Algorithms

Authors:

Nicu D. Cornea,

Deborah Silver,

Patrick MinAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 13, Issue 3

Pages 530 - 548

https://doi.org/10.1109/TVCG.2007.1002

Published: 01 May 2007 Publication History

Abstract

Curve-skeletons are thinned 1D representations of 3D objects useful for many visualization tasks including virtual navigation, reduced-model formulation, visualization improvement, animation, etc. There are many algorithms in the literature describing extraction methodologies for different applications; however, it is unclear how general and robust they are. In this paper, we provide an overview of many curve-skeleton applications and compile a set of desired properties of such representations. We also give a taxonomy of methods and analyze the advantages and drawbacks of each class of algorithms.

References

[1]

3D Studio Max, http://www.autodesk.com/3dsmax. 2006.

[2]

G.H. Abdel-Hamid and Y.-H. Yang, “Multiresolution Skeletonization: An Electrostatic Field-Based Approach,” Proc. IEEE Int'l Conf. Image Processing, pp. 949–953, 1994.

[3]

N. Ahuja and J. Chuang, “Shape Representation Using a Generalized Potential Field Model,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 2, pp. 169–176, Feb. 1997.

Digital Library

[4]

N. Amenta, S. Choi, and R. Kolluri, “The Power Crust,” Proc. Sixth ACM Symp. Solid Modeling, pp. 249–260, 2001.

Digital Library

[5]

N. Amenta, S. Choi, and R. Kolluri, “The Power Crust, Unions of Balls, and the Medial Axis Transform,” Computational Geometry: Theory and Applications, vol. 19, nos. 2–3, pp. 127–153, 2001.

Digital Library

[6]

D. Attali, J.-D. Boissonnat, and H. Edelsbrunner, “Stability and Computation of the Medial Axis-A State-of-the-Art Report,” Math. Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, Springer-Verlag, 2004.

[7]

D. Attali and J.-O. Lachaud, “Delaunay Conforming Iso-Surface, Skeleton Extraction and Noise Removal,” Computational Geometry, vol. 19, nos. 2–3, pp. 175–189, 2001.

Digital Library

[8]

M. Attene, S. Biasotti, and M. Spagnuolo, “Shape Understanding by Contour-Driven Retiling,” The Visual Computer, vol. 19, nos. 2–3, p. 127, 2003.

[9]

S.R. Aylward and E. Bullitt, “Initialization, Noise, Singularities, and Scale in Height Ridge Traversal for Tubular Object Centerline Extraction,” IEEE Trans. Medical Imaging, vol. 21, no. 2, 2002.

[10]

S.R. Aylward, J. Jomier, S. Weeks, and E. Bullitt, “Registration and Analysis of Vascular Images,” Int'l J. Computer Vision, vol. 55, nos. 2–3, 2003.

[11]

D.C. Banks and B.A. Singer, “Vortex Tubes in Turbulent Flows: Identification, Representation, Reconstruction,” Proc. IEEE Visualization Conf., 1994.

[12]

D. Bartz, W. Straßer, M. Skalej, and D. Welte, “Interactive Exploration of Extra- and Intracranial Blood Vessels,” Proc. IEEE Visualization Conf., 1999.

[13]

G. Bertrand and Z. Aktouf, “A Three-Dimensional Thinning Algorithm Using Subfields,” Vision Geometry III, vol. 2356, pp. 113–124, SPIE, 1994.

[14]

S. Biasotti, B. Falcidieno, and M. Spagnuolo, “Extended Reeb Graphs for Surface Understanding and Description,” Proc. Int'l Conf. Discrete Geometry for Computer Imagery, p. 185, 2000.

[15]

S. Biasotti, S. Marini, M. Mortara, and G. Patané, “An Overview on Properties and Efficacy of Topological Skeletons in Shape Modeling,” Proc. Int'l Conf. Shape Modeling and Applications, 2003.

[16]

S. Biasotti, S. Marini, M. Mortara, G. Patané, M. Spagnuolo, and B. Falcidieno, “3D Shape Matching through Topological Structures,” Lecture Notes in Computer Science, vol. 2886, p. 23, 2003.

[17]

I. Bitter, A.E. Kaufman, and M. Sato, “Penalized-Distance Volumetric Skeleton Algorithm,” IEEE Trans. Visualization and Computer Graphics, vol. 7, no. 3, July-Sept. 2001.

[18]

R.L. Blanding, G.M. Turkiyyah, D.W. Storti, and M.A. Ganter, “Skeleton-Based Three-Dimensional Geometric Morphing,” Computational Geometry, vol. 15, pp. 129–148, 2000.

Digital Library

[19]

J. Bloomenthal, “Medial Based Vertex Deformation,” Proc. SIGGRAPH/Eurographics Symp. Computer Animation, pp. 147–151, 2002.

[20]

J. Bloomenthal and C. Lim, “Skeletal Methods of Shape Manipulation,” Proc. Int'l Shape Modeling Conf., 1999.

Digital Library

[21]

H. Blum, “A Transformation for Extraction New Descriptors of Shape,” Models for the Perception of Speech and Visual Form, MIT Press, 1967.

[22]

H. Blum and R.N. Nagel, “Shape Description Using Weighted Symmetric Axis Features,” Pattern Recognition, vol. 10, no. 3, p. 167, 1978.

[23]

G. Borgefors, “On Digital Distance Transforms in Three Dimensions,” Computer Vision and Image Understanding, vol. 64, no. 3, pp. 368–376, 1996.

Digital Library

[24]

G. Borgefors, I. Nyström, and G. Sanniti di Baja, “Computing Skeletons in Three Dimensions,” Pattern Recognition, vol. 32, no. 7, 1999.

[25]

S. Bouix and K. Siddiqi, “Divergence-Based Medial Surfaces,” Proc. European Conf. Computer Vision (ECCV), pp. 603–618, 2000.

[26]

J.W. Brandt and V.R. Alazi, “Continuous Skeleton Computation by Voronoi Diagram,” CVGIP: Image Understanding, vol. 55, pp. 329–338, 1992.

Digital Library

[27]

A. Brennecke and T. Isenberg, “3D Shape Matching Using Skeleton Graphs,” Simulation and Visualization, pp. 299–310, 2004.

[28]

G.J. Brostow, I. Essa, D. Steedly, and V. Kwatra, “Novel Skeletal Representation for Articulated Creatures,” Proc. European Conf. Computer Vision, 2004.

[29]

D. Brunner and G. Brunnett, “Mesh Segmentation Using the Object Skeleton Graph,” Proc. Ini'l Conf. Computer Graphics and Imaging, pp. 48–55, 2004.

[30]

C.A. Burbeck and S.M. Pizer, “Object Representation by Cores: Identifying and Representing Primitive Spatial Regions,” Vision Research, vol. 35, no. 13, p. 1917, 1995.

[31]

S.W. Choi and H.P. Seidel, “Linear One-Sided Stability of MAT for Weakly Injective 3D Domain,” Proc. ACM Symp. Solid Modeling and Applications, 2002.

[32]

J. Chuang, C. Tsai, and M.-C. Ko, “Skeletonization of Three-Dimensional Object Using Generalized Potential Field,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 11, p. 1241, Nov. 2000.

Digital Library

[33]

N.D. Cornea, M.F. Demirci, D. Silver, A. Shokoufandeh, S.J. Dickinson, and P.B. Kantor, “3D Object Retrieval Using Many-to-Many Matching of Curve-Skeletons,” Proc. Int'l Shape Modeling Conf.,2005.

Digital Library

[34]

N.D. Cornea, D. Silver, and P. Min, “Curve-Skeleton Applications,” Proc. IEEE Visualization Conf., p. 95, 2005.

[35]

N. Cornea, D. Silver, X. Yuan, and R. Balasubramanian, “Computing Hierarchical Curve-Skeletons of 3D Objects,” The Visual Computer, vol. 21, no. 11, pp. 945–955, 2005.

[36]

M. Couprie and R. Zrour, “Discrete Bisector Function and Euclidean Skeleton,” Lecture Notes in Computer Science, vol. 3429, 2005.

[37]

T. Culver, J. Keyser, and D. Manocha, “Exact Computation of the Medial Axis of a Polyhedron,” Computer Aided Geometric Design, vol. 21, no. 1, pp. 65–98, 2004.

Digital Library

[38]

T.K. Dey and J. Sun, “Defining and Computing Curve-Skeletons with Medial Geodesic Function,” Proc. Eurographics Symp. Geometry Proc., 2006.

[39]

U. Eckhardt and G. Maderlechner, “Invariant Thinning,” Pattern Recognition and Artificial Intelligence, no. 7, pp. 1115–1144, 1993.

[40]

A.F. Frangi, W.J. Niessen, R.M. Hoogeveen, T. van Walsum, and M.A. Viergever, “Model-Based Quantitation of 3D Magnetic Resonance Angiographic Images,” IEEE Trans. Medical Imaging, vol. 18, no. 10, p. 946, 1999.

[41]

Y. Fridman, S.M. Pizer, S. Aylward, and E. Bullitt, “Extracting Branching Tubular Object Geometry via Cores,” Medical Image Analysis, vol. 8, no. 3, pp. 169–176, 2004.

[42]

D.S. Fritsch, S.M. Pizer, B.S. Morse, D.H. Eberly, and A. Liu, “The Multiscale Medial Axis and Its Applications in Image Registration,” Pattern Recognition Letters, vol. 15, pp. 445–452, 1994.

Digital Library

[43]

N. Gagvani and D. Silver, “Parameter Controlled Volume Thinning,” Graphical Models and Image Processing, vol. 61, no. 3, pp. 149–164, 1999.

Digital Library

[44]

N. Gagvani and D. Silver, “Animating Volumetric Models,” Academic Press Professional, vol. 63, no. 6, pp. 443–458, 2001.

[45]

N. Gagvani and D. Silver, “Shape-Based Volumetric Collision Detection,” Proc. IEEE Symp. Volume Visualization, 2000.

[46]

P. Giblin and B.B. Kimia, “A Formal Classification of 3D Medial Axis Points and Their Local Geometry,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 566–573, 2000.

[47]

P. Golland and W.E.L. Grimson, “Fixed Topology Skeletons,” Computer Vision and Pattern Recognition, 2000.

[48]

W. Gong and G. Bertrand, “A Simple Parallel 3D Thinning Algorithm,” Proc. IEEE Conf. Pattern Recognition, pp. 188–190, 1990.

[49]

B. Gorte and N. Pfeifer, “Structuring Laser-Scanned Trees Using 3D Mathematical Morphology,” Proc. XXth Congress of Int'l Archives of Photogrammetry, p. 929, 2004.

[50]

J. Greer, “Computer Skeletonization and Automatic Electron Density Map Analysis,” Methods in Enzymology, vol. 115, pp. 206–224, 1985.

[51]

T. Grigorishin and Y.H. Yang, “Skeletonization: An Electrostatic Field-Based Approach,” Pattern Analysis and Applications, vol. 1, pp. 163–177, 1998.

Digital Library

[52]

T. He, L. Hong, D. Chen, and Z. Liang, “Reliable Path for Virtual Endoscopy: Ensuring Complete Examination of Human Organs,” IEEE Trans. Visualization and Computer Graphics, vol. 7, no. 4, pp. 333–342, Oct.-Dec. 2001.

Digital Library

[53]

M. Hilaga, Y. Shinagawa, T. Kohmura, and T. Kunii, “Topology Matching for Fully Automatic Similarity Estimation of 3D Shapes,” Proc. SIGGRAPH, 2001.

Digital Library

[54]

L. Hong, S. Muraki, A. Kaufman, D. Bartz, and T. He, “Virtual Voyage: Interactive Navigation in the Human Colon,” Proc. SIGGRAPH, 1997.

[55]

S. Hornus, A. Angelidis, and M.-P. Cani, “Implicit Modeling Using Subdivision Curves,” The Visual Computer, vol. 19, nos. 2–3, p. 94, 2003.

[56]

P.P. Jonker, “Skeletons in N Dimensions Using Shape Primitives,” Pattern Recognition Letters, vol. 23, no. 6, p. 677, 2002.

Digital Library

[57]

A. Kanitsar, D. Fleischmann, R. Wegenkittl, P. Felkel, and M.E. Gröller, “CPR: Curved Planar Reformation,” Proc. IEEE Visualization Conf., 2002.

[58]

A. Kanitsar, R. Wegenkittl, D. Fleischmann, and M.E. Cröller, “Advanced Curved Planar Reformation: Flattening of Vascular Structures,” Proc. IEEE Visualization Conf., 2003.

[59]

S. Katz and A. Tal, “Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts,” Proc. ACM SIGGRAPH, 2003.

[60]

R.A. Katz and S.M. Pizer, “Untangling the Blum Medial Axis Transform,” Int'l J. Computer Vision, vol. 55, nos. 2–3, pp. 139–153, 2003.

[61]

D.-G. Kang and J.B. Ra, “A New Path Planning Algorithm for Maximizing Visibility in Computed Tomography Colonography,” IEEE Trans. Medical Imaging, vol. 24, no. 8, p. 957, 2005.

[62]

T.Y. Kong and A. Rosenfeld, “Digital Topology: Introduction and Survey,” Computer Vision, Graphics, and Image Processing, vol. 48, no. 3, pp. 357–393, 1989.

Digital Library

[63]

T.Y. Kong, A.W. Roscoe, and A. Rosenfeld, “Concepts of Digital Topology,” Topology and Its Applications, vol. 46, no. 3, pp. 219–262, Elsevier, 1992.

[64]

F. Lazarus and A. Verroust, “Metamorphosis of Cylinder-Like Objects,” J. Visualization and Computer Animation., vol. 8, no. 3, pp. 131–146, 1998.

[65]

F. Lazarus and A. Verroust, “Level Set Diagrams of Polyhedral Objects,” Proc. ACM Solid Modeling, 1999.

[66]

T. Lee and R.L. Kashyap, “Building Skeleton Models via 3D Medial Surface/Axis Thinning Algorithms,” CVGIP: Graphical Models and Image Processing, vol. 56, no. 6, pp. 462–478, Nov. 1994.

Digital Library

[67]

F.F. Leymarie and B.B. Kimia, “Computation of the Shock Scaffold for Unorganized Point Clouds in 3D,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2003.

[68]

F.F. Leymarie, “3D Shape Representation via Shock Flows,” PhD thesis Brown Univ., May 2003.

[69]

H. Li, “An Integrated Approach to Protein Backbone Modeling,” MS thesis Queen's Univ., Kingston, Ontario, Canada, Oct. 2002.

[70]

X. Li, T.W. Woon, and Z. Huang, “Decomposing Polygon Meshes for Interactive Applications,” Proc. ACM Symp. Interactive 3D Graphics, pp. 35–42, 2001.

[71]

J.-H. Lien and N.M. Amato, “Simultaneous Shape Decomposition and Skeletonization,” Technical Report TR05-015, Parasol Lab, Dept. of Computer Science, Texas A&M Univ., Dec. 2005.

[72]

A. Lieutier, “Any Open Bounded Subset of Rⁿ Has the Same Homotopy Type than Its Medial Axis,” Proc. ACM Shape Modeling Int'l Conf., 2003.

[73]

P. Liu, F. Wu, W. Ma, R. Liang, and M. Ouhyoung, “Automatic Animation Skeleton Construction Using Repulsive Force Field,” Proc. 11th Pacific Conf. Computer Graphics and Applications, 2003.

Digital Library

[74]

C. Lohou and G. Bertrand, “A 3D 12-Subiteration Thinning Algorithm Based on P-Simple Points,” Discrete Applied Math., vol. 139, pp. 171–195, 2004.

Digital Library

[75]

W.E. Lorensen and H.E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Proc. ACM SIGGRAPH, vol. 21, no. 4, pp. 163–169, 1987.

[76]

C.M. Ma and M. Sonka, “A Fully Parallel 3D Thinning Algorithm and Its Applications,” Computer Vision and Image Understanding, vol. 64, no. 3, pp. 420–433, 1996.

Digital Library

[77]

C.-M. Ma and S.-Y. Wan, “A Medial-Surface Oriented 3D Two-Subfield Thinning Algorithm,” Pattern Recognition Letters, vol. 22, p. 1439, 2001.

Digital Library

[78]

C.-M. Ma, S.-Y. Wan, and H.-K. Chang, “Extracting Medial Curves on 3D Images,” Pattern Recognition Letters, vol. 23, p. 895, 2002.

Digital Library

[79]

C.-M. Ma, S.-Y. Wan, and J.-D. Lee, “Three-Dimensional Topology Preserving Reduction on the 4-Subfields,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 12, p. 1594, Dec. 2002.

Digital Library

[80]

W. Ma, F. Wu, and M. Ouhyoung, “Skeleton Extraction of 3D Objects with Radial Basis Functions,” Proc. IEEE Ini'l Conf. Shape Modeling and Applications, 2003.

[81]

G. Malandain and S. Fernandez-Vidal, Euclidean Skeletons, Image and Vision Computing, vol. 16, pp. 317–327, 1998.

[82]

A. Manzanera, T. Bernard, F. Preteux, and B. Longuet, “A Unified Mathematical Framework for a Compact and Fully Parallel n-D Skeletonization Procedure,” Proc. Vision Geometry VIII, pp. 57–68, 1999.

[83]

Maya, Autodesk.http://www.autodesk.com/maya. 2006.

[84]

D.G. Morgenthaler, “Three-Dimensional Simple Points: Serial Erosion, Parallel Thinning and Skeletonization,” TR-1005, Computer Vision Lab., Univ. of Maryland, 1981.

[85]

B.S. Morse, S.M. Pizer, D.T. Puff, and C. Gu, “Zoom-Invariant Vision of Figural Shape: Effects on Cores of Image Disturbances,” Computer Vision and Image Understanding, vol. 69, no. 1, p. 72, 1998.

Digital Library

[86]

M. Mortara and G. Patané, “Shape-Covering for Skeleton Extraction,” Int'l J. Shape Modeling, vol. 8, no. 2, p. 139, 2002.

[87]

M. Näf, O. Kubler, R. Kikinis, M.E. Shenton, and G. Szekely, “Characterization and Recognition of 3D Organ Shape in Medical Image Analysis Using Skeletonization,” Proc. IEEE Workshop Math. Methods in Biomedical Image Analysis, pp. 139–150, 1996.

[88]

C.W. Niblack, P.B. Gibbons, and D.W. Capson, “Generating Skeletons and Centerlines from the Distance Transform,” Graphical Models and Image Processing, vol. 54, no. 5, pp. 420–437, 1992.

Digital Library

[89]

I. Nyström, G. Sanniti di Baja, and S. Svensson, “Representing Volumetric Vascular Structures Using Curve Skeletons,” Proc. Ini'l Conf. Image Analysis and Processing, p. 495, 2001.

[90]

I. Nyström and Ö. Smedby, “Skeletonization of Volumetric Vascular Images-Distance Information Utilized for Visualization,” J. Combinatorial Optimization, vol. 5, pp. 27–41, 2001.

[91]

R. Ogniewicz, “A Multiscale MAT from Voronoi Diagrams: The Skeleton-Space and Its Application to Shape Description and Decomposition,” Aspects of Visual Form Processing, World Scientific, p. 430, 1994.

[92]

R. Ogniewicz and M. Ilg, “Voronoi Skeletons: Theory and Applications,” Proc. Conf. Computer Vision and Pattern Recognition, p. 63, 1992.

[93]

R. Ogniewicz and O. Kübler, “Hierarchic Voronoi Skeletons,” Pattern Recognition, vol. 28, no. 3, p. 343, 1995.

[94]

K. Palágyi and A. Kuba, “Directional 3D Thinning Using 8 Subiterations,” Lecture Notes in Computer Science, vol. 1568, pp. 325–336, 1999.

[95]

K. Palágyi and A. Kuba, “A Parallel 3D 12-Subiteration Thinning Algorithm,” Graphical Models and Image Processing, vol. 61, no. 4, pp. 199–221, 1999.

Digital Library

[96]

D. Perchet, C.I. Fetita, and F. Preteux, “Advanced Navigation Tools for Virtual Bronchoscopy,” Proc. SPIE Conf. Image Processing: Algorithms and Systems III, 2004.

[97]

S.M. Pizer, D. Eberly, and D.S. Fritsch, “Zoom-Invariant Vision of Figural Shape: The Mathematics of Cores,” Computer Vision and Image Understanding, vol. 69, no. 1, p. 55, 1998.

Digital Library

[98]

S.M. Pizer, G. Gerig, S. Joshi, and S. Aylward, “Multiscale Medial Shape-Based Analysis of Image Objects,” Proc. IEEE, vol. 91, no. 10, pp. 1670–1679, 2003.

[99]

S.M. Pizer, D. Fritsch, P. Yushkevich, V. Johnson, and E. Chaney, “Segmentation, Registration, and Measurement of Shape Variation via Image Object Shape,” IEEE Trans. Medical Imaging, vol. 18, pp. 851–865, 1999.

[100]

S.M. Pizer, A.L. Thall, and D.T. Chen, “M-Reps: A New Object Representation for Graphics,” Technical Report TR99-030, 17, Univ. of North Carolina, Chapel Hill, 1999.

[101]

C. Pudney, “Distance-Ordered Homotopic Thinning: A Skeleto-nization Algorithm for 3D Digital Images,” Computer Vision and Image Understanding, vol. 72, no. 3, pp. 404–413, 1998.

Digital Library

[102]

J.M. Reddy and G.M. Turkiyyah, “Computation of 3D Skeletons Using a Generalized Delaunay Triangulation Technique,” Computer-Aided Design, vol. 27, no. 9, pp. 677–694, 1995.

[103]

M. Sabry Hassouna and A.A. Farag, “Robust Centerline Extraction Framework Using Level Sets,” Proc. Conf. Computer Vision and Pattern Recognition, pp. 458–465, 2005.

[104]

P.K. Saha, B.B. Chaudhuri, and D. Dutta Majumder, “A New Shape Preserving Parallel Thinning Algorithm for 3D Digital Images,” Pattern Recognition, vol. 30, no. 12, pp. 1939–1955, 1997.

[105]

P.K. Saha and B.B. Chaudhuri, “3D Digital Topology under Binary Transformation with Applications,” Computer Vision and Image Understanding, vol. 63, no. 3, pp. 418–429, 1996.

Digital Library

[106]

T. Saito and J. Toriwaki, “New Algorithms for Euclidean Distance Transformation of an n-Dimensional Digitized Picture with Applications,” Pattern Recognition, vol. 27, pp. 1551–1565, 1994.

[107]

G. Sanniti di Baja and S. Svensson, “A New Shape Descriptor for Surfaces in 3D Images,” Pattern Recognition Letters, vol. 23, p. 703, 2002.

[108]

K. Santilli, K. Bemis, D. Silver, J. Dastur, and P. Rona, “Generating Realistic Images from Hydrothermal Plume Data,” Proc. IEEE Visualization Conf., 2004.

[109]

H. Schirmacher, M. Zöckler, D. Stalling, and H. Hege, “Boundary Surface Shrinking-A Continuous Approach to 3D Center Line Extraction,” Proc. Image and Multidimensional Signal Processing Symp., pp. 25–28, 1998.

[110]

M.P.P. Schlicher, E. Bouts, and P.W. Verbeek, “Fast Analytical Medial-Axis Localization in Convex Polyhedra,” Proc. Ini'l Conf. Pattern Recognition, pp. 55–61, 1996.

[111]

J.A. Sethian, “Fast Marching Methods,” SIAM Rev., vol. 41, no. 2, p. 199, 1999.

Digital Library

[112]

E.C. Sherbrooke, N.M. Patrikalakis, and E. Brisson, “Computation of the Medial Axis Transform of 3-D Polyhedra,” Proc. Ini'l Conf. Shape Modeling and Applications, 1995.

[113]

P. Shilane, P. Min, M. Kazhdan, and T. Funkhouser, “The Princeton Shape Benchmark,” Proc. Shape Modeling Ini'l Conf., 2004.

[114]

D. Silver and N. Gagvani, “Unwinding the Colon,” Proc. Medicine Meets Virtual Reality (MMVR), 2002.

[115]

E. Sorantin et al., “Spiral-CT-Based Assessment of Tracheal Stenoses Using 3D-Skeletonization,” IEEE Trans. Medical Imaging, vol. 21, no. 3, p. 263, 2002.

[116]

M. Sramek and A.E. Kaufman, “Alias-Free Voxelization of Geometric Objects,” IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 3, pp. 251–267, July-Sept. 1999.

Digital Library

[117]

M. Straka, M. Cervenansky, A. La Cruz, A. Kochl, M. Sramek, E. Groller, and D. Fleischmann, “The VesselGlyph: Focus & Context Visualization in CT-Angiography,” Proc. IEEE Visualization Conf., 2004.

[118]

H. Sundar, D. Silver, N. Gagvani, and S. Dickinson, “Skeleton Based Shape Matching and Retrieval,” Proc. Shape Modeling Ini'l Conf., 2003.

[119]

K. Suresh, “Automating the CAD/CAE Dimensional Reduction Process,” Proc. ACM Symp. Solid Modeling and Applications, 2003.

[120]

S. Svensson, I. Nystrom, and G. Sanniti di Baja, “Curve-Skeletonization of Surface-Like Objects in 3D Images Guided by Voxel Classification,” Pattern Recognition Letters, pp. 1419–1426, 2002.

[121]

S. Svensson, C. Arcelli, and G. Sanniti di Baja, “Finding Cavities and Tunnels in 3D Complex Objects,” Proc. Ini'l Conf. Image Analysis and Processing, pp. 342–347, 2003.

[122]

A. Tal and S. Katz, “Hierarchical Mesh Decomposition Using Fuzzy Clustering and Cuts,” ACM Trans. Graphics, vol. 22, no. 3, pp. 954–961, 2003.

[123]

A. Telea and A. Vilanova, “A Robust Level-Set Algorithm for Centerline Extraction,” Proc. Eurographics/IEEE Symp. Data Visualization, 2003.

[124]

A. Telea and J.J. van Wijk, “An Augmented Fast Marching Method for Computing Skeletons and Centerlines,” Proc. Symp. Data Vision, 2002.

[125]

C. Theobalt, E. de Aguiar, M.A. Magnor, H. Theisel, and H.-P. Seidel, “Marker-Free Kinematic Skeleton Estimation from Sequences of Volume Data,” Virtual Reality Software and Technology, p. 57, 2004.

[126]

Y.F. Tsao and K.S. Fu, “A Parallel Thinning Algorithm for 3D Pictures,” Computer Vision, Graphics, and Image Processing, vol. 17, pp. 315–331, 1981.

[127]

A. Verroust and F. Lazarus, “Extracting Skeletal Curves from 3D Scattered Data,” The Visual Computer, vol. 16, pp. 15–25, 2000.

Digital Library

[128]

B. Vrolijk, F. Reinders, and F.H. Post, “Feature Tracking With Skeleton Graphs,” Data Visualization: The State of the Art, pp. 37–52, Kluwer Academic, 2003.

[129]

L. Wade and R.E. Parent, “Automated Generation of Control Skeletons for Use in Animation,” The Visual Computer, vol. 18, no. 2, pp. 97–110, 2002.

Digital Library

[130]

M. Wan, F. Dachille, and A. Kaufman, “Distance-Field Based Skeletons for Virtual Navigation,” Proc. IEEE Visualization Conf., 2001.

[131]

R. Webster, M. Harris, R. Shenk, J. Blumenstock, J. Gerber, C. Billman, A. Benson, and R. Haluck, “Using an Approximation to the Euclidean Skeleton for Efficient Collision Detection and Tissue Deformations in Surgical Simulators,” Medicine Meets Virtual Reality, vol. 13, IOS Press, 2005.

[132]

F.-C. Wu, W.-C. Ma, R.-H. Liang, B.-Y. Chen, and M. Ouhyoung, “Domain Connected Graph: The Skeleton of a Closed 3D Shape for Animation,” The Visual Computer, vol. 22, no. 2, p. 117, 2006.

Digital Library

[133]

F. Wu, W.-C. Ma, P. Liou, R. Liang, and M. Ouhyoung, “Skeleton Extraction of 3D Objects with Visible Repulsive Force,” Proc. Eurographics Symp. Geometry Processing, 2003.

[134]

Y. Xiao, P. Siebert, and N. Werghi, “A Discrete Reeb Graph Approach for the Segmentation of Human Body Scans,” Proc. Ini'l Conf. 3D Digital Imaging and Modeling, p. 378, 2003.

[135]

Y. Yang, O. Brock, and R.N. Moll, “Efficient and Robust Computation of an Approximated Medial Axis,” Proc. Solid Modeling and Applications Conf., 2004.

[136]

Y. Zhao, H. Ong, T. Tan, and Y. Xiao, “Intuitive Interfaces for Animation: Interactive Control of Component-Based Morphing,” Proc. ACM SIGGRAPH, 2003.

[137]

Y. Zhou, A. Kaufman, and A.W. Toga, “Three-Dimensional Skeleton and Centerline Generation Based on an Approximate Minimum Distance Field,” The Visual Computer, vol. 14, pp. 303–314, 1998.

[138]

Y. Zhou and A.W. Toga, “Efficient Skeletonization of Volumetric Objects,” IEEE Trans. Visualization and Computer Graphics, vol. 5, no. 3, pp. 196–209, July-Sept. 1999.

Digital Library

[139]

Online resource: http://www.caip.rutgers.edu/=cornea/CurveSkeletons, 2006.

Cited By

Alvarez LTrujillo AMonzón NMorel J(2024)Generation and Editing of 2D Shapes Using a Branched RepresentationACM Transactions on Multimedia Computing, Communications, and Applications10.1145/369163520:12(1-25)Online publication date: 26-Nov-2024
https://dl.acm.org/doi/10.1145/3691635
Zhang MZhang HYou XYang GGu Y(2024)Implicit Representation Embraces Challenging Attributes of Pulmonary Airway Tree StructuresMedical Image Computing and Computer Assisted Intervention – MICCAI 202410.1007/978-3-031-72378-0_51(546-556)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-72378-0_51
Wen QTafrishi SJi ZLai Y(2024)What Criteria Define an Ideal Skeletonisation Reference in Object Point Clouds?Towards Autonomous Robotic Systems10.1007/978-3-031-72059-8_35(422-433)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72059-8_35
Show More Cited By

Index Terms

Curve-Skeleton Properties, Applications, and Algorithms
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Shape representations
      2. Image and video acquisition
        3D imaging
  2. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Index terms have been assigned to the content through auto-classification.

Recommendations

Curve skeleton extraction from incomplete point cloud

We present an algorithm for curve skeleton extraction from imperfect point clouds where large portions of the data may be missing. Our construction is primarily based on a novel notion of generalized rotational symmetry axis (ROSA) of an oriented point ...
Curve skeleton extraction by graph contraction
CVM'12: Proceedings of the First international conference on Computational Visual Media

In this paper, we propose a practical algorithm for extracting curve skeletons from a 3D shape represented by a triangular mesh. We first construct an initial skeleton graph by copying the connectivity and geometry information from the input mesh. We ...
Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 13, Issue 3

May-June 2007

238 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © 2024.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2007

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

122
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alvarez LTrujillo AMonzón NMorel J(2024)Generation and Editing of 2D Shapes Using a Branched RepresentationACM Transactions on Multimedia Computing, Communications, and Applications10.1145/369163520:12(1-25)Online publication date: 26-Nov-2024
https://dl.acm.org/doi/10.1145/3691635
Zhang MZhang HYou XYang GGu Y(2024)Implicit Representation Embraces Challenging Attributes of Pulmonary Airway Tree StructuresMedical Image Computing and Computer Assisted Intervention – MICCAI 202410.1007/978-3-031-72378-0_51(546-556)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-72378-0_51
Wen QTafrishi SJi ZLai Y(2024)What Criteria Define an Ideal Skeletonisation Reference in Object Point Clouds?Towards Autonomous Robotic Systems10.1007/978-3-031-72059-8_35(422-433)Online publication date: 21-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-72059-8_35
Chu YWang WLi L(2023)Robustly Extracting Concise 3D Curve Skeletons by Enhancing the Capture of Prominent FeaturesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2022.316196229:8(3472-3488)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TVCG.2022.3161962
Gratacós GChakrabarti AJu T(2023)Tree Recovery by Dynamic ProgrammingIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.329986845:12(15870-15882)Online publication date: 28-Jul-2023
https://dl.acm.org/doi/10.1109/TPAMI.2023.3299868
Bertram JZambreno JWei P(2023)Efficient Unmanned Aerial Systems Navigation With Collision Avoidance in Dense Urban EnvironmentsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.328113124:8(8163-8173)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3281131
Yang CIndurkhya BSee JGao BKe YBoukhers ZYang ZGrzegorzek M(2023)Skeleton Ground Truth Extraction: Methodology, Annotation Tool and BenchmarksInternational Journal of Computer Vision10.1007/s11263-023-01926-3132:4(1219-1241)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s11263-023-01926-3
Pandey KBærentzen JSingh K(2022)Face Extrusion Quad MeshesACM SIGGRAPH 2022 Conference Proceedings10.1145/3528233.3530754(1-9)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3528233.3530754
He YZhao ZCai KKirby JXiong YXie Y(2022)A thinning algorithm based approach to controlling structural complexity in topology optimizationFinite Elements in Analysis and Design10.1016/j.finel.2022.103779207:COnline publication date: 15-Sep-2022
https://dl.acm.org/doi/10.1016/j.finel.2022.103779
Giordano ADiourté ABordreuil CBugarin FSegonds S(2022)Thermal Scalar Field for Continuous Three-dimensional Toolpath Strategy Using Wire Arc Additive Manufacturing for Free-form Thin PartsComputer-Aided Design10.1016/j.cad.2022.103337151:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.cad.2022.103337
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents