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 f1f_1 is modified by the shape of a function f2f_2.

Mathematical definition

Convolution is mathematically defined as:

[f1f2](t)=+f1(τ)f2(tτ)dτ [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 f2f_2: this is achieved through that τ- \tau. Since τ\tau is the variable we are integrating with respect to, making it negative results in f2f_2 being overturned.

Rewriting f2(tτ)f_2(t - \tau) as f2(τ+t)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:

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

Discrete convolution

If x1x_1 has length MM and x2x_2 has length NN, then the discrete convolution * is going to have length M+N1M + N - 1.

Convolution with images

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

It is therefore possible to compute the discrete convolution between two images — call them x1x_1 and x2x_2. Formula is:

[x1x2](m,n)=u=++x1(u,v)x2(mu,nv) [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”.

Share on: