Quantizing Colors in an image using an Octree and a Binary Heap

Introduction

Quantizing the colors in an image is the process of reducing the number of distinct colors in an image, leaving the picture as visually similar as possible to the original image.  Some examples of why you might want to do this are to reduce the color depth of an image (the number of bits required to store each pixel) or to change the image’s format to one that has a much smaller number of supported colors (such as to GIF which stores each pixel as a 1-byte lookup-number into a table of 256 colors).

High-Level Overview

This is very simplified, but it gives a good general overview of how it works.

  1. Take all the pixels in the image and place them in buckets so that each bucket only holds pixels of the exact same color.  If the image has 20,000 distinct colors, you’ll start off with 20,000 buckets.  Since all the pixels of the image are now in the buckets and there are probably groups of pixels that have the same color, there will probably be buckets that have multiple pixels in them.
  2. Assign each bucket a numeric “weight” based on the number of pixels it has in it and the number of buckets with visually similar colors in them.  This “magic” weight may seem very mysterious now, it’s details will become clearer later when we get into the details of the algorithm I implemented.  For now, understand that this weight is based on how significant this color seems to be to the image right now.  We’ll be adjusting these weights as we combine buckets in just a moment.
  3. Order the buckets based on their “weight” with the lowest weight bucket on the left and the highest on the right.
  4. If the number of buckets is more than the number of colors you’re trying to reduce the image to:
    1. Find the bucket with the lowest numeric weight (the bucket on the left) and call it Bucket A.
    2. Find the bucket with the most visual similar colors in it and call it Bucket B.
    3. Dump the pixels from Bucket A into Bucket B and throw the now empty Bucket A away.
    4. Recalculate Bucket B’s numeric weight and reorder the buckets so Bucket B is in the correct position based on its weight.
    5. Repeat step 4 until the number of buckets equals the number of colors you’re trying to reduce the image to.
  5. When the number of buckets is reduced to the desired number of colors, take each bucket and:
    1. Create a new color that is the average of all the colors in the bucket.
    2. Ask each pixel in the bucket where it originally came from in the image and replace that pixel in the image with the new color you just created.
  6. Marvel in the glory of your new image that has had its number of distinct colors reduced yet still looks as visually similar to the original as possible!

Visually Similar Colors

The algorithm relies heavily on being able to find the pixels with the most visually similar color to a given pixel.  Most humans are pretty good at looking at two colors and making a decision on whether they are very similar colors.  For example, we know just by looking that red and pink are much more similar to each other than, say, red and green.  The human eye is generally capable of distinguishing between about 10 million colors. Computer images typically store the color of a pixel using three 8-bit (1 byte) values, one each for the Red, Green and Blue primary colors that combine to make the color of the pixel.  Each byte represents the intensity of its primary color with 0 meaning none of that color and 255 meaning the maximum intensity of that color.  If you wanted to find the pixel with the most visually similar color to a given pixel in a group of pixels, you would look for the pixel that had the lowest average difference between its red, green and blue values and those of the given pixel.

For a given pixel, if we write out its Red, Green and Blue components as 8-bit binary numbers over top of each other and then take each column of numbers (left most bit from each component, then 2nd left most bit of each, etc.) and treat them as 3-digit binary numbers (with the top bit being the most significant and the bottom bit being the least significant) and write them under each column in decimal we end up with a single number that represents all three of the primary color components of the pixel.

Red:   0 1 1 0 0 1 0 0 (binary)
Green: 1 1 0 1 0 0 1 1 (binary)
Blue:  1 0 0 1 0 1 1 0 (binary)
       - - - - - - - -
       3 6 4 3 0 5 3 2 (decimal)

The more digits from the left that two pixels have identical, the more visually similar the two pixels are.

Octrees

Since we know each digit of our number can only be from 0 to 7 (000 – 111 in binary), an Octree data structure lends itself perfectly to our cause.  An Octree is a hierarchical structure with a single root node at the top.  Each node can have 8 child nodes (numbered 0 – 7) with each of those child nodes having 8 children themselves and so on.

Starting with the left-most digit of our number we create that child of the root node (if our first number is 3 then we create a node for child #3 of the root node), then we take the next digit and create that child of the node we just created, etc.  When we finish we have a node 8 levels deep. Starting with the root node, if we take the child index of each node deeper down the structure we’ll have the number for our pixel.  In the 8th level node (“bucket”) we store our pixel.  We repeat this process for every pixel in the image, creating new child nodes where needed and just navigating down into child nodes when they already exist.  If we insert a 2nd pixel with the exact same color in our Octree we’ll end up just navigating down into the same 8th level deep node we made previously and depositing our pixel into that same bucket.

When we finish depositing all the pixels of our image into our Octree, they’ll all have filtered down to the 8th level nodes at the bottom of our structure like chips dropped in a Plinko board, only with a very specific path each pixel will take based on its specific color.  If we take a node with pixels in it and navigate up to its parent node and then down into a different child node (a sibling of our starting node), we’ll find pixels that are very similar in color.  If we, however, navigate further up the structure before navigating back down a different child branch, we’ll find pixels of more noticeably different color.

Reducing the number of colors

So now we have all these pixels sitting in buckets at the bottom of our Octree.  There are thousand (10’s or 100’s of thousands, maybe even more!) of buckets with pixels in them.  Each bucket currently represents a unique color in our original image.  We want to reduce the number of bucket with pixels in them, probably drastically; Let’s say we want to get down to only 255 buckets because we want to rewrite out our image in the GIF format which only supports 255 colors (not the 50,000 our image may currently have).  How do we do this?

Well, we’ll have to combine the pixels in enough buckets to get the number of buckets with pixels in them down to our target number (255).  We’ll have to choose buckets with visually similar colors that have the least visual impact on the image to combine so as to have the smallest noticeable effect on the image when we average their colors together.

We’ll discuss how to find the bucket containing pixels with the least visual impact on the image in a bit, but for now let’s assume we can find that bucket.  What do we do with it?  Well, chances are that if this bucket has low visual impact on the image, so do its siblings which would be VERY visually similar to it.  That means they’re probably going to be “reduced” as well.  So let’s take this bucket we’ve found and dump it into its parent bucket with the assumption that its siblings will probably also be deemed “reducible” and dumped into the parent bucket as well.  If all the parent bucket’s children eventually get dumped into it, it will become a 7th level node that has pixels and no children and may eventually be deemed “reducible” itself and dumped into its parent.

If we repeat this process enough times (find the bucket with least visual impact on the image and dump it into its parent), we’ll eventually get down to only 255 buckets (or however many we want to get down to) with pixels in them.  We can then take all the pixels in each bucket and average their colors together to make a new color for all the pixels in that bucket.  We then ask each pixel of each bucket where it originally was in the image and update that pixel in the image with the pixel’s new color and …  We’re done!

Find the pixels with the smallest visual impact

But wait, that’s all well and fine, but how do we find the bucket that contains pixels with the least visual impact on the image?  Remember that “mysterious” numeric weight we talked about before?  This is where we have to dive into its mysteries.  This weight must be directly related to the visual impact of the pixels in the bucket. A higher weight means the pixels in the bucket have a higher visual impact on the image, where as a lower weight means the pixels have a lower impact.  If we sort the buckets in order of their weight from lowest on the left to highest on the right, then the left most bucket will always be the bucket with the least visual impact on the image.

So what’s in this weight?  Let’s look at our Octree right after we’ve loaded all our pixels into it.  All the pixels are down on the 8th (bottom) level. The most obvious factor of how significant an impact a bucket’s pixels have on the image at this point is how many pixels are in the bucket.  If an image has 1000 pixels of one color and only 15 of another, those 1000 pixels have a more significant visual impact on the image than the 15 pixels.  So number of pixels in a bucket comes in to play when considering a bucket’s weight.

What about after we’ve merged some buckets into their parent (up to higher levels)?  Changes in colors between sibling buckets at lower levels (e.g. level 8) have exponentially less impact (\frac{1}{2^{(d-1)}} where d is the level depth (1-8) to be precise) than changes in colors between sibling buckets at higher levels (e.g. level 3), so the depth (1-8) should effect the weight. Let’s divide the number of pixels in the bucket by 2^{(d-1)} so 1000 pixels at depth 8 would have a weight of 1000 / 128 = 7 (we use integer math for performance reasons) but 1000 pixels at depth 3 would have a weight of 1000 / 4 = 250.

A bucket of pixels that has fewer of its 8 children buckets with pixels in them than another bucket means that its children are less visually varied than the other bucket’s children and it should weigh less than that other bucket.  This introduces the concept of a bucket’s weight depending on what bucket it’s being compared to.  We’ll have to calculate a bucket’s weight at the point it’s being compared to another bucket.  At this point, we don’t care so much about a precise weight as we do about whether a bucket weighs less than, more than or equal to another bucket (i.e. has less, more or the same visual impact on the image).  If the two buckets have the same number of their 8 children buckets with pixels in them then we’ll use the first method we discussed to determine if they are less than, more than or equal to each other.

We have a situation we have to make sure is handled carefully.  Let’s say we have a level-8 bucket with 2 pixels in it that is the lowest weight bucket.  We dump that bucket’s 2 pixels into its level-7 parent.  Eventually that level-7 bucket becomes the lowest weight bucket so we dump its 2 pixels into its level-6 parent.  This continues until we end up with the 2 pixels in one of the 8 top-most level 1 buckets.  If becomes the lowest weight bucket again, we need to start looking at the 2nd lowest weight bucket to merge into its parent bucket from now on.  Simply put, whenever we look for the lowest weight bucket, we need to look for the lowest weight bucket on level 2 or higher of our Octree ignoring any buckets with pixels in them on level 1.  If we are reducing the colors to 8 or less, there is a slight chance we could merge all our colors into the 8 level-1 buckets and not be able to merge any more.  We could probably modify our algorithm to accommodate merging between sibling buckets at that point, but for this algorithm we’ll just say “Oops, sorry, can’t reduce this image any lower.”  (I realized that we CAN merge buckets at level 1 up one, into the Octree’s “root” node which never gets considered when grabbing the lowest weight bucket.)

Advertisements
Posted in Uncategorized | Leave a comment

Mid-life crisis and electronics!

My normal way of tackling hobbies is to dive head first into something (electronics, game programming, wood working, paper craft, robotics, leather working, …) and pour my heart and soul into it… for about 2 weeks.  Then my enthusiasm wanes and something else catches my mind’s eye and I go “Ooh shiny!” and I’m off pouring my heart and soul into something else.

The life-long result of this is that I’ve passionately dived into learning a LOT (and I mean a lot!) of fun things, all of which I’ve spent a life time saying I’d eventually finish or at least make a name for myself in.  The reality of it is that I’ll be 48 this year and I’ve made a name for myself in none of them.  I have literally hundreds (maybe thousands) of games I’ve started and never finished.  I’ve gotten into game programming more times than I can remember and never finished writing a game.  I’ve gotten into robotics many times and never finished a robot.

Well, I’m tired of it.  I think I must be going through a “mid-life crisis”.  In the past week or so the fact that I’ve spent my entire life diving passionately into one thing after another and never sticking with any of them has started to seriously bother me.  So I’ve decided to do something about it.  I need to pick something and stick with it and just accept that most of the other hundreds of interests I have will have to be ignored.

I’ve given a lot of thought as to what I want to focus on and I’m leaning heavily toward electronics.  This allows for several of my interests to come into play, such as robotics, microprocessors, programming… I also need to make sure I have projects to work on.  Too many times I’ve dived head first into learning something just for the fun of learning it; but Mushroom.Lampwith nothing to apply what I’m learning to it doesn’t stick when the next two-week passion-wave comes along (“Ooh shiny!”).

So I’ve picked a project to start with.  I’m going to make some cool battery powered LED mushroom lamps.  I got the idea from this video on YouTube.  It should give me some starting experience with soldering and it really looks like a fun and fairly easy project.  I’ve already ordered the LEDs and resistors I’ll need and I’m pretty sure I have the rest of what I need.  I just need to establish a work area that can stay dedicated to my electronics adventures.  Wish me luck!

Posted in Uncategorized | Leave a comment

Back of the brain…

This is going to be a living post.  In it I’ll keep a continually changing and morphing list of things I’ve ran across that I want to dig into further and research, learn, play with, etc. Continue reading

Posted in Back of the Brain | Tagged , | Leave a comment

Sorting C# Enum.GetValue(…)

This one caused me a bit of frustration.  Enum.GetValue(…) returns a non-generic Array.  I tried all manner of ways to sort it (short of writing my own quicksort).  If I typed Enum.GetValue(…).OrderBy, there is no OrderBy. Continue reading

Posted in Programming, Technology | Tagged , , , , | 3 Comments

The 32-bit version of Visual Studio Remote Debugging Monitor (MSVSMON.EXE) cannot be used to debug 64-bit processes …

I’ve gotten used to manually starting IISExpress instead of using [F5] in Visual Studio 2010 to start a debugging session. Whenever I need to do server-side debugging, I manually attach Visual Studio’s debugger to the IISExpress.exe process Continue reading

Posted in Programming | 3 Comments

Feeding Time at the O.K. Corral

They all ate together for the first time tonight with no hissing, no growling, no chasing a kitten away so their food can be Continue reading

Posted in Life | Leave a comment

Lazy and Productive day…

If you ask the cats, it was a lazy day today.  Salem has finally accepted the two new annoyances… er, I mean kittens.  Smokey (in the middle) and Storm (on the right) are still shying away from human touch, but they’re starting to warm up to it. Continue reading

Posted in Life | 3 Comments