Gaussian Blurs: The Math

[Illnab1024]

I got bored and decided to look and see what is behind my beloved Gaussian blur.

Now I know.

Firstly, the equation for weighting alone is intimidating. I put it in my graphing calculator, it took a nice time calculating it.

r is the radius, p is the distance from pixel being calculated

(1/(r*sqrt(2*pi)))*(e^((-p^2)/(2r^2)

So what goes through your computer is: take the square root of 2 * pi, multiply by the radius, and then divide 1 by the result. Multiply that by e to the power of negative p (rendered by distance formula (see below)) squared divided by 2 times the radius squared.

The distance formula is also calculated to find p when rendering the blur for the pixel. d = sqrt(dx^2 + dy^2)

Basically, this amounts to a lot of CPU load.

And the amount of load can be described by the last part of the formula (2r^2). For a 10 pixel blur, this is 400. For a 100 pixel blur, this is 40000.

And now comes rendering.

Using a weight matrix generated by the above equation, every channel of each pixel in the image will be calculated by returning a weighted average of every single channel of each original pixel in the blur radius.

Now Paint.NET steps in and sends the rbga data to a renderer that displays this on your monitor.

EDIT: I am not exactly sure whether Paint.NET generates a weight matrix or (more likely) calculates the weighting for every pixel's channel that it needs to.

[13_15_4_14_1_18]

I have no idea what that meant, but cool.

[Illnab1024]

My edit makes me think: Would there be possibility to precreate an array to serve as a matrix for pixels in the blur? Would this speed up the blur?

(Aimed at Rick)

[Rick Brewster]

C'mon man, have you even looked at BlurEffect.cs in the source code? The code I wrote implements all sorts of tricks and wizardry to be fast, you're underestimating me It has linear efficiency with respect to blur radius; it's O(n) and not O(n^2), where n is the blur radius. Of course things are precalculated. There's no way I'd be calculating square roots and exponents for each output pixel. It's all integer math. (It is, however, 64-bit math -- if you're on a 64-bit CPU + 64-bit OS, you will see a 300% speedup, http://blogs.msdn.com/rickbrew/archive/ ... 34394.aspx).

The Photoshop guys just have some proprietary magic sauce that makes things super fast even with a large blur radius.

[Illnab1024]

Okay...not that slow, and no, I only glanced (skimmed over) the source code.

Okay, so half of the topic is now irrelevant (and wrong).

And in no way do I mean to imply that PdN can achieve PhotoShop performance standards.

What I was meaning in this topic was to explain the math and how much processing is required for a Gaussian blur.

[Rick Brewster]

Paint.NET may or may not be able to achieve Photoshop-level speeds ... I don't know what algorithm they're using, or if it's even compatible with our effect framework. It's probably under heavily guarded lock and key Paint.NET's blurring seems very slow in comparison, it's just a fact.

The algorithm you describe is a general convolution filter, and is how Paint.NET v2.1 and before implemented Gaussian Blur. The way we do this in v2.5 and later is to do a weighted vertical sum and then use those values to do a weighted horizontal sum. Many of these computations can be carried over from one pixel to the next, so we don't have to recompute a lot of stuff. There's some inefficiency I'm seeing that would be interesting to try and eliminate, what with a bunch of extranneous memory copying, I'd be curious to find out how much more speed I can wring out of this code.

[Illnab1024]

Something I know is that many times when blurring, there is no need to blur the alpha channel. A way to figure if the alpha channel of the whole image is all 255, 128, et cetera, would save a bit of time, although this could become useless for small images.

The PdN blur method seems similair to something I saw earlier: http://incubator.quasimondo.com/processing/gaussian_blur_1.php

[Picc84]

ok i abviously was not ment to click on this thread.... wow, now my head hurts...

[Rick Brewster]

Something I know is that many times when blurring, there is no need to blur the alpha channel. A way to figure if the alpha channel of the whole image is all 255, 128, et cetera, would save a bit of time, although this could become useless for small images.

So you're proposing to make two passes through the image, thus incurring twice the memory bandwidth. I doubt that would be faster; even if you were clairvoyant and could just assume that the image was all 255 alpha, you would only save up to 25% of the computations, but you'd still have the same memory bandwidth requirements. So it wouldn't really be that much faster.

These days, memory is often relatively quite slow compared to the insatiable demands of the code that's executing. And then the hard drive is glacially slow. Which is why developers like me abhor disk access and cherish L1/L2 cache hits

[aatwo]

lol picc 84 I am supposeed to be attemptiong maths with computer science at university yet the very thought of this post makes my brain implode like a ham sandwhich sellotaped to a mans head. I only hope that jesus will help me through these troubling times.

[Rick Brewster]

More info to make your head explode:

http://en.wikipedia.org/wiki/Gaussian_blur

[trickman]

Whee! Head go boom!!!!

[TKN]

amagad i don't belive that some1 could be interested in that O.o makes my head hurt... nerd