From naughton@sun.COM Sun Sep 18 04:37:55 1988
Path: leah!uwmcsd1!mailrus!ames!oliveb!sun!wind!naughton
From: naughton%wind@Sun.COM (Patrick Naughton)
Newsgroups: comp.graphics
Subject: Re: Color Pallet Mapping?
Summary: References cited.
Keywords: Floyd/Steinberg, Dithering, Paul Heckbert, Color Image Quantization
Message-ID: <68823@sun.uucp>
Date: 18 Sep 88 08:37:55 GMT
References: <101880001@hpcvlx.HP.COM> <522@epicb.UUCP>
Sender: news@sun.uucp
Reply-To: naughton@sun.COM (Patrick Naughton)
Organization: Sun Microsystems, Mountain View
Lines: 55


Yes folks... It's official!
This is now the ``Most Asked Question on Comp.Graphics''

>> I have this image data...  and it has more colors than my display... 
>> and I still want to see the correct colors.  How do I do it?
 
Well the last answer posted for this was mostly correct.  I have a
couple of nits though:

Lou's last name is spelled Steinberg, not Stineberg.  And the median-cut
algorithm attributed to him is actually due to the man who brought us
all "Ray Traced Bill Cosby Commercials..." Paul Heckbert, UCB CS grad
student, and one of the only people on the net to actually flame
himself.  (remember the people without a sense of humor who flamed Paul
for the Jell-O paper? well he was one of them...  :-)

I have coded and used both of these guys' algorithms and have been
putting them to good use for some time now.  (My first posting to
comp.graphics asked this very question, to which Paul and Lou both
responded personally, with code examples...  Isn't USENET a wonderful
resource?)

Anyway, if you are looking to reduce color image data to a bilevel
device such as a mono-printer, use F/S dithering only because you
already know the that the colors in the output colormap are black and
white; and use the CIQ algorithm for reducing the number of colors when
the output is more than monochrome.  In the latter case, F/S dithering
after CIQ color selection can reduce some of the contours in cases where
there are a low number of output colors (i.e.  16 or lower).  At 256
output colors, the images sometimes look better w/o dithering. 

Good luck... here are the references to the original papers.

Floyd, R.W. and Steinberg, L.
``An Adaptive Algorithm for Spatial Gray Scale.'',
Proceedings of the Society for Information Display,
Volume 17, Number 2, 2nd quarter 1976.

Heckbert, Paul
``Color Image Quantization for Frame Buffer Display'',
SIGGRAPH Proceedings on Computer Graphics,
Volume 16, Number 3, June 1982, p. 297.

-Patrick
__________________________________________________________________
Patrick J. Naughton			    ARPA: naughton@Sun.COM
Window Systems Group			    UUCP: ...!sun!naughton
Sun Microsystems, Inc.			    AT&T: (415) 336 - 1080

---``The X11/NeWS Merge... I love it now... you'll love it soon.''
    ______________________________________________________________________
    Patrick J. Naughton				    ARPA: naughton@Sun.COM
    Window Systems Group			    UUCP: ...!sun!naughton
    Sun Microsystems, Inc.			    AT&T: (415) 336 - 1080