基于邻域旋转体积的点云配准方法

摘要

本发明提供一种基于邻域旋转体积的点云配准方法，属于三维图像技术领域，目的是解决现有点云配准方法存在的配准速度慢和抗噪性差等技术问题。包括：载入并分别计算视角相邻的源点云和目的点云的源关键点集合和目的关键点集合；对每个关键点，分别以n倍表面分辨率为邻域计算出邻域内点的旋转体积作为描述向量，得到源关键点描述向量集和目的关键点描述向量集；根据上一步计算结果计算旋转平移矩阵；利用旋转平移矩阵对源关键点描述向量集进行旋转平移得到中间关键点描述向量集；根据中间关键点描述向量集确定最终的旋转平移矩阵；根据最终的旋转平移矩阵将源点云变换到目的点云所在坐标系得到中间点云；利用ICP算法精确配准中间点云和目的点云。

说明书

技术领域

本发明属于三维图像技术领域，具体涉及一种基于邻域旋转体积的点云配准方法，该点云配准方法适用于解决表面具有一部分重合的两片点云的拼接、配准问题。

背景技术

随着三维(3D)点云扫描技术的发展，硬件设备越来越低廉，三维点云数据获取越来越便捷。三维点云数据被广泛应用于各个领域中，如工业零部件的生产、产品质量控制、生物医学、文物、建筑保护等。在数据获取过程中，由于受测量设备视野的限制，通常只能获取被测物体的部分表面视图，而难于一次性获得物体完整的三维点云模型。因此，需要将从多个视角获得的点云数据进行坐标变换，统一到同一坐标系下，形成能完整描述物体的三维点云模型，这就是点云配准问题。

目前，点云配准方法多采用由Besl等提出的ICP(Iterative Closet Point，最近点迭代)算法及其相关改进算法，其核心思想是通过迭代的方式不断地寻找两片点云中的欧式距离最近的点作为匹配点对，并根据匹配点对计算出变换矩阵，达到逼近最佳配准结果的目的。但是，ICP算法中当两片点云初始位置相距较远时，算法要求提供比较精准的初始变换矩阵，否则不仅迭代次数多、收敛速度慢，且易陷入局部收敛、抗噪性差；另外，用于迭代的点云间的对应点对是基于最近欧式距离来获取的，容易造成大量的误匹配点对，从而增加迭代的次数和计算的复杂度。

发明内容

为了解决现有三维点云配准方法存在的迭代次数多、收敛速度慢、计算复杂、配准速度慢、抗噪性差等技术问题，本发明提供了一种基于邻域旋转体积的点云配准方法。

为解决上述技术问题，本发明采用的技术方案是：

一种基于邻域旋转体积的点云配准方法，所述点云配准方法包括：

步骤1，载入视角相邻的源点云source和目的点云target，并分别计算源点云的表面分辨率mr_src和目的点云的表面分辨率mr_tgt；

步骤2，对源点云source和目的点云target，分别以n*mr_src和n*mr_tgt为邻域，计算源点云的法向量normal_src和目的点云的法向量normal_tgt；

步骤3，利用Harris3D算法，根据源点云的法向量normal_src计算源点云的源关键点集合keypoints_src，根据目的点云的法向量normal_tgt计算目的点云的目的关键点集合keypoints_tgt；

步骤4，对源关键点集合keypoints_src和目的关键点集合keypoints_tgt中的每个关键点，分别以n倍表面分辨率为邻域计算出局部坐标系，并根据局部坐标系计算出邻域内点的旋转体积作为描述向量，得到源关键点描述向量集features_src和目的关键点描述向量集features_tgt；

步骤5，根据源关键点描述向量集features_src和目的关键点描述向量集features_tgt，在源关键点集合keypoints_src和目的关键点集合keypoints_tgt中确定多个匹配关键点对；根据匹配关键点对计算出从源关键点描述向量集features_src到目的关键点描述向量集features_tgt的旋转平移矩阵Rt；利用旋转平移矩阵Rt对源关键点描述向量集features_src进行旋转和平移，得到中间关键点描述向量集features_src'；计算中间关键点描述向量集features_src'中的每个描述向量与目的关键点描述向量集features_tgt中的对应描述向量之间的平均欧式距离；多次执行该步骤，取平均欧式距离最小时的旋转平移矩阵Rt作为最终的旋转平移矩阵；

步骤6，根据最终的旋转平移矩阵将源点云source变换到目的点云target所在的坐标系下，得到中间点云source′，以完成根据关键点对源点云source和目的点云target的粗配准；

步骤7，利用ICP算法对中间点云source′和目的点云target进行精确配准。

其中，所述步骤1中，分别计算源点云的表面分辨率mr_src和目的点云的

表面分辨率mr_tgt，包括：

步骤1.1，对于源点云source和目的点云target中的每一个点，通过KD-tree算法找到其最近点；

步骤1.2，计算每一个点与其最近点之间的距离d_i；

步骤1.3，通过如下公式(1)计算点云的表面分辨率mr：

其中，N为点云中点的个数。

可选地，所述步骤4中，对源关键点集合keypoints_src和目的关键点集合keypoints_tgt中的每个关键点，分别以n倍表面分辨率为邻域计算出局部坐标系，并根据局部坐标系计算出邻域内点的旋转体积作为描述向量，得到源关键点描述向量集features_src和目的关键点描述向量集features_tgt，包括：

对于源关键点集合keypoints_src和目的关键点集合keypoints_tgt中的任一关键点p，计算p的描述向量的过程通过如下步骤4.1至步骤4.4实现：

步骤4.1，建立p点及其邻域点Nbhd(p)的局部坐标系，具体为：

首先，以p的法向量为z轴；然后，在Nbhd(p)内找到法向量与p的法向量之间的夹角最小的关键点q，并连接p与q在p的切平面上的投影点q'，将该方向作为x轴；最后，根据z×x计算出y轴，形成p处的局部坐标系其中p为该局部坐标系的原点，代表x轴，代表y轴，代表z轴；

步骤4.2，对邻域球S进行空间几何区间划分，形成m个区间，其中，邻域球S是指Nbhd(p)形成的空间，邻域球S的圆心为p，半径为R，R＝n×mr，mr为源点云的表面分辨率mr_src或目的点云的表面分辨率mr_tgt，具体为：

首先，以的正方向和邻域球S的交点p_north为北极，的逆方向与邻域球S的交点p_south为南极，为中轴，沿着邻域球S球面的经线均匀地将邻域球S剖分为m个区间，该区间集合记为Region，每个独立区间记为Region_j(j∈[0m-1])；然后，将邻域球S正投影到upv平面后所得的圆沿圆心平行下移至以p_south为圆心处，记该圆为C_{prj_S}，该圆C_{prj_S}也即为圆心在p_south、半径为R的与邻域球S正切的圆；接下来，将Region_j分别投影到C_{prj_S}上，形成m个扇形，扇形集合记为Sector，每个扇形记为Sector_j(j∈[0m-1])，且Region_j与Sector_j一一对应；

步骤4.3，确定Nbhd(p)中每个点所属的区间，具体为：

首先，将Nbhd(p)中的任一点p_i，按照如下公式(2)投影到upv平面上，投影点记为q_i，并根据如下公式(3)计算出与坐标轴的逆时针夹角α_i；

然后，因为圆C_{prj_S}所在的平面与upv平面平行的关系，因此，可根据α_i的值计算q_i所属的扇形，从而确定出q_i所处的区间；接着，由p_i与q_i的一一对应性，确定出p_i所处的区间；其中，p_i所处的区间与q_i所处的区间相同；

步骤4.4，计算p的第k(k∈[0m-1])个维度的数值，具体为：

首先，对每个区间内的邻域点集中的每个点，计算其在upv平面上投影点与p的距离，将距离由小到大进行排序，得到每个区间的邻域点序列的各个元素，并将p点作为首元素加入到每个区间的邻域点序列中，形成每个区间的邻域点序列，该邻域点序列记为Nbhd(p)_k(k∈[0m-1])；

