Feature-preserving skeleton extraction algorithm for point clouds

doi:10.11996/JG.j.2095-302X.2023010146

Abstract

Abstract:

The skeleton extraction of 3D models is one of the most important research topics in computer graphics. For point clouds with noise, the difficulty of curve skeleton extraction lies in maintaining the correct topology and good centrality. For point clouds without noise, the difficulty of curve skeleton extraction lies in the preservation of the detail features of the model. The current mainstream point clouds skeleton extraction methods usually cannot solve these two difficulties at the same time. The proposed algorithm combined the idea of clustering on the basis of the optimal transport theory, and transformed the problem of point clouds skeleton extraction into an optimization problem. Firstly, the optimal transport plan between the original point cloud and the sampled point cloud was computed. The original point cloud was segmented by clustering and the sampling points served as the center of the clusters. Then the number of clusters was reduced and the clustering results were optimized by adjusting and merging between clusters. Finally, after being obtained by the iterative method, the rough skeleton was optimized by interpolation operation. A large number of experimental results show that the proposed algorithm can extract good-quality curve skeletons and retain the features of the model on both noisy and noise-free 3D point clouds.

Key words: point clouds, skeleton extraction, optimal transport

CLC Number:

TP391

WANG Jia-dong, CAO Juan, CHEN Zhong-gui. Feature-preserving skeleton extraction algorithm for point clouds[J]. Journal of Graphics, 2023, 44(1): 146-157.

Figures/Tables 19

Fig. 1 The result of optimal transport

Fig. 2 The effect of the cost function on the coordinates of the sampling point ((a) Euclidean distance squared; (b) New cost function)

Fig. 3 Results of cluster adjustment ((a) Before cluster adjustment; (b) After two cluster adjustments; (c) Final result)

Fig. 4 Results of cluster merging ((a) Before merging the two clusters; (b) After merging the two clusters)

Fig. 5 The process of cluster merging ((a) Initial clustering, the clusters are all on the model surface; (b) Clustering results after several executions; (c) Clustering results when the legs form a linear structure)

Fig. 6 Results of curve skeleton interpolation ((a) Rough curve skeleton; (b) Thick and thin branch before insertion operation; (c) Thick and thin branch after insertion operation; (d) Final curve skeleton)

Table 1 Point cloud models for algorithm comparison

模型	原始点数	描述
Armadillo	43 408	无噪声的犰狳模型
Cactus	14 626	无噪声的仙人掌模型
G	26 483	有噪声的字母“G”模型
Human	14 522	有噪声的人模型

Table 2 One-sided Hausdorff distance comparison

模型	LBC	L1中值	MDCS	本文
Armadillo	0.045 8	0.072 7	0.087 4	0.035 1
Cactus	0.013 9	0.023 0	0.030 6	0.028 7
G	0.145 0	0.080 7	0.086 6	0.029 0
Human	0.079 6	0.050 3	0.062 5	0.044 5

Table 3 One-sided Chamfer distance comparison

模型	LBC	L1中值	MDCS	本文
Armadillo	0.000 171 0	0.000 672 0	0.001 110 0	0.000 094 6
Cactus	0.000 015 3	0.000 062 2	0.000 175 0	0.000 036 7
G	0.003 480 0	0.001 330 0	0.002 220 0	0.000 052 9
Human	0.000 617 0	0.000 212 0	0.000 542 0	0.000 133 0

Fig. 7 Curve skeleton results of different point clouds, the models are Armadillo, Cactus, G, Human from top to bottom ((a) MCS algorithm on grid; (b) LBC; (c) L1; (d) MDCS; (e) Ours)

Fig. 8 More results of algorithms

Fig. 9 Effect of Gaussian noise on results ((a) MCS; (b) Noiseless; (c) σ = 0.005; (d) σ = 0.01; (e) σ = 0.02)

Table 4 Quantitative indicators of the models in Figure 9

高斯噪声方差	单向豪斯多夫距离	单向倒角距离
无噪声	0.021 5	0.000 039 3
σ = 0.005	0.030 0	0.000 071 3
σ = 0.01	0.038 2	0.000 125 0
σ = 0.02	0.110 0	0.001 580 0

Fig. 10 The comparison between KNN and DKNN ((a) Edge connection result of KNN; (b) Edge connection result of DKNN)

Fig. 11 The influence of KNN and DKNN on the final result ((a) Final result of KNN; (b) Final result of DKNN)

Fig. 12 The effect of edge connection rules on results ((a) The result of the basic edge rule; (b) The result with extra rules added)

Fig. 13 Results without pyramid angle, maximum cosine, and minimum cosine

Table 5 Running time of each part of the algorithm (s)

步骤	Cactus	G	Armadillo
DKNN	2.815	10.339	11.024
最优传输与坐标更新	86.849	260.037	943.829
簇的调整与合并	141.372	512.974	1203.870
合计	231.036	783.350	2158.723

Table 6 Running time comparison with other algorithms (s)

算法	Cactus	G	Armadillo
OTC (本文)	231.036	783.3500	2158.7230
LBC	68.129	1834.4420	635.4424
L1中值	114.545	510.6930	735.9220
MDCS	98.704	175.5040	4604.5570

References 29

[1]	LOVATO C, CASTELLANI U, GIACHETTI A. Automatic segmentation of scanned human body using curve skeleton analysis[M]//Computer Vision/Computer Graphics Collaboration Techniques. Heidelberg: Springer, 2009: 34-45.
[2]	LI J T, LU G D. Skeleton driven animation based on implicit skinning[J]. Computers & Graphics, 2011, 35(5): 945-954. DOI URL
[3]	BERGER M, TAGLIASACCHI A, SEVERSKY L, et al. State of the art in surface reconstruction from point clouds[EB/OL]. [2022-02-21].http://diglib.eg.org/handle/10.2312/egst.20141040.161-185.
[4]	LIN S J, GUO Y H, LIANG Y, et al. 3D model retrieval based on skeleton[C]//2015 IEEE International Conference on Networking, Architecture and Storage (NAS). New York: IEEE Press, 2015: 321-325.
[5]	OGNIEWICZ R, ILG M. Voronoi skeletons: theory and applications[C]//1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York: IEEE Press, 1992: 63-69.
[6]	TAGLIASACCHI A, ZHANG H, COHEN-OR D. Curve skeleton extraction from incomplete point cloud[C]//SIGGRAPHʹ09: ACM SIGGRAPH 2008 Papers. New York: ACM, 2009: 1-9.
[7]	CAO J J, TAGLIASACCHI A, OLSON M, et al. Point cloud skeletons via Laplacian based contraction[C]//2010 Shape Modeling International Conference. New York: IEEE Press, 2010: 187-197.
[8]	AU O K C, TAI C L, CHU H K, et al. Skeleton extraction by mesh contraction[C]//SIGGRAPHʹ08: ACM SIGGRAPH 2008 Papers. New York: ACM, 2008: 1-10.
[9]	HUANG H, WU S H, COHEN-OR D, et al. L₁-medial skeleton of point cloud[J]. ACM Transactions on Graphics, 2013, 32(4): 1-65.
[10]	QIN H X, HAN J, LI N, et al. Mass-driven topology-aware curve skeleton extraction from incomplete point clouds[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 26(9): 2805-2817. DOI URL
[11]	AGUEH M, CARLIER G. Barycenters in the wasserstein space[J]. SIAM Journal on Mathematical Analysis, 2011, 43(2): 904-924. DOI URL
[12]	JIANG A L, LIU J, ZHOU J L, et al. Skeleton extraction from point clouds of trees with complex branches via graph contraction[J]. The Visual Computer, 2021, 37(8): 2235-2251. DOI
[13]	ZHANG Y, CHEN L F, TAN F, et al. An improved ℓ1 median model for extracting 3D human body curve-skeleton[J]. Multimedia Tools and Applications, 2021, 80(24): 33547-33571. DOI
[14]	MONGE G. Mémoire sur la théorie des déblais et des remblais[EB/OL]. [2022-02-21].https://cir.nii.ac.jp/crid/1572261550791499008.
[15]	KANTOROVICH L. On the transfer of masses[EB/OL]. [2022-02-21].https://cir.nii.ac.jp/crid/1570009750977811456.
[16]	AHUJA R. Network flows[EB/OL]. [2022-02-21]. https://dspace.mit.edu/bitstream/handle/1721.1/49424/networkflows00ahuj.pdf.
[17]	BONNEEL N, VAN DE PANNE M, PARIS S, et al. Displacement interpolation using Lagrangian mass transport[C]//2011 SIGGRAPH Asia Conference. New York: ACM, 2011: 1-12.
[18]	DAMIAN K, COMM B, GARRET M. The minimum cost flow problem and the network simplex method[D]. Irlande: Université College Gublin, 1991.
[19]	VALETTE S, CHASSERY J M. Approximated centroidal voronoi diagrams for uniform polygonal mesh coarsening[J]. Computer Graphics Forum, 2004, 23(3SPEC.ISS.): 381-389. DOI URL
[20]	NICHOLAS S. Polyscope[EB/OL]. (2021-12-03) [2022-02-21].https://github.com/nmwsharp/polyscope.
[21]	TAGLIASACCHIA. Point cloud skeletons via laplacian-based contraction[EB/OL]. (2015-01-01) [2022-02-21].https://github.com/taiya/cloudcontr.
[22]	HUANG H. L1-medial skeleton of point cloud[EB/OL]. (2013-01-01) [2022-02-21].https://vcc.tech/research/2013/L1skeleton.
[23]	QIN H X. Mass driven curve skeleton[EB/OL]. (2020-01-01) [2022-02-21].https://github.com/Hongxing-CQU/Mass-driven-Curve-Skeleton.
[24]	TAGLIASACCHI A, ALHASHIM I, OLSON M, et al. Mean curvature skeletons[J]. Eurographics Symposium on Geometry Processing, 2012, 31(5): 1735-1744.
[25]	GAO X. Triangulated surface mesh skeletonization[EB/OL]. [2022-02-21]. https://doc.cgal.org/5.2.4/Surface_mesh_Skeletonization.
[26]	VISIONAIR. Aim@Shape[EB/OL]. (2021-08-01) [2022-02-21]. http://visionair.ge.imati.cnr.it/ontologies/shapes.
[27]	SIDDIQI K. McGill 3D shape benchmark[EB/OL]. ( 2005-12-14) [2022-02-21]. https:/cim.mcgill.ca/-shape/benchMark/.
[28]	Stanford University Computer Graphics Laboratory. The stanford 3D scanning repository[EB/OL]. (2014-08-19) [2022-02-21].http://graphics.stanford.edu/data/3Dscanrep/.
[29]	CIGNONI. MeshLab[EB/OL]. (2022-02-01) [2022-02-21].Https://github.com/cnr-isti-vclab/meshlab.