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

Perlin Noise in C#

I had some Delphi code banging around that I’ve used many times, it was originally written by Tom Nuydens (tom@delphi3d.net). I decided to translate it to C#, you’ll find it below and some code where I’m using it.

using System;

namespace ImageTools.Core
{

    /* Perlin noise class.  ( by Tom Nuydens (tom@delphi3d.net) )
 * Converted to C# by Mattias Fagerlund, Mattias.Fagerlund@cortego.se

  ******************************************************************************

  I used the following references for my implementation:
    http://students.vassar.edu/mazucker/code/perlin-noise-math-faq.html
    Darwin Peachey's chapter in "Texturing & Modeling: A Procedural Approach"
  Another good resource is
    http://freespace.virgin.net/hugo.elias/models/m_perlin.htm

  ******************************************************************************

  This class generates 3D Perlin noise. The demo that comes with this is 2D, but
  uses the 3rd dimension to create animated noise. The noise does not tile,
  although it could be made to do so with a few small modifications to the
  algorithm.

  Perlin noise can be used as a starting point for all kinds of things,
  including terrain generation, cloud rendering, procedural textures, and more.
  Most of these techniques involve rendering multiple "octaves" of noise. This
  means you generate multiple noise values for every pixel (each with different
  X, Y and/or Z coordinates), and then sum them. There's an example of this in
  the accompanying demo.
*/

    public class PerlinNoise
    {
        private const int GradientSizeTable = 256;
        private readonly Random _random;
        private readonly double[] _gradients = new double[GradientSizeTable * 3];
        /* Borrowed from Darwyn Peachey (see references above).
           The gradient table is indexed with an XYZ triplet, which is first turned
           into a single random index using a lookup in this table. The table simply
           contains all numbers in [0..255] in random order. */
        private readonly byte[] _perm = new byte[] {
              225,155,210,108,175,199,221,144,203,116, 70,213, 69,158, 33,252,
                5, 82,173,133,222,139,174, 27,  9, 71, 90,246, 75,130, 91,191,
              169,138,  2,151,194,235, 81,  7, 25,113,228,159,205,253,134,142,
              248, 65,224,217, 22,121,229, 63, 89,103, 96,104,156, 17,201,129,
               36,  8,165,110,237,117,231, 56,132,211,152, 20,181,111,239,218,
              170,163, 51,172,157, 47, 80,212,176,250, 87, 49, 99,242,136,189,
              162,115, 44, 43,124, 94,150, 16,141,247, 32, 10,198,223,255, 72,
               53,131, 84, 57,220,197, 58, 50,208, 11,241, 28,  3,192, 62,202,
               18,215,153, 24, 76, 41, 15,179, 39, 46, 55,  6,128,167, 23,188,
              106, 34,187,140,164, 73,112,182,244,195,227, 13, 35, 77,196,185,
               26,200,226,119, 31,123,168,125,249, 68,183,230,177,135,160,180,
               12,  1,243,148,102,166, 38,238,251, 37,240,126, 64, 74,161, 40,
              184,149,171,178,101, 66, 29, 59,146, 61,254,107, 42, 86,154,  4,
              236,232,120, 21,233,209, 45, 98,193,114, 78, 19,206, 14,118,127,
               48, 79,147, 85, 30,207,219, 54, 88,234,190,122, 95, 67,143,109,
              137,214,145, 93, 92,100,245,  0,216,186, 60, 83,105, 97,204, 52};

        public PerlinNoise(int seed)
        {
            _random = new Random(seed);
            InitGradients();
        }

        public double Noise(double x, double y, double z)
        {
            /* The main noise function. Looks up the pseudorandom gradients at the nearest
               lattice points, dots them with the input vector, and interpolates the
               results to produce a single output value in [0, 1] range. */

            int ix = (int)Math.Floor(x);
            double fx0 = x - ix;
            double fx1 = fx0 - 1;
            double wx = Smooth(fx0);

            int iy = (int)Math.Floor(y);
            double fy0 = y - iy;
            double fy1 = fy0 - 1;
            double wy = Smooth(fy0);

            int iz = (int)Math.Floor(z);
            double fz0 = z - iz;
            double fz1 = fz0 - 1;
            double wz = Smooth(fz0);

            double vx0 = Lattice(ix, iy, iz, fx0, fy0, fz0);
            double vx1 = Lattice(ix + 1, iy, iz, fx1, fy0, fz0);
            double vy0 = Lerp(wx, vx0, vx1);

            vx0 = Lattice(ix, iy + 1, iz, fx0, fy1, fz0);
            vx1 = Lattice(ix + 1, iy + 1, iz, fx1, fy1, fz0);
            double vy1 = Lerp(wx, vx0, vx1);

            double vz0 = Lerp(wy, vy0, vy1);

            vx0 = Lattice(ix, iy, iz + 1, fx0, fy0, fz1);
            vx1 = Lattice(ix + 1, iy, iz + 1, fx1, fy0, fz1);
            vy0 = Lerp(wx, vx0, vx1);

            vx0 = Lattice(ix, iy + 1, iz + 1, fx0, fy1, fz1);
            vx1 = Lattice(ix + 1, iy + 1, iz + 1, fx1, fy1, fz1);
            vy1 = Lerp(wx, vx0, vx1);

            double vz1 = Lerp(wy, vy0, vy1);
            return Lerp(wz, vz0, vz1);
        }

