From albanycs!leah:rsb584 Sat Jan 16 11:53:34 1988 Received: by albanycs.albany.edu (5.54/4.8) id AA27270; Sat, 16 Jan 88 11:43:47 EST Date: Sat, 16 Jan 88 11:43:44 EST From: albanycs!leah:rsb584 ( Raymond S Brand) Received: by leah.Albany.EDU (5.58/1.1) id AA28020; Sat, 16 Jan 88 11:43:44 EST Message-Id: <8801161643.AA28020@leah.Albany.EDU> To: albanycs:beowulf!rsbx >From awpaeth@watcgl.waterloo.edu Mon Jan 11 17:52:04 1988 Path: leah!uwmcsd1!bbn!rochester!udel!gatech!ufcsv!codas!burl!clyde!watmath!watcgl!awpaeth From: awpaeth@watcgl.waterloo.edu (Alan W. Paeth) Newsgroups: comp.graphics Subject: Floyd-Steinberg Notes Keywords: dither Message-ID: <2886@watcgl.waterloo.edu> Date: 11 Jan 88 22:52:04 GMT References: <3703@ames.arpa> <2741@masscomp.UUCP> <2709@aramis.rutgers.edu> Reply-To: awpaeth@watcgl.waterloo.edu (Alan W. Paeth) Distribution: na Organization: U. of Waterloo, Ontario Lines: 74 In article <2709@aramis.rutgers.edu> (Lou Steinberg) writes: > >I should point out that the actual fractions we used were, assuming >you are at X, moving left to right: > > X 7/16 > 3/16 5/16 1/16 > >Note that the error goes to four neighbors, not three. I think this >will probably do better (at least for black and white)... It does noticeably better. I implemented both on the Alto (606x808 one-bit monochromatic display, think Macintosh) for a Smalltalk page layout system at Xerox in the late 70's. The *true* 4-way algorithm gave "crisper" images with a better contrast range and edge definition, and easily justifies the error pass to the fourth neighbor. The additional computing can be minimized by keeping the errors to be written to the next scan line in three registers, and then using some clever loop unrolling is used so that only one read/write access to the error array need occur (this array maintains the error for the next consecutive scanline). The remaining code is the inter-register shuffling of the error fractions. As someone else pointed out, bit shifting can be used to generate the error values, but it is *VERY* important that the distributed fractions sum to one exactly. As a non-intuitive example: (x/2)+(x/2) is not equal to x, for x odd, using integer math (whether you shift or divide, round or chop). A proper implementation would form the values as "x/2" and "x-(x/2)". Failing this, there is a potential error in the LSB. This is worse than just some imprecision in any single pixel. As this error continues to accumulate, it can eventually bias a pixel to become "whiter than white", so that even a fully-white pixel fails to remove this bogus white error. A typical symptom is diagonal streaking away from fully white objects. A less-severe problem is that shifting of negative values is not the same as division by powers of two, leading to some asymmetries in imaging largely black vs white scenes, but if proper accounting of the error is done, this does not give rise to spatial errors. When table lookup is not expensive, four error tables can be precomputed, and properly computed values placed in each table. A fully table driven system require no multiplies or divides, and can additionally perform the algorithm as described in my last posting, can use Heckbert's method, perform tone reproduction curve correction, etc., all in one imaging pass. >...I've not tried it with color. It works beautifully. As with b/w, there must be output pixels as bright and dark as the max and minimum values in the scene, or the "spill-overflow" described above occurs. These bounds must occur independently for each color component, to allow the error to be reduced simultaneously for each primary. This implies that at least eight output pixels (the corners of the color cube -- the bounding rectangle for all candidate input pixels) must be available on output to avoid any spatial spill-over. Our lab has used such a Floyd-Steinbert IMaging tool to map 24bit RGB into 3 bits, which were then packed both spatially and by planes into a 2048x2048x32 Adage framebuffer, which allowed us about 20 seconds (at 15Hz) zoom-pan-scroll animation to preview scenes from a ray-tracing feature film, prior to an expensive production run. I mention all this because one noticible visual artifact in "screening" the movie was the scintillation of the "noise" bits during previewing, when moving temporally through frames. I tried a few cuts at an extended 3D Floyd-Steinber error diffusion algorithm which would additionally pass errors onto the same (x,y) pixel one frame forward in *time*, in an effort to reduce this blinking effect. I am quite interested to hear if anyone else has explored such an extension to the dimensionality of error diffusion. I'm convinced that there is a lot of good milage left in the Floyd-Steinberg approach (I consider it a larger topic than merely any one algorithm), and am interested in receiving further comments. /Alan Paeth Computer Graphics Laboratory University of Waterloo