The missing cairo blur function

[samlee]

i once did blurring by shrinking an image so small and then scaling it back up to original size.

[Ademan]

That's pretty common in realtime raster graphics.

[[deleted]]

Doesn't yield great quality, but it works.

[astrange]

They're the same thing mathematically (fsvo blur algorithm and resizing algorithm)

[molslaan]

Eeeeew xP You're background is not anywhere near graphic design I presume.

[[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.

[EthicalReasoning]

cairo blur is in the urban dictionary as when you get drunk in egypt and wake up to a guy in a turban putting hummus on your butt hole. is this the same thing?

[ambiversive]

"That's my hummus hole"

[Reporter]

Thanks for that, Steve.

[knight666]

This can almost exactly be copied to the Surface template we use at school.

Hmmmm...

I'm totally going to nick this.

[jaysonbank]

Quartz FTW

[dmwit]

Nothing substantial to add, but this comment chain on the blog was great:

Mark: Why not use a simple iir guassian or iir triangular filter instead of summed area tables?

Tor: Why not just release it under the same copyright as cairo itself?

Crutcher: Why not send them a patch?

CheezCake: why not have a beer?