        private void InitGradients()
        {
            for (int i = 0; i < GradientSizeTable; i++)
            {
                double z = 1f - 2f * _random.NextDouble();
                double r = Math.Sqrt(1f - z * z);
                double theta = 2 * Math.PI * _random.NextDouble();
                _gradients[i * 3] = r * Math.Cos(theta);
                _gradients[i * 3 + 1] = r * Math.Sin(theta);
                _gradients[i * 3 + 2] = z;
            }
        }

        private int Permutate(int x)
        {
            const int mask = GradientSizeTable - 1;
            return _perm[x & mask];
        }

        private int Index(int ix, int iy, int iz)
        {
            // Turn an XYZ triplet into a single gradient table index.
            return Permutate(ix + Permutate(iy + Permutate(iz)));
        }

        private double Lattice(int ix, int iy, int iz, double fx, double fy, double fz)
        {
            // Look up a random gradient at [ix,iy,iz] and dot it with the [fx,fy,fz] vector.
            int index = Index(ix, iy, iz);
            int g = index*3;
            return _gradients[g] * fx + _gradients[g + 1] * fy + _gradients[g + 2] * fz;
        }

        private double Lerp(double t, double value0, double value1)
        {
            // Simple linear interpolation.
            return value0 + t * (value1 - value0);
        }

        private double Smooth(double x)
        {
            /* Smoothing curve. This is used to calculate interpolants so that the noise
              doesn't look blocky when the frequency is low. */
            return x * x * (3 - 2 * x);
        }
    }
}

And here’s an example of how to use it with three octaves of noise. See my previous post about using lambda to manipulate images, that code is required to make this work;

        private void noiseButton_Click(object sender, EventArgs e)
        {
            PerlinNoise perlinNoise = new PerlinNoise(99);
            Bitmap bitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
            double widthDivisor = 1 / (double)pictureBox.Width;
            double heightDivisor = 1 / (double)pictureBox.Height;
            bitmap.SetEachPixelColour(
                (point, color) =>
                {
                    // Note that the result from the noise function is in the range -1 to 1, but I want it in the range of 0 to 1
                    // that's the reason of the strange code
                    double v =
                        // First octave
                        (perlinNoise.Noise(2 * point.X * widthDivisor, 2 * point.Y * heightDivisor, -0.5) + 1) / 2 * 0.7 +
                        // Second octave
                        (perlinNoise.Noise(4 * point.X * widthDivisor, 4 * point.Y * heightDivisor, 0) + 1) / 2 * 0.2 +
                        // Third octave
                        (perlinNoise.Noise(8 * point.X * widthDivisor, 8 * point.Y * heightDivisor, +0.5) + 1) / 2 * 0.1;

                    v = Math.Min(1, Math.Max(0, v));
                    byte b = (byte)(v * 255);
                    return Color.FromArgb(b, b, b);
                });
            pictureBox.Image = bitmap;
        }

Using lambda to manipulate images

Working with every pixel in an image – the lambda way!

When working with images, I frequently need to apply the same function to every pixel in the image. Since I do that a lot, I decided to create some nice lambda image processing extensions!

In C# Win32, you would typically work with the System.Drawing.Bitmap class, so that’s what I’ll use. In C# WPF, there are other classes you’d use instead, but I won’t go into that in this blog post.

Initially I’ll use two methods, one that allows me to compute the color of each pixel in the image. Another that allows me to perform an arbitrary action for each pixel in the bitmap – the action could set the color of the pixel, but it’s not required.

Here are my extension methods for image manipulation;

using System;
using System.Drawing;

namespace LambdaImageProcessing.Core
{
    public static class BitmapExtensionMethods
    {
        public static void ExecuteForEachPixel(this Bitmap bitmap, Action<Point, Bitmap> action)
        {
            Point point = new Point(0, 0);
            for (int x = 0; x < bitmap.Width; x++)
            {
                point.X = x;
                for (int y = 0; y < bitmap.Height; y++)
                {
                    point.Y = y;
                    action(point, bitmap);
                }
            }
        }

        public static void ExecuteForEachPixel(this Bitmap bitmap, Action<Point> action)
        {
            Point point = new Point(0, 0);
            for (int x = 0; x < bitmap.Width; x++)
            {
                point.X = x;
                for (int y = 0; y < bitmap.Height; y++)
                {
                    point.Y = y;
                    action(point);
                }
            }
        }

        public static void SetEachPixelColour(this Bitmap bitmap, Func<Point, Color> colourFunc)
        {
            Point point = new Point(0, 0);
            for (int x = 0; x < bitmap.Width; x++)
            {
                point.X = x;
                for (int y = 0; y < bitmap.Height; y++)
                {
                    point.Y = y;
                    bitmap.SetPixel(x, y, colourFunc(point));
                }
            }
        }

