pete@violet.berkeley.edu (Pete Goodeve) (06/26/89)
Can someone tell me how the Floyd-Steinberg dithering algorithm is supposed
to work? [Pointing me to a reference would be great -- I've scanned just
about every book in the computer graphics section of the campus library
without finding ANY reference to "dithering"...] I've been noticing some
real peculiarities with it, and I've finally decided it's the algorithm,
not me.
The trail is complex, but I'll try to keep it brief. My printer is one of
those Tandy CGP-220 (Canon mechanism) inkjets, which I acquired from Vince
Lee, along with an initial version of a 1.3 driver. Its somewhat brain
damaged Trash-80 interface wants Red, Green, and Blue signals rather than
the Yellow, Magenta, Cyan, and Black actually used by the mechanism.
Vince, therefore, wrote his driver as type PCC-BGR. I had to fix it in a
couple of minor ways (mainly the dither threshold was one level off, so I
never got pure white) but otherwise it seemed to work fine. I was using it
that way for many months.
Then last week I bought Deluxe PhotoLab and REALLY started to play with the
system. One of the first things I did was to create a color step-wedge
to see how it printed. The Ordered Dither mode was just fine, but
Floyd-Steinberg was way off. The LIGHTEST shade (solid color or pure
white, according to the strip on the wedge) was not at value 15 as it
should have been, but at 12 AND 13. Levels 14 and 15 were severely
scrawled. As an additional oddity, when I tried to combine F-S and
Grayscale, all I got was solid black.
The essential part of the code -- transfer.c -- is a straightforward
conversion of the Xerox 4020 (Devcon 88) source, with Red, Green, and Blue
pixel values instead of Yellow, Magenta, Cyan, and Black. (And I have to
CLEAR bits in the output buffer, rather than set them, so that White -- all
bits set -- appears where the transfer function is not applied.)
Anyhow, I decided that the F-S algorithm must be expecting YMC pixel values
to work correctly, so I changed the driver type to PCC-YMC -- a matter of
reversing the direction of the comparison against the dither value.
Bingo! Now the F-S step wedge was clear at value 15 and seemed to grade
smoothly down to black.
But wait! Looking closely, I noticed that what should have been pure black
(value 0) was NOT! Full black with all dots filled occurred at values 2
and 3 (BOTH values..); levels 1 and 0 were lighter. And now when I tried
Grayscale, all I got was pure white!
Finally, I decided to make it a full YMCB driver. This changes the COLOR
step-wedge not in the slightest -- full black is still at 2 and 3 --, but
at least I now get output in Grayscale mode. And guess what! That gray
scale is perfect, with solid black at 0, and solid white at 15,15,15!!
So my guess at the moment is that there is something missing in the
Floyd-Steinberg implementation. Or am I missing something? (Or maybe I
missed all this being hashed out before. If so, I apologise.) I don't
have any immediate way of checking on another color printer, but I'll see
if I can locate one. Maybe someone else could check theirs.
Despite these problems, I like F-S dither. Often its randomization gives
better color rendering than ordered dither on my printer, and it's fine for
"Impressionistic" stuff. I can make it work properly simply by using
PhotoLab to shift the "Black" level up a couple of notches. It would be
nice to have the full contrast range available, though...
-- Pete --richard@gryphon.COM (Richard Sexton) (06/26/89)
In article <25763@agate.BERKELEY.EDU> pete@violet.berkeley.edu (Pete Goodeve) writes: >Can someone tell me how the Floyd-Steinberg dithering algorithm is supposed >to work? Sure. It's supposed to place dots in a more or less random (but ordered) pattern over the page so it fools your eye into thinking that the color it sees is not the color of the dots on the page. Hope this helps. --- "And what is the soup de jour" "Oh, thats the soup of the day" Seriously: thw book you want is Digitial Halftoning from MIT Press. -- ``When I try to sleep at night, I can only dream in red'' richard@gryphon.COM decwrl!gryphon!richard gryphon!richard@elroy.jpl.NASA.GOV
papa@pollux.usc.edu (Marco Papa) (06/26/89)
In article <17118@gryphon.COM> richard@gryphon.COM (Richard Sexton) writes: >In article <25763@agate.BERKELEY.EDU> pete@violet.berkeley.edu (Pete Goodeve) writes: >>Can someone tell me how the Floyd-Steinberg dithering algorithm is supposed >>to work? > >Seriously: thw book you want is Digitial Halftoning from MIT Press. Another reference is the chapter on halftoning in David F. Rogers' "Procedural Elements for Computer Graphics", McGrawHill, p. 102-108. If you want (and can get) the original article, this is the reference: Floyd and Steinberg, "An Adaptive Algorithm for Spatial Gray Scale", SID 1975, Int. Symp. Dig. Tech., Pap., pp. 36-37, 1975. Enjoy. -- Marco Papa 'Doc' -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= uucp:...!pollux!papa BIX:papa ARPAnet:pollux!papa@oberon.usc.edu "There's Alpha, Beta, Gamma, Diga and Caligari!" -- Rick Unland -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
daveb@cbmvax.UUCP (Dave Berezowski) (06/27/89)
The current Floyd-Steinberg dithering is the traditional 3-way distribution and suffers from the artifacting you mentioned. I have the algorithm for a much improved 4-way dither (hmm, its around here someplace) but I don't know if it will make it into the next release of the software or not.