Color Quantization using Octrees

Dean, a programmer/analyst who develops graphics and imaging applications, can be contacted at [email protected].

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

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

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

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

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

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;
}