一种多视角三维激光点云全局优化整体配准方法

摘要

本发明提供一种已知多视激光点云配准初值进行自动全局优化的整体配准方法，其特征在于首先建立并详细推导了多视激光点云配准全局优化整体平差模型，通过估计点云的密度，自动检测所有具有一定重叠度的两视点云；然后利用K-D树搜索具有一定重叠度两视点云中的近似同名点，并将其作为观测值代入到全局优化平差模型中，通过迭代平差计算，同时获得多视激光点云各自最优的旋转平移变换参数，从而完成多视角三维激光点云的整体精确配准。本发明着重于提高多视角三维激光点云的整体配准精度，可以同时处理无序散乱的多视三维激光扫描点云，通过实际多视角三维激光点云数据进行配准实验，结果证明在保证配准效率的基础上，有效提高了整体配准的精度。

说明书

技术领域

本发明属于摄影测量与计算机视觉技术领域，具体涉及一种多视角三维激光点云全局优化整体配准方法。

背景技术

近年来，三维激光扫描测量技术发展迅速，在逆向工程、工业测量、文物数字化保护等方面得到了广泛的应用。在实际应用中，为了获取物体表面完整的三维点云需要对被测物体进行多角度扫描，进而需要将多视激光点云配准到统一的坐标系中，所以配准精度会直接影响物体最终的三维重构精度。因此对初始配准后的三维激光点云进行全局优化整体配准将具有十分重要的现实意义。

计算机视觉界的相关学者对点云配准领域的研究主要集中在两视点云之间的配准，大多都基于BESL P J等人提出的最邻近点迭代方法（iterative closest point，ICP），通过迭代选择对应点计算满足对应点之间的距离误差最小条件的旋转平移变换矩阵。在ICP算法的基础上，很多论文对最邻近点的方法进行了改进，如提出了point-point、point-to-plane、point-to-projection等方法搜索最邻近点，邹际祥采用K-D树加快了最邻近点的查找速度。此外，Johnson和Kang提出了基于彩色三维扫描数据的配准方法，主要在ICP算法中考虑三维扫描点的纹理色彩信息进行搜索最邻近点。路银北、钱鹏鹏等人提出了基于曲率的点云数据配准算法，并结合改进的ICP算法对点云进行精确配准。但以上这些算法都局限于两视点云之间的两两配准。

在多视三维激光点云整体配准领域的研究主要集中在依赖仪器的配准和半自动配准方面。张剑清提出一种激光扫描多视三维点云的全自动无缝镶嵌算法，应用闭合条件约束的整体平差模型，实现了激光扫描仪多视三维点云的全自动无缝镶嵌，但该方法只适用于特定硬件设备获取的360度闭合有序的多视三维点云，对于覆盖物体表面局部区域或散乱无序的多视点云全局优化不适用。周朗明提出一种针对旋转平台获取三维扫描点云数据的配准方法，能够实现将多视三维扫描数据自动配准到统一的坐标系中，配准精度与ICP配准或标志点配准精度相当。该方法自动化程度高，但需要借助旋转平台获取物体表面的三维点云数据，同时需要标定旋转平台与扫描仪之间的相对位置关系，因此适用性相对较低。刘军提出一种基于序列迭代的多视点云三维配准方法，该方法有效抑制了序列配准的累积误差，但是配准过程中人工操作比较多，效率低下。

发明内容

针对现有技术中存在的上述不足，本发明提供了一种已知多视激光点云配准初值进行自动全局优化的整体配准方法，实现了对初始配准后的三维激光点云进行自动全局优化整体配准，提高了物体表面三维模型的重构精度和效率。

为了解决上述技术问题，本发明采用了如下技术方案：

多视角三维激光点云全局优化整体配准方法，该方法包含如下步骤：

（1）建立并推导多视角三维激光点云全局优化整体平差模型；

（2）对物体表面进行多视角扫描，获取多个视角的三维点云，将其初步配准到统一的坐标系中，并对三维点云的密度D进行估计；

（3）遍历经过粗配准后的多视三维点云，自动检测所有具有一定重叠度的两视三维点云，并将点云序号保存至动态数组中；

