[magick-developers] about ImageMagick's dithering on a Hilbert-Peano curve

[Sam Hocevar]

On Thu, Aug 07, 2008, duc.sequere.aut.de.via.decede at imagemagick.org wrote:
> >  Anyway, attached is a serpentine Floyd-Steinberg implementation.
> 
> The mailing list does not accept attachments, instead e-mail it directly
> to this address.
> 
> ImageMagick was originally based on a Floyd-Steinberg implementation
> but in our testing we found the Hilbert curve method gave a more
> visually pleasing result among a set of test images when we compared
> the two methods.  Our testing method was to present a set of 25 images
> side by side (one the original and one dithered with either Hilbert
> or Floyd-Steinberg).  The Hilbert dithering was choosen a majority of
> the time.  Its been about 10 years, so we will revisit the issue when
> we receive your patch.

   I'm pretty surprised. Do you remember what quantisation method was
used with these dithering tests? Here is a side-by-side comparison of
the Hilbert and Floyd-Steinberg methods using "convert src.png -map
pattern:gray50 dest.png" with and without my patch from yesterday:
http://zoy.org/~sam/imagemagick-dithering.png

   So far all the tests I have done with Hilbert curve dithering were
disappointing quality-wise (and believe me, I have tried very hard to
improve on the idea). I *think* one of the reasons people may have
preferred Hilbert dithering is the noise it adds to the image, which
appears to better "spread" pixels; it can be seen with the -monochrome
option: http://zoy.org/~sam/imagemagick-dithering2.png where I admit
it's hard to spontaneously elect Floyd-Steinberg: the grey/black
frontiers look too regular.

   If pixel spread is indeed an important subjective quality metric, I
believe more interesting results could be achieved using random noise
at the quantisation step, or by using a bigger ED kernel such as JaJuNi:
            x 7 5
        3 5 7 5 3  / 48
        1 3 5 3 1
   (I can provide code for this if anyone's interested, it's easily
built on top of the F-S patch)

Cheers,
-- 
Sam.