基于嵌套八叉树的大规模点云数据组织方法

摘要

本发明涉及一种基于嵌套八叉树的大规模点云数据组织方法，所述方法对点云数据进行改进嵌套八叉树的构建：首先构建出外部八叉树，在外部八叉树的节点内嵌套网格索引结构；其次，把点云添加到网格中，保证网格内的点云数据满足最小点间距的这一条件；最后，八叉树索引文件被分割为级别更小的文件。本发明对嵌套八叉树进行了改进，提高了点的编辑效率。构建过程中满足最小点间距的这一条件保证了八叉树的相邻层之间的点云分辨率呈相同的倍数关系，渲染点云时，点大小根据当前节点的点云分辨率自动调节，提高了大规模点云实时可视化的渲染质量。

说明书

技术领域

本发明涉及三维激光点云数据处理技术领域，具体涉及一种基于嵌套八叉树的大规模点云数据组织方法。

背景技术

三维激光扫描技术是三维空间快速获取信息的主要手段之一，被广泛应用在地理信息系统、城市规划建设等众多领域。通过该技术采集得到的三维激光点云数据是三维地理信息空间重要的数据来源，对这些重要数据的高效组织，是后期进行三维重建和可视化研究的关键也是当前的研究热点之一。

目前，国内外学者针对空间数据的组织进行了大量的研究工作，其中，广泛应用的组织策略主要有格网索引、四叉树索引、八叉树索引、KD树索引、R树及其变种树索引等。海量点云的空间形态千差万别，数据量巨大，单纯使用一种索引模型往往难以进行高效管理，为了充分发挥不同索引的优势，多数学者将重心放在了两种及以上索引的混合索引模型的研究。

嵌套八叉树由外部八叉树和内部八叉树组成。外部八叉树定义了遍历的索引结构，内部八叉树由点云数据构成，存在于外部八叉树的节点内。图2表示了一个全填满的嵌套二叉树（嵌套八叉树的简单版本）的实例，其由外部索引节点以及每个节点存放的二叉树构成。外部二叉树（Outer bintree）由方形框表示，每个外部二叉树的节点内都存放一个由圆形表示的内部二叉树。每个内部二叉树的根节点和其所在的外部二叉树节点包围盒相同。点云数据保存在所有的内部二叉树中。但是使用这种方法组织的点云，在实际渲染时存在几个问题：第一，由于每次执行点的删除或者增加都需要对内部八叉树进行重新构建，所以对点的编辑效率较低；二是：嵌套八叉树仅仅保证每个点落入其所属的节点内，但是相邻点之间的间隔距离可能很短，这会对下采样样本的质量造成影响；三是：当处理的点云过于庞大时，其所产生的单个索引文件大小可能会膨胀至百兆以上，加载这种索引文件会导致较长的加载时间。

发明内容

本发明的目的是提供一种基于嵌套八叉树的大规模点云数据组织方法，克服现有组织方法影响渲染效果的技术问题，以提高大规模点云数据实时可视化的渲染效果。

本发明所采用的技术方案为：

基于嵌套八叉树的大规模点云数据组织方法，其特征在于：

所述方法对点云数据进行改进嵌套八叉树的构建：首先构建出外部八叉树，在外部八叉树的节点内嵌套网格索引结构；其次，把点云添加到网格中，保证网格内的点云数据满足最小点间距的这一条件；最后，八叉树索引文件被分割为级别更小的文件。

所述方法包括以下步骤：

步骤1：统计所有原始点云的包围盒initBox，并将其扩展为立方体cubeBox；设置叶子节点的最大点数阈值maxPointNum，设置向磁盘刷新点云的点数阈值flushNum；

步骤2：构建外部八叉树的根节点，设置根节点的点云间隔阈值spacing = cubeBox对角线 / 250；

步骤3：遍历点云，依次从根节点开始添加；

步骤4：判断当前节点是否为叶子节点；如果是，则进入步骤5；否则，进入步骤6；

步骤5：当前节点为叶子节点，保存该点到当前节点的临时容器storage中；判断strosge容器中的点数是否大于叶子节点最大点数阈值maxPointNum；如果是，则创建该节点的8个子节点，子节点的间隔阈值spacing为当前节点spacing的一半，重新遍历storage中的点云，进入步骤4；否则进入步骤7；

步骤6：当前节点为非叶子节点，判断该点在网格中与其他点的检核距离是否大于当前节点的间隔阈值spacing；如果否，则传递该点给其子节点，进入步骤4；否则，保存该点到当前节点的容器cache中；

步骤7：判断当前遍历点数是否等于点云总点数，或者是否为flushNum的整数倍；如果否，则进入继续遍历点云，步骤4；否则，进入步骤8；

步骤8：从根节点开始，将所有节点的容器storage和cache中的点云刷新到磁盘；

步骤9：判断当前遍历点数是否等于点云总数；如果是，则结束遍历，否则，继续遍历点云，进入步骤4。

所述方法中，嵌套八叉树由外部八叉树和网格索引构成，外部八叉树定义了遍历的索引结构，网格索引由点云数据构建，存在于外部八叉树的节点内。

所述方法中，每层节点的点云分辨率由网格单元间点的间距阈值决定，间距阈值指定了点之间的最小距离；根节点的点间距是根据包围盒大小计算的，然后向下每层减半。

所述方法中，嵌套八叉树的索引文件由单一文件分割为多个级别更小的文件。

本发明具有以下优点：

本发明对嵌套八叉树进行了改进，提高了点的编辑效率。构建过程中满足最小点间距的这一条件保证了八叉树的相邻层之间的点云分辨率呈相同的倍数关系，渲染点云时，点大小根据当前节点的点云分辨率自动调节，提高了大规模点云实时可视化的渲染质量。

附图说明

图1 为本发明的总体流程图。

图2 为全填满的嵌套二叉树。

图3 为内部八叉树和网格索引。

图4 为分级索引文件。

具体实施方式

下面结合具体实施方式对本发明进行详细的说明。

本发明涉及一种基于嵌套八叉树的大规模点云数据组织方法，对点云数据进行改进嵌套八叉树的构建：首先构建出外部八叉树，在外部八叉树的节点内嵌套网格索引结构；其次，把点云添加到网格中，保证网格内的点云数据满足最小点间距的这一条件；最后，八叉树索引文件被分割为级别更小的文件。

所述方法具体包括以下步骤：

步骤1：统计所有原始点云的包围盒initBox，并将其扩展为立方体cubeBox；设置叶子节点的最大点数阈值maxPointNum，设置向磁盘刷新点云的点数阈值flushNum；

步骤2：构建外部八叉树的根节点，设置根节点的点云间隔阈值spacing = cubeBox对角线 / 250；

步骤3：遍历点云，依次从根节点开始添加；

步骤4：判断当前节点是否为叶子节点；如果是，则进入步骤5；否则，进入步骤6；

步骤5：当前节点为叶子节点，保存该点到当前节点的临时容器storage中；判断strosge容器中的点数是否大于叶子节点最大点数阈值maxPointNum；如果是，则创建该节点的8个子节点，子节点的间隔阈值spacing为当前节点spacing的一半，重新遍历storage中的点云，进入步骤4；否则进入步骤7；

步骤6：当前节点为非叶子节点，判断该点在网格中与其他点的检核距离是否大于当前节点的间隔阈值spacing；如果否，则传递该点给其子节点，进入步骤4；否则，保存该点到当前节点的容器cache中；

步骤7：判断当前遍历点数是否等于点云总点数，或者是否为flushNum的整数倍；如果否，则进入继续遍历点云，步骤4；否则，进入步骤8；

步骤8：从根节点开始，将所有节点的容器storage和cache中的点云刷新到磁盘；同时将八叉树索引文件被分割为级别更小的文件，刷新到硬盘；

步骤9：判断当前遍历点数是否等于点云总数；如果是，则结束遍历，否则，继续遍历点云，进入步骤4。

所述方法中，嵌套八叉树由外部八叉树和网格索引构成，外部八叉树定义了遍历的索引结构，网格索引由点云数据构建，存在于外部八叉树的节点内（对应步骤1、2、3、4）。

所述方法中，每层节点的点云分辨率由网格单元间点的间距阈值决定，间距阈值指定了点之间的最小距离；根节点的点间距是根据包围盒大小计算的，然后向下每层减半（对应步骤5、6）。

所述方法中，嵌套八叉树的索引文件由单一文件分割为多个级别更小的文件（对应步骤7、8）。

本发明对嵌套八叉树进行了三点改进，具体为：

1.使用网格代替嵌套八叉树中的内部八叉树，如图3所示。改进后的嵌套八叉树由外部八叉树和网格索引构成。外部八叉树定义了遍历的索引结构，网格索引由点云数据构建，存在于外部八叉树的节点内。这样每次执行点的删除或增加都是对网格索引进行操作，不必对网格进行重新构建，提高了点的编辑效率。

2.保证网格单元间点的间隔，提高点云下采样的质量。八叉树每层节点的点云分辨率是由网格单元间点的间距阈值决定的，它指定了点之间的最小距离。根节点的点间距是根据包围盒大小计算的，然后向下每层减半。例如，包围盒大小为200m*200m*200m的点云大小，根节点可是使用1m的点间距阈值。根节点将包含原始点云的最低分辨率版本，其中点与点之间的距离至少为1m。根节点的子节点间距阈值为0.5m，这将有效提高八叉树各层节点的点云分辨率。

3.将嵌套八叉树的索引文件由单一文件分割为多个级别更小的文件。由6400亿个点组成的点云转换产生了一个由13层和3800万索引文件的嵌套八叉树。仅八叉树的索引文件就需要190MB的磁盘空间。在渲染点云时，需要加载索引文件来确定必须机载哪些节点以及哪些节点是可见的，但是读取百兆大小的索引文件会导致较长的加载时间，降低点云的渲染效果。本发明将单个的索引文件分割为多个级别更小的文件（见图4），加载这种索引文件时，不必加载所有文件，只需要从根节点开始加载必要的索引文件即可，缩短了加载索引文件的时间。

本发明的内容不限于实施例所列举，本领域普通技术人员通过阅读本发明说明书而对本发明技术方案采取的任何等效的变换，均为本发明的权利要求所涵盖。