稀疏卷积

构建一个稀疏卷积需要满足哪些要求:

1. 减少不必要的运算量。

2. 满足特征的稀疏性，并且在保证稀疏性的同时维护特征的空间不变性。

1. MinkEngine

$C = \left[ \begin{matrix} x_1 & y_1 & z_1 & b_1\\ & : & : & \\ x_N & y_N & z_N & b_N \end{matrix} \right]$,$F = \left[ \begin{matrix} f_1^T \\ : \\ f_N^T \end{matrix} \right]$

其中 (x,y,z) 表示点云的坐标， b 表示 属于batch中的哪个点云 (MinkowskiEngine也是把点云组织成batch进行训练)， $N$ 表示1个batch中所有点的数量， $f^i_n$ 表示第 i 个点的特征，可以是1维或者3维或者其它维度的。

Sparse Tensor Quantization

数据处理以生成稀疏张量

将所有坐标转换为哈希键，并找到所有唯一的哈希键标签对以消除冲突。

Generalized Sparse Convolution

• 根据输入坐标 Cin（Eq.3）生成输出坐标 Cout。

• 使用指定的内核映射将输入与内核进行卷积

Pooling

Non-spatial Funtions

2. SpConv

traveller59/spconv: Spatial Sparse Convolution Library (github.com)

spConv稀疏卷积 - 知乎 (zhihu.com)

什么是（submanifold）子流形？

We use the term 'submanifold' to refer to input data that is sparse because it has a lower effective dimension than the space in which it lives, for example a one-dimensional curve in 2+ dimensional space, or a two-dimensional surface in 3+ dimensional space.

我们使用术语“子流形”来表示输入数据是稀疏的，因为它的有效维数低于它所在的空间，例如二维空间中的一维曲线，或三维空间中的二维曲面。

建立输入哈希表

首先，稀疏卷积操作会将输入转化为Hash_in这张输入哈希表，hash_in表示着activate输入的标志（也就是说对应的这个稀疏输入是需要被计算的）。

对于P1点而言，在hash_in中对应了v=0 key=(2,1)。其对应的输出tensor中与P1有关的像素点为A1的六个位置那么将这些点视作作为P_out。以此类推P2也会拥有一系列P2_out的点。将这些Pout点合并后可以获得Hash_out表。

构建hash表的最重要原因是我们在前面提到的在完成稀疏卷积后为了防止稀疏特征的塌缩失去几何特征的表示能力，这里将Tensor的坐标与序号进行对应，方便卷积计算好数值之后将其放回原本tensor的位置。

建立RuleBook

在第一步中，我们成功的建立了输入和输出的哈希表。这两个表分别将输入和输出的Tensor坐标映射到了序号，但是这两张表之间的序号是不统一的现在需要额外构建一张rulebook表将输入和输出这两张表对应起来。

上图显示了构建Rulebook的整体流程，其中分为两个主要部分。

第一，将Pout转化到GetOffset(Pin, P)；

第二，从GetOffSet(Pin, P)转化到Rulebook。

• 首先来看如何构建GetOffset（Pin, P）这个函数。假如以Pout(0,0)为例，在这个橙色的窗口中只有右侧P1位置非零，其余位置均为零。那么这次卷积操作只需要通过这个位置的卷积权重和输入值计算得到。P1位置对应到卷积核中的位置就是（1，0）。我们把这个（1，0）放入GetOffset()结果中。

• 将GetOffset()进一步得到Rulebook

  • 在上一步中我们根据Pin与Pout获得GetOffset()，那么这个获得的方法就可以总结成Rulebook。我们可以看到Rulebook中第一列为上一步记录的卷积核权重位置，第三列为输入像素值的输入序号，第四列为卷积结果对应的输出序号,count为各个卷积权重的数量统计。

稀疏卷积在GPU中的运算是通过查询Rulebook实现的，以Rulebook第一行红色方框为例，首先通过（-1，-1）找到卷积核权重F0；其次，根据输入像素序号，查找输入哈希表找到对应的tensor向量（0.1，0.1，0.1）

3. TorchSparse

TorchSparse: Efficient Point Cloud Inference Engine | Papers With Code

TorchSparse++: Efficient Training and Inference Framework for Sparse Convolution on GPUs | Papers With Code

TorchSparse的优化策略包括：

1. 采用自适应的矩阵乘法分组，提高计算的规则性；
2. 采用量化，向量化和局部性感知的内存访问，减少数据移动的开销；
3. 采用内核融合，减少映射操作的延迟

TorchSparse++:

1. 提出了一个稀疏核生成器，可以快速生成高性能的稀疏卷积核，降低了工程复杂度；
2. 设计了一个稀疏自动调优器，可以在扩大的设计空间中搜索最佳的数据流配置，适应不同的训练和推理工作负载。