Color Quantization using Octrees

Mapping 24-bit images to 8-bit palettes

Dean Clark

Dean, a programmer/analyst who develops graphics and imaging applications, can be contacted at 71160.2426@compuserve.com.

---

Much of what goes on inside a computer is a discrete approximation of continuous real-life events. This works because, most of the time, approximations are close enough. Computer graphics, in particular, are full of approximations. We approximate curved lines by stringing together many very short straight lines. We approximate curved surfaces using bunches of tiny flat surfaces. And we approximate a continuous rainbow of colors using many individual discrete colors.

There are a number of ways to approximate continuous colors. One is to throw in buckets of bits, resulting in "true color" (or 24-bit), where three bytes (one each for red, green, and blue primary colors) are dedicated to each color pixel on the screen; see Figure 1. While simple in concept this approach is expensive, both in terms of computing power and money. It takes a lot of CPU horsepower to move 24 bits of data around for every pixel on the screen, and hardware that's able to do so tends to be expensive.

A more common approximation is "palette-table" (or lookup table) color. This is less expensive because it requires only a single byte per screen pixel. The screen pixel value indexes a table of red/blue/green (RGB) values, and the color value at that table position is displayed on the screen; see Figure 2. But the table index is only eight bits, so only 256 colors can be displayed on the screen at any time. Clearly, the challenge is to select the right 256 colors for the image at hand.

There are three common techniques for mapping an image with 24-bit color depth to an 8-bit palette-table workstation. Past issues of DDJ have covered two of these; see "Median-Cut Color Quantization," by Anton Kruger (September 1994), and my article "The Popularity Algorithm" (July 1995). Both techniques were first developed by Paul Heckbert in the early 1980s. In this article, I'll present "octree quantization," the third and most-recent color quantization technique.

Spatial Data Structures

As its name implies, an octree is an 8-way tree; that is, each node has up to eight children. The octree (and its cousin, the quadtree) is a hierarchical data structure that uses the principle of recursive decomposition to represent spatial data.

The RGB color space is a cube, each axis of which is one primary color. If you take the RGB color cube and divide it along each axis, you get eight subcubes; see Figure 3. Divide each subcube on each axis and each of them becomes eight subcubes. Do this eight times, and you've got 2²⁴ subcubes, one for each possible color in a true-color image.

This subdivision can be represented by a tree structure; see Figure 4. The root of the tree represents the entire space. The first level represents the first subdivision. Each region in the subdivision corresponds to a child pointer. The color space can be subdivided until each individual region represents a single color.

The number of levels in a color octree corresponds to the number of bits in the color primaries, so eight bits in each red, green, and blue component equal an octree with eight levels. VGA provides six bits per primary, so an octree with six levels is sufficient for VGA. The 3-bit pattern at each bit position of each byte of a 3-byte RGB determines the decomposition of the color space; see Figure 5.

Suppose you want to insert the RGB color from Figure 5 into the color octree. The most-significant bit is the root (bit 7 in each color byte, level 0 in the octree). The bit pattern is 101==5, so to begin inserting this color, follow the path through tree-->child[5]. At the next level, the bit pattern is 011==3, so continue down the tree through tree-->child[3]. The bit pattern from the least-significant bit pinpoints the color exactly. The first step for a naive octree color-quantization algorithm would be to scan the image and store each unique color in the octree by traversing the tree as previously discussed.

Refining the Process

At the end of the first image scan, the color octree could have as many as rowsxcolumns individual colors in it. Each unique color would be represented by a leaf node in the tree. To get the number of colors down to 256 (or whatever the goal is), the tree must be reduced by somehow merging colors. Colors that are very close together (that is, leaf nodes that share a parent) would be combined into a single average color. The close colors would be deleted, and the new average color inserted into the tree. This would repeat until the tree contained the desired number of colors.

The naive color octree can be improved in several ways. First, instead of building an entire octree containing all image colors, the tree can be reduced immediately whenever the number of leaves exceeds the target number. Thus, there are never more than the target number of leaf nodes in the tree, saving considerable memory.