        public static void SetEachPixelColour(this Bitmap bitmap, Func<Point, Color, Color> colourFunc)
        {
            Point point = new Point(0, 0);
            for (int x = 0; x < bitmap.Width; x++)
            {
                point.X = x;
                for (int y = 0; y < bitmap.Height; y++)
                {
                    point.Y = y;
                    bitmap.SetPixel(x, y, colourFunc(point, bitmap.GetPixel(x, y)));
                }
            }
        }
    }
}

Using my lambda method to draw the color of each pixel as a gradient given the distance to the center of the image. That code looks like this;

        private void renderDistanceFromCenterButton_Click(object sender, EventArgs e)
        {
            // Build the bitmap
            Bitmap bitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
            Point imageCenter = new Point(pictureBox.Width / 2, pictureBox.Height / 2);

            // Ok, this is terrible, you _really_ shouldn't use lambda like this... But you can...
            Func<double, double, double> distance = (x, y) => Math.Sqrt(x * x + y * y);

            double maxDistance = distance(imageCenter.X, imageCenter.Y);
            bitmap.SetEachPixelColour(
                point =>
                {
                    // Pythagoras
                    double dist = distance((point.X - imageCenter.X), (point.Y - imageCenter.Y));
                    byte b = Convert.ToByte(255 * dist / maxDistance);
                    return Color.FromArgb(b, b, b);
                });
            pictureBox.Image = bitmap;
        }

Running this code produces this image;

DistanceFromCenter

Not very pretty, but it works. And I didn’t have to write a single loop, which I find myself doing over and over again when not using lambda functions.

Make image black and white

Converting a color image to black and white can be done this way;

        private void makeBWButton_Click(object sender, EventArgs e)
        {
            Bitmap bitmap = new Bitmap("lena.jpg");
            bitmap.SetEachPixelColour(
                (point, color) =>
                {
                    // Simplest way for making BW
                    byte b = (byte)((color.R + color.B + color.G) / 3);
                    return Color.FromArgb(b, b, b);
                });
            pictureBox.Image = bitmap;
        }

Here’s Lena in color;

lena

And with the BW method above;

lenaBW

Tinting an image – method 1

If you have an image that you wish to tint (mix it with a color) – for instance make it sepia toned – you can use this method;

        public static Color TintColor(Color originalColor, Color tintColor, byte strength)
        {
            byte s1 = (byte)(100 - strength);
            return
                Color.FromArgb(
                (s1 * originalColor.R + strength * tintColor.R) / 100,
                (s1 * originalColor.G + strength * tintColor.G) / 100,
                (s1 * originalColor.B + strength * tintColor.B) / 100);
        }

        private void tintBitmapButton_Click(object sender, EventArgs e)
        {
            Bitmap bitmap = new Bitmap("lena.jpg");
            bitmap.SetEachPixelColour(
                (point, color) =>
                {
                    return TintColor(color, Color.Blue, 50);
                });
            pictureBox.Image = bitmap;
        }

Which produces this Lena;

lenaTint1

Tinting an image – method 2

This method converts the pixel to black and white before mixing in the tint color – so that nothing of the original image color remains;

        private void tint2BitmapButton_Click(object sender, EventArgs e)
        {
            Bitmap bitmap = new Bitmap("lena.jpg");
            Color targetColor = Color.SpringGreen;
            bitmap.SetEachPixelColour(
                (point, color) =>
                {
                    double luminence = ((color.R * 30 + color.G * 59 + color.B * 11) / 100.0) / 255.0;
                    return
                        Color.FromArgb(
                            Convert.ToByte(targetColor.R * luminence),
                            Convert.ToByte(targetColor.G * luminence),
                            Convert.ToByte(targetColor.B * luminence));

                });
            pictureBox.Image = bitmap;
        }

Which produces this Lena;

lenaTint2

Compare two images – the naive way

In a later blog post, I’ll talk about robust ways of comparing images, but here’s a naive approach for comparing two images of the same size. It computes the summed “colour distance” between the images.

        private double CompareBitmaps(Bitmap firstBitmap, Bitmap secondBitmap)
        {
            if (firstBitmap.Width != secondBitmap.Width || firstBitmap.Height != secondBitmap.Height)
            {
                return 1;
            }

            double difference = 0;
            firstBitmap.ExecuteForEachPixel(
                point =>
                {
                    Color firstColor = firstBitmap.GetPixel(point.X, point.Y);
                    Color secondColor = secondBitmap.GetPixel(point.X, point.Y);
                    difference += Math.Abs(secondColor.R / 255.0 - firstColor.R / 255.0);
                    difference += Math.Abs(secondColor.G / 255.0 - firstColor.G / 255.0);
                    difference += Math.Abs(secondColor.B / 255.0 - firstColor.B / 255.0);
                });

            // Normalize the difference so it's not size dependent
            difference /= (firstBitmap.Width * firstBitmap.Height);

            return difference;
        }

Comparing identical images returns 1, comparing totally de-similar images returns 0.