Graphics
GraphicsHere's a simple trick to speed mapping a large set of colors onto a smaller pallette.
Color dithering and color quantization are two common operations used in graphics programs. They approximate high-resolution color on devices with limited available colors. Both techniques require finding the closest match to a given high-resolution color from some set of available colors. Often this is done by computing an inverse color map, a table listing every high-resolution color and its nearest match in the set. Unfortunately, the size of these maps can be prohibitive, especially on microcomputers, both because of the space needed to store the table (17 million entries for 24-bit RGB) and the time required to compute it.
An alternative is to simply maintain a list of available colors in the color map and search this list for the closest match for each color in the image. This process is reasonably efficient if you can assign a linear order to all the colors in RGB space. Then you can search for the closest match to a given color using a binary search over an ordered list of available colors.
Two colors can be considered close if they match in the most significant bits of their color components. The following ordering technique corresponds to this definition of "close:" interleave the bits of an RGB color tuple into a single integer value. For example, if there are eight bits in each color component, then the color tuple
(r7 ... r0, g7 ... g0, b7 ... b0)becomes a 24-bit integer
r7g7b7r6g6b6 ... r1g1b1r0g0b0.This interleaving scheme is also illustrated by Figure 1, in steps 1 and 2.
Red bits have highest significance in the new integer, followed by green, then blue. This is because human eyesight is more sensitive to variations in red than in green, and more sensitive to changes in green than in blue. Listing 1 shows sample code to do the interleaving.
You still need to produce a color map, but now it can be much smaller, since it contains entries only for colors that can be displayed by your hardware. Convert all the colors your hardware can display to 24-bit interleaved format, and store them in numeric order in the map. Figure 1 shows a hypothetical map of 16 colors. The left side of the map contains the "keys" in interleaved format; the right side contains the corresponding "data" that must be sent to the display.
By representing colors in this fashion, you can do a quick binary search of the map using integer arithmetic to find the nearest color match. While not as accurate as methods that generate an inverse color map, this method is reasonably fast and requires significantly less memory than those methods. o
References
Clifford A. Shaffer. "Bit Interleaving for Quad- or Octrees," in Graphics Gems, edited by Andrew S. Glassner, pp. 443-445. (Academic Press, 1990).
Spencer W. Thomas. "Efficient Inverse Color Map Computation," in Graphics Gems II, edited by James Arvo, pp. 116-125. (Academic Press, 1991).
Tim Kientzle works as a technical editor for Dr. Dobbs Journal. He has a Ph.D. in mathematics from the University of California at Berkeley. He is author of The Working Programmer's Guide to Serial Protocols, and Internet File Formats (both published by Coriolis Group). He can be contacted at kientzle@netcom.com.