OctNet：在高分辨率下学习深度3D表示.
OctNet是一种适用于稀疏3D数据的深度学习表示方法。OctNet按照层次将3D空间分为一组非平衡八叉树，叶子节点的数量跟随着分辨率变化。八叉树中的每个叶子节点都存储着体素里包含的所有特征的pooled summary。根据计算量低的特点，可以将分辨率设置的很高，高分辨率对于很多任务都是有帮助的。
1. Hybrid Grid-Octree Data Structure
八叉树是用指针实现的，在八叉树中访问任何一个元素都要从根节点开始向下寻找，因此复杂度与树的深度相关，当采用分辨率高的八叉树时，成本更高。
作者设计了一种混合网格八叉树数据结构，关键思想是限制八叉树的最大深度，并且沿着规则的网格放置较浅的八叉树。尽管这种数据结构可能不像标准八叉树一样计算成本低，但是可以获得很高的压缩比。
该数据结构还有一个优点是可以用字符串表示。比如给定一个深度为3的shallow八叉树，则使用73个bit表示整个八叉树：
在不用指针指向父母和孩子节点情况下，仅需简单的数学计算就能检索：
\[pa(i)=⌊\frac{i−1}{8}⌋,\quad ch(i)=8⋅i+1\]其中$pa()$表示父节点的索引，$ch()$表示孩子节点的索引。
2. Network Operations
OctNet直接在hybrid grid-octree数据结构上进行卷积神经网络操作。若$T_{i, j, k}$表示在体素$(i, j, k)$处的3D张量$T$，假设一个hybrid gridoctree包含$D \times H \times W$个shallow八叉树，每个八叉树的深度为$3$。$O[i,j,k]$表示包含体素$(i,j,k)$结构的最小单元值。
从grid-octree $O$到张量$T$的映射为：
\[\text { oc2ten : } T_{i, j, k}=O[i, j, k] \text {. }\]即要找$(i,j,k)$的值，则寻找能包住$(i,j,k)$, 大小又是最小的cell，这个cell的值就是位置$(i,j,k)$的tensor。
逆变换为：
\[\operatorname{ten} 2 \mathrm{oc}: O[i, j, k]= \underset{(\bar{i}, \bar{j}, \bar{k}) \in \Omega[i, j, k]}{\operatorname{ pool\_voxels }}\left(T_{\bar{i}, \bar{j}, \bar{k}}\right)\]其中$pool_voxels(\cdot)$操作为平均池化操作，将$T$中的体素池化为包含位置$(i,j,k)$的最小grid-octree，记为$\Omega[i, j, k]$。
⚪ 卷积
对于单独的特征，使用带有3D卷积核\(W \in \mathbb{R}^{L \times M \times N}\)对3D张量$T$进行卷积可以写为：
\[T_{i, j, k}^{\text {out }}=\sum_{l=0}^{L-1} \sum_{m=0}^{M-1} \sum_{n=0}^{N-1} W_{l, m, n} \cdot T_{\hat{i}, \hat{j}, \hat{k}}^{\text {in }}\]其中\(\hat{i}=i-l+\lfloor L / 2\rfloor, \hat{j}=j-m+\lfloor M / 2\rfloor, \hat{k}=k-n+\lfloor N / 2\rfloor\)。
相似地，在grid-octree数据结构上的卷积可以表示为：
\[O^{out}[i,j,k]=\mathop{\operatorname{ pool\_voxels }}_{(i¯,j¯,k¯)∈Ω[i,j,k]}(T_{i¯,j¯,k¯}) \\ T_{i,j,k}=∑_{l=0}^{L−1}∑_{m=0}^{M−1}∑_{n=0}^{N−1}W_{l,m,n}⋅O^{in}[\hat{i}, \hat{j}, \hat{k}]\]对于较小的卷积核和较大的体素，$T_{i, j, k}$在体素的一小部分是不变的。因此只需要计算体素内的一次卷积，接着沿着体素表面再进行卷积，其中support发生变化，这是因为邻近体素的值发生了变化。
⚪ 池化
$2^3$的最大池化将输入张量\(T^{\text{in}}\)分成$2^3$个不重叠的区域，并且计算每个区域内的最大值：
\[T_{i, j, k}^{\text {out }}=\max _{l, m, n \in[0,1]}\left(T_{2 i+l, 2 j+m, 2 k+n}^{\text {in }}\right)\]其中\(T^{\text {in }} \in \mathbb{R}^{2 D \times 2 H \times 2 W}, T^{\text {out }} \in \mathbb{R}^{D \times H \times W}\)。
为了在grid-octree数据结构上进行池化操作，对于输入为$2 D \times 2 H \times 2 W$个shallow octree的\(O^{\text {in }}\)，输出为包含$D \times H \times W$个shallow octree的\(O^{\text {out }}\)。\(O^{\text {in }}\)中的每一个体素减为一半，并且在shallow八叉树里复制了一个更深层。\(O^{\text {in }}\)在第三层的体素被池化：
\[\begin{aligned} & \mathrm{O}^{\text {out }}[\mathrm{i}, \mathrm{j}, \mathrm{k}]= \begin{cases}\mathrm{O}^{\text {in }}[2 \mathrm{i}, 2 \mathrm{j}, 2 \mathrm{k}] & \text { if vxd }(2 \mathrm{i}, 2 \mathrm{j}, 2 \mathrm{k})<3 \\ \mathrm{P} & \text { else }\end{cases} \\ & \mathrm{P}=\max _{\mathrm{l}, \mathrm{m}, \mathrm{n} \in[0,1]}\left(\mathrm{O}^{\text {in }}[2 \mathrm{i}+1,2 \mathrm{j}+\mathrm{m}, 2 \mathrm{k}+\mathrm{n}]\right), \end{aligned}\]其中\(\operatorname{vxd}(\cdot)\)计算在shallow octree中被索引体素的深度。
⚪ 上采样
最简单的上采样策略是使用最近邻插值：
\[T_{i, j, k}^{\text {out }}=T_{\lfloor i / 2\rfloor,\lfloor j / 2\rfloor,\lfloor k / 2\rfloor}^{\text {in }}\]其中\(T^{\text {in }} \in \mathbb{R}^{D \times H \times W},T^{\text {out }} \in \mathbb{R}^{2 D \times 2 H \times 2 W}\)。
在hybrid grid-octree数据结构上定义一个相似地操作：
\[O^{\text {out }}[i, j, k]=O^{\text {in }}[\lfloor i / 2\rfloor,\lfloor j / 2\rfloor,\lfloor k / 2\rfloor]\]该操作改变了数据结构：shallow octree的数量减少了8倍，因为在0层的深度生成了一个新的shallow octree，其他顶点的大小变为了两倍。为了捕获细节，体素可以根据对应池化层的原始八叉树再次以高分辨率进行划分。
