Point Cloud Registration Method Based on Improved Grey Wolf Algorithm and Adaptive Splitting KD-Tree

doi:10.16182/j.issn1004731x.joss.23-1190

Abstract

Abstract:

Traditional GWO algorithms suffer from limitations such as insufficient search efficiency and susceptibility to local optima. A novel method for the registration of point clouds of complex industrial components is proposed based on an improved GWO algorithm and ICP. To address the problem of uneven population distribution caused by random initialization in GWO, chaotic mapping is employed to initialize the gray wolf population, ensuring a more uniform distribution of individuals within the search space.A non-linear control parameter strategy is introduced to strike a balance between the algorithm's local search and global search capabilities. Elite reverse learning is integratedto improve the quality of the algorithm's solutions. The refined registration is achieved using the ICP algorithm. An adaptive dimension splitting method is developed. This method dynamically selects the splitting dimensions to enhance the quality of the point cloud data. The experiments show that the RMSE of IGWO increases by 80.31%, 73.99% and 47.7% on average compared with the other three comparison algorithms.

Key words: improved gray wolf optimization, chaos mapping, nonlinear parameter, elite backward learning, point cloud registration, adaptive splitting dimension

CLC Number:

TP18

Du Yuanhao, Geng Xiuli, Xu Chengzhi, Liu Yinhua. Point Cloud Registration Method Based on Improved Grey Wolf Algorithm and Adaptive Splitting KD-Tree[J]. Journal of System Simulation, 2025, 37(2): 424-435.

Figures/Tables 13

Fig. 1

Table 1

Table 2

Fig. 2

Table 3

Fig. 3

Table 4

Statistics of registration results of different algorithms

数据种类	模型	RMSE	$[θ, φ, γ, T x, T y, T z]$
Bunny	GWO	0.038 5	[0.114, -4.96, 0.187, 0.04, 0.029]
	SSA	0.103 5	[-5, -5, -10.41, 0.031, -0.005, 0.046]
	PSO	0.017 8	[-3.988, 1.098, 0.236, 0.028, -0.001, 0.02]
	IGWO	0.013 0	[-5, -0.704, -11.723, 0.03, -0.006, 0.047]
Dragon	GWO	0.745 3	[5, 0.986, 41.33, -0.004, 0.032, -0.106]
	SSA	0.086 1	[-5, -4.032, 40.979, -0.007, 0.03, -0.105]
	PSO	0.071 1	[-1.328, -0.371, 20.59, -0.009, 0.01, -0.07]
	IGWO	0.084 5	[-3.118, 0.649, 43.32, -0.013, 0.034, -0.11]
Happy Buddha	GWO	0.071 2	[-1.537, -5, 4.033, 0.007, 0.012, -0.004]
	SSA	0.071 2	[-1.274, -5, 3.891, 0.008, 0.01, -0.004]
	PSO	0.097 1	[3.98, 4.78, 79.64, -0.002, 0.133, -0.112]
	IGWO	0.070 3	[3.58, -0.975, 5.29, 0.017, 0.008, -0.004]
Drill bit	GWO	0.094 1	[-0.21, -0.195, 3.404, 0.013, 0.002, -0.001]
	SSA	0.094 7	[3.171, -4.251, 0.516, 0.019, 0.001, 0.007]
	PSO	0.093 0	[-5, 0.068, -0.921, 0.001, -0.001, 0.027]
	IGWO	0.085 9	[1.684, -0.423, 1.91, 0.017, 0.001, 0.003]

Table 4

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Table 5

Statistics of registration results of all models under multi-target point clouds

配准对象	模型	RMSE	$[θ, φ, γ, T x, T y, T z]$
O→A	GWO	3.43×10^-4	[-75.24, -78.93, -60.48, 35.71, 26.99, 33.78]
	SSA	1.04×10^-4	[-69.08, -78.47, -74.96, 40, 34.81, 33.40]
	PSO	8.09×10^-5	[-14.58, -68.9, -121.6, 40, 10.3, 22.54]
	IGWO	6.06×10^-5	[-79.01, -75.15, -59.4, 39.82, 39.39, 39.41]
O→B	GWO	1.32×10^-4	[-23.14, -20.46, -28.49, 19.44, 13.18, 17.77]
	SSA	2.77×10^-4	[-30.98, -23.48, -23.50, 37.46, 33.54, 4.62]
	PSO	8.52×10^-5	[-25.12, -22.01, -27.6, 21.8, 18.3, 12.75]
	IGWO	4.94×10^-5	[-25.02, -19.98, -30.28, 20.04, 20.17, 20.43]
O→C	GWO	3.23×10^-4	[-54.71, -39.79, -97, 7, -5.72, 3.78, 11.32]
	SSA	7.52×10^-4	[-62.13, -37.87, -95.18, 11.16, 11.17, 16.14]
	PSO	4.94×10^-5	[-58.1, -39.32, -99.46, 3.64, 8.14, 10.68]
	IGWO	1.12×10^-5	[-59.27, -40.34, -100.42, 8.99, 9.60, 8.90]

