_COLOR QUANTIZATION USING OCTREES_
by Dean Clark

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


Example 1: 

Initialize the differential to 1/scale;
Initialize the accumulated differential to 0;
Get the first original pixel;
Do
	Copy original pixel to next resized pixel;
	If (int)(accumulated differential + differential) > 
                                     (int)(accumulated differential) then
		Get next original pixel;
	Add differential to accumulated differential;
While there are unprocessed original pixels.