Followup: "Sorting" colors by distinctiveness

Question

Original Question

If you are given N maximally distant colors (and some associated distance metric), can you come up with a way to sort those colors into some order such that the first M are also reasonably close to being a maximally distinct set?

In other words, given a bunch of distinct colors, come up with an ordering so I can use as many colors as I need starting at the beginning and be reasonably assured that they are all distinct and that nearby colors are also very distinct (e.g., bluish red isn't next to reddish blue).

Randomizing is OK but certainly not optimal.

Clarification: Given some large and visually distinct set of colors (say 256, or 1024), I want to sort them such that when I use the first, say, 16 of them that I get a relatively visually distinct subset of colors. This is equivalent, roughly, to saying I want to sort this list of 1024 so that the closer individual colors are visually, the farther apart they are on the list.

Answer 1

Do you mean that from a set of N colors, you need to pick M colors, where M < N, such that M is the best representation of the N colors in the M space?

As a better example, reduce a true-color (24 bit color space) to a 8-bit mapped color space (GIF?).

There are quantization algorithms for this, like the Adaptive Spatial Subdivision algorithm used by ImageMagic.

These algorithms usually don't just pick existing colors from the source space but creates new colors in the target space that most closely resemble the source colors. As a simplified example, if you have 3 colors in the original image where two are red (with different intensity or bluish tints etc.) and the third is blue, and need to reduce to two colors, the target image could have a red color that is some kind of average of the original two red + the blue color from the original image.

If you need something else then I didn't understand your question :)

Answer 2

You can split them in to RGB HEX format so that you can compare the R with R's of a different color, same with the G and B.

Same format as HTML

XX XX XX
RR GG BB

00 00 00 = black
ff ff ff = white
ff 00 00 = red
00 ff 00 = green
00 00 ff = blue

So the only thing you would need to decide is how close you want the colors and what is an acceptable difference for the segments to be considered different.

Answer 3

@lassevk

No, that's not what I mean. Given some large and visually distinct set of colors (say 256, or 1024), I want to sort them such that when I use the first, say, 16 of them that I get a visually distinct set of colors.

This is equivalent, roughly, to saying I want to sort this list of 1024 so that the closer individual colors are visually, the farther apart they are on the list.

Answer 4

This also sounds to me like some kind of resistance graph where you try to map out the path of least resistance. If you inverse the requirements, path of maximum resistance, it could perhaps be used to produce a set that from the start produces maximum difference as you go, and towards the end starts to go back to values closer to the others.

For instance, here's one way to perhaps do what you want.

1. Calculate the distance (ref your other post) from each color to all other colors
2. Sum the distances for each color, this gives you an indication for how far away this color is from all other colors in total
3. Order the list by distance, going down

This would, it seems, produce a list that starts with the color that is farthest away from all other colors, and then go down, colors towards the end of the list would be closer to other colors in general.

Edit: Reading your reply to my first post, about the spatial subdivision, would not exactly fit the above description, since colors close to other colors would fall to the bottom of the list, but let's say you have a cluster of colors somewhere, at least one of the colors from that cluster would be located near the start of the list, and it would be the one that generally was farthest away from all other colors in total. If that makes sense.

Answer 5

This problem is called color quantization, and has many well known algorithms: http://en.wikipedia.org/wiki/Color_quantization I know people who implemented the octree approach to good effect.

Answer 6

It seems perception is important to you, in that case you might want to consider working with a perceptual color space such as YUV, YCbCr or Lab. Everytime I've used those, they have given me much better results than sRGB alone.

Converting to and from sRGB can be a pain but in your case it could actually make the algorithm simpler and as a bonus it will mostly work for color blinds too!

Answer 7

N maximally distant colors can be considered a set of well-distributed points in a 3-dimensional (color) space. If you can generate them from a Halton sequence, then any prefix (the first M colors) also consists of well-distributed points.

Answer 8

If I'm understanding the question correctly, you wish to obtain the subset of M colours with the highest mean distance between colours, given some distance function d.

Put another way, considering the initial set of N colours as a large, undirected graph in which all colours are connected, you want to find the longest path that visits any M nodes.

Solving NP-complete graph problems is way beyond me I'm afraid, but you could try running a simple physical simulation:

1. Generate M random points in colour space
2. Calculate the distance between each point
3. Calculate repulsion vectors for each point that will move it away from all other points (using 1 / (distance ^ 2) as the magnitude of the vector)
4. Sum the repulsion vectors for each point
5. Update the position of each point according to the summed repulsion vectors
6. Constrain any out of bound coordinates (such as luminosity going negative or above one)
7. Repeat from step 2 until the points stabilise
8. For each point, select the nearest colour from the original set of N

It's far from efficient, but for small M it may be efficient enough, and it will give near optimal results.

If your colour distance function is simple, there may be a more deterministic way of generating the optimal subset.

Answer 9

1. Start with two lists. CandidateColors, which initially contains your distinct colors and SortedColors, which is initially empty.
2. Pick any color and remove it from CandidateColors and put it into SortedColors. This is the first color and will be the most common, so it's a good place to pick a color that jives well with your application.
3. For each color in CandidateColors calculate its total distance. The total distance is the sum of the distance from the CandidateColor to each of the colors in SortedColors.
4. Remove the color with the largest total distance from CandidateColors and add it to the end of SortedColors.
5. If CandidateColors is not empty, go back to step 3.

This greedy algorithm should give you good results.