(ML) Sparse Convolution
卷積神經網絡 (CNN) 使用在 二維的圖像處理非常有效，但是在處理三維點雲（point clouds）時，額外增加的維度 Z 也就增加了計算量，且 3D 點雲大部分的體像素都是空的，若使用常規卷積不僅會增加計算量，也會嚴重破壞原本稀疏的程度，如下圖
Sparse Convolution 分為兩種：
- Regular sparse convolution
- Submanifold sparse convolution
Example
輸入一張 2D Sparse 的 RGB 影像（Channel = 3，Width = 5，Height = 5）
下圖中的 input tensor 只有在 p1, p2 有數值，其它的地方數值都是 0
進行（stride = 1 ,padding = 0）卷積操作
filter 中的 channel 是 input tensor 的 channel 所決定的
Regular sparse convolution
下圖中 空白地方的數值為 0，若使用 Regular sparse convolution 輸出的 feature map 就會發生膨脹
Submanifold sparse convolution
在 Submanifold sparse convolution 上，當 kernel 的中心有數值時，才會進行卷積運算，這樣就能保有原本稀疏的程度
Submanifold sparse convolution operation
- Build the hash table
- Build Rule Book
- Computation for GPU
Build the hash table
對於上圖，右上角的輸出 feature map 代表 p1 卷積後產生的輸出結果，右下角的輸出 feature map 代表 p2 卷積後產生的輸出結果
將 P1, P2 卷積輸出的結果結合起來（主要是消除掉重複元素），最後得到了一張位置表（Hash out）
Build Rule Book
- build getoffset
接下來會建立 getoffset ，getoffset 會存取 kernel 經過 tensor 中 p1 的權重所在位置
當然也會紀錄 p2 所在的權重位置
最後使用 getoffset 來建立 Rulebook
Computation for GPU
最後就是透過查詢 Rulebook 來進行卷積計算，而建構 Rulebook 就是使用 GPU 來實現
以上就是 Submanifold sparse convolution 運作方式，總結就是通過對 input tensor 不為 0 的 value 建立位置哈希表和 RuleBook，只對有效數據計算卷積運算，從而減少計算量，且不破壞原本稀疏的程度
網路上有不少的文章，但是表格對我來說有點複雜，所以我將表格進行簡化，並且省略一些看起來不重要的地方，重新製作新的圖表來幫助我理解
