Image palette reduction?

EDIT: updated to support palette of 256 colors.

Up vote 5 down vote favorite 3 share g+ share fb share tw.

I am playing with computer graphics programming for the first time. I want to convert RGB (24-bit) images to indexed-palette (8-bit) images (like GIF). My initial thought is to use k-means (with k=256).

How would one go about picking the optimal palette for a given image? This is a learning experience for me, so I would prefer an overview-type answer to source code. Edit: Dithering is currently off-topic.

I am only referring to "simple" color conversion, psycho-visual/perceptual models aside; color-space is also currently off-topic, though moving between color-spaces is what got me thinking about this in the first place :) algorithm image-processing gif link|improve this question edited Nov 7 '11 at 21:19Jason Sundram1,75921331 asked Oct 3 '10 at 8:35Trevor 1566 75% accept rate.

This is no simple task. There's a lot that can go into this type of conversion (dithering & human color perception for example). You just asked quite a mouthful... a whole college course full, I'd wager :) – JoshD Oct 3 '10 at 8:39 +1 for a good question...see my answer below.

You may want to start with conversion between 24-bit values and the standard "web safe" palette. That will be far less complex than determining your own palette (though probably not as much fun). – Tim Medora Oct 3 '10 at 9:00.

EDIT: updated to support palette of 256 colors If you need simplest method then I would suggest histogram based approach: Calculate histograms of R/G/B channels Define 4 intensity ranges For each channel in intensity range Split histogram into 4 equal parts For each histogram part Extract most frequent value of that part Now you will have 4*4^3=256 colors palette. When assigning pixel to palette color, just calculate average intensity of pixel to see what intensity region you must use. After that just map one of those 64 colors of intensity region to pixel value.

Good luck.

So, for each (RGB) channel, I have 4 intensity-range buckets (0-63, 64-127, 128-191, 192-255). Each of which further divided into 4 sub-range buckets (e.g. 0-15, 19 Oct, 39 Oct, 49 Oct for the 0-63 range); Giving a total of 16 buckets per channel. Each such (sub-)bucket will be represented in the form of its mean value (say 12 for the R0-15 sub-bucket).

I now have a total of 16 Red (and same for Green and Blue), for a total of 16*16*16=4096 colors?! What did I get wrong?! – Trevor 9 Oct at 12:26 That's because you mixed colors from different intensity range buckets.

Algorithm idea is to find-out which intensity bucket to use- for example calculate pixel intensity Ip=(R+G+B)/3. Then choose intensity bucket by this Ip and use the SAME intensity bucket for all three R/G/B channels. (If some value is out of intensity range, just use leftmost or rightmost sub-bucket in current range).

So, resume - don't mix sub-buckets from different buckets and everything will be fine. Also don't use mean value for sub-bucket - use most frequent value, otherwise this method won't work. – 0x69 Oct 4 '10 at 13:51 Or you could also try 8*8*4 approach (with no sub-buckets at all), because human eye is more sensitive to red,green than to blue.

– 0x69 Oct 5 '10 at 6:41 There are many possible ways one could have gone about it. In fact, I am not sure the above proposed one, is the one I'll take. However, it is both good, and well commented afterwards.

So my V goes to this one. – Trevor 9 Oct at 18:18.

URL1 Octree Median-cut K-means Gamut subdivision cs.berkeley.edu/~dcoetzee/downloads/scolorq.

en.wikipedia.org/wiki/Color_quantization In this case, C++ will potentially be much faster than Java because of its ability to directly manipulate memory. I am much better with . Net than Java, but for what it's worth, my team always uses either managed C++ or unsafe (memory-manipulation) code in C# to perform byte-level tasks like scanning and modifying thousands or millions of pixels.

The difference between managed and unmanaged code when processing pixels can be as significant as 10 to 1. A Java expert may be able to provide more insight on equivalent functionality, but I'm not sure it exists. If you really want to get deep into your question, you will also want to consider the color profile in use on the machine (and/or supply a profile to your algorithm).

The reference links people have provided are good, and there are several solutions to this problem, but since I've been working on this problem recently (with complete ignorance as to how others have solved it), I offer my approach in plain English: Firstly, realize that (human perceived) color is 3-dimensional. This is fundamentally because the human eye has 3 distinct receptors: red, green, and blue. Likewise your monitor has red, green, and blue pixel elements.

Other representations, like, hue, saturation, luminance (HSL) can be used, but basically all representations are 3-dimensional. This means RGB color space is a cube, with red, green, and blue axes. From a 24-bit source image, this cube has 256 discrete levels on each axis.

A naive approach to reducing the image to 8-bit is to simply reduce the levels per axis. For instance, an 8x8x4 cube palette with 8 levels for red and green, 4 levels for blue is easily created by taking the high 3 bits of the red and green values, and the high 2 bits of the blue value. This is easy to implement, but has several disadvantages.

In the resulting 256 color palette, many entries will not be used at all. If the image has detail using very subtle color shifts, these shifts will disappear as the colors snap into the same palette entry. An adaptive palette approach needs to account for not just averaged/common colors in the image, but which areas of color space have the greatest variance.

That is, an image that has thousands of subtle shades of light green requires a different palette than an image that has thousands of pixels of exactly the same shade of light green, since the latter would ideally use a single palette entry for that color. To this end, I took an approach that results in 256 buckets containing exactly the same number of distinct values each. So if the original image contained 256000 distinct 24-bit colors, this algorithm results in 256 buckets each containing 1000 of the original values.

This is accomplished by binary spatial partitioning of color space using the median of distinct values present (not the mean). In English, this means we first divide the whole color cube into the half of pixels with less than the median red value and the half with more than the median red value. Then, divide each resulting half by green value, then by blue, and so on.

Each split requires a single bit to indicate the lower or higher half of pixels. After 8 splits, variance has effectively been split into 256 equally important clusters in color space. In psuedo-code: // count distinct 24-bit colors from the source image // to minimize resources, an array of arrays is used paletteRoot = {colors: color0,count,color1,count, ...} // root node has all values for (i=0; I Sort(colorPlane) // sort by red, green, or blue node.

Lo = { colors: node. Colors0..node.colors. Length/2 } node.

Colorsnode.colors. Length/2..node.colors. Length } delete node.

Colors // free up space! Otherwise will explode memory node. SplitColor = node.hi.

Colors0 // remember the median color used to partition node. ColorPlane = colorPlane // remember which color this node split on } } You now have 256 leaf nodes, each containing the same number of distinct colors from the original image, clustered spatially in the color cube. To assign each node a single color, find the weighted average using the color counts.

The weighting is an optimization that improves perceptual color matching, but is not that important. Make sure to average each color channel independently. The results are excellent.

Note that it is intentional that blue is divided once less than red and green, since the blue receptors in the eye are less sensitive to subtle changes than red and green. There are other optimizations possible. By using HSL you could instead put the higher quantizing in the luminance dimension instead of blue.

Also the above algorithm will slightly reduce overall dynamic range (since it ultimately averages color values), so dynamically expanding the resulting palette is another possibility.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.