From albanycs!leah:rsb584 Mon Dec 21 18:54:01 1987
Received: by albanycs.albany.edu (5.54/4.8)
	id AA28845; Mon, 21 Dec 87 18:13:02 EST
Date: Mon, 21 Dec 87 18:12:59 EST
From: albanycs!leah:rsb584 ( Raymond S Brand)
Received: by leah.Albany.EDU (5.58/1.1)
	id AA24231; Mon, 21 Dec 87 18:12:59 EST
Message-Id: <8712212312.AA24231@leah.Albany.EDU>
To: albanycs:beowulf!rsbx

>From lou@bearcat.rutgers.edu Mon Dec 21 15:04:02 1987
Path: leah!uwmcsd1!bbn!husc6!hao!gatech!rutgers!aramis.rutgers.edu!bearcat.rutgers.edu!lou
From: lou@bearcat.rutgers.edu (Lou Steinberg)
Newsgroups: comp.graphics
Subject: Re: Advanced Dither Needed
Keywords: dither
Message-ID: <545@bearcat.rutgers.edu>
Date: 21 Dec 87 20:04:02 GMT
References: <3703@ames.arpa>
Distribution: na
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 60
To: watson@ames.UUCP

In article <3703@ames.arpa> watson@ames.arpa (John S. Watson) writes:
>     I'm looking for either references to, or code for a really 
> nice color dithering algorithm.  The algorithm produces 8-bit dithered 
> images that are almost indistinguishable from the original 24-bit images.  
> 
>    The algorithm colors a pixels by somehow taking into account the 
> quantization errors in coloring the neighboring pixels.
> I think a similar algorithm is used in Sun's NeWS.
> 
>     I think the algorithm was first described by Floyd and Steinberg
> in 1975 but I don't have the exact reference(s).  If I had some harder
> references I could probably code up the algorithm myself, but I also
> don't want to re-invent the wheel.

I think you are referring to the article 
  Paul Heckert, "Color Image Quantization for Frame Buffer Display",
  Computer Graphics, V. 16 #3, July 1982, p. 297.

The dithering method he uses is an adaptation of an algorithm
developed by Bob Floyd and myself for B/W halftoning.  Our algorithm
is described in 
  Robert Floyd and Louis Steinberg, "An Adaptive Algorithm for Spatial
  Greyscale", Proceedings of the Society for Information Display, 
  V.17 #2, 2nd Quarter 1976, P. 75

A good recent source on the B/W problem is Digital Halftoning, a book
by Robert Ulichney, MIT Press, 1987 (based on his PhD thesis).  Among
other things, it discusses some improvements to our algorithm.

The basic idea is that reducing a 24 bit color to an 8 bit color
introduces some error.  The closest available 8 bit color might have
a certain amount too much red, a certain amount too little green, and
a certain amount too much blue (or whatever other dimensions you are
using for your color space).  The algorithm scans the image.  At each
pixel it chooses the closest 8 bit color and calculates the error it
has thus introduced.  Some fraction of this error is used to adjust
the color of each of those neighboring pixels that have not been
processed yet.  E.g. if the 8 bit color is too red, reduce the red
value of the neighboring pixels.

Heckert's article also discusses how to choose the specific 256 colors
to use for the 8 bit picture (he assumes you have an 8 bit -> 24 bit
color map in your display), and how to efficiently find the closest
color in this set to any given 24 bit color.

I believe Heckert is at Pixar now.  Perhaps he can provide the code,
although it should not be hard to rewrite it yourself.  Also, Paul
Roetling at Xerox's labs in Webster (Mass??) has been working on
similar things.  I can provide the code for the B/W version, with the
standard disclaimer that "the secretary will disavow any knowledge
...".  It is in C, runs on Suns and should run on anything.

I do not know what is used in NeWS, but the B/W images I've seen do
look as if they were produced by our algorithm.  I'd be curious to
know what method they use, since it seems to run very fast.
-- 
					Lou Steinberg

uucp:   {pretty much any major site}!rutgers!aramis.rutgers.edu!lou 
arpa:   lou@aramis.rutgers.edu