# Convolution

There are different types of Convolution in CNN such as

* 2D Conv, 3D Conv
* 1x1 Conv, BottleNeck
* Spatially Separable
* Depthwise Separable
* Grouped Convolution
* Shuffled Grouped

Read the following blog for more detailed explanations on types of convolution

{% embed url="https://towardsdatascience.com/a-comprehensive-introduction-to-different-types-of-convolutions-in-deep-learning-669281e58215" %}

## Convolution: single channel

It is the element-wise multiplication and addition with window sliding.

Read the followings for more detailed information

* [Intuitive Understanding of Convolution](https://towardsdatascience.com/intuitively-understanding-convolutions-for-deep-learning-1f6f42faee1)
* [Guide to convolution arithmetic for deep learning](https://arxiv.org/abs/1603.07285)

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-0ee61935bf31857134fbd96bdbf794fceeb34158%2Fimage%20\(181\).png?alt=media)

![Convolution for a single channel. Image is adopted from medium@IrhumShafkat](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-ff5b2fdecff0a4e6f50e9b7575b768a848be1ac8%2Fimage%20\(188\).png?alt=media)

Using 3x3 kernel. from 5x5=25 input features --> 3x3=9 output.

Common techniques in convolution

* Padding: pad the edges with '0','1' or other values
* With padding: WxHxC --> WxHxC
* Without padding: WxHxC -> (W-w+1)x(H-h+1)xC

![Two-dimensional cross-correlation with padding](https://d2l.ai/_images/conv-pad.svg)

image from[ here](https://d2l.ai/chapter_convolutional-neural-networks/padding-and-strides.html)

![Same padding\[1\]](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-f730a8cf39fed772390d8b754fb3c0e651058811%2Fimage%20\(186\).png?alt=media)

* Striding: skip some of the slide locations
* ⌊(nh−kh+ph+sh)/sh⌋×⌊(nw−kw+pw+sw)/sw⌋.
* With padding: WxHxC  (W+S-1)/S x (H+S-1)/S x C Without padding: WxHxC  (W-w+S)/S x (H-h+S)/S xC

![Cross-correlation with strides of 3 and 2 for height and width, respectively.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-431ba4c7095dd41008b86470fd065abf9180c55d%2Fimage%20\(234\).png?alt=media)

![A stride 2 convolution w/o padding \[1\]](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-8564687d29dd60c3e686452143fb5a3a1565aa96%2Fimage%20\(179\).png?alt=media)

### Filter vs Kernel

For 2D convolution, kernel and filter are the same

For 3D convolution, a filter is the collection of the stacked kernels

![Image fDifference between “layer” (“filter”) and “channel” (“kernel”)or post](https://miro.medium.com/max/1524/1*NCDUVdTGF3hu6zrzdYFqJA.png)

## 2D Convolution: multiple channel

The filter has the same depth (channel) as the input matrix.

The output is 2D matrix.

Example: Input is 5x5x3 matrix. Filter is 3x3x3 matrix.

![The first step of 2D convolution for multi-channels: each of the kernels in the filter are applied to three channels in the input layer, separately. The image is adopted from this link.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-7b0af5636fc280dc296c3dc5997dd8c7c24a9a43%2Fimage%20\(191\).png?alt=media)

Then, three channels are summed by element-wise addition to form one single channel (3x3x1)

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-b182ff15bc724894a6793a8e4c1b40be6ff4b275%2Fimage%20\(185\).png?alt=media)

![Another way to think about 2D convolution: thinking of the process as sliding a 3D filter matrix through the input layer. Notice that the input layer and the filter have the same depth (channel number = kernel number). The 3D filter moves only in 2-direction, height & width of the image (That’s why such operation is called as 2D convolution although a 3D filter is used to process 3D volumetric data). The output is a one-layer matrix](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-02ada85eba549fd73290843f1e3858345e84bc20%2Fimage%20\(177\).png?alt=media)

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-d777e5f8ff2675d264bc03aa3977eeae2ddb0a07%2Fimage%20\(229\).png?alt=media)

## 3D Convolution

A general form of convolution but the filter _kernel size < channel size. The filter moves in three directions: height, width, channel_

The output is 3D matrix.

![In 3D convolution, a 3D filter can move in all 3-direction (height, width, channel of the image). At each position, the element-wise multiplication and addition provide one number. Since the filter slides through a 3D space, the output numbers are arranged in a 3D space as well. The output is then a 3D data.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-c3876d816eb7a1df246babf8e0624adca4f2b2e5%2Fimage%20\(176\).png?alt=media)

## 1D Convolution

Input: HxWxD. Filtering with 1x1xD produces the Output' HxWx1

![1 x 1 convolution, where the filter size is 1 x 1 x D.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-19ff70553ccd146184505092dc39838e35bc9cc8%2Fimage%20\(182\).png?alt=media)

Initially, proposed in 'Network-in-Network (2013)' . Widely used after introduced in 'Inception (2014)'

* Dimensionality reduction for efficient computations
  * HxWxD --> HxWx1
*   Efficient low dimensional embedding, or feature pooling

    \*
* Applying nonlinearity again after convolution
  * after 1x1 conv, non-linear activation(ReLU etc) can be added

## Cost of Convolution

Calculation cost for a convolution depends on:

1. Input size: i\*i\*D
2. Kernel Size: k\*k\*D
3. Stride: s
4. Padding: p

The output image ( o\*o\*1 ) then becomes

![For output o\*o.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-7b872f26fd11d255874382bf29ca64e6075bcd91%2Fimage%20\(183\).png?alt=media)

The required operations are

* o\*o repetition of { (k\*k) multiplications and (k\*k-1) additions}

In terms of multiplications

* For input of size H x W x D, 2D convolution (stride=1, padding=0) with Nc kernels of size h x h x D, where h is even
* Total multiplications: Nc x h x h x D x (H-h+1) x (W-h+1)

## Separable Convolution

Used in [MobileNet(2017)](https://arxiv.org/abs/1704.04861), [Xception(2016)](https://arxiv.org/abs/1610.02357) for efficient processing.

### Spatially Separable Convolution

Not used much in deep learning. It is decomposing a convolution into two separate operations

Example: A Sobel kernel can be divided into a 3 x 1 and a 1 x 3 kernel.

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-922edbbf488bab452aec21b88f0d90df7829fd45%2Fimage%20\(180\).png?alt=media)

![Spatially separable convolution with 1 channel.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-cb485e3a5334c6d72c83453bc54ce33938e975f0%2Fimage%20\(184\).png?alt=media)

### **Depthwise Separable Convolution**

Commonly used in Deep Learning such as MobileNet and Xception. It is two steps of (1) Depthwise convolution (2) 1x1 convolution

For example: Input 7\*7\*3 --> 128 of 3\*3\*3 filters --> 5\*5\*128 output

* Step1: Depthwise convolution
  * Each layer of a single filter is separated into kernels. (e.g. 3 of 3x3x1)
  * Each kernel convoles with 1 channel(only) layer input : (5\*5\*1) for each kernel
  * Then, stack the maps to get the final output e.g. (5\*5\*3)

![Depthwise separable convolution — first step: Instead of using a single filter of size 3 x 3 x 3 in 2D convolution, we used 3 kernels, separately. Each filter has size 3 x 3 x 1. Each kernel convolves with 1 channel of the input layer (1 channel only, not all channels!). Each of such convolution provides a map of size 5 x 5 x 1. We then stack these maps together to create a 5 x 5 x 3 image. After this, we have the output with size 5 x 5 x 3.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-bcf01c148cce18da9c8cd17c9e5e7c42dd2bea37%2Fimage%20\(178\).png?alt=media)

* Step 2: 1\*1 Convolution
  * Apply 1\*1 convolution with 1\*1\*3 kernels to get 5\*5\*1 map.
  * Apply 128 of 1x1 convolutions to get 5\*5\*128 map

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-4d68bddd79f8f0dd34fa957a0c1c58f87f1ff16b%2Fimage%20\(193\).png?alt=media)

![Depthwise separable convolution — second step: apply multiple 1 x 1 convolutions to modify depth.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-ca176f613875200e881b6204d070418607cea697%2Fimage%20\(175\).png?alt=media)

* Standard 2D convolution vs Depthwise Convolution

![Standard 2D convolution](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-10e3a2139d6417f350fd34dd94a7e4909941d651%2Fimage%20\(190\).png?alt=media)

![The overall process of depthwise separable convolution.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-8868b99027f543a0dc51ffa1a1427c7a6e62be55%2Fimage%20\(189\).png?alt=media)

Calculation comparison

* Standard: 128\*(3\*3\*3)\*(5\*5) multiplications
  * 128\*(3\*3\*3)\*(5\*5) =86,400
  * Nc x h x h x D x (H-h+1) x (W-h+1)
* Separable: 3\*(3\*3\*1)\*(5\*5)+128\*(1\*1\*3)\*(5\*5) multiplications
  * \=675+9600=10,275 (12%)
  * D x h x h x 1 x (H-h+1) x (W-h+1) + Nc x 1 x 1 x D x (H-h+1) x (W-h+1) = (h x h + Nc) x D x (H-h+1) x (W-h+1)
* The ratio of multiplication is

![](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-62df0e43bc2acd3a40aa646ec9346f4a50b04080%2Fimage%20\(187\).png?alt=media)

* If Nc>>h, then it is approx. 1/(h^2). for 5x5 filters, 25 times more multiplications

## Grouped Convolution

Introduced in AlexNet(2012), to do parallel convolutions. The filters are separated into different groups. Each group is responsible for standard 2D conv with certain depth. Then the each outputs are concetenated in depth-wise

![Grouped convolution with 2 filter groups](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-00cad677cce9710944c2cd8ada04d4447d706c3e%2Fimage%20\(192\).png?alt=media)

* Model-Parallelization for efficient training
  * each group can be handled by different GPUs
  * Better than data parallelization using batches
* Efficient Computation
  * Standard: h x w x Din x Dout
  * Grouped: 2\*(h x w x Din/2 x Dout/2)= (1/2)\*(h x w x Din x Dout)

## Shuffled Grouped Convolution

Introduced by[ ShuffleNet(2017)](https://arxiv.org/abs/1707.01083) for computation -efficient convolution. The idea is mixing up the information from different filter groups to connect the information flow between the channel groups.

Read [this blog ](https://towardsdatascience.com/review-shufflenet-v1-light-weight-model-image-classification-5b253dfe982f)for the paper explanations

![Channel shuffle.](https://3883264845-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MR8tEAjhiC8uN1kHR2J%2Fuploads%2Fgit-blob-c6725c96eea6f9befed0f1b704da497398380330%2Fimage%20\(199\).png?alt=media)

## Pointwise grouped convolution

The group operation is performed on the 3x3 spatial convolution, but not on 1 x 1 convolution. The ShuffleNet suggested 1x1 convolution on Group convolution

> Group convolution of 1x1 filters instead of NxN filters (N>1).