（4）由步骤（3）可以检测出多视点云中所有具有一定重叠度的两视点云，然后利用K-D树搜索这些具有一定重叠度的两视点云中的近似同名点对，并将这些近似同名点对作为观测值代入到全局优化整体平差模型中，通过迭代平差计算，获得最小二乘意义下多视激光点云各自最优的旋转平移变换参数，从而完成多视角三维激光点云的整体精确配准。

为实现发明目的，所述的多视角三维激光点云全局优化整体配准方法，在步骤（1）中，对一个物体表面进行多视角扫描，共获取K个视角的三维点云，并且假定这K个视角的三维点云之间具有一定的重叠区域，全局优化的目的是确定旋转平移参数                                                ，使得整体配准误差最小，公式如下：

（1）

其中，分别表示第m个视角和第n个视角的点云，即多视点云的视角序号；K表示多视三维点云的数量，即共有K个视角的点云；表示第m个视角点云和第n个视角点云重叠区域中的近似同名点对的数量；代表第m个视角点云和第n个视角点云中第i对近似同名点；分别表示将第m个视角的点云转换到基准坐标系下的旋转矩阵和平移向量，分别表示将第n个视角的点云转换到基准坐标系下的旋转矩阵和平移向量；

式（1）中，，

，将代入公式（1）中，得到：

（2）

将公式（2）简化后写成：      

（3）

假定将第一个视角的点云所在的坐标系作为基准坐标系，那么第一个视角点云的旋转平移参数为已知量，不参与平差迭代计算，即旋转矩阵为3×3的单位矩阵，平移向量为3×1的零向量。因此对初始配准后的点云进行全局优化的过程即是同时求解未知参数的过程，未知参数可用近似值加相应的改正数表示。利用泰勒公式对式（3）进行线性展开，得到线性化误差方程式如式（4）：

（4）

其中，是使用各未知数的近似值代入式（3）后计算得到的具有一定重叠度的两视点云中某一对近似同名点距离的平方值。对于多视点云重叠区域中的任一对近似同名点，均可列出如下误差方程：

 （5）

由于旋转矩阵是由三个旋转角的9个方向余弦值组成，结合式（2），经推导可以得到误差方程式中各偏导数的值。多视激光点云配准全局优化平差模型（式（5））为典型的间接平差模型，利用多视点云重叠区域中的近似同名点即可通过最小二乘法获得多视点云各自的旋转平移变换参数。

为实现发明目的，所述的多视角三维激光点云全局优化整体配准方法，在步骤（2）中，对三维点云密度D进行估计的具体方法是：

这里假定多视角三维点云是使用同一种扫描手段获取的，因此认为K个视角的点云密度基本相同，以其中一个视角点云为例来介绍点云密度估计的方法：如果点云数量较大，则可以通过间隔采样方式在点云中获取采样点；否则可以取点云中所有的点作为采样点。遍历采样点，通过K-D树搜索每个采样点在点云中的最邻近点，并计算两者之间的距离，最后计算所有采样点到各自最邻近点距离的平均值即为点云密度，其计算公式如下：

（6）

其中，n为采样点的数量。

为实现发明目的，所述的多视角三维激光点云全局优化整体配准方法，在步骤（3）中，计算两视点云重叠度的方法定义如下：

假设两视点云中的三维点的数量分别为m和n，遍历其中一个点云中的三维点，在另外一个点云中搜索与该三维点最邻近的点，如果这两点之间的距离小于一定阈值（阈值一般为3倍点云密度）时，则定义该两点为近似同名点。利用K-D树检测该两视点云中所有的近似同名点，并假定其数量为N，则该两视点云的重叠度W计算公式如下：

（7）。 

为实现发明目的，所述的多视角三维激光点云全局优化整体配准方法，在步骤（3）中，自动检测K视三维点云中所有具有一定重叠度的两视点云方法的具体检测步骤是：

①定义一个二维动态数组I，将第一维大小设置为K-1；

②从第2视角到第K视角点云中，检测与第1视角点云具有一定重叠度的三维点云，并将点云视角序号依次保存到I[0]中；

③从第3视角到第K视角点云中，检测与第2视角点云具有一定重叠度的三维点云，并将点云视角序号依次保存到I[1]中；

④依次类推，直到检测第K视角点云与第K-1视角点云是否具有一定重叠度，若有一定重叠度则将视角序号K保存到I[K-2]中。

为实现发明目的，所述的多视角三维激光点云全局优化整体配准方法，在步骤（4）中，采用K-D树搜索重叠区域的最邻近点对作为近似同名点对，代入到平差模型中整体解算多视点云之间的坐标系变换参数的具体步骤为：

①假定将第一个视角的点云所在的坐标系作为基准坐标系，则K视点云全局优化配准的过程就是求解未知数的过程；

②第一次迭代平差，将未知数的初始近似值设定为0；

③经过第一次平差后，得到未知数的改正数，分别加上对应未知数的近似值后作为下一次迭代新的近似值，经过循环迭代，直到迭代次数达到给定的最大值或未知数改正数小于给定限差后，整个平差过程结束。

本发明与现有技术相比，具有以下优点：

（1）本发明介绍的这种已知多视激光点云配准初值进行自动全局优化的精确配准方法，详细推导了多视激光点云全局优化整体平差模型，给出了算法详细的实现步骤，获得了最小二乘意义下各视角点云模型的最优变换参数；

（2）相对于ICP两两精确配准方法，多视角激光点云全局优化整体配准方法能够自动地对散乱无序的多视扫描点云进行整体精确配准，配准精度较ICP算法有较大幅度地提高，同时减少了人工寻找具有重叠区域的两视点云的过程，配准效率也得到一定程度地提高。

附图说明

图1是具有重叠度的多视角点云覆盖范围分布图。

图2是对图1所示的多视角点云进行自动检测得到的重叠度动态数组。

图3是多视三维点云全局优化配准算法流程图。

图4是玩偶模型8个不同视角的三维点云数据。

图5是全局优化整体配准后的点云模型。

具体实施方式

下面对本技术发明进行详细说明，但是本发明的保护范围不局限于所述实施例。

多视角三维激光点云全局优化整体配准方法,该方法详细实现步骤如下：

（1）建立并推导多视角三维激光点云全局优化整体平差模型；

（2）对物体表面进行多视角扫描，获取多个视角的三维点云，将其初步配准到统一的坐标系中，并对三维点云的密度D进行估计；

（3）遍历经过粗配准后的多视三维点云，自动检测所有具有一定重叠度的两视三维点云，并将点云序号保存至动态数组中；

（4）由步骤（3）可以检测出多视点云中所有具有一定重叠度的两视点云，然后利用K-D树搜索这些具有一定重叠度的两视点云中的近似同名点对，并将这些近似同名点对作为观测值代入到全局优化整体平差模型中，通过迭代平差计算，获得最小二乘意义下多视激光点云各自最优的旋转平移变换参数，从而完成多视角三维激光点云的整体精确配准；

（5）将多视角三维激光点云全局优化整体配准方法与经典ICP算法相比较，证明本发明方法能够获取更高的配准精度。

多视角三维激光点云全局优化整体平差模型，具体的建立过程和推导步骤如下：

对一个物体表面进行多视角扫描，共获取K个视角的三维点云，并且假定这K个视角的三维点云之间具有一定的重叠区域，全局优化的目的是确定旋转平移参数，使得整体配准误差最小，公式如下：

（1）

其中，分别表示第m个视角和第n个视角的点云，即多视点云的视角序号；K表示多视三维点云的数量，即共有K个视角的点云；表示第m个视角点云和第n个视角点云重叠区域中的近似同名点对的数量；代表第m个视角点云和第n个视角点云中第i对近似同名点；分别表示将第m个视角的点云转换到基准坐标系下的旋转矩阵和平移向量，分别表示将第n个视角的点云转换到基准坐标系下的旋转矩阵和平移向量；

式（1）中，，

，将代入公式（1）中，得到：

   （2）

