Curve skeleton extraction via k-nearest-neighbors based contraction

Zhou, Jianling ; Liu, Ji ; Zhang, Min

International Journal of Applied Mathematics and Computer Science, Tome 30 (2020) no. 1, pp. 123-132.

Résumé

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.

Détail

Keywords: curve skeleton, points contraction, point cloud, k nearest neighbors
Mots-clés : szkieletyzacja, chmura punktów, metoda k najbliższych sąsiadów

Bibliographie

[1] 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 Graphics 27(3): 44.

[2] 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 Science 26(1): 81–97, DOI: 10.1515/amcs-2016-0006.

[3] Bucksch, A., Lindenbergh, R. and Menenti, M. (2010). Skeltre: Robust skeleton extraction from imperfect point clouds, The Visual Computer 26(10): 1283–1300.

[4] 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.

[5] Cornea, N.D., Silver, D. and Min, P. (2007). Curve-skeleton properties, applications, and algorithms, IEEE Transactions on Visualization and Computer Graphics 13(3): 530–548.

[6] 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.

[7] 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.

[8] 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.

[9] 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 Graphics 32(4): 65.

[10] 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.

[11] Lee, I.-K. (2000). Curve reconstruction from unorganized points, Computer Aided Geometric Design 17(2): 161–177.

[12] 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.

[13] Li, L. and Wang, W. (2018). Improved use of LOP for curve skeleton extraction, Computer Graphics Forum 37(7): 313–323, DOI: 10.1111/cgf.13570.

[14] Lipman, Y., Cohen-Or, D., Levin, D. and Tal-Ezer, H. (2007). Parameterization-free projection for geometry reconstruction, ACM Transactions on Graphics 26(3): 22.

[15] 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.

[16] 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.

[17] Sharf, A., Lewiner, T., Shamir, A. and Kobbelt, L. (2007). On-the-fly curve-skeleton computation for 3D shapes, Computer Graphics Forum 26(3): 323–328, DOI: 10.1111/j.1467-8659.2007.01054.x.

[18] Song, C., Pang, Z., Jing, X. and Xiao, C. (2018). Distance field guided l1-median skeleton extraction, The Visual Computer 34(2): 243–255.

[19] Tagliasacchi, A., Alhashim, I., Olson, M. and Zhang, H. (2012). Mean curvature skeletons, Computer Graphics Forum 31(5): 1735–1744, DOI: 10.1111/j.1467-8659.2012.03178.x.

[20] Tagliasacchi, A., Delame, T., Spagnuolo, M., Amenta, N. and Telea, A. (2016). 3D skeletons: A state-of-the-art report, Computer Graphics Forum 35(2): 573–597, DOI: 10.1111/cgf.12865.

[21] 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.

[22] Verroust, A. and Lazarus, F. (2000). Extracting skeletal curves from 3D scattered data, The Visual Computer 16(1): 15–25.

[23] 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.

[24] Weber, A. and Friedrich, C.J. (1929). Alfred Weber’s Theory of the Location of Industries, University of Chicago Press, Chicago, IL.

[25] Yan, Y., Sykes, K., Chambers, E., Letscher, D. and Ju, T. (2016). Erosion thickness on medial axes of 3D shapes, ACM Transactions on Graphics 35(4): 38.

[26] Zhu, Q., Feng, J. and Huang, J. (2016). Natural neighbor: A self-adaptive neighborhood method without parameter k, Pattern Recognition Letters 80: 30–36.