research-article

Curve skeleton extraction from incomplete point cloud

Authors:

Andrea Tagliasacchi,

Daniel Cohen-OrAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 28, Issue 3

Article No.: 71, Pages 1 - 9

https://doi.org/10.1145/1531326.1531377

Published: 27 July 2009 Publication History

Abstract

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 set. Specifically, given a subset S of oriented points, we introduce a variational definition for an oriented point that is most rotationally symmetric with respect to S. Our formulation effectively utilizes normal information to compensate for the missing data and leads to robust curve skeleton computation over regions of a shape that are generally cylindrical. We present an iterative algorithm via planar cuts to compute the ROSA of a point cloud. This is complemented by special handling of non-cylindrical joint regions to obtain a centered, topologically clean, and complete 1D skeleton. We demonstrate that quality curve skeletons can be extracted from a variety of shapes captured by incomplete point clouds. Finally, we show how our algorithm assists in shape completion under these challenges by developing a skeleton-driven point cloud completion scheme.

Supplementary Material

JPG File (tps080_09.jpg)

Download
13.03 KB

Zip (71-353.zip)

Supplemental material

Download
18.01 MB

MP4 File (tps080_09.mp4)

Download
59.84 MB

References

[1]

Amenta, N., and Kil, Y. J. 2004. Defining point-set surfaces. ACM Trans. on Graph. 23, 3, 264--270.

Digital Library

[2]

Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. on Graph. 27, 3, 44:1--44:10.

Digital Library

[3]

Blum, H. 1967. A transformation for extracting new descriptors of shape. Models for the perception of speech and visual form. MIT Press, 362--380.

[4]

Bouix, S., Siddiqi, K., Tannenbaum, A., and Zucker, S. 2006. Medial axis computation and evolution. Statistics and Analysis of Shapes.

[5]

Carr, J. C., Beatson, R. K., Cherrie, J. B., Mitchell, T. J., Fright, W. R., McCallum, B. C., and Evans, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proc. of SIGGRAPH, 67--76.

Digital Library

[6]

Chuang, J.-H., Ahuja, N., Lin, C.-C., Tsai, C.-H., and Chen, C.-H. 2004. A potential-based generalized cylinder representation. Computers & Graphics 28, 6, 907--918.

Digital Library

[7]

Cornea, N. D., Min, P., and Silver, D. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Vis. & Comp. Graphics 13, 3, 530--548.

Digital Library

[8]

de Aguiar, E., Theobalt, C., Thrun, S., and Seidel, H.-P. 2008. Automatic conversion of mesh animations into skeleton-based animations. Computer Graphics Forum (Proc. of Eurographics) 27, 2 (4), 389--397.

[9]

Dey, T., and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. In Symp. on Geom. Proc., 143--152.

Digital Library

[10]

Giblin, P. J., and Brassett, S. A. 1985. Local symmetry of plane curves. American Mathematical Monthly, 689--707.

[11]

Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proc. of SIGGRAPH, 203--212.

Digital Library

[12]

Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Proc. of SIGGRAPH, 71--78.

Digital Library

[13]

James, D., and Twigg, C. 2005. Skinning mesh animations. ACM Trans. on Graph. 24, 3, 399--407.

Digital Library

[14]

Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. on Graph. 22, 3, 954--961.

Digital Library

[15]

Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3D shape matching. In Symp. on Geom. Proc., 115--123.

Digital Library

[16]

Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Symp. on Geom. Proc., 61--70.

Digital Library

[17]

Kim, Y. J., Varadhan, G., Lin, M. C., and Manocha, D. 2003. Fast swept volume approximation of complex polyhedral models. In Proc. of Symp. on Solid Modeling and App., 11--22.

Digital Library

[18]

Lee, I. 2000. Curve reconstruction from unorganized points. Computer Aided Geometric Design 17, 2, 161--177.

Digital Library

[19]

Lehtinen, J., Zwicker, M., Turquin, E., Kontkanen, J., Durand, F., Sillion, F., and Aila, T. 2008. A meshless hierarchical representation for light transport. ACM Trans. on Graph. 27, 3, 37:1--37:10.

Digital Library

[20]

Lewis, J. P., Cordner, M., and Fong, N. 2000. Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation. In Proc. of SIGGRAPH, 165--172.

Digital Library

[21]

