PopPalFast

Fast Palette construction for 256 colour bitmaps

July 10th 2003 (UK time)

Intro, Details of the speed up method, Source code, Changes

Intro

Conversion to 256 colour bitmaps from higher colour resolutions can be surprisingly slow. What takes time is the need to construct a suitable colour palette - given that the orginal bitmap may have many more than 256 colours.

The simplest approach to understand is the popularity algorithm- you simply go through all the pixels and count how many there are in each colour and use the most popular colours. However, you don't know in advance how many distinct colours there might be and what colour values they may have. One may first attempt this by setting up an array for the entire colour space with 256*256*256 entries - to contain the colour counts. It will be quite large as each entry will be a four byte integer to be set to the number of pixels found in that colour, making it a 64 MB array, larger than most bitmaps. This gives a time penalty already as it takes a little while to just allocate this amount of memory. Then the count takes time, and then finally, you have to sort the numbers in the array by size, and again, doing a qsort of a 64 MB array doesn't exactly promise to be particularly speedy!

You can speed it up by reducing the colour resolution, e.g. you could use only the five most significant bits for each of the r, g, and b values. This works, but it is enough to make for a noticeable degradation in the exactness of the result - particularly if the bitmap has continuous gradations of colour.

Most resort to other methods such as median cut or octrees.

However, when I needed to code for colour conversion to help users of Virtual Flower and Lissajous 3D who might wish to save the animation frames as 256 colour bitmaps to convert to anmated gifs, I found a super fast popularity method to use instead..

I started off with the popularity algorithm code in Charles Petzold's Programming windows chapter 16 (I'm using the 1999 edition), and had a go at speeding it up first. After using a number of speeding up tricks I was surprised to suddenly find out that the resulting algorithm I had ended up with was fast, very fast indeed in fact.

But - afterwards I learnt that the FreeImage library I'm using already has a colour quantization routine, which I'd somehow missed. It has two fast colour quantization methods - by Xiaolin Wu and Anthony Dekker, which are faster than this one.

Anyway, here is the one I found for anyone interested.

top

Details of the speed up method

I converted it to use sparse arrays which reduces the memory requirements to maybe two or three hundred KB or so, at any rate usually and much less than a megabyte (of course depends on the bitmap). You need to avoid using the slow GetPixel(hdcMem,x,y) too once the algorithm is super fast or your program will spend most of its time on that line.

Then a couple of other ideas speeded it up further. One idea is to combine two of the palettes - make colour palettes for increasing resolution say 5 bits, 6 bits then 7 bits. Stop when you go over 256 colours, which may well be at a resolution of 7 rather than 8. Then use the previously found palette, and add in any new colours you found in the new one. To make sure you add the most useful new colours, use only ones at the maximum distance from the ones already found every time you add a newcolour.

To deal with the problem of the loss of information when you reduce the resolution of the search, keep a record of one of the original pixels for each colour bin. This ensures that every colour in the palette does occur somewhere as a pixel value in the original bitmap rather than being say a 6 bit or 7 bit approximation to one of them..

Finally, to speed up the sort, you just need to keep track of the highest 256 entries as you go through the array. Rather than qsorting it, use the sparse array as it is and simply step through it and add new entries to your 256 element array - which means you quickly speed through the empty sections of it. Keep the array elements in increasing order as you add new entries. Then if you find a colour count that is smaller than any of the entries so far you can skip it at once - which will happen often if the original bitmap has many colours, once you have got just a bit of the way through the count.

All this speeds it up amazingly. I was astonished to find it gave a ten to twenty times speed improvement. From being the slowest of the algorithms I was trying, the popularity algorithm became the fastest, and it also gave good and accurate results too for the images I tried. (Though later I found that the FreeImage libirary I was using actually has a couple of colour quantization algorithms in it already which are faster).

One might speed this up further by using a binary tree to keep the top 256 most popular colours as you go through the sparse array of colour counts - but if so, you need to make sure you have a super-quick way of testing to see if a new element is smaller than all the entries in the tree so far. It is already so fast I haven't bothered to try to speed it up any more. It seems to be as fast or faster than algorithms in commercial graphics programs already, and to give as good results - at least with the images I tested it for - pictures made by my Virtual Flower and Lissajous 3D.

Having made ones palette, then one needs to convert the original bitmap to 8 bit using the palette. Again this can be speeded up - rather than use the slow GetPaletteEntry(...) for every pixel, one can use a sparse array again for the colour space and use that to record the palette value for each new colour value as it is needed,using GetPaletteEntry - but after that you just look it up in the colour space sparse array instead of using the routine again.

Also you can initialise the colour space with all the entries already in the palette (though come to think of it, that just saves 236 calls to GetPaletteEntry so probably isn't a particularly significant speed up).

top

Source code

So anyway without further ado, here is the source. It should be easy enough to read I hope.

poppalfast.zip [9 Kb]

I used it with the FreeImage library. This has an especially clear syntax which should make the code easy to read. You will need the freeimage dll to use the code as it is. Note though that acutally it already has a colour quantization algorithm - you just need to use FreeImage_ColorQuantize(...) so don't need this code!

You can convert it to use ordinary windows routines to convert a bitmap to a device independent bitmap, then look up the bits, colour masks if needed and so forth. For details see Chapter 15 of Charles Petzolds programming windows. You will probably want to use the GetDIBits(hdc, hBitmap,... ) routine at some point to access the bits and colour organisation information,.

Note - if your bitmap might be used in a display set to 256 colour mode actually you want a 236 colour bitmap because Windows will reserve 20 of them for system colours. The source code is based on this assumption. However nowadays this is more often used to reduce the colour in order to make gifs, or smaller pngs, for web pages - in which case one could use all 255 entries.

This is free source - do with it as you like. Treat it as you would a demo program in a c programming book - which the code is originally derived from in fact.

top