In Reality Gaussian Blur Algorithm uses the Gaussian function it is really slow to compute for large input like a picture which has a certain amount of pixels and it has complexity O(n3) for (RGB).
Gaussian blur algorithm is a process of performing a weighted average operation on the entire image. The value of each pixel is obtained by weighted averaging of itself and other pixel values in the field which are Red, Green, Blue, and Alpha if desired in each pixel
So computing basic Gaussian blur is time consuming to get a fast result, but there’s a work around.
First The Box-Blur Algorithm
This Algorithm by : Wojciech Jarosz
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.
A 3 by 3 box blur can be written as 1/9 * determinant matrix:
But Box Blur can be much faster! than this approach.
How?
Notice the Box-Blur Kernel is 2D Matrix so we can split it to 2 x 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 make it faster Just by Moving Average technique .
Since we are now just doing 2 x 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!
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[] {
0 f, 0 f, 0 f, 0 f
};
float[] iAvg = new float[] {
0 f, 0 f, 0 f, 0 f
};
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[] {
0 f, 0 f, 0 f, 0 f
};
float[] iAvg = new float[] {
0 f, 0 f, 0 f, 0 f
};
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 Fast Gaussian Blur
This Algorithm by : Peter Kovesi
If you read the Calculus behind the algorithm you will know that we can achieve Gaussian Blue with 3 passes of Box Blue.
I wont explain the Calculus but if you’re interested you can read the paper.
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
To see it in action i Implemented this algorithm in an open-source C# library called NetFx you can find here on GitHub