back
Blurring

by Tim "Azure" Böscke

This small tutorial is based on a few newsgroups postings I did recently. I just did some copy&paste and added some glue. I thought you might be interested in the postings.

This text is about applying lowpass filtering to 2D arrays aka blurring 2D images. I assume that you know the idea behind blurring and filter kernels.

Optimizing box (boxcar) filtering.

A box filter is a filter with a kernel similar to f(x,y)=1. Basically it means that you sum up all pixels in a box (square region of the image) and divide the sum by the number of pixels.

One very simple way of optimizing this filter is doing two passes. One horizontal and one vertical pass. This is possible when the 2D kernel can by expressed by the product of two 1D kernels. In this case the 2D kernel is f(x,y)=1*1. Really trivial: f(x,y)=fh(x)*fv(y) with fh(x)=1 and fv(y)=1.

There is another way of getting even more speed out of this simple filter. It requires and add, a sub and a division per pixel (per 1D pass) independent of the kernel size. The division can be optimized to a multiplication.

The idea is quite simple. Code for a normal boxcar filter of size 5:

for (x=xleft; x<xright; x++)
{
    int sum=0;
    for (kernel=-2; kernel<=2; kernel++)
        sum+=source[x+kernel];

    dest[x]=sum/5;
}

By taking a close look it becomes quickly obvious that we sum up almost the same terms for adjacent pixels. Just the leftmost pixel drops out and at the rightmost position of the kernel a new pixel comes in..

Source:

/* initializing (calculating the first pixel in the tradional way)*/

int sum=0;
for (kernel=-2; kernel<=2; kernel++)
        sum+=source[xleft+kernel];

dest[xleft]=sum/5;

for (x=left+1; x<right; x++)
{
    sum-=source[x-3];    // subtract left pixel
    sum+=source[x+2];    // add right pixel

    dest[x]=sum/5;
}

Of course this does work for arbitrary sized filters. Special case code for the left and right border has to be added aswell, but you also dont get around this with the traditional boxcar filter.

This technique can be used for realtime filters with adjustable blur amount. I dont want to see more precalculated blurrers from now on ;)

Simple and fast gaussian blurring.

Gaussian blurring is a much better way of blurring. People like it because it has lots of nice properties (which i will not discuss here) but if you want perfect natural blurring - use gaussian blurring.

The kernel funktion is f(x,y)=1/(o*sqrt(2*pi))*exp(-(x^2+y^2)/(2*o^2)). This looks probably annoying to you but luckily things get a lot easier.

The gauss function can be approximated by the pascal triangle. This makes gauss filtering quite simple, because the pascal triangle can be computer recursively. Everything we have to do for a 1D filter is to apply a [1 2 1] filter to our array for several times. With each further recursion the blur radius is increased by one pixel.

/* Recursive gaussian filter */


for (int r=0; r<radius; r++)
{
    int lpixel=source[left-1];
    int cpixel=source[left];
    for (int x=left; x<right; x++)


            int rpixel=source[x+1];
            int sum=lpixel+(cpixel<<1)+rpixel;
            lpixel=cpixel;
            cpixel=rpixel;
            source[x]=sum>>2;
    }
}

For a full 2D filter this code has to be applied both on the lines and columns of the image.