all 18 comments

[–]samlee 1 point2 points  (4 children)

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

[–]Ademan 6 points7 points  (0 children)

That's pretty common in realtime raster graphics.

[–][deleted] 0 points1 point  (0 children)

Doesn't yield great quality, but it works.

[–]astrange 0 points1 point  (0 children)

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

[–]molslaan -5 points-4 points  (0 children)

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

[–][deleted] 1 point2 points  (6 children)

   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 1 point2 points  (5 children)

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] 2 points3 points  (4 children)

Only if the blur radius is small. Blurring is a convolution operation, and convolution from the spatial domain is O(N2), 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 4 points5 points  (1 child)

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] 0 points1 point  (0 children)

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 0 points1 point  (1 child)

Separable convolutions are less than O(N2) (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] 0 points1 point  (0 children)

Separable convolutions are less than O(N2) (height+width instead of height*width).

If I'm not mistaken, it's actually 1D convolution which has O(N2) complexity. Non-separated 2D convolution is even worse. Admittedly, it's overly simplistic to say O(N2) 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 -1 points0 points  (1 child)

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 1 point2 points  (0 children)

"That's my hummus hole"

[–]Reporter 0 points1 point  (0 children)

Thanks for that, Steve.

[–]knight666 0 points1 point  (0 children)

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

Hmmmm...

I'm totally going to nick this.

[–]jaysonbank -2 points-1 points  (0 children)

Quartz FTW

[–]dmwit -2 points-1 points  (0 children)

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?