将公式（2）简化后写成：      

 （3）

假定将第一个视角的点云所在的坐标系作为基准坐标系，那么第一个视角点云的旋转平移参数为已知量，不参与平差迭代计算，即旋转矩阵为3×3的单位矩阵，平移向量为3×1的零向量。因此对初始配准后的点云进行全局优化的过程即是同时求解未知参数的过程，未知参数可用近似值加相应的改正数表示。利用泰勒公式对式（3）进行线性展开，得到线性化误差方程式如式（4）：

 （4）

其中，是使用各未知数的近似值代入式（3）后计算得到的具有一定重叠度的两视点云中某一对近似同名点距离的平方值。对于多视点云重叠区域中的任一对近似同名点，均可列出如下误差方程：

（5）

其中，

由于旋转矩阵是由三个旋转角的9个方向余弦值组成，结合式（2），经推导可以得到误差方程式中各偏导数的值。多视激光点云配准全局优化平差模型（式（5））为典型的间接平差模型，利用多视点云重叠区域中的近似同名点即可通过最小二乘法获得多视点云各自的旋转平移变换参数。

对三维点云密度D进行估计的具体方法是：

这里假定多视角三维点云是使用同一种扫描手段获取的，因此认为K个视角的点云密度基本相同，以其中一个视角点云为例来介绍点云密度估计的方法：如果点云数量较大，则可以通过间隔采样方式在点云中获取采样点；否则可以取点云中所有的点作为采样点。遍历采样点，通过K-D树搜索每个采样点在点云中的最邻近点，并计算两者之间的距离，最后计算所有采样点到各自最邻近点距离的平均值即为点云密度，其计算公式如下：

（6）

其中，n为采样点的数量。

计算两视点云重叠度的方法定义如下：

假设两视点云中的三维点的数量分别为m和n，遍历其中一个点云中的三维点，在另外一个点云中搜索与该三维点最邻近的点，如果这两点之间的距离小于一定阈值（阈值一般为3倍点云密度）时，则定义该两点为近似同名点。利用K-D树检测该两视点云中所有的近似同名点，并假定其数量为N，则该两视点云的重叠度W计算公式如下：

（7） 

考虑到重叠度对配准精度的影响，定义当W>0.2时，则判断该两视点云具有一定的重叠度。根据以上的描述，对于图1所示的多视角三维点云，自动检测得到的重叠度动态数组见图2。从重叠度动态数组中可以看出，与点云1具有一定重叠度的是点云2和点云4；与点云2具有一定重叠度的是点云3和点云4；与点云3具有一定重叠度的是点云4。实际上图1中显示的点云3和点云1亦有部分重叠区域，但由于重叠度W<0.2，不满足上述提出的具有一定重叠度的条件，所以判断点云3与点云1不具有一定的重叠度。

自动检测所有具有一定重叠度的两视三维点云，并将点云序号保存至动态数组中，具体检测步骤如下：

①定义一个二维动态数组I，将第一维大小设置为K-1；

②从第2视角到第K视角点云中，检测与第1视角点云具有一定重叠度的三维点云，并将点云视角序号依次保存到I[0]中；

③从第3视角到第K视角点云中，检测与第2视角点云具有一定重叠度的三维点云，并将点云视角序号依次保存到I[1]中；

④依次类推，直到检测第K视角点云与第K-1视角点云是否具有一定重叠度，若有一定重叠度则将视角序号K保存到I[K-2]中。

 采用K-D树搜索重叠区域的最邻近点对作为近似同名点对，代入到平差模型中整体解算多视点云之间的坐标系变换参数的具体步骤为：

①假定将第一个视角的点云所在的坐标系作为基准坐标系，则K视点云全局优化配准的过程就是求解未知数的过程；

②第一次迭代平差，将未知数的初始近似值设定为0；

③经过第一次平差后，得到未知数的改正数，分别加上对应未知数的近似值后作为下一次迭代新的近似值，经过循环迭代，直到迭代次数达到给定的最大值或未知数改正数小于给定限差后，整个平差过程结束。

步骤（4）中，有以下几点需要指出的是：

①在平差过程中，对于具有一定重叠度的两视点云中近似同名点对的确定方法是：考虑到多视点云初始配准结果的精度有限，因此在前三次迭代中若两最邻近点距离小于3D（3倍点云密度）时就认为是近似同名点；经过三次迭代平差后，多视点云的配准结果整体得到优化，因此在第三次以后的迭代中，两个最邻近点之间距离满足小于nD（1<n<2）的条件，即认为是近似同名点。其中，n为经验值，值的大小对应着搜索得到的近似同名点数量的多少，n一般取值为1.5；

②由于每次循环迭代后，多视点云都会得到各自新的旋转平移参数，因此每次迭代平差过程中的观测值（即两视点云中的近似同名点）都需要重新进行计算获取，从而造成计算量较大；另外近似同名点对数量越多即误差方程个数越多，误差方程规模也会越大。因此为了适当降低计算量以及误差方程的规模，采取的方法是：对于具有一定重叠度的两视点云，在其中一个点云中通过间隔采样点，利用K-D树在另一个点云中搜索该采样点的近似同名点。间隔采样的程度根据两视点云的重叠度和点的数量来确定；

③迭代终止条件的确定：迭代次数设定的最大值为50次，旋转角参数的改正数限差设定为0.1′(3×10^-5弧度)，平移参数的改正数限差设定为D/5。

综上所述，本发明提出的多视角三维点云全局优化配准方法的具体实现流程参见图3。

本发明利用激光扫描仪对一个玩偶模型进行无序扫描共获得8个视角的三维扫描数据，参见图4。对扫描数据进行了两组实验，并对结果进行比较分析。

第一组试验，对具有一定重叠区域的两视点云手动选取三对及以上同名点，计算初始刚体变换参数，然后利用ICP算法实现两视点云的精确配准，通过这种两两配准的方法将所有视角扫描数据变换到同一个坐标系中；第二组试验，应用本发明提出的多视点云全局优化配准方法，进行整体平差后解求出各视角三维点云的变换参数，再根据解算出的变换参数将所有扫描数据统一到同一个坐标系中，全局优化配准后的点云模型参见图5。

为了定量比较这两组试验结果，通过计算多视点云重叠区域的最邻近点对距离平方和的平均值的平方根，作为整体配准后的距离中误差用于评估多视点云间的配准精度。假设近似同名点对用和 表示，近似同名点的总数量用n表示，则配准距离中误差的计算公式如下：

 （8）

根据距离中误差计算公式，第一组试验得到的配准中误差为0.41mm，第二组试验得到的配准中误差为0.18mm；经计算得到玩偶三维扫描数据的点云密度为0.28mm。试验结果表明，全局优化整体配准精度要明显优于使用ICP算法进行两两点云配准的精度，另外从试验结果还可以看出，全局优化配准中误差近似为0.6倍点云密度，因此全局优化整体配准的精度比较理想。

在算法执行效率方面，为了使本发明提出的整体配准算法和ICP算法的迭代收敛情况具有可比性，两种算法均采用点与点间欧氏距离最近来搜索近似同名点，同时在两种算法中设置相同的迭代终止条件。本发明方法对8个视角的三维扫描数据进行了全局优化整体配准，共迭代13次程序收敛，采用ICP两两精确配准算法共迭代71次完成配准（经过7次两两配准总共的迭代次数）。

本发明方法与ICP算法在全局配准过程中的各项参数如表1所示；

表1：

 

从以上分析可以看出，本发明提出的多视角三维激光点云整体配准算法相对于ICP两两精确配准算法，其优点在于能够自动地对散乱无序的多视扫描点云进行一次性整体精确配准，同时减少了人工搜寻具有重叠区域的两视点云的过程，配准精度和效率较ICP两两精确配准算法有较大的提高。

最后说明的是，以上实施例仅用以说明本发明的的技术方案而非限制，尽管参照较佳实施例对本发明进行详细说明，本领域的普通技术人员应该理解，可以对本发明的技术方案进行修改或者同等替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围之中。