07 November, 2013

# Tutorial on 2D convolution of images

• How convolution can be done in two dimensions?
• Can you show me an example and explanation of the 2D convolution?
• How can two dimensional convolution be done in MATLAB?

In a previous post the basics of convolution was already discussed with some examples. It would be worth to have a look at that short discussion before reading this article.

## Discussing the 1D convolution again

Instead of explaining the definition for the 2D convolution, here is the formula for the 1D convolution again:

$$y_{k} = \sum_{n = 0}^{N - 1}h_{n}\,\cdot\,x_{k-n}$$

There are two input signals, x and h, while N is the number of elements in h. The output vector is y. The subscripts denote the nth element of the vector.

Convolution does the basically the following: we have a so-called kernel denoted by h. We reverse the order of its elements, and slid it along the input x signal. In each step the appropriate elements are multiplied and summarized: this result will be the output value for the current point. See the example below:

\begin{aligned} x & = \left[ \begin{array}{c} 1 \, 2 \, 1 \, 3 \end{array} \right] \\ h & = \left[ \begin{array}{c} 2 \, 0 \, 1 \end{array} \right] \end{aligned} \\ \begin{array}{c|cccccccc|r} k & \it{0} & \it{0} & 1 & 2 & 1 & 3 & \it{0} & \it{0} & \it{y_{k}}\\ \hline 0 & 1 & 0 & 2 & & & & & & 2 \cdot 1 = 2\\ 1 & & 1 & 0 & 2 & & & & & 2 \cdot 2 = 4\\ 2 & & & 1 & 0 & 2 & & & & 2 \cdot 1 + 1 \cdot 1 = 3\\ 3 & & & & 1 & 0 & 2 & & & 2 \cdot 3 + 1 \cdot 2 = 8\\ 4 & & & & & 1 & 0 & 2 & & 1 \cdot 1 = 1\\ 5 & & & & & & 1 & 0 & 2 & 1 \cdot 3 = 3\\ \end{array}

Zeros are supposed where x is not defined – in case of negative indices or overindexing. The reversed h vector is slid along, the multiplications and additions are visualized in the yk column.

## Extending the convolution into the 2D space

Two dimensional convolution does exactly the same. Suppose, that we have a 3×3 kernel:

$$h = \left[\begin{array}{ccc}1 & 2 & 3 \\ 0 & 0 & 0 \\ 6 & 5 & 4\end{array}\right]$$

When doing convolution, this kernel has to be flipped both in vertical and horizontal direction. Denote this flipped kernel by f:

$$f = \left[\begin{array}{ccc}4 & 5 & 6 \\ 0 & 0 & 0 \\ 3 & 2 & 1\end{array}\right]$$

When doing 2D convolution, this 3×3 window will be put on each pixel of the input image: the coherent elements will be multiplied and then summarized.

Suppose that we have an I input image of the following pixel values:

$$I = \left[\begin{array}{ccc}1 & 5 & 2 & 3 \\ 8 & \color{red}{7} & \color{blue}{3} & 6 \\ 3 & 3 & 9 & 1\end{array}\right]$$

Then the result of the convolution for the red-marked point will be the following:

$$\left[\begin{array}{lll}1 \cdot \color{green}{4} \quad 5 \cdot \color{green}{5} \quad 2 \cdot \color{green}{6} \\ 8 \cdot \color{green}{0} \quad \color{red}{7} \cdot \color{green}{0} \quad \color{blue}{3} \cdot \color{green}{0} \\ 3 \cdot \color{green}{3} \quad 3 \cdot \color{green}{2} \quad 9 \cdot \color{green}{1}\end{array}\right] \Rightarrow 1 \cdot 4 + 5 \cdot 5 + 2 \cdot 6 + 3 \cdot 3 + 3 \cdot 2 + 9 \cdot 1 = 65$$

And the result for the blue-marked point is:

$$\left[\begin{array}{lll}5 \cdot \color{green}{4} \quad 2 \cdot \color{green}{5} \quad 3 \cdot \color{green}{6} \\ \color{red}{7} \cdot \color{green}{0} \quad \color{blue}{3} \cdot \color{green}{0} \quad 6 \cdot \color{green}{0} \\ 3 \cdot \color{green}{3} \quad 9 \cdot \color{green}{2} \quad 1 \cdot \color{green}{1}\end{array}\right] \Rightarrow 5 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 + 3 \cdot 3 + 9 \cdot 2 + 1 \cdot 1 = 76$$

The elements of the convolution kernel are marked by green colour. The pattern is clear: this operation is done for each pixel of the input resulting an output image.

## 2D convolution in MATLAB

In MATLAB conv2 function in used to do the two-dimensional convolution. It has three parameters: the input array, the kernel, and a string defining the size of the output. There are three different modes of it:

• Option same outputs an array of the same size as the input.
• Option full gives back the whole result.
• Option valid returns those elements only which were fully covered, so there was no sliding off during the windowing.

A usage example doing the calculations as in the previous example is the following:

% define the kernel and the input image
h = [1 2 3;     0 0 0;     6 5 4];
I = [1 5 2 3;     8 7 3 6;     3 3 9 1]

% do the two-dimensional convolution
conv2(I, h, 'same')


The output is:

I =
1   5   2   3
8   7   3   6
3   3   9   1

ans =
23  41  33  21
44  65  76  52
82  85  79  42


Please compare the output with our calculations above: the results are the same.

## A short note on the kernels

Most of the used kernels are symmetric, so flipping of them does not matter really. For example the sharpening kernel remains the same after flipping:

$$h = \left[\begin{array}{rrr}-1 & -1 & -1 \\ -1 & 9 & -1 \\ -1 & -1 & -1\end{array}\right]$$

Some commonly used 3x3 kernels with an interactive online demo will be discussed in the next post.