Thread: "Nearest value" algorithm?

  1. #1
    Registered User
    Join Date
    Jun 2008
    Posts
    54

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

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    Ha Ha Snort!
    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?)

  4. #4
    Registered User
    Join Date
    Jun 2008
    Posts
    54
    Quote Originally Posted by Salem View Post
    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.

  5. #5
    Registered User ITAmember's Avatar
    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?

  6. #6
    Registered User ITAmember's Avatar
    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?

  7. #7
    Registered User ITAmember's Avatar
    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!

  8. #8
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,834
    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.

  9. #9
    Registered User ITAmember's Avatar
    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.

  10. #10
    pwning noobs Zlatko's Avatar
    Join Date
    Jun 2009
    Location
    The Great White North
    Posts
    132
    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.
    Last edited by Zlatko; 06-26-2009 at 07:18 PM.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM