>
Blog
Book
Portfolio
Search

2/28/2011

4450 Views // 0 Comments // Not Rated

A Color Comparison Algorithm

Every once in a while you are presented with an opportunity to write something that is truly cool. And by "cool" I don't mean programmatically interesting or logically fun. I've done cool things with SharePoint list event handlers and cool things with .NET RIA Services, for example. But what I mean here is something, literally, cool; something that someone who is not in the world of software development would overhear and think to themselves, "Wow. That sounds...cool."

We are building a Facebook-ish Silverlight application for a group of designers. Part of the data model for this app is the storage of about two thousand "Defined Colors," which they use in their brands. Each color is stored in a bit-shifted integer representation (four 8-bit bytes smashed together) of the component aRGB values. The requirement was to allow users to be able to select an image from their machine, and have it pop open on the page. They could then click anywhere within in, and based on the shade of the selected pixel, I needed to return the closest color to it from among the palette of Defined Colors.

Yeah. That's cool.

My brain immediately whirred with how this could be done. I had played with WritableBitmap in the past for some lightweight photo-cropping functionality I needed, and knew this was the correct vehicle to use. Not only did it serve as an ImageSource, but also provided an aperture into the underlying array of pixels beneath the image, not unlike a microscope exposing the atoms making up a flower. However, this was not the cool part, not the part that exited me.

The cool part was the algorithm that flew into my head to compare two colors for similarity. The math wasn't complicated at all (as you'll see); it was the careful dissection of the colors that I found fascinating. Any time something abstract can be mapped to a system of numbers, I feel like anything is possible. That's how technologies like voice recognition or handwriting-to-text conversion probably came about: whittle it down to a number, something you can work with, something that follows rules, and we can make it do anything.

Suddenly my excitement waned and quickly turned to anxiety. The lines of code that I had already begun subconsciously composing in my head seemed so simplistic - someone had certainly done something like this before...right? But a little bit of Binging put my mind back at ease. If this has been done, and then had been written up, it wasn't well tagged; I couldn't find anything quite like what I came up with. A lot of things were close: calculating luminosity, converting hex to RGB, etc. But there was nothing exactly hitting home regarding the comparison of two colors. Perhaps it had been deemed too obscure or unusable to be worth the time to blog. Either way, it was a rare occurrence for me to be glad not to find what I was looking for; this was my story to tell.

So let's get to it. My idea was to first lobotomize the "input" color (corresponding to the clicked-on pixel from the image) and store its constituent aRGB parts as four integer variables. Next, spin through all of the Defined Colors, performing the same operation on them. In each iteration, we need to obtain a new color, the literal "difference" between the current Defined Color and selected input color, by subtracting the aRGB values from one another, component by component. In other words: for each comparison, subtract alpha from alpha, red from red, green from green, and blue from blue. I'll refer to this "new" color as the "offset color."

Now that we have each "difference," we need to know which one is the least different. This is done by summing the four parts of each offset color, (which I'll call the "constituent sum" because that sounds awesome) and tracking the smallest such sum as we iterate through our palette. Think of these aRGB values as vectors with the same origin and length. If we have an input vector and a finite set of source vectors, the one pointing in the "closest" direction to our input is the one with the smallest magnitude of difference from it; the one least offset from it.

Turns out it's the same story with colors. Basically, after enumerating the source Defined Colors, we grab the one corresponding to the offset color whose constituent sum produced that smallest delta from the input color's sum. And upon testing, it totally worked! I think the code is much more straightforward than the narrative, so let's take a look:

Code Listing 1

  1. private Color GetClosestColor(Color color)
  2. {
  3. //initialization
  4. int minA = byte.MaxValue;
  5. int minR = byte.MaxValue;
  6. int minG = byte.MaxValue;
  7. int minB = byte.MaxValue;
  8. Color closest = Colors.Transparent;
  9. //iterate all colors
  10. foreach (DefinedColor dc in DataAccessLayer.GetAllDefinedColors())
  11. {
  12. //get each .net color
  13. Color c = Utilities.GetColorFromDefinedColorRGB(dc.RGB);
  14. //subtract the components
  15. int a = Math.Abs(c.A - color.A);
  16. int r = Math.Abs(c.R - color.R);
  17. int g = Math.Abs(c.G - color.G);
  18. int b = Math.Abs(c.B - color.B);
  19. //determine if the sum of the differences of this color is the least of all so far
  20. if ((a + r + g + b) < (minA + minR + minG + minB))
  21. {
  22. //if so, this is the closest color
  23. minA = a;
  24. minR = r;
  25. minG = g;
  26. minB = b;
  27. //store this color
  28. closest = c;
  29. this.ExistingColor = dc;
  30. }
  31. }
  32. //return
  33. return closest;
  34. }

Some notes:

  • The "DefinedColor" object in Line #10 is simply a wrapper object around what we have stored in the database for each source Defined Color: basically the "int" value (byte representation of the aRGB and a friendly name).
  • Line #29 stores the closest Defined Color in a global variable for use in data binding (which is outside the scope of this discussion).
  • You'll see a call to a utility method in Line #13. This converts the integer representation of a color ("raw" aRGB) into a .NET color. Here's that method, along with its corollary (which isn't used here, but I wanted to include it for your reference).

Code Listing 2

  1. public static Color GetColorFromDefinedColorRGB(int definedColor)
  2. {
  3. //convert color
  4. return Color.FromArgb(255, (byte)(definedColor >> 16 & 0xFF), (byte)(definedColor >> 8 & 0xFF), (byte)(definedColor & 0xFF));
  5. }
  6. public static int GetIntFromColor(Color color)
  7. {
  8. //convert color
  9. return color.A << 24 | color.R << 16 | color.G << 8 | color.B;
  10. }

In Line #4, you'll see that I "hard coded" 255 for the alpha channel. This simplification is due to fact that the application doesn't support transparent colors (although it easily could).

That's about it for my color comparison algorithm. Although certainly not an everyday thing, it's interesting to understand how to extract the constituent parts of colors in general. This has come up more times than I thought it would, especially using technologies like Silverlight.

Have fun coloring!

3 Tags

No Files

No Thoughts

Your Thoughts?

You need to login with Twitter to share a Thought on this post.


Loading...