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.

         

New comment

comments powered by Disqus