通俗易懂的解釋 Sparse Convolution 過程

來自｜知乎  作者丨月明星稀風蕭蕭

鏈接丨 https://zhuanlan.zhihu.com/p/382365889

編輯丨極市平臺

爲什麼需要稀疏卷積，稀疏卷積是如何工作的？本文作者運用簡單的舉例和圖片對稀疏卷積這一工作進行了詳細的闡述，閱讀本文只需 “幼兒園智商” 即可搞懂稀疏卷積！

前言

我之前寫過一次稀疏卷積的論文閱讀筆記，不過這個纔是最易懂的版本（嘔心瀝血畫了好些圖）。

閱讀本文只需要擁有幼兒園智商即可明白稀疏卷積

本文的理論部分是在 “3D Semantic Segmentation with Submanifold Sparse Convolutional Networks” 的基礎上完成的。

https://arxiv.org/pdf/1711.10275.pdf

實現部分，是基於 “SECOND: Sparsely Embedded Convolutional Detection” 的論文。

https://pdfs.semanticscholar.org/5125/a16039cabc6320c908a4764f32596e018ad3.pdf

一、爲什麼提出稀疏卷積？它有什麼好處？（可以跳過這個先看卷積過程）

卷積神經網絡已經被證明對於二維圖像信號處理是非常有效的。然而，對於三維點雲信號，額外的維數 z 顯著增加了計算量。

另一方面，與普通圖像不同的是，大多數三維點雲的體素是空的，這使得三維體素中的點雲數據通常是稀疏信號。

稀疏的 2D image。其中深灰色像素全爲零，淺灰色像素代表非零數據點

稀疏的 3D grid

我們是否只能有效地計算稀疏數據的卷積，而不是掃描所有的圖像像素或空間體素？

否則這些空白區域帶來的計算量太多餘了。

這就是 sparse convolution 提出的 motivation。

下面是一個示例，解釋了稀疏卷積是如何工作的。

二、舉例子之前的定義

爲了逐步解釋稀疏卷積的概念，使其更易於理解，本文以二維稀疏圖像處理爲例。由於稀疏信號採用數據列表和索引列表表示，二維和三維稀疏信號沒有本質區別。

1. 輸入定義

使用以下稀疏圖像作爲輸入

如圖所示，我們有一個 5 × 5 的 3 通道圖像。除了 P1 和 P2 兩點外，所有像素都是 (0,0,0) （雖然 0 這個假設也很不嚴謹）。根據文獻 [1] ，P1 和 P2，這種非零元素也稱爲 active input sites。

在稀疏格式中，數據列表是 [[0.1,0.1,0.1] ，[0.2,0.2,0.2] ，索引列表是 [1,2] ，[2,3] ，並且是 YX 順序。

2. kernel 定義

假設使用以下參數進行卷積操作

稀疏卷積的卷積核與傳統的卷積核相同。上圖是一個例子，其內核大小爲 3x3。

深色和淺色代表兩種濾鏡。在本例中，我們使用以下卷積參數。

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

3. 輸出的定義

稀疏卷積的輸出與傳統的卷積有很大的不同。

對於稀疏卷積的發展，有兩篇很重要的論文，所以對應的，稀疏卷積也有兩種輸出。

一種是 regular output definition，就像普通的卷積一樣，只要 kernel 覆蓋一個 active input site，就可以計算出 output site。

另一個稱爲 submanifold output definition。只有當 kernel 的中心覆蓋一個 active input site 時，卷積輸出纔會被計算。

上圖說明了這兩種輸出之間的區別。

A1 代表 active site，即 P1 產生的卷積結果。

類似地，A2 代表從 P2 計算出的 active site。A1A2 代表 active site，它是 P1 和 P2 輸出的總和。

深色和淺色代表不同的輸出通道。

好的，假設完了，讓我們看看稀疏卷積到底是怎麼算的。

三、稀疏卷積的計算過程

1、構建 Input Hash Table 和 Output Hash Table

現在要把 input 和 Output 都表示成 hash table 的形式。

爲什麼要這麼表示呢？

input hash table 和 output hash table 對應上圖的 Hash_in，和 Hash_out。

對於 Hash_in：

v_in 是下標，key_ in 表示 value 在 input matrix 中的位置。

現在的 input 一共兩個元素 P1 和 P2，P1 在 input matrxi 的 (2, 1) 位置, P2 在 input matrix 的 (3,2) 的位置，並且是 YX 順序。

是的沒錯，這裏只記錄一下 p1 的位置 ，先不管 p1 代表的數字。所以其實可以把這個 input hash table 命名爲 input position hash table。

input hash tabel 的構建完成了，接下來構建 output hash table。

先來看一下卷積過程中 P1 是怎麼向下傳導的：

用一個 kernel 去進行卷積操作：

但是，並不是每次卷積 kernel 都可以剛好碰到 P1。所以，從第 7 次開始，輸出的這個矩陣就不再變化了。

然後記錄每個元素的位置。

上面說的只是操作 P1，當然 P2 也是同樣的操作。

然後把 P1, P2 的結果結合起來（主要是消除掉重複元素），得到了一張位置表。是的沒錯，此處記錄的還是位置。

然後編號，就得到了 output hash table。

2、構建 Rulebook

第二步是建立規則手冊——rulebook。

這是稀疏卷積的關鍵部分！！！（敲黑板了）

規則手冊的目的類似於 im2col [5] ，它將卷積從數學形式轉化爲有效的可編程形式。

但是與 im2col 不同的是，rulebook 集合了卷積中所有涉及到的原子運算，然後將它們關聯到相應的核元素上。

上圖就是如何構建 rulebook 的例子。

rulebook 的每一行都是一個 atomic operation（這個的定義看下面的列子就知道了），rulebook 的第一列是一個索引，第二列是一個計數器count， v_in 和 v_ out 分別是 atomic operation 的 input hash table 的 index 和 output hash tabel 的 index。（沒錯，到現在爲止，依然是 index，而沒有用到真實的數據。）

atomic operation 是什麼呢？舉個例子

紅色框框表示的是下圖的 atomic operation

黃色框框表示的是下圖的 atomic operation

因爲這個時候 (0, -1) 是第二次被遍歷到，所以 count+1.

3、Computation Pipeline

綜上，編程中的過程是什麼樣子的呢？

現在有輸入（這個圖上面出現過了）

對它進行卷積操作

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

深色和淺色的 kernel 表示 2 個不同的 kernel，即 output channel=2。

則，程序裏的稀疏卷積過程是：

如圖所示，稀疏卷積中的卷積計算，不用滑動窗口方法，而是根據 rulebook 計算所有的原子操作。在圖中，紅色和藍色箭頭表示兩個不同的計算實例。

紅色箭頭處理 rulebook 中第一個 atomic operation。從 rulebook 中，我們知道這個 atomic operation 有來自 input index (v_in) =0 位置 (2,1) 的 P1 的輸入，和 output index (v_out) =5 位置 (2,1)的輸出。

對於 p1 代表的 (0.1, 0.1, 0.1)，分別跟深色和淺色兩個 kernel 進行卷積運算，得到深黃色和淺黃色兩個 channel 的輸出。

同樣，藍色箭頭表示另一個原子操作。

可以看到紅色操作和藍色操作有相同的 output index (v_out），沒事的，直接把他們的輸出加起來就好了。

四、總結

input/output hash tabel 只維護那些真正有元素的條目。

所以說，稀疏卷積是非常 efficient 的，因爲我們只計算非零元素（元素指的是像素 或者 體素）的卷積，而不需要計算所有的元素。

雖然構建 rulebook 也是需要額外的計算開銷的，但是這個構建過程也是可以在 GPU 上並行處理的。

引用

[1] Graham, Benjamin, Martin Engelcke, and Laurens Van Der Maaten. “3d semantic segmentation with submanifold sparse convolutional networks.”Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.

[2] Yan, Yan, Yuxing Mao, and Bo Li. “Second: Sparsely embedded convolutional detection.”_Sensors_18.10 (2018): 3337.

[3] Li, Xuesong, et al. “Three-dimensional Backbone Network for 3D Object

[4] https://towardsdatascience.com/how-does-sparse-convolution-work-3257a0a8fd1

本文部分插圖用了這篇文章的，已經聯繫過作者獲得了轉載的授權，筆芯。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/UNNMSclcHeCrEJZ5cpRJcA