IT教程 ·

3D点云配准算法简述

Java 添加、读取、删除Excel文档属性

蝶恋花·槛菊愁烟兰泣露

槛菊愁烟兰泣露,罗幕轻寒,燕子双飞去。

明月不谙离恨苦,斜光到晓穿朱户。

昨夜西风凋碧树,独上高楼,望尽天涯路。

欲寄彩笺兼尺素。山长水阔知那边?

——晏殊

导读:
3D点云配准是盘算机视觉的症结研讨问题之一,在多范畴工程运用中具有重要运用,如逆向工程、SLAM、图象处置责罚和模式识别等。点云配准的目的是求解出统一坐标下差别姿势点云的变更矩阵,应用该矩阵完成多视扫描点云的准确配准,终究猎取完全的3D数字模子、场景。本质上,关于六自由度(扭转和平移)的3D点云配准问题是典范的非凸优化问题,其目的函数在六维可行域空间中具有多个波峰波谷,即优化求解历程当中受初始变更矩阵影响,轻易堕入部份最优解。点云配准效果虽然受限于其初始位置,然则初期的一些部份的配准算法对处理点云配准问题具有重要的运用、启发意义。因而,本文重点引见一些鲁棒性或效力较好的部份、全局3D点云配准算法。

3D点云配准算法简述 IT教程 第1张

--部份的3D点云配准算法--

ICP(Iterative Closest Point)算法是运用最普遍的3D点云配准算法之一, 其经由历程欧式变更求解出两片点云的扭转平移矩阵及对应的配准偏差。
ICP算法的中心头脑能够简述为:假定数据点云 。向源点云 挪动配准,ICP算法经由历程不停求解预计的变更矩阵,直到RMSE(Root Mean Square Error)配准偏差收敛于部份最优解 (每一次迭代历程能够形貌为:在 中搜刮关于 的近来邻点集,组织协方差矩阵,奇异值分解取得单元四元数,进而求解扭转矩阵,平移向量则由对应点云的质心肯定,由此完成数据点云的扭转平移变更)。个中,关于RMSE的配准模子能够示意为:

3D点云配准算法简述 IT教程 第2张

在对扭转、平移可行域举行参数化的前提下,关于 范数配准模子的点云配准问题能够转化为关于扭转和平移的非凸优化问题。ICP虽然具有简朴、收敛性好等长处,但其受限于点云初始位置且在处理具有离群值的点云配准问题,轻易堕入部份最优解。
为了进步ICP算法的鲁棒性,学者提出了一系列的变种ICP算法。LM-ICP算法提出应用Levenberg-Marquardt算法对ICP配准模子举行求解,并应用DT(Distance-Transform)算法替换KD-tree搜刮近来邻点时,减小点云初始位置对其配准效果的影响,并进步了配准效力。Chetverikov等。在ICP算法的基础上,提出了鲁棒性更好、更有用的Trimmed ICP 算法,对每次迭代婚配获得的近来邻点举行挑选,即对两两预计的婚配点的欧式间隔举行排序,摒弃个中间隔较大的点集,责罚的百分率由核函数动态盘算。Trimmed ICP 算法运用于具有离群值、噪声的点云配准问题时,能取得优越的配准精度。但是,高占比的离群值对点云配准算法的鲁棒性要求仍然是庞大的应战。Bouaziz等提出Sparse ICP算法应用希罕示意理论对进一步革新ICP算法的鲁棒性,即在 范数配准模子上增添p范数的责罚项,进步每次迭代中求解婚配点的准确性,但其应用增广拉格朗日求解大规模点云配准问题时效力较差。Mavridis等连系模拟退火算法提出了更加高效的Efficient Sparse ICP算法,加快点云配准的收敛速率。

3D点云配准算法简述 IT教程 第3张

为了进一步进步配准效力,Li等应用CAD模子的三角切片性子,高效求解近来邻点,保证了配准精度,并进一步提出动态步长试探性配准,防止收敛曲线涌现震动。但现实扫描点云的散布并不是匀称,基于CAD 模子的配准要领仅适用性于抱负点云配准问题。Zhu等经由历程设置硬、软指标完成点云的高效准确配准,即在每次迭代历程当中应用双向婚配的体式格局对噪声及离群值举行责罚。然则配准效果受限于核函数中参数的预设值。上述基于 范数的迭代近来点配准算法重要包括ICP算法及其变种算法,该类部份的配准算法受限于点云初始位置,仅适用于小角度错开的点云配准问题。在人机交互取得较好点云初始位置的前提下,迭代近来点算法在处理点云配准问题时具有优越的鲁棒性,但也存在一些能够继承优化的不足,能够总结为三点:
(一)受限于主身分剖析、奇异值分解算法,迭代近来点算法虽然具有优越的收敛性,但其迭代次数较多,后期收敛迟缓。
(二)受限于数据结构,迭代近来点算法在每次迭代历程当中搜刮近来邻点的本钱较高,KD-tree虽然搜刮效力较高,但仍没法满足于处理大规模点云的配准问题。
(三)受限于点云的希罕特性,而且现实运用中重要经由历程对点云举行下采样以进步配准效力,迭代近来点算法没法完成准确配准。
针对上述不足点,学者区分于迭代近来点的配准算法构建新的配准模子,如几率密度模子、隐式最小二乘函数和高斯夹杂模子等,并连系别的优化算法进步点云配准的效力和精度。Biber等基于几率密度模子提出了Normal Distribute Transform(NDT)算法,即运用D维的高斯函数作为配准模子:

3D点云配准算法简述 IT教程 第4张

NDT算法经由历程对源点云Q举行体素离别,即求解点云Q的围困盒,并对该围困盒举行细分,对包括于差别体素的源点云离别构建高斯模子。该算法最大的上风是迭代历程当中不须要求解近来邻婚配点,其盘算庞杂度较低。个中体素的离别体式格局与点云配准的精度和效力相干,可应用回环控制点云配准精度,重要运用于机器人的及时Simultaneous Localization And Mapping(SLAM)环节。Jian等提出应用夹杂高斯模子替换单一的高斯模子。为了进步配准模子的鲁棒性,体素高斯模子被离别举行加权盘算,个中多标准的点云配准要领运用较为普遍,如NDT、EM-ICP等。上述基于几率模子的点云配准算法只需在每次迭代中求解雅可比矩阵,盘算庞杂度大大下降,且Magnusson等指出NDT算法较ICP算法能更好地防止点云初始位置对配准效果的影响。
针对点云配准的精度问题,部份学者提出了点到面的点云配准算法,应用曲线、曲面拟合求解出源点云的显、隐式表达,并应用法向量求解每次迭代中的对应点对,如下图所示

3D点云配准算法简述 IT教程 第5张

Liu等提出应用动曲面构建源点云的拓扑外形完成点云配准,重要运用于简朴外形组合而成的零件点云配准问题,如圆锥、圆柱、扭转扫掠螺旋曲面等。为了处理庞杂外形点云的配准问题,学者提出了鲁棒性更强的曲面拟合要领,如B样条模子、八叉树结点等。该类配准算法的有用性更强且运用局限更广。在此基础上,张等剖析了挪动最小二乘法在曲面拟合运用中的生长及其优越性,并提出该要领能完成准确的点云配准且对噪声具有优越的鲁棒性。然则此类算法其须要预先设置较好的参数,如分支数、权值等。
相较之下,迭代近来点的点云配准算法的鲁棒性更强,因其不需设置冗余的优化参数,但别的算法则在进步效力和精度方面更具上风。上述部份算法及其变种普遍运用于处理点云配准问题,且可有用防止噪声和离群值对配准效果的影响。然则,此类配准算法受限于点云初始位置,轻易堕入部份最优。区分于此类具有鲁棒性的部份配准算法,学者针对点云初始配准位置的优化问题提出了一系列全局优化的配准算法。

--全局的3D点云配准算法--

