基于熵准则遗传算法的点云配准算法
|
摘要
迭代最近点(ICP)算法由于其配准精度很高,通常运用于点云的精配准,但其配准精度和迭代收敛性取决于待配准点云的初始位置。提出一种将遗传算法和空间分布熵相融合的空间最优变换矩阵求解算法,以一种新的点云空间位置评价方法——空间分布熵作为遗传算法的目标函数,采用遗传算子指导解的搜索方向,通过新种群的不断迭代使空间分布熵最小,结束后对最优个体解码实现点云的粗配准。实验表明,该算法有效可行,克服了传统方法在有点云缺陷和噪声点时不能提供很好的初始拼接位置的问题,在误差允许的范围内,可以直接实现点云拼接。
The iterative closest point( ICP) algorithm is usually used in the fine registration of point cloud because of its high registration accuracy,but its registration accuracy and iteration convergence depend on the initial registration position of the point cloud to be registered. This paper proposed an algorithm of spatial optimization transformation matrix combining genetic algorithm with spatial distribution entropy,in which used a new point cloud spatial position evaluation method as the objective function of genetic algorithm,it used the genetic operator to guide the solution of search direction. The algorithm achieved the minimum spatial distribution entropy through the new population of iterations,after which the coarse registration of point cloud was achieved by decoding the optimal individuals. The experimental results show that the algorithm is effective and feasible,and it can overcome the problem that traditional method can't provide a good initial position when the defects and noise exist in the point cloud. The algorithm can directly realize point cloud registration within the acceptable error range.
The iterative closest point( ICP) algorithm is usually used in the fine registration of point cloud because of its high registration accuracy,but its registration accuracy and iteration convergence depend on the initial registration position of the point cloud to be registered. This paper proposed an algorithm of spatial optimization transformation matrix combining genetic algorithm with spatial distribution entropy,in which used a new point cloud spatial position evaluation method as the objective function of genetic algorithm,it used the genetic operator to guide the solution of search direction. The algorithm achieved the minimum spatial distribution entropy through the new population of iterations,after which the coarse registration of point cloud was achieved by decoding the optimal individuals. The experimental results show that the algorithm is effective and feasible,and it can overcome the problem that traditional method can't provide a good initial position when the defects and noise exist in the point cloud. The algorithm can directly realize point cloud registration within the acceptable error range.
引文
[1] Besl P J,Mc Kay H D. A method for registration of 3-D shapes[J].IEEE Trans on Pattern Analysis&Machine Intelligence,1992,14(2):239-256.
[2]戴静兰,陈志杨,叶修梓. ICP算法在点云配准中的应用[J].中国图象图形学报,2007,12(3):517-521.(Dai Jinglan,Chen Zhiyang,Ye Xiuzi. The application of ICP algorithm in point cloud alignment[J]. Journal of Image and Graphics,2007,12(3):517-521.)
[3]王欣,张明明,于晓,等.应用改进迭代最近点方法的点云数据配准[J].光学精密工程,2012,20(9):2068-2077.(Wang Xin,Zhang Mingming,Yu Xiao,et al. Point cloud registration based on improved iterative closed point method[J]. Optics and Precision Engineering,2012,20(9):2068-2077.)
[4]左超,鲁敏,谭志国,等.一种新的点云拼接算法[J].中国激光,2012,39(12):211-218.(Zuo Chao,Lu Min,Tan Zhiguo,et al. A novel algorithm for registration of point clouds[J]. Chinese Journal of Lasers,2012,39(12):211-218.)
[5] Silva L,Bellon O R P,Boyer K L. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2005,27(5):762-76.
[6]孙殿柱,史阳,刘华东,等.基于遗传算法的散乱点云最小包围盒求解[J].北京航空航天大学学报,2013,39(8):995-998.(Sun Dianzhu,Shi Yang,Liu Huadong,et al. Solution of minimum bounding box of scattered points based on genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics,2013,39(8):995-998.)
[7] Mavridis P,Andreadis A,Papaioannou G. Efficient sparse ICP[J].Computer Aided Geometric Design,2015,35-36(5):16-26.
[8] Chen Chusong,Hung Y P,Cheng J B. RANSAC-based DARCES:a new approach to fast automatic registration of partially overlapping range images[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2002,21(11):1229-1234.
[9] Aiger D,Mitra N J,Cohen-Or D. 4-points congruent sets for robust pairwise surface registration[J]. ACM Trans on Graphics,2008,27(3):article No. 85.
[10]Meng Yu,Zhang Hui. Registration of point clouds using sample-sphere and adaptive distance restriction[J]. Visual Computer,2011,27(6-8):543-553.
[11]雷玉珍,李中伟,钟凯,等.基于随机抽样一致算法的误匹配标志点校正方法[J].光学学报,2013,33(3):205-212.(Lei Yuzhen,Li Zhongwei,Zhong Kai,et al. Mismatching marked points correction method based on random sample consensus algorithm[J]. Acta Optica Sinica,2013,33(3):205-212.)
[12]武殿梁,黄海量,丁玉成,等.基于遗传算法和最小二乘法的曲面匹配[J].航空学报,2002,23(3):285-288.(Wu Dianliang,Huang Hailiang,Ding Yucheng,et al. Surface matching algorithm based on genetic algorithm and least aquare criterion[J]. Acta Aeronautica et Astronautica Sinica,2002,23(3):285-288.)
[13]平雪良,耿鲁,华婷,等.遗传算法在点云配准技术中的应用[J].机械科学与技术,2010,29(6):809-812.(Ping Xueliang,Geng Lu,Hua Ting,et al. Application of genetic algorithm to point cloud registration[J]. Mechanical Science and Technology for Aerospace Engineering,2010,29(6):809-812.)
[14]郑德炯,卢科青.基于自适应八叉树的三维点云快速拾取方法研究[J].机电工程,2016,33(4):417-420.(Zheng Dejiong,Lu Keqing. Quick picking method for 3D piont cloud based on adaptive octree[J]. Journal of Mechanical&Electrical Engineering,2016,33(4):417-420.)
[15] Lee C Y,Han S K. Evolutionary optimization algorithm by entropic sampling[J]. Physical Review E:Statistical Physics Plasmas Fluids&Related Interdisciplinary Topics,1998,8753(3):3611-3617.
[16]Goldberg D E. Genetic algorithm in search,optimization,and machine learning[M]. Boston:Addison-Wesley Longman Publishing Co,Inc,1989:2104-2116.
[17]曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):3222-3225,3229.(Qu Zhijian,Zhang Xianwei,Cao Yanfeng,et al. Research on genetic algorithm based on adaptive mechanism[J]. Application Research of Computers,2015,32(11):3222-3225,3229.)
[18]雷英杰,张善文,李续武,等. MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:8-14.(Lei Yingjie,Zhang Shanwen,Li Xuwu,et al. MATLAB genetic algorithm toolbox and application[M]. Xi’an:Xi’an University of Electronic Science and Technology Press,2005:8-14.)
[2]戴静兰,陈志杨,叶修梓. ICP算法在点云配准中的应用[J].中国图象图形学报,2007,12(3):517-521.(Dai Jinglan,Chen Zhiyang,Ye Xiuzi. The application of ICP algorithm in point cloud alignment[J]. Journal of Image and Graphics,2007,12(3):517-521.)
[3]王欣,张明明,于晓,等.应用改进迭代最近点方法的点云数据配准[J].光学精密工程,2012,20(9):2068-2077.(Wang Xin,Zhang Mingming,Yu Xiao,et al. Point cloud registration based on improved iterative closed point method[J]. Optics and Precision Engineering,2012,20(9):2068-2077.)
[4]左超,鲁敏,谭志国,等.一种新的点云拼接算法[J].中国激光,2012,39(12):211-218.(Zuo Chao,Lu Min,Tan Zhiguo,et al. A novel algorithm for registration of point clouds[J]. Chinese Journal of Lasers,2012,39(12):211-218.)
[5] Silva L,Bellon O R P,Boyer K L. Precision range image registration using a robust surface interpenetration measure and enhanced genetic algorithms[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2005,27(5):762-76.
[6]孙殿柱,史阳,刘华东,等.基于遗传算法的散乱点云最小包围盒求解[J].北京航空航天大学学报,2013,39(8):995-998.(Sun Dianzhu,Shi Yang,Liu Huadong,et al. Solution of minimum bounding box of scattered points based on genetic algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics,2013,39(8):995-998.)
[7] Mavridis P,Andreadis A,Papaioannou G. Efficient sparse ICP[J].Computer Aided Geometric Design,2015,35-36(5):16-26.
[8] Chen Chusong,Hung Y P,Cheng J B. RANSAC-based DARCES:a new approach to fast automatic registration of partially overlapping range images[J]. IEEE Trans on Pattern Analysis&Machine Intelligence,2002,21(11):1229-1234.
[9] Aiger D,Mitra N J,Cohen-Or D. 4-points congruent sets for robust pairwise surface registration[J]. ACM Trans on Graphics,2008,27(3):article No. 85.
[10]Meng Yu,Zhang Hui. Registration of point clouds using sample-sphere and adaptive distance restriction[J]. Visual Computer,2011,27(6-8):543-553.
[11]雷玉珍,李中伟,钟凯,等.基于随机抽样一致算法的误匹配标志点校正方法[J].光学学报,2013,33(3):205-212.(Lei Yuzhen,Li Zhongwei,Zhong Kai,et al. Mismatching marked points correction method based on random sample consensus algorithm[J]. Acta Optica Sinica,2013,33(3):205-212.)
[12]武殿梁,黄海量,丁玉成,等.基于遗传算法和最小二乘法的曲面匹配[J].航空学报,2002,23(3):285-288.(Wu Dianliang,Huang Hailiang,Ding Yucheng,et al. Surface matching algorithm based on genetic algorithm and least aquare criterion[J]. Acta Aeronautica et Astronautica Sinica,2002,23(3):285-288.)
[13]平雪良,耿鲁,华婷,等.遗传算法在点云配准技术中的应用[J].机械科学与技术,2010,29(6):809-812.(Ping Xueliang,Geng Lu,Hua Ting,et al. Application of genetic algorithm to point cloud registration[J]. Mechanical Science and Technology for Aerospace Engineering,2010,29(6):809-812.)
[14]郑德炯,卢科青.基于自适应八叉树的三维点云快速拾取方法研究[J].机电工程,2016,33(4):417-420.(Zheng Dejiong,Lu Keqing. Quick picking method for 3D piont cloud based on adaptive octree[J]. Journal of Mechanical&Electrical Engineering,2016,33(4):417-420.)
[15] Lee C Y,Han S K. Evolutionary optimization algorithm by entropic sampling[J]. Physical Review E:Statistical Physics Plasmas Fluids&Related Interdisciplinary Topics,1998,8753(3):3611-3617.
[16]Goldberg D E. Genetic algorithm in search,optimization,and machine learning[M]. Boston:Addison-Wesley Longman Publishing Co,Inc,1989:2104-2116.
[17]曲志坚,张先伟,曹雁锋,等.基于自适应机制的遗传算法研究[J].计算机应用研究,2015,32(11):3222-3225,3229.(Qu Zhijian,Zhang Xianwei,Cao Yanfeng,et al. Research on genetic algorithm based on adaptive mechanism[J]. Application Research of Computers,2015,32(11):3222-3225,3229.)
[18]雷英杰,张善文,李续武,等. MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:8-14.(Lei Yingjie,Zhang Shanwen,Li Xuwu,et al. MATLAB genetic algorithm toolbox and application[M]. Xi’an:Xi’an University of Electronic Science and Technology Press,2005:8-14.)