岩体点云数据的四叉树-八叉树联合索引优化

对于岩体点云数据这种含有大量噪点和无效数据且表面起伏不均的不规则形式，如果不进行有序的组织和索引，而直接采用最邻近搜索的算法计算每个点的法向量并在此基础上完成聚类分组，其计算效率将会非常低下。为了达到高效快速提取的目标，针对岩体点云数据复杂、散乱、海量的特点，需要对点云数据进行高效的组织与索引，通过分组、分区域地计算法向量和聚类，达到提高效率的目的。

一般情况下采用KNN算法、FDN算法以及TIN模型对整个点云数据进行子集的划分以达到分组处理的目的，根据点的密度、厚度、大小等特性设定点之间的“几何距离”作为阈值，每次选择一个点，计算它与其他点之间的距离，如果碰到距离小于该阈值的点，则将这些点作为初选点的邻居，这个过程将重复迭代直到没有点可选为止。这种计算每个点与其他点之间距离的过程在海量岩体点云数据中时间成本非常高，计算相当耗时。

图4-7　*.PTX文件结构示意图

由于单站内的点云数据都保留了点与点之间的原始拓扑关系，每个点除了自身的三维坐标（x、y、z）以外，其在单站扫描线内所处的位置可以用平面坐标的形式来表示，以此构成点云矩阵（u、v、x、y、z），u和v表示该点在单站点云矩阵中的平面坐标位置，（x、y、z）表示该点的三维坐标。

本书构建索引的思路是首先对原始点云矩阵数据进行四叉树编码，在此基础上，联合八叉树结构对配准后的点云进行管理，该方法既可以保留在一个扫描站内的点和点之间的邻接拓扑关系，又可以方便高效地进行空间查询和检索。由于*.PTX格式的点云数据按照一定的规则和顺序对原始扫描线进行了排列，因此采用规则空间八叉树与四叉树相结合的嵌套复合结构进行组织，可以在不影响三维点云数据空间查询检索效率的前提下，进一步提高岩体点云数据的法向量计算、平面分割和拟合的效率。

在点云数据分割和结构面平面拟合的过程中，涉及到大量的点云邻接关系的计算和存储等工作。由于本书所采用的数据来自于地面Lidar扫描仪，在激光扫描仪记录数据的过程中，对于一个扫描站来说，其点和点之间的邻接关系是已知的，而目前市面上大量的点云数据后处理软件在处理数据时并没有考虑该邻接关系，其原因主要是因为完成点云配准拼接以后，这种单站内的点与点之间的邻接关系会由于其他站点云数据的加入而发生改变，从而影响点云之间的正确邻接关系的计算。本书认为该拓扑关系是非常重要的数据信息，故从反映这种点之间的原始邻接关系信息为出发点，提出一种新的点云组织方法，在保持点云原始邻接关系的同时对点云数据进行高效的数据组织，使得下一步的法向量计算、聚类统计以及结构面提取等算法可以便捷地利用点与点之间原始的拓扑关系。具体组织策略如下：

对单站点云数据来说，完成与其他站的配准工作后，其坐标并不是马上发生改变，而是将其旋转、平移、缩放的变换矩阵进行单独存放，随后对该单站点云进行四叉树划分，粒度可以任意设置，本书中采用32×32的方格进行划分，同时计算每个四叉树叶节点在最终配准坐标系下的三维最小包围盒，经过计算后，单站点云数据被分成若干个带有三维最小包围盒，且点和点之间的邻接关系均完好保存的数据块。按照相同方式划分第二站点云。最终将多站数据所分成的所有点云数据块的三维最小包围盒进行合并，得到所有点云的三维最小包围盒之后，对整体点云进行八叉树组织。

岩体点云数据的四叉树-八叉树联合索引的示意图如图4-8所示，主要研究思路如下：

（1）读取导出的格式为*.PTX的扫描数据，将数据点按照扫描线的顺序进行排列，形成规则的点云矩阵形式。

（2）对第一步建立的格网点云选择合适的格网大小作为四叉树分割的叶节点。(www.xing528.com)

（3）通过配准矩阵来计算每个四叉树叶节点的三维最小包围盒，并对所有叶节点的最小包围盒进行合并操作，以得到最终整体点云的最小包围盒。

（4）对配准后整体点云的最小包围盒进行八叉树分割，并对之前的四叉树叶节点的最小包围盒与八叉树叶节点的最小包围盒进行求交运算，一旦两者有交集，则将该四叉树叶节点的编码存储入八叉树的叶节点。

本书中的四叉树-八叉树联合索引方法与传统的八叉树方法相比，有较为显著的区别，具体如下：

（1）在本书方法组织下，八叉树叶节点中存储的为四叉树编码，而不是直接的点云几何数据。

图4-8　四叉树-八叉树联合索引示意图

（2）本书方法中多个不同的八叉树叶节点可能包含同一个四叉树编码，即根据八叉树的叶节点来检索点云时，可能一次检索过程中会检索到多个重复的四叉树编码，传统八叉树的叶节点之内包含的点云一般不会出现重复的现象，之所以出现这样的情况，是由于从二维四叉树到三维八叉树的逆映射导致的冗余现象，但本质上并不影响检索和下一步的计算工作。

（3）本书的组织和索引不仅仅以空间为要素对点进行了聚类，而且保留了原始扫描数据中点和点之间的邻接拓扑关系，提高了后续的法向量计算和RANSAC算法的实现效率。

在本书的四叉树-八叉树联合索引方法的组织下，点云浏览时的空间检索效率与传统八叉树索引一致，而在岩体结构面提取时点云法向量计算的时间则会优于传统八叉树索引方法。该方法的应用，提高了点云数据的计算效率和岩体结构面提取效率，也为岩体结构面提取的可靠性提供了保障。