schwarze@isa.de (Jochen Schwarze) (11/17/90)
I am wondering how the postscript halftoning algorithm works. It seems
to be much more than simply painting one halftone dot after the other.
Rather than varying dot size in proportion to gray values the dot
shape seems to change according the gray values of the adjacent
pixels. I've studied Digital Halftoning by R. Ulichney, but I couldn't
find references pointing in that direction.
Can anybody enlighten me? Or is this a proprietary and/or patented
and/or secret technique by Adobe?
Thanks.
--
Jochen Schwarze Domain: schwarze@isa.de
ISA GmbH, Stuttgart, West Germany UUCP: schwarze@isaak.uucp
Bang: ...!uunet!unido!isaak!schwarzenelson@melodian.cs.uiuc.edu (Taed Nelson) (11/19/90)
If you don't get other responses, I can go into more detail... Essentially, it uses a thing called the "spot function" which gives an ordering of the pixels in an area around the nearest dot of the halftoning grid. Imagine a 300dpi printer and a 30dpi halftoning screen at 0 degrees (look in the red book if you don't see what I mean). That means that each halftoning dot is responsible for a 10 x 10 area, or 100 pixels (I picked those numbers to work out nice; the default grid is usually 53dpi at 45 degrees). The spot function orders the 100 pixels so that the ones closest to the dot have a value of 0 and the ones in the corners have a value of 1, ie the distance function. It then asks what shade of gray you want. Say 87%. It then colors 87% of those pixels, in increasing order, black. Thus a big halftone dot. If you said 23%, it would be a small halftone dot. Note that if we reversed the spot function so the 1 values were in the center and the 0 were farthest away, we would NOT get an inverse of the same value (as I thought before I understood it), but 87% would give you a small white dot (using "white halftoning"), and not the 13% gray that you might expect. The size of the screen and the angle give you the banding effects that you see if you print a postScript rainbow. Higher screen values give you much nicer grays, but much larger banding effects. This is due to the fact that at, say, a 150dpi halftone screen, each dot is only for a 2 x 2 pixel area, and thus the only values are 0%, 25%, 50%, 75%, and 100% -- any other value of gray will be represented as one of these, thus giving large bands. But it does give very crisp (not dotty) grays...
philip@beeblebrox.dle.dg.com (Philip Gladstone) (11/20/90)
Can someone explain if it would be possible to add (say) Floyd-Steinberg to a Postscript printer to provide greyscale support rather than halftoning via a screen? My experiments in printing greyscale images using F-S look *really* nice although you have to tune various aspects of the algorithm for each particular printer. [It is also really slow as I compute each device pixel on the host and then squirt it down a 9k6 bps line to the printer!] It is unclear if it would go any faster if run on the printer itself (if written in postscript) as it involves quite a lot of manipulation for each pixel. -- Philip Gladstone Development Lab Europe Data General, Cambridge England. +44 223-67600
CXT105@psuvm.psu.edu (Christopher Tate) (11/20/90)
[Person asks about Floyd-Steinberg dithering as a PostScript screen function]
Does anyone have code for doing this? I'd really appreciate having it!
-------
Christopher Tate | I hate writing, and I hate statistics,
| but most of all I hate writing about
cxt105@psuvm.psu.edu | statistics. I'd rather go to the
...!psuvax1!psuvm.bitnet!cxt105 | dentist; at least there you get to spit.
cxt105@psuvm.bitnet | - Ed Sewellchoinski@primerd.prime.com (11/21/90)
>[Person asks about Floyd-Steinberg dithering as a PostScript screen function] > >Does anyone have code for doing this? I'd really appreciate having it! Ditto here. I have played with FS dithering by hand (dithering on the computer and running it through IMAGE), but if a version was available where I could dither ath the 300dpi level would be great!. /============================================================================\ |Burton Choinski choinski@s35.Prime.com| | Prime Computer, Inc. (508) 879-2960 x3233| | Framingham, Ma. 01701 PRIME Computer -- We're still the one| |----------------------------------------------------------------------------| |Disclaimer: Don't even think that these are PRIME's opinions... | \============================================================================/
woody@chinacat.Unicom.COM (Woody Baker @ Eagle Signal) (11/21/90)
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. Cheers Woody
Bruce.Hoult@bbs.actrix.gen.nz (11/21/90)
Pixel-by-pixel dithering will be OK on something like a Linotronic, but will be completely useless on a xerographic printer because of toner spread. It's a big enough problem at the character level, or screen halftoning level, but would be totally unacceptable at the pixel level.
jaa@cs.su.oz (James Ashton) (11/21/90)
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.
steve@tweedledee.uucp (Steve Trainoff) (11/22/90)
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...
eckert@medusa.informatik.uni-erlangen.de (Toerless Eckert) (11/23/90)
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
philip@beeblebrox.dle.dg.com (Philip Gladstone) (11/23/90)
In article <3273@medusa.informatik.uni-erlangen.de> eckert@medusa.informatik.uni-erlangen.de (Toerless Eckert) writes:
eckert> - Conclusion: if you need to render images on low resolution (300dpi)
eckert> printers with more spatial resolution than the standard dot function
eckert> of postscript, use ordered dither. It can be done simply by
eckert> redefining the spot function and the transfer function.
After some private discussions with other netlanders about this, I
don't think that you can redefine the spot and transfer functions to
achieve this. It turns out that in *at least* one implementation of
postscript, the spot function is called during the execution of the
setscreen operator (AND NOT during the display of grey levels), and
the transfer function is called during the execution of the setgrey
operator.
I admit that I have not tested when the transfer function is called
for images -- but I would expect it to be called once for each SOURCE
point.
All this is consistent with reducing the amount of work that the
interpreter has to do (i.e. goes faster).
Of course, all this may be wrong, and I'd be only too pleased to be
contradicted by a piece of postscript posted to the net!
--
Philip Gladstone
Development Lab Europe
Data General, Cambridge
England. +44 223-67600avi@dgp.toronto.edu (Avi Naiman) (11/24/90)
In article <7344@hub.ucsb.edu> steve@tweedledee.ucsb.edu (Steve Trainoff) writes: > In short, the FS algorithm works best on displays like CRT's or inkjet > printers that don't have problems turning on single pixels. Actually, contrary to popular assumptions, CRTs also suffer from this spatial non-linearity. The average intensity of a checkerboard pattern of alternating black and white pixels will usually be darker than the mean of the black and white levels (see, for example, [Mulligan and Stone 89]). In my work, I have found monitors on which the space-averaged (normalized) luminance of a checkerboard is as low as 0.2, rather than the expected 0.5 [Naiman 90]. %L Mulligan and Stone 89 %A Jeffrey B. Mulligan %A Leland S. Stone %T Halftoning Method for the Generation of Motion Stimuli %J Journal of the Optical Society of America A %V 6 %N 8 %D August 1989 %P 1217-1227 %L Naiman 90 %A Avi C. Naiman %T The Use of Grayscale for Improved Character Presentation %D 1990 %C Toronto, Ontario %R Ph. D. Thesis, Department of Computer Science, University of Toronto -- Avi Naiman avi@dgp.toronto.edu
Bruce.Hoult@bbs.actrix.gen.nz (11/26/90)
In article <1990Nov23.134554.24723@jarvis.csri.toronto.edu> avi@dgp.toronto.edu (Avi Naiman) writes: > Actually, contrary to popular assumptions, CRTs also suffer from this > spatial non-linearity. The average intensity of a checkerboard pattern > of alternating black and white pixels will usually be darker than the > mean of the black and white levels (see, for example, [Mulligan and > Stone 89]). In my work, I have found monitors on which the > space-averaged (normalized) luminance of a checkerboard is as low as 0.2, > rather than the expected 0.5 [Naiman 90]. Do you happen to know how bad/good the standard Macintosh b&w display is in this regard?