Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!mit-eddie!genrad!decvax!ucbvax!hplabs!parcvax!tow
From: tow@parcvax.Xerox.COM (Robert Francis Tow)
Newsgroups: comp.sys.mac
Subject: Re: Looking for Dithering Algorithms
Message-ID: <536@parcvax.Xerox.COM>
Date: Fri, 25-Sep-87 15:53:40 EDT
Article-I.D.: parcvax.536
Posted: Fri Sep 25 15:53:40 1987
Date-Received: Sun, 27-Sep-87 10:31:20 EDT
References: <3320020@hpcid.HP.COM>
Reply-To: tow@parcvax.xerox.com.UUCP (Robert Francis Tow)
Organization: Xerox PARC
Lines: 51
Keywords: dithering halftoning images
Summary: Where to look

In article <3320020@hpcid.HP.COM> cnc@hpcid.HP.COM (Chris Christensen) writes:
>
>I am looking for information about dithering algorithms.
>
>I often see images on the Mac that were dithered with an algorithm with
>which I am unfamiliar.
>
>I am familiar with contrained average (checkerboard like patterns) and 
>pseudo-optical screening (various size dots), but the algorithm I speak
>of looks like it uses a pseudo random screen. It is grainy in apperence
>but has fewer "dithering artifacts" than either of the above algorithms.
>
>For anyone with Hypercard, the picture of the baby in the photo album stack
>uses the algorithm to which I refer.
>
>
>So... anyone know what I am talking about?
>
The Floyd-Steinberg error diffusion method is a better basic method, 
which results in images that do not exhibit posterization. In this class
of algorithms, when a pixel is compared against a threshold value
(which may be varied according to some screening or dithering pattern)
and either set or not set in the output bitmap, the 'error' from this
is distributed to neighboring pixels.  

Error diffusion algorithms tend to produce several artifacts peculiar
to themselves: crystalline-like patterns, ringing at edges, wave like
patterns, and a blurring of the image. There are proprietary versions of 
these algorithms which manage to avoid these (I have myself worked out 
some), but these tend to be closely guarded by scanner and graphics companies.

You will find the basic Floyd-Steinberg error diffusion algorithm
described on pages 104-106 of 'Procedural Elements of Computer Graphics'
by David F. Rogers (MacGraw-Hill, 1985); the original paper is
'An Adaptive Algorithm for Spatial Gray Scale, SID 1975', Int. Symp.
Dig. Tech., Pap., pp. 36-37, 1975, by Floyd and Steinberg.

An excellent reference for halftoning and image processing techniques 
applicable to halftoning and dithering is 'Digital Document Processing', by 
Hsieh S. Hou (John Wiley and Sons, 1983).  Hint: I found some quite
useful starting points here which lead to a vastly improved version
of the error diffusion algorithm.

Rob Tow
Graphics Wizard ("I can call spirits from the vasty deep")
ParcPlace Systems 
2400 Geng Road
Palo Alto CA. 94303
 
ARPANet:    tow@ParcPlace.com 
USENET:     ...!{ucbvax, allegra, seismo, pyramid, decvax}!sun!pplace!tow