Li, X., Woon, T., Tan, T., and Huang, Z. 2001. Decomposing polygon meshes for interactive applications. In Proc. of Symposium on Interactive 3D graphics, 35--42.

Digital Library

[22]

Lipman, Y., Cohen-Or, D., Levin, D., and Tal-Ezer, H. 2007. Parameterization-free projection for geometry reconstruction. ACM Trans. on Graph. 26(3), 22:1--22:6.

Digital Library

[23]

Lu, L., Choi, Y.-K., Wang, W., and Kim, M.-S. 2007. Variational 3D shape segmentation for bounding volume computation. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 329--338.

[24]

Malandain, G., and Fern&#225;ndez-Vidal, S. 1998. Euclidean skeletons. Image and Vision Computing 16, 5, 317--327.

[25]

Mitra, N., Guibas, L., and Pauly, M. 2006. Partial and approximate symmetry detection for 3D geometry. ACM Trans. on Graph. 25, 3, 560--568.

Digital Library

[26]

Mitra, N. J., Fl&#246;ry, S., Ovsjanikov, M., Gelfand, N., Guibas, L., and Pottmann, H. 2007. Dynamic geometry registration. In Symp. on Geom. Proc., 173--182.

Digital Library

[27]

Nehab, D., Rusinkiewicz, S., Davis, J., and Ramamoorthi, R. 2005. Efficiently combining positions and normals for precise 3D geometry. ACM Trans. on Graph. 24, 3, 536--543.

Digital Library

[28]

Ogniewicz, R., Ilg, M., and Zurich, E. 1992. Voronoi skeletons: theory and applications. In Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., 63--69.

[29]

Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. In Computer Graphics Forum (Proc. of Symp. on Geom. Proc.), vol. 27, 1341--1348.

Digital Library

[30]

Patane, G., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graph computation based on a minimal contouring. In Proc. IEEE Conf. on Shape Modeling and App., 73--82.

[31]

Pekelny, Y., and Gotsman, C. 2008. Articulated object reconstruction and motion capture from depth video. Computer Graphics Forum (Proc. of Eurographics) 27, 2, 399--408.

[32]

Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Trans. on Graph. 25, 3, 549--559.

Digital Library

[33]

Raab, R., Gotsman, C., and Sheffer, A. 2004. Virtual woodwork: Making toys from geometric models. Int. J. of Shape Modeling 10, 1, 1--30.

[34]

Sharf, A., Lewiner, T., Shamir, A., and Kobbelt, L. 2007. On-the-fly curve-skeleton computation for 3D shapes. Computer Graphics Forum (Proc. of Eurographics) 26, 3, 323--328.

[35]

Sharf, A., Lewiner, T., Shklarski, G., Toledo, S., and Cohen-Or, D. 2007. Interactive topology-aware surface reconstruction. ACM Trans. on Graph. 26, 3, 43:1--43:10.

Digital Library

[36]

Sharf, A., Alcantara, D. A., Lewiner, T., Greif, C., Sheffer, A., Amenta, N., and Cohen-Or, D. 2008. Space-time surface reconstruction using incompressible flow. ACM Trans. on Graph. 27, 5, 110:1--110:10.

Digital Library

[37]

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

[38]

Simari, P. D., and Singh, K. 2005. Extraction and remeshing of ellipsoidal representations from mesh data. In Proc. of Graphics Interface, 161--168.

Digital Library

[39]

Sorkine, O., and Cohen-Or, D. 2004. Least-squares meshes. In Proc. IEEE Conf. on Shape Modeling and App., 191--199.

Digital Library

[40]

Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Proc. of Int. Conf. on Comp. Vis., vol. 2, 1824--1831.

Digital Library

[41]

Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L., and Schilling, A. 2007. Reconstruction of deforming geometry from time-varying point clouds. In Symp. on Geom. Proc., 49--58.

Digital Library

Cited By

Lai QXin QTian YChen XLi YWu R(2025)Structural Analysis and 3D Reconstruction of Underground Pipeline Systems Based on LiDAR Point CloudsRemote Sensing10.3390/rs1702034117:2(341)Online publication date: 20-Jan-2025
https://doi.org/10.3390/rs17020341
Dutta SRussig BGumhold S(2025)Enhanced Plant Phenotyping Through Spatio-Temporal Point Cloud RegistrationAdvances in Computer Graphics10.1007/978-3-031-81806-6_27(358-370)Online publication date: 27-Feb-2025
https://doi.org/10.1007/978-3-031-81806-6_27
Wen QTafrishi SJi ZLai Y(2024)GLSkeleton: A Geometric Laplacian-Based Skeletonisation Framework for Object Point CloudsIEEE Robotics and Automation Letters10.1109/LRA.2024.33841289:5(4615-4622)Online publication date: May-2024
https://doi.org/10.1109/LRA.2024.3384128
Show More Cited By

