Thursday, September 6, 2012

Color Distribution Methodology

Getting independent colors which are maximally dissimilar from all previous colors is a fairly common problem. The standard suggested algorithm is to subdivide the most significant differences in colors and then pattern them. I thought this was the case too. So much so that I solved the problem because I thought it would be very useful (and it might). Generally this required two minor breakthroughs understanding how to encode maximally significant differences in colors through binary (flip the ends), which I went through a lot of struggle to get to including my anti-gray codes and derivation algorithm and proof (intersperced gray codes with an additional zero anywhere in it and flipped will maximize hamming distance). And secondly understanding the patterning such that I could derive any value without iteration of the previous values.

Well, looking at the results, it quickly seems that they aren't that great.

Largely there are issues with greens being pretty close even when their RGB values are far, and the patterns constantly making what turn out to be slight variations of your standard pure colors RGB and CYM. You start clashing rather quickly.

The better solution is computationally much more difficult. And generally sort of cheating. You do the hard work. You run through every color you can represent in RGB (16,77,216 of them) and run a heavy duty color distance routine, likely CIE-Lab 2000, then you go in there and manually choose the colors. And then use this as a master list and just read from the list. The standard solution starts picking some greens that look pretty much like the previous greens after like 20. And you should be able to get like 50 colors or so which are visually distinct from one another. Perhaps with pruning of the list by hand.

Using 20k guesses (rather than brute forcing 16-million) I produced this after an hour or so.

There's likely not much left to gain brute forcing the algorithm, but I did (for a smaller value 64) and came out with this.

Which manages to out perform the heck out of the dividing algorithm and could just be read by a standard list. There might be some enhancements to be achieved by converting away from finding maximally good results initially which may cost the overall result to become pareto optimal. Or employ something like k-mean clustering in LabDE2000 colorspace (not really defined as a colorspace but pretty much is exactly that) to better maximize the list. Or goodness forbid collect data by humans voting (it's how the color spaces came about, that and math to approximate that data). Although, this would need to be done in somewhat controlled systems because human eyes are excessively sensitive to conditions. Some colors look similar on a black background when they wouldn't on a white background. Which could maybe be randomized to average out or find colors that do this less than others. It wouldn't be too hard to define a list or two which specifically address this question, because programmatically the question of which colors seem very distinct from a set of previously distinct colors has nothing really to do with computers but humans and how they perceive color, and the ability to approximate this has everything to do with humans and not that much to do with programming.

Observations which have been noted before.
http://www.edwardtufte.com/bboard/q-and-a-fetch-msg?msg_id=0001JS

There are some good color dictionaries out there. But, I'm not convinced there are much more optimal solutions. And it turns out the algorithms needed are much better at making color dictionaries than they would be generating colors on the fly. And since we're dealing with 64 colors max, we're much better doing that.

Miguel Sánchez said...

Ok, so here it is your list for others not to do it again:

R - G - B
0 0 0
1 0 103
213 255 0
255 0 86
158 0 142
14 76 161
255 229 2
0 95 57
0 255 0
149 0 58
255 147 126
164 36 0
0 21 68
145 208 203
98 14 0
107 104 130
0 0 255
0 125 181
106 130 108
0 174 126
194 140 159
190 153 112
0 143 156
95 173 78
255 0 0
255 0 246
255 2 157
104 61 59
255 116 163
150 138 232
152 255 82
167 87 64
1 255 254
255 238 232
254 137 0
189 198 255
1 208 255
187 136 0
117 68 177
165 255 210
255 166 254
119 77 0
122 71 130
38 52 0
0 71 84
67 0 44
181 0 255
255 177 103
255 219 102
144 251 146
126 45 210
189 211 147
229 111 254
222 255 116
0 255 120
0 155 255
0 100 1
0 118 255
133 169 0
0 185 23
120 130 49
0 255 198
255 110 65
232 94 190

Miguel Sánchez said...

Oops, I failed to say thanks at the end of my post ;-)

Tatarize said...

public static final String[] indexcolors = new String[]{
"#000000", "#FFFF00", "#1CE6FF", "#FF34FF", "#FF4A46", "#008941", "#006FA6", "#A30059",
"#FFDBE5", "#7A4900", "#0000A6", "#63FFAC", "#B79762", "#004D43", "#8FB0FF", "#997D87",
"#5A0007", "#809693", "#FEFFE6", "#1B4400", "#4FC601", "#3B5DFF", "#4A3B53", "#FF2F80",
"#61615A", "#BA0900", "#6B7900", "#00C2A0", "#FFAA92", "#FF90C9", "#B903AA", "#D16100",
"#DDEFFF", "#000035", "#7B4F4B", "#A1C299", "#300018", "#0AA6D8", "#013349", "#00846F",
"#372101", "#FFB500", "#C2FFED", "#A079BF", "#CC0744", "#C0B9B2", "#C2FF99", "#001E09",
"#00489C", "#6F0062", "#0CBD66", "#EEC3FF", "#456D75", "#B77B68", "#7A87A1", "#788D66",
"#885578", "#FAD09F", "#FF8A9A", "#D157A0", "#BEC459", "#456648", "#0086ED", "#886F4C",
"#34362D", "#B4A8BD", "#00A6AA", "#452C2C", "#636375", "#A3C8C9", "#FF913F", "#938A81",
"#575329", "#00FECF", "#B05B6F", "#8CD0FF", "#3B9700", "#04F757", "#C8A1A1", "#1E6E00",
"#7900D7", "#A77500", "#6367A9", "#A05837", "#6B002C", "#772600", "#D790FF", "#9B9700",
"#549E79", "#FFF69F", "#201625", "#72418F", "#BC23FF", "#99ADC0", "#3A2465", "#922329",
"#5B4534", "#FDE8DC", "#404E55", "#0089A3", "#CB7E98", "#A4E804", "#324E72", "#6A3A4C",

Tatarize said...

Posted a more complete list,
http://stackoverflow.com/questions/33295120/how-to-generate-gif-256-colors-palette

Generally colors just aren't that distinct. You should use other classifications like candycaning, line breaks, thickness, etc. Also, there are color blind people and they will be even less able to tell the differences. Distinct colors are better as a list, but get progressively less useful after about 20-30 items. More if you consider things like the background colors you're using. A white background will cause colors to look like other colors than a black background, and somethings like yellow might not even be visible (yellow on white is basically invisible).