ICP算法在点云配准中的应用

《ICP算法在点云配准中的应用》由会员分享，可在线阅读，更多相关《ICP算法在点云配准中的应用（6页珍藏版）》请在装配图网上搜索。

1、第12卷第3期2007年3月中国图象图形学报Journal of In age and GraphicsVol 12. Nq 3Mar . 2007 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, KP戴静兰“陈志杨”叶修梓“ (浙江大学计算机学院计算机图形图像实脸室.杭州310027) (淅江工业大学软件学院计算

2、机软件研究所.杭州310014)逆向工程中经常需要把多次测量得到的点云进行配准。提出了一种基干特征点的改进EP算法.在采用 主方向贴合法实现初始配准的基础上便用曲率特征点和A-J live寻找煩近点提高了 EP算法的效率。该算法具 有速度快精确度高的特点.并且在实际应用中验证了配准效果和算法稳定性。点云配准最近点迭代算法逆向工程:TP39L 7: A: 1006-8961 (2007)03-0517-05The Applicatbn of ICP A Igor itlm h Po h t C loud A lnni en tDAIJing-Ian, CHEN Thryang , YE Xiu-

3、zi*11 ( Can pit ter Science College, Zhejiang Unhrmity,310027)J (71 inccring College. Zhejiang Unhrrxity of Technology. Himgzhou 310014)Abstract This paper describes an accurate and efficient algorithm of point ebud aub registration The alg)rithn contains hvo steps: initial registration and precise

4、registration We use eigenvecIorsof point cbuds achieve initial registratbn For precise registratbn. an inpR)ved CP( Iterative Cbsest Point) algorithm based on feature points generated by curvature is inlioduccd The effect of tlie alporidm is verified in the iipplicatbnsKeywords point ebud registrati

5、on, iterative cbsest point reverse engineering 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 国家自然科学基金项目(60273060.60333010.60473106);浙江省自然科学基金项目(Y1O4269):2005-09-19: 2005-11-29戴静兰(1

6、981 ).女.2006年于浙江大学茯计算机专业硕士学位主要研究方向为逆向工程与CAD逮模Eniaitshuihnl981 sina can随着计算机辅助设计技术的发展通过实物模 型产生数字模型的逆向工程技术由于它的独特魅力 获得了越来越广泛的应用。逆向工程技术通过实物 数字化技术进厅数据采集。受到測量设备和环境的 限制物体表面完整测量数据的获得往往需要通过 多次測量完成。由于每次测量得到的点云数据往往 只覆盖物体部分表面并且可能出现平移错位和旋 转错位.因此为了得到物体完整表面的点云数据需 要对这些局部点云数据进行整合和配准。点云配准有手动配准、依赖仪器的配准和自动 配准。通常我们所说的点云

7、配准技术即是指最后一 种。点云自动配准技术是通过-定的算法或者统计 学规律利用计算机计算两片点云之间的错位从而 达到把两片点云自动配准的效呆。目前采用的自动 配准技术一般分为初始配准和精确配准两步.初始 配准是为了缩小点云之间的旋转和平移错位以提高 精确配准的效率和趋向精确配准则是为了使两个 点云之间的配准误差达到最小。精确配准一般采用 CP (itemtive cbsest point) 算法。但传统的EP算法计算效率不高，因此国 内外许多研究者都为改进EP算法做出了努力。文 献2醍出了用点的切平面来逼近点云最后归结 为求点到切平面的最小二乘距离的方法但这种方 法速度仍然比较慢。文献丨3结合

8、了逆向定标法和 随机搜寻法来提高速度但会对配准精度产生一定 的影响。文献丨4 提出了一种CL (iterative cbsest line)算法通过直接对两个点云中的点连线并寻找 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved, 第3期戴静兰锌：ET算法在点云配准中的应用521对应线段进行配准但存在无法保证线段之间的对 应关系的缺陷。文献5屣出用扰动平移矩阵法加 快收敛速度但该方法只能对某些模型有较明显的 效果。常见的初始配准方法有：中心重合法简单 的把两个点云的重心重合这种方式

9、只能缩小平移 错位而无法缩小旋转错位:标签法门即在測量时 人为地贴上一些特征点.然后使用这些特征点进行 定位，这种方式仍然是依赖于测量和仪器的:提取特 征法有提取平面特征、提取轮廓曲线等.这种 方式要求点云有比较明显的特征。通过对目前点云配准算法的分析针对EP算 法进行了以下算法改进研究：(1) 对于点云初始配准提出了一种新的主方 向贴合法能够快速缩小平移和旋转错位，并且对仪 器和点云都没有特殊要求具有广泛的适用性；(2) 对于精确配准，改进了 EP算法，提出了一 种基于特征点的EP算法。通过计算曲率特征提取 点云特征点并使用k证c搜寻最近点.大大提高 了算法效率.尤其适用于海量数据的计算，具

