easy.Filter

Efficient Gaussian Blur Algorithm

This pages presents a fast Gausian blur calculation. Details of the algorithm can be read below.

First of all a sample implementation in Filtermeister code: gauss.ffp. This Gaussian Blur source code has the benefits of:

simple: very easy blur calculation
fast: no run time dependency on blur radius
accurate: correct blur calculation of pixel near the boarder
large blur range of floating point radius

Extended Binomial Filter for Fast Gaussian Blur

Abstract

The extended binomial filter algorithm is a very simple and fast Gaussian blur algorithm where the run time per pixel is independent of the blur radius.

The Gaussian blur is a widely used filter for many effects, especially for image processing. It is important to have a fast and easy algorithm for computation. The runtime of most algorithms for calculating the Gaussian blur like the binomial sequence is proportional to the blur radius r. This disadvantage of having a complexity of O(r) per pixel makes such algorithm very slow for larger blur radii.

The extended binomial filter is an approximation of the normal binomial filter with constant complexity O(1), making the runtime per pixel independent of the blur radius. The accuracy of the approximation is chosen by the approximation degree.

Key Features

Constant complexity O(1) per pixel, independent of the blur radius.
Minimum pixel readouts, also independent of the blur radius.
Computation as simple (and fast) as box blur.
Adequate approximation selectable to the desired accuracy.

Paper

A detailed description of the algorithm is available in PDF: gauss.pdf.

Sample implementation

Some example programs of the extended binomial filter for fast Gaussian blur explain the operation of the algorithm in Filtermeister C-code.

If not other stated all example programs work with 8 and 16 bit images in any color mode.

gauss2.ffp: The program for the first degree approximation is a great improvement to the box blur. It is as easy to understand and has only slight approximation error.
gauss3.ffp: The program for the second degree approximation is accurate enough for most applications.
gauss4.ffp: The third degree approximation has nearly no difference to the Gaussian blur for 8-bit images apart of rounding errors.
gaussN.ffp: The arbitrary degree approximation program only tests the algorithm. The implementation is not very efficient because of the use of array functions. It needs at least Filtermeister version 1.0 beta 9.
gauss.ffp: The same program as for the first degree approximation including two improvements: Floating point radius for continus blur instead of integer and correct blur handling of near boarder pixel.

Other programs related to Gaussian blur

Some programs illustrate the use of the Gaussian blur algorithm.

All source code of this site is free and could be used and modified for own applications.

Edge detection

This example program detects edges in images by a derivation of the Gaussian blur. Image noise for edge detection could be ignored due to adjustable blurring. The derivation is calculated as part of the extended Binomial algorithm.

Edge detection is useful in many applications. It could be used as mask for other operations like blur or sharpen to protect certain parts of the image against modification.

The short and fast version uses only the gray values of the pixel. It works only for 8-bit RGB images.
Simple edge detection source code: edgeDetection.ffp.

The long and flexible version considers all color planes separately before summing up the edge information and works in any color mode.
Flexible edge detection source code: edgeDetection2.ffp, plugin: edgeDetection2.8bf.

Blur - Sharpen

This application for fast Gaussian blur is a combined blur - sharpen filter.

Blurring and sharpening have separate sliders and are applied at the same time. If both sliders have the same value of course nothing happens. The difference makes the threshold slider. If the local contrast (of the selected radius) is below the threshold only blurring is applied. For local contrast above the threshold both blur and sharpening is applied. In this way for low contrast like noise the blur filter is applied whereas higher contrast is sharpened.

Without blur this filter works the same than an USM-filter. In addition a blur could be applied.

Blur - sharpen filter source code: blursharpen.ffp, plugin: blursharpen.8bf.

Downsampled Gaussian blur

The Gaussian blur filter has the effect of reducing the image's high-frequency components. Because of this low pass effect the image can be down sampled before applying the Gaussian filter. This is especially fast for larger blur radius.

The filter first does a box down-sampling, applies the normal Gaussian blur (with reduced radius) and up-samples the image again by a bilinear interpolation.

Source code of down sampled Gaussian blur filter: downsampleGauss.ffp.

Recursive Gaussian blur

An implementation by Tom Fiddaman (slightly improved) of the recursive Gaussian blur according to Young
(http://www.ph.tn.tudelft.nl/~lucas/publications/1995/SP95TYLV/SP95TYLV.pdf).

Young et al. use a recursive implementation of the Gaussian filter which has also a runtime complexity independent of the blur radius. The disadvantage of this approach is that the length of the temporary output stream is infinite. For practical implementation the output stream has to be cut off somewhere.

Recursive Gaussian blur source code: recursivegauss.ffp, plugin: recursivegauss.8bf.

Bilateral Filter

In addition to the spacial radius bilateral filter consider the pixel range for the blur calculation. This way the edges in images are preserved and not blured.

A detailed description is available at http://people.csail.mit.edu/sparis/bf_course/.

Bilateral filter source code: bilateral.ffp, plugin: bilateral.8bf.

home.pages.at Counter