设任一区间Region_k的邻域点序列Nbhd(p)_k为{p,p₁,p₂,...,p_s}，按序依次取出p和p₁，并分别投影至C_{prj_S}平面上，投影点分为别为p_south和q₁，依次连接p_south、q₁、p₁和p形成一个梯形T₁；然后，将T₁绕着轴旋转360°，其扫过的体积记为V_k，1；同理，依次计算序列<p₁，p₂>、<p₂，p₃>，…，<p_s-1，p_s>扫过的体积V_k，2，V_k，3，…，V_k，s；接下来，利用如下公式(4)将所有体积累加从而计算出Region_k内所有邻域点序列扫过的体积和V_k，将其作为p的描述向量的第k个维度的数值；

其中，在计算Region_k中两相邻邻域点<p_i-1，p_i>及其投影点<q_i-1，q_i>所形成的梯形旋转后的模型的体积V_k,i时，可将该模型拆分为一个空心圆柱体Model_k,i,1和一个中间为空心圆柱的圆台Model_k,i,2；Model_k,i,1的体积V_k,i,1可通过如下公式(5)进行计算，其中，h_k,i,1代表Model_k,i,1的高，可通过如下公式(6)进行计算；r_k,i-1和r_k,i分别代表Model_k,i,1的内、外半径，均可通过如下公式(7)进行计算；Model_k,i,2的体积V_k,i,2可由圆台的体积V_k,i,3与圆柱的体积V_k,i,4相减而得，见如下公式(8)；如下公式(9)用于计算体积V_k,i,3，其中h_k,i,2代表圆台的高，r_k,i-1和r_k,i分别代表圆台的内、外半径，其也通过公式(7)进行计算；公式(10)用于计算体积V_k,i,4，其中h_k,i,2代表空心圆柱的高，其通过公式(11)进行计算，r_k,i-1代表圆柱的半径；另外，r_k,0＝0，h_k,0,1＝R；

V_k,i,2＝V_k,i,3-V_k,i,4(8)

h_k,i,2＝h_k,i-1,1-h_k,i,1(11)；

步骤4.5，依据上述步骤4.4，计算p的其余m-1个维度的数值，最终组成p的m维的描述向量。

可选地，所述步骤5中，根据源关键点描述向量集features_src和目的关键点描述向量集features_tgt，在源关键点集合keypoints_src和目的关键点集合keypoints_tgt中确定多个匹配关键点对；根据匹配关键点对计算出从源关键点描述向量集features_src到目的关键点描述向量集features_tgt的旋转平移矩阵Rt；利用旋转平移矩阵Rt对源关键点描述向量集features_src进行旋转和平移，得到中间关键点描述向量集features_src'；计算中间关键点描述向量集features_src'中的每个描述向量与目的关键点描述向量集features_tgt中的对应描述向量之间的平均欧式距离；多次执行该步骤，取平均欧式距离最小时的旋转平移矩阵Rt作为最终的旋转平移矩阵，包括：

步骤5.1，随机从源关键点描述向量集features_src中选取3组描述向量fs0、fs1和fs2，置入集合fs中，利用KD-Tree算法在目的关键点描述向量集features_tgt中为fs0搜索5个欧式距离最近的描述向量，并从5个欧式距离最近的描述向量中随机选取一个描述向量ft0作为fs0对应的描述向量；同理，从目的关键点描述向量集features_tgt中确定fs1对应的描述向量ft1和fs2对应的描述向量ft2，将ft0、ft1和ft2置入集合ft中；

步骤5.2，在源关键点集合keypoints_src中找到fs0、fs1和fs2分别对应的源关键点ks0、ks1和ks2，在目的关键点集合keypoints_tgt中找到ft0、ft1和ft2分别对应的目的关键点kt0、kt1和kt2，形成匹配关键点对<ks0，kt0>、<ks1，kt1>和<ks2，kt2>；依次连接ks0和ks1、ks1和ks2、ks2和ks0形成三条边并分别计算三条边的长度，记为d_ks01、d_ks12和d_ks20；同理，依次连接kt0和kt1、kt1和kt2、kt2和kt0形成三条边并分别计算三条边的长度，记为d_kt01、d_kt12和d_kt20；依次计算对应边长度相似比，即计算min(d_ks01/d_kt01，d_kt01/d_ks01)、min(d_ks12/d_kt12，d_kt12/d_ks12)和min(d_ks20/d_kt20，d_kt20/d_ks20)；如果相似比均大于预设阈值δ(δ∈[0 1])，则执行步骤5.3，否则返回步骤5.1；

步骤5.3，基于匹配关键点对<ks0，kt0>、<ks1，kt1>和<ks2，kt2>，通过SVD算法分解计算从源关键点描述向量集features_src到目的关键点描述向量集features_tgt的旋转平移矩阵Rt；

步骤5.4，利用旋转平移矩阵Rt对源关键点描述向量集features_src进行旋转和平移，得到中间关键点描述向量集features_src'；对中间关键点描述向量集features_src'中的每个描述向量，利用KD-Tree算法在目的关键点描述向量集features_tgt中搜索欧式距离最近的描述向量作为其对应的描述向量，并计算中间关键点描述向量集features_src'中的每个描述向量与目的关键点描述向量集features_tgt中的对应描述向量之间的平均欧式距离，将该平均欧式距离作为一个评价标准fitness；

步骤5.5，多次执行上述步骤5.1至5.4，选取最小fitness时的旋转平移矩阵作为最终的旋转平移矩阵。

本发明采用上述技术方案，利用Harris 3D算法对载入的源点云和目的点云进行处理，以确定源点云和目的点云中的关键点，并在进一步确定关键点的描述向量时通过在关键点处建立局部坐标系的方式，可以增加配准方法的旋转平移稳定性，同时描述时仅仅利用关键点邻域内点的位置等简单信息计算描述向量，避免复杂运算，相对其它方法减少了运行时间，提高了配准效率。在寻找匹配关键点对的过程中采用寻找多个匹配关键点的方法，避免只找一个对应点时因噪声等因素造成的误匹配，使得配准结果更加准确。同时在计算旋转平移矩阵过程中，采用多次计算找最优解的方法，减少结果错误的几率，增大了配准的准确性。因此，与背景技术相比，本发明具有计算量少、方法简单、配准速度快、旋转平移鲁棒性高、抗噪性好、稳定性高及配准结果更准确等优点。

附图说明

图1是本发明的方法流程图。

具体实施方式

下面结合附图和实施例对本发明作进一步的详细描述。

目前，为了提高点云配准的效率，减少配准过程中的迭代次数、解决抗噪性差的问题，很多方法采用先将点云的关键点进行配准，以期完成两片点云之间的粗配准，使两片点云具有良好的初始位置，再利用ICP或其改进算法对点云进行精配准，从而可以确保获得正确、完整的三维点云模型。本发明在点云配准过程中，也是先提取两片点云的关键点，先对点云的关键点进行配准，以完成两片点云之间的粗配准后，再利用ICP或其改进算法对点云进行精配准。具体的点云配准方法详见下述内容：

如图1所示，本发明中的基于邻域旋转体积的点云配准方法，其包括步骤1至步骤7：

步骤1，载入视角相邻的源点云source和目的点云target，并分别计算源点云的表面分辨率mr_src和目的点云的表面分辨率mr_tgt。

其中，在分别计算源点云的表面分辨率mr_src和目的点云的表面分辨率mr_tgt时，可以通过下述步骤1.1至步骤1.3来实现：

步骤1.1，对于源点云source和目的点云target中的每一个点，通过KD-tree算法找到其最近点；

步骤1.2，计算每一个点与其最近点之间的距离d_i；

步骤1.3，通过如下公式(1)计算点云的表面分辨率mr：

其中，N为点云中点的个数。

具体地，在计算源点云的表面分辨率mr_src时，对于源点云source中的每个点，先通过KD-tree算法找到其最近点；然后，计算每一个点与其最近点之间的距离d_i；接下来，通过公式(1)计算源点云的表面分辨率mr_src，此时，N代表源点云source中点的个数。

在计算目的点云的表面分辨率mr_tgt时，对于目的点云target中的每个点，先通过KD-tree算法找到其最近点；然后，计算每一个点与其最近点之间的距离d_i；接下来，通过公式(1)计算目的点云的表面分辨率mr_src，此时，N代表目的点云target中点的个数。其中，源点云source中点的个数与目的点云target中点的个数可以相同，也可以不同。

