Resource Library: Graphics/graphics-16000.iso/formats/gif/floyd.txt

Internet Message Format | 1988-03-21 | 4KB

From: [e-mail] (Alan W. Paeth)
Subject: Floyd-Steinberg Notes
Date: 11 Jan 88 22:52:04 GMT
In article <[e-mail]> (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