圖解 | 通俗易懂的Sparse Convolution過程

前言

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

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

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

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

實現(xiàn)部分，是基于“SECOND: Sparsely Embedded Convolutional Detection”的論文。

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

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

卷積神經(jīng)網(wǎng)絡(luò)已經(jīng)被證明對于二維圖像信號處理是非常有效的。然而，對于三維點云信號，額外的維數(shù) z 顯著增加了計算量。

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

稀疏的2D image。其中深灰色像素全為零，淺灰色像素代表非零數(shù)據(jù)點

稀疏的3D grid

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

否則這些空白區(qū)域帶來的計算量太多余了。

這就是 sparse convolution 提出的motivation。

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

二、舉例子之前的定義

為了逐步解釋稀疏卷積的概念，使其更易于理解，本文以二維稀疏圖像處理為例。由于稀疏信號采用數(shù)據(jù)列表和索引列表表示，二維和三維稀疏信號沒有本質(zhì)區(qū)別。

1. 輸入定義

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

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

在稀疏格式中，數(shù)據(jù)列表是[[0.1,0.1,0.1] ，[0.2,0.2,0.2] ，索引列表是[1,2] ，[2,3] ，并且是 YX 順序。

2. kernel 定義

假設(shè)使用以下參數(shù)進行卷積操作

稀疏卷積的卷積核與傳統(tǒng)的卷積核相同。上圖是一個例子，其內(nèi)核大小為3x3。

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

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

3. 輸出的定義

稀疏卷積的輸出與傳統(tǒng)的卷積有很大的不同。

對于稀疏卷積的發(fā)展，有兩篇很重要的論文，所以對應(yīng)的，稀疏卷積也有兩種輸出。

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

另一個稱為submanifold output definition。只有當(dāng)kernel的中心覆蓋一個 active input site時，卷積輸出才會被計算。

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

A1代表 active site，即 P1產(chǎn)生的卷積結(jié)果。

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

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

好的，假設(shè)完了，讓我們看看稀疏卷積到底是怎么算的。

三、稀疏卷積的計算過程

1、構(gòu)建 Input Hash Table 和 Output Hash Table

現(xiàn)在要把 input 和 Output 都表示成 hash table 的形式。

為什么要這么表示呢？

input hash table和output hash table 對應(yīng)上圖的 Hash_in，和 Hash_out。

對于 Hash_in：

v_in 是下標(biāo)，key_ in 表示value在input matrix中的位置。

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

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

input hash tabel的構(gòu)建完成了，接下來構(gòu)建 output hash table。

先來看一下卷積過程中 P1是怎么向下傳導(dǎo)的：

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

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

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

上面說的只是操作P1，當(dāng)然P2也是同樣的操作。

然后把P1, P2的結(jié)果結(jié)合起來（主要是消除掉重復(fù)元素），得到了一張位置表。是的沒錯，此處記錄的還是位置。

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

2、構(gòu)建 Rulebook

第二步是建立規(guī)則手冊——rulebook。

這是稀疏卷積的關(guān)鍵部分！！！（敲黑板了）

規(guī)則手冊的目的類似于 im2col [5] ，它將卷積從數(shù)學(xué)形式轉(zhuǎn)化為有效的可編程形式。

但是與 im2col 不同的是，rulebook集合了卷積中所有涉及到的原子運算，然后將它們關(guān)聯(lián)到相應(yīng)的核元素上。

上圖就是如何構(gòu)建 rulebook 的例子。

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

atomic operation是什么呢？舉個例子

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

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

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

3、Computation Pipeline

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

現(xiàn)在有輸入（這個圖上面出現(xiàn)過了）

對它進行卷積操作

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

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

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

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

紅色箭頭處理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的輸出。

同樣，藍(lán)色箭頭表示另一個原子操作。

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

四、總結(jié)

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

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

雖然構(gòu)建 rulebook 也是需要額外的計算開銷的，但是這個構(gòu)建過程也是可以在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

整理不易，點贊三連↓