Octree Color Quantization

Hamburg (Germany), the 29th April 1997.
Revised 21. April 1998
Written by Nils Pipenbrinck aka Submissive/Cubic & $eeN

Abstract

This article explains a fast way to get a good approximation of the most important 256 colors of a RGB-Picture. It may be useful for graphics- and game programmers. The article will also cover a introduction on the OCTREE data-structure which isn't only usefull for color-quantization but could also be used for raytracing, 3d engines and lots of other things.

Another programmer, Till Toenshoff told me, that I should add a note to this tutorial. "Jakson und Tanimoto, 1980" where the first, who used this data-structure for quantization purposes. Till suggested to take a look into the book Graphic Gems (Andrew Glassner, Academic Press). I can absolutely agree. If you have fun reading my tutorials you should definately try the Graphic Gems! They're great.

What are Octrees?

Octrees are a very efficient data structure to store 3 dimensional data of any form. Their big advantage is, that you can search and insert in such an octree very fast. However, deleting and moving entries is a slow proccess. If you're familiar with binary trees you'll have no problem to understand the basic concept of the octrees. They're just like binary trees but have 8 subnodes instead of two. However, a short refesh of trees can't hurt, so you might read this chapter to refresh your knowlage. If all this is new to you you should read the entire article, even if you don't understand it. After you saw an example how to use them you'll surely understand them.

A Octree is a tree-structure which contains data. The data is stored in a hirarchical way so that you can search an element very fast. Every tree has at least a root-node which is the anchor of all subnodes. Every Node has pointers to 8 subnodes. A C(++) structure of such a node will look like this:

struct octreenode
{
  void *data;
  struct octreenode childs[8];
};

where data point to any data and the childs point to other octree nodes or point to NULL and indicate that there aren't any childnodes (such nodes are called leafes).

Insertion of Data

Data is stored in a binary way. In our example we want to store RGB-tripples (colors). Now lets insert a color into the tree.We start at the root-node of the tree and examine our RGB-Trippes. From each element we take the most significant bit combine them into a index-byte like this: 00000RGB where R,G, and B are the bits we have extracted. The higest value this byte could have is 7 (binary 00000111) and the lowest is zero (binary 00000000). This byte is an index of the child-nodes we have. Now we look at the child node pointed by our binary index. If it's NULL we create a new node and let the child-node point to it. We also initialize all fields to zero. Then we traverse down the tree and take a closer look to node childs[index]. We've done the first step. Now we examine the next bits of our tripple and continue the traversal until we've used all 8 bits of our input-data.

Using the Tree for Color Quantization

We want to quantizate colors. To do this we extend our Node-structure by a reference counter and three color markers. We don't need the data pointer anymore because we've stored all the informations we need directly into the octree node structure. The structure will now look like this:

struct octreenode
{
  unsigned long references;
  unsigned long red;
  unsigned long green;
  unsigned long blue;
  struct octreenode childs[8];
};

Now we insert all colors into the tree each time we found the leaf of the tree we increment the reference count and add the color value to the red, green and blue counters. This will help us to find the colors that are most important. After we inserted all our colors we begin to reduce them. We count all the nodes that have a reference greater than zero (only leafes can have a reference). Now we go into this code-fragment:

WHILE (number of leafes>256)
  search the node, where the sum of the childs references is minimal and reduce it.
ENDWHILE

Node Reduction

How to reduce a node? Actually that's pretty simple. We sum the color components and referece-counts together. This gathers the color-statistics of all subnodes. The code will show how it's done:

for (int n = 0; n<8; n++)
{
  if (currentnode->child[n]) {
    currentnode->reference += currentnode->child[n].reference;
    currentnode->red       += currentnode->child[n].red;
    currentnode->green     += currentnode->child[n].green;
    currentnode->blue      += currentnode->child[n].blue;
    // free the node. We don't need it anymore
    delete (currentnode->child[n])
    currentnode->child[n]=NULL;
  }
}

Building the Palette

Rebuilding the palette is easy too. We traverse the tree and if we find a leave we calculate the RGB-components of the node and store them in a palette. Calculation is very easy: It works like this:

palette[index].red   = currentnode->red / currentnode->reference;
palette[index].green = currentnode->green / currentnode->reference;
palette[index].blue  = currentnode->blue / currentnode->reference;

Now we have a good palette we could use to dither the picture. The quality of the palette isn't that bad at all, other algorithms like median cut generate better palettes, but the algorithm is very fast.

Final Optimizations

There are some final things that can be used to gain more speed. Most of the time is spent finding the node which has to be reduced. It doesn't hurt to maintain a list of all nodes that are on the same level (level means how deep the node is stored in the tree). A simple linked list could be very usefull for this. The best node to reduce is always stored at the highest level in the tree. It also doesn't hurt to reduce random nodes and don't analyse the contents of the node as long as you reduce in the highest level. The palette won't be as good, but it'll be a lot faster (and the difference is hardly noticable)
Also after you've created the palette the tree is still usefull. You can use them to fast map a RGB-tripple to a palette index. To do this you have to store the palette indice into the nodes during the palette calculation. When you want to find a color you simply traverse the tree down until you find a node which reference-count is greater than zero. The palette indice can be directly read out of the node. To my knowlege this is the fastest way to map RGB colors to adaptive palettes. Normally you don't need to use all 8 bits of the color-components. Using only 6 bits will give more performance and because standard VGA-adapters can only use 6 bits per primary color noone would be able to spot the difference at all. It also saves a lot of memory
If memory-usage is an issue you might reduce the nodes after you inserted a complete scanline. I wouldn't reduce to 256 colors in this case but to 4000 or so.. This will help you to keep the tree small

Some Comments and Reactions

I just received a email from a guy called Peter Martin. He wrote about a simple yet genious idea how to speed up the quantization process. His idea was to keep the tree small. He reduced the nodes which have a reference count of 1 (thus represent only one pixel of the source-image). This of cause keeps the tree small and saves lots needless tree-traversal. Martin told me, that he improved the speed of his implementation by factor 100. That's what I call a cool optimization!

I also received a mail from marcos who implemented the algorithm using c++ templates only. Click here to visit his site.

Final Words

I've written this article because I find the algorithm very elegant and usefull. It's a good example of the high art of computer programming and maybe it makes you interested in other algorithms. I haven't invented the algorithm nor I know who owns the copyright of it (if anyone does, please contact me). However, even if I dont't have any rights on the algorithm I spend some hours writing this article. Don't copy it and put it into your website. A reference is much better because I'll be able to update it from time to time.

Some month ago I found a nice color quantization algorithm on the net. This algorithm (while having some drawbacks) has the best quantization results I've ever seen im my live. Best thing.. It comes with a ready-to-use sourcecode. Check it out: NeuQuant: Fast High-Quality Image Quantization

Glossary

© by submissive