结合八叉树结构对ICP算法在点云配准方面的改进

吕明慧

（山东科技大学 山东 青岛 266590）

1 引言

随着三维激光扫描技术的广泛应用，三维激光扫描仪和它所获取的点云数据的处理方法也在飞速发展。近些年来，三维激光扫描仪的技术已经初步成熟，获取被测地物的点云数据的精度和密度都达到了现阶段社会发展的要求，但大量的点云数据处理是我们面临的一大难题。点云数据处理的难度主要体现在点云数据的拼接与配准方面，本文则主要介绍一种在原有ICP算法的基础上，结合八叉树结构的点云配准方法。

2 八叉树

2.1 八叉树结构

八叉树结构是由四叉树结构推广到三维空间而形成的一种三维数据结构。主要思想就是将一个空间三维模型用一个正方体进行包围，按照三维直角坐标的方式进行八等份切割，将每一个切割所得到的结构体存储在其下属的小区域内，对于每个区域都用相同的方式再向下分割，直到子区域内为空或达到某一规定条件。图1为八叉树结构示意图。

图1

在应用八叉树结构进行数据组织时，通常利用Morton码作为一种较好的编码方式，还可以应用改进后的Morton码[1]，一种线性八叉树地址码进行编码。

2.2 八叉树应用于点云配准

通常的点云配准方式为利用ICP算法进行配准，但ICP算法在有一个较好的初值时能得到比较理想的配准结果，否则此算法会含有较大的误差。而八叉树结构则可以较好的解决这个问题。基本思路为在两个点集中分别以八叉树结构组织数据，则每一个根节点或是叶节点都有其相应的属性信息，包括坐标数据和体积数据。我们的目标就是找出两个点集中最为密合的部分，即在空间位置上相差最小甚至是完全相同的两个点，那么就可以利用八叉树结构快速而精确地找到这两个点。

具体方法为自顶向下分别对两个点集的同层根节点进行比较，比较每个相对应的根节点，根据根节点内的坐标信息求取其对应的重心坐标，以两个完全平方和相差最小的重心坐标所在的根节点为目标点进行下一层根节点的比较，用同样的方法求取重心坐标进行比较，以此类推，依次向下总能求取出两个相对应的点或点集。用这种方法求解时，为了避免不必要的时间和精度浪费可以设置两个重心点的相对精度初步得到两个点集，后续的精度提高可以再利用迭代进行调整。这种得到最邻近点或点集的方式不仅可以提高精度，还能够减少处理时间，相比于以往的遍历每个点的方式所提高的处理速度是指数级的。

3 应用八叉树结构对ICP算法的改进

3.1 ICP算法

经典的ICP算法的基本原理很简单，就是要求两个点云数据之间的变换关系，实质上的不同的坐标系统转换到相同坐标系统下的计算。坐标系统的转换一般是利用七参数法，三个平移参数，三个旋转参数和一个比例缩放因子。而在点云数据中，我们默认比例缩放因子为1，即将问题转化为求解一个旋转矩阵和一个平移向量。它们的解算方法即为ICP迭代最近点算法[2-3]。有很多对于此种算法的改进方法，大多是利用去除误差较大的点对或是给不同的约束条件分配权重来减小误差，对于ICP算法来说，耗费时间最长的部分就是对应点的计算，接下来将介绍在八叉树结构的参与下，以迭代方式不断地改进点集的重心坐标来快速精确定位两个空间位置最邻近点甚至是重合点。

3.2 应用八叉树结构的ICP算法

基于ICP算法的基本原理[4]，有以下的解算步骤：（1）根据参考点集中的点坐标，在待配准点集上搜索相应最近点点集；（2）计算两个点集的重心位置坐标，并进行点集中心化生成新的点集；（3）由新的点集计算正定矩阵N，并计算N的最大特征值及其最大特征向量；（4）由于最大特征向量等价于残差平方和最小时的旋转四元数，将四元数转换为旋转矩阵R；（5）在旋转矩阵R被确定后，由平移向量t仅仅是两个点集的重心差异，可以通过两个坐标系中的重心点和旋转矩阵确定；（6）由参考点集计算旋转连续两次距离平方和之差绝对值作为迭代判断数值；（7）当此数值满足一定精度要求时，ICP配准算法就停止迭代，否则重复（1）至（6）步，直到满足条件后停止迭代。

八叉树结构可以应用于一、二两个解算步骤，在搜索最近点点集时，不采用遍历搜索，而是进行前文所说的八叉树结构搜索提高搜索速度。这个点集可以作为配准的最初点集来使用，有了最初的相对精度较高的起算数据，就可以得到比较好的配准结果了。由这个点集继续进行ICP算法的后续计算直到计算出第一个旋转矩阵和平移参数。由于有很多次的迭代，每次迭代都是用八叉树结构进行查找而不是遍历每一个点进行欧氏距离的解算，因此它所提高的工作速度是巨大的。接下来进行迭代计算，下面的解算步骤也是八叉树起到改进作用的主要部分。

由第一次计算的旋转矩阵和平移参数解算出待配准点集在参考点集坐标系下的坐标值，计算出重心坐标，根据重心坐标取一定半径的球内的临近点形成新的点集，对新的点集数据重新按照八叉树结构进行组织，再与参考点集进行同层次根节点的三维重心坐标差平方和的比较，找出最邻近的两个坐标点。这里找出的是两个相对应的坐标点，而不是两个点集，由于不断地进行迭代，所查找的点集的重心位置也在不断改变，因此灵活性有了很大的提升，避免了有更加匹配的点对而无法发现的情况的发生。经过一定次数的迭代，利用八叉树结构总是能查找到一对最为临近甚至是空间位置相同的对应点，此时的迭代条件可以是两对应点对的相对精度。这样就完成了一个点对的查找。根据实际扫描情况，一定是有多个配准特征可供选择，那么只要在两个点云数据中完成上述三个对应点对的查找就可以解算出不同坐标系的转换参数，即完成点云数据的配准工作。若是对更多的点集进行比较计算，则可以求解出很多相应的点对，选择其中误差最小的几对数据进行解算即可进一步提高配准精度。

4 结语

这种结合八叉树的点云配准算法与经典ICP算法的本质上的不同在于它是根据解算查找出的对应点对来精确计算最终的旋转矩阵和平移参数，而不是直接用点集进行解算。它的优势体现在两个方面，一是在每一次迭代计算中都提高了运算速度，二是由重心位置不断改变的空间球状点集利用八叉树结构一步步找出最邻近点对，提高了配准精度。八叉树结构特殊的数据组织方式和查找方式是提高点云配准速度和精度的关键。