复杂onnx解决方案（以sparseconv为例）

前言

杜老师推出的 复杂onnx解决方案（以sparseconv为例） 课程，通过本次课程学习稀疏卷积以及 SCN 模型的导出细节，记录下个人学习笔记，仅供自己参考。

1. 稀疏卷积

我们先来了解下稀疏卷积和对应的一些基础知识

正常卷积如 图1 所示，需要 9 次乘，而稀疏卷积仅需要 3 次乘

图1-1 卷积

我们在 图1-1 中观察到矩阵中存在大量 0 元素，因此可以采用稀疏化储存表示

• features = [1 2 5]，代表非 0 元素值，一般用二维数组表示 n x 1
• indices = [[0, 0], [1, 1], [2, 2]]，表示非 0 元素值的索引，一般用二维数组表示 n x 2

卷积核只需要与非 0 元素值进行运算即可，因此只需要 3 次乘

那为什么需要稀疏卷积呢？在什么情况下会存在大量的零元素呢？

稀疏主要用在点云数据上，假设现有 100 个点，每个点对应有 k 个特征，则可稀疏表示为

• features.shape = 100 x k
• indices.shape = 100 x 4 这里 4 分别表示 [batch, x, y, z]，一个点有 xyz 在 voxel grid 中的坐标，以及属于哪个 batch

稀疏卷积就是标准卷积的稀疏版本，其输入是稀疏的。

对于稀疏卷积有两种形式：(copy自here)

一种是 Spatially Sparse Convolution，在 spconv 中为 SparseConv3D。就像普通的卷积一样，只要卷积核 kernel 覆盖了一个非零输入点，就会计算对应的输出。对应论文 SECOND:Sparsely Embedded Convolutional Detection

另一种是 Submanifold Sparse Convolution，在 spconv 中为 SubMConv3D。只有当卷积核 kernel 中心覆盖一个非零输入点时，卷积输出才会被计算。对应论文 3D Sematic Segmentation with Submanifold Sparse Convolutional Networks

更多细节可查看下面的第 2.3 小节内容

2. Sparse Convolution Model

卷积神经网络已被证明对二维图像信号处理非常有效。然而，对于三维点云信号，额外的维度 Z 大大增加了计算量。另一方面，与普通图像不同，三维点云的大部分体素是空的，这使得三维体素中的点云数据往往是稀疏的信号。

问题在于我们是否只用稀疏的数据有效地计算卷积，而不是扫描所有的图像像素或空间体素。

很直观的一个想法是，常规的图像信号被存储为矩阵或张量，而相应的卷积计算为密集矩阵的乘法。稀疏信号通常可以被表示为数据列表和索引列表，我们可以采用特殊的卷积模式，利用稀疏性号特殊的表示的优势。

简单来说，传统卷积使用 FFT 或者 im2col 来构建计算管道，而稀疏卷积会收集所有关于卷积核元素的原子操作，并将它们作为计算指令保存在 Rulebook 中

下面我们通过一个例子来解释稀疏卷积的工作原理。

以下内容均 Copy 自 https://towardsdatascience.com/how-does-sparse-convolution-work-3257a0a8fd1

2.1 输入数据模型

为了一步步解释稀疏卷积的概念，让它更容易理解，我们先以二维图像处理为例。由于稀疏信号是采用数据列表和索引列表来表示的，因此二维和三维稀疏信号并没有本质的区别

图2-1 稀疏图像示例(除P1、P2外所有元素均为零)

如 图2-1 所示，我们现在有一个 3 通道的 5x5 大小的图像。除了 P1 和 P2 两个点之外，其余所有像素均为 (0,0,0)。P1 和 P2 这种非零元素也称为 active input sites

在密集形式下，输入张量的 shape 为 [1x3x5x5]，对应的维度分别为 NCHW；在稀疏形式下，数据列表为 [[0.1, 0.1, 0.1], [0.2, 0.2, 0.2]]，索引列表为 [[1, 2], [2, 3]] (采用 YX 顺序)

2.2 卷积核

图2-2 kernel示例

稀疏卷积的卷积核和传统卷积核相同。图2-2 中的 kernel size 为 3x3。深色和浅色分别代表 2 个 filter，在这个例子中我们使用如下的卷积参数：

conv2D(kernel_size=3, out_channels=2, stride=1, padding=0)
1

2.3 输出的定义

稀疏卷积的输出与传统卷积有很大不同。稀疏卷积有 2 种输出定义。

一种是 regular output 定义，就像普通的卷积一样，只要卷积核 kernel 覆盖了一个非零输入点，就会计算对应的输出。

另一种被称为 submanifold output 定义，只有当卷积核 kernel 中心覆盖一个非零输入点时，卷积输出才会被计算。

图2-3 两种输出定义

图2-3 说明了这两种输出的区别，A1 代表 active output sites 也就是 P1 的卷积结果；同样地，A2 也代表 active output sites 是由 P2 计算出来的。A1A2 也代表 active output sites 是 P1 和 P2 的输出之和。深色和浅色代表着不同的输出通道。

因此，在密集形式下，输出张量的形状为 [1x2x3x3] 其维度顺序为 NCHW；在稀疏形式下，输出是由两个列表构成，一个是数据列表，一个是索引列表，这与稀疏形式下的输入的表达是类似的。

2.4 计算流程

传统卷积通常使用 im2col 将卷积重写并将卷积视为密集矩阵乘法问题。然而，稀疏卷积使用一个 Rulebook 来计算所有的原子操作，而不是使用 im2col。

2.4.1 构建 hash table

第一步是来构建 hash tables

图2-4 哈希表构建

完整的流程如 图2-4 所示，在 图2-4 中输入哈希表存储了所有 active input sites ，然后，我们估计了所有可能的 active output sites，并考虑两种输出定义 (Sparse Output、Submanifold Output) 中的某一种去计算输出，最后使用输出哈希表来记录所有的 active output sites

值得注意的是，在 图2-4 中对于键值的描述并不是那么清楚，$v$ 更像一个哈希键，而 $key$ 更像一个哈希值，它们都没有重复的元素。因此，具体哪一个应该是键，哪一个应该是值，取决于你的程序。

接下来我们一步步来介绍构建过程，先来看下 P1 是怎么进行卷积操作的：

图2-5 P1卷积过程(1)

但是，并不是每次 kernel 在卷积过程中都可以碰到 P1，从第七次开始，输出矩阵就不再发生变化了。

图2-5 P1卷积过程(2)

得到 P1 的输出后我们来记录每个元素的位置

图2-5 P1卷积过程(3)

上面的只是操作 P1，对于 P2 也是同样的操作，如下图所示：

图2-6 P2卷积过程

最后把 P1，P2 的结果结合起来(主要是消除掉重复元素)，得到一张位置表，编号得到 output hash table

图2-7 输出哈希表

2.4.2 构建 Rulebook

第二步是建立 Rulebook，这是稀疏卷积的关键部分。Rulebook 的目的类似于 im2col，它将卷积从数学形式转换为有效的可编程形式。但与 im2col 不同的是，Rulebook 收集了卷积中所有涉及的原子操作，然后将它们关联到相应的 kernel 元素上。

图2-8 构建Rulebook

图2-8 演示了如何构建 Rulebook，$P_{in}$ 中包含着输入索引，在这个示例中，我们在位置 (2,1) 和 (3,2) 有两个非零元素，$P_{out}$ 中有相应的输出索引，接下来，我们会收集卷积计算过程中的原子操作(atomic operator)，即把卷积过程看成是许多原子操作。最后，我们将所有的原子操作记录在 Rulebook 中， 在 图2-8 的 Rulebook 中，第一列是 kernel element 的索引，第二列是一个计数器，关于这个 kernel element 涉及多少个原子操作。第三列和第四列是关于这个原子操作中输入哈希表的索引和输出哈希表的索引。

$(i,j)$ 具体是如何生成的呢？很简单，我们在做卷积的时候对应的非零元素 P 在 single channel kernel template 的位置就是对应的 $(i,j)$，比如在 P1 第一次卷积时，P1 对应的位置是 (+1,0)，因此其对应的 $(i,j)$ 就是 (+1,0)

图2-9 ij生成示例

2.4.3 在GPU上计算Pipeline

最后是在程序中实现稀疏卷积，过程如下：

图2-10 计算稀疏卷积

图2-10 是计算稀疏卷积的示例，初看可能觉得复杂，细看你会发现也不简单