Silva等将点云配准问题转换为多变量的非凸优化问题,并连系遗传算法求解出全局优化的变更矩阵,能有用防止点云初始位置对配准效果的影响。其他运用于点云全局配准的智能算法还包括粒子群算法、模拟退火等。但是,此类启发式算法需屡次挪用配准模子举行优化求解,在处置责罚大规模点云配准问题时效力较低,且其全局解并未有严厉的证实。为了进步点云配准效力,部份学者提出经由历程组织多少不变量婚配对应点对(理论上三组婚配点对便可求解出点云配准的变更矩阵),该类要领一样不受点云初始位置影响,且盘算庞杂度更低。Wyngaerd等经由历程曲率特性求解对应点对,完成点云全局配准;Gelfand等则经由历程组织积分体积特性盘算婚配点对求解变更矩阵;Rusu等提出组织点特性直方图作为部份形貌符。RANSAC要领被直接运用于点云配准,但受限于其配准效力,一开始重要运用于处理二维的点云配准问题。随后,Aiger等应用4点法组织多少特性进而提取希罕的婚配点对,使得RANSAC要领能有用地运用于三维点云配准。当点云的特性不变量较为显著时,基于多少不变量的点云配准要领能够作为机能优秀的算法运用。
Yang等基于 范数配准模子初次推导出了关于六维变更域的上下界函数,并应用分支定界算法提出了全局优化的Go-ICP算法,且该算法有用地证实了所求解变更矩阵的全局最优性。然则,Go-ICP算法需连系DT算法才大概高效地完成点云配准,而DT算法的初始化较为耗时。Lian等提出了更加高效的AMP算法举行点云全局优化配准,但其重要适用于图象处置责罚范畴。为了进步点云配准效力,Chin等提出了Glob-GM-ML算法将六维的点云配准问题分解为两个自力的三维平移、扭转问题,该算法经由历程构建特性不变量求解平移参数并以为其在配准问题中是先验的,即六维的点云配准问题有用地转化为关于扭转的三维非凸优化问题。该要领应用解耦的头脑高效地完成点云全局优化配准,是近年研讨的热门之一,Liu和Li等基于扭转不变量并应用分支定界要领求解出全局优化的平移参数,进而完成高效的点云全局优化配准。

3D点云配准算法简述 IT教程 第6张

为了处理组织扭转不变量是的超参数设置问题,Yang等应用多项式时候提出了TEASER算法对处理具有极高离群值的点云全局配准问题具有优越的鲁棒性。区分于运用于CPU通例硬件的全局点云配准算法,GOGMA算法等基于夹杂高斯模子构建了适用于GPU框架的高效点云全局优化配准算法,即在全局优化历程当中可应用GPU框架完成并行盘算,进步加快点云全局优化配准效力。

参考文献

