In 1988, M. Gervautz and W. Purgathofer of Austria's Technische UniversitŠt Wien published an article entitled "A Simple Method for Color Quantization: Octree Quantization." They proposed an elegant new method for quantizing color bitmap images by employing octrees-tree-like data structures whose nodes contain pointers to up to eight subnodes. Properly implemented, octree color quantization is at least as fast as the median-cut method and more memory-efficient.
The basic idea in octree color quantization is to graph an image's RGB color values in a hierarchical octree. The octree can go up to nine levels deep-a root level plus one level for each bit in an 8-bit red, green, or blue value-but it's typically restricted to fewer levels to conserve memory. Lower levels correspond to less significant bits in RGB color values, so allowing the octree to grow deeper than five or six levels has little or no effect on the output. Leaf nodes (nodes with no children) store pixel counts and running totals of the red, green, and blue color components of the pixels encoded there, while intermediate nodes form paths from the topmost level in the octree to the leaves. This is an efficient way to count colors and the number of occurrences of each color because no memory is allocated for colors that don't appear in the image. If the number of leaf nodes happens to be equal to or less than the number of palette colors you want, you can fill a palette simply by traversing the octree and copying RGB values from its leaves.
The beauty of the octree method is what happens when the number of leaf nodes n exceeds the desired number of palette colors k. Each time adding a color to the octree creates a new leaf, n is compared to k. If n is greater than k, the tree is reduced by merging one or more leaf nodes into the parent. After the operation is complete, the parent, which was an intermediate node, is a leaf node that stores the combined color information of all its former children.
Because the octree is trimmed continually to keep the leaf count under k, you end up with an octree containing k or fewer leaves whose RGB values make ideal palette colors. No matter how many colors the image contains, you can walk the octree and pick leaves off it to formulate a palette. Better yet, the octree never requires memory for more than k+1 leaf nodes plus some number of intermediate nodes.
There are two parts of an octree that I want to study: the parent-child relationship between nodes and the significance of the RGB data in each leaf. Figure 1 shows the parent-child relationship for each node. At a given level in the tree, a value from zero to 7, derived from the RGB color value, identifies a child node. At the uppermost (root) level, bit 7 of the red value is combined with bit 7 of the green value and bit 7 of the blue value to form a 3-bit index. Bit 7 from the red value becomes bit 2 in the index, bit 7 from the green value becomes bit 1 in the index, and bit 7 from the blue value becomes bit zero in the index. At the next level, bit 6 is used instead of bit 7, and the bit number keeps decreasing as the level number increases. For red, green, and blue color values equal to 109 (binary 01101101), 204 (11001100), and 170 (10101010), the index of the first child node is 3 (011), the index of the second child node is 6 (110), and so on. This mechanism places the more significant bits of the RGB values at the top of the tree. In this example, the octree's depth is restricted to five levels, which allows you to factor in up to 4 bits of each 8-bit color component. The remaining bits are effectively averaged together.
No comments:
Post a Comment