Fast Blur (Box Blur with accumulator)

This post is similar to my previous post, but this post is about blurring an existing image, the previous post was about rendering colored rectangles.

For a game I’m creating (check out a beta at Flow) I needed a really fast way to repeatedly blur images (WriteableBitmap in this case) in Silverlight.
There are blur functions as image effects, and if that satisfies your needs then you should go with that. But I needed to generate my bitmap, blur it, update it, blur it and so on.

I’ve submitted the code below to the WriteableBitmapEx project as a contribution, but it hasn’t been accepted nor rejected yet. I’m publishing it here in case anyone needs it.

Box Blur is a very fast method for blurring (http://www.vcskicks.com/box-blur.php) but for it to be fast you must implement it as an accumulator, not a convolution loop.

Finding implementations of Box Blur, in C#, that uses convolution kernels (as in the link above) is trivial, finding one that uses an accumulator proved more difficult. The method below uses an accumulator.

The code for using the blur method looks like this;


WriteableBitmap bitmap = new WriteableBitmap((BitmapSource)Image.Source);
bitmap.BoxBlur(13);
Image.Source = bitmap;
bitmap.Invalidate();

Before Box Blur;

After Box Blur (range=13);

Running BoxBlur on this 512×512 takes about 32 ms (averaged over 1000 runs) on my computer.

public static void BoxBlur(this WriteableBitmap bmp, int range)
{
	if ((range & 1) == 0)
	{
		throw new InvalidOperationException("Range must be odd!");
	}

	bmp.BoxBlurHorizontal(range);
	bmp.BoxBlurVertical(range);
}

public static void BoxBlurHorizontal(this WriteableBitmap bmp, int range)
{
	int[] pixels = bmp.Pixels;
	int w = bmp.PixelWidth;
	int h = bmp.PixelHeight;
	int halfRange = range / 2;
	int index = 0;
	int[] newColors = new int[w];

	for (int y = 0; y < h; y++)
	{
		int hits = 0;
		int r = 0;
		int g = 0;
		int b = 0;
		for (int x = -halfRange; x < w; x++)
		{
			int oldPixel = x - halfRange - 1;
			if (oldPixel >= 0)
			{
				int col = pixels[index + oldPixel];
				if (col != 0)
				{
					r -= ((byte)(col >> 16));
					g -= ((byte)(col >> 8 ));
					b -= ((byte)col);
				}
				hits--;
			}

			int newPixel = x + halfRange;
			if (newPixel < w)
			{
				int col = pixels[index + newPixel];
				if (col != 0)
				{
					r += ((byte)(col >> 16));
					g += ((byte)(col >> 8 ));
					b += ((byte)col);
				}
				hits++;
			}

			if (x >= 0)
			{
				int color =
					(255 << 24)
					| ((byte)(r / hits) << 16)
					| ((byte)(g / hits) << 8 )
					| ((byte)(b / hits));

				newColors[x] = color;
			}
		}

		for (int x = 0; x < w; x++)
		{
			pixels[index + x] = newColors[x];
		}

		index += w;
	}
}

public static void BoxBlurVertical(this WriteableBitmap bmp, int range)
{
	int[] pixels = bmp.Pixels;
	int w = bmp.PixelWidth;
	int h = bmp.PixelHeight;
	int halfRange = range / 2;

	int[] newColors = new int[h];
	int oldPixelOffset = -(halfRange + 1) * w;
	int newPixelOffset = (halfRange) * w;

	for (int x = 0; x < w; x++)
	{
		int hits = 0;
		int r = 0;
		int g = 0;
		int b = 0;
		int index = -halfRange * w + x;
		for (int y = -halfRange; y < h; y++)
		{
			int oldPixel = y - halfRange - 1;
			if (oldPixel >= 0)
			{
				int col = pixels[index + oldPixelOffset];
				if (col != 0)
				{
					r -= ((byte)(col >> 16));
					g -= ((byte)(col >> 8 ));
					b -= ((byte)col);
				}
				hits--;
			}

			int newPixel = y + halfRange;
			if (newPixel < h)
			{
				int col = pixels[index + newPixelOffset];
				if (col != 0)
				{
					r += ((byte)(col >> 16));
					g += ((byte)(col >> 8 ));
					b += ((byte)col);
				}
				hits++;
			}

			if (y >= 0)
			{
				int color =
					(255 << 24)
					| ((byte)(r / hits) << 16)
					| ((byte)(g / hits) << 8 )
					| ((byte)(b / hits));

				newColors[y] = color;
			}

			index += w;
		}

		for (int y = 0; y < h; y++)
		{
			pixels[y * w + x] = newColors[y];
		}
	}
}
public static void BoxBlur(this WriteableBitmap bmp, int range) { if ((range & 1) == 0) { throw new InvalidOperationException(“Range must be odd!”); }   bmp.BoxBlurHorizontal(range); bmp.BoxBlurVertical(range); } public static void BoxBlurHorizontal(this WriteableBitmap bmp, int range) { int[] pixels = bmp.Pixels; int w = bmp.PixelWidth; int h = bmp.PixelHeight; int halfRange = range / 2; int index = 0; int[] newColors = new int[w]; for (int y = 0; y < h; y++) { int hits = 0; int r = 0; int g = 0; int b = 0; for (int x = -halfRange; x < w; x++) { int oldPixel = x – halfRange – 1; if (oldPixel >= 0) { int col = pixels[index + oldPixel]; if (col != 0) { r -= ((byte)(col >> 16)); g -= ((byte)(col >> 8)); b -= ((byte)col); } hits–; } int newPixel = x + halfRange; if (newPixel < w) { int col = pixels[index + newPixel]; if (col != 0) { r += ((byte)(col >> 16)); g += ((byte)(col >> 8)); b += ((byte)col); } hits++; } if (x >= 0) { int color = (255 << 24) | ((byte)(r / hits) << 16) | ((byte)(g / hits) << 8) | ((byte)(b / hits)); newColors[x] = color; } } for (int x = 0; x < w; x++) { pixels[index + x] = newColors[x]; } index += w; } } public static void BoxBlurVertical(this WriteableBitmap bmp, int range) { int[] pixels = bmp.Pixels; int w = bmp.PixelWidth; int h = bmp.PixelHeight; int halfRange = range / 2; int[] newColors = new int[h]; int oldPixelOffset = -(halfRange + 1) * w; int newPixelOffset = (halfRange) * w; for (int x = 0; x < w; x++) { int hits = 0; int r = 0; int g = 0; int b = 0; int index = -halfRange * w + x; for (int y = -halfRange; y < h; y++) { int oldPixel = y – halfRange – 1; if (oldPixel >= 0) { int col = pixels[index + oldPixelOffset]; if (col != 0) { r -= ((byte)(col >> 16)); g -= ((byte)(col >> 8)); b -= ((byte)col); } hits–; } int newPixel = y + halfRange; if (newPixel < h) { int col = pixels[index + newPixelOffset]; if (col != 0) { r += ((byte)(col >> 16)); g += ((byte)(col >> 8)); b += ((byte)col); } hits++; } if (y >= 0) { int color = (255 << 24) | ((byte)(r / hits) << 16) | ((byte)(g / hits) << 8) | ((byte)(b / hits)); newColors[y] = color; } index += w; } for (int y = 0; y < h; y++) { pixels[y * w + x] = newColors[y]; } } }
Advertisements

Colored/Shaded Rectangle on a WriteableBitmap

I recently needed a way to render a colored rectangle on a WriteableBitmap in Silverlight – though the code could be used in WPF with minor changes. Typically, you’d not use WriteableBitmaps but different Shapes in WPF, but this time I needed to create my own bitmap.

I’ve submitted the code as a contribution to the WriteableBitmapEx.codeplex.com project, but it hasn’t been accepted nor rejected yet, so I figured I’d post it here in case anyone ever needs something similar.

Drawing a 255×255 shaded block takes 2.06 ms (averaged over 1000 draws).

Shaded rectangle rendered on picture of lena;

WriteableBitmap bitmap = new WriteableBitmap((BitmapSource)Image.Source);
int width = 255;
int start = (512 - width) / 2;
bitmap.DrawFilledRectangle(
 start, start,
 start + width, start + width,
 Colors.White,
 Colors.Red,
 Colors.Green,
 Colors.Blue);

Image.Source = bitmap;
bitmap.Invalidate();

public static void DrawFilledRectangle(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, Color color)
{
	// Add one to use mul and cheap bit shift for multiplicaltion
	var a = color.A + 1;
	var col = (color.A << 24)
			 | ((byte)((color.R * a) >> 8 ) << 16)
			 | ((byte)((color.G * a) >> 8 ) << 8 )
			 | ((byte)((color.B * a) >> 8 ));

	bmp.DrawFilledRectangle(x1, y1, x2, y2, col);
}

public static void DrawFilledRectangle(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, Color color00, Color color01, Color color10, Color color11)
{
	// Add one to use mul and cheap bit shift for multiplicaltion
	var a00 = color00.A + 1;
	var col00 = (color00.A << 24)
			 | ((byte)((color00.R * a00) >> 8 ) << 16)
			 | ((byte)((color00.G * a00) >> 8 ) << 8 )
			 | ((byte)((color00.B * a00) >> 8 ));

	var a01 = color01.A + 1;
	var col01 = (color01.A << 24)
			 | ((byte)((color01.R * a01) >> 8 ) << 16)
			 | ((byte)((color01.G * a01) >> 8 ) << 8 )
			 | ((byte)((color01.B * a01) >> 8 ));

	var a10 = color10.A + 1;
	var col10 = (color10.A << 24)
			 | ((byte)((color10.R * a10) >> 8 ) << 16)
			 | ((byte)((color10.G * a10) >> 8 ) << 8 )
			 | ((byte)((color10.B * a10) >> 8 ));

	var a11 = color11.A + 1;
	var col11 = (color11.A << 24)
			 | ((byte)((color11.R * a11) >> 8 ) << 16)
			 | ((byte)((color11.G * a11) >> 8 ) << 8 )
			 | ((byte)((color11.B * a11) >> 8 ));

	bmp.DrawFilledRectangle(x1, y1, x2, y2, col00, col01, col10, col11);
}

public static void DrawFilledRectangle(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, int color)
{
	// Use refs for faster access (really important!) speeds up a lot!
	int w = bmp.PixelWidth;
	int h = bmp.PixelHeight;
	int[] pixels = bmp.Pixels;

	// Check boundaries
	if (x1 < 0) { x1 = 0; }
	if (y1 < 0) { y1 = 0; }
	if (x2 < 0) { x2 = 0; }
	if (y2 < 0) { y2 = 0; }
	if (x1 >= w) { x1 = w - 1; }
	if (y1 >= h) { y1 = h - 1; }
	if (x2 >= w) { x2 = w - 1; }
	if (y2 >= h) { y2 = h - 1; }

	int i = y1 * w;
	for (int y = y1; y < y2; y++)
	{
		int i2 = i + x1;
		while (i2 < i + x2)
		{
			pixels[i2++] = color;
		}
		i += w;
	}
}

public static void DrawFilledRectangle(this WriteableBitmap bmp, int x1, int y1, int x2, int y2, int color00, int color01, int color10, int color11)
{
	// Use refs for faster access (really important!) speeds up a lot!
	int w = bmp.PixelWidth;
	int h = bmp.PixelHeight;
	int[] pixels = bmp.Pixels;

	// Check boundaries
	if (x1 < 0) { x1 = 0; }
	if (y1 < 0) { y1 = 0; }
	if (x2 < 0) { x2 = 0; }
	if (y2 < 0) { y2 = 0; }
	if (x1 >= w) { x1 = w - 1; }
	if (y1 >= h) { y1 = h - 1; }
	if (x2 >= w) { x2 = w - 1; }
	if (y2 >= h) { y2 = h - 1; }

	// Retrieve the color channels
	byte a00 = (byte)(color00 >> 24); byte r00 = (byte)(color00 >> 16); byte g00 = (byte)(color00 >> 8 ); byte b00 = (byte)(color00);
	byte a10 = (byte)(color10 >> 24); byte r10 = (byte)(color10 >> 16); byte g10 = (byte)(color10 >> 8 ); byte b10 = (byte)(color10);
	byte a01 = (byte)(color01 >> 24); byte r01 = (byte)(color01 >> 16); byte g01 = (byte)(color01 >> 8 ); byte b01 = (byte)(color01);
	byte a11 = (byte)(color11 >> 24); byte r11 = (byte)(color11 >> 16); byte g11 = (byte)(color11 >> 8 ); byte b11 = (byte)(color11);

	//r01, r10
	int xrange = x2 - x1;
	int yrange = y2 - y1;

	for (int x = 0; x < xrange; x++)
	{
		int negx = xrange - x;
		byte atop = (byte)((a00 * negx + a01 * x) / xrange);
		byte rtop = (byte)((r00 * negx + r01 * x) / xrange);
		byte gtop = (byte)((g00 * negx + g01 * x) / xrange);
		byte btop = (byte)((b00 * negx + b01 * x) / xrange);

		byte abottom = (byte)((a10 * negx + a11 * x) / xrange);
		byte rbottom = (byte)((r10 * negx + r11 * x) / xrange);
		byte gbottom = (byte)((g10 * negx + g11 * x) / xrange);
		byte bbottom = (byte)((b10 * negx + b11 * x) / xrange);

		for (int y = 0; y < yrange; y++)
		{
			int negy = yrange - y;
			int p = (y + y1) * w + x + x1;

			int color =
				(byte)((atop * negy + abottom * y) / yrange) << 24 |
				(byte)((rtop * negy + rbottom * y) / yrange) << 16 |
				(byte)((gtop * negy + gbottom * y) / yrange) << 8 |
				(byte)((btop * negy + bbottom * y) / yrange);

			pixels[p] = color;
		}
	}
}