Need efficient algorithem to search a Color in an array
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: Need efficient algorithem to search a Color in an array

  1. #1
    Join Date
    Feb 2009
    Posts
    7

    Need efficient algorithem to search a Color in an array

    I am trying to find an efficient algorithem to search from a given Color array the closest color to another given Color. The best match is the one where the difference between its R, G, B values are the lowest - i.e. The minimal of abs(Color1.R - Color2.R) + abs(Color1.G - Color2.G) + abs(Color1.B - Color2.B).
    Is there an algorithem that allows me to search for this color in way that won't require me to run on all my array, i.e. an algorithem that will run in less than O(n)? I am free to organize my array of colors any way I want.
    Thanks for the help!

    BTW, I am using .Net 3.5, But i think that this problem is a very general one.
    Last edited by blabla2006; May 28th, 2010 at 04:03 PM.

  2. #2
    Join Date
    Jun 2008
    Posts
    2,477

    Re: Need efficient algorithem to search a Color in an array

    well, you can sort the array first, but remember that also takes time depending on the sort algorithm. Is this proving to be a bottleneck in your application?
    If you liked my post go ahead and give me an upvote so that my epee.... ahem, reputation will grow.

    Yes; I have a blog too - http://the-angry-gorilla.com/

  3. #3
    Join Date
    Feb 2009
    Posts
    7

    Re: Need efficient algorithem to search a Color in an array

    sort it by what? R? G? B?
    And yes, this is a real bottleneck in my app. I am searching a color in the array thounsnds of times, and it may contain thousands of different colors, so I need it as efficient as possible.

  4. #4
    Join Date
    Jul 2001
    Location
    Sunny South Africa
    Posts
    11,101

    Re: Need efficient algorithem to search a Color in an array

    What about using the GetPixel API - it is very quick and it does return the certain colour at a certain point? Just an idea...

  5. #5
    Join Date
    Feb 2009
    Posts
    7

    Re: Need efficient algorithem to search a Color in an array

    it won't help - i have an array of individual colors, not a bitmap.
    This is realy a more of a computer science problem rather than a C# one. I need some sort of structure that will allow me to search an array by 3 variables rather then just one. The problem is that the best R value of the pixel may be very different from the best B value, and the two of them may be different from the best G value.

  6. #6
    Join Date
    Mar 2007
    Posts
    90

    Re: Need efficient algorithem to search a Color in an array

    Hello blabla2006,
    Although I do not know exactly what you are doing I suspect that your method for searching the closest color to another given color is wrong.
    Considering a color is a 3D vector who's coordinates are (R,G,B) the function that should be used to determine its distance from another 3D vector (color) should be the euclidean distance function.
    So looking for the distance of color C from the color P should look something like:
    Code:
    Math.Sqrt((C.R - P.R) * (C.R - P.R) + (C.G - P.G) * (C.G - P.G) + (C.B - P.B) * (C.B - P.B))
    Since you are only interested in the distance compared to others you can remove the square root and compare the squares, which brings me to say that you cannot calculate that distance beforehand.

    Where exactly is the bottleneck? Accessing the image? Looping the array? How big is it anyway? Is it represented in memory as an array of the System.Drawing.Color structure?

    Are you doing a Floyd-Steinberg dithering by any chance?

  7. #7
    Join Date
    May 2007
    Posts
    1,546

    Re: Need efficient algorithem to search a Color in an array

    There's no easy way to do this as there's no easy way to sort the colors beforehand. If you use that as your definition of closeness and tried sorting your array you'd end up putting colors which are visually completely beside each other.

    If you want to speed up your searching you're going to have some way of sorting your colors so you can either do dictionary-like lookups or binary searches to find the closest match.

    EDIT: If you have a list of known colors and you're trying to convert a random color to one of your 'known' colors, you could create a 3D lookup table (R, G, B) and use the euclidean distance as a way to binary search the lookup table.
    Last edited by Mutant_Fruit; May 29th, 2010 at 12:29 PM.
    www.monotorrent.com For all your .NET bittorrent needs

    NOTE: My code snippets are just snippets. They demonstrate an idea which can be adapted by you to solve your problem. They are not 100% complete and fully functional solutions equipped with error handling.

  8. #8
    Join Date
    May 2010
    Posts
    7

    Re: Need efficient algorithem to search a Color in an array

    What do you mean by search an array by three variables? All points in color space are three dimensional; you kinda have to. Did you actually mean than you wanted to look at only one component at a time and try some kind of optimization that way? You can't do that.

  9. #9
    Join Date
    Feb 2009
    Posts
    7

    Re: Need efficient algorithem to search a Color in an array

    Quote Originally Posted by someuser77 View Post
    Hello blabla2006,
    Although I do not know exactly what you are doing I suspect that your method for searching the closest color to another given color is wrong.
    Considering a color is a 3D vector who's coordinates are (R,G,B) the function that should be used to determine its distance from another 3D vector (color) should be the euclidean distance function.
    So looking for the distance of color C from the color P should look something like:
    Code:
    Math.Sqrt((C.R - P.R) * (C.R - P.R) + (C.G - P.G) * (C.G - P.G) + (C.B - P.B) * (C.B - P.B))
    Since you are only interested in the distance compared to others you can remove the square root and compare the squares, which brings me to say that you cannot calculate that distance beforehand.

    Where exactly is the bottleneck? Accessing the image? Looping the array? How big is it anyway? Is it represented in memory as an array of the System.Drawing.Color structure?

    Are you doing a Floyd-Steinberg dithering by any chance?
    I am buildig a program that builds image mosaics. In order to do this, I take the average RGB colors from a directory of images (Thousands of them) and for each tile in the target image I search its closest match in my array. So I am doing (on average) somthing like 5000 searches on a color array the size of 2000. So I was hoping i can improve my iteration on my color array.
    BTW, for some reason I get better looking results when using my orignal comparing method, Though when I think about it yours is more accurate. Its weird...
    Last edited by blabla2006; May 29th, 2010 at 01:00 PM.

  10. #10
    Join Date
    May 2007
    Posts
    1,546

    Re: Need efficient algorithem to search a Color in an array

    Well, if you really want to spend the time you could turn your directory of images into an RGB lookup table easily enough. Psuedo code would be:
    Code:
    // This can be considered to be a table spanning all the possible values in [r, g, b]
    var lookup = new string[255, 255, 255];
    
    // Populate the lookup table
    foreach (string file in MyDirectory) {
        Color c = CalculateAverageColor (file);
        lookup [c.R, c.G, c.B] = file;
    }
    
    // The idea here is that we first check for an exact match, then we
    // circle outwards trying to find the closest color. First with 1 color
    // difference, then with 2, etc etc. The code below is a very simplistic
    // version of the algorithm but you should be able to figure it out
    // from there. There are probably better ways of implementing this
    // but it'll do ;) For example you need to be able to cope of matching
    // [200, 150, 150] to [203, 150, 150].
    var c = RandomColor ();
    string result = null;
    if ((result = lookup [c.R, c.G, c.B]) != null)
        return result; // We have a direct match, use it!
    else {
        for (int i = 1; i < 255; i++) {
            if ((result = lookup [c.R + i, c.G, c.B]) != null)
                return result;
            else if ((result = lookup c.R - i, c.G, c.B]) != null;
                return result;
           ... similarly for G and B.
        }
    }
    Last edited by Mutant_Fruit; May 30th, 2010 at 11:14 AM.
    www.monotorrent.com For all your .NET bittorrent needs

    NOTE: My code snippets are just snippets. They demonstrate an idea which can be adapted by you to solve your problem. They are not 100% complete and fully functional solutions equipped with error handling.

  11. #11
    Join Date
    Jun 2001
    Location
    Melbourne/Aus (C# .Net 4.0)
    Posts
    686

    Re: Need efficient algorithem to search a Color in an array

    Stating the obvious...

    If your array hardly changes, then when you build it, you need to add as much information into it (not just the colour) as possible. So as to allow your lookup routine to be as efficient as possible. This may mean creating multiple arrays/list/dictionarys with differing keys etc.

    This is analogous with adding indexes to a Database table. There is extra overhead when adding entries, but lookup is much quicker.
    Rob
    -
    Ohhhhh.... Old McDonald was dyslexic, E O I O EEEEEEEEEE.......

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center