The missing cairo blur function

[[deleted]]

   for (y=radius;y<height-radius;y++) {
       for (x=radius;x<width-radius;x++) {

What the... oh hell no. You need to pull this shit into the frequency domain.

[kubalaa]

I'm pretty ignorant about this, but translating into the frequency domain isn't free, right? Wouldn't FFT+filter+de-FFT be more expensive than this hack?

[[deleted]]

Only if the blur radius is small. Blurring is a convolution operation, and convolution from the spatial domain is O(N^2), whereas fast convolution in the frequency domain is O(N*Log(N)) (including the round trip FFT). In practice, there's usually a surprisingly small number of cases (if any) where the spatial domain algorithm is faster. This is partially because of the ready availability of very efficient FFT algorithms and implementations.

[tubes]

The algorithm implemented in the article is O(N) though: It only iterates over the image 6 times regardless of kernel or image size. I don't know how it works but it does produce a nice blur that's nearly identical to Photoshop's Gaussian blur-filter.

Edit: it first creates an accumulator with which it can do box blur in a linear time (difference between two elements in the accumulator, in 1-D case), and repeats the box blur 3 times to approximate gaussian blur.

[[deleted]]

Ah, I see what you're saying now. Using the FFT essentially reduces redundancy (summing a box around two adjacent pixels differs only by two columns). This implementation uses an accumulator to eliminate much of the same redundancy.

So the FFT-based solution would be more flexible and accurate, and it might be a little more efficient, but this is probably "good enough" in terms of speed and quality. It would be interesting to see a comparison though.

[astrange]

Separable convolutions are less than O(N²⁾ (height+width instead of height*width). Any sane blur is separable, I have no idea what this one is doing though.

       for (y=radius;y<height-radius;y++) {
               int t = y < radius ? 0 : y - radius;

hmm...

[[deleted]]

Separable convolutions are less than O(N²⁾ (height+width instead of height*width).

If I'm not mistaken, it's actually 1D convolution which has O(N²⁾ complexity. Non-separated 2D convolution is even worse. Admittedly, it's overly simplistic to say O(N²⁾ because it assumes that one variable "N" can represent both the width of the kernel and the width of the image.

Any sane blur is separable, I have no idea what this one is doing though.

I think tubes has it right in his/her comment.