Convolution-based filters

Short tutorial

In image processing, many operators are based on applying some function to the pixels within a local window. That is, when finding the value of an output pixel, a window is centered at that location, and only the pixels falling within this window are used when calculating the value of that output pixel.

When applying the convolution operator, the function we apply is merely a weighted average of the within-window pixels. E.g., in the applet above, the window size is 5x5 pixels, hence we can define the function by providing a 5x5 weight-matrix. So, at the location of every pixel in the image, we place this 5x5 matrix and perform the element-wise multiplications before summing up. This sum is deemed the output value at that location.

If we let \( f \) be the image we want to filter, \( g \) the corresponding output image, and let \( h \) be the convolution kernel (the "flipped" weight matrix), we have: \[ g(x,y) = \sum_{i=-w}^{w} \;\; \sum_{j=-w}^{w} h(i,j) f(x-i, y-j) , \] where the size of the kernel is \( (2w+1) \times (2w+1) \).

The convolution operator is linear, that is, we get the same result if we perform the convolution on two separate images and sum their results as if we were to sum the two images before we apply the convolution.

According to the convolution theorem, applying convolution is equivalent to a per-frequency multiplication in the frequency domain. That is, if we were to change the basis for both the convolution kernel and the image to one that consists of simple sine and cosine functions (applying a discrete Fourier transform), we can take each of these components and multiply them and get the same result. This means that we can take the Fourier transform of the convolution kernel (and study its spectrum) and immediately see which frequencies it will dampen (those having an amplitude <1), strenghten (>1) or leave unchanged (=1). If we have a maximum amplitude value of one, we can say that each of the different frequencies are independently attenuated, that is, we can "filter" the frequency components in an image.

Related links:
Convolution article at wikipedia
Convolution theorem at wikipedia
2D convolution tutorial on songho.ca

Applet instructions

Click the images on the upper right to change the image being processed. Choose between a set of predefined convolution kernels (filters) by clicking on the radio button group next to these image buttons. When "Normal" is checked, the pixel values are displayed with only a linear graylevel scaling making the output have a certain variance and mean value. The same graylevel standardization is done in "Absolute" mode, although negative pixel values are first negated, giving only positive pixel values. Clicking "Spectrum" shows the spectrum of the image; here, the logarithm of the absolute values of the discrete Fourier transform (FFT). You can also manually edit the filter kernels; just type in integers and hit the enter key.

Comments

comments powered by Disqus