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

[Anthony Thyssen]

Sam Hocevar on  wrote...
| On Sat, Aug 09, 2008, Anthony Thyssen wrote:
|
| >      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.
|
That is okay.  Any change in the quantization or dithering causes me
this problem,  I have been trying to develop a 'test' that will compare
two GIF images and inform me then they differ, but not due to dithering
effects.  Not a lot of luck with this as yet, as it is a very fine line.


But this is becides that point. Which was that BOTH dithers should be
made available.

Actually as  "-dither" is a extremely rare option, it could probably be
directly given an 'what dither' argument without upsetting too many people.


| >   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.
|
Was that test with BOTH a odd and even number of pixels wide image?

| 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);
|
It looks like Crisy has added this to your replacement...

   ResetMagickMemory(scanlines,0,2*sizeof(*scanlines));

No indication of any move to give an argument to the rarely use option,
"-dither" so that BOTH forms of dither can be used.

|    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.
|
Ues I reported this before.

It is caused by  Gray50  being defined as  #7F7F7F
which expands to a non 50% 16 bit vaue of  #7F7F7F7F7F7F
Instead of a true 50% gray of  #7FFF7FFF7FFF
You may like to check your test code...

Hmmm... If you use the color   gray(50%)   which is a recently added
color function.  you get...  #800080008000

    convert xc:'gray(50%)' -depth 16 txt:
    # ImageMagick pixel enumeration: 1,1,65535,rgb
    0,0: (32768,32768,32768)  #800080008000  grey50

UPDATE:  Quick test show  gray50 is also defined as "rgb(50%,50%,50%)"
the equivelent to "gray(50%)", so your tests may work better now.

Hmmmm testing...
   convert -size 100x100 xc:'#7FFF7FFF7FFF' \
           -size 1x2 -map gradient: -scale 500% x:
and
   convert -size 100x100 xc:'#800080008000' \
           -size 1x2 -map gradient: -scale 500% x:

produces a tiling of 2 pixel high columns, rather than a checkerboard.

while
   convert -size 101x101 xc:'#7FFF7FFF7FFF' \
           -size 1x2 -map gradient: -scale 500% x:
and
   convert -size 101x101 xc:'#800080008000' \
           -size 1x2 -map gradient: -scale 500% x:

Produces a mix of 2 pixel columns with checker board rows interspersed.

All of them naturally had some inital distrubence for the first couple
of rows.


| > 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.
|
The image "alpha_gradient.png"  is being seperated into -separate
channel images.  The alpha channel image (a linear gradient) is then
being -monochrome dithered, be fore the channel images are being
-combine back into a original image.

That is IsAssociatedAlpha() IS always false.

The dither aspect should be equivelent to...
    convert -size 100x100 gradient: -monochrome  alpha_channel.png

And that works fine.  But when it is part of the larger image processing
sequence, it stuffs up...

This should be the equivelent to the last command...

   convert alpha_gradient.png -channel RGBA -separate \
        \( -size 100x100 gradient: -negate -monochrome \) +swap +delete \
        -combine alpha_dither_monochrome.gif

And that works correctly.   Definatally some interaction when dithering
a 'channel' image is causing the dither to 'just stop'  halfway through
without any indication of an error.

However i am also getting "Floating point exception" when I run "display"
of the resulting GIF images, or if I add "-montior",  so something may
be wrong elsewhere.


  Anthony Thyssen ( System Programmer )    <A.Thyssen at griffith.edu.au>
 -----------------------------------------------------------------------------
   The nice thing about machines, Roger thought, was that they 
   couldn't be impressed by rank.   They took you as you were.
                                 --- Anne McCaffrey,  "Damia's Children"
 -----------------------------------------------------------------------------
     Anthony's Home is his Castle     http://www.cit.gu.edu.au/~anthony/