Graphics Reference
In-Depth Information
big issue today because graphics systems typically have no problem displaying 24 bits
of color; however, in earlier days it was only possible to display 256 colors (or less).
We sketch some solutions to the color quantization problem here. More details can
be found in [Lind92]. See also [Paet90].
Fixed Palette Quantization.
Here one basically ignores the problem and simply
uses a fixed palette of, say, 256 colors for
all
pictures and “rounds” all image colors
to one of these. This is obviously the simplest approach but would probably not be
very satisfying.
Uniform Quantization.
Here we divide the RGB color cube into uniformly spaced
subcubes and round any number to its appropriate subcube representative.
Popularity Quantization
([Heck82])
.
In this approach we count the number of
pixels associated to each color in the image and then use the colors with the largest
counts. All other colors are mapped to one of these using some sort of minimum dis-
tance criterion. The algorithm works fairly well if there are only a small number of
colors in the image. It has problem with highlights that usually account for only a few
pixels. One way that this problem is diminished is by always including the eight
corners of the RGB cube.
Median Cut Quantization
([Heck82])
.
This improves on the popularity quantiza-
tion and is probably the most popular method. The idea here is to choose colors so
that each represents roughly the same number of pixels in the image. The set of colors
in the RGB color cube from the image is enclosed in a box and the longest side of the
box is divided in half at the median point so that half of the image colors are in each
half. This division process is repeated recursively on the smaller boxes until we have
as many boxes as the desired number of colors in our palette. All image colors are
then rounded to the colors at the centroid of the boxes.
Octree Quantization
([GerP90])
.
This approach mimics the octree approach to
representing solids. We start with the color cube and divide it into eight subcubes.
These subcubes are then further subdivided recursively depending on whether or not
they contain a color from the image. The tree is maintained at the desired size with
an averaging process. Any reductions in size are carried out as the tree is being built.
There is no need to use up a lot of space and build the complete tree first. The main
advantages of octree quantization are that it is faster, uses less memory, and produces
similar results to the other methods.
9.11
Programming Notes
This section provides the reader with a few helpful hints for using shading in a mod-
eling program. Most are in reference to the Bouknight or Phong reflectance models.
First of all, use ambient light because, without ambient light, back faces would
be black. Set the ambient light to the color of the background, even though this is not
what we actually experience because in real life light reaches that face from diffuse
