The selective color effect, implemented with ChunkyPNG
So, I won Codebrawl #10. I participated the previous time that ChunkyPNG was featured and I really enjoyed using it. ChunkyPNG is a pure Ruby library for handling PNG files. One of the nice features it has is that it gives you direct read-write access to the pixels, so you can just load an image, do a map or fold over the array of pixels and then save it right back to a new PNG. ChunkyPNG is well documented and gives you several easy methods to work with pixels and colors, so be sure to take a look.
When I started to work on this Codebrawl, I thought about two ways to do this: Try to detect each crayon as an object and keep one of them in color, or take a reference color and just keep the colors that are similar to it. Object detection would be great, of course. Just changing colors based on reference does not work in cases were you want to, for example, keep a flag in color. Okay, it does work when you use it on a Japanese flag... Just using a color reference and a distance does work great for the example image that the Codebrawl uses, though, and implementing object detection is a much harder problem than mapping over colors.
I think I know how to iterate over an array, so all I was missing was a distance function for colors. But how do you actually compare colors?
How to measure the distance between colors
There are several ways to get a value that tells you how much alike two colors are. If you have an RGB pixel, you could just take the red, green and blue values as coordinates in a three dimensional space and calculate the distance there (and I guess you know how to do that).
I did not actually implement this, as it does not represent similar colors in the way we would see them. Think about it, the color (255, 0, 0) and (127, 0, 0) are both just shades of red, but they would have the same distance as (255, 0, 0) and (255, 128, 0), which introduces green to the mix and looks pretty different overall.
This also tells us something about what kind of representation we want: One where only the color counts, but not the brightness (or luminance). Skipping through Wikipedia, I first noticed rg chromacity space.
rg chromacity
rg chromacity is a simple way to remove intensity information from your colors and only keep the proportions of red, green and blue. You normalize the values to be between 0 and 1, with r + g + b always adding up to one. It is called rg chromacity because only the red and green components are needed to describe a color, as the blue component is always b = 1 - (r + g). For example, rgb(255,0,0) is rg(1,0), as is rgb(127,0,0).
You now have a 2d space, so distances can be easily calculated. Using this to decide which colors to keep gives somewhat satisfactory results, at least for some of the crayons. But in the end, it just was not as good as I had hoped. Part of this surely is the way this color space actually looks. It is somewhat uneven, as the distance between pure red, rg(1,0), and pure blue, rg(0,0), is one. But between red and green, rg(0,1), it is the square root of two!
By just measuring the distance, I am essentially cutting a circle of colors I want to keep out of this triangle, but colors in this space are not uniformly distributed. I had a lot of ideas how to counter these problems: Make colors spread from a reference color if the neighbors are similar, make negative cuts in this space by specifying colors that should always be made gray, etc... What I really needed was a better distance function for my colors. So let's use a grown-ups color system, HSV.
HSV
If you go looking for color spaces, you will encounter HSL and HSV pretty soon. They use hue, saturation and lightness (or value, respectively) to define a color. If you take a look at some pictures of this color space, you will see that the hue component looks pretty much like what we need.
Now, calculating the hue is more complicated than calculating rg chromacity colors. If I understood it correctly, you make a hexagon of colors, put red at 0°, green at 120° and blue at 240° and then calculate where your color lies. You can see the formula I used in the code.
Calculating the distance is just subtracting one hue from the other. We have to do it two times, though, as the hue is circular and has red on both ends, so the shorter distance counts. This gives good results for most colors. I could not get the yellow and red crayon to seperate perfectly... This may be because I did not find a good reference color, or just that the dark yellow in the tip of the crayon and the light red are actually too similar and this approach won't work at all. You should take a look at the other entries and see how well they did.
Better color distance
I tackled the problem of color similarity from a rather primitive point of view: Numerical values of single pixels. As it turns out, this is not enough to mirror human color perception. Take a look at this: http://gizmodo.com/5839481/the-most-wicked-optical-illusion-ive-seen-so-far. Both spirals have the same color, but you would never think that if you didn't know or check. As far as I know, no algorithm that works for cases like this exists, yet.
There is a standard for measuring color difference by the International Commission on Illumination (sounds good, right?). It takes into account how humans perceive color, so it should give you the best results (if you are human, that is). I did not try it, though, as it seems somewhat complicated and I wanted to keep this entry short and to the point. Peplin did it like this and his code is much more complicated, but still quite readable. One problem with this approach is that you have a lot of magic numbers that you get from the standard definition. These are (at least for me) hard to visualize and I find it hard to grasp their meaning.
Anyway, here are my pictures and my Ruby code.
BONUS: Coffeescript version
I also wrote a Coffescript version of the same algorithm which you can use to quickly check the effects of changing the reference color or the color distance. Porting it over from Ruby was pretty straight-forward, except for the strange interface for pixels that the HTML5 canvas element uses and the fact that modulus is broken in Javascript (WTF?!). I tried to take a functional approach, but I am not a Coffee/Javascript programmer, so this code is rather bad. If you are interested anyway, you can see the code at GitHub.
You can find this version ready to use at http://severe-autumn-9391.heroku.com/index.html. Use the slider to set the color distance that will still be colored, and just click on any point in the image on the right to set it as the reference color. Have fun!