基于局部坐标系法线投射的点云精细配准算法

蔡先杰

（四川大学计算机学院，成都　610065）

基于局部坐标系法线投射的点云精细配准算法

蔡先杰

（四川大学计算机学院，成都610065）

点云配准是逆向工程中用于拼接点云模型的方法，可分为初始配准和精细配准两个步骤。假设在已经实现初始配准的情况下，提出基于局部坐标系法线投射的点云精细配准算法。通过对点云采样得到的采样点建立局部坐标系，然后将采样点的相邻点集投影到该坐标系下，就可以得到代表模型的每个局部曲面的控制点集，再用法线投射算法求解出关联点对集并计算两个点云之间的变换参数（旋转角度和位移量）。局部坐标系法线投射算法获取到的关联点对有效性高，能明显减少迭代次数，提高配准效率。

点云配准；精细配准；局部坐标系；法线投射；关联点对

0　引言

点云是指通过三维扫描仪扫描物体得到的、用三维点集表示物体表面轮廓的模型。点云技术是逆向工程的一个重要环节，广泛应用于医学、工业制造与工程［1-2］、数字娱乐、文物保护等领域。

由于扫描仪的扫描范围限制，单一扫描仪无法通过一次扫描就得到物体的完整点云模型。要将不同角度扫描得到的多组点云拼成完整的模型，需要用到点云配准技术。点云配准，是指将具有重叠区域的两个点云模型，通过重叠区域的欧几里德不变量和几何特征［3-4］等建立两个点云的联系，将它们映射到同一坐标系下，使之拼接成为一个模型的过程。

点云配准又可分为初始配准和精细配准两个步骤。初始配准主要是将两个点云移动到相近的位置，配准结果比较粗糙。精细配准建立在做了初始配准之后，两个点云的重叠区域比较接近的基础上，进一步对点云进行配准，使重叠区域达到近似重合的效果。

本文假设初始配准的步骤已经实现，主要对精细配准进行探讨。

1　相关工作

ICP［5-6］是精细配准最著名的算法，大部分点云配准算法，如T.Pajdla［7］等提出的ICRP（查找欧氏距离最近的两点作为关联点对，再通过二次反向查找最近点的方法筛选点对），都是基于此算法。ICP算法的思想是：

①建立两个点云之间的联系，选取关联点对集合；

②以其中一个点云（目标点云）为基准，通过关联点对集合计算出的变换参数，将另一个点云（源点云）移向该点云；

③重复以上步骤，直到两个点云间的距离小于某一阈值。

ICP算法的实现一般分为4步：点集采样、点对关联、去噪、计算变换并移动点云。其中，点对关联和去噪是ICP算法的关键步骤。

点对关联一般是在两个点云距离较近的情况下，进行点到点的最近距离关联、点到切平面交点的关联和点到面的投影关联［8-9］。Rusinkiewicz等［8］指出当初始配准的误差较小时，点到面投影的关联方式优于点到点最近距离的关联方式。

去噪主要是利用刚体运动的不变属性去除噪声点对，可分为曲面几何特征约束和点的距离约束。

