Convolution処理の手法　Im2Col方式の図解

先日のConvolution処理の記事[「高速な Convolution 処理を目指してみた。Kn2Image方式」](http://qiita.com/t-tkd3a/items/879a5fd6410320fe504e)で　の 比較対象として紹介した Im2Col 方式 について図解します。

#参考文献
* [cuDNN: Efficient Primitives for Deep Learning(arXiv:1410.0759)](https://arxiv.org/abs/1410.0759)
* [Pete Warden's blog (2015/04/20) Why GEMM is at the heart of deep learning](https://petewarden.com/2015/04/20/why-gemm-is-at-the-heart-of-deep-learning/)

# Im2Col 方式
* Im2Col方式の特徴は、行列積演算１回でConvolution処理を行うために、Source Image の画素配置を(重複ありで)変形させるところにあります。
* 本記事では、変形させた画素配置を col展開 と呼称します。
* 以下、順を追って図解します。

## 画素配置変換 (Image → Col展開)
* 下図の８×６の画像 を 入力画像として説明していきます。
* 説明用に１画素のみ 色 を変えてあります。

![01_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/5d526556-f421-6c2f-dab0-ab0663725583.png)

* フィルタは ３×３ です。
* ⑤を注目画素とします。

![01_2.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/b4a3ced8-daf3-ee82-0975-3bcc36e5b062.png)

---

* 左上の画素を始点とします。
* 注目画素 と 近傍（３×３）を、１列にシリアライズします。
* 範囲外の ①②③④⑦ は 0値 を格納します。


![02_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/51b0cf1a-d656-50f0-c8ad-08fa53c2cd7e.png)


---
* 注目画素を右に移動させます。
* 同様に、注目画素 と 近傍（３×３）を、１列にシリアライズします。

![02_2.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/c4fec42f-9c1b-af02-6456-d562060da906.png)


---
* 同様に...

![02_3.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/c080e7d8-fcf5-5ade-fd9f-87985802d58e.png)

---
* 右端に達すると、

![02_4.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/c4f6a232-0a2b-1cbb-963a-0e402286accc.png)

---
* 注目画素を 一行下の左端に 移します。

![02_5.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/6594b99a-f92e-8ce4-a71c-6fa7a9c4e383.png)

---
* 同様に...

![02_6.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/6ef36023-e198-75f2-46db-ce41b8e1b095.png)

---
* 同様に...
 
![02_7.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/6832cadc-e527-a2a5-f1be-ee784b62fdfa.png)

---
* 同様に...

![02_8.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/2bd89c26-3bad-f35a-ed02-b559fe294455.png)

---
* 同様に...

![02_9.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/cc32a934-0a35-7418-1398-19591feb2b01.png)

---
* 同様に...

![02_10.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/4aa3f099-cd27-0667-cf1a-b26039cdce35.png)

---
* 同様に...

![02_11.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/1ca2462c-307c-1d99-36c2-9ee267600e92.png)

* Sorce Image の右下の終点まで行います。

---
### 補足
* Sorce Image の画素A は、Col展開上に９か所($A_1$～$A_9$)に 存在します。
![03_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/6442053a-7fb0-166b-ba87-7d42f49f53df.png)




## 画素配置変換 (Col展開 → Image)
* 先ほどとは逆に、Col展開 から Image状 に戻す方法です。
* 逆伝播で dIn を算出する際に 使用します。　
* 先ほどの Col展開 の図を用います。

![04_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/c534f3e9-e9ee-a235-dd12-a2b53c1859f1.png)

---
* 左端を開始列とします。
* 注目列 を ３ｘ３に戻します。

![04_2.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/564a1455-07d4-67ff-c1ec-23c1bc925048.png)

---
* 注目列を1つ左に移します。
* 注目列 の ３ｘ３に戻します。　
* Destination Image に 加算 します。

![04_3.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/6f04f088-c241-cb0d-6105-513936274568.png)

---
* 同様に、注目列を1つ左に移します。
* 注目列 の ３ｘ３に戻します。　
* Destination Image に 加算 します。

![04_4.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/41cece63-5575-5199-4c88-f79dbb6b1132.png)

* 注目列が Col 展開の右端に達するまで繰り返します。

### 補足
* Image 状に戻し終わった際、画素$A$の値は $A_1$～$A_9$ の総和 となります。

## MCMK × MiniBatch
チャンネル と MiniBatch の col 展開の配置を 下図に示します。  

![05_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/091d157a-64dc-99db-7c50-38d07ff18bb0.png)

## 順伝播

![03_02_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/2d2dad0a-ee28-3087-36c4-e48c6d3bb421.png)

* Bias 値を Out に BoradCast します。
* 下記の行列演算で、Convolution処理となります。

![06_1.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/a42df65b-5418-ca6e-468a-23b621f2ecc7.png)

* 行列演算は BLAS の gemm関数がお勧めです。

## 逆伝播

![03_04_0.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/a2a5acfc-9793-ef51-2d19-5788efb0f60d.png)

* 画素の傾きdIn , Weightの傾きdW , Biasの傾き dB を順に図解します。

### dIn
* $dIn = Weight^T × dOut$

![06_2.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/812b2620-a3fc-2063-e0e8-e0e0c25b06f1.png)

* Col展開(dIn) は Image状に戻し、前層に伝達します。

### dW
* $dW = In^T × dOut$ 

![06_3.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/9d1932e9-ad94-cf72-096b-ff96257a26b0.png)



### dB
* dB は Channel 毎の dOut の総和です。
 
![06_4.PNG](https://qiita-image-store.s3.amazonaws.com/0/169589/0ba29ad3-c516-cfe8-9d51-61cf5d774094.png)


## 補足
* cudnn の Convolution関数はアルゴリズムは選択可能になっており、その中の１つが この im2col 方式の様です。


---
ここまで読んで頂き、ありがとうございます。