子流形卷积层

子流形卷积层

Convolution is the most common operation for processing data in deep learning. However, since most of the data we paid attention to, such as pictures and videos, can be seen as regular dense grids, convolution is also based on the characteristics of this dense structure, but in fact, there are a lot of data that do not meet the characteristics of regular and dense, such as one-dimensional curves in two-dimensional space, two-dimensional curved surfaces in three-dimensional space, and 3D point clouds.

卷积是深度学习中处理数据的最常见操作。 但是，由于我们关注的大多数数据(例如图片和视频)可以看作是规则的密集网格，因此卷积也基于这种密集结构的特征，但是实际上，有很多数据可以不满足规则和密集的特征，例如二维空间中的一维曲线，三维空间中的二维曲面和3D点云。

When the data structure is sparse, directly applying the traditional dense convolution to these data will waste a lot of computing resources due to invalid calculations in the empty space, so it is very important to use sparsity to process these data. As the convolution layer deepens, the sparsity of the data cannot be maintained. As shown in Figure above, the input data is a one-dimensional curve in a two-dimensional space. But after traditional convolution, the extracted features are no longer sparse. The author calls this phenomenon the submanifold expansion problem, submanifolds refer to sparse input data, such as one-dimensional curves in two-dimensional space, two-dimensional curved surfaces and point clouds in three-dimensional space, and they do not occupy the space in which they are located.

当数据结构稀疏时，由于在空空间中无效的计算，直接对这些数据应用传统的密集卷积将浪费大量计算资源，因此使用稀疏性来处理这些数据非常重要。 随着卷积层加深，无法保持数据的稀疏性。 如上图所示，输入数据是二维空间中的一维曲线。 但是在传统的卷积之后，提取的特征不再稀疏。 作者将此现象称为子流形扩展问题，子流形是指稀疏的输入数据，例如二维空间中的一维曲线，二维空间中的二维曲面和点云，它们不占据空间它们所在的位置。

In order to extract point cloud features with sparse structure, researchers have come up with many methods, such as the PointNet series, deep continuous convolution, edge convolution, point cloud convolution, and so on. The manifold sparse convolution introduced here is a different method. Sparse 3D Convolution was first proposed in [1] , and then the author proposed Submanifold Sparse Convolution [2] and applied it to 3D semantic segmentation [3] . [4] improved the implementation of Sparse 3D Convolution and applied it to 3D target detection.

为了提取具有稀疏结构的点云特征，研究人员提出了许多方法，例如PointNet系列，深连续卷积，边缘卷积，点云卷积等。 这里介绍的流形稀疏卷积是另一种方法。 稀疏3D卷积首先在[1]中提出，然后作者提出了子流形稀疏卷积[2]并将其应用于3D语义分割[3]。 [4]改进了稀疏3D卷积的实现并将其应用于3D目标检测。

To solve the problem of submanifold expansion, the most straightforward idea is to only convolve the active site, but in this case, each pixel is processed independently, and the network cannot extract all the information. Through analysis, the author believes that pooling is added or stride convolution can effectively alleviate this problem.

为了解决子流形扩展的问题，最直接的想法是只对活动站点进行卷积，但是在这种情况下，每个像素都是独立处理的，并且网络无法提取所有信息。 通过分析，作者认为添加池化或跨步卷积可以有效地缓解此问题。

Source[2] 来源[2]

The author proposes two convolution operations:

作者提出了两种卷积运算：

The sparse convolution operation that can be expressed as SC(m, n, f, s), where m is the input feature space, n is the output feature space, f is the convolution kernel size, and s is the stride length. For active sites, SC is the same as traditional dense convolution. If the input size is l, the output size is (l-f + s) / s, and for non-active sites, the author directly sets it to 0.

可以表示为SC(m，n，f，s)的稀疏卷积运算，其中m是输入特征空间，n是输出特征空间，f是卷积核大小，s是跨步长度。 对于活动站点，SC与传统的密集卷积相同。 如果输入大小为l，则输出大小为(lf + s)/ s，对于非活动站点，作者直接将其设置为0。

An SC convolution computes the set of active sites in the same way as a regular convolution: it looks for the presence of any active sites in its receptive field of size f^d. An SC convolution differs from a regular convolution in that it discards the ground state for non-active sites by assuming that the input from those sites is exactly zero.

SC卷积以与常规卷积相同的方式计算活动位点集：它在大小为f ^ d的接受域中寻找任何活动位点的存在。 SC卷积与常规卷积的不同之处在于，它假定非活动站点的输入恰好为零，从而放弃了非活动站点的基态。

