通俗易懂的解釋Sparse Convolution過程

前言

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

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

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

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

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

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

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

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

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

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

稀疏的3D grid

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

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

這就是 sparse convolution 提出的motivation。

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

二、舉例子之前的定義

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

1. 輸入定義

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

如圖所示，我們有一個(gè)5 × 5的3通道圖像。除了 P1和 P2兩點(diǎn)外，所有像素都是(0,0,0) （雖然0這個(gè)假設(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ù)進(jìn)行卷積操作

稀疏卷積的卷積核與傳統(tǒng)的卷積核相同。上圖是一個(gè)例子，其內(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 覆蓋一個(gè) active input site，就可以計(jì)算出output site。

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

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

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

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

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

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

三、稀疏卷積的計(jì)算過程

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一共兩個(gè)元素 P1和P2，P1在input matrxi的(2, 1)位置, P2在 input matrix 的(3,2)的位置，并且是 YX 順序。

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

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

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

用一個(gè)kernel去進(jìn)行卷積操作：

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

然后記錄每個(gè)元素的位置。

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

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

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

2、構(gòu)建 Rulebook

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

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

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

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

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

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

atomic operation是什么呢？舉個(gè)例子

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

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

因?yàn)檫@個(gè)時(shí)候(0, -1) 是第二次被遍歷到，所以count+1.

3、Computation Pipeline

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

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

對它進(jìn)行卷積操作

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

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

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

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

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

對于p1 代表的 (0.1, 0.1, 0.1)，分別跟深色和淺色兩個(gè)kernel進(jìn)行卷積運(yùn)算，得到深黃色和淺黃色兩個(gè)channel的輸出。

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

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

四、總結(jié)

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

所以說，稀疏卷積是非常 efficient的，因?yàn)槲覀冎挥?jì)算非零元素（元素指的是像素 或者 體素）的卷積，而不需要計(jì)算所有的元素。

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

本文部分插圖用了這篇文章的，已經(jīng)聯(lián)系過作者獲得了轉(zhuǎn)載的授權(quán)，筆芯。

如果覺得有用，就請分享到朋友圈吧！