稀疏卷积Submanifold Sparse Convolutional Networks

稀疏卷积Submanifold Sparse Convolutional Networks

论文 Submanifold Sparse Convolutional Networks

论文地址：https://arxiv.org/pdf/1706.01307.pdf

本文提出了稀疏卷积，介绍了具体的做法，后续很多三维点云语义分割/目标识别都沿用了这种做法

参考：https://blog.csdn.net/u013066730/article/details/108512125论文的解释

https://zhuanlan.zhihu.com/p/383299678 整体的计算过程

https://jishuin.proginn.com/p/763bfbd673db 整体的计算过程 同上

有点难 没有完全看懂 有时间再补一下

摘要

卷积网络是分析时空数据（如图像、视频、3D形状等）的通用方法。虽然其中一些数据自然密集（例如照片），但许多其他数据源本质上是稀疏的。例如，在一张纸上形成笔画，或使用激光雷达扫描仪或RGB-D相机获得（彩色）3D点云。卷积网络的标准“密集”实现在应用于此类稀疏数据时效率非常低。我们引入了一种稀疏卷积运算，专门用于处理稀疏数据，与之前在稀疏卷积网络上的工作不同，它严格地在子流形上操作，而不是在网络的每一层上“扩展”观测。我们对产生的子流形稀疏卷积网络的实证分析表明，它们的性能与最先进的方法相当，同时需要更少的计算量。

引言

卷积网络是一种最先进的方法，适用于涉及空间和/或时间结构数据分析的广泛任务，如照片、视频或三维表面模型。虽然此类数据通常包含密集填充的（2D或3D）网格，但其他时空数据集自然是稀疏的。例如，笔迹由二维空间中的一维线条组成，RGB-D相机拍摄的图片是三维点云，而非模型在三维空间中形成二维曲面。
维度灾难尤其适用于生活在具有三个或更多维度的网格上的数据：网格上的点数随维度呈指数增长。
在这种情况下，尽可能利用数据稀疏性以减少数据处理所需的计算资源变得越来越重要。事实上，在分析RGB-D视频时，利用稀疏性是至关重要的，例如，RGB-D视频是维度较少且能实现较好功能的4D结构。

传统的卷积网络实现针对密集网格上的数据进行了优化，无法有效处理稀疏数据。最近，已经提出了一些卷积网络实现，这些实现是为有效处理稀疏数据而定制的[1,2,9]。从数学上讲，这些实现中的一些与常规卷积网络相同，但它们在触发器[1]和/或内存[2]方面需要更少的计算资源。八元网络[9]稍微修改卷积算子，在远离感兴趣区域的网格部分产生“平均”隐藏状态。
卷积网络之前的稀疏实现的缺点之一是，它们在每一层中“扩展”稀疏数据，因为它们实现了“完全”卷积。在这项工作中，我们展示了在不扩展特征映射的情况下，成功地训练在整个网络层中保持相同稀疏模式的卷积网络是可能的。为此，我们探索了两种新的卷积算子：稀疏卷积（SC）和有效稀疏卷积（VSC）。在我们识别手写数字和3D形状的实验中，使用SC和VSC的网络实现了最先进的性能，同时减少大约50%的计算

研究的动机why

我们将d维卷积网络定义为以（d+1）维张量作为输入的网络：输入张量包含d个时空维度（如长度、宽度、高度、时间等）和一个额外的特征空间维度（例如，RGB颜色通道、表面法向量等）。稀疏输入对应于与特征向量关联的站点的d维网格。如果特征向量中的任何元素不处于基态，例如，如果它是非零1，我们将输入中的站点定义为活动的。在许多实际问题中，可以使用阈值来消除特征向量距离基态很小的位置。请注意，即使输入张量是（d+1）维的，活动也是一种d维现象：沿特征维的整个平面要么是活动的，要么不是。
卷积网络的隐藏层也由特征空间向量的d维网格表示。当通过网络传播输入数据时，如果作为输入的层中的任何站点处于活动状态，则隐藏层中的站点处于活动状态。（请注意，使用3×3卷积时，每个站点都连接到下面隐藏层中的3×3=9个站点。）因此，隐藏层中的活动遵循归纳定义，其中每一层决定下一层中的活动状态集。在每个隐藏层中，非活动站点都具有相同的特征向量：对应于基态的特征向量。请注意，隐藏层中的基态通常不等于零，特别是在使用带偏置项的卷积时。然而，无论基态值如何，在训练期间每次向前传球只需计算一次基态值（测试时所有向前传球只需计算一次）。这就大大节省了计算和内存需求；具体的节省取决于数据稀疏性和网络深度。