步骤2，对源点云source和目的点云target，分别以n*mr_src和n*mr_tgt为邻域，计算源点云的法向量normal_src和目的点云的法向量normal_tgt。

其中，n的取值通常为6-18。另外，计算源点云的法向量normal_src和目的点云的法向量normal_tgt的方式，可以参考已有的点云法向量的计算方式，此处不做具体阐述。

步骤3，利用Harris 3D算法根据源点云的法向量normal_src计算源点云的源关键点集合keypoints_src，利用Harris3D算法根据目的点云的法向量normal_tgt计算目的点云的目的关键点集合keypoints_tgt。

该步骤为提取源点云source和目的点云target的关键点的步骤。本发明具体通过Harris 3D算法提取源点云source和目的点云target的关键点。其中，利用Harris 3D算法分别根据源点云的法向量normal_src和目的点云的法向量normal_tgt计算源点云的源关键点集合keypoints_src和目的关键点集合keypoints_tgt的具体实现方式，可参见已有的关键点提取算法来实现。

步骤4，对源关键点集合keypoints_src和目的关键点集合keypoints_tgt中的每个关键点，分别以n倍表面分辨率为邻域计算出局部坐标系，并根据局部坐标系计算出邻域内点的旋转体积作为描述向量，得到源关键点描述向量集features_src和目的关键点描述向量集features_tgt。

该步骤中，对于源关键点集合keypoints_src和目的关键点集合keypoints_tgt中的任一关键点p，在以n倍表面分辨率为邻域计算出局部坐标系，并根据局部坐标系计算出邻域内点的旋转体积作为p的描述向量时，可以通过如下步骤4.1至步骤4.5实现：

步骤4.1，建立p点及其邻域点Nbhd(p)的局部坐标系，具体为：

首先，以p的法向量为z轴；然后，在Nbhd(p)内找到法向量与p的法向量之间的夹角最小的关键点q，并连接p与q在p的切平面上的投影点q'，将该方向作为x轴；最后，根据z×x计算出y轴，形成p处的局部坐标系其中p为该局部坐标系的原点，代表x轴，代表y轴，代表z轴。本发明中，字母上面的箭头均表示向量。

步骤4.2，对邻域球S进行空间几何区间划分，形成m个区间，其中，邻域球S是指Nbhd(p)形成的空间，邻域球S的圆心为p，半径为R，R＝n×mr，且当p为源关键点集合keypoints_src中的一个关键点时，mr为源点云的表面分辨率mr_src；当p为目的关键点集合keypoints_tgt中的一个关键点时，mr为目的点云的表面分辨率mr_tgt。其中，m的取值可以为24、36或48等。该步骤4.2具体为：

首先，以的正方向和邻域球S的交点p_north为北极，的逆方向与邻域球S的交点p_south为南极，为中轴，沿着邻域球S球面的经线均匀地将邻域球S剖分为m个区间，该区间集合记为Region，每个独立区间记为Region_j(j∈[0m-1])；然后，将邻域球S正投影到upv平面后所得的圆沿圆心平行下移至以p_south为圆心处，记该圆为C_{prj_S}，该圆C_{prj_S}也即为圆心在p_south、半径为R的与邻域球S正切的圆；接下来，将Region_j分别投影到C_{prj_S}上，形成m个扇形，扇形集合记为Sector，每个扇形记为Sector_j(j∈[0m-1])，且Region_j与Sector_j一一对应。

步骤4.3，确定Nbhd(p)中每个点所属的区间，具体为：

首先，将Nbhd(p)中的任一点p_i，按照如下公式(2)投影到upv平面上，投影点记为q_i，并根据如下公式(3)计算出与坐标轴的逆时针夹角α_i；

然后，因为圆C_{prj_S}所在的平面与upv平面平行的关系，因此，可根据α_i的值计算q_i所属的扇形，从而确定出q_i所处的区间；接着，由p_i与q_i的一一对应性，确定出p_i所处的区间；其中，p_i所处的区间与q_i所处的区间相同。例如，如果q_i属于Sector₃，则q_i所处的区间为Region₃，p_i所处的区间也为Region₃。

