Methods for creating a color palette from an image?

Say I have an image, of unspecified color depth and dimensions.

What ways are there of compressing this down to an n-color palette?

My google-fu is weak with this开发者_高级运维 one.

Well the simplest approach is simply to look over the image and create a dictionary mapping pixel colours to ints. For each pixel, if its colour is in the dictionary, increment its count. If it isn't, add it with a count of 1. This gives you the number of times each colour appears in the image.

Then, sort by count and you will find the 256 most-common colours in the image. Those colours make up your palette.

Then, iterate over the image again. For each pixel, find the palette colour which is closest to that pixel's colour, and set that pixel's index to that palette index.

That will be a good "first go", but in images with a lot of colours it might not do such a good job of finding the palette. In the dictionary phase, you may want to combine colours which are "close enough" to avoid having a lot of very similar colours all scoring poorly, even though together they would be very common.

For better results, you will want to look at dithering techniques.

The problem is called color quantization. See pngquant for example.

If you're looking for algorithms, then search for Median Cut, Octtree, K-Means, Linde–Buzo–Gray, NeuQuant. Ideally on Google Scholar, as regular results are spammed by cloaking paywalls.