May 92 - IN SEARCH OF THE OPTIMAL PALETTE
IN SEARCH OF THE OPTIMAL PALETTE
DAVE GOOD AND KONSTANTIN OTHMER
When you want to display an image that contains more color information than the
display device is capable of rendering, how do you pick the best colors to use? The
Picture Utilities Package, new in System 7, provides two methods, which we describe
here. You also have the option of developing your own color selection algorithm. This
article and the accompanying code on the Developer CD Series disc will get you started.
It's tricky to display an image when the number of colors used in the source exceeds
the number of colors available on the device. On an indexed device (256 or fewer
colors), an application can choose, via the Palette Manager, which colors to use. But
how will it know which colors are the best ones to choose, given a particular image?
To avoid this issue altogether, your application can simply draw the image and let
QuickDraw use its default color palettes to make the choice. Because these palettes
contain a well-dispersed set of colors, most images look pretty good. However, in the
case of an image that uses an unbalanced set of colors, such as an underwater scene
with many subtle shades of blue, relying on the default palette will not produce a
good-looking result. In this case, youmust tackle the issue of how to choose the
optimal palette. That's when the new Picture Utilities Package can help.
Picture Utilities provides two methods--the popular method and the median
method--for determining the best colors. This article describes these two methods. In
addition, it describes a third method--the octree method--which, in addition to being
useful in itself, makes a convenient starting point for you to develop your own
algorithm for choosing the optimal color palette.
DECIDING WHICH METHOD TO USE
It would be nice if one method of selecting colors worked best for all types of images.
But the truth is that the methods provided in Picture Utilities work best for some
types of images (such as those whose colors are all clustered in one small portion of
the RGB cube), while QuickDraw's standard method works best for other types.
Therefore, it's always important to give the user a choice of which Picture Utilities
color-picking method to use and whether to use one of these at all.
The three methods we discuss here differ in how they approximate the ideal color set.
The popular method bases its choices on a frequency count of colors used in the image,
returning the most frequently used colors. Both the median and octree methods are
algorithms that describe occupancy in a space. In this case, the space is the color cube
with axes of red, green, and blue, and the occupants are the colors in the image. These
algorithms differ in the way they divide up the space in order to return the correct
number of colors. The median algorithm starts with one giant box covering the entire
cube and splits it into successively smaller boxes; the octree algorithm starts with
lots of tiny boxes and joins them into larger ones. Both methods return the weighted
average of each of the boxes as the final set of colors.
The most appropriate method for your particular use depends on factors such as the
type of image you want to display (real world, computer-generated, graphic, and so
on), image content (perhaps the colors of items in the foreground are more important
than the colors of items in the background), or even how the image will be displayed
(halftoned or dithered, for example). For instance, none of these methods take
dithering into account, although since we provide you with the source code, you could
modify the octree method to do so.
The speed of each method also varies, with the popular method being fastest, the
median method slower, and the octree method slowest, since in the latter there are
more calculations involved for each color chosen. Also, the code that we supply for the
octree method is intended to be easy to understand rather than blazingly fast. In fact,
the current code is slower than the popular method by a factor of four, but with a little
work this could probably be improved to be only twice as slow.
Another basic consideration is whether you want to represent the majority of colors in
the image or the range of colors present. For example, if you could select only two
colors to represent an image that contains several different shades of red and one blue
dot, you would have to decide whether to pick two reds in an attempt to represent the
majority of colors in the image, or one red and one blue to represent the range of
colors the image contains. The popular method would do the former, while the median
method would do the latter.
In general, the best method to use for an image that has a fairly well dispersed set of
colors is QuickDraw's default palette. The popular method is useful when the source
image contains only a few more colors than are available on the display device. For
example, if you want to display a 32-bit image that uses only 200 distinct colors on
an 8-bit device, the popular method is the best choice for speed and accuracy. While
this case is trivial, using the popular method does guarantee that the needed colors will
be made available, a claim that can't be made for the default palette. The median and
octree methods generally give the best results for images where small patches of a
distinctly different color must be preserved at the cost of blending together large
patches of similar colors.
Experience will give you a better feel for the strengths and weaknesses of each of these
methods. Meanwhile, for purposes of comparison, Figure 1 shows screen snapshots of
a 32-bit image as it originally appeared, using QuickDraw's default 16-color palette,
using 16 popular colors, using 16 median colors, and using 16 octree colors. The
original image has 77 different colors (to a resolution of five bits per color
component). A test program on theDeveloper CD Series disc enables you to experiment
with this image (or others) and to take a look at the code used to generate the various
versions.
Notice in the original image that the colors marking the minutes follow a smooth
progression from cyan on the far left to dark blue at the top to magenta on the right to
purple on the bottom and then to dark red just before the cyan. Also notice the subtle
color blending where the translucent minute and second hands intersect the underlying
clock. When the standard 16-color palette is used, the soft colors of the minute
markers change into much brighter, harder colors, and the smooth transitions are
replaced by sudden transitions. The colors of the background and the face of the clock
have changed. Furthermore, the subtle difference in color between the background and
the background of the date (January 24) is lost.
The popular method preserves the colors of the largest color areas: the background,
the clock face, the background of the date, the color of the minute and hour hands, and
the lettering. The colors of the minute markers remain soft, but lose their shading
resolution; for example, the cyan is replaced by a darker blue. Because it preserves
the range of colors, the median method performs somewhat better on the minute
markers than the previous two methods, but the clock face turns to black and the green
hand becomes washed out. Although the image's appearance may not be ideal because
many of the large areas are wrong, areas of the image that depend on the color ranges
(which in this image just happen to occupy small areas) are reproduced more
accurately. When the octree method is used, the result is similar to that of the median
method, except the green hour hand is completely lost. This is due to the simple tree
reduction algorithm we use; if the tree reduction improvements that we suggest at the
end of the article were implemented, the hour hand most likely would be preserved,
although its shade of green might change (much as happened with the median method).
The octree performed better than the median in preserving the color of the text and the
background of the date.
One conclusion from these images is that there is not a single best color-picking
algorithm, even for a particular picture. For this image, we would be inclined to use
the popular method, since we don't care too much about the subtle shading effects on
the minute markers. However, an artist might be much more concerned with the
subtle shading effects and actually not care if the face of the clock went to a completely
different but still solid shade. In this case, the artist would probably pick the median
or octree method. This is why applications that provide color optimization should allow
the user to choose between the various available methods.
Default 16-color palette 16 popular colors
16 median colors 16 octree colors
Figure 1 An Image Displayed Using Four Different Color-Picking Methods
There is also a "system" method built into the Picture Utilities Package that tries to
select the best general method available. Currently, the popular method is selected if
the number of requested colors is 75% or greater of the total number of distinct
colors in the image (to a resolution of five bits per color component); otherwise the
median method is selected. The operation of this system method is almost certain to
change in the future.
Now that you have some idea of how the available color-picking methods compare, we
turn to details of how the popular, median, and octree methods work.
HOW THE POPULAR METHOD WORKS