Multi-contour segmentation algorithm for point cloud slices of irregular objects

doi:10.11772/j.issn.1001-9081.2022101536

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (10): 3209-3216.DOI: 10.11772/j.issn.1001-9081.2022101536

• Multimedia computing and computer simulation • Previous Articles

Multi-contour segmentation algorithm for point cloud slices of irregular objects

Jin ZHANG¹, Wen XU¹, Yuqiao ZHOU², Kai LIU¹()

^1.College of Electrical Engineering，Sichuan University，Chengdu Sichuan 610065，China
^2.Key Laboratory of Green Chemistry and Technology，Ministry of Education （Sichuan University），Chengdu Sichuan 610064，China

Received:2022-10-13 Revised:2023-01-10 Accepted:2023-01-11 Online:2023-10-07 Published:2023-10-10
Contact: Kai LIU
About author:ZHANG Jin， born in 1998， M. S. candidate. His research interests include point cloud analysis， structured light three-dimensional imaging and its applications.
XU Wen， born in 1992， Ph. D. candidate. Her research interests include structured light three-dimensional imaging and its applications， artificial intelligence.
ZHOU Yuqiao， born in 1988， Ph. D. His research interests include X-ray crystallography， structural chemistry， computational chemistry.
Supported by:
Key Research and Development Project of Science and Technology Department of Sichuan Province(22ZDYF3012);Sichuan Higher Education Talent Training Quality and Teaching Reform Project(JG2021-36);Sichuan University Science Characteristic Direction Cultivation Program(2020SCUNL204);Sichuan University Postgraduate Education and Teaching Reform Research Project(GSSCU2021020)

不规则物体点云切片中的多轮廓分割算法

张瑾¹, 徐文¹, 周宇乔², 刘凯¹()

^1.四川大学电气工程学院，成都 610065
^2.绿色化学与技术教育部重点实验室（四川大学），成都 610064

通讯作者: 刘凯
作者简介:张瑾（1998—），男，四川南充人，硕士研究生，主要研究方向：点云分析、结构光三维成像及应用
徐文（1992—），女（彝族），四川雅安人，博士研究生，主要研究方向：结构光三维成像及应用、人工智能
周宇乔（1988—），男，浙江绍兴人，博士，主要研究方向：X射线晶体学、结构化学、计算化学；
基金资助:
四川省科技厅重点研发项目(22ZDYF3012);四川省高等教育人才培养质量和教学改革项目(JG2021?36);四川大学理科特色方向培育计划项目(2020SCUNL204);四川大学研究生教育教学改革研究项目(GSSCU2021020)

Abstract

Abstract:

When using the slicing method to measure the point cloud volumes of irregular objects， the existing Polygon Splitting and Recombination （PSR） algorithm cannot split the nearer contours correctly， resulting in low calculation precision. Aiming at this problem， a multi-contour segmentation algorithm — Improved Nearest Point Search （INPS） algorithm was proposed. Firstly， the segmentation of multiple contours was performed through the single-use principle of local points. Then， Point Inclusion in Polygon （PIP） algorithm was adopted to judge the inclusion relationship of contours， thereby determining positive or negative property of the contour area. Finally， the slice area was multiplied by the thickness and the results were accumulated to obtain the volume of irregular object point cloud. Experimental results show that on two public point cloud datasets and one point cloud dataset of chemical electron density isosurface， the proposed algorithm can achieve high-accuracy boundary segmentation and has certain universality. The average relative error of volume measurement of the proposed algorithm is 0.043 6%， which is lower than 0.062 7% of PSR algorithm， verifying that the proposed algorithm achieves high accuracy boundary segmentation.

Key words: volume measurement of point cloud, point cloud slicing, multi-contour segmentation, Point Inclusion in Polygon (PIP) algorithm, nearest point search method

摘要：

使用切片法进行不规则物体点云体积测量时，现有的多边形拆分再重组（PSR）算法难以正确拆分较近的轮廓，进而导致计算精度较低。针对这一问题，提出一种多轮廓分割算法——改进最近点搜索（INPS）算法。首先，通过局部点的单次使用原则分割多轮廓；其次，使用多边形内点判定（PIP）算法判断轮廓的包含关系，以确认轮廓面积的正负；最后，采用切片面积乘以厚度并累加的方式获取不规则物体点云的体积。实验结果表明，在两个公开点云数据集和一个化学电子密度等值面点云数据集上，所提算法都能实现高正确率的边界分割，具有一定的普适性；且该算法体积测量的平均相对误差为0.043 6%，低于PSR算法的0.062 7%，可见所提算法实现了高正确率的边界分割。

