八叉树索引的三维点云数据压缩算法
摘 要：针对现有的三维点云简化算法普遍存在运行效率较低、内存消耗大、处理时间过长等问题，该文利用八叉树索引的速度优势和点云数据空间分割的逻辑结构，并结合三维点云网格简化算法高效的优势，提出一种基于八叉树索引的三维点云简化算法。该算法基本满足点云简化的理想标准，计算快速、运行时间短。利用实测大雁塔数据对各种三维点云压缩算法进行比较，结果表明该文提出的新算法对点云数据的压缩简化效率和压缩率较现有算法均有较大提高。
随着科技进步，三维激光扫描技术的诞生和发展被称为“继ＧＰＳ技术之后测绘领域的又一次技术革命”。三维激光扫描技术能够快速、精确的获取建筑物表面大量高精度的三维点云数据，三维激光扫描技术在建筑物建模、文物保护、逆向工程中得到广泛的应用。海量三维点云数据对建筑物模型、文物古迹的特征表达具有重要意义，同时三维激光点云数据的海量特性，为点云数据的存储、处理、传输与显示带来了挑战。在一些情况下，高密度的点云数据并不是必须的，如一般建筑物建模、非精细模型建模等。高密度的点云对后续模型建模的处理速度具有重大影响，甚至会降低建筑物模型的建模精度。因此，在实际的应用中，特别是建筑物建模过程中需要对三维点云数据进行一定的简化，提取对模型表达更有用的信息，达到三维点云的数据量与模型精度相适应。目前，国内点云数据简化的主流方法主要有３种：基于网格拓扑信息的简化、基于曲面拟合的简化和直接作用于三维点集的简化。
基于网格拓扑信息的简化方法包括顶点聚类法、迭代法等，该类简化方法一般步骤是首先为原始采样点集构建网络拓扑信息，然后为每个采样点分配一个误差，在网络拓扑的基础上根据每个采样点对网格面的重要性进行简化。该方法简化效果较好，但是需要构造和维护庞大的拓扑信息，计算内存消耗大，效率比较低。
基于曲面拟合的简化方法一般根据采样点集拟合一个曲面，然后在该曲面上根据某种规则（如点的曲率、点的法向量变化、距离权重等）进行重采样，采样后的点通常不再是原始的点集合。该方法得到的简化模型精度高，但是由于需要求取采样点的隐式表达式，重建复杂的点云曲面模型，所以简化速度非常慢。
直接作用于三维点集合的简化算法主要包括包围盒法、随机采样法、网格法等。由于该方法直接对三维点云数据进行简化，不需要建立任何拓扑关系与曲面模型。该方法操作简单，但需要借助某些数据结构来获取临近信息，集合一定的邻域信息进行简化。该算法原理简单，对内存要求不高，实现过程相对简单。但是对某些高精度模型的简化效果不理想，容易丢失特征信息，如文物保护、人体精细特征提取等。
通过以上对比可以看出，现阶段对海量三维点云的简化算法普遍存在一个致命的缺点，即对海量三维点云的处理能力不足，运行效率较低、内存消耗大、处理时间过长。理想的三维点云简化结果应该是用尽可能少的点云数据对模型特征尽可能精细的表达，并且处理的过程是快速高效的。目前还没有一个很好的算法能满足以上要求。
本文基于八叉树索引对三维点云数据简化进行研究，利用八叉树索引的速度优势和点云数据空间分割的逻辑结构，结合三维点云网格简化算法高效的优势，提出基于八叉树索引的三维点云简化算法，该算法基本满足点云简化的理想标准，并且计算快速、运行时间短。
八叉树结构（Ｏｃｔｒｅｅ）是由四叉树结构（Ｑｕａｄｔｒｅｅ）推广到三维空间而形成的一种三维栅格数据结构。八叉树的特点是空间逻辑结构简单，便于组织、分析和处理，不足的是数据量大、存储空间占用较大。本文首先基于八叉树建立三维点云数据的索引，充分利用八叉树空间分割的逻辑结构特点和快速索引的能力，结合三维点集的包围盒简化算法，在保证点云质量的前提下，实现三维点云的快速、高效的简化。
八叉树来表示三维形体是由Ｈｕｎｔｅｒ博士首次提出，八叉树被认为是四叉树在三维空间的推广或者三维形体阵列表示形体方法的一种改进。八叉树是一种利用对空间结构进行划分建立索引的一种方法。用八叉树来管理三维点云的基本思想是，首先根据所有三维点云的外包络立方体建立八叉树的根节点。在立方体进行剖分的过程中将父节点中的三维点云根据位置进行剖分，剖分到相应的叶子节点中，完成三维点云数据的剖分与索引的建立。对所有节点以及所包含的三维点集不断进行递归剖分，当某节点（立方体）的大小小于规定的阈值或者该节点（立方体）内部的三维点数目少于规定的最小立方体所包含点数目时停止剖分，该节点成为整个八叉树的叶子节点。
本文在八叉树剖分的过程中设置叶节点大小的阈值和叶节点包含点云数目的阈值，在节点剖分的过程中满足以上任何一个阈值条件即停止剖分。叶节点大小阈值的设定能够及时停止节点的剖分，节点点云数目阈值的设定能够防止节点不合理的剖分。综合这两个阈值条件能够建立一个合理、高效的最优化八叉树索引。八叉树的节点设计根据不同的结构进行不同的设计，八叉树的叶子节点除了存储一般的节点信息之外，还需要存储三维点集。为了八叉树索引建立的方便，一般节点需要存储所包含的孩子节点的信息，但不需要存储具体的三维点集数据。因此，为了节省存储空间叶子节点与一般节点的结构不同。首先定义叶子节点与一般节点的抽象父类，存储叶子节点与一般节点的公共信息。然后定义一般节点和叶子节点的结构。
三维网格简化算法是根据三维点集的坐标范围将它包围在一个立方体内，立方体的边长为三维数据点坐标差的最大值，在最小网格内根据所包含的数据点，利用平均、加权平均、距离权重或者提取中心点的方法选取部分特征点代替立方体网格内全部的数据点，这样就可以达到精简的目的。三维点集简化的精度主要由立方体网格的大小决定，立方体网格越小简化的精度越高。同时采用不同的简化方法对三维点集的简化精度也有一定的影响，本文采用平均点距简化算法、中心点提取简化算法和间隔取点法对三维点云进行简化研究。
平均点距简化算法的核心思想是在一定空间内点云的密度越大，则该空间内点与点之间的距离就越小。因此可以通过点与点之间的平均距离判断点云密度的大小，点的平均点距越小，点云的密度就越大，反之点云的密度就越小。根据点云密度的大小选择需要删除的点的数目。该方法的优点是对于平缓特征较少的地区，简化速度较快易于实现。但是对于特征信息复杂，如曲率变化较大区域，容易丢失特征信息。中心点提取算法同样也是包围盒立方体提取算法的一种，当立方体足够小时，距离中心点最近的点能够取代立方体内的点集，完成对立方体内点集的压缩。该方法算法简单计算速度快，易于实现，对于均匀分布的点云简化效果较好。但是由于立方体栅格大小设置的随意性，导致点云简化的精度无法保证，在点密度大的区域容易丢失细节信息。
间隔取点法是在平均点距简化算法的基础上发展而来的，平均点距简化算法根据点的平均距离按比例去除平均点距较小的点，但是对于分布比较均匀的点云，平均点距算法容易造成点云数据出现孔洞的情况。间隔取点简化算法主要针对分布比较均匀的点云的简化，将点集内的各个点的平均点距进行排序，然后进行间隔取点，完成数据的简化。
间隔取点简化算法是平均点距简化算法的进一步发展，针对均匀分布的点云数据具有很好的简化效果，算法简单易行，效率高。但是对于散乱分布的点云数据简化效果不理想，不能有效去除噪声点。
对于海量的三维点云数据简化，本文提出了一种结合传统的网格简化算法的八叉树索引简化方法，本文的基于八叉树索引的简化算法能够提高算法的效率、降低执行时间。同时八叉树的逻辑结构能够很好地与网格简化算法相结合。另一方面，海量三维点云数据八叉树索引的建立，对三维点云数据的组织、管理以及分层细节显示具有重要的意义，对于后续点云数据的建模同样具有重要意义。
尽管基于八叉树索引的网格简化算法在海量点云数据的压缩简化方面具有重要优势，但是对于一些特征复杂的点云数据压缩容易丢失细节特征，在点云细节特征提取方面采用曲面拟合的方法通过曲率、法向量变化等特征进行提取的方法具有无可比拟的优势，但该方法需要快速拟合曲面、查找点的邻域信息。基于八叉树索引的结构在查找点的领域方面存在不足，后续将八叉树与ＫＤ树等具有邻域特征信息的数据组织结构相结合，使点云压缩算法进一步改进为重心进行研究。
引用格式：姚顽强，郑俊良，陈鹏，等．八叉树索引的三维点云数据压缩算法［Ｊ］．测绘科学，２０１６，４１（７）：１８-２２．
联系我们