点云数据的配准算法研究

李红彦，王韩波

(建设综合勘察研究设计院有限公司，北京 100007)

随着三维激光扫描技术的发展，利用三维激光扫描仪采集信息，构建三维模型成为了热门的课题。三维激光扫描技术采用高速激光扫描，能够快速、精确地获取物体表面的信息，主要用于重构物体三维模型。由于受到观测环境和观测方向等影响[1]，无法一次性地获得物体的所有的点云数据，因此不同视角下点云数据的配准成为了三维建模中的关键技术，直接影响了最终的重合结果以及模型精度。配准算法作为三维扫描技术的核心，已然成为了当今国内外研究的热点之一。本文利用主方向贴合法和最近点迭代算法(ICP算法)作为点云数据的配准算法，对点云数据进行配准，验证编码的正确性。最后，对实际案例运用该算法进行点云数据配准，得出配准结果和配准精度。

1 配准算法的发展以及研究现状

最初配准算法指的是平面图像的配准，而平面图像的配准也只是实现曲线的配准。随着研究的深入，配准算法实现功能也越发强大。配准算法运用于三维空间，从二维空间中的算法理论照搬到三维空间进行计算，然而，两个空间的事物必然存在一定的差距，算法无法适用于其中[2]。为解决这一问题国内外专家学者提出了诸多配准方法，如：迭代配准算法、基于曲面的配准算法、基于几何特征的配准算法和主方向贴合法。迭代配准算法，最具代表性的是最近点迭代(ICP)算法，1992 年由Besl和Mckay提出[3]。该算法以四元数算法为基础，利用搜索算法寻找两组对应点云的最近点，采用欧式距离作为目标函数，通过不断地迭代逼近目标函数的最小值，求得变换矩阵。文献[4]在ICP算法的基础上做出了改进，提出了一种基于迭代最近直线(ICL)和迭代最近三角片面(ICT)的算法。该算法对两个配准点集中的点进行连接或者三角化操作，然后找出几何特征相似线段或者三角片，然后用四元数法对目标函数求解，求得旋转矩阵。周儒荣等[5]提出了一种基于几何特征点云配准算法，使对应关系不明确的点云数据可以快速、有效地配准。王育坚等[6]提出了主方向贴合法，能够快速缩小点云的旋转和平移错差，且对点云的大小没有特殊要求。

2 配准算法在三维建模中作用

通常情况下重构物体的三维模型时，需要对物体进行全方位扫描。由于受到观测环境、观测方向和物体自身形状的影响，无法一次性地获得物体的所有点云数据。因此，点云数据的配准成为了三维建模中的关键技术，直接影响了最终的重合结果以及模型精度。建立物体的三维模型如图1所示。

图1 三维建模流程

图中点云去噪是采用滤波平滑的方法去掉离散点与噪声点，点云粗配准中采用主方向贴合法，用matlab语言实现该算法，然后对点云数据进行配准，以验证编码的正确性。选取ICP算法作为精配准算法，在matlab上进行实现，再对已经粗配准的点云数据进行配准，验证编码的正确性。

3 基于主方向贴合法点云数据的粗配准

为了减小点云间旋转、平移的错位，使得精确配准拥有良好的初始位置，不至于在配准过程中不断趋向错误的方向。本文研究的方法为主方向贴合法，其具有简单、快捷、易于实现的特点。

3.1 主方向贴合法

3.1.1 主方向贴合法介绍

每个点云在空间上都存在一个主方向，该主方向可以用所计算的点云中所有点的特征向量求得，还能得到和主方向垂直的两个次方向。对于重叠率较大的数据，配准的问题就转换为坐标变换的问题，只需要把两个坐标系变换一致[6]。

主方向有正反两个方向，有可能会出现配准后点云相差180°的情况，所以在配准前还应该设置一个值，使向量指向同一侧。本文是通过计算两个点云对应的参考坐标系的坐标轴相点乘，如果它们的值小于所设定的值，那么认为坐标轴的方向指向不同侧，需要调整其中一个坐标轴的方向180°[7]。待方向确定后，根据坐标系的坐标轴的方向向量，求得旋转矩阵，然后再求出平移矩阵，作为粗配准的结果。

为了达到良好的配准效果，本文采用了人机结合的方式，在算法实现前，先粗略地提取两个点云可以重叠的部分，这种方法适用于点云数据重叠区域小的情况，可以减少噪音的影响。

