点到邻域重心距离特征的点云拼接

1、第5期辛伟等:点到邻城重心距鳥特征的点云拼接887第16卷第5期2011年5月中国图象图形学报Journal of Image and GraphicsVol. 16, No. 5May. 2011第5期辛伟等:点到邻城重心距鳥特征的点云拼接887中图法分类号：TP3M.7文駅标A 文It号:1006.8961(2011)05-0886-06论文*引侑:辛Hi. IT杰信点動邻域倉心距鳥待征的点云拼槎J中国图您图形学报.2011.16(5): 186-891点到邻域重心距离特征的点云拼接辛伟，普杰信(河剧科技大学电子信AI8学院烙阳471003)摘 S:不規则曲面的拼接是3维拼接中的难点，提岀

2、采用不規则曲面点与其一邻城点亶心间的距冑作为刚性待 征对点云进行粗配准使用迭代量邻近点算法和刚性特征进行稱配准。实购结果我明两性特征迭代量邻近点算 法的谋羞收敛速度显菩提高。当点云为重心距薦大于10的差姿玄时该算法与不进行組配准的迭代最邻近点算 法相比收Aj和拼接质St都有较大提奇。关词：不規则曲面；待征配准；賣心距离特征；迭代最邻近点算法Point cloud integration base on distances between points and theirneighborhood centroidsXin Wei, Pu Jiexin(Ekdrcnic Information E

3、nginttring College9 Henan Univmity cf Sciener & Technology. iMoycng 471003 China)Abstract： The nregular surface registration it a challenging ifttue in the three-dimensional regiUration. Thm paper proposed an approach to point cloud coame registration by using the distance between an irregular surfa

4、ce point and the center of mam* of its one length neighboring points as the rigid feature, and to point cloud fine registration by the iteration close point Algorithm and rigid feature The experimental results show that the error convergence rate of the rifpd feature iteration close point algorithm

5、is tignificantly improved And then, both the convergence rate and the registration quality of the algorithm are improved v coapared with iteration close point algorithm that not have coarse registration v rhen point clouds which the distance between the center of gravity is bigger than 10.Keywords：

6、irregular surface： feature registration； center of mass dintance feature； iteration close point algorithm第5期辛伟等:点到邻城重心距鳥特征的点云拼接887第5期辛伟等:点到邻城重心距鳥特征的点云拼接887ttMSM: 2010-01 -21 回日期：2010-06. IIH金项目：河剧省墓与前沿技术研究计划虞目(102300410113)；烙阳市大科技攻关计刘项H(070l04IA)o第一作耆介:辛伟(1986- )男。洵爾科技大学计算机软件与理论专业績七研丸生主要研究方向为图处理、计算机

7、 图舷学。K-mail：buthionmadi0 163. com00引言3维扫描技术在逆向工程、文物保护、医学图 像处理.计算机视竟.人脸识别等领域广泛应用点 云拼接已成为研究热点。点云曲面可以看作是一动 线在空间运动的轨迹，该动线称为母线。母线做不 规则运动形成不規则曲面，而做规则运动则形成规 则曲面。由于不规则曲面的复杂性使不规则曲面 的拼接成为拼接中的难点。运用最为广泛的点云拼接方法是由Besl等 人山和Chen等人分别提岀的迭代最邻近点算 法简称ICP (iterative close point)算法两者的区 别是定义邻近点间的距髙不同，B“l使用点点距离， 而Chen使用点面距离

8、。ICP算法属于迭代下降算. 法，其在两点云中寻找杲邻近点作为配准点，之后通 过优化均方谋差函数来求取旋转、平移矩阵。该算 法在点云姿态较好时，能够得到好的精度，但收敛较 慢。由于其迭代耗时、配准易受噪声干扰、易陷入局 部最;卜、对初始姿态不好的点云拼接精度较差甚至 失败2卯因此使点云在精配准前有好的姿态、提离 配准的准确性、滅小收敛误差和提高拼接速度成为 研究的重点。目前主要采用粗配准使点云有好的姿态，然后 使用改进的ICP算法精配准来克眼ICP算法的峡 陷lM，o其中待征法提取点云的刚性特征，利用特 征进行粗配准随后使用特征改进的ICP算法进行 精配准。待征法的优点是不需要寻找全部点的配准

9、 点和初始迭代矩阵。由于特征的独特性，且配准点 不会集中在一个区域，可减小陷入局部最小的几率。点云的刚性特征有曲率、点与邻域重心的距离. 点法向与邻域点法向的夹角、局部张量等”曲率特征拼接去由于点云的曲率不会随着整个 点云的运动而变化而点的曲率一般都具有唯一性, 因此采用曲率待征来配准可提高拼接精度和加快 配准速度。戴静兰等人l，0Yang等人使用曲率 特征进行拼接，但使用了不同的曲率估计方法。估 计曲率的方法有Chen和Schmitt提岀的最小二乘 法问%Taubin提出的Taubin估计法.Meyer等人 提岀的Voronoi法M、董辰世和汪国昭在文献12 基础上改进的估计去。由于估计曲率

10、需耍使用邻近 点因此都摆脱不了噪声的影响而噪声对曲率估计 的形响使得曲率特征法的鲁棒性变差，且估计曲率 需要消耗大敖时间。Basdogan等人何对敵乱的点云拼接提岀使用 KNN估计局部邻近点，将点与邻域重心的距离作 为点的待征。提取邻近点数目大的点构成点集，在 点集中使用特征却找配准点对，之后使用or = Otmars = II 5和II评价拼接质址。该方 法要求噪声不能太大，对邻近点数目估计的准确性 要求高而估计邻近点数目时没有考虑点云的拓扑 特征，邻近点数目估计的准确性不一定可靠。Jiang等人提出使用夹角待征进行拼接。将 点与邻近点法向之间的夹角作为该点的K维待征， 利用K维夹角特征寻找

11、配准点对进行拼接。该方 法不但噪声形响法向估计，而且估计法向时也会引 入误差，从而形响夹角转征估计的准确性。该方法 加快了误差收敘速度，但计算和比较点之间的Q维 夹角待征将耗费不少时间。Mian等人3；提出使用方体提取局部区域并计 算局部区域的张尅恃征。先利用张誥待征寻找匹配 区域进行粗配准然后使用ICP算法进行精配准。 该方法抗噪声能力强、鲁棒性好，但要得到好的拼接 结果要求点云重桂率大于50%，且匹配局部区域的 寻找和使用张量待征配准需耗费大量时间。对三角网格化的点云，本文使用点与邻域雨:心 的距离作为刚性待征进行拼接。首先计算点到邻域 重心的距离待征,使用刚性特征进行粗配准;然后用 特征

12、改进的最邻近点算迭进行精配准拼接后使用 均方误差评价点云的拼接质。该方法实现了对不 规则曲面点云的准确护接，在收敛速度上有较大 提岛。1 ICP算法假设目标点云为p参考点云为x。p中点的 个数为N.,X中点的个数为必,且N,WN“算法步骤：1）计算两点云的最邻近点L = c（p.,x）；对 于p中的毎个点，找到1（于x的与p中点最近的 点,S.Nr = Nro2）计算配准矩阵（R.,T.） =（?（?.,KJ；使用 奇异值分解法（svd）对点集p和点集y的配准点 求旋转平移矩阵R和儿3）求旋转、平移后的点云数据:r. =+几。4）求均方误差并设定阈值终止迭代。定义旋 转平移后两点云之间的距离I

13、I 几（心.必r给定阈值/ 0,当时迭代终止。2重心特征法重心距离特征：点到其K邻域点重心间的距 离。K邻域指点到邻近点的最小路径为K,本文取 K为1,如图1所示。图1点的I邻域Fig. 1 One length neighborbocxlB of point不规则曲面都有凸起区域如图2所示,有利于 特征提取。本文使用1邨域雀心距离待征，便于提 髙配准速度；若使用多邻域重心距离特征，有利于配 准，但计算多邻域重心匪离待征要耗费更多时间。笫5期辛佑等：点到邻域jfc心距离特征的点云拼按889(a) rhi chicken 2 点云Fig. 2 SIiuh of point cloud假设点其邻域

14、真心为0 P点法向为/可采 川邻血法向的半均值来估讣。如图3所示.提取的 車心距离特征为：1）当彳-P和/的内积为负时丿 为凸点；（特征値为P和q间的距离；2） 气q-p和 /的内积为正时，则P为凹点，其待征值为0。（b）阿点图3点的类型Fig. 3 Kind of points若曲面中点的邻近点数目和邻近点位置不同. 则重心距离特征亦不同，从而特征具有独特性:，本 文定义凹点待征为零.是为了羅免凹点影响配准的 准确性。亜心待征法由粗杞准和轿配准组成，粗配准的 冃的是便点云获鮒好的姿态，而刚性特征轲配准的 冃的是加快收敛速度和握岛配准擀度。因为对于点 云中的点，用ICP算法在另外一个模型上可能

15、同时 存在多个与该点距离最近的点，从面引入错溟的配 准点。而当两点云姿态不好时，用最邻近点法找到 的邻近点的准确性亦不高c经过粗配准后的点云冇 了较好姿态.使用垠邻近法找到的邻近点准确性捉 高.但仍存在错谋点对；此时用待征排除谋配准点 对，可以捉高配准的准确性，加快误差收效連度3方法步骤3.1粗配准首先计算頤心距离待征，之片提取各点云中n 个币心距离待征值杲大的点构成集合0和Q：c 然后选取待征阈值*寻找配准点，其中阈值应大于 50%以上0和中点对之间的特征距离II要剔 除持征距离大的点对最启对配准点对使川SVD 分解法求取切治矩阵。对点P,记其丨邻域为nearp = /-化丨；皿emr（P,

16、）为点P,到其1邻域点 車心的距离。步骤：1）对点zi 1和2计算1邻域near, .near,和朿 心距离待征 vdcentrl jdcrntr,2）找出两点云中“个特征值最大的点“应大 于1 00）a选取适当的特征配准闹值7寻找配准点 对，其中丁应大F 50%以上的点对特征距离，配准 点对嘤满足特征距离小-FWffi.H空间距离辰近3）使用SVD法求旋转、平移矩阵。3.2精配准对干机配於后的点云，便用噸心序离待征改进 的ICP算法箱配准，简称C.ICP并法该算法使用 特征在最邻近点对中寻找配准点对，同时耍求配准 点的邻点数相同，以提高配准点对的准确性.为避 免陷入前部笊小,选取很小的迭代终

17、止闽伉并要求 均方误基多次小于终止國值。迭代终止后将配准点 对之间的平均距离作为均方误差评价点丘拼接 质量。步骤:1）将粗配准得到的矩阵作为初始迭代矩阵或 将点云2旋转平移后处干新的位国。2）选取新的持征阈值八但比配准中的略小 一些。先便用册邻近点法和待征周值来寻找配准点 对然后使用SVD法求旋转平移矩阵和均方谋雄。3）选取迭代终止阈值门并规定最大的迭代步数W.N应选人些，卅谋差le.为第m步的均方谋差）转到步骤2）。当le.达到10次以上或迭代步数达到“时，迭代终止。 旋转平移点云2后使用均方谋基评价点公拼接 Afto4实验与分析实验使用3种方法对Dr. Mian提供的点云进行 拼接.分别为

18、ICP第法.粗配准1CP算法、粗配准 CJCP算法。本文把两点云重心之间的距离记为d. 均方误差记为W迖代步数记为叽使用点止重心之间的距离来评价点云姿态的好坏且大于10的 点云姿态较蓬。4.1 chicken 1 和 chicken 2 的实验chicken 1: 29 518 个点,chicken 2：30 165 个点。 粗配准选取I 000个恃征值展大的点，计算特征距 离见图4然后选取待征阖值为0.08。 1拼接结果Tb. 1 Results of registrationtmriur拼接侑况ICP0. 246 7255粗配橋1CP0.246 7160林效me c-icp0. 242 6

19、52令效笫5期辛佑等：点到邻域jfc心距离特征的点云拼按889笫5期辛佑等：点到邻域jfc心距离特征的点云拼按889图4舒征聊离Eig. 4 Feature distance图6拼接过程Fig. 6 ProrrH of rrgiMration笫5期辛佑等：点到邻域jfc心距离特征的点云拼按889汕斛啪配itt的点公在图4中特征庁号越小该点的待征值越大。 恃征距离为点之间待征值的基值。山图5(c)可看出糊配准后的点云冇了好的姿 态，但一些地方仍未配准好。C-ICP算法选取的特 征阈值为0.03,迭代终止阀值为0.0005。特征周值 不能太小以免得到的配准点对太少3种方法得到 的拼接结果见图5和拦

20、I,详细的拼接过程见图6。图5(.)中的阿点云敢心距离为5.295 8小于 10点冇相对较好的姿态因此CP算法的均方何原点加比P配准后的战云 (int cloudx registration谋差小，点云曲接成功。由衣1和图6可看岀，相配 准CJC玖pre+C-ICP)n法的均方谋差相比ICP算 法提岛得很小，但收敛速度得到了很大提岛。而粗 配准ICP算法(pre +ICP)虽然辆度相比ICP算法没 有提高，但收敛速度有了一定提岛。4.2对差姿态点云的拼接对4.丨廿中的点云chicken 2移动使点云之间 収心距离变大。给点云chicken 2加平移矩阵(20.5. 10.5,10.5)、(50

21、. 10.5,10.5)和(95.10. 5.10. 5 ) 后，两点云鱼心之间的距离分别为27. 071 ,52. 32、 95. 644 .点云姿态絞潍，见图7(a)。1配准阈値仍为0.08和I000.G1CP侑配准 参数仍为0. 03.0.0005各种算法的拼接结果见 图7和表2,可看出在购点云載心之间距离为27.071 和52. 32的差姿态厂粗配准后的轴配准取得/好 的效果说明粗配准在班心距离大的悄况下依然使 点云得到r好的姿态。C-ICP算法辅配准相比fi接 1CP算法侨度有人的提高.与ICP算法辅配准相比 右更快的收徹速度由于币:心距离为95.644的点公错位人人.3种 方法都没