在本文中，我们认为上面描述的框架限制过多，特别是因为卷积运算没有被修改以适应输入数据的稀疏性。如果输入数据包含单个活动站点，则在应用3d卷积后，将存在3d活动站点。应用同样大小的第二次卷积将产生5d活性位点，以此类推。在实施由数十个甚至数百个卷积组成的现代卷积网络体系结构时，活动站点数量的快速增长前景不佳，例如VGG网络、Resnet和DenseNets[3,4,10]。当然，卷积网络通常不适用于仅具有单个活性位点的输入，但当输入数据包括二维或多维空间中的一维曲线，或三维或多维空间中的二维曲面时，上述“膨胀”问题同样存在问题。
为了解决活性位点膨胀的问题，我们提出了两种在卷积网络中使用的略有不同的卷积运算。这两种运算的共同点是，它们都忽略了基态：它们用零向量替换基态，以简化卷积运算。这两种操作的区别在于它们处理活动位点的方式：我们最有效的卷积操作只考虑中心输入，而不是在感受野的任何输入激活时自动激活一个位点（从而扩大活动位点集）。因此，活动站点的输出集正好反映了输入集的输出集。我们的经验证明，使用我们的自适应卷积算子，我们可以构建更深层的网络，从而实现最先进的结果，同时通过保持稀疏性，需要更少的资源。

2.1 “submanifold” dilation问题

为什么不能用一般的卷积操作处理稀疏数据？

“submanifold” dilation 问题

左： 原始输入，是一个手画的圆形， 是嵌入在二维网格(grid)上的一维曲线(curve)。

中：一次3x3卷积之后的结果

右：两次3x3卷积之后的结果

上图的输入是一个手写数字识别的例子，作者把上图表示出来的问题叫做“submanifold” dilation 问题 ，可以看到原始数据是非常sparse的，但是用了传统卷积之后，稀疏性很快就消失了。

如果不是对所有的pixel进行卷积，只对白色的有curve的pixel进行卷积操作会怎么样？

结果就是，会丢失很多信息，没法分类。

2.22 Very Deep Convolutional Networks

在图像分类中，带有小过滤器的非常深的卷积网络，通常大小为3×3像素，填充为1像素（以保持特征图的大小），已被证明是非常有效的。这种小型滤波器已成功应用于具有相对较宽层的VGG网络中。残余网络（resnet）的引入表明，带有小过滤器的更深但窄的网络更有效。非常深入的resnet、ResNeXt模型和具有瓶颈连接的densenet[3、4、12]的成功表明，一次计算相对较少数量的特征，并通过向量相加或特征向量串联将这些特征合并成更大的状态变量是有用的。
不幸的是，使用现有的稀疏卷积网络实现这些技术是实际的。因为具有多条路径的网络将倾向于生成不同的活动路径集，这些活动路径必须合并才能重新连接输出。似乎很难有效地执行这种合并。更重要的是，resnet和densenet产生了如此大的感受野，以至于稀疏性几乎会立即被活跃位点数量的激增所摧毁。

什么是（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.

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

3 (Valid) Sparse Convolutions: SC and VSC稀疏卷积SC和VSC

作者提出两种卷积操作：SC 和 VSC。

（1）SC卷积操作

引自：https://blog.csdn.net/u013066730/article/details/108512125

（2）VSC卷积操作

（3）激活函数和pooling函数