The picture shows a two-dimensional cross-correlation operation with a stride of 3 vertically and 2 horizontally. 
The shaded portions are the output elements as well as the input and kernel tensor elements used for the output computation: 
 0×0+0×1+1×2+2×3=8 ,  0×0+6×1+0×2+0×3=6 . 

We can see that when the second element of the first column is outputted, the convolution window slides down three rows. The convolution window slides two columns to the right when the second element of the first row is outputted. When the convolution window continues to slide two columns to the right on the input, there is no output because the input element cannot fill the window (unless we add another column of padding).

Strided Convolution Example

i. Lesser Memory needed for output

ii. Processing of output is easier as the volume is smaller

iii. The output *spatial dimensions* are smaller, which when given as an input to the next layer, simplifies the model.

iv. It avoids **overfitting** especially in case of image processing having a large no. of attributes.

Advantages of Strided Convolution

Input size $= n_h^{[l-1]} \times n_w^{[l-1]}$
Kernel size $= k_h \times k_w$
Stride size $= s_h \times s_w$
Padding size $= p_h \times p_w$

Output size $= n_h^{[l]} \times n_w^{[l]}$
$$n_h^{[l]} = \left \lfloor{ \frac{n_h^{[l-1]} + 2p_h^{[l]} − k_h^{[l]}}{s_h^{[l]}}}\right \rfloor + 1$$
$$n_w^{[l]} = \left \lfloor{ \frac{n_w^{[l-1]} + 2p_w^{[l]} − k_w^{[l]}}{s_w^{[l]}}}\right \rfloor + 1$$

Output Size of Strided and Padded Convolution

Note: Standard convolution, in this case, implies 0 padding and a stride of 1

1. Every convolution operation layer being applied would shrink the image further to a point where the final image size would then end up being 1x1. This essentially puts a hard limit on the number of convolution layers that a model can have.
2. Border pixels get used very little in the convolution operation as compared to other parts of the input and, as a result, the same effect gets propagated further down the layers. 



The downsides of the standard convolution method

When computing the cross-correlation, we start with the convolution window at the top-left corner of the input tensor, and then slide it over all locations both down and to the right. Usually, we default to slide one element at a time. However, sometimes, either for computational efficiency or because we wish to down-sample, we move our window more than one element at a time, skipping the intermediate locations.

We refer to the number of rows and columns traversed per slide as the stride.

University of Michigan - Ann Arbor

- The convolution operation, denoted by the asterisk (*), indicates mapping the filter matrix (kernel) to every possible position on the input matrix, multiplying each of the pairs of numbers, elementwise, and adding them up to calculate the corresponding element in the result matrix.


- In mathematics, the asterisk is the standard symbol for convolution but in Python, this is also used to denote multiplication or elementwise multiplication.


- Traditionally, the convolution operation before its application has a kernel mirroring step (left to right, and up to down). This allows associativity across convolutions to hold. In deep learning, this mirroring doesn't have a significant impact on the operations and thus is omitted. Also when the kernel is symmetric, the operations are identical. Hence, convolution in deep learning refers to cross-correlation. 

The Cross-Correlation (Convolution) Operation

This node before explained how it works, and now we need to understand how to write the operation mathematically and more importantly code it efficiently. So suppose we have the input I with the shape H x H x C, where B - the batch, H - is the height and width of the image( just taking square image for the example), C - the amount of channels. One kernel k has a size of K x K x C( also taking square kernel for the sake of the example). b is the bias for that kernel

$ ( I * K)_{i,j} = \sum_{m=0}^{k-1} \sum_{n=0}^{k-1} \sum_{c=0}^{C} K_{m,n,c} I_{i + m, j + n, c} + b$
-------------------------------------------------
$ ( I * K)$ - is the output matrix for the current kernel with size of H-K+1, H-K+1. This is the variation of the Convolution with no padding and stride one. Most of the libraries call it convolution but it is actually an operation called cross-correlation. In terms of coding the formula for convolution, there are several ways to implement it. One of them might be just straight brute force with nested loops, turning everything int a big matrix multiplication, and even using Fourier transforms. While brute force solution is straight forward, other two ways are not that easy to visualize and understand


Mathematical Implementation of Forward Propagation

Here is the visualization of the convolution operation were you can play with different hyperparameters of CNN:
https://ezyang.github.io/convolution-visualizer/index.html

Convolution Visualizer

On the left, we have a 6 x 6 grayscale image, so we represent it using a 6 x 6 x 1 matrix because there are no separate RGB channels. To detect vertical edges, we construct a 3 x 3 matrix, called filter or kernel, shown in the middle. We convolve the 6 x 6 matrix with the 3 x 3 filter. The output of this convolution operator will be a 4 x 4 matrix.

To compute the upper left element of this 4 x 4 matrix, we take the 3 x 3 filter and paste it on top of the 3 x 3 region of the original input image and sum up all the 9 the element-wise products. So, the result would be 3 x 1 + 1 x 1 + 2 x 1 + 0 x 0 + 5 x 0 + 7 x 0 + 1 x (-1) + 8 x (-1) + 2 x (-1) = -5. Next, to compute the second element, we shift the pasted filter matrix one step to the right on the 6 x 6 image, do the same element-wise products, and then add them up, which will give us -4, and so on.

To compute the next rows, we shift the pasted filter matrix one step down on the 6 x 6 image. Then, we repeat the same element-wise products, and additions for the second row, and so on.

Calculating Cross-Correlation (Convolution) Operation Example

Since kernels generally have width and height greater than 1, after convolving an image by the kernel, the image size will be reduced. By adding padding to the input image, we can have the output with the same size as input.

If we start with a 240×240-pixel image, 10 layers of 5×5 convolutions reduce the image to 200×200 pixels, slicing off 30% of the image and with it obliterating any interesting information on the boundaries of the original image. Padding is the most popular tool for handling this issue.

In the below example, we pad a 3×3 input, increasing its size to 5×5. The corresponding output then increases to a 4×4 matrix. The shaded portions are the first output element as well as the input and kernel tensor elements used for the output computation:  0×0+0×1+0×2+0×3=0.

Padding Convolution

Strided Convolution

Input size: $n_h * n_w$ 
Kernel size: $k_h * k_w$ 
Output size: $(n_h-k_h+1) * (n_w-k_w+1)$

Computation of Convolution Output Size

In the two-dimensional cross-correlation operation, we begin with the convolution window positioned at the top-left corner of the input tensor and slide it across the input tensor, both from left to right and top to bottom.
When the convolution window slides to a certain position, the input subtensor contained in that window and the kernel tensor are multiplied elementwise and the resulting tensor is summed up yielding a single scalar value. This result gives the value of the output tensor at the corresponding location.

Two-Dimensional Convolution Operation Procedure

A 2D convolution layer performs an entry per entry multiplication between the input and the filter, where the input and the filter are 2D matrices. 

In a 3D convolution layer, the same operation is performed on 3D inputs and the filters, such that:
- We multiply corresponding entries in the input and filter cubes and add up the results to determine the output entry.
- In addition to shifting (striding) the filter on two dimensions of the input matrix to perform the convolution operation, we also shift it in the third dimension.

For example, if we have a 4 x 4 x 4 input and a 3 x 3 x 3 filter, because we can shift the filter for only one entry per dimension, the output will be 2 x 2 x 2.

3D Convolution Layers

For example, if we have a 3 x 3 x 3 RGB filter, to perform the convolution operation, we start with placing the filter in the upper left most position of the image. We can consider this 3 x 3 x 3 filter as a cube with 27 parameters, where the first dimension is called "width," the second is called height, and the third indicates the number of channels. We multiply each of these 27 numbers with the corresponding numbers from the red, green, and blue channels of the image and sum up the results to calculate the corresponding output number. Then to compute the next output, we take this cube and slide it over by one, do the 27 multiplications, and add up the results to calculate the next output number, and so on. This way, convolving a 6 x 6 x 3 image with a 3 x 3 x 3 filter will give us a 4 x 4 output.

Learn Before

Related

Learn After