关键词: 点云体积测量, 点云切片, 多轮廓分割, 多边形内点判定算法, 最近点搜索法

CLC Number:

TP301.6

Jin ZHANG, Wen XU, Yuqiao ZHOU, Kai LIU. Multi-contour segmentation algorithm for point cloud slices of irregular objects[J]. Journal of Computer Applications, 2023, 43(10): 3209-3216.

张瑾, 徐文, 周宇乔, 刘凯. 不规则物体点云切片中的多轮廓分割算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3209-3216.

Figures/Tables 20

Fig. 1 Experimental point cloud Cat6

Fig. 2 Molecular potential point cloud generation process

Fig. 3 Schematic diagram of contours processed by MC algorithm

Fig. 4 Representative two-layer slice point cloud projection

Fig. 5 INPS algorithm to split point sets

Fig. 6 Contour lines processed by INPS algorithm

Fig. 7 Position relationship judgment with PIP algorithm

Fig. 8 Multi-contour position relationship

Tab. 1 Cat6 point cloud data information

参数名	值
点数	26 717
三角面数	51 592
点云体积/Bohr³	13 633.485
分层间隔 $h$ /Bohr	0.502 645

Tab. 1 Cat6 point cloud data information

参数名	值
点数	26 717
三角面数	51 592
点云体积/Bohr³	13 633.485
分层间隔 $h$ /Bohr	0.502 645

Tab. 2 Standard deviation and segmentation threshold in PSR algorithm

切片位置/Bohr	标准差	分割阈值	分割参数/Bohr	标准差	分割阈值
-10.64	1.767	5.023	8.46	0.187	0.866
-7.63	1.142	3.362	8.96	1.480	4.233
4.94	0.931	2.802	12.98	1.510	4.357

Fig. 9 Comparison of contour segmentation results at different slice positions （Z-axis） of Cat6 point cloud

Fig. 10 Comparison of contour segmentation results at different slice positions （Y-axis） of Cat6 point cloud

Fig. 11 Comparison of contour segmentation results at different slice positions （X-axis） of Cat6 point cloud

Tab. 3 Comparison of cross-sectional area calculation results at different slice positions （Z-axis） of Cat6 point cloud

算法	切片位置/Bohr	参考面积/Bohr³	横截面积/Bohr³	绝对误差/Bohr³	相对误差/%
INPS	-10.64	191.855 6	191.931 6	0.076 0	0.039 6
	-7.63	514.623 9	514.690 4	0.066 5	0.012 9
	4.94	598.201 2	598.054 5	0.146 7	0.024 5
	8.46	432.881 8	432.500 2	0.381 6	0.088 2
	8.96	384.347 8	383.921 6	0.426 2	0.110 9
	12.98	76.843 3	76.450 1	0.393 2	0.511 7
PSR	-0.64	191.855 6	198.064 1	6.208 5	3.236 0
	-7.63	514.623 9	515.032 5	0.408 6	0.079 4
	4.94	598.201 2	598.383 4	0.182 2	0.030 5
	8.46	432.881 8	432.649 6	0.232 2	0.053 6
	8.96	384.347 8	384.519 3	0.171 5	0.044 6
	12.98	76.843 3	65.769 5	11.073 5	14.410 5

Fig. 12 Real entities and three-dimensional surface models

Tab. 4 Data processing parameters for two point clouds

参数名	Stanford Bunny	Happy Buddha
点数	1 040 752	10 010 722
三角面数	2 081 496	10 005 248
点云体积/mm³	753 955	354 206
分层间隔 $h$ /mm	1	1
参数 $k$	5	4
投影厚度 $δ$ /mm	0.053 192 8	0.016 786 6

Tab. 4 Data processing parameters for two point clouds

参数名	Stanford Bunny	Happy Buddha
点数	1 040 752	10 010 722
三角面数	2 081 496	10 005 248
点云体积/mm³	753 955	354 206
分层间隔 $h$ /mm	1	1
参数 $k$	5	4
投影厚度 $δ$ /mm	0.053 192 8	0.016 786 6

Fig. 13 Comparison of contour segmentation results at different slice positions （Z-axis） of Stanford Bunny point cloud

Fig. 14 Comparison of contour segmentation results at different slice positions （Z-axis） of Happy Buddha point cloud

Tab. 5 Comparison of 6 cross-sectional area errors in Stanford Bunny and Happy Buddha point clouds by using PSR and INPS algorithms