For the first layer, active site is the pixel or point that has data. The site should be understood as the pixel in the image and the point in the point cloud. For the subsequent layers, if there is an active site in the receptive field of this site, then this site is an active site. This calculation method is the same as the traditional convolution operation to calculate the active site.

对于第一层，活动站点是具有数据的像素或点。 该位置应理解为图像中的像素和点云中的点。 对于后续层，如果此站点的接受域中有一个活动站点，则此站点为活动站点。 这种计算方法与传统的卷积运算来计算活动站点相同。

Set the ground state of these sites to 0 directly , then, when the input and the kernel weight are multiplied, the output is still 0. In this way, non-active sites are equivalent to being discarded. Therefore, the input of each layer of sc is a non-active site, and the output of this layer is still a non-active site. This is different from the traditional convolution operation.

将这些站点的基态直接设置为0，然后，当输入和内核权重相乘时，输出仍为0。这样，无效站点等效于被丢弃。 因此，sc的每一层的输入都是非活动站点，而该层的输出仍然是非活动站点。 这不同于传统的卷积运算。

The submanifold sparse convolution that can be expressed as SSC(m,n,f), where s=1, and (f-1)/2 is added to each side of the input feature to ensure that the input and output have the same size. The difference between SSC and SC is that as long as there is an active site in the receptive field of the output site, the output site is regarded as the active site in the SC, and the output site is regarded as the active site in the SSC only when the center point of the receptive field of the output site is the active site. site, as shown in Figure 3:

可以表示为SSC(m，n，f)的子流形稀疏卷积，其中s = 1，并且(f-1)/ 2被添加到输入要素的每一侧，以确保输入和输出具有相同的尺寸。 SSC和SC的区别在于，只要输出站点的接收域中有一个活动站点，该输出站点就被视为SC中的活动站点，而该输出站点则被视为SC中的活动站点。仅当输出站点的接收场的中心点是活动站点时，才进行SSC。 站点，如图3所示：

Submanifold Sparse Convolution is implemented in [2] , in which the convolution operation is handwritten matrix multiplication, so the speed is slow; [4] is based on GEMM to achieve a more efficient Submanifold Sparse Convolution. As shown in Figure 3. It has nearly doubled the speed increase.It first performs matrix multiplication of non-zero elements through the gather operation, and then maps the result back to the original position through the scatter operation. In order to speed up, the calculation of the mapping matrix of the front and back elements is more critical.

子流形稀疏卷积在[2]中实现，其中卷积运算是手写矩阵乘法，因此速度较慢； [4]基于GEMM实现了更有效的子流形稀疏卷积。 如图3所示。它的速度增加了将近一倍。它首先通过聚集操作执行非零元素的矩阵乘法，然后通过分散操作将结果映射回到原始位置。 为了加快速度，前后元素的映射矩阵的计算更为关键。

Source[4] 来源[4]

Submanifold Sparse Convolution can be applied to point cloud classification, segmentation, detection and other tasks of feature extraction. SECOND [4] is a point cloud detection method. Its detection framework is consistent with the traditional one, but the point cloud feature information after voxelization is further used for feature extraction by Sparse Convolution. This method is not only faster, but also has a lot of performance improvements. So Submanifold Sparse Convolution is very efficient and can be used as a basic operation for point cloud feature extraction.

子流形稀疏卷积可用于点云分类，分割，检测和其他特征提取任务。 第二[4]是点云检测方法。 它的检测框架与传统框架一致，但是体素化后的点云特征信息被稀疏卷积进一步用于特征提取。 这种方法不仅速度更快，而且还改善了许多性能。 因此，子流形稀疏卷积非常有效，可以用作点云特征提取的基本操作。

However, the traditional Convolution, under the GPU platform, already has more hardware-level optimizations, and there are also many instruction set optimizations under the CPU platform, so in the end, the speed of Submanifold Sparse Convolution can be improved when Inference is made on specific hardware.

但是，传统的卷积在GPU平台下已经进行了更多的硬件级优化，并且在CPU平台下也有很多指令集优化，因此最终，进行推理时可以提高子流形稀疏卷积的速度。在特定的硬件上。

翻译自: https://towardsdatascience.com/submanifold-sparse-convolutional-networks-b0c54f07f4e3

子流形卷积层

相关资源：fastai_sparse：2D3D稀疏数据的3D增强和变换，例如3D三角形网格或欧几里得空间中的点云。 扩展Fast.ai库以训练子流形稀疏卷积网络-源码