"Nearest value" algorithm?

Boxknife · 06-26-2009, 02:31 PM

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}},
};

**Salem** · 06-26-2009, 02:53 PM

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.

Zlatko · 06-26-2009, 02:55 PM

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?)

Boxknife · 06-26-2009, 03:00 PM

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.

ITAmember · 06-26-2009, 03:03 PM

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?

ITAmember · 06-26-2009, 03:20 PM

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?

ITAmember · 06-26-2009, 03:25 PM

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!

nonoob · 06-26-2009, 04:03 PM

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.

ITAmember · 06-26-2009, 04:07 PM

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.

Zlatko · 06-26-2009, 06:30 PM

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.

iMalc · 06-26-2009, 11:42 PM

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.

06-26-2009, 02:53 PM	#2
Salem and the hat of vanishing Join Date: Aug 2001 Location: The edge of the known universe Posts: 21,214	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. __________________ If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut. Up to 8Mb PlusNet broadband from only £5.99 a month!
Salem is offline

06-26-2009, 03:03 PM	#5
ITAmember Registered User Join Date: Mar 2009 Location: Nebraska Posts: 72	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? __________________ Super amazing game!
ITAmember is offline

06-26-2009, 03:20 PM	#6
ITAmember Registered User Join Date: Mar 2009 Location: Nebraska Posts: 72	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? __________________ Super amazing game!
ITAmember is offline

06-26-2009, 03:25 PM	#7
ITAmember Registered User Join Date: Mar 2009 Location: Nebraska Posts: 72	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! __________________ Super amazing game!
ITAmember is offline

06-26-2009, 04:03 PM	#8
nonoob Registered User Join Date: Sep 2008 Location: Toronto, Canada Posts: 494	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.
nonoob is offline

06-26-2009, 04:07 PM	#9
ITAmember Registered User Join Date: Mar 2009 Location: Nebraska Posts: 72	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. __________________ Super amazing game!
ITAmember is offline

06-26-2009, 06:30 PM	#10
Zlatko pwning noobs Join Date: Jun 2009 Location: The Great White North Posts: 125	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. __________________ Sun Certified Java Programmer / Developer IEEE CSDP Last edited by Zlatko; 06-26-2009 at 07:18 PM.
Zlatko is offline

06-26-2009, 11:42 PM	#11
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,434	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. __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Implement of a Fast Time Series Evaluation Algorithm	BiGreat	C Programming	7	12-04-2007 02:30 AM
Euclid Algorithm (extended)Part2 Doubt about pointers - INITIALIZATION	nacho4d	C Programming	4	12-10-2006 07:08 PM
Binary Search Trees Part III	Prelude	A Brief History of Cprogramming.com	16	10-02-2004 03:00 PM
Request for comments	Prelude	A Brief History of Cprogramming.com	15	01-02-2004 10:33 AM