Reducing the tree by traversing to the leaf level is time consuming. As a further improvement, maintain an array of linked lists of reducible tree nodes; see Figure 6. The tree can grow no deeper than the number of bits in our color primaries, so an array of this size will do.

A Level-Linked Octree

A node is reducible if it isn't a leaf. As new nodes are created at each level except the leaf level, they're added to the reducible list for that level.

To reduce the tree, all the children of a reducible node are averaged together into the node. The child subtrees are discarded, and the reducible node becomes a leaf node. The result is that all those colors are now represented by the single larger node. Further, since the node is now a leaf, any new colors whose path through the tree takes them through this node now stop here--after reduction, the tree never grows downward again.

You can now outline the octree quantization algorithm:

1. 1. Scan the image, and insert colors into an octree structure.

1. 2. If the number of leaf nodes in the octree exceeds the number of final colors, reduce the tree.

1. 3. When the image scan is finished, the leaf nodes of the octree contain the reduced image colors. Rescan the image to map image colors to their appropriate octree leaves.

Implementing Octree Quantization

Listings One and Two present an implementation of the refined color-octree algorithm just described. InsertTree takes an RGB color and inserts it into the octree at the leaf level, which is initially level 6 for VGA. Each leaf node maintains a count of the number of image pixels containing that color and a sum of the RGB instances. InsertTree recurses down the tree, creating new nodes as necessary. As nodes are created in CreateOctNode, they're added to the reducible linked list for their level.

ReduceTree does the reduction. The reduction level is always one higher than the leaf level. ReduceTree takes the first node from the list and sums the component RGB values and pixel counts for all its children.

Once the tree is built, MakePaletteTable traverses the tree and builds an array of leaf RGB values for the output color palette. The palette index value is also stored in the color-octree leaf node. QuantizeColor uses this value to map an image RGB value to a palette-table entry. This function takes an image RGB value and traverses the octree in the same manner as InsertTree. When a leaf node is reached, the palette index in the leaf node is the appropriate quantization value.

CONVERT.C (available electronically, see "Availability," page 3) reads an RGB image file, maps its colors down to 256 palette-table cells, and either displays the quantized image or writes a PCX file of it. The input file format is the same as that in my July 1995 article--essentially an ASCII file of RGB values between 0 and 1, plus a short header. The screen output uses the MetaWindow graphics library from Metagraphics (Scotts Valley, CA), but it is easily adapted to most any graphics kernel.

Results and Additional Heuristics

This algorithm is quite efficient in both time and space. Since the color octree never has more than N+1 leaf nodes, plus internal nodes (at most, N more) it compares favorably to other methods, which typically require space proportional to the number of unique colors in the original image. Inserting colors into the tree and mapping original colors into the palette table are all bounded by the tree depth (eight or less) times the number of image pixels, while building the palette table is proportional to the tree depth times the number of final quantization colors. In practice, the running time of the program is dominated by disk accesses, managing about 4300 pixels per second on a 486/33 PC.

The tree is always reduced by merging the colors at the leaf level into their parent nodes. Any node at the reducible level could be chosen, but the final output can be affected by the selection criteria, which include: picking a node arbitrarily; picking the node representing the most image pixels; picking the node representing the least image pixels; and some hybrid, such as alternating most/least or favoring center pixels over edge pixels.

What's the difference? Picking colors that represent many pixels and averaging them results in larger groups of pixels that share the same (slightly wrong) color. The tendency then is to have more individual colors available for less-conspicuous regions of the image. Picking the fewest pixels tends to preserve subtle gradations in large, nearly constant shaded areas, reducing overall error, but at the expense of small image detail. An alternative technique would attempt to balance these two effects. A heuristic that favors central pixels might be useful in an animation scenario, where the user tends to focus on the middle of the image.

Listing One selects reducible nodes "randomly"--it simply takes the first node in the reducible list, which is the most recently added one. Implementing any of the aforementioned heuristics requires that more information be stored at each node. For the pixel-count heuristics, you have to know how many pixels are represented in the subtree rooted at each reducible node. This could be calculated as an extra step as the leaf level changes, or the counts could be accumulated as colors are inserted into the tree. The list could then be sorted before reductions are done on the level, or for each reduction the list could be scanned for the largest/smallest number of pixels.

