🚀 go-pugleaf

>Tom_Lane@G.GP.CS.CMU.EDU writes:
>
>>The free JPEG image compression software currently uses traditional
>>Floyd-Steinberg dithering when reducing the number of colors in its output.
>
>>Even with careful coding, F-S dithering is a remarkably expensive
>>proposition... in our current release, dithering *alone* (not counting color
>>selection) takes nearly as much time as JPEG decompression proper.
>
>>If anyone is aware of cheaper dithering techniques that give results as good
>>as F-S, or of implementation tricks to speed up F-S, I'd appreciate hearing
>>about them.
>
>I once made a variant of F-S that was somewhat faster: instead of
>distributing the error to four neighbouring pixels, distribute it to
>only one. The idea is to make the choice of which pixel to distribute
>to random: in the simplest case you randomly choose either the next
>pixel on the same scan-line or the same pixel on the next scan-line.
>You need a fast way to generate random bits, bit a simple
>shift-register method works reasonably well. If you want slightly
>better quality, you randomly choose one of the four pixels that F-S
>would distribute the error to.
>
>The quality is not quite up to the standard of F-S, but nearly so.
>
>	Torben Mogensen (torbenm@diku.dk)

Another alternative is to only propogate error to the next pixel in the path,
but to use a more convoluted path than the standard linear or serpentine scan
that F-S uses.  If you can find a cheap space filling curve to cover your image,
then traversing the image along that curve and propogating error to just the
next pixel produces results that are in many cases better than F-S. (a lot of
the directional artifacts go away).

For more information on this, see :

Cole, "Naive Halftoning", Proceedings of CG International '90, Chua and Kunii eds.
Springer Verlag, 1990  pp 203-222

Witten and Neal "Using Peano Curves for Bilevel display of continuous tone images"
IEEE CG&A, May 1982, pp 47-52

Wyvill and McNaughton, "Three Plus Five Makes Eight, A Simplified Approach to
Halftoning", Scientific Visualisation of Physical Phenomena, Proceedings of CG
International '91, Patrikalakis (ed), Springer Verlag, 1991, pp 379-392.


Craig McNaughton (craig@godzilla.cgl.citri.edu.au)





-- 
Craig McNaughton                  | "If at first you don't succeed, then
craig@godzilla.cgl.citri.edu.au   | just give up and go and watch TV, no
Advanced Computer Graphics Centre | matter whats on."
RMIT, Melbourne, Australia        |	                 Homer J. Simpson

--
Moderated by SCRI Vis <>           Submissions to: graphics@scri1.scri.fsu.edu
Guy, John R. Murray   <> Administrivia to: graphics-request@scri1.scri.fsu.edu