Bitmapdata Colour Palette

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 some experimentation 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 the ColourUtils class and also some examples of how to use it:

Download: ColourUtils Download: ColourUtils Demo

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.
Posted on 11 Oct 2008
55 Comments
15 Trackbacks

Meta

BitmapData Colour Palette was posted on October 11th 2008 in the category Code / Actionscript 3.0, Flash, Open Source and tagged; , , , , , , .

You can Leave a comment.


Warning: file_get_contents(http://search.twitter.com/search.atom?q=from:soulwire&rpp=1) [function.file-get-contents]: failed to open stream: HTTP request failed! HTTP/1.0 410 Gone in /home/soulwire/webapps/soulwire_blog/wp-content/themes/soulwire/functions.php on line 203

Discussion

59 Responses to BitmapData Colour Palette

1 3 4 5

Leave a Reply

Pingbacks / Trackbacks

  1. 8 years ago Tracking Multiple Objects Using a Webcam | NORTH Advertising | Brand advertising and content | design + film + interactive + music | Based in Portland, OR

    [...] small in the camera’s depth of field. To overcome this you could search for similar colors. Soulwire has written a sweet Color utility class that can aid you in this endeavor. However, searching for a [...]

  2. 8 years ago actionscript,as3,color,flash10,getColorBoundsRect,motion detection,multiple objects,tracking,webcam | Chris Teso - Director of Digital Media. Portland Photographer. Flash Ninja.

    [...] small in the camera’s depth of field. To overcome this you could search for similar colors. Soulwire has written a sweet Color utility class that can aid you in this endeavor. However, searching for a [...]

  3. 7 years ago BeBlog » BitmapData Colour Palette

    [...] Via | Soulwire [...]

  4. 7 years ago Adobe — наш верный друг » Дайте мне цвет! — блог о air, flash, flex и других технологиях Adobe

    [...] штука – загружаете фотку и вот вам на блюдце почти все [...]

  5. 7 years ago Eamonn O’Brien-Strain :: links for 2009-07-25

    [...] AS3 Colour class for extracting the color palette from a BitmapData image or photo, ColourUtils.as An algorithm to determine the palette of an image. (tags: programming design code flash imaging graphics webpageprinting) [...]

  6. 7 years ago Median Cut « GrgrDvrt

    [...] belle image, tu peux tout de suite aller chez soulwire voir ces articles: couleurs moyennes et extraire une palette de couleurs, c’est plus simple et ça marche mieux. Par contre tu vas rater la partie intéressante de [...]

  1. andrew 6 years ago

    Hi, I am really grateful you put out this work, it is really brilliant!
    anw, do you know how to integrate this code for detecting the color in video?
    coz i have a work that require detecting the video average color value and come out with some respond based on the color

    Reply to this comment

    1. Soulwire 6 years ago

      Just draw the video to a bitmapdata first: myBitmapdata.draw(myVideo); then average that.

  2. Mitch 6 years ago

    Wow great job, and really thanks for sharing.
    Is it possible to extract a color range from an image. To get the black and white effect with 1 color? For example black and white image with the color range light orange to darker orange?

    Reply to this comment

    1. Soulwire 6 years ago

      It sounds like you might want to look at the BitmapData.threshold method.

  3. JH 6 years ago

    Hi, i downloaded the demo, but flash puts out an unexpected file format error when i start the Colour Palette Demo.fla.
    I use flash professional 8
    Please some help, so i can view your demo.

    Reply to this comment

    1. Soulwire 6 years ago

      You’ll need CS3 or above to open it I’m afraid.

  4. JH 5 years ago

    Hi,
    Thank you, that fixed it.
    Little question;
    I am using your code in flex/air. The ColourUtils.as file is exactly the same, the image, the amount of colors in the palette and the tolerance are the same, but i don’t get the same colors as in your example… the colors i get doesn’t even match the image..
    Any idea?
    I can provide a flex example, just let me know by mail.
    Greets, J.

    Reply to this comment

  5. JH 5 years ago

    Please delete my last comment, I did something wrong.
    Greets, J.

    If you want a working example for flex/air just let me know by email and i will send you the example for your site.

    Reply to this comment

  6. danbo 5 years ago

    Nice work. I’m working on maps, your appplication permits many works.
    Very good!

    Reply to this comment

  7. Hcsaba 5 years ago

    Hi, it is a very good job. I can use the unique colors in my second hobby.
    The first is the programming. :) Thanks.

    But I have a little problem. So I think You can help me. Because Google don’t help.
    How to put my 16 unique colors to a paletteMap. And apply to bitmapdata.
    My code work fine with threshold but very slowly.

    for (var i=0; i<actcolsdb; i++) {
    var c1:uint=actcols[i].colour;
    olddist=1000;
    for (var j=0; j> 16) – ((c2 & 0xff0000)>> 16));
    var gx:uint = Math.abs(((c1 & 0xff00) >> 8) – ((c2 & 0xff00) >> 8));
    var bx:uint = Math.abs((c1 & 0xff) – (c2 & 0xff));
    dist=Math.sqrt(rx*rx+gx*gx+bx*bx);
    if (dist<=olddist) {
    olddist=dist;
    id=j;
    }
    }
    Image.threshold(Image,Image.rect,new Point(0,0),"==",returnARGB(c1,255),returnARGB(m_colours[id],255));
    }

    Thanks for reply and sorry my bad English.

    Reply to this comment

  8. Tim 5 years ago

    HI.
    This is amazing work. Very well made coding + tutorial.
    Im trying to embed it with a photo album, so when u switch to another picture, the colors shows.
    Im adding the images from a xml file..
    any help here?
    Thanks alot for the great work so far. Tim

    Reply to this comment

  9. Allie 5 years ago

    Know this is old, but it’s exactly what I was looking for and has a *great* walkthrough. I appreciate it!

    Reply to this comment