一种基于曲率特征的三维点云数据快速加权配准方法

摘要

本发明公开基于曲率特征的三维点云数据快速加权配准方法，包括：分别对待匹配点云数据P和模型点云数据M按照曲率特征进行下采样，得到待匹配点云样本数据P’和模型点云样本数据M’；计算采样点的曲率特征，并根据计算得到的曲率特征，利用索引加速方法在M’中搜索P’中各个待匹配点的匹配点，得到多个待匹配点对；对得到的多个待匹配点对，进行基于欧氏距离的筛选以去除欧氏距离大于一预设阈值的待匹配点对；对经过筛选后的待匹配点对利用迭代再加权最小二乘法进行粗匹配，得到初步刚体变换矩阵；利用初步刚体变换矩阵对P和M进行粗匹配；以初步刚体变换矩阵作为初始刚体变换矩阵，利用按距离加权的Trimmed ICP算法，对粗匹配结果进行精匹配。

说明书

技术领域

本发明涉及三维点云数据的配准领域，尤其涉及一种基于曲率特征的三维点云数据快速加权配准方法。

背景技术

近年来，三维点云数据广泛应用于三维建模、目标识别、物体表面检测等领域，三维点云数据的多角度快速、精确配准技术是当前研究的热点之一。

三维点云数据配准的目的是寻找一个三维刚体变换，将物体不同角度的离散的三维点云数据快速、精准地匹配和融合。理论上，如果能找到两组点云上确定的不共面的三个对应的点对，点云数据的配准就可以精确快速完成，但是，由于数据获取设备分辨率和精度的有限，实际上很难找到确定的三个对应的点对，因此，点云配准问题实为数据的优化问题。

传统的配准ICP(Iterative Closest Points，迭代最近点)算法被广泛应用，然而这种方法是逐点求最小的欧氏距离，运算量巨大，耗时长，并且算法的运行速度以及收敛性在很大程度上依赖于给定的初始变换估计，初始变换估计不准确会直接导致配准结果陷入局部最优值；另外，如果点云数据只有少部分重叠也会导致配准失败；再一方面，随着技术飞速发展，获取的三维点云点数据量巨大，如何达到快速而且高精度的配准成为了研究的难点。

以上背景技术内容的公开仅用于辅助理解本发明的发明构思及技术方案，其并不必然属于本专利申请的现有技术，在没有明确的证据表明上述内容在本专利申请的申请日前已经公开的情况下，上述背景技术不应当用于评价本申请的新颖性和创造性。

发明内容

本发明的主要目的在于克服传统ICP算法的不足，提高算法的实用性，提出一种基于曲率特征的三维点云数据快速加权配准方法，利用曲率特征的旋转不变性，基于点云数据曲率变化率的KD-Tree快速最近邻搜索方法，在去除边缘点和错误匹配点后，利用一种迭代再加权的IRLS-ICP算法对待匹配点进行粗匹配，然后利用按距离加权的一种TrimmedICP算法进行精匹配，获得精确度较高的刚体变换，可进行快速、精确的配准。

本发明为达上述目的所提出的技术方案如下：

一种基于曲率特征的三维点云数据快速加权配准方法，用于进行两组三维点云数据的配准，所述配准方法包括以下步骤：

S1、分别对待匹配点云数据和模型点云数据按照曲率特征进行下采样，得到待匹配点云样本数据和模型点云样本数据；

S2、计算所述待匹配点云样本数据和所述模型点云样本数据中采样点的曲率特征，并根据计算得到的曲率特征，利用索引加速方法，在所述模型点云样本数据中搜索所述待匹配点云样本数据中各个待匹配点的匹配点，得到多个待匹配点对；

S3、对步骤S2得到的多个待匹配点对，进行基于欧氏距离的筛选以去除欧氏距离大于一预设阈值的待匹配点对；

S4、对经过步骤S3筛选后的待匹配点对，利用迭代再加权最小二乘法进行粗匹配，得到初步刚体变换矩阵；

S5、利用所述初步刚体变换矩阵对所述待匹配点云数据和所述模型点云数据进行粗匹配，得到粗匹配结果；

S6、以步骤S4得到的所述初步刚体变换矩阵作为初始刚体变换矩阵，利用按距离加权的Trimmed ICP算法，对步骤S5得到的所述粗匹配结果进行精匹配。

本发明提供的上述技术方案，与现有技术相比，具有以下有益效果：

1)由于采用特征值表示的曲率特征具有旋转不变性，因此采用按照曲率特征采样的方法对海量的原始点云数据进行下采样，在简化数据、去除冗余的基础上，还能够尽可能地保证点云数据几何特征的完整性；

2)在匹配点的寻找策略中，利用了点云数据的几何特征之一即曲率特征，并采用索引加速方法来加快寻找匹配点；

3)按照最近邻匹配点欧氏距离排序，去除一定比例的错误点，可进一步减弱错误数据对匹配精度的影响；

4)应用迭代再加权的匹配算法IRLS-ICP进行粗匹配，能提高粗匹配的鲁棒性；

5)把按照距离加权的方法加入到TrimmedICP算法中进行精匹配，不仅能得到一个比较精确的匹配点对数目，还能够进一步加强正确匹配点对的作用，减弱错误匹配点对的影响，大大提高了结果的精度和鲁棒性。

附图说明

图1是本发明一种实施例提供的基于曲率特征的三维点云数据快速加权配准方法的流程图；

图2-1和图2-2是两例待匹配点云数据和模型点云数据的示意图；

图3-1和图3-2是采用传统ICP算法分别对图2-1和图2-2的点云数据进行配准得到的配准结果示意图；

图4-1和图4-2是采用本发明的方法对图2-1和图2-2的点云数据进行配准得到的配准结果示意图；

图5是传统ICP算法与本发明的方法的MSE的变化差值对比示意图。

具体实施方式

下面结合附图和具体的实施方式对本发明作进一步说明。

本发明的具体实施方式提供一种基于曲率特征的三维点云数据快速加权配准方法(后述简称“配准方法”)，可用于对任意两组海量点云数据进行配准。参考图1，所述配准方法包括以下步骤S1至S6：

步骤S1、分别对待匹配点云数据P和模型点云数据M按照曲率特征进行下采样，得到待匹配点云样本数据P’和模型点云样本数据M’。其中，可以利用matlab中的按曲率特征采样函数来进行所述下采样。在海量的点云数据中，对其中任意一个点x，描述点的几何特征一般有两类，即特征值和对应的特征向量。曲率特征对特征识别是一个很重要的基础，点的曲率特征反映了该点在点云表面的凹凸程度，其特征值可以有效地对两组散乱点云寻找匹配点。例如，参考图2，待匹配点云数据P来源于物体的实际模型100，P＝{p₁,p₂…,p_m}；模型点云数据M来源于物体的理想模型200，M＝{y₁,y₂…,y_n}。

步骤S2、计算所述待匹配点云样本数据P’和所述模型点云样本数据M’中采样点的曲率特征，并根据计算得到的曲率特征，利用索引加速方法，在所述模型点云样本数据M’中搜索所述待匹配点云样本数据中各个待匹配点的匹配点，得到多个待匹配点对。其中，点的曲率特征可以通过分析其k个最近邻点的协方差矩阵而获得，k的值会影响匹配的结果，k代表该点的搜索半径内点的数量，因此，为了增强鲁棒性，采用逐渐扩大搜索半径来搜索最近邻点，再取不同搜索半径下计算出的曲率特征的差值作为匹配信息对两组散乱的点云数据寻找匹配点。

在一种优选的实施例中，利用KD-Tree加速方法在M’中搜索P’中各待匹配点p_i的匹配点y_i，该过程具体包括：对每一待匹配点p_i，取不同搜索半径下计算得到的曲率特征并进行相邻搜索半径之间的曲率特征差值计算，将计算得到的曲率特征差值组成一个矩阵，作为所述待匹配点的匹配计算矩阵；基于所述匹配计算矩阵，利用KD-Tree加速方法在所述模型点云数据中搜索所述待匹配点的最邻近点，以得到所述待匹配点的匹配点。例如，对于任意待匹配点p，假设有D个不同的搜索半径，则对于任意搜索半径r_d，其协方差矩阵C_d为：

其中，d＝1,…,D，K_d＝{x_i|||x_i-p||≤r_d}为搜索半径r_d内点的个数，x_i为搜索到的半径r_d内p的最近邻点集，p为待匹配点云样本数据P’中的任一点。应用奇异值分解法处理得到的3×3的协方差矩阵C_d，从而可得到三个特征值及其特征向量，选取从大到小的三个特征值λ_d1、λ_d2、λ_d3来描述点的曲率特征，并将三个特征值组成的向量规范化，得到p在搜索半径r_d下的曲率特征s_d，记为：