[1] Besl P J, Mckay N D. A Method for Registration of 3-D Shapes[M]. 1992: 239-256.
[2] Yang J, Li H, Campbell D, et al. Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2016, 38(11): 2241-2254.
[3] Fitzgibbon A W. Robust registration of 2D and 3D point sets[J]. Image & Vision Computing, 2001, 21(13): 1145-1153.
[4] Moré J J. The Levenberg-Marquardt algorithm: Implementation and theory[J]. Lecture Notes in Mathematics, 1978, 630: 105-116.
[5] Chetverikov D, Svirko D, Stepanov D, et al. The Trimmed Iterative Closest Point algorithm[J], 2002.
[6] Bouaziz S, Tagliasacchi A, Pauly M. Sparse iterative closest point[C]. Eleventh Eurographics/acmsiggraph Symposium on Geometry Processing, 2013.
[7] Mavridis P, Andreadis A, Papaioannou G. Efficient Sparse ICP[J]. Computer Aided Geometric Design, 2015, 35-36(C): 16-26.
[8] Li W, Song P. A modified ICP algorithm based on dynamic adjustment factor for registration of point cloud and CAD model[J]. Pattern Recognition Letters, 2015, 65(65): 88-94.
[9] Zhu J, Jin C, Jiang Z, et al. Robust point cloud registration based on both hard and soft assignments[J]. Optics & Laser Technology, 2019, 110: 202-208.
[10] Biber P, Strasser W. The normal distributions transform: a new approach to laser scan matching[J]. Proc.of IEEE/RSJ Intl Conf.on Intelligent Robots & Systems, 2003, 3: 2743-2748 vol.3.
[11] Engel J, Schöps T, Cremers D. LSD-SLAM: Large-Scale Direct Monocular SLAM[M]. 2014.
[12] Jian B, Vemuri B C. A Robust Algorithm for Point Set Registration Using Mixture of Gaussians[C]. Tenth IEEE International Conference on Computer Vision, 2005.
[13] Granger S, Pennec X. Multi-scale EM-ICP: A Fast and Robust Approach for Surface Registration[C]. Computer Vision - ECCV 2002, 7th European Conference on Computer Vision, Copenhagen, Denmark, May 28-31, 2002, Proceedings, Part IV, 2002.
[14] Magnusson M, Nuchter A, Lorken C, et al. Evaluation of 3D Registration Reliability and Speed - A Comparison of ICP and NDT[C]. IEEE International Conference on Robotics & Automation, 2009.
[15] Liua Y. Constrained 3D shape reconstruction using a combination of surface fitting and registration[J]. Computer-Aided Design, 2006, 38(6): 572-583.
[16] Huang Y, Qian X, Chen S. Multi-sensor calibration through iterative registration and fusion[J]. Computer-Aided Design, 2009, 41(4): 240-255.
[17] Huang Q-X, Adams B, Wand M. Bayesian Surface Reconstruction via Iterative Scan Alignment to an Optimized Prototype[J]. Proc Eurographics Symposium on Geometry Processing, 2007, (2007): 213-223.
[18] Levin, David. The approximation power of moving least-squares [J]. Mathematics of Computation, 67(224): 1517-1532.
[19] Zuppa C. Good quality point sets and error estimates for moving least square approximations[J]. Applied Numerical Mathematics, 47(3-4): 575-585.
[20] Dey T K, Sun J. . An Adaptive MLS Surface for Reconstruction with Guarantees[C]. Third Eurographics Symposium on Geometry Processing, Vienna, Austria, July 4-6, 2005, 2005.
[21] Ahn S J, Yoo J, Lee B G, et al. 3D Surface Reconstruction from Scattered Data Using Moving Least Square Method[C]. Image Analysis and Processing - ICIAP 2005, 13th International Conference, Cagliari, Italy, September 6-8, 2005, Proceedings, 2005.
[22] Silva L, Bellon O R P, Boyer K L. Multiview range image registration using the surface interpenetration measure [J]. Image & Vision Computing, 2007, 25(1): 114-125.
[23] Sandhu R, Dambreville S, Tannenbaum A. Point set registration via particle filtering and stochastic dynamics[J]. IEEE transactions on pattern analysis and machine intelligence, 2010, 32(8): 1459-1473. [24] Wachowiak M P, Smolíková R, Zheng Y, et al. An Approach to Multimodal Biomedical Image Registration Utilizing Particle Swarm Optimization[J]. Evolutionary Computation IEEE Transactions on, 2004, 8(3): 289-301.
[25] Papazov C, Burschka D. Stochastic global optimization for robust point set registration[J]. Computer Vision & Image Understanding, 2011, 115(12): 1598-1609.
[26] Wyngaerd J V, Gool L V. Automatic Crude Patch Registration: Toward Automatic 3D Model Building[J]. Computer Vision & Image Understanding, 2002, 87(1–3): 8-26.
[27] Desbrun M, Pottmann H, Gelfand N, et al. Robust Global Registration[J]. Proceedings of Eurographics Symposium on Geometry Processing, 2008: 197.
[28] Rusu R B, Blodow N, Beetz M. Fast Point Feature Histograms (FPFH) for 3D registration[C]. Robotics and Automation, 2009. ICRA '09. IEEE International Conference on, 2009.
[29] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[M]. ACM, 1981: 726-740.
[30] Irani S, Raghavan P. Combinatorial and experimental results for randomized point matching algorithms[C], 1996.
[31] Aiger D, Mitra N J, Cohenor D. 4-points congruent sets for robust pairwise surface registration[J]. Acm Transactions on Graphics, 2011, 27(3): 1-10.
[32] Lian W, Zhang L, Yang M H. An Efficient Globally Optimal Algorithm for Asymmetric Point Matching[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2017, 39(7): 1281-1293.
[33] Chin T J, Suter D. Fast Rotation Search with Stereographic Projections for 3D Registration[C]. IEEE Conference on Computer Vision and Pattern Recognition, 2014: 3930-3937.
[34] Liu Y, Wang C, Song Z, et al. Efficient Global Point Cloud Registration by Matching Rotation Invariant Features Through Translation Search: 15th European Conference, Munich, Germany, September 8–14, 2018, Proceedings, Part XII[M]. 2018.
[35] Li X, Liu Y, Wang Y, et al. Fast and Globally Optimal Rigid Registration of 3D Point Sets by Transformation Decomposition[J], 2018.
[36] Yang H, Carlone L. A Polynomial-time Solution for Robust Registration with Extreme Outlier Rates[J].
[37] Campbell D, Petersson L. GOGMA: Globally-Optimal Gaussian Mixture Alignment[J].
[38] Straub J, Campbell T, How J P, et al. Efficient Global Point Cloud Alignment using Bayesian Nonparametric Mixtures[J].

 

并发编程之Master-Worker模式

参与评论