22、能准呦拼接：实际中点云隨心距离超过 50应算错位很大如图7(“中的第2幅图若超过笫5期辛佑等：点到邻域jfc心距离特征的点云拼按889第5期辛伟尊:点到邻域董心距离特征的点云拼接891第5期辛伟尊:点到邻域董心距离特征的点云拼接891Pam 12(0.01J0000)(0.005.0.0005)9.950 2T-rei 12(0.05.10000)(0.04.0.0005)11.993Par- 34(O.O5.5OOO)(0.03.0.000 5)31.019CM 12(0.03.10000)(0.01.0.000 5)10.7534 4个点云的拼接比较Tab. 4 Comparison of

23、 four point clouds registration点zi名称filBg准【CP箱配椎 CJCPerroriurerroriuferroriurPara 120.246 81880.246 71190.255 261T-rex 120.607 01640.2M92310.232 150Para 340.604 43210.244 5SI0.235 424Chef 120.66S52750.228 24640.247 697对不规则曲面的扶接提出采用粗配准和刚性 待征改进的ICP算法精配准进行拼接。为点云重心 之间距离小于10时，本文提出的方法在准确拼接的 情况下使收敛速度得到显蒼提髙

24、。而对于重心距离 大于10的差初始姿态点云，本文采用的重心待征法 克眼了直接使用ICP算法拼接不准确的问題，同时 比粗配准后的ICP算法精配准有更快的收敛速度。 虽然重心特征法对不规则曲面点云的拼接实验取得 了好的效果，但并没有考虑噪声对重心待征法的形 响,未来将对歼法的鲁棒性进行研究。參考文献(References)1 Beal P J. Mckay N D A method for refstrtUon of 3D shapes J IEEE TraiuactUMU on Pattern Analysw and Machine IntelUgeoce. 1992. 14 (2) : 239

25、2562 Cben Y, Medioai C. Object modeling by regiMration of multiple rane image* ( J Imapag and ViiM Compuhoo v 19921 10(3):145-1553 Lin Yonghuai. Conatraints for clotest point fitMiing( J. Pattern Recognition Letton. 2008,29(7)： 841-851.4 Rusinkiewiex Se Lmoy M Efficient varunu of the ICP algorithm (

26、C /Proceeding* of Third InteniUxi&l Cmlerencc on 3D Diptaland Modeling. Wabintoci DC, USA $ IEEEComputer Society Presa, 2001: 145-1S2.S Xie Zcxiao, Xu Shaagv Li Xuyong, A highaccmcy method for fine refistrahon of orcdappiBg point ckmdt j . Image and Vbioa Computing. 2010 . 28(4) : 5635706 Ballc E, M

27、atabotch C. Sdri J. Savunjuia( iaue Mirfaoe regMtraiioa for 6DOF robot/camera pote cstimahon J. Pattern Recognition and Image Aaalytia, 2007 , 4478(2) : 10S-1127 Zhu Yanjun, Zhou Laishui, Zhang Liyan. Registration of catterai cloud kta J Journal of Computer-aided Deaipi & Computer Craphiet, 2006. 18

28、(4)： 475-479.朱基周来 水.乱点云数聲配虑算法J)卄算机辅助设忡与 图形学学报，2006, 18(4)：475-479.)8 Wang Sen, Wan Yang, Jin Miao, et al. Conformal geonetry aad its applicatiom oa 3D shape matching, reeonitioa9 and J Medical Enpueenng & Physics, 2007 t 29(7)： 1209-1220.9 AstMn Kv KarlMon J. Enlist 09 et d. Augabc feature poiat oom

29、poodence and shape analytb withUu and ovllienMDL(J. lnue Atulyab. 2007 . 4522(5) ： 21-3010 Dai Jitijao. Cben Zhiy冲.Ye Xisi The 中plication of ICP algorithm in point cloud alignment J. Journal of Image and Graphics, 2007, 12 (3)： 517-521. (兰陈玄杨叶修梓. ICP算法在点云促?t中的!4用J 中形学报.2OO7. 12(3)： 517-521.11 Yaag S

30、ben9 Sbco Xukut, Qi Yue. aL Ab autooutedregUtratioo method for rangeC /Proeeedinf of the 2ndInteniAlwaAl Conference co Technologies for ELeaniing and Digital Enteruinnent. Heidelberg, Beriio, Gervuiiy： Springer- VerUg. 2007.772-783.12 Chen Xin. Schmitt F Intriiuic turfftce properties from surface trianguUtkmf C / Proceedinp of the Evrvpean Conference on Computer Vision. Heideberg, Briin9 Germaay： Springer. VerU9 1992 ： 739-7413 Taubin G Eadmaiing lh Ibmot of currttaro of a surface from a polyhedral appnn