Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!apple!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!mcsun!unido!fauern!fauern!eckert
From: eckert@medusa.informatik.uni-erlangen.de (Toerless Eckert)
Newsgroups: comp.lang.postscript
Subject: Re: Halftoning Algorithm
Message-ID: <3273@medusa.informatik.uni-erlangen.de>
Date: 22 Nov 90 19:47:04 GMT
References: <7344@hub.ucsb.edu>
Organization: CSD, University of Erlangen, W-Germany
Lines: 56

From article <7344@hub.ucsb.edu>, by steve@tweedledee.uucp (Steve Trainoff):
> In article <1504@cluster.cs.su.oz.au> jaa@cluster.cs.su.oz (James Ashton) writes:
>>
> resolution of 300 dpi, this refers to the addressability of the page,
> not the size of the smallest dot.  You can turn the laser on and off
> in increments of 1/300th of an inch but you can not print a dot that
> is only 1/300 of an inch wide.  Try printing a 150dpi checkerboard
> sometime.  You usually get a completely blank page or some smeary
> grey.  This is because the coating on the drum can not support
> discharging such a small region reliablilty.
> 
> The "clustered algorithms" (or regular graphics such as lines or
> characters) are not affected by this problem since they rely on
> large dots or lines whose size can be changed in fine increments.
> 
> In short, the FS algorithm works best on displays like CRT's or inkjet
> printers that don't have problems turning on single pixels.
> 
> One problem with the FS algorithm is that it creates artifacts that cause
> objectionable mottling on short length scales.  You can reduce these
> patterns considerably by making the algorithm nondeterministic,
> using what is called a random dither.  Simply turn on pixels with the
> probability equal to the intensity at that point.  Then propogate the
> error to the neighboring pixels in the same way as before.  The pure
> random dither with no error propogation is a real dog but with FS it
> is really nice.  By the way, FS is also known as "error diffusion"

I recalled the notion "error distribution" for FS, but anyway the above
statements are correct to my experiences, but:

- The problem of the pixels not being equal in size to the raster
  can be solved by changing the transfer function. This has of course
  to be optimized for every printer (or at least for every kind of printer).
- FS is just one possible algorithm to approach the problem of increasing
  spatial resolution of grayscale imaging on binary output devices. The
  other dominant king of algorithms is "ordered dithering", which is
  an image independent process (FS is image dependant).
- Postscript's halftoning is well compatible to "ordered dithering", i.e.:
  it is a superset of "ordered dithering". Ordered dithering may well be
  used to obtain greater resolution rendering compared to the standard
  spot function. Again you'll have to change the transfer function
  to get the gray values right. 
- At resolutions greater than 200dpi (in my experience) the advantage
  of FS against "ordered dither" wears off. At lower resolutions the
  patterns of "ordered dither" are more obvious than those of FS.
- Conclusion: if you need to render images on low resolution (300dpi)
  printers with more spatial resolution than the standard dot function
  of postscript, use ordered dither. It can be done simply by
  redefining the spot function and the transfer function.
  (if you want to implement FS in your laserprinter, either get sources
  for postscript, or learn 68000 assembler ;-))

-- 

Toerless Eckert          | /C=de/A=dbp/P=uni-erlangen/OU=informatik/S=eckert
V.4: Noah's ark of Unix  | X.400 ^ Internet> eckert@informatik.uni-erlangen.de