10、有良好 的收敛速度和配准精度。2为了缩小点云之间的旋转和平移错位.使得精 确配准不致趋向错误的方向需要进行点云初始配 准。本文利用点云主方向贴合法实现自动初始配 准具有方便快捷精确的效果。每个点云都存在一个空间上的主方向，这个主方 向可由计算点云中所有点的特征向量得到，根据特征 向量还可以得到与主方向垂直的两个次方向。由此 可建立一个以点云重心为原点点云主方向以及次方 向为坐标轴的一个参考坐标系。这样对于相似度大 的两个点云只要把两个参考坐标系调整到一致即 可以实现点云配准。对于差异较大的点云通过这 种方式也可以达到缩小点云之间错位的目的。由于主方向具有正反两个方向因此可能出现 配准后两个点云

11、正好相差180为勺情况所以配准后 还需测试是否出现这种情况。本文通过计算两个点 云的包围盒来测试两点云是否重合。设VR吓角R 代表reference)为参考点云包围盒体积听(下角T 代表为目标点云包围盒体积，匕为参考点云 和目标点云包围盒相交得到的包51盒的体积。则包 围盒重合系数为f = (Vt XVJ/(VR XVT)(1)如果/T,T为设定阈值，则两点云大致重合。 否则两点云不重合，反转参考坐标系的x轴或丫轴 再次测试。如果4种可能性都测试过并且没有任 何一个/大于T.则说明两点云差异较大，取丿最大 的那种即可。算法流程说明如下：(1) 读取参考点云和目标点云；(2) 分别粗略选取两片点

12、云可以重叠部分；(3丿分别用雅克比法计算选取区域的特征向量 和特征值,按特征值从大到小排列特征向量为EV0. EV. EV,;(4) 分别计算点云重心C以Q为原点.以EV。 为X轴，EV,为y轴,EV0 XEV,为Z轴.建立参考 坐标系：(5) 由两个坐标系计算得到坐标变换矩阵； (6丿根据坐标变换矩阵变换目标点云坐标；(7丿测试变换后点云和参考点云是否大致重 合.不重合则反转目标点云X轴或丫轴，跳到步 骤5;(8)点云重合.结束。3为了尽可能配准两个点云使它们之间的误差最 小还需在初始配准的基础上进行自动精确配准。 本文采用基于特征点的EP算法进行精确配准，该 算法可以有效提高计算速度对于海

13、量数据点云效 果十分显蓍，可以有效缩短原EP算法的计算时间0在研究EP算法之前必须先了解其中所使用 的一个关键算法，即对应点集配准算法 (correjponding point set registratbn) 0A 1对应点集配准算法的目标在于寻找最小二乘逼 近的坐标变换矩阵对于互相对应的两个点集.可以 采用单位四元数法得到。若目标点集P对应于参考点集X.对应点集应 满足以下条件：(I) P中点的个数Np和X中点的个数Nx相 等即 Np =Nx；(2丿对于P中每一个点P,都应该对应于X中 具有相同下标啲X,即p, =X/0设旋转变换向量为单位四元数* = /缆4经0八其中4 AO 并且4+N

14、+丕+4=1可 得3 M旋转矩阵R()o设平移变换向量为qT = 绘绻广可得完全坐标变换向量q=/qj qr。则 求对应点集间的最佳坐标变换向量问题可转化为求 (使得函数f(q)x R(*)p, orII2 最小化的问题。算法流程如下：(1丿得到对应点集P和X：(2)计算目标点集P的重心和参考点集X的重心:1 T恳P1 二恳P 由点集P和X构造协方差矩阵力P.X(P. -Mp)(X. -Mx) /p. X)/ - M p M x(4丿由协方差矩阵构造4熔对称矩阵血 P.X)LA P X Q P. X Q P.X)I(5)其中，是3 X3单位矩阵.tr(Ep.x)是矩阵Ep.x的 迹 = /A2

15、3 Aji A|2 , A( y = p.x -2 P.XX(5丿计算Q (L p.x )的特征值和特征向量其最 大特征值对应的特征向量即为最佳旋转向量乐 /绑彳0你/(6丿计算最佳平移向量q=M x )U p(6)其中R(Qk 丿二2(qi(h - 5丿2 22 2鬲 =1,0, 0, 0,0, 0, 0 |T,=0;(4) 利用k-d tec寻找F在X中的最近点Y:Yt =C(F*, X) (cost O ( bgVx )，-(5丿计算坐标变换向量和误差.dk) =0(Fo, Yk) (cost O(NJ；(6丿特征点集坐标变换.F4 + 1 =qx(Fo)；(7)判断i吴差是否收敛如果d

16、k - J4+1 0则收敛.否则跳到步骤4(8丿误差收敛于I,目标点云坐标变换 P、 q* (P)；(9)结束。由图2可知，仅用初始配准会造成配准精度不 够.不能满足要求。 align the pointebud data in Fig 2(a)配准前(b)配准后图5图3数据采用本文算法后的配准Fig 5 The result of using our algorithn to align the pointebud data in Fig 3本文算法不仅具有良好的配准精度.也具有令 人满倉的配准速度。与原来的CP算法相比基于 特征点的改进EP算法在海量数据下的效率较高。由表1中的比较分析可以

17、看出.点云数据点数 量越大本文的改进:P算法与原算法在配准速度 上的优势越明显。(a)配准前(b)配准后0 6局部点云的配准Fig 6 The result of using our alg)rithn G align the pointcbud data partlyTah 1 The perfonnances c(m)parison between tlie two algorithm s of huge data数据点数-平均花费时问(s)EP算法改进算法117039. 462Q 1152063159. 099Q 34463 868286 204ft 610127 0601 099. 4

18、221. 204215 34720002 079705 82120006 9065本文提出的主方向贴合法和基于特征点的改进 EP算法的结合可以快速消除点云模型之间的错 位能够使同一个模型的多次测量数据之间保持一 致性和完整性在海量数据的计算中尤其具有优势, 是逆向工程点云处理过程中相当有用的一个算法。在实际应用中.本算法有较好的配准精度和收 敛速度具有较高的实际应用价值。(References)1 Besl P J. Mckay N D. A method for ivgistniibn of 3-d shapes) J . EEE Tmnsaclbns on Paltem Analysis

19、and Machine Intelligence. 1992. 14(2): 2392562 Chen Y. Medbni G Object modeling by registniibn of multph range inages (A |. h Proceeding of the 1991 IEEE htematbnal Conlerence on Robotics and Aukmatbn | C Sacnniento CA VSA. 1991: 272427293 Bhis G. Levme M D. Registering muhivieu1 mnge data k create

20、3D oemputer graphics! J . EEE Transactbns on Pattern Analysis and Machine Intelligence. 1995. 17(8): 8208244 LiQ. Griffiths J G hemlivc ebsest gccnietnc objects registnubi | J |. Ccnputers andMatlieinaticswith Applicatons. 2000. 40( 10): 1171-118 &5 ZH.ANG Xue*chang, XI Jun*t)ng Y-KN Jun*qi Research

21、 on digital measuivnient technobgy based on point cbud data of conplex surfaces J . Ccmpuier htegrated Manufacturing Systems. 2005. 11 (5): 727731. |张学昌习俊通.严第無.基于点云数据的复杂塑 面数字化检测技术研究|J】计算机隼成制港系统.2005 11(5): 727-731. 16 LUO Xian-bo. ZHONG Yue*xian. LI Ren-ju Data ivgistrutbn h 34) scanning systems | J

22、 |. Journal of Tsinghua University ( Science aid Technique). 2004 44(8): 1104 1106【罗先波钟约先. 李仁举.三维扫描系统中的数据配准技术IJ.清华大学学旅(自然科学版).2004. 44(8): 1104-1106 |7 WUM in ZHOU Lai由ui. WANG Zhairdong r/ al Research cf mulli*view rcgistmtbn and integration on measured point cbud data J . Journal of Nanjing Univer

23、sity of Acmnautics and AstK)nautic2v 2003. 35(5): 552-557. |吴缎.周来水.王占东等.测量点云 数t的多视拼合技术研究IJL南京航空航天大学学报.2003 35(5): 552-557. 18 HE Wcn-feng. ZHA Hong-bui Rcgistmtbn of mnge data based on planarfeaturesl A |. in: The A dvancemeni of Artificial htelligence h China: 2(X)3 C . Beijing The Publishing Compa

24、ny of Beijmg Umyvrsityot Hosts and releammun tea tons. 2003: b45 (4K I 何文 峰查红彬.基于平面持征的探度图像配准【A I.见：中国人工 智毙进展2003 上卷)|C|.北京：北京邮电大学出版社.2003: 643 64& |9 Yang R. Allen P Registering, inlcgratiiig. and building cad models finn range dati A . h: IEEE htematbnal Conference on Robotics and AutomatbnC. Leuven. Belgiun. 1998: 3115312Q 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved,