同一物体不同视角的点云配准方法

陈 卓，宋丽梅，陈昌曼，唐 欢

（天津工业大学电工电能新技术天津市重点实验室，天津 300387）

同一物体不同视角的点云配准方法

陈 卓，宋丽梅，陈昌曼，唐 欢

（天津工业大学电工电能新技术天津市重点实验室，天津 300387）

对两幅不同视角下的点云采用面表法管理，而后对两幅不同视角下的点云采用曲率特征的ICP改进算法进行配准处理.具体处理方法为先根据获得的两幅海量点云数据进行面表法处理，然后根据获得的面表计算每幅点云中的近似曲率，对其中一幅点云的曲率按大小分类，并且每类进行随机采样.根据随机采样的结果按照曲率第一、距离第二的原则在另一幅点云中查找对应点，最后求出第一幅点云的旋转和平移矩阵从而完成配准过程.实验结果表明：在相同海量点云下，面表法的生成时间比八叉树法生成时间平均少406 ms，查找时间平均少53.5 ms；并且曲率特征的ICP算法可以迭代25次收敛到0.241 625 mm的精度，基本满足多视角点云配准的精度高、计算速度快等要求.

物体；视觉；点云配准；ICP算法；点云管理

自21世纪以来，国内有很多学者对点云的配准算法进行了研究.1987年，Horn、Arun等用四元数法提出点集对点集配准方法.这种点集与点集坐标系匹配算法通过实践证明是一个解决复杂配准问题的关键方法.1992年，计算机视觉研究者Besl和Mckay介绍了一种高层次的基于自由形态曲面的配准方法，也称为迭代最近点法（iterative closest point，ICP）.ICP法经过十几年的发展，不断得到完善和补充：Senin等[1]提出够增强增强ICP配准精度的方法；Martínez等[2]提出了与镭射光扫描相结合的ICP配准算法；Lena等[3]分析并改进了ICP算法的匹配错误；Sacharow等[4]提出ICP-NI的改进算法；王蕊等[5]和吴禄慎等[6]提出基于特征的点云配准算法；程效军等[7]研究了点云配准误差传播规律；王程冬[8]等提出一种基于SIFT算法的点云配准.张蕾等[9]和郑德华等[10]针对点云配准方法进行约束改进；王欣等[11]提出了一种改进方法来对点云进行配准；张金魁[12]提出了基于曲率的局部配准算法；周春艳等[13]研究了三维点云ICP改进算法.因此，本文在上述研究成果与已有研究的结果[14-15]的基础上，提出了多视角点云配准的新方法.

1 点云的存储方式

经典的点云的存储方法有八叉树、三维网格等算法.八叉树算法将点云按照树的结构进行排列，但是无法确定点云内部距离最近的两点，而且无法快速确定该点是否是边界点，并且该算法的访问速度比较慢.如果需要找到点云空间中一部分区域内的全部点，可以使用八叉树算法或者三角网格算法.八叉树算法需要遍历整个树，速度较慢；三角网格算法将空间分割为多个盒子，每个盒子内部按序存放点云，该方法消耗的空间与分成盒子的体积大小成反立方关系，也就是体积越小计算机消耗的空间就越大.本文提出了一种改进的三维网格管理点云的算法——面表法，该方法将消耗的空间大小转变为平方关系，同时不会降低生成和访问速度.

面表法是三维网格算法的改进，首先要计算点云的包围盒，计算好包围盒（xmin，ymin，zmin，xmax，ymax，zmax），取x，y，z中任意2个向量作为基准.例如取x，y向量，给定阈值（假设阈值为T）进行x，y平面分割，将平面分成（xmin-xmax）×（ymin-ymax）/（T×T）个方块，然后对整个点云进行遍历，使得每个点找到对应的方块，并且按照链表的方式存储.如图1所示.

图1 面表的生成与点的存储Fig.1 Generation of surface list method and store points

面表生成后有一个较大的缺陷，就是无法获知z方向上的大小，因此每个表格中的点应该对原链表进行再改进.具体改进方法为，每个表格中的点按照阈值对z方向上的大小进行分类.分类方法如图2所示.

图2 z方向分类方法Fig.2 z classification method

如果按照面表法寻找点（x0，y0，z0），应先提取出该点坐标的x和y方向的坐标（x0，y0），而后根据自定义的映射规则找出（x0，y0）所对应的表格.假设自定义的映射规则是所有点的x，y方向应遵循x= [（x0-xmin+0.5×T）/T]，y= [（y0-ymin+0.5×T）/T].生成面表后按照该规则找到对应的（x，y）面表.然后根据z0找到z方向的分类.找到包含z0的一类后，通过遍历该类获知（x0，y0，z0）的位置.遍历空间区域的方法为找出该区域中包含的所有x，y表格：应从x低表向x高表顺序访问，访问到最高位置时，将y表增加1，x置成低表，继续访问，直到y表达到最高位置为止.z表根据给定的区域对z的分类进行限定，超过或低于该范围的z类不进行访问.

2 基于曲率特征的ICP的改进算法

基于曲率特征的ICP算法概述：首先需要获知两幅点云的全部曲率特征，由于曲率的含义是根据均匀平滑的曲面来定义的.因此需要对部分点云进行曲面拟合，然后针对拟合后的曲面进行曲率计算，即可获知该点的估计曲率.本文选用的曲面模型是二次曲面模型，即需要拟合曲面的点云数量不能低于4个点.而本文所提出的面表法存储结构，可以有效地进行曲率计算.由于面表法首先是对全部点云进行x，y平面上的表格分类，然后再对每个x，y表格里进行有序的z分类，因此每一个z方向的表格都代表一个空间体.由于每个空间体内点云数量不同，并且当空间体内点云数量少于4个时，无法对这部分点云进行曲面拟合，因此必须对所有的空间体进行归并和删除，即对于空间体内较少的点去尝试找附近有较多点的空间体进行归并运算，如果找不到附近有较多点的空间体则删除该空间体.归并与删除算法是配准算法的预处理环节.在预处理结束后，选择空间体内曲面拟合模型，如公式（1）所示：

公式（1）没有加入旋转和平移，因此这个模型必须将点云旋转平移到原点附近，否则无法拟合.由此可见，对于空间体内的点云不能使用公式（1）进行拟合.空间体内的点云进行平面拟合如公式（2）所示：

设空间体Q={q1，q2，…，qn}（n>3），q1点的x坐标表示为xq1，则拟合公式（2）可以表示为公式（3）：

通过解上式可知A、B的数值，从而获得平面向量（A，B，-1），这个平面向量单位化后需要转到（0，0，1）.根据二次曲面模型在原点附近求出的曲率，可以找到空间体中一点作为估计参考点，将空间体Q中所有点带入平面方程，获得每个点的状态（大于0，或者小于0，或者等于0）.将大于0的所有点设为点集Qu，将小于0的所有点设为点集Qd.对Qu、Qd求取方差Δu、Δd，期望Eu、Ed.在Δu、Δd中选择范数小的方差Δx对应的期望Ex和点集Qx，由于期望Ex是一个空间点，因此只需要从这个空间点引出一条向量为（A，B，-1）的直线l，并从点集Qx中找一点t求取其到直线l的距离.计算通过t点的平面方程式（4）：

将t点坐标代入（x，y，z）中求D.现已知经过期望点的直线方程如式（5）所示：

将平面方程与直线方程联立可以求解出期望点在平面中的投影点s.接下来就可以计算出点t与投影点s的欧式距离d，实质上d就是点t到l的距离.在Qx中找一点tm使得其d的数值小于等于其他点的d的数值.将Q中全部点坐标减去tm坐标获得空间体Q′.对Q′进行旋转变换，进行旋转变换时可使用基于四元数的旋转矩阵.四元数q内每个元素的定义如公式（6）所示：

式中：（nx，ny，nz）是旋转轴的单位向量，是围绕该旋转轴的正向角度.因此只需求出旋转轴和所需的角度即可.现已知向量（A，B，-1）单位化后的向量T为（a，b，c），转到的位置为R（0，0，1）.因此仅需算出U=T×R就可以计算出旋转轴的向量.

即旋转轴的向量U为（b，-a，0），θ=arcos（c）（0≤θ≤π）.代入上面的四元数中，通过四元数求旋转矩阵后将空间体Q′转到Q″.对空间体Q″进行二次曲面拟合，其拟合过程如式（7）所示：

将二次曲面拟合后对这部分点求高斯曲率如式（8）所示.

通过上式计算出点云A的每个点的高斯曲率后，将点云A分成n类，每类含有点的数量近似相等，并且下一类中的任何一个点的曲率都要大于上一类任何一点的曲率.接下来对每一类曲率进行随机采样其采样结果为点云C.

点到点的查找方式：从点云C中抽取一点g.在点云B中按面表法的查找规则进行查找，选出与g点具有相近曲率的几个点.最后在这几个点中找到离g点最近一点h从而完成配对过程.点到面的查找方式为：在找到h点的基础上，在点云B中找2个点m和n，使这两点离h点的距离最近.然后令h、m、n三点共面，求g点到平面投影点k，从而完成新的配对.由于在最近距离这一条件上加入了曲率限制，使得算法在稳定性、适用性、迭代速度等方面都有不同层次的上升.

3 数值实验结果

面表法生成与查找时间如表1所示.

表1 面表法的查找与生成时间对比Tab.1 Search and generation time contrast of surface list method ms

根据表1中测试的结果可以发现面表法相对于八叉树法的快速性.由于八叉树法是针对整部点云进行查找的算法，因此该算法需对整部点云进行查找；而面表法可以通过包围盒间的关系进行查找，从而大大减少点云的查找速度.表2、表3给出的是经典ICP算法与本文算法对比的迭代值表格.

表2 初值精度较好的2种方法迭代结果Tab.2 Iteration results of better initial precision of two methods

表3 初值精度较差的2种方法的迭代结果Tab.3 Iteration results of worse initial precision of two methods

图3所示为在ICP算法未匹配前对两幅点云进行了标记点粗匹配，因此该算法能够很快收敛到两幅点云匹配精度较高的位置.

图3 单纯ICP匹配结果Fig.3 ICP matching result

图4所示为未经过标记点粗匹配而将3D扫描仪的扫描结果直接使用本文算法进行匹配.

图4 基于曲率ICP算法匹配结果Fig.4 Matching results of ICP algorithm based on curvature

由于基于曲率特征的匹配，所以两幅点云依旧能够收敛到正确位置.其中表2的迭代对比是在初值误差为0.561的拼接的结果.在这种情况下经典ICP算法使用了10次迭代，而本文算法仅仅使用了7次迭代.在表3对应的图4的迭代结果中可以发现，在出现较差初值时，ICP使用了122次迭代，而迭代后的精度只有0.670 429.这个精度没有任何实际意义，因为在图3中的未配准前的精度仅仅是0.561 57，并且在图3（a）中可以看出两幅点云有较大差距.而使用本文算法后通过24步迭代就可以获得0.241 625 93的精度.表中无论ICP与本文算法都写有“搜索域变化”，这也是面表法所特有的.当两部点云旋转到适当精度时可以调整比较合适的搜索域来加速整个算法的收敛速度.

4 结论

本文根据多视角点云的配准要求提出了面表法与基于曲率特征的ICP算法，并详细介绍了如何构造面表来对点云进行快速访问.根据表1中记录的结果可知，面表法的生成速度比八叉树方法的生成速度平均快406 ms，而查找速度平均少53.5 ms.通过实验表明，本文所提出的改进的ICP算法要比经典的ICP算法迭代次数平均少8.5次.在初值不好的情况下，改进的ICP算法收敛精度可以超过经典ICP算法.

[1]SENIN N，COLOSIMO B M，PACELLA M.Point set augmentation through fitting for enhanced ICP registration of point clouds in multisensor coordinate metrology[J].Robotics and Computer-Integrated Manufacturing，2013（29）：39-52.