Table 5

Fig. 8

References 23

1	陈勇刚, 张沅, 杨力, 等. 一种基于实测点云数据的壁板类零件修配加工路径计算方法[J]. 南京航空航天大学学报, 2023, 55(3): 444-451.
	Chen Yonggang, Zhang Yuan, Yang Li, et al. A Repairing Method of Wall Plate Parts Based on Measured Point Cloud[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2023, 55(3): 444-451.
2	魏效玲, 孟艺, 孙秀军. 损伤零件点云模型配准的ICP算法[J]. 制造技术与机床, 2020(5): 118-121.
	Wei Xiaoling, Meng Yi, Sun Xiujun. ICP Algorithm for Registration of Point Cloud Model of Damaged Parts[J]. Manufacturing Technology & Machine Tool, 2020(5): 118-121.
3	Besl P J, Mckay N D. Method for Registration of 3-D Shapes[C]//Sensor Fusion IV: Control Paradigms and Data Structures. Bellingham: SPIE, 1992: 586-606.
4	刘贺伟, 卿兆波, 黄加俊. 基于改进ICP的帧间匹配算法研究[J]. 现代电子技术, 2023, 46(8): 73-78.
	Liu Hewei, Zhaobo Qing, Huang Jiajun. Research on Inter-frame Matching Algorithm Based on Improved ICP[J]. Modern Electronics Technique, 2023, 46(8): 73-78.
5	He Ying, Liang Bin, Yang Jun, et al. An Iterative Closest Points Algorithm for Registration of 3D Laser Scanner Point Clouds with Geometric Features[J]. Sensors, 2017, 17(8): 1862.
6	王文博, 田茂义, 俞家勇, 等. 改进的迭代最近点点云配准方法[J]. 激光与光电子学进展, 2022, 59(2): 382-391.
	Wang Wenbo, Tian Maoyi, Yu Jiayong, et al. Improved Iterative Nearest Point Point Cloud Alignment Method[J]. Laser & Optoelectronics Progress, 2022, 59(2): 382-391.
7	Wu Zongze, Chen Hongchen, Du Shaoyi, et al. Correntropy Based Scale ICP Algorithm for Robust Point Set Registration[J]. Pattern Recognition, 2019, 93: 14-24.
8	周丽敏, 卜昆, 董一巍, 等. 基于简化点云带动的涡轮叶片快速配准技术[J]. 计算机集成制造系统, 2012, 18(5): 988-992.
	Zhou Limin, Bu Kun, Dong Yiwei, et al. Rapid Registration Technology of Turbine Blade Based on Simplified Cloud Data[J]. Computer Integrated Manufacturing Systems, 2012, 18(5): 988-992.
9	Shi Xiaojing, Liu Tao, Han Xie. Improved Iterative Closest Point(ICP) 3D Point Cloud Registration Algorithm Based on Point Cloud Filtering and Adaptive Fireworks for Coarse Registration[J]. International Journal of Remote Sensing, 2020, 41(8): 3197-3220.
10	Liu Hai, Wang Shulin, Zhao Donghong. Initial Alignment for Point Cloud Registration by Improved Differential Evolution Algorithm[J]. Optik, 2021, 243: 166856.
11	Zhan Xu, Cai Yong, Li Heng, et al. A Point Cloud Registration Algorithm Based on Normal Vector and Particle Swarm Optimization[J]. Measurement and Control, 2020, 53(3/4): 265-275.
12	Feng Yaqing, Tang Jialin, Su Binghua, et al. Point Cloud Registration Algorithm Based on the Grey Wolf Optimizer[J]. IEEE Access, 2020, 8: 143375-143382.
13	Voronin Sergei, Makovetskii Artyom, Kober Vitaly, et al. ICP Algorithm Based on Stochastic Approach[C]//Applications of Digital Image Processing XLIV. Bellingham: SPIE, 2021: 118421P.
14	宁小娟, 李春旭, 王嘉豪, 等. 基于关键点精确配对的点云曲面匹配方法[J]. 系统仿真学报, 2023, 35(6): 1169-1182.
	Ning Xiaojuan, Li Chunxu, Wang Jiahao, et al. Point Cloud Surface Matching Method Based on Precise Matching of Critical Point[J]. Journal of System Simulation, 2023, 35(6): 1169-1182.
15	Mirjalili Seyedali, Seyed Mohammad Mirjalili, Lewis Andrew. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
16	郭现峰, 李浩华, 魏金玉. 基于 Fibonacci 变换和改进 Logistic-Tent混沌映射的图像加密方案[J]. 吉林大学学报(工学版), 2023, 53(7): 2115-2120.
	Guo Xianfeng, Li Haohua, Wei Jinyu. Image Encryption Scheme Based on Fibonacci Transform and Improved Logistic-Tent Chaotic Map[J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(7): 2115-2120.
17	曹梦龙, 赵文彬, 陈志强. 融合粒子群算法与改进灰狼算法的机器人路径规划[J]. 系统仿真学报, 2023, 35(8): 1768-1775.
	Cao Menglong, Zhao Wenbin, Chen Zhiqiang. Robot Path Planning by Fusing Particle Swarm Algorithm and Improved Grey Wolf Algorithm[J]. Journal of System Simulation, 2023, 35(8): 1768-1775.
18	Teng Zhijun, Jinling Lü, Guo Liwen. An Improved Hybrid Grey Wolf Optimization Algorithm[J]. Soft Computing, 2019, 23(15): 6617-6631.
19	Yang Xinshe. Flower Pollination Algorithm for Global Optimization[C]//Unconventional Computation and Natural Computation. Berlin: Springer Berlin Heidelberg, 2012: 240-249.
20	Bahmani B, Sun W C. A Kd-tree-accelerated Hybrid Data-driven/model-based Approach for Poroelasticity Problems with Multi-fidelity Multi-physics Data[J]. Computer Methods in Applied Mechanics and Engineering, 2021, 382: 113868.
21	Yang Jiaqi, Cao Zhiguo, Zhang Qian. A Fast and Robust Local Descriptor for 3D Point Cloud Registration[J]. Information Sciences, 2016, 346-347: 163-179.
22	Jain Meetu, Saihjpal Vibha, Singh Narinder, et al. An Overview of Variants and Advancements of PSO Algorithm[J]. Applied Sciences, 2022, 12(17): 8392.
23	Xue Jiankai, Shen Bo. A Novel Swarm Intelligence Optimization Approach: Sparrow Search Algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.

点云模型	点云类别	点的数量	扫描次数	扫描仪	分辨率/mm
Bunny	Bunny000	40 256	10	Cyberware 3030 MS	x轴：0.100 y轴：0.002 z轴：0.003
Bunny	Bunny045	40 097	10	Cyberware 3030 MS
Dragon	DragonStandRight_0	41 841	70	Cyberware 3030 MS + spacetime analysis
Dragon	DragonStandRight_48	22 092	70	Cyberware 3030 MS + spacetime analysis
Happy Buddha	Happy Buddha_0	78 056	60	Cyberware 3030 MS + spacetime analysis
Happy Buddha	Happy Buddha_48	69 158	60	Cyberware 3030 MS + spacetime analysis
Drill bit	Drillbit_0	4 220	12	Cyberware 3030 MS
Drill bit	Drillbit_60	4 223	12	Cyberware 3030 MS

对比模型	参数设置
PSO^[22]	惯性权重ρ=0.9
	个体学习因子c₁=1.49
	群体学习因子c₂=1.49
	r₁, r₂ ∈ rand [0,1]
SSA^[23]	警戒值ST=0.8
	发现者麻雀比例PD=0.3
	危险麻雀比例SD=0.2
GWO	相关参数同IGWO一致

迭代次数	GWO	PSO	SSA	IGWO
1	2.590 2	3.175 1	3.058 3	4.823 7
2	2.255 7	2.016 4	2.718 0	2.910 4
3	0.767 1	1.047 5	2.644 1	2.400 1
4	0.767 1	0.865 4	0.644 1	0.938 9
5	0.767 1	0.678 3	0.425 7	0.430 9
...
15	0.178 7	0.090 8	0.348 0	0.087 3
16	0.178 7	0.090 8	0.348 0	0.087 3
17	0.178 7	0.090 8	0.348 0	0.087 3
18	0.178 7	0.077 9	0.348 0	0.083 3
19	0.178 7	0.077 9	0.348 0	0.083 3
20	0.178 7	0.077 9	0.348 0	0.083 3

[1]	Li Weigang, Zou Shaofeng, Wang Yongqiang, Yu Chuxiang. Intensity-based Feature Filtering for LiDAR-based SLAM [J]. Journal of System Simulation, 2025, 37(2): 392-403.
[2]	Wang Haichao, Yin Yong, Jing Qianfeng, Cong Lin. Estimation of the Berthing Parameter of Unmanned Surface Vessels Based on 3D LiDAR [J]. Journal of System Simulation, 2024, 36(8): 1737-1748.
[3]	Li Weigang, Yu Chuxiang, Wang Yongqiang, Zou Shaofeng. Real-time Lidar SLAM Algorithm Based on Distribution Optimal Registration [J]. Journal of System Simulation, 2024, 36(11): 2566-2577.
[4]	Xu Yuanxing, Zhang Mengjian, Wang Deguang. Chaotic-encode Quantum PSO Algorithm for Flexible Job-shop Scheduling Problem [J]. Journal of System Simulation, 2024, 36(10): 2371-2382.
[5]	Yuan Zhang, Haoyu Han, Xie Han, Jiaxu Fu. Point Cloud Registration Method Based on Improved Covariance Matrix Descriptor [J]. Journal of System Simulation, 2023, 35(5): 979-986.
[6]	Sun Shuifa, Li Zhun, Xia Kun, Shi Yunfei, Yang Jiquan, Dong Fangmin. Variable Scale Point Cloud Registration Algorithm [J]. Journal of System Simulation, 2018, 30(7): 2465-2474.