12.6 COLORS

---

Ø•Û��ÛØ“Û

It has been long know that the eye can be tricked into seeing a wide range of colors by blending three different colors in different intensities.

In the additive color scheme we add red blue and green (RGB). We start with black and add shades of these colors.

In the subtractive color scheme we start a white pixel. The intensity is reduced by filtering the colors magenta, cyan and yellow.

Most computers use the RGB scheme, but the subtractive color scheme is popular in printing and photographic reproduction techniques.

Some of the techniques used when limited numbers of colors or shades are available are,

- colors maps

- dithering

12.6.1 Color Maps

A color map is a list of colors that the computer can use to draw with.

The eye is very sensitive and can sense millions of different colors. And current trends are to go to 24 bit color systems that have 8 bits for each primary color. This gives the ability to display different colors so close that the human eye cannot detect the difference.

For various reasons we will use machines that have limited numbers of colors available (256 is common).

When this occurs colors that should look like smooth transitions tend to look more like bands of color.

One approach to providing colors is to construct a well distributed pallet (a fixed set of colors) that the user can select from. They must always find the best match to their desired colors.

The eye tends to be more sensitive to certain colors, and so one approach is to map the colors into a pallet using color bit assignments. For example for a pallet of 256 (8 bits) we may choose to assign 3 bits to blue, 3 bits to blue and only 2 bits to red. This means that there will be 8 intensity levels for both green and blue, but only four for red.

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.

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

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

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:

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.