Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucsd!hub.ucsb.edu!tweedledee!steve
From: steve@tweedledee.uucp (Steve Trainoff)
Newsgroups: comp.lang.postscript
Subject: Re: Halftoning Algorithm
Message-ID: <7344@hub.ucsb.edu>
Date: 21 Nov 90 22:52:17 GMT
References: <225043@<1990Nov18> <49400002@primerd> <1713@chinacat.Unicom.COM> <1504@cluster.cs.su.oz.au>
Sender: news@hub.ucsb.edu
Reply-To: steve@tweedledee.ucsb.edu (Steve Trainoff)
Organization: University of California at Santa Barbara, Physics program
Lines: 49

In article <1504@cluster.cs.su.oz.au> jaa@cluster.cs.su.oz (James Ashton) writes:
>
>Dithering algorithms fall into two main categories:  clustered dot and
>distributed dot (these may not be the correct terms but you get the
>idea).  Postscript uses the clustered algorithm - all the black dots
>within each small rectangle are clustered together into a blob.  FS
>distributes the dots around so that in areas less than 50% black, the
>black dots are usually isolated from other dots.  Implementation
>requires generating the whole image at some number of bit planes (say
>8) and then converting it to a one bit deep image only once the image
>is complete.  This has obvious disadvantages for 300 dpi devices and in
>any case, FS output at 300dpi is going to look strange because the
>isolated dots are not well formed.  You'll need to carefully choose the
>transfer function to get it to look good.  A brief description of the
>algorithm follows.
> [... Good explanation of FS algorithim deleted ]

This is correct but there is another more pressing problem with using
FS as a halftoning algorithm that comes from the materials properties
of xerographic print drums.  FS and related "distributed dot"
algorithms require the printer to be able to print isolated dots that
are one pixel wide.  When one specifies a laser printer as having a
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"
..STeve

------------------------------------
Insert pity maxim here...