3.1.2 主方向贴合法算法流程

(1)首先读取参考点云与目标点云；

(2)分别粗略地提取两个点云中可以重叠的部分；

(3)计算点云的重心；

(4)对点云进行中心化处理；

(5)分别求算点云的特征值与特征向量，特征向量依次作为x、y、z轴，建立坐标系；

(6)设置一个阈值，确定坐标轴方向指向同一侧；

(7)计算点云之间的旋转矩阵、平移矩阵，结束[8]。

3.2 算法的实现

根据上述流程，利用matlab编写主方向贴合法实现代码，所用的数据为美国斯坦福大学的深度图像数据库中标准参考数据，数据点为400 097 个，数据读取格式为asc格式。

算法运行后，得出的旋转矩阵R为：

(1)

平移矩阵T为：

(2)

点云数据配准前，显示图像如图2所示，利用主方向贴合法配准之后如图3所示。

图2 点云粗配准前三维显示效果图

图3 点云粗配准后三维显示效果图

由图可见，两个点云数据的重叠区域较大，可以直接对整个数据进行特征值和特征向量的提取，配准之后，点云的重叠效果良好，满足精确配准的要求。主方向贴合法的优点在于算法思想简单，便于编程实现，而且对于大量的数据，该算法可以很快地计算出结果该算法仅用了0.095 986 s，但它的缺点也显而易见，只适用于那些点云数据重叠率较大的情况，如果重叠区域太小，噪音对点云主方向的影响较大，配准后的效果不佳，仅仅是适当地缩小了点云之间错位误差，但仍然达不到精配准的要求。

4 基于ICP算法的点云数据的精配准

ICP算法自提出以来，通过不同学者的研究，已经日益趋于成熟。其以迭代的方式逼近最佳的成果，在理想的时间下得出人们满意的结果。由于它的算法特性，也决定了它对数据集的初始位置需要一个较高的要求，不然则会出现配准错误。这就需要粗配准为ICP算法提供一个良好的初始位置，而主方向贴合法的配准结果也很好地满足了这一要求[9]。

4.1 ICP算法

4.1.1 ICP算法介绍

Besl等在1992 年提出了最近点迭代算法(ICP算法)这种算法不需要精确的控制点，它只是对每次迭代中的目标函数中的最近点控制点，用于估算变换矩阵的参数。迭代计算过程中，以两次迭代目标函数的值得变化小于某一个阈值为结束。

对于数据集X，其中每一个数据点在点云数据Y中都可以计算找到对应的点，将这些点组合起来形成对应点集Yk，这需要运用到最近点算法，将这种操作记为：

Yk=C(X,Y)

(3)

对于对应点集X、Yk，运用四元数算法估算配准参数，操作记为：

(H,d)=sysf(X,Yk)

(4)

对于点云数据X的每一个数据点，通过变换矩阵H的旋转平移变换，操作记为：

H(X)=R(X)+T

(5)

上述操作构成了ICP算法的基本操作，ICP算法的基础为寻找最近点，其思路为迭代逼近最佳值，核心为四元数算法计算配准参数。

4.1.2 ICP算法流程

(1)寻找最近点：由公式Yk=C(X,Y)对点云数X中的每个数据点，计算其在点云数据Y中的最近点，构成点集Yk；

(3)更新数据集：由公式H(X)=R(X)+T，利用变换矩阵H对数据集X进行更新；

(4)迭代计算：对更新后的数据集重复1、2操作，得到新的配准参数H′和估计误差。如果连续两次计算得到的估计误差的变化小于某一阈值时，即为‖d-d′‖≻≤τ，则停止迭代，输出结果。

4.2 算法的实现

根据上述流程，利用matlab编写ICP算法，部分代码如下：

function Yk=C(X0,Y) %X0为目标数据经过变换矩阵变换后的数据集