曲面几何特征约束是利用物体同一位置的表面几何特征（法矢、曲率、重心等）在任意视角保持不变的原理，比较关联点对的特征值之差，筛选出差值大于指定阈值的点对。Turk等［10］对构建了三角面片的点云模型进行ICP配准，关联点对时加上距离和非边界附近点的限制，使ICP算法适用于三维扫描点云的配准。Godin等［11-12］等计算点云的曲率、密度向量集，选取关联点对。Sharp等［13］提出ICPIF（Iterative Closest Points using Invariant Features），利用点对距离、曲率、球谐函数等确定关联点对，在计算点对的距离信息时，使用欧氏距离和特征向量距离的加权方程。Devrim等［14］用空间点集间的角度和距离参数确立关联点对。Bae等［15］提出GP-ICPR（Geometric Primitive ICP with the RANSAC）算法，利用曲率的变化量与对应点的法矢的夹角来确定点对，然后用变种的RANSAC算法去除噪声点。王蕊［16］等用曲率及邻近点的曲率特征，建立10维向量，进行点云配准。Jiang等［17］等提出基于法线夹角的点对关联方法，在目标点云中选取关联点的k个邻近点，对法线夹角组成的向量求差，根据邻近点的法线方向去除点云的噪声点。Flöry［18］等对原ICP算法进行修改，用l1-norm（曼哈顿距离）代替l2-norm（欧氏距离），计算关联点对距离最小的变换矩阵。Xie等［19］将点云投影到垂直于投影轴的平面，建立均匀网格，随机选取控制点矩阵，建立双三次B样条进行法线到面的求交获取关联点对集。这类算法适合扫描点云和模型点云，对点云的重合度要求也不是很高，但要求点足够多且足够密集，且有较好的采样和去噪声算法。

点的距离约束是利用刚体运动保证物体重叠区域关联点之间的距离和关联点与其相邻点的距离关系不变的原理，筛选掉距离不在指定阈值内的点对。Dorai等［20］利用两组关联点对的邻近点距离差小于指定阈值来去除噪声点对。Zhou和Liu等［21-22］运用矢量运算和三角不等式分析了ICP算法最邻近点的传统标准，提出去除噪声点对的方向约束（Orientation Constraint）、刚性约束（Rigidity Constraint）和匹配误差约束（Matching Error Constraint），证明了传统标准可以满足这三个约束，关联出的点具有较高的匹配质量。

然而，对于重叠区域表面凹凸程度较大的点云模型，重叠区域有歧义点或者重叠区域与投影面夹角较大的点云模型，上述算法的处理效果并不是很好。

本文提出了基于局部坐标系法线投射的点云精细配准算法，能高效地处理复杂模型。

2　算法描述

2.1ICP

Besl等提出的ICP算法是三维点云配准的经典算法，其目的主是计算出公式（1）中的R和T，使∑（R，T）最小，式中n表示点云P和点云Q的关联点对数，pi、qi分别表示P和Q上的第i个关联点，R为旋转矩阵，T为平移向量。

ICP算法基本思想是，通过反复查找Pk（k为迭代的次数）和Q的关联点对集，计算旋转矩阵R和平移向量T，更新P的坐标，使P逼近Q，直至P和Q的距离达到阈值（满足公式（1）中的∑（R，T）＜σ），迭代结束时返回R和T。ICP查找关联点对的方式是直接计算在Q中距离最近的点qi，若满足则认为是关联点对。找到Pk和Q中的所有点对后，再通过最小二乘思想拟合出最佳变换关系。

2.2法线投射双向插补算法

Xie等［19］用法线投射方法求点云的关联点对，并用双向插补的距离约束及曲率约束对关联点对进行去除噪声对的处理。如图1所示，Xie等［19］主要对ICP算法进行了采样、关联和去除噪声点对的修改：采样时，按垂直于扫描仪的方向建立N×N的网格，将点云P和点云Q中的点分别投影到网格中，然后在每个网格中随机保留一个点作为采样点；关联时，使用采样点作为控制点建立双三次B样条曲面，然后用点云P中每个曲面的中心插值点pi沿法线方向与点云Q对应曲面求交，得到关联点对（pi，qi）；去除噪声点对时，在qi附近求插值点qi'，再与P的对应曲面块求交点pi'，再求pi与qi的主曲率（k1（pi），k2（pi），k1（qi），k2（qi））。当满足公式（2）和（3）的条件时，认为（pi，qi）是有效的关联点对。Xie等［19］的算法在处理扫描结果较好，且初始配准后网格采样可行的模型时，具有较好的配准效果。

图1　法线投射双向插补算法求关联点对

2.3基于局部坐标系法线投射的点云配准算法（LCSNS）

我们获取的三维点云可能并不包含扫描仪扫描角度参数。对于这种情况，法线投射双向插补算法并不适用。于是，针对无法获知扫描角度的点云模型，本文提出了基于局部坐标系法线投射的点云配准算法（LCSNS，Local Coordinate System Normal Shooting），该算法对某一点云（本文选取的是点云Q）进行随机采样或者均匀采样，得到多个采样点，再以这些采样点的相邻点集为局部点集，建立局部坐标系，然后分别将各点在Q和P上的相邻点集投影到该坐标系下，或者通过已知控制点矩阵，查找另一点云中最近点为控制点，就可以得到多个局部曲面控制点集，再用法线投射算法求解出关联点对集。由关联点对集，计算点云P变换到点云Q的旋转矩阵R和平移向量T，使点云P逐渐移近点云Q，直至两个点云达到重叠区域基本重合的效果或达到迭代结束条件。

（1）采样

LCSNS用局部坐标系进行点对关联，除了要求采样得到的、同一点云模型上的样本点之间距离足够大外没有其他要求。采样方法不限，为了方便，本文选用随机采样方式。

（2）点对关联

①建立局部坐标系

随机采样后，对于Q上每个采样点qi，以qi为中心，选取邻近的N个点为一个集合，组成分散点云块。如果输入的点云带有法线信息，则选取最接近点云块重心的点，作为局部坐标系的原点，以该点的法线作为局部坐标系z轴，建立局部坐标系。如果输入的点云不带有法线信息（本文假设法线信息缺失），取点云块重心点为局部坐标系原点，用PCA算法分析得出局部坐标系的xyz轴。假设局部坐标系的方向向量为X=（x0，y0，z0），Y=（x1，y1，z1），Z=（x2，y2，z2），原点坐标为（x'，y'，z'），可以根据局部坐标系方向向量和原点坐标，建立局部坐标系到整个点云模型所处的世界坐标系的转换矩阵MT，如公式（4）所示。

②构建网格并获取控制点矩阵

对于每一个点云块，通过在其局部坐标系的XOY平面构建网格，再将点云块投影到网格内随机采样，得到用于拟合局部曲面的控制点矩阵。考虑到点云块形状多变，可能导致一些网格中不包含投影点，本文采用扩展划分，收缩采样的方式进行网格构建和控制点采样。将网格划分为（NG+EG）×（NG+EG）的区域，其中NG表示控制点矩阵大小，EG表示扩展网格大小。由于点云P的坐标是迭代变化的，所以每次选取关联点对前需要更新P的局部控制点矩阵。每次迭代更新P的坐标后，对于点云Q的控制点矩阵中的每一个点，通过在P上查找最近点，来得到P的局部曲面控制点矩阵。

③关联点对选取

对于点云Q的每一个采样点qi，按照转换矩阵MT，将其在局部坐标系下的法线转换到世界坐标系中，计算其法线所在的直线与点云P上对应点云块所在的局部曲面（由局部曲面控制点矩阵计算得出）的交点pi，将（pi，qi）作为候选关联点对。

（3）去除噪声点对

同法线投射双向插补算法，去掉候选关联点对集中不满足公式（2）和公式（3）的点对，得到有效关联点对集。

（4）计算变换并移动点云

由有效关联点对集计算出点云P到点云Q的旋转矩阵R和平移向量T，将点云P转换到点云Q的坐标系下。

（5）迭代结束条件

精细配准是通过迭代精细调整点云位置的过程，迭代结束的判断方式是点云配准的复杂度、效率和效果的综合考量。本文采用以下几种通用的迭代结束判断方式：

①迭代次数，当迭代达到指定次数后，结束点云配准。本文发现，一般初始配准结束后，精细配准只需20次以内的迭代就可以达到较好的匹配效果。

②变换矩阵增量，计算当前点云配准的（R，T），若T近似于单位阵，T近似于零向量，则结束点云配准。

③点云距离，计算最新位置的P'与Q点对间距离之差。当P'和Q的距离达到阈值后，结束点云配准。

④点云距离变化，前后两次P'与Q点对间距离之差。当两次距离差小于阈值，结束点云配准。

3　实验结果

在这一节，我们会讨论我们的算法（LCSNS）与上文所述的两种算法（经典算法ICP，以更精确的ICRP为代表，以及Xie等［19］的法线投射（Normal Shooting）双向插补算法，简称NS）的适用情况。我们所用的点云模型均是扫描仪从0°开始，以24°为增量对同一三维模型进行扫描得到的结果。

3.1佛像模型

以如图2所示的佛像模型为例，各个算法的实验结果如图3、表1和表2所示。

图2　佛像模型

?色代表从一个角度扫描得到的点云模型）

图3　佛像模型三种算法配准效果示意图

表1　不同算法在处理佛像模型时达到收敛条件所用时间对比（单位：ms）

表2　不同算法在处理佛像模型时达到收敛条件所需的迭代次数对比（单位：次）

3.2龙模型

以如图4所示的龙模型为例，各个算法的实验结果如图5、表3和表4所示。

图4　龙模型

图5　龙模型三种算法配准效果示意图

通过对比可以看出，LCSNS中，因为目标点云（点云Q）的控制点矩阵一经确定后就不再改变，每次迭代过程使用目标点云的控制点矩阵求得新计算出的源点云（点云P）的控制点矩阵，而不是重新通过投影整个点云P到网格平面并随机采样的方式来确定点云P上的控制点矩阵，所以效率会优于NS算法。

同时，由于结合了法线投射和最近点查找的方式，所以在达到收敛时所需迭代次数会明显少于ICRP算法。

表3　不同算法在处理龙模型时达到收敛条件所用时间对比（单位：ms）

4　结语

本文提出了基于局部坐标系法线投射的点云精细配准算法（LCSNS），该算法对点云模型的局部点集建立投影坐标系，再将坐标系附近的点集投影到该坐标系下，得到双三次B样条曲面控制点矩阵。相对于ICRP和法线投射双向插补算法，局部坐标系法线投射算法能获取更好的匹配点对集，从而减少迭代次数，提高配准效率。

下一步我们将继续改进和完善算法，例如研究更好的点云去噪方式等，以提高算法的适用性和效率。

表4　不同算法在处理龙模型时达到收敛条件所需的迭代次数对比（单位：次）

［1］Larsson S，Kjellander J A P.Motion Control and Data Capturing for Laser Scanning with an Industrial Robot［J］.Robotics and Autonomous Systems，2006，54（6）：453-460.

［2］Dorn M，Browne M，Ghidary S S.Landmark Detection by a Rotary Laser Scanner for Autonomous Robot Navigation in Sewer Pipes［C］. The Second International Conference on Mechatronics and Information Technology.Jecheon（Korea），2003：600-604.

［3］J.V.Wyngaerd，L.V.Gool，Automatic Crude Patch Registration：Toward Automatic 3D Model Building，Computer Vision and Image Understanding 87（1-3）（2002）8-26.

［4］L.Li，N.Schemenauer，X.Peng，Y.Zeng，P.Gu，A Reverse Engineering System for Rapid Manufacturing of Complex Objects，Robotics and Computer-Integrated Manufacturing，18（1）（2002）：53-67.

［5］Besl P J，McKay N D.Method for Registration of 3D Shapes［C］.Robotics-DL Tentative.International Society for Optics and Photonics，1992：586-606.

［6］Chen Y，Medioni G.Object Modeling by Registration of Multiple Range Images［C］.Robotics and Automation，1991.Proceedings.，1991 IEEE International Conference on.IEEE，1991：2724-2729.

