Extracting Palette from a 24 or 32 bits picture

[jcottier]

Hi,

I am looking for some src code or libs to compute a palette (256 colors) from a 24 or 32 bits picture.

Can you help?

Thanks

JC

[PeterM]

Sounds like you're talking about colour quantisation (http://en.wikipedia.org/wiki/Color_quantization) (or more likely "color quantization", ick). You may want to search for info on the "median cut" algorithm.

There are probably libraries out there to do it, but I don't know them.

If this could be done as an offline process, maybe something like Image Majick could do it.

[Sol_HSA]

I've written a library (long ago) to do just that - http://sol.gfxile.net/zip/qmedian.zip

can't remember what I wrote as license there but it's free to use as you like, as long as you don't sue me (or something). =)

[jcottier]

Thanks guys.

Sol_HSA, thanks I will have a look at your stuff.

Jean-Claude

[Nikster]

also check out neuquant, much betters results imho and you can get the code with freeimage (24bit) and some pngquant, which will do 32bit rgba.

[lennard]

A standalone tool called Debabelizer does a great job of this kind of task and it will do batch processing on a bunch of files as well.

[Spaceman Spiff]

For those interested, there is a good reference page on Quantization at http://datacompression.info/Quantization.shtml, that includes links to various sources.

One quantization method I would recommend taking a look at is LBG Vector Quantization. There is good page on it at http://www.data-compression.com/vq.shtml


From a game developer standpoint, there are a couple issues with Quantization that most sources don't touch upon: (think of them as more math focused than game focused)

1) Quantizing Alpha channel data.

If all you are doing is running in 256 color mode, and want to convert static art, then almost any method out there will handle converting RGB (3 component) data to indexed color.

If, on the other hand, you are just color reducing textures to save space, and some of those textures have variable data in the Alpha channel, you will find that most of the code and utilities (Photoshop, etc) don't handle quantizing RGBA (4-component) data. (i.e. red with alpha 0 and red with alpha 255 would be quantized to the same value when you really want two different entries). There is one imaging processing app out there that handles it really well, but the name escapes me (I can look it up at work tomorrow if you're interested).

And with Alpha channel data, there is an additional caveat that you might encounter: You may want Alpha == 0, Alpha == 1.0 (255) and Alpha in-between (1-254) to be distinct. i.e. A color with zero transparency and a similar RGB color with a little transparency really should result in two separate quantized values if possible to avoid solid areas turning transparent when quantized and vice versa.

2) Non-uniform distance weighting, or maybe using alternate color spaces to improve visual perception.

Wait, what the frak is he talking about??? Ok. Let’s try and visualize the math behind quantizing RGB colors. Image a Cube… NO! Not this cube: CUBE video takes games to ‘a whole new dimension’ (httphttp://www.joystiq.com/2007/02/01/cube-video-takes-games-to-a-whole-new-dimension/)

Imagine a cube representing the RGB color space, with (0,0,0) at one corner and (255,255,255) at the opposite corner. Every texel from a source texture is represented by a 3D point inside of the RGB cube. The result is thousands of individual points in the RGB Cube. The result of running our quantizing code is to pick to 256 colors – aka 3D points in the cube – to represent the thousands of individual points/colors.

Once we have the 256 quantized colors, every individual color in the source texture is converted to a quantized color. This is usually done by finding the quantized color (aka 3D point) that is closest to the source color as measured in the 3D RGB color cube (aka minimum sqrt(x^2 + y^2 + z2) ). The shorter the distance in the RGB cube that the color has to go to be quantized, the less “quantization error” that results (and the better the result looks). Median-cut or other box-splitting methods have higher quantization error that most newer methods.

Anyway, now that you have the image in your head of points moving around inside a 3D cube, you can ask the question if getting the best mathematical results also means getting the best visual results. The truth is the color changes in some directions and areas of the RGB cube are more noticeable than in other. Some vectors in the RGB color space result in only changes to brightness, other to only color hue, and still others to intensity.

Ok, fast forwarding to the end, as I have to go help my wife… Change your colors from RGB to a different color space such as HSV or HSB (Hue, Saturation, Value/Brightness) and then Quantize them. Apply different, tweakable, weighting values to each component (axis in the color cube) and you can make your quantizer emphasize finding a similar hue, or keeping the brightness close.

You can also calibrate your quantizer for the color-response of your target (if you are doing handheld games for example), and to give more importance (quantized colors) to certain portions of the color space (really bright colors get washed out, so you care less about them so you compress the high end of the brightness axis for example).

[Spaceman Spiff]

Another good link for those interested in quantization, and a very powerful OSS image processing app: http://www.imagemagick.org/Usage/quantize/.

[jcottier]

Thank you guys.

Spaceman Spiff, you seem to know the subject a lot.

JC

[Spaceman Spiff]

Thank you guys.

Spaceman Spiff, you seem to know the subject a lot.

JC

You're quite welcome. At my day job, one of things we're developing for is the Sony PSP. To get decent rendering performance, you really need to use indexed textures (DXTn is totally broken on it), preferably 16-color textures (4-bit) over 256 (8-bit). So giving the content guys dials to adjust to get the best results from so few colors on that particular display is important.