Finally, note that the octree algorithm can't guarantee exactly N colors in the final palette table. This is because a reduction trims an entire subtree, which may be up to eight leaf nodes, while adding only one additional leaf. This might be important in a situation where an image is mapped to a very small number of colors, say 64 or less.

References

Clark, Dean. "The Popularity Algorithm." DDJ (July 1995).

Gervautz, M. and W. Purgathofer. "A Simple Method for Color Quantization: Octree Quantization" in New Trends in Computer Graphics. New York, NY: Springer-Verlag, 1988.

Heckbert, Paul. "Color Image Quantization for Frame Buffer Display." Computer Graphics (July 1982).

Kruger, Anton. "Median-Cut Color Quantization." DDJ (September 1994).

Samet, Hanan. Applications of Spatial Data Structures. Reading, MA: Addison-Wesley, 1990.

Figure 1: 24-bit color display.

Figure 2: Palette-table color scheme.

Figure 3: Recursive subdivision of a 2-D space.

Figure 4: Hierarchical space subdivision--a quadtree.

Figure 5: Determining the color space at each tree level.

Figure 6: A level-linked octree.

Listing One

// oct1.h -- Header file for octree color quantization function
// Dean Clark
//
#ifndef OCT1_H
#define OCT1_H
typedef unsigned char   byte;
typedef unsigned int    uint;
typedef unsigned long   ulong;
typedef int             bool;
#ifndef True
#define False   0
#define True    1
#endif
// RGBType is a simple 8-bit color triple
typedef struct {
    byte    r,g,b;                      // The color
} RGBType;
// OctnodeType is a generic octree node
typedef struct _octnode {
    int     level;                      // Level for this node
    bool    isleaf;                     // TRUE if this is a leaf node
    byte    index;                      // Color table index
    ulong   npixels;                    // Total pixels that have this color
    ulong   redsum, greensum, bluesum;  // Sum of the color components
    RGBType *color;                     // Color at this (leaf) node
    struct _octnode *child[8];          // Tree pointers
    struct _octnode *nextnode;          // Reducible list pointer
} OctreeType;
OctreeType *CreateOctNode(int level);
void MakePaletteTable(OctreeType *tree, RGBType table[], int *index);
ulong TotalLeafNodes(void);
void ReduceTree(void);
void InsertTree(OctreeType **tree, RGBType *color, uint depth);
int QuantizeColor(OctreeType *tree, RGBType *color);
#endif

Listing Two

// oct1.c -- Color octree routines.
// Dean Clark
//
#include    <stdio.h>
#include    <stdlib.h>
#include    "oct1.h"
#define     COLORBITS   8
#define     TREEDEPTH   6
byte MASK[COLORBITS] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
#define BIT(b,n)   (((b)&MASK[n])>>n)
#define LEVEL(c,d)((BIT((c)->r,(d)))<<2 | BIT((c)->g,(d))<<1 | BIT((c)->b,(d)))
OctreeType  *reducelist[TREEDEPTH];             // List of reducible nodes
static byte glbLeafLevel = TREEDEPTH;
static uint glbTotalLeaves = 0;
static void *getMem(size_t size);
static void MakeReducible(int level, OctreeType *node);
static OctreeType *GetReducible(void);
// InsertTree -- Insert a color into the octree
//
void InsertTree(OctreeType **tree, RGBType *color, uint depth)
{
    int level;
    if (*tree == (OctreeType *)NULL) {
        *tree = CreateOctNode(depth);
    }
    if ((*tree)->isleaf) {
        (*tree)->npixels++;
        (*tree)->redsum += color->r;
        (*tree)->greensum += color->g;
        (*tree)->bluesum += color->b;
    }
    else {
        InsertTree(&((*tree)->child[LEVEL(color, TREEDEPTH-depth)]),
                   color,
                   depth+1);
    }
}
// ReduceTree -- Combines all the children of a node into the parent, 
// makes the parent into a leaf
//
void ReduceTree()
{
    OctreeType  *node;
    ulong   sumred=0, sumgreen=0, sumblue=0;
    byte    i, nchild=0;
    node = GetReducible();
    for (i = 0; i < COLORBITS; i++) {
        if (node->child[i]) {
            nchild++;
            sumred += node->child[i]->redsum;
            sumgreen += node->child[i]->greensum;
            sumblue += node->child[i]->bluesum;
            node->npixels += node->child[i]->npixels;
            free(node->child[i]);
        }
    }
    node->isleaf = True;
    node->redsum = sumred;
    node->greensum = sumgreen;
    node->bluesum = sumblue;
    glbTotalLeaves -= (nchild - 1);
}
// CreateOctNode -- Allocates and initializes a new octree node.  The level 
// of the node is determined by the caller.
// Arguments:  level   int     Tree level where the node will be inserted.
// Returns:    Pointer to newly allocated node.  Does not return on failure.
//
OctreeType *CreateOctNode(int level)
{
    static OctreeType  *newnode;
    int                 i;
    newnode = (OctreeType *)getMem(sizeof(OctreeType));
    newnode->level = level;
    newnode->isleaf = level == glbLeafLevel;
    if (newnode->isleaf) { 
        glbTotalLeaves++;
    }
    else {
        MakeReducible(level, newnode);
    }
    newnode->npixels = 0;
    newnode->index = 0;
    newnode->npixels = 0;
    newnode->redsum = newnode->greensum = newnode->bluesum = 0L;
    for (i = 0; i < COLORBITS; i++) {
        newnode->child[i] = NULL;
    }
    return newnode;
}
// MakeReducible -- Adds a node to the reducible list for the specified level
//
static void MakeReducible(int level, OctreeType *node)
{
    node->nextnode = reducelist[level];
    reducelist[level] = node;
}
// GetReducible -- Returns next available reducible node at tree's leaf level
//
static OctreeType *GetReducible(void)
{
    OctreeType *node;
    
    while (reducelist[glbLeafLevel-1] == NULL) {
        glbLeafLevel--;
    }
    node = reducelist[glbLeafLevel-1];
    reducelist[glbLeafLevel-1] = reducelist[glbLeafLevel-1]->nextnode;
    return node;
}
// MakePaletteTable -- Given a color octree, traverse tree and: 
//  - Add the averaged RGB leaf color to the color palette table;
//  - Store the palette table index in the tree;
// When this recursive function finally returns, 'index' will contain
// the total number of colors in the palette table.
//
void MakePaletteTable(OctreeType *tree, RGBType table[], int *index)
{
    int i;
    if (tree->isleaf) {
        table[*index].r = (byte)(tree->redsum / tree->npixels);
        table[*index].g = (byte)(tree->greensum / tree->npixels);
        table[*index].b = (byte)(tree->bluesum / tree->npixels);
        tree->index = *index;
        (*index)++;
    }
    else {
        for (i = 0; i < COLORBITS; i++) {
            if (tree->child[i]) {
                MakePaletteTable(tree->child[i], table, index);
            }
        }
    }
}
// QuantizeColor -- Returns palette table index of an RGB color by traversing 
// the octree to the leaf level
//
int QuantizeColor(OctreeType *tree, RGBType *color)
{
    if (tree->isleaf) {
        return tree->index;
    }
    else {
        QuantizeColor(tree->child[LEVEL(color,6-tree->level)],color);
    }
}
// TotalLeafNodes -- Returns the total leaves in the tree (glbTotalLeaves)
//
ulong TotalLeafNodes()
{
    return glbTotalLeaves;
}
// getMem -- Memory allocation routine
//
static void *getMem(size_t size)
{
    void *  mem;
    mem = (void *)malloc(size);
    if (mem == NULL) {
        printf("Error allocating %ld bytes in getMem\n",(ulong)size);
        exit(-1);
    }
    return mem;
}