page 136

•When using a pallet the some colors will be overused, and other may never be used.

•Another useful approach is to quantize the color map so that it has the best coverage of the desired colors, and lower coverage of unused colors. This process is called quantization.

12.6.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.

page 138

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;

page 139

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

12.6.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:

-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,