####
1.5.1.1 - Quantization with an Octree RGB Cube

• In the octree quantization method [Graphic Gems by Andrew Glassner] the RGB color information is read sequentially from an input data file. The first k different colors are used as initial entries to the color table. If another color is added so that there are now k+1 colors, some very closely related colors are merged into one and their mean is used as the entry in the colormap. This procedure is repeated for each additional color.

• The RGB cube can be represented by an octree of depth eight by recursive subdivision of the RGB cube. The RGB values (0 - 255) are coordinates into the RGB cube. The bit pattern, corresponding to the same level in the octree as the bit position, can be used as the index for the branch into the octree.

Figure 20 - Mapping an RGB Value into the RGB Cube/Octree

#####
1.5.1.1.1 - Algorithm and Implementation

• The algorithm has the following three phases:

• Phase 1. Evaluation of Representative Colors

The first step to read the input data and insert colors into leaves of the octree.

InsertTree(Tree: Octree; RGB: Color);

begin

if Tree = NIL

then Make_and_Initialize_New_Node;

if Leaf

then

begin

{Update the number of represented pixels}

inc(Tree^.ColorCount);

{Sum the color values}

AddColors(Tree^.RGB,RGB)

end

else

InsertTree(Next[Branch(RGB)],RGB);

end

The next step is to combine successors of an intermediate node to one leaf node if there are more than the number of colors permitted in the colormap. Closest neighbors are found by putting the position of each leaf node in the octree into a linear list in sorted order and then finding leaves belonging to the same parent node. This is done by masking out the bits below a given parent node level and then finding a parent node with two or more children.

ReduceTree(Tree);

begin

{Find a reducible node}

GetReducible(Tree);

Sum := (0,0,0);

Children := 0;

for i : integer := 0,7 do

if Next[i] <> NIL

{There is an ith successor}

then

begin

Children := Children + 1;

AddColors(Sum,Tree^.Next[i],RGB);

end;

Tree^.Leaf := True;

{Cut the tree at this level}

Tree^.RGB := Sum;

{The node represents the sum of all color values of its children}

Size := Size - Children + 1;

end

• Filling the color table

The k leaves of the octree contain the colors for the color table (RGB/Color Count). The colors are written to the table by recursively examining the octree and the index to the colormap is stored in the node.

• Mapping the original colors onto the representatives

The image is read a second time using the RGB values stored in an array. For each color in the input, the representative color in the octree is found and its index to the color table is returned.

Quant(Tree: Octree; Original_Color: Color): index;

begin

if Leaf

then

return Tree^.ColorIndex

else

Quant(Tree^.Next[Branch(Orignial_Color)],Original_color);

end

#####
1.5.1.1.2 - Color Quantization Data Structures

• The following structure for an octnode is the basic structure used for mapping RGB values into the octree:

structure octnode{

int leaf,

colorcnt,

colorindex,

level,

sumR,

sumG,

sumB;

struct octnode *next[8];

}

- level is the level of the node in the octree,

- leaf indicates whether the node is an interior node in the octree or a leaf node,

- If the node is a leaf node,

• colorcnt counts the number of input colors that have been mapped to the node,

• sumR, sumG, and sumB are the sums of the color components of the colors that have been mapped to the node,

• colorindex is the index assigned to the color in the node when the colormap is made.

• Each node holds pointers to eight children. If the node is a leaf node, these pointers must be NULL pointers.

• A list is used to hold octree positions for the representative colors in the colormap. The list is sorted in ascending order to facilitate finding the most closely related colors when it becomes necessary to reduce the number of colors to the maximum size allowed in the colormap.

list[256]

• The colormap is a 3 by 256 array to hold the red, green, and blue color intensities.

colormap[3][256]

• When colors are to be displayed, the color intensities for the pixels are obtained with an index into the colormap. The module which displays the ray tracer image also uses this data structure.

• The RGB color vectors formed when reading the color intensities from the input file into the color quantizer are stored in an array:

pict[]

• The color vectors are used initially as representative colors to establish the colormap and a second time to obtain the indices for the original colors.