algorithm - Image palette reduction

Question

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 :)

Answer 1

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