Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!samsung!munnari.oz.au!metro!cluster!jaa
From: jaa@cs.su.oz (James Ashton)
Newsgroups: comp.lang.postscript
Subject: Re: Halftoning Algorithm
Message-ID: <1504@cluster.cs.su.oz.au>
Date: 21 Nov 90 06:38:40 GMT
References: <225043@<1990Nov18> <49400002@primerd> <1713@chinacat.Unicom.COM>
Sender: news@cluster.cs.su.oz.au
Reply-To: jaa@cluster.cs.su.oz (James Ashton)
Organization: Basser Dept of Computer Science, University of Sydney, Australia
Lines: 61

In article <1713@chinacat.Unicom.COM> woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) writes:
>In article <49400002@primerd>, choinski@primerd.prime.com writes:
>> 
>> >[Person asks about Floyd-Steinberg dithering as a PostScript screen function]
>> >
>> 
>> Ditto here.  I have played with FS dithering by hand (dithering on the
>
>If someone posts the algo, or some application code that does it given 
>a bitmapped image (preferably 'C'), I'm sure we can find a way to do it.
>I personaly don't know what Floyd-Steinberg dithering achieves and how it
>is done.  I've not had any call to know the info, but would be interested,
>so someone post some code.

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.

Each pixel is treated in turn.  The simplest method is to proceed left
to right, top to bottom but better results are achieved using a
serpentine raster:  you alternate between left to right and right to
left as you go from top to bottom.

For each pixel the result is black if the pixel is < 50% and white
otherwise - simple thresholding.  The trick comes when you pass the
error on to neighbouring pixels.  Say the pixel is 30%:  your output is
black - effectively 0% so you have an error of -30% which you attempt
to rectify by adding 30% distributed amongst neighbour pixels not yet
processed.  There are varying distribution ratios but the following
seems to be (to me) the simplest that works well)

		*       7
	3       5       1

You have just processed the pixel at * and are proceeding left to
right, top to bottom.  You add 7/16.30% = 13% to the next pixel on the
right, 3/16.30% = 6% to the next lower left pixel, 5/16.30% = 9% to the
next lower pixel and 1/16.30% = 2% to the next lower right pixel.  When
using a serpentine raster and proceeding right to left, the
distribution is laterally transposed.

FS is great at around 100dpi on your 1 bit deep screen - it is used to
produce 48x48 images of faces that are quite recognisable.  For PS
implementations designed to work on such screens it's probably better
in some applications that halftoning but again, you need to have a
memory intensive multi plane bit map of the imaging area and you have
to have the whole image complete in that bit map before you use FS to
render it onto your 1 bit deep screen.  It's probably not practical or
useful to use it at 300dpi on laser printers.

						James Ashton.