PCL中八叉树理论

建立空间索引在点云数据处理中已被广泛的应用，常见的空间索引一般是自顶向下逐级划分空间的各种空间索引结构，比较有代表性的包括BSP树，KD树，R树，CELL树，八叉树等索引结构，其中就属KD树和八叉树在3D点云中的应用最为广泛，KD树的理论基础在上一篇推文中已经讲解，那么我们知道PCL库中已经对KD树和八叉树的数据结构的建立和索引的方法进行的实现，以方便在此基础上的其他点云的处理操作。

简介

八叉树结构是由 Hunter 博士于1978年首次提出的一种数据模型。八叉树结构通过对三维空间的几何实体进行体元剖分，每个体元具有相同的时间和空间复杂度，通过循环递归的划分方法对大小为( 2 nx 2 n x 2 n ) 的三维空间的几何对象进行剖分，从而构成一个具有根节点的方向图。在八叉树结构中如果被划分的体元具有相同的属性，则该体元构成一个叶节点；否则继续对该体元剖分成8个子立方体，依次递剖分，对于( 2 n x 2 n x 2 n ) 大小的空间对象，最多剖分 n 次，如下图所示。

八叉树的存贮结构

八叉树有三种不同的存贮结构，分别是规则方式、线性方式以及一对八方式。相应的八叉树也分别称为规则八叉树、线性八叉树以及一对八式八叉树。不同的存贮结构的空间利用率及运算操作的方便性是不同的。分析表明，一对八式八叉树优点更多一些。

规则八叉树

规则八叉树的存贮结构用一个有九个字段的记录来表示树中的每个结点。其中一个字段用来描述该结点的特性(在目前假定下，只要描述它是灰、白、黑三类结点中哪一类即可)，其余的八个字段用来作为存放指向其八个子结点的指针。这是最普遍使用的表示树形数据的存贮结构方式。

规则八叉树缺陷较多，最大的问题是指针占用了大量的空间。假定每个指针要用两个字节表示，而结点的描述用一个字节，那么存放指针要占总的存贮量的94％。因此，这种方法虽然十分自然，容易掌握，但在存贮空间的使用率方面不很理想。

线性八叉树

线性八叉树注重考虑如何提高空间利用率。用某一预先确定的次序遍历八叉树(例如以深度第一的方式)，将八叉树转换成一个线性表，表的每个元素与一个结点相对应。对于结点的描述可以丰富一点，例如用适当的方式来说明它是否为叶结点，如果不是叶结点时还可用其八个子结点值的平均值作为非叶结点的值等等。这样，可以在内存中以紧凑的方式来表示线性表，可以不用指针或者仅用一个指针表示即可。

  一对八方式

一个非叶结点有八个子结点，为了确定起见，将它们分别标记为0，1，2，3，4，5，6，7。从上面的介绍可以看到，如果一个记录与一个结点相对应，那么在这个记录中描述的是这个结点的八个子结点的特性值。而指针给出的则是该八个子结点所对应记录的存放处，而且还隐含地假定了这些子结点记录存放的次序。也就是说，即使某个记录是不必要的(例如，该结点已是叶结点)，那么相应的存贮位置也必须空闲在那里，以保证不会错误地存取到其它同辈结点的记录。这样当然会有一定的浪费，除非它是完全的八叉树，即所有的叶结点均在同一层次出现，而在该层次之上的所有层中的结点均为非叶结点。

实现Octree的步骤

(1). 设定最大递归深度

(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体

(3). 依序将单位元元素丢入能被包含且没有子节点的立方体

(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八个子立方体

(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目还是一样，会造成无穷切割的情形。

(6). 重复3，直到达到最大递归深度。

PCL中octree模块以及类的介绍

PCL中octree库提供了octree的数据结构，利用FLANN进行快速领域检索，领域检索在匹配，特征描述子计算，领域特征提取中是非常基础的核心操作。octree模块利用了十几个类实现了利用octree数据结构对点云的高效管理和检索，以及相应的一些空间处理的算法，比如压缩，空间变化检测等

PCL中octree 在压缩点云数据方面应用

点云由海量的数据集组成，这些数据通过距离、颜色、法线等附加信息来描述空间三维点。此外，点云能以非常高的速率被创建出来，因此需要占用相当大的存储资源，一旦点云需要存储或者通过速率受限制的通信信道进行传输，提供针对这种数据的压缩方法就变得十分有用。PCL库提供了点云压缩功能，它允许编码压缩所有类型的点云，包括无序点云，它具有无参考点和变化的点尺寸、分辨率、分布密度和点顺序等结构特征。而且，底层的octree数据结构允许从几个输入源高效地合并点云数据。

point_cloud_compression.cpp解释单个点云和点云数据流是如何高效压缩的实例。有兴趣的小伙伴可以去运行尝试一下。

以下图示为带有RGB纹理信息的实时可视化结果，缩放可视化结果看到经过压缩后点云进行了重采样，纹理信息有所丢失，但数据量有所减小，在实际应用中需要折中取舍

同时在压缩和解压缩的过程中  因为设置compressedData为true所以在标准输出上打印处压缩率帧数等信息：

八叉树和k-d树比较

八叉树算法的算法实现简单，但大数据量点云数据下，比较困难的是最小粒度（叶节点）的确定，粒度较大时，有的节点数据量可能仍比较大，后续查询效率仍比较低，反之，粒度较小，八叉树的深度增加，需要的内存空间也比较大（每个非叶子节点需要八个指针），效率也降低。而等分的划分依据，使得在数据重心有偏斜的情况下，受划分深度限制，其效率不是太高。

k-d在邻域查找上比较有优势，但在大数据量的情况下，若划分粒度较小时，建树的开销也较大，但比八叉树灵活些。在小数据量的情况下，其搜索效率比较高，但在数据量增大的情况下，其效率会有一定的下降，一般是线性上升的规律。

也有将八叉树和k-d树结合起来的应用，应用八叉树进行大粒度的划分和查找，而后使用k-d树进行细分，效率会有一定的提升，但其搜索效率变化也与数据量的变化有一个线性关系。

拓展延伸

研究SLAM的可能还知道OctoMap也是基于八叉树的原理，我们知道一个PCD文件的点云一般都比较大，所以存储点云需要大量的存储空间，而读取文件也需要较长时间去加载进来，所以一般我们在处理点云时会进行一次滤波预处理，以减少数据量的运算，而且我们知道点云在重叠区域的处理并不够好，会出现阴影。以及点云只能展示物体的三维点信息，难以用于导航处理。所以这里就出现了OCtoMap，这是一种高效的可以很好的压缩点云节省存储空间，可实时更新地图，可设置分辨率的八叉树地图。

当分辨率较高时，方块很小；分辨率较低时，方块很大。每个方块表示该格被占据的概率。因此你可以查询某个方块或点“是否可以通过”，从而实现不同层次的导航。简而言之，环境较大时采用较低分辨率，而较精细的导航可采用较高分辨率。我们是可以直接将一个点云的PCD文件转换到OCtoMap地图的形式的。有兴趣的小伙伴可以尝试一下。

octomap的网页见：https://octomap.github.io

github源码在：https://github.com/OctoMap/octomap

ROS下的安装方式：http://wiki.ros.org/octomap

参考文献：

[1]. OctoMap: An efficient probabilistic 3D mapping framework based on octrees, Hornung, Armin and Wurm, Kai M and Bennewitz, Maren and Stachniss, Cyrill and Burgard, Wolfram, Autonomous Robots, 2013.

[2]. OctoMap: A probabilistic, flexible, and compact 3D map representation for robotic systems, Wurm, Kai M and Hornung, Armin and Bennewitz, Maren and Stachniss, Cyrill and Burgard, Wolfram, ICRA 2010.