Convolution

Published May 19, 2022 - By Marco Garosi

You can find an introduction to signals here. This post is part of a series on Image and Signal Processing. If you are looking for cross-correlation, you may find it here.

Convolution is the operation that express how the shape of a function $f_1$ is modified by the shape of a function $f_2$ .

Mathematical definition

Convolution is mathematically defined as:

[f_1 * f_2](t) = \int_{-\infty}^{+\infty} f_1(\tau) f_2(t - \tau) d\tau

Cross-correlation formula

Convolution vs cross-correlation

Convolution and cross-correlation share a deep interconnection. Their mathematical definition are pretty similar. At a quick glance, they may seem identical indeed. They are not, however. Convolution, indeed, overturns the second signal $f_2$ : this is achieved through that $- \tau$ . Since $\tau$ is the variable we are integrating with respect to, making it negative results in $f_2$ being overturned.

Rewriting $f_2(t - \tau)$ as $f_2(-\tau + t)$ may help visualize it a little better.

Discrete convolution

Computers work with discrete set of values. That is why we use discrete convolution, which is defined as:

[x_1 * x_2](n) = \sum_{k = -\infty}^{+\infty} x_1(k) x_2(n - k), k \in \Z

Discrete convolution

If $x_1$ has length $M$ and $x_2$ has length $N$ , then the discrete convolution $*$ is going to have length $M + N - 1$ .

Convolution with images

Images can be though of as 2D signals. In fact, $image(m, n) = z$ , where $m$ and $n$ are the pixel coordinates and $z$ is the grayscale or RGB value of that pixel $(m, n)$ .

It is therefore possible to compute the discrete convolution between two images — call them $x_1$ and $x_2$ . Formula is:

[x_1 * x_2](m, n) = \sum_{u = -\infty}^{+\infty} \sum_{-\infty}^{+\infty} x_1(u, v) x_2(m - u, n - v)

Discrete 2D convolution

2D convolution is very useful in filtering, since one of its most important properties states that a convolution in the spacial domain (which, as you may see, is pretty expensive to compute) becomes a simple multiplication in the frequency domain thanks to the Fourier transform (and vice-versa). This leads us to write pretty powerful and efficient implementation of convolutions in space. Assuming the filter we want to apply is already in the frequency domain: 1) transform the image in the frequency domain; 2) compute the multiplication of the two matrices; 3) transform back to the spacial domain, to get the filtered image.

Thanks to the deep connection with cross-correlation, it is also possible to apply this technique when we have to compute cross-correlations as well: you just have to “invert” the signal — or rotate it 180°, for images — in order to be able to apply the previous “pipeline”.