Curve Skeleton Extraction Via K–Nearest–Neighbors Based Contraction

Zhou, Jianling; Liu, Ji; Zhang, Min

doi:10.34768/amcs-2020-0010

Abstract

We propose a skeletonization algorithm that is based on an iterative points contraction. We make an observation that the local center that is obtained via optimizing the sum of the distance to k nearest neighbors possesses good properties of robustness to noise and incomplete data. Based on such an observation, we devise a skeletonization algorithm that mainly consists of two stages: points contraction and skeleton nodes connection. Extensive experiments show that our method can work on raw scans of real-world objects and exhibits better robustness than the previous results in terms of extracting topology-preserving curve skeletons.

References

Au, O.K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D. and Lee, T.-Y. (2008). Skeleton extraction by mesh contraction, ACM Transactions on Graphics27(3): 44.10.1145/1360612.1360643
Search in Google Scholar Back to article
Belter, D., Łabecki, P., Fankhauser, P. and Siegwart, R. (2016). RGB-D terrain perception and dense mapping for legged robots, International Journal of Applied Mathematics and Computer Science26(1): 81–97, DOI: 10.1515/amcs-2016-0006.10.1515/amcs-2016-0006
Search in Google Scholar Back to article
Bucksch, A., Lindenbergh, R. and Menenti, M. (2010). Skeltre: Robust skeleton extraction from imperfect point clouds, The Visual Computer26(10): 1283–1300.10.1007/s00371-010-0520-4
Search in Google Scholar Back to article
Cao, J., Tagliasacchi, A., Olson, M. and Zhang, H. (2010). Point cloud skeletons via Laplacian based contraction, Shape Modeling International (SMI 2010), Aix-en-Provence, France, pp. 187–197.
Search in Google Scholar Back to article
Cornea, N.D., Silver, D. and Min, P. (2007). Curve-skeleton properties, applications, and algorithms, IEEE Transactions on Visualization and Computer Graphics13(3): 530–548.10.1109/TVCG.2007.1002
Search in Google Scholar Back to article
Desbrun, M., Meyer, M., Schroder, P. and Barr, A.H. (1999). Implicit fairing of irregular meshes using diffusion and curvature flow, Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, CA, USA, pp. 317–324.
Search in Google Scholar Back to article
Fuhrmann, S., Langguth, F. and Goesele, M. (2014). MVE—a multi-view reconstruction environment, in R. Klein and P. Santos (Eds), Eurographics Workshop on Graphics and Cultural Heritage, Eurographics Association, Strasbourg, pp. 11–18.
Search in Google Scholar Back to article
Huang, H., Li, D., Zhang, H., Ascher, U. and Cohen-Or, D. (2009). Consolidation of unorganized point clouds for surface reconstruction, ACM Transactions on Graphics (TOG)28(5): 176.10.1145/1618452.1618522
Search in Google Scholar Back to article
Huang, H., Wu, S., Cohenor, D., Gong, M., Zhang, H., Li, G. and Chen, B. (2013). L1-medial skeleton of point cloud, ACM Transactions on Graphics32(4): 65.10.1145/2461912.2461913
Search in Google Scholar Back to article
Lazarus, F. and Verroust, A. (1999). Level set diagrams of polyhedral objects, Proceedings of the 5th ACM Symposium on Solid Modeling and Applications, Ann Arbor, MI, USA, pp. 130–140.
Search in Google Scholar Back to article
Lee, I.-K. (2000). Curve reconstruction from unorganized points, Computer Aided Geometric Design17(2): 161–177.10.1016/S0167-8396(99)00044-8
Search in Google Scholar Back to article
Levet, F. and Granier, X. (2007). Improved skeleton extraction and surface generation for sketch-based modeling, Graphics Interface 2007, New York, NY, USA, pp. 27–33.
Search in Google Scholar Back to article
Li, L. and Wang, W. (2018). Improved use of LOP for curve skeleton extraction, Computer Graphics Forum37(7): 313–323, DOI: 10.1111/cgf.13570.10.1111/cgf.13570
Search in Google Scholar Back to article
Lipman, Y., Cohen-Or, D., Levin, D. and Tal-Ezer, H. (2007). Parameterization-free projection for geometry reconstruction, ACM Transactions on Graphics26(3): 22.10.1145/1276377.1276405
Search in Google Scholar Back to article
Livny, Y., Yan, F., Olson, M., Chen, B., Zhang, H. and Elsana, J. (2010). Automatic reconstruction of tree skeletal structures from point clouds, International Conference on Computer Graphics and Interactive Techniques, Seoul, South Korea, p. 151.
Search in Google Scholar Back to article
Seitz, S.M., Curless, B., Diebel, J., Scharstein, D. and Szeliski, R. (2006). A comparison and evaluation of multi-view stereo reconstruction algorithms, CVPR 2006, New York, NY, USA, pp. 519–528.
Search in Google Scholar Back to article
Sharf, A., Lewiner, T., Shamir, A. and Kobbelt, L. (2007). On-the-fly curve-skeleton computation for 3D shapes, Computer Graphics Forum26(3): 323–328, DOI: 10.1111/j.1467-8659.2007.01054.x.10.1111/j.1467-8659.2007.01054.x
Search in Google Scholar Back to article
Song, C., Pang, Z., Jing, X. and Xiao, C. (2018). Distance field guided l₁-median skeleton extraction, The Visual Computer34(2): 243–255.10.1007/s00371-016-1331-z
Search in Google Scholar Back to article
Tagliasacchi, A., Alhashim, I., Olson, M. and Zhang, H. (2012). Mean curvature skeletons, Computer Graphics Forum31(5): 1735–1744, DOI: 10.1111/j.1467-8659.2012.03178.x.10.1111/j.1467-8659.2012.03178.x
Search in Google Scholar Back to article
Tagliasacchi, A., Delame, T., Spagnuolo, M., Amenta, N. and Telea, A. (2016). 3D skeletons: A state-of-the-art report, Computer Graphics Forum35(2): 573–597, DOI: 10.1111/cgf.12865.10.1111/cgf.12865
Search in Google Scholar Back to article
Tagliasacchi, A., Zhang, H. and Cohenor, D. (2009). Curve skeleton extraction from incomplete point cloud, International Conference on Computer Graphics and Interactive Techniques, New Orleans, LA, USA, p. 71.
Search in Google Scholar Back to article
Verroust, A. and Lazarus, F. (2000). Extracting skeletal curves from 3D scattered data, The Visual Computer16(1): 15–25.10.1007/PL00007210
Search in Google Scholar Back to article
Wang, Y., Chang, X., Ning, X., Zhang, J., Shi, Z., Zhao, M. and Wang, Q. (2012). Tree branching reconstruction from unilateral point clouds, in Z. Pan et al. (Eds.), Transactions on Edutainment VIII, Springer, Berlin/Heidelberg, pp. 250–263.10.1007/978-3-642-31439-1_23
Search in Google Scholar Back to article
Weber, A. and Friedrich, C.J. (1929). Alfred Weber’s Theory of the Location of Industries, University of Chicago Press, Chicago, IL.
Search in Google Scholar Back to article
Yan, Y., Sykes, K., Chambers, E., Letscher, D. and Ju, T. (2016). Erosion thickness on medial axes of 3D shapes, ACM Transactions on Graphics35(4): 38.10.1145/2897824.2925938
Search in Google Scholar Back to article
Zhu, Q., Feng, J. and Huang, J. (2016). Natural neighbor: A self-adaptive neighborhood method without parameter k, Pattern Recognition Letters80: 30–36.10.1016/j.patrec.2016.05.007
Search in Google Scholar Back to article

Curve Skeleton Extraction Via K–Nearest–Neighbors Based Contraction

Abstract

Paradigm

My account