ALGORITHM ALLEY

The Popularity Algorithm

Every color is completely specified by the path to its blue component, so you store the color counts there. To store a color, each axis is scanned in turn until all three color components have been matched. If any component is not found, a new node is created. To speed the search a little, each list is kept sorted.

To find the most popular colors in the image, you need to access them in order by count. The function AddColorToList() in Example 1 maintains an array of pointers (popcolors) to the most popular nodes in the color matrix. When the first image scan is finished, popcolors will point to the 256 colors for the new color-palette table. (Example 1 is excerpted from the popular.c program, which is available electronically; see "Availability, page 3.)

Finally, the new quantized color image is built. As the original image is rescanned, the popcolors table is searched for a matching RGB value. If a color in the table exactly matches the image color, then the color-table index is displayed or saved. If you go past the 256th element, then you use the index of the color in the table closest to the image color.

Vector Basics

What do I mean by "closest" color? In a qualitative sense, you want the color in the table that is the least distinguishable from the color in the image. In quantitative terms, you want the color in the table that is the shortest straight-line distance from the actual color. Remember that all the colors are inside a 3-D cube, so the distance between two colors is d= half brace c2-c1, where c1 and c2 are two points in the color cube defined by their individual R, G, and B values. In algebraic terms, d=sqrt((r2-r1)²+(g2-g1)²+(b2-b1)²), where d is always nonnegative because of the squared terms, and implying that (c2-c1)=(c1-c2). The smaller d is, the closer the two colors are; if d is 0, then the colors are the same. In practice, you eliminate the square-root calculation, since the square-root function doesn't change the ordering of the numbers (if a>b then sqrt(a)>sqrt(b)).

The Code

As each image RGB value is read, it is converted to VGA (6 bits per primary) and added to the color matrix, or its count is incremented if it's already in the matrix. The popular-colors list is then updated. When the entire image has been read, LinearizePopcolors() extracts the most popular RGB components from the popular-colors list. This is simply a convenience to help make the next scan a little easier and faster.

The program then asks whether it should display the image or write it to a file. As written, the program uses the MetaWINDOW graphics-kernel system from Metagraphics Software (Scotts Valley, CA) for displaying images. However, all you really need are graphics initialization, VGA color palette, and pixel-drawing functions, which are universal in any graphics library or even through BIOS calls. The PCX code is also straightforward.

Results and Additional Heuristics

The proof of the pudding is in the eating, and the proof of any computer graphics technique is the result on the screen. Figure 2 is a computer-generated graphic at 24-bit color resolution. The image is 512x375 and contains about 4200 distinct colors. Figure 3 shows the same image quantized to 256 colors using popular.c. By most standards, the quantized image is an acceptable approximation.

The algorithm might miss small but visually significant areas of colors if none of them are popular enough. This is much more likely to occur on workstations, where each primary color is eight bits instead of VGA's six. The result can be that no color in the quantized palette table is close enough to these areas to produce good results.

One way of addressing this is to reduce the color resolution. Instead of eight or six bits of color, use five or even four bits. The sample program does this by prompting for a color "compression factor" for each primary color. These factors are used to reduce the number of distinct primary colors on each axis. Lowering the effective color resolution allows more image colors to become clumped around a single point in the system color cube; that is, the points in the color cube get "bigger." Fewer colors fall outside the clumps, so more fringe colors are represented.

Figure 4 shows the sample image quantized with five bits of color; Figure 5 shows it with four. Note that the highlights in the spheres and light reflections in the background mirrors are becoming more distinct, but the smooth-colored red floor begins to show serious banding. This is a typical result when color resolution is lowered. Which image--6-bit, 5-bit, or 4-bit--is "best" is subjective.

Most images have far fewer than their theoretical maximum number of colors, and those colors tend to group into a relatively small number of regions of similar colors. This is called "color coherence." Consider a photograph of a child on a sunny day in the park. The main elements of the photo are the child's face and clothing, the sky, grass and trees, and clouds. The sky is likely subtle shades of blue, the clouds are mostly gray-white, the grass and trees are expanses of green, and so on. A careful scan of the photo at VGA resolution and 24 bits of color might result in 60,000 distinct colors.

Yet most of those colors are in one of a few regions; blues for the sky, greens for the grass and trees, grays for clouds, and skin tones for the child. The many distinct colors in the scan are largely the result of minute subtleties of shading.

You might be able to improve some quantized images by making sure you get a representative sample from different regions in the color cube. Let's implement a heuristic that divides the output color palette into four regions; red-dominant, green-dominant, blue-dominant, and gray-dominant. A color is dominated by its brightest component. For the gray-dominant region, no primary color is significantly brighter than the others. I'll allow 64 elements of the 256-color palette for each dominant region.

In the sample program, if the user chooses to apply the color-dominance heuristic, the initial scan distributes input colors into four popularity-ordered lists instead of just one. After scanning, the four lists are combined into a single color palette by taking the most-popular 64 colors from each region. If a region doesn't have 64 distinct colors, its leftover palette space is distributed among the others.

Just as you have to define "closest color," you also have to define "dominant." There's no hard rule. A fast test would be that a primary color is at least N greater than either of the other colors, say 15. So the rgb value (56,37,18) is red-dominant, but (12,1,2) isn't. A different rule would make the dominant color N% greater, say 15 percent. By this rule, both of the example colors are red-dominant; popular.c uses a percentage of 20 percent.

You could extend this approach by distributing the colors among the eight octants of the color cube, or even use image characteristics to drive the distribution, but the code quickly becomes complex and, it turns out, the benefits tend to diminish. Figure 6 shows the sample image with the color-dominance heuristic applied.

Conclusion

For a long time I thought I had "invented" the popularity algorithm. It turns out, however, that Paul Heckbert published a paper describing the algorithm in 1982: "Color Image Quantization for Frame Buffer Display," (ACM 1982 SIGGRAPH Proceedings, Vol. 16, No. 3). The same paper describes another quantization technique called "Median-cut" (see also "Median-Cut Color Quantization," by Anton Kruger, DDJ, September 1994).

The algorithm's running time is bounded mainly by the number of pixels in the original image and the size of the quantized color table. These values drive the two image scans, the sparse matrix insertions, and the code that maintains the popularity list. The memory costs are bounded by the number of distinct colors in the original image. In practice, popular.c processes about 2800 image pixels per second on a 486/33 and spends most of its time accessing the disk. The program could be sped up somewhat by postponing the popularity ordering (AddColorToList()) until the color matrix has been built. There's a little extra unused space in each matrix node. The program assumes there will be at least 256 distinct colors in an image.

Other Color-Quantization Methods

The median-cut algorithm was first published by Heckbert, in the same article as the popularity algorithm. As in the popularity algorithm, you first create a cube structure containing all the colors in the original image. The cube is then recursively subdivided along its axes such that about the same number of pixels are represented in each subdivision. When there are 256 subcubes (or some other target number), the colors within them are averaged to find the lookup-table colors.

Michael Gervautz and Werner Purgathofer published their octree quantization technique in New Trends in Computer Graphics (edited by Nadia Magnenat-Thalman and David Thalman, Springer-Verlag, 1988). This technique was later summarized in Graphics Gems (edited by Andrew S. Glassner, Academic Press, 1990). As the name implies, an octree is a tree structure in which each node has eight children. As the original image is scanned, unique colors are inserted into the octree. Inserting the 257th color (or N+1) causes the tree to be reduced by merging the two closest tree colors into a single color. This method is unique in that there are never more than the final number of colors stored in the tree.

--D.C.

Example 1: The AddColorToList function.

/****************************************************************************
** AddColorToList
** Adds a color to the list of most popular colors in the image, if necessary
*****************************************************************************/
void AddColorToList(COLOR_NODE **popcolors, int npal,
                                int *currentcount, COLOR_NODE *color)
{
    COLOR_NODE  *temp;
    int         i;
    /* If table is empty then insert this color */
    if (*currentcount < 0) {
        *currentcount = 0;
        popcolors[*currentcount] = color;
        return;
    }
    /* Search the table for the same color */
    for (i = 0; i <= *currentcount; i++) {
        if (popcolors[i] == color) break;
    }
    if (popcolors[i] == color) {
        /* Found it. Since the color is already in the table, adjust it
        ** to its proper position */
        while (i && (popcolors[i-1]->count < popcolors[i]->count)) {
            temp = popcolors[i-1];
            popcolors[i-1] = popcolors[i];
            popcolors[i] = temp;
            i-;
        }
        return;
    }
    /* This color isn't in the list.  See if it belongs there.  First of all,
    ** if the list isn't full, this color must have a count of 1 and can be
    ** simply added to the end */
    if (*currentcount < npal-1) {
        (*currentcount)++;
        popcolors[*currentcount] = color;
    }
    else {
        /* Otherwise the list is full and this color may belong in the list.
        ** Start at the low end (if the color had a high count it would
        ** already be in the list) */
        if (color->count > popcolors[npal-1]->count) {
          i = npal - 1;
          popcolors[i] = color;
          i-;
          while ((i >=0) && (popcolors[i]->count < popcolors[i+1]->count)) {
                temp = popcolors[i+1];
                popcolors[i+1] = popcolors[i];
                popcolors[i] = temp;
                i-;
          }
        }
    }
}

Figure 1: Sparse 3-D matrix structure.

Figure 2: Original 24-bit image with a 512x375 resolution and about 4200 colors.

Figure 3: Same image as Figure 2, but quantized to 256 colors using the popular.c program.

Figure 4: Same image as Figure 3, but quantized with five bits of color.

Figure 5: Same image as Figure 3, but quantized with four bits of color.

Figure 6: Sample image with color-dominance heuristic applied.