# 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
[email protected]*

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^{24} 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
*row**s*x*columns* 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. Scan the image, and insert colors into an octree structure.

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

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