Monday, December 12, 2016

Next Best Color?

Have you ever wanted to recolor an image with a limited number of colors, replacing each color with the next best color?  Probably not, but I needed it for another project I'm working on, and it end up being a fun exercise.  The basic idea behind this program was to loop through each pixel of an image, and compare it to several colors in a list, and replacing the original color with the color from the list that is closest.

If you read my post "Is it There?" you'll recall I brought up the concept of the distance between two colors.  In the "Is it There" project I used the Euclidean distance, which isn't really that good.  The Euclidean distance just looks at the distance between two points, in this case two points in a three dimensional grid.  Though you can represent colors in an RGB format with a number from 0 to 255 representing how much Red, Green, and Blue are in the color, and you can represent that as a 3 dimensional point, finding the Euclidean distance between two of these points doesn't really work...because color doesn't work like that.

This is where the Delta E (ΔE) comes in.  This is a metric defined by the International Commission on Illumination (a lot of bright people work here), to measure the difference between two colors.  The equation changes between the years and you can find more information about it here.

To illustrate the difference between the Delta E and Euclidean methods I picked a sprite from one of my favorite video games (Terra from Final Fantasy VI).  Here I chose a limited selection of colors and used both the Delta E method, and the Euclidean method to find the the next closet colors.
As you can see, Delta E leads to a much more vibrant image.  The Euclidean distance works, and we are left with a very similar image, but the Delta E gives us brighter greens, closer purples, and just an overall better image.

Now for some fun...

You may recognize this spider to the right as Ochos Locos from my previous post on spiders.  I ran my program, but instead of giving it a set of colors, I had it generate a list of between 15 to 40 randoms colors (and then look at each pixel in the image and replace it with the next closest color.  As it turns out this is a pretty long process, and at sometime in the future I might optimize it.

But! After hours and hours of waiting I bring the work of art that is "Ocho Ochos Locos"

Ocho Ochos Locos
Ocho Ochos Locos

If you're interested in taking a look at the code you can find it here!