实验数据	切片位置/mm	误差/%
实验数据	切片位置/mm	INPS	PSR
Stanford Buuny	-19.52	0.035 2	0.129 8
	-13.02	0.020 5	0.241 2
	-8.02	0.080 3	0.060 3
	-2.02	0.014 4	0.047 9
	38.48	0.015 2	0.085 7
	42.98	0.036 9	0.052 1
Happy Buddha	64.00	0.006 6	0.006 8
	82.00	0.030 0	0.028 0
	129.00	0.000 8	0.000 4
	167.00	0.029 7	0.029 4
	219.00	0.093 7	0.044 9
	239.00	0.016 8	0.021 1

Tab. 6 Comparison of three sets of data volume measurement results by using PSR and INPS algorithms

算法	实验数据	体积V		绝对误差		相对误差/%	层数
算法	实验数据	激光扫描/mm	分子点云/Bohr³	激光扫描/mm	分子点云/Bohr³	相对误差/%	层数
PSR	Stanford Bunny	753 276		679		0.090 1	120
	Happy Buddha	353 998		208		0.058 7	198
	Cat6		13 638.832		5.347	0.039 2	54
INPS	Stanford Bunny	753 727		568		0.075 3	120
	Happy Buddha	354 323		117		0.033 0	198
	Cat6		13 630.485		3.085	0.022 6	54

References 25

1	郭仁忠. 空间分析［M］. 2版. 北京：高等教育出版社， 2001： 143-145.
	GUO R Z. Spatial Analysis［M］. 2nd ed. Beijing： Higher Education Press， 2001： 143-145.
2	ANDERSEN H E. Estimation of critical forest structure metrics through the spatial analysis of airborne laser scanner data［D］. Seattle， WA： University of Washington， 2003： 197-202. 10.1109/ICI.2011.40
3	刘明学，崔进业. 基于点云三维坐标数据计算复杂物体体积［J］. 测绘地理信息， 2018， 43（3）： 96-98.
	LI M X， CUI J Y. Calculate volume of complex objects based on 3D coordinates of points cloud data［J］. Journal of Geomatics， 2018， 43（3）： 96-98.
4	魏言标，郑磊，薛少兵，等. 基于三坐标测量和3D扫描的凸轮逆向建模设计［J］. 机械设计， 2021， 38（9）： 71-74.
	WEI Y B， ZHENG L， XUE S B， et al. Reverse modeling design of the cam based on three-coordinate measurement and 3D scanning［J］. Journal of Machine Design， 2021， 38（9）： 71-74.
5	王鑫龙，孙文磊，张建杰，等. 基于点云数据的逆向工程技术研究综述［J］. 制造技术与机床， 2018（2）： 49-53. 10.19287/j.cnki.1005-2402.2018.02.010
	WANG X L， SUN W L， ZHANG J J， et al. Review on reverse engineering research based on point cloud data［J］. Manufacturing Technology and Machine Tool， 2018（2）： 49-53. 10.19287/j.cnki.1005-2402.2018.02.010
6	董亚涵，李永强，李鹏鹏，等. 基于改进凸包算法的树冠轮廓点提取与体积计算［J］. 测绘工程， 2018， 27（8）： 66-71. 10.19349/j.cnki.issn1006-7949.2018.08.012
	DONG Y H， LI Y Q， LI P P， et al. Tree crown outline points extracting and volume calculation based on improved convex hull algorithm［J］. Engineering of Surveying and Mapping， 2018， 27（8）： 66-71. 10.19349/j.cnki.issn1006-7949.2018.08.012
7	陈琛，李宝顺，包亚萍. 基于光栅投影和点云体积计算的过度包装检测系统［J］. 计算机测量与控制， 2014， 22（12）： 3919-3922. 10.3969/j.issn.1671-4598.2014.12.024
	CHEN C， LI B S， BAO Y P. Excessive packaging detection system based on point set volume calculation method and grating projection［J］. Computer Measurement and Control， 2014， 22（12）： 3919-3922. 10.3969/j.issn.1671-4598.2014.12.024
8	吕小宁，刘晓丽，段云岭，等. 地下能源储库群容积激光测量方法及现场实验［J］. 中国激光， 2016， 43（10）： No.1004002. 10.3788/cjl201643.1004002
	LYU X N， LIU X L， DUAN Y L， et al. Laser measurement method and in-situ experiment of underground energy storage caverns volume［J］. Chinese Journal of Lasers， 2016， 43（10）： No.1004002. 10.3788/cjl201643.1004002
9	张吉星，程效军，程小龙. 三维激光扫描技术在船舶排水量计量中的应用［J］. 中国激光， 2016， 43（12）： No.1204003. 10.3788/cjl201643.1204003
	ZHANG J X， CHENG X J， CHENG X L. Application of three-dimensional laser scanning technology in measurement of ship displacement［J］. Chinese Journal of Lasers， 2016， 43（12）： No.1204003. 10.3788/cjl201643.1204003
10	LU T， CHEN F W. Multiwfn： a multifunctional wavefunction analyzer［J］. Journal of Computational Chemistry， 2012， 33（5）： 580-592. 10.1002/jcc.22885
11	LU T， CHEN F. Quantitative analysis of molecular surface based on improved Marching Tetrahedra algorithm［J］. Journal of Molecular Graphics and Modelling， 2012， 38： 314-323. 10.1016/j.jmgm.2012.07.004
12	连强强，顾敏. 基于α-shape的三维激光点云计算树冠体积的研究［J］. 青海大学学报， 2020， 38（5）： 74-79. 10.13901/j.cnki.qhwxxbzk.2020.05.011
	LIAN Q Q， GU M. Research on the calculation of tree crown volume by 3D laser point cloud based on α-shape［J］. Journal of Qinghai University， 2020， 38（5）： 74-79. 10.13901/j.cnki.qhwxxbzk.2020.05.011
13	付敬帅，李斌. 基于点云截面数据点的多轮廓排序算法［J］. 河南科学， 2019， 37（6）： 933-937. 10.3969/j.issn.1004-3918.2019.06.012
	FU J S， LI B. Multi-contour sorting algorithm based on point cloud cross-section data points［J］. Henan Science， 2019， 37（6）： 933-937. 10.3969/j.issn.1004-3918.2019.06.012
14	程效军，熊鑫鑫，杨泽鑫，等. 基于地面激光雷达的洞库容量计量［J］. 激光与光电子学进展， 2019， 56（23）： No.231201. 10.3788/lop56.231201
	CHENG X J， XIONG X X， YANG Z X， et al. Cavern capacity calculation using terrestrial lidar［J］. Laser and Optoelectronics Progress， 2019， 56（23）： No.231201. 10.3788/lop56.231201
15	钱锦锋，陈志杨，张三元，等. 点云数据压缩中的边界特征检测［J］. 中国图象图形学报， 2005， 10（2）： 164-169. 10.11834/jig.20050232
	QIAN J F， CHEN Z Y， ZHANG S Y， et al. The detection of boundary point of point cloud compression［J］. Journal of Image and Graphics， 2005， 10（2）： 164-l69. 10.11834/jig.20050232
16	JAIN A K. Data clustering： 50 years beyond K-means［J］. Pattern Recognition Letters， 2010， 31（8）： 65l-666. 10.1016/j.patrec.2009.09.011
17	NG A Y， JORDAN M I， WEISS Y. On spectral clustering analysis and an algorithm［C］// Proceedings of the 14th International Conference on Neural Information Processing Systems： Natural and Synthetic. Cambridge： MIT Press， 2001 ：849-856.
18	程效军，方芳. 基于形态学的散乱点云轮廓特征线提取［J］. 同济大学学报（自然科学版）， 2014， 42（11）： 1738-1743. 10.11908/j.issn.0253-374x.2014.11.018
	CHENG X J， FANG F. Morphology-based scattered point cloud contour extraction［J］. Journal of Tongji University （Natural Science）， 2014， 42（11）： 1738-1743. 10.11908/j.issn.0253-374x.2014.11.018
19	刘金锦，李浩军. 基于点云切片改进法的不规则物体体积测量［J］. 光学学报， 2021， 41（23）： No.2312003. 10.3788/AOS202141.2312003
	LIU J J， LI H J. Volume measurement of irregular objects based on improved point cloud slicing method［J］. Acta Optica Sinica， 2021， 41（23）： No.2312003. 10.3788/AOS202141.2312003
