My previous post explained and provided a very simple method for extracting colours from a BitmapData image, by averaging the colours in specific areas.

This can have several applications, for example it features in a large amount of prototypes for the update to my Motion Tracking engine. However, if you want to create an accurate and representative colour palette from an image it has several flaws, the most obvious being that by averaging colours, you are actually removing or diluting the striking but perhaps less frequent colours in the image – the very colours which often make an image’s colour palette so exiting!

So, if we’re to extract an exciting and more representative palette from an image, we need a more intelligent algorithm; one which takes into account what makes a colour palette interesting – the contrasts and juxtapositions of colours within the image.

After a lot of trial and error I arrived at the following solution. I have posted the code bellow, but I think it’s important to understand how it works and why each step is taken, so without further ado, here be my approach to calculating the colour palette of a BitmapData image…

Reducing the colours

We’re going to be performing quite a few operations on the colours in our input image, so for the sake of performance it’s wise to reduce the colours in the image as much as possible without losing the overall look and feel of the palette.

Nicolas Barradeau has done some really cool things with this, and his Color Depth Change script is really worth checking out. We can actually enhance this technique slightly by omitting the two loops which cycle through every pixel in the image and use paletteMap. The result is good enough for our needs and substantially quicker. I’m also glad I could use the BitmapData paletteMap method, because up until now I hadn’t ever had a use for it :)

I’ve found that reducing the image’s colour palette to 64 colours works well performance wise and still looks great, but you might want to use anything up to 256.

I won’t go into how paletteMap works, and the docs aren’t very helpful on this matter so I suggest you check out Google if you want a bit more information. In short, we create a new index of colours for the image by creating three arrays, one for each channel (red, green and blue) and pass these values to the paletteMap method, which takes care of the rest at blisteringly fast speeds. What we are left with is a dithered version of our original image, allowing us to analyse it’s pixels in a much speedier manner.

public static function reduceColours( source:BitmapData, colours:int = 16 ):void
{
	var Ra:Array = new Array(256);
	var Ga:Array = new Array(256);
	var Ba:Array = new Array(256);
 
	var n:Number = 256 / ( colours / 3 );
 
	for (var i:int = 0; i < 256; i++)
	{
		Ba[i] = Math.floor(i / n) * n;
		Ga[i] = Ba[i] << 8;
		Ra[i] = Ga[i] << 8;
	}
 
	source.paletteMap( source, source.rect, new Point(), Ra, Ga, Ba );
}

Note: at this stage, if you’re working with a very large image, it’s advisable to draw the image to a smaller BitmapData using a scaled Matrix, as we will be looping over its pixels and so a 2000 x 2000 image is likely to make your CPU rather pissed off at you!

Indexing the colours

The next step is to build an index of the colours in the image. By index, I mean that we want a list of unique colours and a tally for each telling us how many times they occur in the image. We can do this by using an Object or a Dictionary, which uses the colour values as a key and a counter as the value.

public static function indexColours( source:BitmapData, sort:Boolean = true ):Array
{
 
	var n:Object = {};
	var a:Array = [];
	var p:int;
 
	for (var x:int = 0; x < source.width; x++) 
	{
		for (var y:int = 0; y < source.height; y++) 
		{
			p = source.getPixel(x, y);
			n[p] ? n[p]++ : n[p] = 1;
		}
	}
 
	for (var c:String in n)
	{
		a.push ( { colour:c, count:n[c] } );
	}
 
	function byCount( a:Object, b:Object ):int
	{
		if ( a.count > b.count ) return 1;
		if ( a.count < b.count ) return -1;
		return 0;
	}
 
	return a.sort( byCount, Array.DESCENDING );
}

We are left with an Object containing all the colours in the image, grouped by their colour value and with a reference to how frequently they appear. We can then use a for in loop to create an array from the Objects properties.

Finally, we need to sort the resulting Array, essentially by popularity, so that the colours which appear most frequently within the image are at the start of the Array. We can do this using the Array’s sort method, and passing a custom function which compares each colour’s count or frequency to that of the other colours. Now we can discard the count value, and what we are left with is a correctly ordered array of unsigned integers representing our entire spectrum of colours.

Finding unique, contrasting colours

At this point, we could simply take the first values from the array and call this our palette, after all if we wanted, say, a 16 colour palette then we know that the first 16 colours in our Array are the most frequently occurring colours in our source image. The problem with this is that, as with most things in life, just because something is popular doesn’t necessarily make it good! Take a landscape photograph for example; there may be a beautiful collection of flowers with striking colours in the foreground, and a burning orange and pink sunset descending over the horizon, yet the first group of colours in our Array will likely be a host of different shades of green from the hills and fields – not exactly what we were hoping for!

So we need an algorithm which can discern between colours and tell us which of our colours have a sufficient variance, therefore producing a palette which fairly represents the broader spectrum of colours in our image.

The best solution that I found was to add up the square of the red, green and blue components of two colours and compare their results. If they are sufficiently different (as determined by a variable tolerance) then we have a match.

public static function similar( colour1:uint, colour2:uint, tolerance:Number = 0.01 ):Boolean
{
	var RGB1:Object = Hex24ToRGB( colour1 );
	var RGB2:Object = Hex24ToRGB( colour2 );
 
	tolerance = tolerance * ( 255 * 255 * 3 ) << 0;
 
	var distance:Number = 0;
 
	distance += Math.pow( RGB1.red - RGB2.red, 2 );
	distance += Math.pow( RGB1.green - RGB2.green, 2 );
	distance += Math.pow( RGB1.blue - RGB2.blue, 2 );
 
	return distance <= tolerance;
}

To apply this idea, we need to create an empty Array which will eventually become our results. We then begin to loop through our colours, taking the first and comparing it to subsequent colours until we find one which is sufficiently different. We then push this colour into our results Array, and then continue searching, this time comparing each colour in our initial Array to each colour in our growing Array of unique colours. Once we have reached our predefined quota of colours, or the end of the Array, we have our beautiful colour palette!

public static function different( colour:uint, colours:Array, tolerance:Number = 0.01 ):Boolean
{
	for (var i:int = 0; i < colours.length; i++) 
	{
		if ( similar( colour, colours[i], tolerance ) )
		{
			return false;
		}
	}
	return true;
}
 
 
 
public static function uniqueColours( colours:Array, maximum:int, tolerance:Number = 0.01 ):Array
{
	var unique:Array = [];
 
	for (var i:int = 0; i < colours.length && unique.length < maximum; i++) 
	{
		if ( different( colours[i], unique, tolerance ) )
		{
			unique.push( colours[i] );
		}
	}
 
	return unique;
}

Putting it all together

I’ve packaged the above technique, as well as the averageColour and averageColours methods from my last post into a ColourUtils class. Most of the methods detailed above, despite being necessary steps in finding an image’s colour palette, are useful in their own right and so I have separated them out into a documented collection of static methods.

You can download my ColourUtils class here along with some examples of its usage.

Download the ColourUtils class which includes the colourPalette method

Download the ColourUtils demo showing you how to use ColourUtils to extract the colour palette from an image.

Possible Enhancements

I have a few ideas for possible enhancements to the algorithm, and would like to hear yours if you have any. Currently, these are my intentions for the next revision:

• Integration of the Müller formula so that a single colour from a group of similar colours is chosen not by its frequency but by its suitability for the extracted palette – i.e. a colour with greater tonal variation is preferred by the algorithm much the same way as it would be by the eye.
• Palette colour sorting by hue, saturation or brightness.
• A faster way of discarding unwanted colours, preferably before looping through the colour index, resulting in much better performance.