Efficient Gaussian Blur Algorithm

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

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

Extended Binomial Filter for Fast Gaussian Blur

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.

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: blurring.pdf.

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

Sample implementation

  void blur(int radius) { // first degree approximation 
    int buffer[radius]; // pixel buffer 
    
    for (int x = x_start; x < x_end; ++x) { // vertical blur
      long dif = 0, sum = 0;
      for (int y = y_start-2*radius; y < y_end; ++y) {
        sum += dif;            // accumulate pixel blur
        dif += getPixel(x, y+radius);   // next pixel
        if (y >= y_start) {
          dif += buffer[y%radius];  // sum up differences: +1, -2, +1
          setPixel(x, y, sum/(radius*radius)); // set blurred pixel
        } 
        if (y+radius >= y_start) {
          int p = getPixel(x,y);
          buffer[y%radius] = p;    // buffer pixel
          dif -= 2*p;
        }
      } // y
    } // x

    for (y = y_start; y < y_end; ++y) { // horizontal blur...
      dif = 0; sum = 0;
      for (x = x_start-2*radius; x < x_end; ++x) {
        sum += dif;              // accumulate pixel blur
        dif += getPixel(x+radius, y);  // next pixel
        if (x >= x_start) {
          dif += buffer[x%radius];  // sum up differences: +1, -2, +1
          setPixel(x, y, sum/(radius*radius)); // set blurred pixel
        } 
        if (x+radius >= x_start) {
          p = getPixel(x,y);
          buffer[x%radius] = p;    // buffer pixel
          dif -= 2*p;
        }
      } // x
    } // y
  } // blur