Implementation of Fast Image Blurring Algorithms in C#

 

First the Box-Blur  Algorithm

This Algorithm by : Wojciech Jarosz link below

Box Blur standard Algorithm uses A Kernel with values of 1 we approach the effect by convolution to the Image pixels , each pixel in the resulting image has a value equal to the average value of its neighboring pixels in the input image.

Example : from wiki

A 3 by 3 box blur can be written as 1/9 * determinant matrix:

  {\displaystyle {\frac {1}{9}}{\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}}}

but Box Blur can be much faster!!

How?

Notice the Box-Blur Kernel is 2D Matrix so we can split it to 2 One-dimensional kernels and the blur that uses 1d kernel is motion-Blur so we’re going to preform horizontal motion blur, and then a vertical motion blur.  this will create an image that is equivalent to a box-blurred image!  and much faster computing .

still we cloud do it faster

Just by Moving Average technique .

Since we are now just doing 2 motion blurs, lets just
consider motion blur:
The accumulation of the neighborhood of pixel i, shares a lot of pixels in common with the accumulation for pixel i+1.

so:

accumulation(i+1) = accumulation(i) –leftmost pixel of neighborhood(i) + rightmost
pixel of neighborhood(i+1)

This means  by getting the first Average and the sum of the first Horizontal and Vertical pixels of an Image we are Speeding Up a Box Blur .

so we need to compute the whole kernel for only the first pixel in each row. Successive pixel blur values can be attained with  just an add and a subtract to the previous blur value!

In C# :

       private Bitmap FastBoxBlur(Bitmap img, int radius)
{
int kSize = radius;
if (kSize % 2 == 0) kSize++;
Bitmap Hblur = img.Clone();
float Avg = (float)1 / kSize;

for (int j = 0; j < img.Height(); j++)
{

float[] hSum = new float[] { 0f, 0f, 0f, 0f };
float[] iAvg = new float[] { 0f, 0f, 0f, 0f };

for (int x = 0; x < kSize; x++)
{
Color tmpColor = img.GetPixel(x, j);
hSum[0] += tmpColor.A;
hSum[1] += tmpColor.R;
hSum[2] += tmpColor.G;
hSum[3] += tmpColor.B;
}
iAvg[0] = hSum[0] * Avg;
iAvg[1] = hSum[1] * Avg;
iAvg[2] = hSum[2] * Avg;
iAvg[3] = hSum[3] * Avg;
for (int i = 0; i < img.Width(); i++) { if (i – kSize / 2 >= 0 && i + 1 + kSize / 2 < img.Width())
{
Color tmp_pColor = img.GetPixel(i – kSize / 2, j);
hSum[0] -= tmp_pColor.A;
hSum[1] -= tmp_pColor.R;
hSum[2] -= tmp_pColor.G;
hSum[3] -= tmp_pColor.B;
Color tmp_nColor = img.GetPixel(i + 1 + kSize / 2, j);
hSum[0] += tmp_nColor.A;
hSum[1] += tmp_nColor.R;
hSum[2] += tmp_nColor.G;
hSum[3] += tmp_nColor.B;
//
iAvg[0] = hSum[0] * Avg;
iAvg[1] = hSum[1] * Avg;
iAvg[2] = hSum[2] * Avg;
iAvg[3] = hSum[3] * Avg;
}
Hblur.SetPixel(i, j, Color.FromArgb((int)iAvg[0], (int)iAvg[1], (int)iAvg[2], (int)iAvg[3]));
}
}
Bitmap total =Hblur.Clone();
for (int i = 0; i < Hblur.Width(); i++)
{
float[] tSum = new float[] { 0f, 0f, 0f, 0f };
float[] iAvg = new float[] { 0f, 0f, 0f, 0f };
for (int y = 0; y < kSize; y++)
{
Color tmpColor = Hblur.GetPixel(i, y);
tSum[0] += tmpColor.A;
tSum[1] += tmpColor.R;
tSum[2] += tmpColor.G;
tSum[3] += tmpColor.B;
}
iAvg[0] = tSum[0] * Avg;
iAvg[1] = tSum[1] * Avg;
iAvg[2] = tSum[2] * Avg;
iAvg[3] = tSum[3] * Avg;

for (int j = 0; j < Hblur.Height(); j++) { if (j – kSize / 2 >= 0 && j + 1 + kSize / 2 < Hblur.Height())
{
Color tmp_pColor = Hblur.GetPixel(i, j – kSize / 2);
tSum[0] -= tmp_pColor.A;
tSum[1] -= tmp_pColor.R;
tSum[2] -= tmp_pColor.G;
tSum[3] -= tmp_pColor.B;
Color tmp_nColor = Hblur.GetPixel(i, j + 1 + kSize / 2);
tSum[0] += tmp_nColor.A;
tSum[1] += tmp_nColor.R;
tSum[2] += tmp_nColor.G;
tSum[3] += tmp_nColor.B;
//
iAvg[0] = tSum[0] * Avg;
iAvg[1] = tSum[1] * Avg;
iAvg[2] = tSum[2] * Avg;
iAvg[3] = tSum[3] * Avg;
}
total.SetPixel(i, j, Color.FromArgb((int)iAvg[0], (int)iAvg[1], (int)iAvg[2], (int)iAvg[3]));
}
}
return total;
}

The Gaussian Blur

This Algorithm by : Peter Kovesi link below

with this algorithm, we will simulate the Gaussian blur with 3 passes of box blur.Nice!!

I wont explain the Calculus if you’re interested you can read his paper in the link below  😛 .

Now into coding :

First the three boxes are not in the same size so we need function that calculate each box size

 private int[] boxesForGaussian(double sigma, int n)
{
double wIdeal = Math.Sqrt((12 * sigma * sigma / n) + 1);

double wl = Math.Floor(wIdeal); if (wl % 2 == 0) wl–;
double wu = wl + 2;

double mIdeal = (12 * sigma * sigma – n * wl * wl – 4 * n * wl – 3 * n) / (-4 * wl – 4);
double m = Math.Round(mIdeal);

int[] sizes = new int[n];
for (int i = 0; i < n; i++)
{
if (i < m) { sizes[i] = (int)wl; } else { sizes[i] = (int)wu; }
}
return sizes;
}

Now the easy part we will preform the Fast-Blur Function on each box

 private Bitmap FastGaussianBlur(BitmapW src, int Raduis)
{
var bxs = boxesForGaussian(Raduis, 3);
BitmapW img = FastBoxBlur(src, bxs[0]);
BitmapW img_2 = FastBoxBlur(img, bxs[1]);
BitmapW img_3 = FastBoxBlur(img_2, bxs[2]);
return img_3;
}

and Holla! super Fast Photoshop Like Gaussian Blur 🙂

I Implement this code in open-source C# library called NetFx  you can find  here on GitHub

Fast Algorithms :
   Box Blur Algorithm by: Wojciech Jarosz on :
http://elynxsdk.free.fr/ext-docs/Blur/Fast_box_blur.pdf
and the Fast Gaussian Algorithm by: Peter Kovesi on :
http://www.peterkovesi.com/papers/FastGaussianSmoothing.pdf

NETFx

 C# Image Manipulation Library by : Asad Memon on :

https://github.com/LionRoar/NETFx

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Powered by WordPress.com.

Up ↑

%d bloggers like this: