rberlin@birdland.sun.com (Rich Berlin) (11/29/90)
Some of the disagreement over whether this is possible may be due to confusion over different dithering algorithms. The Floyd-Steinberg algorithm, as someone mentioned, does error diffusion and as such needs access to the entire image space. The other method suggested was ordered dither, and this indeed can be implemented using the PostScript operators setscreen and settransfer. (It is really setscreen that implements the dither; the transfer function is used to compensate for ink spread etc., i.e. to even out the results.) What makes ordered dither suitable for a PostScript implementation while error diffusion is not possible? The distinction is that the ordered algorithm overlays a threshold matrix over the image and uses that matrix to determine how to color the cells. This is analogous to laying a "screen" over the image, which is what traditional halftoning does. In neither case does the algorithm call for adjusting the values of neighboring pixels, so this technique will work despite the fact that the spot function knows nothing about the image being rendered. (For more info, see Foley and Van Dam, 1st ed. page 600-601.) The materials handed out at the Adobe Developer's conference in June of this year include a simple example of how to feed a threshold matrix to setscreen. (Unfortunately, there's a copyright notice glaring up at me from the bottom of the page, so I don't feel free to publish the example. Perhaps someone at Adobe would be so kind?) PostScript level II, according to the last specification I saw, includes a simpler method of doing ordered dither. My understanding is that support for error diffusion is NOT part of that work, however. -- Rich
eckert@medusa.informatik.uni-erlangen.de (Toerless Eckert) (12/07/90)
From article <RBERLIN.90Nov28104017@birdland.sun.com>, by rberlin@birdland.sun.com (Rich Berlin): > What makes ordered dither suitable for a PostScript implementation > while error diffusion is not possible? The distinction is that the > ordered algorithm overlays a threshold matrix over the image and uses > that matrix to determine how to color the cells. This is analogous to > laying a "screen" over the image, which is what traditional halftoning > does. In neither case does the algorithm call for adjusting the > values of neighboring pixels, so this technique will work despite the > fact that the spot function knows nothing about the image being > rendered. (For more info, see Foley and Van Dam, 1st ed. page > 600-601.) Thanks for explaining, this is exactly what happens. In article <PHILIP.90Nov23100713@beeblebrox.dle.dg.com> Philip Gladstone writes: > 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. See above. You are correct to notice how setscreen works. Imagine how slow it would be if it is executed every time the screen is used. There is surely no postscript interpreter that calls the setscreen operator on other times than 'set.*screen' or '.*restore'. The same is true for the transfer function, but in both cases, the defined postscript functions (spot function and transfer function) are only scanned, and the results of this scanning (i.e.: kind of bitmap or transfer table) is used later for the real imaging process. > The materials handed out at the Adobe Developer's conference in June > of this year include a simple example of how to feed a threshold > matrix to setscreen. (Unfortunately, there's a copyright notice > glaring up at me from the bottom of the page, so I don't feel free to > publish the example. Perhaps someone at Adobe would be so kind?) Really, there is something like an Adobe developer ??? I really would like to start adobe bashing, given that they proved to be very incooperative to use once ago, but anyway, here is my ordered dither screen, that i wrote some time ago: %!PS % % Ordered-Dither spot function definitions for postscript. % Given that the setscreen funtion of postscript is quite flexible, % it was easy to define a funtion which, when given to the % set(color)screen operator will define the screen as an ordered dither % screen. % % The basic advantage of using dithering is the higher spatial resolution % compared to dot type spot functions. The negative effects are the tendency % of dithering to produce visible patterns. % % The given code does not use the standard square-dither matrices, but % magic-square matrices. These matrices results in patterns that are not % that visible to human eye, than the patterns produced by the standard % ones. % % Toerless Eckert 1990 (eckert@informatik.uni-erlangen.de) /dither-dict 50 dict def dither-dict begin /resolution 72 0 matrix defaultmatrix dtransform pop def % % This gets called from set(color)screen, through the embodying % procedure created by createditherspot. % % x y matrix size <ditherspot> matrix[x',y'] /ditherspot { dither-dict begin /size exch def /dithmat exch def /y exch def /x exch def dithmat x 1 add 2 div size mul cvi y 1 add 2 div size mul cvi size mul add get size div size div end } def % % matrix <createditherspot> freq angle spot % /createditherspot { dither-dict begin /dithmat exch def /l dithmat length def /dithmat dithmat l array copy def /sqrtl l sqrt cvi def l sqrtl dup mul ne { /createditherspot errordict /rangecheck get exec } if resolution sqrtl div 0 [ dithmat sqrtl /ditherspot load aload pop ] cvx end } def % square a matrix % % matrix replmat <relmatrix> large-matrix % /sqrdither { dither-dict begin /repmat exch def /smallmat exch def /size smallmat length sqrt cvi def repmat length 4 ne size dup mul smallmat length ne or { /sqrdither errordict /rangecheck get exec } if /largemat size dup mul 4 mul array def /lsize size 2 mul def 0 1 3 { /part exch def /delta [ 0 size size lsize mul dup size add ] part get def /incr repmat part get def 0 1 size 1 sub { /y exch def 0 1 size 1 sub { /x exch def /val smallmat x y size mul add get def largemat x y lsize mul add delta add val 4 mul incr add put } for } for } for largemat end } def % The basic replication pattern. If you are using a color postscript % engine, it is useful to rotate the values of this matrix, to % generate different patterns for the colorplanes. /rep [ 0 3 2 1] def % dither matrices of the indicated size. This are the % rectangular versions. /rect-dither4 rep def /rect-dither16 rep rep sqrdither def /rect-dither64 rect-dither16 rep sqrdither def % One with a magic square. /magic-dither16 [0 6 9 15 11 13 2 4 7 1 14 8 12 10 5 3] def % Most laser printers don't print dots of the exact size of the 300/400 dpi % raster, but dots that are larger and even not fully square. % For dithering, where a grayscale vaule is represented by a pattern, % this results in the patterns being too dark. This effect can easily % eliminated by a simple transfer function which maps the % grayscale to the lighter end. % maybe this one... { sqrt } settransfer % set screen with dither matrices .. % for monochrome postscript printer magic-dither16 [0 3 2 1] sqrdither createditherspot setscreen % for color postscript printer % magic-dither16 [0 3 2 1] sqrdither createditherspot % magic-dither16 [1 0 3 2] sqrdither createditherspot % magic-dither16 [2 1 0 3] sqrdither createditherspot % magic-dither16 [3 2 1 0] sqrdither createditherspot % setcolorscreen end -- Toerless Eckert | /C=de/A=dbp/P=uni-erlangen/OU=informatik/S=eckert 50GB/M limit: NO MERCY | X.400 ^ Internet> eckert@informatik.uni-erlangen.de