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

[Sam Hocevar]

On Sat, Aug 09, 2008, Anthony Thyssen wrote:

>   1/ Your patch just completely replaces the Hilbert Curve.
> 
>   2/ Cristy has applied your patch directly, and has now started the
>      release of IM v6.4.2-7.  So that will have FS dither, rather than
>      a Hilbret Curve Dither.
> 
>      This has removed the old dither completely (I have saved a copy)
> 
>      It will also mean that every GIF image in IM Examples will on the
>      next update flag as having changed!! Arrrggghhhh....

   Sorry, I really didn't mean it to happen like that. I hope things can
still be sorted out.

>   3/ It is doing direct ratios of the error, with no 'remainer' to
>      add to the last color being updated.  As such its error distribution
>      and rounding errors.
> 
>      See notes in probably one of the best (and oldest) guides..
>         Dithering and Halftoning  "DHALF.TXT"
> 
>   4/ From that text...
>           Floyd and Steinberg carefully chose this filter so that it
>           would produce a checkerboard pattern in areas with intensity
>           of 1/2.
>      Your Serpentine implementation does NOT provide that effect, but
>      produces columns of pixels.

   I disagree here. Since the code is handling RealPixelPacket variables
there is no practical benefit in handling the rounding error. I once
simulated Floyd-Steinberg on a 50% gray 1000000x1000000 image and even
with floats instead of doubles or long doubles the result was a perfect
checkerboard.

   However, there are indeed several problems right now that cause this
issue. First, my patch was modified and the code that was checked in is
now incorrect:

[...]
           pixel.red+=previous[u-v].red-15*previous[u-v].red/16;
           pixel.green+=previous[u-v].red-15*previous[u-v].green/16;
                                      ^^^ should be "green"
           pixel.blue+=previous[u-v].red-15*previous[u-v].blue/16;
                                     ^^^ should be "blue"
           if (IsAssociatedAlpha(image,cube_info) != MagickFalse)
             pixel.opacity+=previous[u-v].red-15*previous[u-v].opacity/16;
                                          ^^^ should be "opacity"
[...]

   Second, I mistakenly assumed that AcquireQuantumMemory would
zero the memory, which it apparently doesn't do. The following code
is therefore required after the AcquireQuantumMemory() call in
FloydSteinbergDither():

      memset(scanlines, 0, 2*sizeof(*scanlines) * image->columns);

   Third, and I am afraid you are never going to see a perfect
checkerboard until this is dealt with, the IM RealPixelPacket values for
a 50% gray pixel are 32639 instead of 32767. Not sure where to fix that.

> Hmmm it has a fault however...
> 
> Compare the results for the IM examples  alpha_dither_monochrome.gif
> (from IM Examples, Quantization and Dithering,
>   Color Quantization and Transparency
>      http://www.imagemagick.org/Usage/quantize/#color_trans
> 
>   convert xc:red xc:yellow xc:green1 xc:cyan xc:blue \
>           +append -filter Cubic -resize 100x100\!  -size 100x100 \
>           gradient: +matte -compose CopyOpacity -composite alpha_gradient.png
> 
>   convert alpha_gradient.png -channel RGBA -separate \
>           \( +clone -monochrome \) +swap +delete \
>           -combine alpha_dither_monochrome.gif
> 
> The dither starts, but then just seems to die about half way through!
> I have attempted to simplify the above example as yet.
> 
> If you can't see the problem, let me know and I'll post you the images.
> and try to simplify the problem.

   I can reproduce the problem, but I don't really know where to look.
It looks like a problem somewhere else: IsAssociatedAlpha() always
returns false here, so the opacity error is never computed.

Cheers,
-- 
Sam.