由于利用特征值代表的曲率特征有着旋转不变性，伴随着搜索半径逐渐变大，s_d缓慢变化，因此，选取相邻搜索半径下曲率特征的差值Δs_d作为搜索的匹配点的匹配信息，定义为Δs_d＝s_d+1-s_d，将该点的所有Δs_d组成一个矩阵N，作为搜索匹配点时的匹配计算矩阵，其表达式为：

基于上述矩阵N，利用KD-Tree加速方法即可在M’中(或M中)快速寻找P’中各待匹配点p_i的匹配点y_i，从而得到多个待匹配点对<p_i,y_i>。

步骤S3、对步骤S2得到的多个待匹配点对，进行基于欧氏距离的筛选以去除欧氏距离大于一预设阈值的待匹配点对。由于步骤S2得到的待匹配点对难免存在误差，即有些点对中的两个点可能实际上并不是相匹配的，因此，本步骤中采用基于欧氏距离的筛选来去除可能匹配错误的点对，这是后续进行点云粗匹配的关键。

在一具体的实施例中，步骤S3进行基于欧氏距离的筛选的过程大致包括：首先，对每个待匹配点对，都计算点对内两个点的欧氏距离；其次，将各个待匹配点对按欧氏距离大小进行排序，然后去除10％最差(欧氏距离越大，则越差)的待匹配点对。或者，可以预先设定一阈值，如果欧氏距离大于该阈值的点对就去除。

在更优选的实施例中，还可进一步对上述经过基于欧氏距离筛选之后的待匹配点对进行去除尖锐点的二次筛选。所述二次筛选采用三角剖分点云数据的方法找到尖锐点，可对两组点云数据中任一组进行三角剖分，找出在三角平面外的尖锐点，再将这些尖锐点及其在另一组点云数据中的匹配点一同去除。比如：先对所述待匹配点云数据P进行三角剖分，再从经过基于欧氏距离的筛选后的匹配点对的待匹配点中找出位于三角平面外的尖锐点，并将包含所述尖锐点的匹配点对删除；或者，对所述模型点云数据M进行三角剖分，再从经过基于欧氏距离的筛选后的匹配点对的模型点中找出位于三角平面外的尖锐点，并将包含所述尖锐点的匹配点对删除。

经过上述两道筛选去除错误的匹配点和边界点所在的待匹配点对后，大大减弱了错误点对匹配结果的扰动，为下一步粗配准奠定了基础。

步骤S4、对经过步骤S3筛选后的待匹配点对，利用迭代再加权最小二乘法(IRLS-ICP)进行粗匹配，得到初步刚体变换矩阵。在粗配准过程中，应用一种迭代再加权最小二乘法(IRLS-ICP)，两组散乱点云配准本质上是找到包含一个旋转矩阵R和一个平移向量t的刚体变换矩阵，该刚体变换矩阵能将两组处于不同坐标系下的海量散乱点云数据变换到同一个坐标系中，并实现精确地配准重合。该算法(IRLS-ICP)主要包括两个步骤：寻找最近邻点和寻找能够使两组点云匹配的刚体变换矩阵，具体如下：

首先，初始化一个刚体变换(R⁽⁰⁾，t⁽⁰⁾)，R⁽⁰⁾＝I,t⁽⁰⁾＝0。设定符号C为最近邻点运算符，则求待匹配点p_i在模型点云数据M中(或M’中)的最近邻点y_i的运算公式即可表示为：

其中，k-1表示迭代次数。

从而，迭代更新的刚体变换(R^*，t^*)可由下式得到：

[R^*,t^*]＝argming(R,t)>

其中，

其中，w(r)为Tukey’s bi-weight权重函数，r为点对内两点之间的欧氏距离，k_Tu＝7.0589，Tukey’s>

当利用所有待匹配点对完成上述对刚体变换的迭代更新后，即完成了待匹配点对的粗匹配，即得到了一个初步的刚体变换矩阵。

步骤S5、利用步骤S4得到的初步刚体变换矩阵对所述待匹配点云数据P和所述模型点云数据M进行粗匹配，得到粗匹配结果。

步骤S6、再以步骤S4得到的初步刚体变换矩阵作为初始刚体变换矩阵，利用按距离加权的Trimmed ICP算法，对步骤S5得到的所述粗匹配结果进行精匹配。从而完成了两组点云数据P和M的精确配准。

为克服传统ICP算法的局限性，改进的方法一般从提高算法的鲁棒性、收敛性(收敛速度)和精确性三个方面开展研究。而本发明的核心在于保证数据完整的基础上尽量减少冗余数据，适当简化数据点的个数以提升运算速度，同时尽可能的增加正确的匹配点个数，特别是特征明显的点，以提高算法的鲁棒性和准确性。为了减弱错误的匹配点对所代入的误差，可以通过对待匹配点对加权系数来加强正确匹配点对的作用，减弱错误匹配点对的影响。因此，步骤S6提出将按欧氏距离加权加入到Trimmed ICP算法中进行精匹配。具体做法是：

首先，对于Trimmed ICP算法最终获取的每一个匹配点对求基于欧氏距离的加权系数，例如一个匹配点对(p,q)，其欧氏距离表示的加权系数为：

然后，利用加权系数w^P再对点云数据P’和M进行一次精匹配。

Trimmed ICP算法是传统ICP算法的一个提高鲁棒性的改良版，该算法将各匹配点对的平方误差进行排序，只对一定数目的较小的值进行优化，这个数目是根据两组点云数据初始的重叠率获得，Trimmed ICP具有更好的收敛速率和鲁棒性。本发明把按照距离加权的方法加入到Trimmed ICP算法中，这样不仅得到了一个比较精确的匹配点对数目，还能够进一步加强正确匹配点对的作用，减弱错误匹配点对的影响，简化了海量数据的计算量，提高了结果的精度。

下面对本发明提出的基于曲率特征的快速加权配准方法进行仿真验证，以评估算法的有效性。具体而言，是将本发明的方法与常用的ICP算法进行比较。采用StanfordUniversity Graphic Laboratory数据集中的Bunny数据集和Dragon数据集进行对比评估。在实验中，分别使用算法消耗的时间、均方差MSE和MSE的变化差值与时间的曲线对传统ICP算法和本发明提出的算法的实时性、准确性和鲁棒性进行评估比较。

如图2-1和图2-2所示，所采用的Bunny数据集和Dragon数据集均是包括待匹配的点云模型100(模型上的所有三维点云构成待匹配点云数据P)和理论点云模型200(模型上的所有三维点云构成模型点云数据M)。对于同样的两例数据集Bunny数据集和Dragon数据集，采用本发明的配准方法进行配准后得到的结果如图4-1和图4-2所示，而采用传统ICP算法进行配准后得到的结果如图3-1和图3-2所示，可以看出，本发明的配准结果更精确，而图3-1和图3-2中的配准结果较差一些，例如图3-1所示的配准结果，存在多处不重叠之处例如10、20、30等区域。实验结果表明，传统ICP算法由于其对初始条件有一定的局限性，很难得到精确的配准结果，并且随着点云数据的复杂性提高(比如Dragon数据集)，与复杂度较低的Bunny数据集相比，配准结果更差。反观本发明，所提出的算法对两例数据集都能完成精确的配准。另一方面，通过性能比较，传统ICP算法通过逐点求取欧氏距离的方法来寻找最近邻点，计算量巨大，耗时长，匹配时间约为113.2s，均方差为1.594×10^-5m。本发明提出的算法不管是在时间上还是在精度上都取得了很好的配准效果，匹配时间约为31.1s，均方差为1.97×10^-6m，匹配精度提高了接近十倍。

再对比本发明与传统ICP算法MSE的变化差值，可得到图5所示的曲线，横坐标代表时间，纵坐标即代表算法的MSE的变化差值，从图中可以看出：传统ICP算法收敛非常缓慢，而且还伴随着较大的波动；本发明提出的算法不管在收敛性还是鲁棒性都有更好的效果。

随着技术飞速发展，获取的三维点云数据量越来越庞大，如何处理海量三维数据并达到快速且高精度的配准成为了研究的难点。针对散乱的三维点云配准中基于传统ICP算法的局限性，本专利算法首先按照曲率特征进行下采样，利用曲率特征快速寻找匹配点，并去除错误点对，利用IRLS-ICP算法进行散乱点云粗匹配，最后用按距离加权的TrimmedICP算法进行精匹配。通过上述实验结果证明了本发明的方法达到很好的收敛性和鲁棒性，大大缩减了配准的时间。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的技术人员来说，在不脱离本发明构思的前提下，还可以做出若干等同替代或明显变型，而且性能或用途相同，都应当视为属于本发明的保护范围。