[2]MARTÍNEZ Jorge L，REINA Antonio J，MANDOW Anthony，et al.3D registration of laser range scenes by coincidence of coarse binary cubes[J].Springer-Verlag，2012（23）：857-867.

[3]LENA Maier-Hein，FRANZ Alfred M，DOS SANTOS Hiago R，et al.Convergent iterative closest-point algorithm to accomodate anisotropic and inhomogenous localization error[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（8）：1520-1531.

[4]SACHAROW A，BALZER J，BIERMANN D，et al.Non-rigid isometric ICP：A practical registration method for the analysis and compensation of form errors in production engineering[J]. Computer-Aided Design，2011（43）：1758-1768.

[5] 王蕊，李俊山，刘玲霞，等.基于几何特征的点云配准算法[J].华东理工大学学报：自然科学版，2009（5）：768-773.

[6]吴禄慎，孔维敬.基于特征点的改进ICP三维点云配准技术[J].南昌大学学报：工科版，2008（3）：294-297.

[7] 程效军，施贵刚，王峰，等.点云配准误差传播规律的研究[J].同济大学学报：自然科学版，2009（12）：1668-1672.

[8] 王程冬，程筱胜，崔海华，等.SIFT算法在点云配准中的应用[J].传感器与微系统，2012（2）：149-152.

[9] 张蕾，冀治航，普杰信，等.约束改进的ICP点云配准方法[J].计算机工程与应用，2012（18）：197-200.

[10]郑德华，岳东杰，岳建平.基于几何特征约束的建筑物点云配准算法[J].测绘学报，2008（4）：464-468.

[11]王欣，张明明，于晓，等.应用改进迭代最近点方法的点云数据配准[J].光学精密工程，2012（9）：2068-2077.

[12]张金魁.基于曲面的局部配准算法[J].科技资讯，2011（9）：68-69.

[13]周春艳，李勇，邹峥嵘.三维点云ICP算法改进研究[J].计算机技术与发展，2011（8）：75-77.

[14]SONG Limei，DONG Xiaoxiao，XI Jiangtao，et al.A new phase unwrapping algorithm based on three wavelength phase shift profilometry method[J].Optics&Laser Technology，2013，45：319-329.

[15]SONG Limei，CHEN Changman，CHEN Zhuo，et al.Essential parameters calibration for the 3D scanner using only single camera and projector[J].Optoelectronics Letters，2013，9（2）：143-147.

Points registration of same objects with different view

CHEN Zhuo，SONG Li-mei，CHEN Chang-man，TANG Huan
（Key Laboratory of Advanced Electrical Engineering and Energy Technology，Tianjin Polytechnic University，Tianjin 30087，China）

Two point clouds in two different perspectives is managed by the method of surface and then the ICP algorithm is adopted based on curvature characteristic to improve the registration process.The surface method for processing the acquired point clouds from two different perspectives is used firstly.Then the curvature of two point clouds based on the surface method is calculated,and classify one of two point clouds by the curvature size and sample randomly from different classes.According to the result of random sample,to find the corresponding points which is in another point cloud in accordance with the principle of the curvature first,distance second.At last,calculate rotation matrix and translation matrix of the first point cloud to complete the registration process.Experimental results show that under the condition of the same mass point cloud,surface table generation time is less than the octree generation time on average 406 ms while the finding time is less than average 107 ms.What′s more,the ICP algorithm for curvature features based on curvature features achieves the precision of 0.241 625 mm.It can be basically satisfied the requirements of the multi-view point cloud of high registration precision,fast computing speed,etc.

object；view；points′registration；ICP algorithm；points′management

TP391.7

A

1671-024X（2014）01-0045-05

2013-08-12

国家自然科学基金（60808020，61078041）；天津市应用基础及前沿技术研究计划（10JCYBJC07200）

陈 卓（1988—），男，硕士研究生.

宋丽梅（1976—），女，博士，教授，硕士生导师.E-mail：liymay1976@126.com