Fastest Gaussian blur implementation

Question

You should use the fact that a Gaussian kernel is separable, i. e. you can express a 2D convolution as a combination of two 1D convolutions.

If the filter is large, it may also make sense to use the fact that convolution in the spatial domain is equivalent to multiplication in the frequency (Fourier) domain. This means that you can take the Fourier transform of the image and the filter, multiply the (complex) results, and then take the inverse Fourier transform. The complexity of the FFT (Fast Fourier Transform) is O(n log n), while the complexity of a convolution is O(n^2). Also, if you need to blur many images with the same filter, you would only need to take the FFT of the filter once.

If you decide to go with using an FFT, the FFTW library is a good choice.

Math jocks are likely to know this, but for anyone else..

Due to a nice mathematical propertiy of the Gaussian, you can blur a 2D image quickly by first running a 1D Gaussian blur on each row of the image, then run a 1D blur on each column.

ULTIMATE SOLUTION

I was very confused by so much information and implementations, I didn't know which one should I trust. After I figured it out, I decided to write my own article. I hope it will save you hours of time.

Fastest Gaussian Blur (in linear time)

It contains the source code, which (I hope) is short, clean and easily rewritable to any other language. Please vote it up, so other people can see it.

1. I found Quasimondo : Incubator : Processing : Fast Gaussian Blur. This method contains a lot of approximations like using integers and look up tables instead of floats and floating point divisions. I don't know how much speedup that is in modern Java code.

2. Fast Shadows on Rectangles has an approximating algorithm using B-splines.

3. Fast Gaussian Blur Algorithm in C# claims to have some cool optimizations.

4. Also, Fast Gaussian Blur (PDF) by David Everly has a fast method for Gaussian blur processing.

I would try out the various methods, benchmark them and post the results here.

For my purposes, I have copied and implemented the basic (process X-Y axis independently) method and David Everly's Fast Gaussian Blur method from the Internet. They differ in parameters, so I couldn't compare them directly. However the latter goes through much fewer number of iterations for a large blur radius. Also, the latter is an approximate algorithm.

You probably want the box blur, which is much faster. See this link for a great tutorial and some copy & paste C code.

For larger blur radiuses, try applying a box blur three times. This will approximate a Gaussian blur very well, and be much faster than a true Gaussian blur.