Index Terms

Curve skeleton extraction from incomplete point cloud
1. Computing methodologies
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

L₁-medial skeleton of point cloud

We introduce L₁-medial skeleton as a curve skeleton representation for 3D point cloud data. The L₁-median is well-known as a robust global center of an arbitrary set of points. We make the key observation that adapting L₁-medians locally to a point set ...
Curve skeleton extraction from incomplete point cloud
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

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 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 ACM Transactions on Graphics

ACM Transactions on Graphics Volume 28, Issue 3

August 2009

750 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1531326

Issue’s Table of Contents

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2009

Published in TOG Volume 28, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

198
Total Citations
View Citations
3,000
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)13

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lai QXin QTian YChen XLi YWu R(2025)Structural Analysis and 3D Reconstruction of Underground Pipeline Systems Based on LiDAR Point CloudsRemote Sensing10.3390/rs1702034117:2(341)Online publication date: 20-Jan-2025
https://doi.org/10.3390/rs17020341
Dutta SRussig BGumhold S(2025)Enhanced Plant Phenotyping Through Spatio-Temporal Point Cloud RegistrationAdvances in Computer Graphics10.1007/978-3-031-81806-6_27(358-370)Online publication date: 27-Feb-2025
https://doi.org/10.1007/978-3-031-81806-6_27
Wen QTafrishi SJi ZLai Y(2024)GLSkeleton: A Geometric Laplacian-Based Skeletonisation Framework for Object Point CloudsIEEE Robotics and Automation Letters10.1109/LRA.2024.33841289:5(4615-4622)Online publication date: May-2024
https://doi.org/10.1109/LRA.2024.3384128
Pandey SColliaux DChaudhury A(2024)Spatio-Temporal Correspondence Estimation of Growing Plants by Hausdorff Distance based Skeletonization for Organ Tracking2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10610490(13625-13631)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10610490
Hui ZHe YXia YHui TXia Y(2024)A Robust Skeleton Lines Extraction Method for Individual Tree Modeling Using Terrestrial LiDAR Point Clouds2024 IEEE International Conference on Image Processing Challenges and Workshops (ICIPCW)10.1109/ICIPCW64161.2024.10769128(4110-4114)Online publication date: 27-Oct-2024
https://doi.org/10.1109/ICIPCW64161.2024.10769128
Jignasu ABalu ASarkar SHegde CGanapathysubramanian BKrishnamurthy A(2024)SDFConnect: Neural Implicit Surface Reconstruction of a Sparse Point Cloud with Topological Constraints2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW)10.1109/CVPRW63382.2024.00536(5271-5279)Online publication date: 17-Jun-2024
https://doi.org/10.1109/CVPRW63382.2024.00536
Wu SYang QRen LLiu JYuan JLuo Z(2024)3D Human Curve Skeleton Extraction Based on Solid-State LiDARIEEE Access10.1109/ACCESS.2024.345008412(120899-120912)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3450084
fu DXia RZhao HWang FZhao LZhang TChen Y(2024)Extraction of Complex Pipeline Features fromIncomplete Point CloudsMeasurement Science and Technology10.1088/1361-6501/ad7482Online publication date: 28-Aug-2024
https://doi.org/10.1088/1361-6501/ad7482
Li MLi ZZhang MLiu QLi M(2024)Efficient shrub modelling based on terrestrial laser scanning (TLS) point cloudsInternational Journal of Remote Sensing10.1080/01431161.2024.230563345:4(1148-1169)Online publication date: 2-Feb-2024
https://doi.org/10.1080/01431161.2024.2305633
Ding CLiu YCao TWang J(2024)Aero-engine pipe gap automatic detection based on 3D scanning point cloudsMeasurement10.1016/j.measurement.2023.113732224(113732)Online publication date: Jan-2024
https://doi.org/10.1016/j.measurement.2023.113732
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents