Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!pasteur!miro.Berkeley.EDU!ph
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to best EGA/VGA palette?
Keywords: color, quantization, perception
Message-ID: <17086@pasteur.Berkeley.EDU>
Date: 12 Sep 89 04:45:22 GMT
Sender: news@pasteur.Berkeley.EDU
Organization: University of California at Berkeley
Lines: 161

I'd like to comment on some of the interesting ideas that people
have proposed recently regarding color image quantization algorithms.

(1) ITERATIVE IMPROVEMENT OF A COLORMAP

Patrick Flynn (flynn@pixel.cps.msu.edu) suggested:
 | ... Construct a (stratified?) sample from the original image by picking
 | up a subset of the true-color pixels falling into each bin Then cluster
 | those babies.  See if the resultant clustering is an improvement.  If
 | it is, publish it in SIGGRAPH and make big bucks.

Actually, I tried this and discussed such an iterative quantization
improvement algorithm in my paper:

	Paul Heckbert, "Color Image Quantization for Frame Buffer Display"
	SIGGRAPH '82 Proceedings

Once you've got a colormap, it can be improved by iterating the following step:

    For each color in the colormap, find the colors from the original
    image whose nearest neighbor in the colormap is that color
    (like finding the Voronoi diagram in color space), find the centroid
    of those original colors, and move the colormap color there.

The method converges to a (usually local) minimum of the error metric.
The technique was first proposed, I believe, in

	Lloyd, S. P.,  "Least squares quantization in PCM's",
	Bell Telephone Labs Memo, Murray Hill, N.J., 1957

and improved upon by

	Gray, R. M., Kieffer, J. C., and Linde, Y.  "Locally optimal
	block quantizer design", Information and Control 45, 1980, pp. 178-198.
    
Such techniques are common in clustering/classification algorithms for
pattern recognition.  I believe the K-MEANS algorithm uses it.

The method works fairly well in my experience: you can start with a
pretty poor colormap such as a uniform grid in RGB space with 3 bits
red, 3 bits green, 2 bits blue, iterate it maybe 10 times and the
quantization is much improved.  The results were not as good as median
cut in my experiments, however.

A digression into deeper issues:  Actually, the way I was
making the final color choice in my median cut algorithm, as the
centroid of the colors in a rectilinear box, is inferior to the
centroid-of-Voronoi-cell method used by such an iteration scheme.  The
median cut algorithm and many other rectilinear subdivision clustering
algorithms approximate the true Voronoi cells, which are convex
polyhedra of varying topology, with boxes.  A multidimensional
quantization (clustering) algorithm attempting to find the global error
minimum using true Voronoi cells would probably be extremely hairy.
The problem is tractable in 1-D, however, because Voronoi cells in 1-D
have fixed topology: they're intervals.  In fact, optimal monochrome image
quantization can be done in polynomial time using dynamic programming.
I mention the algorithm in my SIGGRAPH paper and it's described in full
in my Bachelor's thesis:

	Paul Heckbert, "Color Image Quantization for Frame Buffer Display"
	Bachelor's thesis, Math Dept, 1980
	(copies probably available through the MIT Media Lab)

and in

	Bruce, J. D., "Optimum quantization",
	MIT R.L.E. Technical Report #429, 1965.


(2) QUANTIZATION AS INVERSE COLORMAPS

Patrick also suggested:
 | ... it's interesting to examine the almost-inverse relationship
 | between color quantization and pseudocoloring...

Yes, I've often found it helpful to think of these data structures or
procedures for finding nearest neighbors in the colormap as inverse colormaps.
Colormaps take an index as input and return a color; while
nearest-color-in-colormap functions take a color as input and return an index.
Any cosmic significance here??  Who knows?


(3) FLESH TONES AND PERCEPTUAL IMAGE DIFFERENCE METRICS

Michael L. Mauldin (mlm@nl.cs.cmu.edu) brought up the subject of flesh tones:
 | Has anyone experimented with psychological color preferences ...
 | In some images containing people's faces, where the face is
 | only a small part of the image, very few colors are assigned
 | to "flesh" color.  The result is banding/loss of resolution in
 | an area of the image that is interesting to the viewer ...

Yes!  When I was testing quantization algorithms (popularity, median cut,
iterative, and others), I found that the quantization errors in many
images were not perceptually bothersome.  On the mandrill or other
images with lots of high frequencies, the contours and color errors are
lost in the noise, so to speak, and on expressionist paintings (I did a
lot of experiments with Franz Marc's painting "Blue Horses") the errors
aren't so bothersome, because who's to say what color a blue horse is
supposed to be, anyway? :-)  The numerical error as computed by the
quantitative metric (sum of squared distances in RGB space, in my case)
could be very high yet the eye didn't care.  On the other hand, when
I ran my algorithms on "Pamela" [Playboy, April 1978], any contouring on
the low-frequency areas of the face or color errors on the lips or eyes
were very noticeable.  Many of the colormap selection algorithms I tried
failed to pick a good red for the lips or a good blue for the eyes.
The median cut algorithm fared better than the others, but I never found an
algorithm that could select a 4-color colormap for Pamela as well as I could
by hand.

Clearly, a truly perceptually-based image difference metric would
have to go far beyond merely using a perceptual color space.  It would have
to take spatial differences into account as well, dealing with such issues
as contour edges, dithering, noise, frequency, spatial distortions,
and ultimately, image understanding.  Humans have evolved and learned to
focus their vision on faces, so a perceptual image difference metric would
weight such regions of an image more heavily than less "interesting" portions
of the image.

As a quick hack for my Bachelor's thesis, I implemented a program
called "doodle" that allowed the user to manually indicate the regions
of the picture that needed extra weight in the error calculation, by
tracing over them with a tablet.  For Pamela, I'd doodle over her eyes
and lips.  This technique, also recently suggested by Eric Pepke
(pepke@gw.scri.fsu.edu), helped quite a bit, but it was a slow,
iterative process for the user to wait a few minutes (back then) for
the resulting quantized image to come out.  Ken Sloan of U. of Washington
has suggested that this could be automated by weighting all edges more than
smooth regions, but this doesn't sound quite right to me, because it is was
the smoothly shaded, distinctive colors of the eyes and lips that gave me
the most trouble, not the edges and high frequency regions (such as hair).

I think it's easy to ascribe too much meaning to the numerical value of
simplistic error metrics such as the one I used.  I was disappointed that
Wan et al, in their paper:

	S. J. Wan, K. M. Wong, P. Prusinkiewicz,
	"An Algorithm for Multidimensional Data Clustering", ACM Trans.
	on Mathematical Software, vol. 14, no. 2, June 1988, pp. 153-162.

didn't show more pictures (did they show any color pictures?) to allow
comparison of the perceptual, subjective difference with their
quantitative, objective one.  Their variation on the median cut algorithm
splits at the point that minimizes the variance in the two sub-boxes,
rather than at the median; a technique that I discussed (but did not
analyze) in my BS thesis and SIGGRAPH paper.

Has anybody else tried automatic weighting in image difference metrics,
for color image quantization or any other purpose?


--

The popularity of this color image quantization topic in comp.graphics
never ceases to amaze me!  I almost didn't publish my 1982 paper because
I figured then that the 8 bit frame buffers of the time would all be replaced
by 24-bit ones in a few years.  The worldwide average depth today,
however, must be around 4 bits!

Paul Heckbert, CS grad student
508-7 Evans Hall, UC Berkeley		ARPA: ph@miro.berkeley.edu
Berkeley, CA 94720			UUCP: ucbvax!miro.berkeley.edu!ph