Y0= delaunayn(Y'); %Y0为对参考数据Y进行三角剖分

k = dsearchn(Y',Y0,X0'); %利用matlab中自带的寻找最近点的函数，

Yk = Y(:,k); %Yk为Y中对应X中数据点的最近点

Rqr=[q0^2+q1^2-q2^2-q3^2 2*(q1*q2-q0*q3) 2*(q1*q3+q0*q2);2*(q1*q2+q0*q3) q0^2-q1^2+q2^2-q3^2 2*(q2*q3-q0*q1);2*(q1*q3-q0*q2) 2*(q2*q3+q0*q1) q0^2-q1^2-q2^2+q3^2]; %特征向量构成的旋转矩阵

……

在粗配准的基础上进行，算法运行后，得出的旋转矩阵R为：

(6)

平移矩阵T为：

(7)

通过上述算法，设置的阈值为0.000 000 5，经过了11次迭代，配准结果如图4所示。

图4 点云数据精配准后三维显示效果图

ICP算法思想在于迭代，控制阈值的大小，决定了结果的精度、迭代次数以及运算时间。可见，它们之间的关系式相互矛盾的，要想得到较高的精度，将阈值设置得尽量地小，但迭代次数随之增加，运算时间也变长；同样的，为了节省时间，缩小迭代次数，却会牺牲结果的精度。这就需要根据要求确定合适的阈值，使得精度、运算时间和迭代次数都可以达到一个可以接受的状态。

5 实例分析

依据文章中所提的数据采集的方法，数据采集的对象为镜湖边的焦作路矿学堂大门，通过考察后设计的测量方案中决定采取两站对物体进行测量，分别位于焦作路矿学堂大门的正面和背面。实地测量时，三维激光扫描仪开始工作，采集到的数据为焦作路矿学堂大门以及其周围事物的空间信息，得到的焦作路矿学堂大门的点云数据在软件上的显示如图5、图6所示。按照上述方法，首先提取两份点云数据的重叠区，大致为大门内侧，第二，运用RealWorks Survey Advanced 6.4对点云数据进行处理；第三，利用主方向贴合法对数据进行粗配准；第四，利用ICP算法对数据进行精配准；最后，对最终的配准结果，进行评定。该数据最终配准后的结果进行精度评定，得到的配准误差为0.048 7 mm。

图5 焦作路矿学堂背面三维显示

图6 焦作路矿学堂正面三维显示

首先，主方向贴合法主要适用于重叠率较大的点云数据，对于重叠率小的数据，其主方向的生成守干扰因素较大，必须先进行人工处理，即粗略地选取点云数据中可以重叠的区域。本文实例所采用的数据十分庞杂，不仅包含了对象物体的空间数据，还有许多其他事物的空间数据，而重叠区域仅为路矿学堂大门内侧的一部分，所占比例极小，如果直接用于粗配准，误差必然很大，因此，需要先选取出点云数据中可以重叠的区域。

其次，主方向贴合法适用于物体表面不规则的情况，例如雕像等。对于物体表面光滑的情况，该算法显现出明显的不足，例如竖直墙面等。

最后，对于两个点云数据，如果它们的点的分布规则不同，比如其中一个是均匀分布的点，另一个则是不规则分布的点，这就对它们的重心的选取产生了影响，进而对点云数据的配准产生了影响。重心选取的误差，使得点云数据虽然得到了较为正确的旋转，但在平移以后出现了很大的偏差，所提供的点云的初始迭代位置无法满足精确配准的要求，进而是得精配准后出现了这种图像交叉的现象。

6 结 论

点云数据的配准是三维建模中的一项关键技术，配准的结果好坏关系到了构建模型的完整性以及精确性，配准效果不良会导致物体的信息数字化的速度下降，将会影响整个三维数据处理工作，最终影响整个三维建模的质量。由于主方向贴合法和ICP算法有思路清晰、算法简单易于编程实现等特点，本文选取了这两种算法进行了matlab的实现，通过调试良好后对采集的数据进行了配准。文中精度评定是根据点云数据中配准点未达到配准要求的点所占总点数的比例来判定的。从配准结果中可看出主方向贴合法适用于重叠率较大的点云数据，对于重叠率小的数据，其主方向的生成守干扰因素较大，必须先进行人工处理，即粗略地选取点云数据中可以重叠的区域。ICP算法只是对每次迭代中的目标函数中的最近点最为控制点，用于估算变换矩阵的参数。迭代计算过程中，以两次迭代目标函数的值得变化小于某一个阈值为结束。因此，该算法对于初次迭代时点云的相对实际位置的要求较高。如果点云的初始相对位置相差很大，那么迭代很难保证单调收敛于最佳结果，极有可能出现局部精确配准，实际相差甚远的效果。综上所述文章的两种配准算法均得到了满意效果。