Path: utzoo!attcan!uunet!pyrdc!pyrnj!rutgers!aramis.rutgers.edu!bearcat.rutgers.edu!lou From: lou@bearcat.rutgers.edu (Lou Steinberg) Newsgroups: comp.graphics Subject: Re: Floyd-Steinberg Errors: What do I do with them? Message-ID: Date: 21 Jul 88 17:41:46 GMT References: <6506@well.UUCP> <13172@jumbo.dec.com> <252@versatc.UUCP> Organization: Rutgers Univ., New Brunswick, N.J. Lines: 62 In article <252@versatc.UUCP> aden@versatc.UUCP (Michael Aden) writes: > The problem with Floyd-Steinberg (and all the others) when used on scanlines > is a tendency towards "worm tracks", a propagation of error in a coherent direction. I don't believe the problem is "propagation of error in a coherent direction" so much as *lack* of propagation in a coherent direction. To state it more clearly (but less poetically :-), the problem is the existence of two pixels placed such that no error propagates between them, even indirectly. For instance, in raster scan Floyd-Steinberg, using our original 4-neighbor method, no error propagates from a pixel to the pixel one line below and two pixels back, so that when the first pixel turns on there is no way for this to inhibit the other pixel from firing. In a region of constant low brightness, however, the errors tend to build up more or less uniformly, so if the first pixel is on, chances are good the second pixel, not being inhibited, will be on as well, leading to worm tracks at this "knight's move" (one down and two back) orientation. With a serpentine scan, there is no such pattern of points that do not have at least an indirect error propagation path, and worm tracks are not a problem. There are other artifacts, such as apparent lines where a stable pattern (e.g. a checkerboard) suddenly breaks down or where two patterns meet out of phase (e.g. two checkerboards, one shifted a row down). (As a point of credit, the serpentine scan was first suggested by John Roach, one of our grad students, but as far as I know was rediscovered independently by Ulichney, and I think Ulichney was the first to publish it.) > While serpentine helps this, even better would be error propagation along > a non-trivial path, which leads us back to the Peano curve discussion of a few months > back. I never saw a discussion of how to do those fast. Anybody have any hints > they'd like to share? The idea of propagating error along a Peano curve scan path was suggested by Witten and Neal of the University of Calgary in the May 82 Computer Graphics and Applications ("Using Peano Curves for Bilevel Display of Continuous Tone Images"). They only propagate the error forward along the scan, rather than also off to the sides as in error diffusion, and the result is (to my biased eye) not as good. (They had apparently never heard of our method when they published the paper.) I've never seen anyone try a peano curve with error off to the sides. It sounds a bit messy, and I'm dubious that the results would be much better than serpentine scan, but I'd be interested to hear if anyone tries it. Witten and Neal do not actually cover the whole image with one peano curve - they cover a box (e.g. 64x64), and replicate that over the image. Probably you could pre-compute the peano path in the form of a list of offsets (+/- 1 or unchanged for x and y) that take you from one point to the next within the box, so that the extra cost of the scan would not add that much to the whole cost per pixel - and would perhaps be even faster than standard Floyd/Steinberg, since you would not have to compute the fractional errors. On the other hand, if the individual bits of the bi-level version of the picture are packed up into bytes, accessing them in peano order may be pretty expensive. -- Lou Steinberg uucp: {pretty much any major site}!rutgers!aramis.rutgers.edu!lou arpa: lou@aramis.rutgers.edu