例如，如果m的取值为36，第一个扇形所包括的度数区间为0°到9°，第二个扇形所包括的度数区间为10°到19°，以此类推，则，在计算出α_i的值后，即可根据α_i的值确定其属于哪个度数区间，进而确定q_i所属的扇形，如，如果α_i的值为12，则可以确定q_i属于第二个扇形。

步骤4.4，计算p的第k(k∈[0m-1])个维度的数值，具体为：

首先，对每个区间内的邻域点集中的每个点，计算其在upv平面上投影点与p的距离，将距离由小到大进行排序，得到每个区间的邻域点序列的各个元素，并将p点作为首元素加入到每个区间的邻域点序列中，形成每个区间的邻域点序列，该邻域点序列记为Nbhd(p)_k(k∈[0m-1])；

设任一区间Region_k的邻域点序列Nbhd(p)_k为{p,p₁,p₂,...,p_s}，按序依次取出p和p₁，并分别投影至C_{prj_S}平面上，投影点分为别为p_south和q₁，依次连接p_south、q₁、p₁和p形成一个梯形T₁；然后，将T₁绕着轴旋转360°，其扫过的体积记为V_k，1；同理，依次计算序列<p₁，p₂>、<p₂，p₃>，…，<p_s-1，p_s>扫过的体积V_k，2，V_k，3，…，V_k，s；接下来，利用如下公式(4)将所有体积累加从而计算出Region_k内所有邻域点序列扫过的体积和V_k，将其作为p的描述向量的第k个维度的数值；

其中，在计算Region_k中两相邻邻域点<p_i-1，p_i>及其投影点<q_i-1，q_i>所形成的梯形旋转后的模型的体积V_k,i时，可将该模型拆分为一个空心圆柱体Model_k,i,1和一个中间为空心圆柱的圆台Model_k,i,2；Model_k,i,1的体积V_k,i,1可通过如下公式(5)进行计算，其中，h_k,i,1代表Model_k,i,1的高，可通过如下公式(6)进行计算；r_k,i-1和r_k,i分别代表Model_k,i,1的内、外半径，均可通过如下公式(7)进行计算；Model_k,i,2的体积V_k,i,2可由圆台的体积V_k,i,3与圆柱的体积V_k,i,4相减而得，见如下公式(8)；如下公式(9)用于计算体积V_k,i,3，其中h_k,i,2代表圆台的高，r_k,i-1和r_k,i分别代表圆台的内、外半径，其也通过公式(7)进行计算；公式(10)用于计算体积V_k,i,4，其中h_k,i,2代表空心圆柱的高，其通过公式(11)进行计算，r_k,i-1代表圆柱的半径；另外，r_k,0＝0，h_k,0,1＝R；

V_k,i,2＝V_k,i,3-V_k,i,4(8)

h_k,i,2＝h_k,i-1,1-h_k,i,1(11)。

步骤4.5，依据上述步骤4.4，计算p的其余m-1个维度的数值，最终组成p的m维的描述向量。

按照上述步骤4.1至步骤4.5，对源关键点集合keypoints_src中的每个关键点，均确定其描述向量，并将每个关键点的描述向量组合为一个集合，即得到源关键点描述向量集features_src。同理，对目的关键点集合keypoints_tgt中的每个关键点，均确定其描述向量，并将每个关键点的描述向量组合为一个集合，即得到目的关键点描述向量集features_tgt。

步骤5，根据源关键点描述向量集features_src和目的关键点描述向量集features_tgt，在源关键点集合keypoints_src和目的关键点集合keypoints_tgt中确定多个匹配关键点对；根据匹配关键点对计算出从源关键点描述向量集features_src到目的关键点描述向量集features_tgt的旋转平移矩阵Rt；利用旋转平移矩阵Rt对源关键点描述向量集features_src进行旋转和平移，得到中间关键点描述向量集features_src'；计算中间关键点描述向量集features_src'中的每个描述向量与目的关键点描述向量集features_tgt中的对应描述向量之间的平均欧式距离；多次执行该步骤，取平均欧式距离最小时的旋转平移矩阵Rt作为最终的旋转平移矩阵。

具体地，该步骤可以通过如下步骤5.1至步骤5.5来实现：

