raveling@isi.edu (Paul Raveling) (01/06/90)
In answering an email message I just somewhat announced
a new color quantization algorithm whose prototype first
worked without bugs a few days ago. It appears to be
about an order of magnitude faster than my old algorithm
and it produces (I think) better perceived image fidelity.
Here are some notes from the email reply...
> How does it differ from Paul's algorithm? [Paul is Paul Heckbert]
His algorithm prequantizes pixels to some precision, 5 bits per
RGB component suggested, and builds a histogram of these prequantized
colors. Then he uses a median cut algorithm to partition
RGB space into boxes (parellelopipeds) containing [ideally] equal
numbers of colors.
My new algorithm begins by doing something like Heckbert's
prequantization, but the array it builds contains pointers to
structures that will be manipulated in various ways. First
they're threaded into a queue in descending order by color
frequency. Next, a tree synthesis phase puts them into a
threaded tree until the number of nodes matches the desired
number of colors.
The synthesis algorithm is a key component, and builds the
tree breadth-first. To oversimplify a bit, for each original
color it finds the nearest color in the tree. That's a relatively
short process because of the tree structure. If the subject color
is within a given "capture radius" of the nearest color, the subject
color is forwarded to a thread to be reprocessed deeper in the tree.
The nearest color will become the subject node's parent, so its identity
is saved immediately. If the nearest color is outside the current
capture radius, the subject color becomes a new sibling among its
parent's offspring. As each node is added to the tree, it's also
appended to a thread that enables convenient scanning of the entire
tree or of any given level.
Capture radius begins at 255 so that the tree's root node is the
most frequent color. Capture radius is divided by 2 for each successively
deeper level in the tree. Since nodes are added to each level in
descending order by frequency, it represents clusters of colors
at increasing resolution as the tree grows deeper and favors locating
these clusters at the most frequent colors. The "capture radius"
logic assures that low frequency colors can be retained, and serves
the same sort of function as the median cut's box-splitting while
(hopefully) getting better association between individual colors
and clusters.
Distance computation is important. It uses a lot of table lookups
both for speed and for versatility in changing the distance function.
The best distance function I've tried is NOT purely Euclidean distance
in RGB space; it's
sqrt ((|R1**2 - R2**2| + |G1**2 - G2**2| + |B1**2 - B2**2|)/ 3 )
so that distance is partly dependent on luminance. Using fixed-point values
to represent color components in [0,1], this produces relatively small
distances for bright colors and relatively large distances for dark
colors. Combined with a constant capture radius in the tree synthesis
phase, this produces higher resolution for bright colors and lower
resolution for dark colors.
----------------
Paul Raveling
Raveling@isi.edu