［7］T.Pajdla，L.V.Gool，Matching of 3D Curves Using Semi-Differential invariants，in：Fifth International Conference on Computer Vision，Cambridge，MA，USA，1995，pp.390-395.

［8］Rusinkiewicz S，Levoy M.Efficient Variants of the ICP Algorithm［C］.3D Digital Imaging and Modeling，2001.Proceedings.Third International Conference on.IEEE，2001：145-152.

［9］Park S Y，Subbarao M.A Fast Point-to-Tangent Plane Technique for Multi-View Registration［C］.3D Digital Imaging and Modeling，2003.3DIM 2003.Proceedings.Fourth International Conference on.IEEE，2003：276-283.

［10］Turk G，Levoy M.Zippered Polygon Meshes from Range Images［C］.Proceedings of the 21st Annual Conference on Computer Graphics and interactive techniques.ACM，1994：311-318.

［11］Godin G，Boulanger P.Range Image Registration Through Viewpoint Invariant Computation of Curvature［J］，1995.

［12］Godin G，Laurendeau D，Bergevin R.A Method for the Registration of Attributed Range Images［J］，2001.

［13］Sharp G C，Lee S W，Wehe D K.ICP Registration Using Invariant Features［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，2002，24（1）：90-102.

［14］Devrim A.Full Automatic Registration of Laser Scanner Point Clouds［J］.ETH Zurich，2003.

［15］Bae K H，Lichti D D.A Method for Automated Registration of Unorganised Point Clouds［J］.ISPRS Journal of Photogrammetry and Remote Sensing，2008，63（1）：36-54.

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

［17］Jiang J，Cheng J，Chen X.Registration for 3D point Cloud Using Angular-Invariant Feature［J］.Neurocomputing，2009，72（16）：3839-3844.

［18］Flöry S，Hofer M.Surface Fitting and Registration of Point Clouds Using Approximations of the Unsigned Distance Function［J］. Computer Aided Geometric Design，2010，27（1）：60-77.

［19］Xie Z，Xu S，Li X.A High-Accuracy Method for Fine Registration of Overlapping Point Clouds［J］.Image and Vision Computing，2010，28（4）：563-570.

［20］Dorai C，Wang G，Jain A K，et al.Registration and Integration of Multiple Object Views for 3D Model Construction［J］.Pattern Analysis and Machine Intelligence，IEEE Transactions on，1998，20（1）：83-89.

［21］Zhou H，Liu Y.Accurate Integration of Multi-View Range Images Using K-means Clustering［J］.Pattern Recognition，2008，41（1）：152-175.

［22］Liu Y.Constraints for Closest Point Finding［J］.Pattern Recognition Letters，2008，29（7）：841-851.

A Fine Registration Algorithm of Point Clouds Based on Local Coordinate System Normal Shooting

CAI Xian-jie
（College of Computer Science，Sichuan University，Chengdu 610065）

Registration of point clouds is a method for jointing point cloud models.It can be divided into two stages，the rough registration and the fine registration.Realizes assuming that the former，proposes a fine registration algorithm，which is based on local coordinate system normal shooting（LCSNS），builds local coordinate systems for each point we sample in advance from our point clouds，and adjacent points of each sampled point are projected to the corresponding local coordinate system，then we can get control points sets for building local surfaces，which represent the whole point cloud.After that，corresponding points set of two point clouds can be figured out by using the normal shooting algorithm，and we can finally calculate transformation parameters（about rotation and translation）between two point clouds. By LCSNS，we get more valid corresponding points，which contribute greatly in reducing iterative times and in increasing registration efficiency.

Registration of Point Clouds；Fine Registration；Local Coordinate System；Normal Shooting；Corresponding Points

1007-1423（2016）26-0057-06DOI：10.3969/j.issn.1007-1423.2016.26.014

蔡先杰（1991-），男，广东澄海人，研究生，研究方向为计算机图形学

2016-06-28修改日期：2016-08-30