What would be the complexity of this color-quantization algorithm?

Question

I started toying with this idea some years ago when I wrote my university papers. The idea is this - the perfect color quantization algorithm would take an arbitrary true-color picture and reduce the number of colors to the minimum possible, while maintaining that the new image is completely indistinguishable from the original with a naked eye.

Basically the setting is simple - you have a set of points in the RGB cube (from 0 to 255 integer values on each axis). You have to replace each of these points with another point in such a way that:

• The total number of points after the operation is as small as possible;
• The distance from an original point to the replaced point is no larger than some predefined constants R, G and B on each of the red, green and blue axis (these are taken from the sensitivity of the human eye and are in general configurable by the user).

I know that there are many color quantization algorithms out there that work with different efficiencies, but they are mostly targeted at reducing colors to a certain number, not "the minimum possible without violating these constraints".

Also, I would like the algorithm to produce really absolute minimum possible, not just something that is "pretty close to minimum".

Is this possible without a time consuming full search of all combinations (infeasible for any real picture)? My instincts tell me that this is a NP-complete problem or worse, but I cannot prove it.

Bonus setting: Change the limit from constants R,G,B to a function F(R_source, G_source, B_source, R_target, G_target, B_target) which returns TRUE if the mapping would be OK, and FALSE if it was out of range.

Answer 1

Given your definitions the structure of the picture (i.e. how the pixels are organized) does not matter at all, the only thing that matters is the subset of RGB triplets that appear at least once in the picture as a pixel value. Let that subset be S. You want to find then another subset of RGB triplets E (the encoding) such that for every s in S there exists a counterpart e in E such that diff(s,e) <= threshold where threshold is the limit you impose on the acceptable difference and diff(...) reduces the triplet distance into a single number. Additionally, you want to find E that is minimal in size i.e. for any E' s.t. |E'|<|E|, there is at least one (s,e) pair violating the difference constraint.

This particular problem cannot be given an asymptotic complexity assessment because it has only a finite set of instances. It can be solved in constant time (theoretically) by precalculating the minimum set E for every subset S. There is a huge amount of subsets S but yet only a finite number, so the problem cannot be e.g. classified as NP-complete optimization problem or anything. The actual run-time of your algorithm for this parcticular problem hence depends completely on the amount of preprocessing you are willing to tolerate. In order to get an asymptotic complexity assessment you need to generalize the problem first so that the set of problem instances is strictly infinite.

Answer 2

Here's an idea how I'd go about this - unfortunately this will probably need a lot of memory and be very slow:

You create a 256x256x256 cubic data structure that contains a counter and a "neighbors" list of colors. For every unique color that you find in your image you increase the counter of each cell which is within the radius of a sphere around that color. The radius of the sphere is the maximum acceptable distance that you have defined originally. You also add the color to the neighbors list of each cell.

Once you have added all unique colors you loop through the cube and find the cell with the maximum counter value. Add this color to your result list. Now loop through your cube again and remove this color and all colors that are in the neighbors list of that color from all cells and decrease each cell's counter whenever you remove a color. Then repeat searching for the maximum counter and removing until no more colors are in the cube.

Alternatively once could also add the same color multiple times if it occurs more often in the image. Not sure if that would improve the visual result.