11

I try to get the most matching color name depending on an given hex-value. For example if we have the hex-color #f00 we've to get the colorname red.

'#ff0000' => 'red' '#000000' => 'black' '#ffff00' => 'yellow'

I use currently the levenshtein-distance algorithm to get the closest color name, works well so far, but sometimes not as expected.

For example:

'#0769ad' => 'chocolate' '#00aaee' => 'mediumspringgreen'

So any ideas how to get the result closer?

Here's what I made to get the closest color:

Array.closest = (function () { // http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript function levDist(s, t) { if (!s.length) return t.length; if (!t.length) return s.length; return Math.min( levDist(s.substring(1), t) + 1, levDist(t.substring(1), s) + 1, levDist(s.substring(1), t.substring(1)) + (s[0] !== t[0] ? 1 : 0) ); } return function (arr, str) { // http://stackoverflow.com/q/11919065/1250044#comment16113902_11919065 return arr.sort(function (a, b) { return levDist(a, str) - levDist(b, str); }); }; }());

http://jsfiddle.net/ARTsinn/JUZVd/2/

Another thing is the performance! It seems that it there's somewehere a really big issue that makes this really slow (is it the algorithm?).

Improve this question
9
  • 1
    For more similar colors it would be better to use HSL colors instead. Commented Jun 18, 2013 at 17:58
  • 1
    You could make the sort step a lot faster if you'd precalculate the distances before sorting. Commented Jun 18, 2013 at 18:00
  • Also I'm not sure why you wouldn't use a simple cartesian distance computation. (Actually I guess I'd convert to an angular coordinate space and do the distance in HSL or HSV terns.) Commented Jun 18, 2013 at 18:00
  • 1
    i would calc the diff of two colors by averaging the difference between each of the two color's on each R, G, and B channel. ex (3,4,5) and (10,14,18) have an avg diff of 10. Commented Jun 18, 2013 at 18:01
  • I'll bet you find you have some problem colors that you can leave out of the list. I don't know your problem domain but, perhaps, less is more. If I put up a shade of green and you call it mint or light green or spring green, it might not matter. Commented Jun 18, 2013 at 18:03

1 Answer 1

Reset to default
13

Levenshtein distance isn't really appropriate here, because it will compare character by character for equality. You need to check each color separately, and you would want 79 to be much closer to 80 than 00.

The following seems to be a lot closer to what you want, with only minimal changes to your code:

Array.closest = (function () { function dist(s, t) { if (!s.length || !t.length) return 0; return dist(s.slice(2), t.slice(2)) + Math.abs(parseInt(s.slice(0, 2), 16) - parseInt(t.slice(0, 2), 16)); } return function (arr, str) { return arr.sort(function (a, b) { return dist(a, str) - dist(b, str); }); }; }());

Note that this will only give reasonable results when both s and t are 6-character color hex codes.

Your code is inefficient because you don't need to sort the entire array to get the closest color. You should instead just loop through the array and keep track of the shortest distance.

For example:

Array.closest = (function () { function dist(s, t) { if (!s.length || !t.length) return 0; return dist(s.slice(2), t.slice(2)) + Math.abs(parseInt(s.slice(0, 2), 16) - parseInt(t.slice(0, 2), 16)); } return function (arr, str) { var min = 0xffffff; var best, current, i; for (i = 0; i < arr.length; i++) { current = dist(arr[i], str) if (current < min) { min = current best = arr[i]; } } return best; }; }());

Note that after this change Array.closest() will return a single value rather than an array, so you will need to remove the [0] further down in your code.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Wow, great! Thanks so far :-* reasonable results when both s and t are 6-character color hex codes No problem I convert 3-digit hex-colors to 6 ones :)
BTW: Pointy mentioned that precalculating the distance before sorting makes it even faster?!
one thing to keep in mind is that the G channel is actually more important than the R and B channels.Also not every level step is the same at each of the 0-255 values, ex: 7-2 is a huge change but 132-127 is relatively minor. Screen against this by averaging the perceptually-corrected (NTSC) gray level diff with the avg rgb diff as computed above. I think it should be worth 25%, so add it into the rgb and div by 4 instead of 3. NTSC gray is computed as ((0.29*r)+(0.59*g)+(0.12*b)) / 3 in case you're wondering...
@dandavis Sounds great, though I don't know how to implement that. However, thanks for your mentation, nonetheless :)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.