Jump to content

Gaussian Blurs: The Math


Recommended Posts

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.

~~

Link to comment
Share on other sites

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.

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

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.

~~

Link to comment
Share on other sites

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.

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

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

~~

Link to comment
Share on other sites

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 :)

The Paint.NET Blog: https://blog.getpaint.net/

Donations are always appreciated! https://www.getpaint.net/donate.html

forumSig_bmwE60.jpg

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

×
×
  • Create New...