八叉树

3D物体建模在计算机辅助设计系统、医疗系统、机器人以及物体自动检测中扮演了越来越重要的角色。在这其中，八叉树是一种非常有效的储存数据的方法，尤其是对于像流形物体、点云图（point cloud）、体素（voxel）这样的稀疏化（sparse）数据来说，八叉树可以更好地展示数据的结构特性。

图1 八叉树结构的数据存储原理

图片来源：Figure 3, Riegler, G., Ulusoy, A. O., & Geiger, A. (2017, July). Octnet: Learning deep 3d representations at high resolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (Vol. 3).

首先我们看一下八叉树结构是如何有效储存稀疏化数据的。如图1左所示，我们把一个物体用最小的立方体包裹起来，然后我们对这个立方体使用八叉树的方式进行分割。因为是立体空间，所以每次划分都会把一个方块分为8个等分的子方块。如果某个子方块中没有包含这个物体，那么就把这个小方块储存的数据置为0，表示这是一个空的区域。反之，就置为1，并且继续分割下去，直到子方块的大小低于我们设定的某一预设值，或者达到预设的八叉树最大深度后停止分割。

如图1左所示，在第一次分割完成后，我们发现只有两个方块不是空的，于是这两个位置的数据被置为1，其他全为0，这就是我们在图1右第二行所看到的那串数字，然后我们继续分割值为1的子方块，直到达到最大深度后停止分割。图1右展示了八叉树最大深度为3时的分割情况。根据图1右，我们最终需要用73位（bit）来存储这种八叉树结构：1 01010000 00000000 01010000 01010000 0...。第一位的数字1代表了根节点是被分割的，第二位到第九位数字01010000表示了八叉树分割深度达到2时的子节点的分割情况，以此类推下去，深度为3时我们需要一共8*8=64位来储存相应的子节点的分割情况。

这样我们可以看到，我们一共需要1+8+64=73位（bit）来建立图1右所示的八叉树结构的索引，换言之，为了看清楚物体的形状，我们只需要找到这73个位置对应的数值就行了。而对于同样的分辨率的体素来说，因为是3维空间，每一点都有3个坐标，所以建立同样的空间我们需要多达8*8*8=512个坐标的索引，因此也就需要记录512个位置的数据。这种思想叫做位表示（Bit-representation），它能帮助我们更加高效地存储稀疏化数据。

通过上面的例子我们可以看出，八叉树数据结构可以更高效地储存数据，减少计算机内存和磁盘空间的占用，这一特点使得其在3D模型等稀疏化数据处理中逐渐受到学者的青睐。同时八叉树也是一种对数据的特征提取，因为八叉树一层一层不断划分子空间的过程也包含了物体的空间信息，这也给我们后续的数据进一步处理（比如说计算机视觉领域的物体分类等）提供了便利。

[描述来源：Meagher, D. J. (1980). Octree encoding: A new technique for the representation, manipulation and display of arbitrary 3-d objects by computer. Electrical and Systems Engineering Department Rensseiaer Polytechnic Institute Image Processing Laboratory.

URL：https://www.researchgate.net/publication/238720460_Octree_Encoding_A_New_Technique_for_the_Representation_Manipulation_and_Display_of_Arbitrary_3-D_Objects_by_Computer

描述来源：Riegler, G., Ulusoy, A. O., & Geiger, A. (2017, July). Octnet: Learning deep 3d representations at high resolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (Vol. 3).

URL：https://arxiv.org/abs/1611.05009]

发展历史

描述

自从上个世纪以来，物体建模就是一个非常热门的领域，它被广泛使用在计算机辅助设计（Computer-Aided Design, CAD）、医疗系统、机器人、有限元素建模（Finite element modeling）以及自动物体识别。在八叉树出现前，学者们提出过很多种建模方法。

1972年，Sidhu和Boute构建了四叉树（Quadtree），并将其应用在图像处理领域。

1974年，Freeman提出了一种2D编码方法，这种思想后来被学者们拓展至3D编码领域。

1978年，Gomez和Guzman提出了一种用三角形分割2D平面的方法，类似于八叉树的思想，如果一个三角形超过预设值，就会被分割成4个子三角形。

1979年，Baer等人发表综述论文《Geometric modelling: a survey》，研究了11种3D建模方法，这些建模方法都从边缘-面-顶点（edge-face-vertex）的角度出发，通过合并（union）、插值（intersection）和差分（difference）的方式构建3D模型。

1980年，Meagher提出了Octree数据结构，并且针对平移(translation)、调幅(scaling)、旋转(rotation)、合并(union)、插值(intersection)、差分(sections)操作提供了相应的算法，而且这些算法可以并行运算，使得八叉树结构可以通过大型计算机网络提高计算效率，今年来，随着计算机CPU和GPU硬件的提升，并行已经成为现在大数据时代不可缺少的重要运算方法。

主要事件

发展分析

瓶颈

①Octree对于3D物体建模编码非常有效，但是对于非稀疏化的数据来说，并没有明显的效率上的提升。

②Octree不具有旋转不变形（rotational invariance）,这影响了Octree结构数据的泛化性，比如影响了计算机视觉领域的神经网络训练的准确性。

③Octree并不是3D物体的直观表达，数据的可视化往往还需要经过大量的运算进行还原，在很多应用场景中是数据处理的一个中间的表达。

④现代图像处理方法多以卷积神经网络为基础，Octree虽然在稀疏化数据编码中有优势，但是不能天然地应用在像素、体素的卷积运算中。

未来发展方向

①构建Octree和普通像素、体素图像的快速转换，因为Octree结构的本身就是一种特征提取，因此Octree更接近于物体本身的结构。如果这种转换效率足够高，那么可以获得更好的数据结构。

②直接在Octree的数据结构上定义新型的深度神经网络，这样可以免去数据转换带来的效率损失，充分把Octree和深度神经网络的优势结合在一起。

contributor: Keyu Qi