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