Color Quantization Algorithm

I'm working on a color quantization algorithm.

This is the basic process:

• Convert the image to a set of three dimensional vectors (RGB space for instance).
• Put that set in a list of sets.
• While the number of sets in the list is less than the number of color you want:
  • Remove the 开发者_如何学运维worst set from the list.
  • Split it in two.
  • Add the two new sets in the list.
• Done.

What I mean by "worst set" is the set where the accumulated distance between each vector and the mean vector is the bigger.

And this is how I "split a set":

• Compute the mean vector by adding all vectors and dividing by vector count.
• Compute a vector composed of the absolute differences between each vector and the mean vector. Normalize it and we got the normal of a plane that divide our vector set in two equal halves.
• Use this normal two split the set in two sets depending on which side of the plane the vectors belong.

This works, basically, but image palette looks odd, like picked out of a linear gradient...

Is my algorithm plain wrong ? Can someone help ?

---

The problem is that your algorithm depends a LOT on the initial sets. Because you only split sets, if two points that are very close to each other happen to be in different sets at the beginning they will always be in different sets. This is not good.

So yes - this is worse than the k-means algorithm.

---

The first step of color quantization is to choose representative K colors from N colors.
However, some gradient/banding problems are inevitable for images having so much colors.
Then error diffusion and dithering works by approximating unavailable colors with available colors, by mixing and matching available colors in a way that mimicks unavailable ones.

Top 6 color quantization algorithms.

Here some examples of output:

Original image:

Reduced to 256 colors by NeuQuant Neural-Net Quantization Algorithm:

Reduced to 256 colors by Xialoin Wu's fast optimal color Quantization Algorithm:

Original photo:

Reduced to 256 colors by NeuQuant Neural-Net Quantization Algorithm:

Reduced to 256 colors by Pairwise Nearest Neighbor Quantization Algorithm:

The readers can see coding of the error diffusion and dithering are quite similar among the top 5 color quantization algorithms.
Each algorithm has its own advantages. I share the source of color quantization to invite further discussion and improvements.
Such source code are written in C++ to gain best performance. It also serves as an opening for studying machine learning.

---

I don't see how this is better than the k-means algorithm. Maybe you should just do regular k-means.