Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wasatch!cs.utexas.edu!uunet!seismo!esosun!cogen!celerity!celit!billd
From: billd@fps.com (Bill Davidson)
Newsgroups: comp.graphics
Subject: Re: How to map 24-bit RGB to best EGA/VGA palette?
Message-ID: <586@celit.com>
Date: 25 Aug 89 04:05:53 GMT
References: <3129@cbnewsm.ATT.COM> <7743@cbmvax.UUCP> <13319@well.UUCP>
Sender: daemon@fps.com
Reply-To: billd@fps.com (Bill Davidson)
Distribution: na
Organization: FPS Computing Inc., San Diego CA
Lines: 43
Keywords: RGB EGA VGA color

In article <13319@well.UUCP> gors@well.UUCP (Gordon Stewart) writes:
>The classic paper on this subject is in SIGGRAPH notes (1982?) by
>Paul Heckbert, (paraphrased) "Color Image Quantization for Frame
>Buffer Display."

It was '82.  Most libraries don't carry it.  Find people who've been
into graphics a while.

>I myself have a color-selection algorithm which obviates truncating
>the pixels to 15 bits.  It doesn't use a histogram, but a multi-way
>partition method, and if applied using Heckbert's criterion (longest
>box),it is equivalent to the Heckbert method using a 24-bit histogram.

I'd like a more detailed description of this.  I'm collecting color
quantization algorithms (kind of like Jim Blinn and his margarine
tubs, er circle algorithms :-).  I have several modifications to
Heckbert's algorithm as well as a tree-based subdivision algorithm
by Paul Raveling.

>The process, as described in Heckbert, is two-fold (possibly three-fold)"
>
>	1) Select the best N colors;

		This is the median-cut method which *IS* Heckbert's
		paper.  The other two steps are peripheral (but
		important).  If you try and try and can't find
		a copy of the SIGGRAPH '82 proceedings, send me
		email and I'll sumarize the method for you.

>	2) Render the image via mapping function;
>opt.	3) While rendering, apply a dithering scheme to trade spatial
>	   for color resolution (effective if the target N colors are
>	   few - say, 16 or less - though this varies from image to image)

Speaking of dithering, I understand how to use Floyd-Steinberg for
color.  It's quite simple since you keep an error vector in RGB
three-space instead of just an error value.  This makes sense since
it will pull colors back against the error in the adjacent pixels.

How would one do an ordered dither in color or does this even make
sense?  It doesn't make sense to me.  Do you set up more matrices?

--Bill