步骤5.1，随机从源关键点描述向量集features_src中选取3组描述向量fs0、fs1和fs2，置入集合fs中，利用KD-Tree算法在目的关键点描述向量集features_tgt中为fs0搜索5个欧式距离最近的描述向量，并从5个欧式距离最近的描述向量中随机选取一个描述向量ft0作为fs0对应的描述向量；同理，从目的关键点描述向量集features_tgt中确定fs1对应的描述向量ft1和fs2对应的描述向量ft2，将ft0、ft1和ft2置入集合ft中。

步骤5.2，在源关键点集合keypoints_src中找到fs0、fs1和fs2分别对应的源关键点ks0、ks1和ks2，在目的关键点集合keypoints_tgt中找到ft0、ft1和ft2分别对应的目的关键点kt0、kt1和kt2，形成匹配关键点对<ks0，kt0>、<ks1，kt1>和<ks2，kt2>；依次连接ks0和ks1、ks1和ks2、ks2和ks0形成三条边并分别计算三条边的长度，记为d_ks01、d_ks12和d_ks20；同理，依次连接kt0和kt1、kt1和kt2、kt2和kt0形成三条边并分别计算三条边的长度，记为d_kt01、d_kt12和d_kt20；依次计算对应边长度相似比，即计算min(d_ks01/d_kt01，d_kt01/d_ks01)、min(d_ks12/d_kt12，d_kt12/d_ks12)和min(d_ks20/d_kt20，d_kt20/d_ks20)；如果相似比均大于预设阈值δ(δ∈[0 1])，则执行步骤5.3，否则返回步骤5.1。其中，预设阈值δ的取值优选为0.6-0.8。

步骤5.3，基于匹配关键点对<ks0，kt0>、<ks1，kt1>和<ks2，kt2>，通过SVD算法分解计算从源关键点描述向量集features_src到目的关键点描述向量集features_tgt的旋转平移矩阵Rt。

具体通过SVD算法分解计算旋转平移矩阵Rt的方式，可以参见已有的技术，本发明对此不作详细阐述。

步骤5.4，利用旋转平移矩阵Rt对源关键点描述向量集features_src进行旋转和平移，得到中间关键点描述向量集features_src'；对中间关键点描述向量集features_src'中的每个描述向量，利用KD-Tree算法在目的关键点描述向量集features_tgt中搜索欧式距离最近的描述向量作为其对应的描述向量，并计算中间关键点描述向量集features_src'中的每个描述向量与目的关键点描述向量集features_tgt中的对应描述向量之间的平均欧式距离，将该平均欧式距离作为一个评价标准fitness。

步骤5.5，循环多次执行上述步骤5.1至5.4，选取最小fitness时的旋转平移矩阵作为最终的旋转平移矩阵。

其中，循环执行的次数可以为50000-100000次，次数越多，确定的最终的旋转平移矩阵越准确。

步骤6，根据最终的旋转平移矩阵将源点云source变换到目的点云target所在的坐标系下，得到中间点云source′，以完成根据关键点对源点云source和目的点云target的粗配准。

步骤7，利用ICP算法对中间点云source′和目的点云target进行精确配准。

其中，也可以利用ICP改进算法对中间点云source′和目的点云target进行精确配准。采用ICP算法或ICP改进算法对中间点云source′和目的点云target进行精确配准的方式采用已有技术中的方式，本发明对此不作详细阐述。

为表明本发明具有以上优点，分别利用SHOT方法、FPFH方法以及本发明所述配准方法对同样的三维点云模型进行配准。因为经过ICP算法精确配准后模型配准基本都能达到一个良好的效果，所以只对精确配准之前的粗配准结果进行配准效果比较，而对运行时间方面采用整个配准流程的运行时间进行比较。表1为三种方法运行时间上的对比。

经过比较发现，虽然SHOT方法和FPFH方法同样对点云数据进行了配准处理，但是在配准的准确性上比不上本发明提出的方法。

表1不同方法配准时间对比

方法SHOTFPFH本发明配准时间(ms)1703953734

从表1可以看出，使用本发明提出的配准方法较其它方案在配准效率上有了很大的提高。