Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!topaz!ll-xn!mit-amt!mit-eddie!genrad!decvax!decwrl!pyramid!hplabs!ucbvax!ucsfcgl!pixar!ph
From: ph@pixar.UUCP
Newsgroups: net.graphics
Subject: Re: Translating an image of 24 bits to 8 bits
Message-ID: <2773@pixar.pixar>
Date: Mon, 12-May-86 16:40:22 EDT
Article-I.D.: pixar.2773
Posted: Mon May 12 16:40:22 1986
Date-Received: Thu, 15-May-86 07:31:22 EDT
References: <656@eneevax.UUCP>
Organization: Pixar -- Marin County, California
Lines: 38
Summary: color quantization algorithms discussed

In article <656@eneevax.UUCP>, phaedrus@eneevax.UUCP (Praveen Kumar) asks:
> Are there any algorithms to compress a 24-bit picture into an 8-bit picture?

Yes, I wrote a paper discussing such algorithms:
	Paul Heckbert
	Color Image Quantization for Frame Buffer Display
	SIGGRAPH '82 proceedings, pp. 297-307

To summarize the article, a good first approximation can be achieved by
using 3 bits red, 3 bits green, and 2 bits blue.  This "uniform quantization"
does not perform well on images which use a small gamut of colors in RGB
space, or contain large areas of smooth gradation (such as a human face),
however.  For such images it is preferable to use "adaptive tapered
quantization", which means choosing a colormap which is optimized for the
distribution of colors in that image.  The method which worked best involved
(a) collecting a histogram of colors in the original image, (b) clustering
the histogram to create a colormap of the desired length, and (c) quantizing
the original image to that colormap.  The last phase entails nearest neighbor
searching in 3-D color space.  Regardless of what colormap you use, dithering
can improve the appearance of quantized images.
On a vax 780, my implementation of the above ran in under a minute.
I'm currently re-implementing it on the Pixar Image Computer,
where it should be blindingly fast.

I'll be presenting this quantization work at the Advanced Image Processing
course at the SIGGRAPH conference in Dallas, August 18-22.

I'd like to hear from those who have implemented algorithms (mine or anyone's)
for color image quantization; please e-mail.

You might check the literature in remote sensing and image processing as well,
where such algorithms are called "unsupervised multispectral classification".

-- 
Paul Heckbert
Pixar				415-499-3600
P.O. Box 13719			UUCP: {sun,ucbvax}!pixar!ph
San Rafael, CA 94913		ARPA: ph%pixar.uucp@ucbvax.berkeley.edu