"Nearest value" algorithm?

I want to write a program that will take a user-created RGB value and label it with the name of the closest matching color in a list.

I know I could have the program search through the whole list and compare the user value with each entry in the list, but I want to try for something more efficient and was wondering if you fancy-pants computer science majors knew of any algorwhatevers that might be of use. :)

The list looks like this:

Code:

---

struct color
{
  const char* name;
  int red;
  int green;
  int blue;
  int alpha;
} colors[NUM_COLORS]=
  {
{"black", 0, 0, 0, 1},
{"dark blue", 0, 0, 127, 0},
{"blue", 0, 0, 255, 0},
{"light blue", 127, 127, 255, 0},
{"dark blue-green", 0, 48, 63, 0},
{"blue-green", 0, 96, 127, 0},
{"light blue-green", 127, 175, 191, 0},
{"dark green", 0, 96, 0, 0},
{"green", 0, 192, 0, 0},
{"light green", 127, 223, 127, 0},
{"dark green-yellow", 63, 111, 0, 0},
{"green-yellow", 127, 223, 0, 0},
{"light green-yellow", 191, 239, 127, 0},
{"dark yellow", 127, 127, 0, 0},
{"yellow", 255, 255, 0, 0},
{"light yellow", 255, 255, 127, 0},
{"dark yellow-orange", 127, 105, 0, 0},
{"yellow-orange", 255, 210, 0, 0},
{"light yellow-orange", 255, 232, 127, 0},
{"dark orange", 127, 82, 0, 0},
{"orange", 255, 165, 0, 0},
{"light orange", 255, 210, 127, 0},
{"dark orange-red", 127, 41, 0, 0},
{"orange-red", 255, 82, 0, 0},
{"light orange-red", 255, 168, 127, 0},
{"dark red", 127, 0, 0, 0},
{"red", 255, 0, 0, 0},
{"light red", 255, 127, 127, 0},
{"dark red-brown", 105, 10, 10, 0},
{"red-brown", 210, 21, 21, 0},
{"light red-brown", 232, 138, 138, 0},
{"dark brown", 82, 21, 21, 0},
{"brown", 165, 42, 42, 0},
{"light brown", 210, 148, 148, 0},
{"dark violet", 119, 65, 119, 0},
{"violet", 238, 130, 238, 0},
{"light violet", 246, 192, 246, 0},
{"gray", 127, 127, 127, 0},
{"white", 255, 255, 255, 1},
{"cloudy white", 127, 127, 127, 1},
{"clear", 255, 255, 255, 0}},
};

---

Depends what you mean.

Nearest, based on just the arithmetic difference of two values?

Or nearest, based on the perceived similarity to the observer?
Chromaticity - Wikipedia, the free encyclopedia
The RGB scale is not linear in this respect.

Ha Ha Snort!

Quote:

---

fancy-pants

---

Well, I guess you'd have to read through the entire list in the worst case just to determine which colour is closest to the user's input. How would one measure closeness? I'd try a simple 'distance' calculation between the input r,g,b and the ones in colors (you mis-spelled it by the way), then choose the one with the smallest error. You know what I mean? (r-red)^2+(g-green)^2+(b-blue)^2. I don't know what alpha is. (I'm new here, are we allowed to post even if we don't know?)

Quote:

---

Originally Posted by Salem

Depends what you mean.

Nearest, based on just the arithmetic difference of two values?

Or nearest, based on the perceived similarity to the observer?
Chromaticity - Wikipedia, the free encyclopedia
The RGB scale is not linear in this respect.

---

As long as it's in the ballpark, it's fine.

The program I'm writing is just a part of a text game.
Basically, I plan to allow players to mix different colored liquids together to produce new ones and want the resulting liquids' colors to be somewhat realistic.

alpha regarding color determines the amount of translucency in the image. kind of like see-through. like the window boarders in vista. 32 bit color depth images have 8 bits for red, green, blue, and alpha for each pixel.

as for the algorithm i have no idea. :) i was just explaining alpha.

EDIT:

so why can't you use full 24 or 32 bit color?

I suppose if all the components of your colors were in intervals of, say, 64 you could do simple division. Say your color is (234, 73, 147). you could divide each side by 64 and round to the nearest number. That would give you (4, 1, 2). Then you could loop over and check for equality.

Or if you wanted to, you could shift each number over 3 * index position bits (that's for a 64 bit threshold, you would change it for a different threshold) and add them together. I'm pretty sure you could use that number to index an array. Do you gurus see any problem with this algorithm?

You would have this list of color values:


(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
(0, 0, 3)
(0, 0, 4)
(0, 1, 0)
(0, 1, 1)
(0, 1, 2)
(0, 1, 3)
(0, 1, 4)
(0, 2, 0)
(0, 2, 1)
(0, 2, 2)
(0, 2, 3)
(0, 2, 4)
(0, 3, 0)
(0, 3, 1)
(0, 3, 2)
(0, 3, 3)
(0, 3, 4)
(0, 4, 0)
(0, 4, 1)
(0, 4, 2)
(0, 4, 3)
(0, 4, 4)
(1, 0, 0)
(1, 0, 1)
(1, 0, 2)
(1, 0, 3)
(1, 0, 4)
(1, 1, 0)
(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 1, 4)
(1, 2, 0)
(1, 2, 1)
(1, 2, 2)
(1, 2, 3)
(1, 2, 4)
(1, 3, 0)
(1, 3, 1)
(1, 3, 2)
(1, 3, 3)
(1, 3, 4)
(1, 4, 0)
(1, 4, 1)
(1, 4, 2)
(1, 4, 3)
(1, 4, 4)
(2, 0, 0)
(2, 0, 1)
(2, 0, 2)
(2, 0, 3)
(2, 0, 4)
(2, 1, 0)
(2, 1, 1)
(2, 1, 2)
(2, 1, 3)
(2, 1, 4)
(2, 2, 0)
(2, 2, 1)
(2, 2, 2)
(2, 2, 3)
(2, 2, 4)
(2, 3, 0)
(2, 3, 1)
(2, 3, 2)
(2, 3, 3)
(2, 3, 4)
(2, 4, 0)
(2, 4, 1)
(2, 4, 2)
(2, 4, 3)
(2, 4, 4)
(3, 0, 0)
(3, 0, 1)
(3, 0, 2)
(3, 0, 3)
(3, 0, 4)
(3, 1, 0)
(3, 1, 1)
(3, 1, 2)
(3, 1, 3)
(3, 1, 4)
(3, 2, 0)
(3, 2, 1)
(3, 2, 2)
(3, 2, 3)
(3, 2, 4)
(3, 3, 0)
(3, 3, 1)
(3, 3, 2)
(3, 3, 3)
(3, 3, 4)
(3, 4, 0)
(3, 4, 1)
(3, 4, 2)
(3, 4, 3)
(3, 4, 4)
(4, 0, 0)
(4, 0, 1)
(4, 0, 2)
(4, 0, 3)
(4, 0, 4)
(4, 1, 0)
(4, 1, 1)
(4, 1, 2)
(4, 1, 3)
(4, 1, 4)
(4, 2, 0)
(4, 2, 1)
(4, 2, 2)
(4, 2, 3)
(4, 2, 4)
(4, 3, 0)
(4, 3, 1)
(4, 3, 2)
(4, 3, 3)
(4, 3, 4)
(4, 4, 0)
(4, 4, 1)
(4, 4, 2)
(4, 4, 3)
(4, 4, 4)

that's 125 total.

Generate an array of them with the above method and you can index it with your new color index!

That would work if it's guaranteed that those human-perceived colors such as light-brown and cloudy white are guaranteed to be mappable to larger grained intervals or RGB values - and still remain unique. Plus you'd end up with a very sparse (wasteful) array with just a relatively few defined colors that have human names associated with them.

What if someone were to add some new oddball color such as "ultra maroon" (Bugs Bunny reference), then your direct indexing scheme may not work.

Linear search using 'nearest' as in Zlatko's method seems the most reasonable. Treat the RGB as coordinates in 3-dimensional space and find shortest distance.

But until you had millions of reference colors to search through, times millions of anticipated searches, I wouldn't start worrying about maybe implementing a 3-dimensional variant of quad tree or some such.

I realize the shortcommings of my approach. The OP just wanted a faster method without looping through everything. The 3D search would be by far the most flexible and most accurate.

Yo Yo Yo Check it out fo' shizzle.

DivShare File - out.html

The html available in the above link shows what colors match to the OP's color array using the simple 'shortest distance' formula.

Most of the time it's pretty close, but the light blue green row has a lot of variation at the end.
Also, white and gray are way off. I think the idea needs to be refined.

I would consider constructing a KD-Tree, and look the names up using that.
When building the tree, the set of all possible values for that branch get passed down to that branch. Then you sort according to the next dimension and pass the set of appropriate ones to the next branches.
Note that sometimes colours will be passed down to both branches because their value is close to the splitter value. You stop splitting when there is at most a certain number of colours left in a branch. You'd then finish off with a distance calculation.