基于改进灰狼算法和自适应分裂KD-Tree的点云配准方法

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

摘要/Abstract

摘要：

针对传统GWO存在搜索效率不足、易陷入局部最优等问题，提出了一种基于改进GWO和迭代最近点(ICP)的工业复杂零件点云配准方法。针对GWO随机初始化导致种群分布不均匀的问题，采用混沌映射对灰狼种群进行初始化，使种群更加均匀地分布在搜索空间内；引入一种非线性控制参数策略，平衡灰狼算法的局部搜索和全局搜索能力；融合精英反向学习，提高算法后期解的质量；利用ICP算法进行精配准。设计一种自适应分裂维度的方法，动态选择分裂维度，提高点云数据质量。仿真结果表明：IGWO相较于3种对比算法的RMSE平均提高了80.31%、73.99%、47.7%。

关键词: 改进灰狼算法, 混沌映射, 非线性参数, 精英反向学习, 点云配准, 自适应分裂维度

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

中图分类号:

TP18

杜沅昊,耿秀丽,徐诚智等 . 基于改进灰狼算法和自适应分裂KD-Tree的点云配准方法[J]. 系统仿真学报, 2025, 37(2): 424-435.

Du Yuanhao,Geng Xiuli,Xu Chengzhi,et al . 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.

图/表 13

图1

表1

表2

图2

表3

图3

表4

不同算法配准结果统计

数据种类	模型	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]

表4

图4

图5

图6

图7

表5

多目标点云下所有模型配准结果统计

配准对象	模型	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]

表5

图8

参考文献 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]	李维刚, 邹少峰, 王永强, 余楚翔. 基于强度信息特征滤波的激光SLAM算法[J]. 系统仿真学报, 2025, 37(2): 392-403.
[2]	童亮, 杨婕, 甘旭升, 沈堤, 杨文达, 陈达雄. 基于改进混沌蚁群算法的多机冲突解脱仿真研究[J]. 系统仿真学报, 2025, 37(1): 155-166.
[3]	王海超, 尹勇, 景乾峰, 丛琳. 基于3D激光雷达的水面无人艇靠泊参数估计[J]. 系统仿真学报, 2024, 36(8): 1737-1748.
[4]	朱宇挺, 苏焕坤, 冯小东, 雷诗洁, 傅妍芳. 基于改进差分算法的数据链时隙分配方法[J]. 系统仿真学报, 2024, 36(5): 1242-1250.
[5]	李高扬, 黎向锋, 赵康, 金玉超, 易志东, 左敦稳. 全粒子推动野马优化算法的无人机三维路径规划[J]. 系统仿真学报, 2024, 36(3): 595-607.
[6]	李维刚, 余楚翔, 王永强, 邹少峰. 基于分布优化配准的实时激光SLAM算法[J]. 系统仿真学报, 2024, 36(11): 2566-2577.
[7]	胥远兴, 张孟健, 王德光. 面向柔性作业车间调度问题的混沌编码量子粒子群优化算法[J]. 系统仿真学报, 2024, 36(10): 2371-2382.
[8]	张元, 韩浩宇, 韩燮, 付嘉旭. 基于改进的协方差矩阵描述子的点云配准方法[J]. 系统仿真学报, 2023, 35(5): 979-986.
[9]	焦业峰, 王艳, 纪志成. 基于BLP-ALO-SVM的风电功率短期预测方法[J]. 系统仿真学报, 2022, 34(12): 2535-2545.
[10]	刘景森, 袁蒙蒙, 李煜. 基于改进樽海鞘群算法求解工程优化设计问题[J]. 系统仿真学报, 2021, 33(4): 854-866.
[11]	郭业才, 马伟伟, 朱赛男. 基于混沌人工蜂群优化的声源定位算法[J]. 系统仿真学报, 2017, 29(6): 1168-1173.
[12]	吴肇星, 金鑫, 宋承根, 张春伟, 李晓东. 基于随机可逆矩阵的3D点云模型加密[J]. 系统仿真学报, 2016, 28(10): 2455-2459.
[13]	余文利, 周明全, 税午阳, 武仲科. 基于曲率的点云自动配准方法[J]. 系统仿真学报, 2015, 27(10): 2374-2379.