20	HAINES E. Point in polygon strategies［M］// HECKBERT P S. Graphics Gems IV. San Diego， CA： Academic Press， 1994： 24-46. 10.1016/b978-0-12-336156-1.50013-6
21	LORENSEN W E， CLINE H E. Marching cubes： a high resolution 3D surface construction algorithm［J］. ACM SIGGRAPH Computer Graphics， 1987， 21（4）：163-169. 10.1145/37402.37422
22	LIU K， RAN X， GONG J， et al. Extending epipolar geometry for real-time structured light illumination Ⅱ： lossless accuracy［J］. Optics Letters， 2021， 46（4）： 837-840. 10.1364/ol.415858
23	JIA M， YANG X， LIU K. Automatically detecting rigidly and nonrigidly deformed facial landmarks from coarseness to fineness［J］. Journal of Electronic Imaging， 2019， 28（6）： No.063009. 10.1117/1.jei.28.6.063009
24	ZHANG G， XU B， LAU D L， et al. Correcting projector lens distortion in real time with a scale-offset model for structured light illumination［J］. Optics Express， 2022， 30（14）： 24507-24522. 10.1364/oe.462120
25	柯映林，王青. 反求工程中的点云切片算法研究［J］. 计算机辅助设计与图形学学报， 2005， 17（8）： 1798-1802. 10.3321/j.issn:1003-9775.2005.08.024
	KE Y L， WANG Q. Research on point cloud slicing technique in reverse engineering［J］. Journal of Computer-Aided Design and Computer Graphics， 2005， 17（8）： 1798-1802. 10.3321/j.issn:1003-9775.2005.08.024

[1]	Lei MA, Chuan LUO, Tianrui LI, Hongmei CHEN. Fuzzy-rough set based unsupervised dynamic feature selection algorithm [J]. Journal of Computer Applications, 2023, 43(10): 3121-3128.
[2]	. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	Bo WANG, Hao WANG, Xiaoxin DU, Xiaodong ZHENG, Wei ZHOU. Hybrid dragonfly algorithm based on subpopulation and differential evolution [J]. Journal of Computer Applications, 2023, 43(9): 2868-2876.
[4]	Bin LI, Zhibin TANG. Multiple level binary imperialist competitive algorithm for solving heterogeneous multiple knapsack problem [J]. Journal of Computer Applications, 2023, 43(9): 2855-2867.
[5]	Dahai LI, Meixin ZHAN, Zhendong WANG. Enhanced sparrow search algorithm based on multiple improvement strategies [J]. Journal of Computer Applications, 2023, 43(9): 2845-2854.
[6]	Saijuan XU, Zhenyu PEI, Jiawei LIN, Genggeng LIU. Constrained multi-objective evolutionary algorithm based on multi-stage search [J]. Journal of Computer Applications, 2023, 43(8): 2345-2351.
[7]	. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 0, (): 0-0.
[8]	DU Xiaoxin, ZHOU Wei, WANG Hao, HAO Tianru, WANG Zhenfei, JIN Mei, ZHANG Jianfei. Survey of subgroup optimization strategies for intelligent algorithms [J]. Journal of Computer Applications, 0, (): 0-0.
[9]	Zhihui SHAN, Meng HAN, Qiang HAN. Closed high utility quantitative itemset mining algorithm on incremental data [J]. Journal of Computer Applications, 2023, 43(7): 2049-2056.
[10]	Ming DU, Wanli GU, Junfeng ZHOU, Zhijun WANG. Community search method based on motif connectivity [J]. Journal of Computer Applications, 2023, 43(7): 2190-2199.
[11]	Fei LI, Qiang YUE, Ziwei PAN, Yining SUN, Xiaoliu YU. Dynamic particle swarm optimization algorithm based on automatic fast density peak clustering [J]. Journal of Computer Applications, 2023, 43(S1): 154-162.
[12]	Wei BAI, Cheng WANG, Cailing WANG, Xi ZHAN, Lei ZHANG. Improved ant colony optimization algorithm based on ant number dynamic adjustment [J]. Journal of Computer Applications, 2023, 43(S1): 163-168.
[13]	Yanping LI, Guangyu SUN, Wenxuan YANG, Chuanxian LI, Wenliang ZHAO, Huachang NIU, Yang YU. Parallel shuffled frog-leaping algorithm based on adaptive weight adjustment and differential evolution strategy [J]. Journal of Computer Applications, 2023, 43(S1): 169-176.
[14]	Yizhuo WANG, Lei WANG, Fangjie XU, Yaguang ZHANG. Precision defect repair method for floating point program based on program rewriting [J]. Journal of Computer Applications, 2023, 43(S1): 177-181.
[15]	Yiwen ZHAO, Yunpeng LIU. Image set recognition method based on subspace manifold [J]. Journal of Computer Applications, 2023, 43(S1): 207-211.

Multi-contour segmentation algorithm for point cloud slices of irregular objects

不规则物体点云切片中的多轮廓分割算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 25

Related Articles 15

Recommended Articles

Metrics