3D稀疏卷积 3D Sparse Convolution

点云数据体素化后，有90%+的Voxel是空的，如果像VoxelNet那样直接使用3D Conv，计算量太大。

左图是稀疏的2D Tensor，深灰色像素都是0，浅灰色是non-zero点。

右图是稀疏的3D Tensor，只有红色的体素才是non-zero。

因此提出了3D稀疏卷积——3D Sparse Convolution。传统的3D卷积则被称为稠密卷积——Dense Convolution。

核心机制

Dense Conv处理的是矩阵。

Sparse Conv处理的是表。

Sparse Conv使用类似于哈希表的结构，只记录坐标 $[X, Y, Z]$ 和特征向量。
做卷积时，算法会提前计算好，当卷积核在有数据的地方滑动时，哪些输入点会和卷积核的哪个权重相乘。这个过程是在构建Rulebook。
计算时直接根据Rule把对应的数据拿出来算一下就行，不需要遍历整个空间。

既然是表结构，那么2D和3D稀疏卷积其实没有什么本质区别。那就以2D为例，2D Dense Convolution输入的是 $[N,C,H,W]$ 的矩阵；Sparse Convolution输入的则是2套列表：

Data List：只存non-zero点的值，我们称之为活跃点Active Sites。
Index List：保存non-zero点的坐标位置。

稀疏卷积流程

定义输入

我们先定义一个输入，这部分内容除了Focal Sparse Convolutional以外，均参考《How does sparse convolution work?》^[1]。

输入维度 $[N,3,5,5]$ 。只有P1和P2位置non-zero，取值分别为 $[0.1,0.1,0.1]$ 和 $[0.2,0.2,0.2]$ 。

卷积核为 $[3 \times3]$ ，stride=1，padding=0。深浅代表两个输出通道。

得到稀疏表示：

Data： $[[0.1,0.1,0.1], [0.2,0.2,0.2]]$
Index： $[[2,1], [3,2]]$ ，注意这里是列/行索引。

构建Hash Table

Input Hash Table储存所有Active Sites，根据示例的P1和P2，那就是保存2个。

$v_{in}$ ： $[0,1]$
$key_{in}$ ： $[[2,1], [3,2]]$

然后构建Ouput Hash Table，先操作P1：

P2对准过程同理。然后记录卷积后Active Sites元素的位置。P1和P2输出对应的索引为：

P1	P2
(0, 0)	(1, 0)
(1, 0)	(2, 0)
(2, 0)	(1, 1)
(0, 1)	(2, 1)
(1, 1)	(1, 2)
(2, 1)	(2, 2)

把重复的部分合并，得到输出的位置表，即Output Hash Table。

输入&输出的Hash Table构建完整过程如下图：

构建Rulebook

构建Rulebook的目的和im2col算法类似，将卷积从数学形式变为高效的可编程形式。

im2col 核心是空间块→列的维度重组，相当于用空间换时间，完全不关注原子操作或Kernel Elements的独立性，即使输入稀疏，im2col 仍会完整展开所有窗口，包含大量无效零值计算。

和im2col不同的是，Rulebook的核心是收集原子操作，按Kernel Elements分组。

收集原子操作：只有输入中non-zero的点参与卷积乘法加法，跳过所有zero值，每个原子操作会记录：
- 输入的non-zero的Index： $v_{in}$
- 对应的Kernel Element（weight & offset）
- 输出的Index： $v_{out}$
- 乘法加法次数 $count$
按Kernel Element关联操作，将所有原子操作按Kernel Element分组（如 F0 组、F1 组…F8 组），每组内的操作共享同一 Kernel偏移与权重，可并行执行。

下图是构建Rulebook的示例，图中 $GetOffset(P_{in},P)$ 中的 $P$ 并没有被直接体现出来，而且作者没详细解释Query Kernel的过程，所以让人困惑。 $GetOffset(P_{in},P)$ 的意义应该是给定输入点 $P_{in}$ 和输出点 $P_{out}$ 的位置，计算卷积核（Kernel）上对应的权重位置偏移量。

以P1点为例， $GetOffset(P_{in},P)$ 就是当卷积核滑动到以输出点 $P_{out}$ 对应的输入位置为中心的位置时，输入点 $P_{in}$ 相对于这个卷积核几何中心的偏移量。最直白版：输入点P1在当前卷积核内部的相对位置（不能更直白乐）。

所以公式应该可以重写为：

(i,j)=P_{in} - (P_{out}+K//2)

其中 $K$ 是卷积核的Kernel Size，这里就是3，除后是1。

我们快速回顾一下到这里都做了什么（For P1 Pixel）：

获取了像素点P1在2D Tensor中的位置信息，以及索引（编号），以此构造Input Hash Tabel
获取了像素点P1在Conv操作后，也就是在输出特征图中的每个输出的位置信息，以及对应索引（编号），以此构造Output Hash Table
获取了像素点P1在Kernel中的相对位置（offset偏移量），这决定P1的Value和Conv Kernel中的哪个Weight执行运算，并得到Rulebook
建立了完整的Input Pixel -> Conv Kernel × Input -> Output Feature的完整索引、空间位置映射链路

所以，Rulebook本质是在做 $P_{in} - Feature$ 的映射。

稠密卷积对每个输出点，必须遍历K×K个输入点，无论是否为zero；但是稀疏卷积对每个non-zero输入，只需要遍历它能产生结果的输出点。