Image palette reduction

Question

Hello SO,
I am playing with computer graphics programming for the first time.
Don't ask me why, but it feels like a good day to convert RGB (24bit) images, to indexed-palette (8bit) images (like GIF).
How would one go about picking the optimal palette, for a given image?
I just thought of going with k-means, with k=256.
Any suggestions, or past experience are welcomed.
Remember, this is a learning experience for me, so I would rather have a more overviewish answer, than bits and bytes.
In addition, what language would one choose for the job?
I speak Java and C/C++ fluently. Would C be really faster than Java (as I imagine many will say).

Edit: Dithering is currently off-topic. I am only referring to "simple" colour conversion, psycho-visual/perceptual models aside; colour-space is also currently off-topic, though moving between colour-spaces is what got me thinking about this in the first place :)

Answer 1

http://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).

Answer 2

• http://en.wikipedia.org/wiki/Color_quantization
• Octree
• Median-cut
• K-means
• Gamut subdivision
• http://www.cs.berkeley.edu/~dcoetzee/downloads/scolorq/

Answer 3

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.