If you have to map many pixels to a relatively small palette, building a translation table wisely may prove to be the best approach.
Introduction
True color images are made of pixels stored as red, green, and blue (RGB) components, and the amount of different colors contained in the image can be very large (i.e., millions of colors). The large number of colors makes true color desirable for high-quality image display, but there are still many situations for which it is not practical. For example, many graphics displays can show only 256 colors. A certain printer may be limited to a specific set of colors. In addition, high-speed applications such as animation typically require limited color, palette-based images. Therefore, we need a way to convert the true color output of certain processes (e.g. ray tracing) to palette-based images.
Converting a true color image to a palette-based image consists of several steps. In general, these are:
1. Do a color quantization; that is, find a small number of colors (called a palette) that best represents the colors contained in the true color image.
2. Find closest matches. Convert the original RGB pixels to another set of pixels that use the palette obtained in step 1. Select colors from the palette that best approximate the original image, maybe performing, at the same time, some type of dithering technique.
In the case of a color printer the number of colors is usually fixed and thus step 1 above isn't necessary. For displays, sometimes you want to create a palette manually, or you want it to be automatically created from the true color image(s).
Matching via 3-D Lookup
I have come up with an algorithm that solves step 2, which I've called 3-D lookup table color matching. The algorithm operates with a C three-dimensional array of bytes (i.e., C chars) for converting the original pixels. As always, it's easier to begin with a simple example, so let's consider for a moment the two-dimensional case. Suppose the pixels of the image don't have three components (for RGB), but only two. In this case all possible colors in this image can be mapped inside a square in a two-dimensional space. Obviously, the palette colors would also map to the inside of this square in some way. (I say "in some way" because palette colors may consist of fewer bits than their true color counterparts, such as the six bits per color component used in VGA and SVGA 256-color modes.) Suppose the palette consists of just three two-component colors: (50,175), (255,255), and (0,0). Figure 1 shows a plot of this square and the palette colors.
The lookup technique works as follows: Create a 2-D array in C to represent this square, and plot the palette colors in this array. The rest of the array must then be filled in such a way that each array entry automatically gives the closest plotted palette color. This is the fastest method I can think of for performing a color match, especially when having to convert a large number of pixels to a single palette.
Figure 2a shows how this array is filled. Starting with each palette color as a center point, the algorithm grows circular regions which expand outward by steps. Each circular region is filled with the palette color index representing the palette color at its center. A given circle cannot override what has already been filled. When all array entries are filled, the array represents an "influence map" that gives the closest palette color for any given two-component color.
The three-dimensional case is exactly the same except that the palette colors are plotted in a 3-D array and the algorithm must fill spheres instead of circles. Of course, larger 3-D arrays bring extra resolution and thus more precision, but take longer to fill. Fortunately, for a given palette, the filling happens only once. After that, converting a true-color pixel to a palette-based color just takes a table lookup.
Implementation
Implementing this algorithm requires the following steps:
1. Create the 3-D array for a given palette (call function creatematcharray)
2. Look up elements in the array as many times as needed (call findcolor)
3. Destroy the array when finished (call destroymatcharray)
These functions are shown in 3dtable.c (Listing 1) .
Function creatematcharray creates the 3-D array. It accepts several parameters: the palette to use and the resolution of the array, in maximum bits to use for each color component. The function requires the palette to be passed as an array of struct rgb_color (defined in 3dtable.h, see Listing 2) . The resolution is passed as three ints (rbits, gbits, and bbits) that indicate the number of bits to use for each component in determining the size of the array. For example, rbits=3, gbits=4, and bbits=6 would result in an array of 23 * 24 * 26 = 8192 bytes. To plot the palette colors into the array, creatematcharray converts the palette colors' components to the range specified by the resolution parameters. For VGA graphics I've tried bit sizes of 5 for all three components and various palettes, achieving good times and color conversions. (In this case, the required array size is 32,768 bytes.) I've chosen the color resolution parameters as numbers of bits so that color component scale conversions are really fast when finding matches, consisting only of bit shifts.
creatematcharray carries out the following steps:
1. It dynamically assigns memory for the array
2. It selects the palette colors to use for filling the array and plots them in the array. creatematcharray must "select" palette colors because some palette colors may have exactly the same component values, or when scaled to array coordinates may yield equal component values (especially when the array resolution is low). In both cases only one of the many possible coincidences must be filled.
3. It fills the rest of the array.
creatematcharray fills the array using cubes instead of spheres. Filling with cubes is much faster than with spheres, the code is greatly simplified, and it gives good quality. (See Figure 2b for a comparison of the filled 2-D array.)
Note also that creatematcharray assigns two 3-D arrays, but when it finishes only one array is needed to perform color matches. The other is deleted from memory. Keep this in mind when choosing values for rbits, gbits, and bbits. By the way, the maximum number you can use for these resolution parameters is eight. Of course, the minimum bit value is 1. If you specify eight bits for all components you'll get an array of 16,777,216 bytes. That kind of defeats the purpose of 3-D lookup. Besides, for a VGA palette there's no reason to use more than six bits for the resolution because that's the maximum resolution it supplies for each RGB component. A bit size of 6 for all components requires an array of just 262,144 bytes.
Naturally, due to memory requirements and array indexing, it's better to use a 32-bit compiler for this technique, but any 16-bit compiler that lets you create 32-bit integers and big arrays in memory should work (not without some performance penalty). Analyze the code and find where you should place the compiler-specific modifiers to make it work. Any compiler that lets you use 32-bit pointers and ints will do.
Function findcolor takes two parameters, the match array returned by creatematcharray, and an rgb_color struct that specifies the RGB color to be matched. findcolor converts the rgb_color parameter to the correct range of values obtained by taking into account the resolution parameters specified earlier (see above).
deletematcharray simply removes the dynamically allocated array from the heap.
An Example
Here's a piece of code that prepares the structures for doing searches on a four-color palette using an array with a resolution of 6, 5, and 5 for each color component:
struct rgb_color palette[4]={{0,0,0}, {90,60,90},
{120,20,90}, {200,128,30}};
struct rgb_color color1, color2;
struct match_array *table;
int match1, match2;
/* First, create the 3D table: */
table=creatematcharray(6, 5, 5,
table, 4);
/* Find as many color matches as you need */
/* These two calls find the best
color approximations */
/* for just two RGB colors:
(2,90,100) and (45,200,89): */
color1.r=2; color1.g=90; color1.b=100;
color2.r=45; color2.g=200; color2.b=89;
match1=findcolor(table, color1);
match2=findcolor(table, color2);
/* Remove array from memory: */
deletematcharray(table);
Final words
Maybe one day we will all have computers powerful enough to manage the data bandwidth required to effectively use true color images in all situations. Then we can have full-screen true color animation, computer games with real-time true color special effects. But until that day comes, we'll have to live with the limitation of low color graphics.
Leonard Vila has a BS in Computer Science from the University of Salamanca (Spain). He is mainly interested in computer graphics, especially computer games graphics and programming as well as 3-D modelling and animation. He is currently working at Dinamic Multimedia in Spain. He may be reached at +1(91)6586609, or at [email protected].
