Algorithm to reduce number of colors used on an image. (sRGB)

Question

Introduction:

I have a program that receives an image as input and does stuff.

The more colors the image has the longer it takes for the program to finish and the less visible the difference between two colors, the less important it is to have both of them.

Since I know very little about working with computer colors I have been using Photoshop to reduce the amount of colors an image has.

The goal:

To convert the program to be usable by normal people.

It will need to have some code capable of reducing the amount of colors on the images given by the users.

I've learned some color reducing theories for image compression but I don't really know how to apply them in practice with the data I have.

The need:

An algorithm that receives a list (or matrix) of sRGB colors and reduces the amount of colors on that list keeping the most information of the original image possible with the colors available.

Preferably one where a number n can be specified which is the number of colors the output will have.

Extra details

Speed is a bit more valuable than color perfection as if possible it would be nice to show the user the converted image in real time (or near real time) so they could see how the settings they chose are going to affect the result.

The user should be able to use lots of colors if desired but the main use case expected is a number between 10 and 200 colors.

I'm looking for descriptions and/or suggestions of algorithms I can learn and implement not random implemented code to copy/steal.

Answer 1

Very briefly, the term you are looking for is colour quantisation which is a subset of the more general Vector Quantisation.

Probably the simplest (and fastest?) one for colour data is that of Heckbert's "Color Image Quantization for Frame Buffer Display".

If you want better quality, there a numerous others but I once wrote a VQ quantiser (for Dreamcast's texture compression) that was based on Wu's "Color quantization by dynamic programming and principal analysis" which I felt produced great results.

Answer 2

One possibility is to use k-means clustering. Here, the number of clusters represents the number of colors in the output image.

This is how you use the k-Means clustering algorithm for color reduction. Color is in 3D space (r, g, b) where each value can be between "0" and "1". By iterating over each pixel of your image, you can add the color of the pixel to your search space. Once this is done for all pixels, you need to specify the number of colors for your output image. Each of them will be given a random 3D value between 0 and 1 in the color space.

Each of your input colors must calculate the distance (Euclidean) to all output colors. The pixel belongs to the output color with the smallest distance. When you have done this for all colors, the positions of the output colors are recalculated. The new position is the arithmetic mean position of all input colors grouped to the output color. This algorithm must be run several times to get good results. You can stop the algorithm if no input color has changed the output color group during a whole iteration.

Be aware that you can have flipping input colors. This means that one or more input color positions are between two output groups and change to the other group on each iteration. Because of this phenomenon, you should add a counter that stops the algorithm after a few iterations.

To get an idea of what the result can look like, let me share one of my projects that uses this technique to reduce colors. In this video you can see the original input object on the left side. On the right side you see the voxelized output. All colors have been reduced to 6 colors. In second 26, the algorithm is applied to the model. If you look closely, you can see that the colors of the voxelized output (on the right) change for a few frames in the video and then become stable.