What Gaussian blur algorithm is used in Adobe Photoshop?

I'm doing some graphics programming here for fun, so I wrote an

implementation of gaussian blur algorithm. The thing is, no matter

what I do I can't make it run faster than N^2 w.r.t. the length of

convolution vector. The larger the radius the longer the vector, and

with a large radius (say, 5) it takes up to 15 times longer for my

code to blur a 6MP image than the same thing done in Photoshop - 15

seconds instead of one second.

 

One thing I've also noticed about Photoshop is that the speed of its

blur algorithm doesn't depend on the length of convolution vector

all that much. My algorithm is straight convolution, I do dozens of

integer multiplications for each pixel.

 

So the question is, where can I find a description of a faster

algorithm?

The question is a bit incorrect. I know of at least one algorithm that should give me "Photoshop speed" - it uses FFT, and as such is a huge pain in the butt to write. What I really want to know is if there are any clever simple and fast algorithms for one-dimensional convolution.

I can't specifically answer your question, but Paint Shop Pro used to have a slow algorithm (Version 7 and earlier), while Version 8 has a fast algorithm. Most likely someone spent a while programming this (I don't think they will give you the code).

Heh, I'm not asking for the code. I can write code myself. This stuff is very well studied, it's just that I don't want to wait another week or two for the right book to come my way.

If you unroll the matrix appropriately you can do the whole 2d convolution as a single

FFT. I wouldn't be at all surprised if something like this is what Photoshop does. You

don't have to write the FFT part yourself, there's a fast and free one available at

<a href="http://www.fftw.org/">http://www.fftw.org/</a>.

The first thing you should know about the Gaussian Blur is that it is separable and is this means it can be computed in O(n) time rather than in O(n^2) time. In general 2-D symmetric convolution kernels are not separable. To do this you compute the 1-D Gaussian blur in the x dirextion and then do it in the y direction. This is the big secret. The next big speedup is likely to involve redesiging this algorithm based upon memory and optimal assembly language implementation. I remember reading that MMX made for a speadup in the Gaussian blur.

 

But it is the separable part that gets you into linear time.

 

my $0.02,

 

Sean

Or you might start <a href='http://citeseer.nj.nec.com/cs?q=gaussian+blur&cs=1'> at citeseer </a> and see what algorithms you can find. A great search engine, but you may need to refine your search or follow through several references to find something that meets yoru needs. <p>

I've already been doing two separate 1D convolutions, the numbers I've provided above are for this method.

 

After a bit of googling, I've found two algorithms that can do the trick. One of them is just a simple recursive digital filter. Another is based on finite-state machines (resembles filtering, too).

 

I'm going to try the recursive digital filter as it seems to be the fastest approach yielding pretty decent accuracy.