[EDIT] This post was migrated from my blog from 2011…
I talked about several strategies to optimize convolutions in some of my previous posts. I still got to talk about how to approximate a Gaussian blur using a multi-step Box blur in a future post. However, there is yet another good technique to optimize a Gaussian blur that may come handy in some cases.
This post is inspired by a need that I had some days ago: Say that you need to do a 3D Gaussian blur on a potentially humongous 3D data buffer. Working with downsampled data sounds ideal in terms of storage and performance. So that’s what I am going to talk about here:
What happens when downsampled data is used as input for a Gaussian blur?
Here’s the 0-centered and un-normalized 1D Gaussian function:
The sigma parameter in the Gaussian function stretches the bell shape along the x axis. So it is quite straightforward to understand that if one downsamples the input dataset by a scale factor k, then applies a (smaller) Gaussian where sigma’=s/k, and finally upscales the result by the same scale factor k, the result will approximate a true Gaussian on the original dataset where sigma=s.
In cleaner terms: if one has an input dataset (e.g., an image) I and wants to have it blurred by a Gaussian where sigma=s:
- I’<=I downsampled by a certain scale factor k.
- I”<=I’ blurred by a small Gaussian where s’=s/k.
- I”’<=I” upscaled by a scale factor k.
How good is this approximation?
The Sampling Theorem states that sampling a signal at (at least) twice its smallest wavelength is enough. Which means that downsampling cuts frequencies above the Nyquist limit (half the sampling rate). In other words: Downsampling means less data to process, but at the expense of introducing an error.
Fortunately, a Gaussian blur is a form of low-pass frequency filter. This means that blurring is quite tolerant to alterations in the high part of the frequency spectrum.
In the examples below I am downsampling with a simple pixel average, and I am upscaling with a simple bilinear filter. The 2x2 grids below compare:
- Top-left – The original image I.
- Top-right – I downsampled and upscaled by k (note the blocky bilinear filter look).
- Bottom-left – The resulting image I”’.
- Bottom-right – I blurred by a true Gaussian where sigma=s.
In these examples, k=sigma was chosen for simplicity. This means that the small Gaussian uses sigma’=1.
Gaussian blur where sigma=4
Gaussian blur where sigma=16
Gaussian blur where sigma=64
As shown, the approximation (bottom-left vs. bottom-right) is pretty good.
The gain in speed depends on multiple implementation factors. However, as I explained above, this post was inspired by a need to cope with a cubic memory storage problem when doing Gaussian blurs on a 3D buffer. Working with a heavily downsampled buffer clearly helps in that sense. And it is needless to say that decreasing the amount of data to process by k^3 also brings a dramatic speed boost, making it possible to use tiny separable convolutions along the 3 (downsampled) axes.
Note that one might pick any downsampling scale factor k>=1. The higher the value of k, the higher the approximation error and the smaller and faster the convolution.
The choice k=sigma offers a good trade-off between approximation error and speed gain as shown above.