保特征的点云骨架提取算法

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

图学学报 ›› 2023, Vol. 44 ›› Issue (1): 146-157.DOI: 10.11996/JG.j.2095-302X.2023010146

• 计算机图形学与虚拟现实 • 上一篇下一篇

保特征的点云骨架提取算法

王佳栋¹(), 曹娟², 陈中贵¹()

1.厦门大学信息学院，福建厦门 361005
2.厦门大学数学科学学院，福建厦门 361005

收稿日期:2022-06-20 修回日期:2022-08-01 出版日期:2023-10-31 发布日期:2023-02-16
通讯作者: 陈中贵
作者简介:王佳栋(1997-)，男，硕士研究生。主要研究方向为计算机图形学。E-mail：wjd97zzz@gmail.com
基金资助:
国家自然科学基金项目(61972327);虚拟现实技术与系统国家重点实验室(北京航空航天大学)开放课题基金(VRLAB2021B01)

Feature-preserving skeleton extraction algorithm for point clouds

WANG Jia-dong¹(), CAO Juan², CHEN Zhong-gui¹()

1. School of Informatics, Xiamen University, Xiamen Fujian 361005, China
2. School of Mathematical Sciences, Xiamen University, Xiamen Fujian 361005, China

Received:2022-06-20 Revised:2022-08-01 Online:2023-10-31 Published:2023-02-16
Contact: CHEN Zhong-gui
About author:WANG Jia-dong (1997-), master student. His main research interest covers computer graphics. E-mail：wjd97zzz@gmail.com
Supported by:
National Natural Science Foundation of China(61972327);The Open Project Program of State Key Laboratory of Virtual Reality Technology and Systems, Beihang University(VRLAB2021B01)

摘要/Abstract

摘要：

三维模型的骨架提取是计算机图形学中一个重要的研究方向。对于有噪声的点云模型，曲线骨架提取的难点在于保持正确的拓扑结构以及良好的中心性；对于无噪声的点云模型，曲线骨架提取的难点在于对模型细节特征的保留。目前主流的点云骨架提取方法往往无法同时解决这2个难点。算法在最优传输理论的基础之上结合聚类的思想，将点云骨架提取的问题转化为一个最优化问题。首先使用最优传输得到原始点云与采样点云之间的传输计划。然后使用聚类的思想将原始点云进行分割，采样点即成为了簇的中心。接着通过簇与簇之间的调整与合并减少聚类个数，优化聚类结果。最后通过迭代的方式得到粗糙的骨架并使用插点操作进行优化。大量实验结果表明，该算法在有噪声与无噪声的三维点云模型上均能提取出质量良好的曲线骨架并保留模型的特征。

关键词: 点云模型, 骨架提取, 最优传输

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

中图分类号:

TP391

王佳栋, 曹娟, 陈中贵. 保特征的点云骨架提取算法[J]. 图学学报, 2023, 44(1): 146-157.

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.

图/表 19

图1 最优传输结果展示

Fig. 1 The result of optimal transport

图2 代价函数对采样点坐标的影响((a)欧氏距离的平方；(b)新的代价函数)

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

图3 簇的调整结果展示((a)簇调整执行前；(b) 2次簇调整后；(c)最终结果)

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

图4 簇合并结果展示((a) 2个簇合并前；(b) 2个簇合并后)

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

图5 簇的合并过程((a)初始聚类，簇都在模型表面上；(b)执行若干次后的聚类结果；(c)腿部形成线状结构时的聚类结果)

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)

图6 曲线骨架插点结果展示((a)粗糙曲线骨架；(b)粗细分支插点操作前；(c)粗细分支插点操作后；(d)最终的曲线骨架)

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)

表1 算法比较的点云模型

Table 1 Point cloud models for algorithm comparison

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

表2 单向豪斯多夫距离比较

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

表3 单向倒角距离比较

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

图7 不同点云模型的曲线骨架结果图，模型从上到下分别是Armadillo，Cactus，G和Human ((a)网格上的MCS算法，作为参考标准；(b) LBC算法；(c) L1中值算法；(d) MDCS算法；(e)本文算法)

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)

图8 本文算法更多的结果

Fig. 8 More results of algorithms

图9 高斯噪声对结果的影响

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

表4 图9模型对应的定量指标

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

图10 KNN与DKNN的连边对比((a) KNN的连边结果；(b) DNKK的连边结果)

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

图11 KNN与DKNN对最终结果的影响((a) KNN的最终结果；(b) DNKK的最终结果)

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

图12 连边规则对结果的影响((a)基础连边规则的结果；(b)添加了额外规则的结果)

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)

图13 未使用棱锥角、最大余弦值和最小余弦值的结果

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

表5 对于不同模型算法各部分耗时(s)

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

表6 本文与其他算法的耗时比较(s)

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

参考文献 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.

保特征的点云骨架提取算法

Feature-preserving skeleton extraction algorithm for point clouds

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 19

参考文献 29

相关文章 4

编辑推荐

Metrics

本文评价

[1]	刘妍, 熊游依, 韩妙妙, 杨龙. 几何特征引导的物体点云模型多层级分割[J]. 图学学报, 2023, 44(4): 755-763.
[2]	朱磊, 李东彪, 闫星志, 刘向阳, 沈才华. 基于改进Mask R-CNN深度学习算法的隧道裂缝智能检测方法[J]. 图学学报, 2023, 44(1): 177-183.
[3]	王春香, 刘流, 周国勇, 纪康辉. 面向自动修补的圆柱特征孔洞识别[J]. 图学学报, 2021, 42(3): 511-516.
[4]	程志全，叶永凯，李宝. 一种基于RANSAC 框架的椭球提取算法[J]. 图学学报, 2012, 33(2): 68-71.