Fast algorithm to detect main colors in an image?

Question

Does anyone know a fast algorithm to detect main colors in an image?

I'm currently using k-means to find the colors together with Python's PIL but it's very slow. One 200x200 image takes 10 seconds to process. I've several hundred thousand images.

Answer 1

One fast method would be to simply divide up the color space into bins and then construct a histogram. It's fast because you only need a small number of decisions per pixel, and you only need one pass over the image (and one pass over the histogram to find the maxima).

Update: here's a rough diagram to help explain what I mean.

On the x-axis is the color divided into discrete bins. The y-axis shows the value of each bin, which is the number of pixels matching the color range of that bin. There are two main colors in this image, shown by the two peaks.