Sam Hocevar on wrote...
| On Thu, Aug 07, 2008, [EMAIL PROTECTED] wrote:
| > > Anyway, attached is a serpentine Floyd-Steinberg implementation.
| >
| > 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
|
That is what I would expect. The better handling of a hilbert curve dither is
however in small changes when colors are close to the the original colors.
In a ditherly dithering situation a FS style dither does appear better.
However
1/ Your patch just completely replaces the Hilbert Curve.
I would have prefered to allow the user a choice.
That in turn would, also allow for other 'color map' dithering
methods, especially other error spreading methods.
It also may allow for a future colormaped ordered dither, if I can
even get information on how to provide this.
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....
And my discussions in IM examples will need to be modified.
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 would still prefer to have BOTH, as it then means IM has expanded
functionality, with a user choice to change the default (whichever it
is).
That is a choice of None, FS (Floyd-Steinberg), or Hilbert (Riemersma)
| 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.
|
And I am sure you are right about that. But the psuedo-randomness also
means a little more clumping, but not greatly.
That is whay I recommend BOTH be available.
| 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)
|
Expecially is both becomes available.
Lets first intergrate the two dithers, then add varients.
| On Fri, Aug 08, 2008, Anthony Thyssen wrote:
| > Of course, It would be better to implement BOTH, and then let the user
| > decide rather than just replacing one for another.
|
| That seems like a very reasonable
|
| > The most important thing being that a remainer method of distribution be
| > used, so that any integer rounding is taken into account. Your patch
| > does not seem to take that into account. though that is also probably
| > easily fixed.
|
| Yes. I was wary of propagating 100% of the error because I did not
| know how the quantiser would react (I have seen ImageMagick choose weird
| colours when dealing with restrictive palettes).
|
Yes E-Dither Pixel Speckling, where near colors slowly build up the
error until it reaches enough to select the next available (and very
distant) color.
See E-Dither Pixel Speckling
http://www.imagemagick.org/Usage/quantize/#dither_speckle
| But after thinking more
| about it, I think it would do no harm. I'll update the patch.
|
It may be better at this point to send the whole file.
I am sure either I or Cristy can add a dither selection option
and make the old +/-dither setting do the basic switch for the new
option for backward compatibility.
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.
Simularly in...
http://www.imagemagick.org/Usage/quantize/#colors
convert colorwheel.png -colors 64 colors_64.gif
The first two lines has a random set of colors.
It is not the only image to show this problem along the top fir rows of
pixels, but it is the most pronounced example.
| > Then again there is a variety of ways of distributing the error
| > than just the Floyd-Steinberg method. It was just the first, and in
| > many papers was not regarded as the best of this type.
|
| True (though I have shown in a recent paper that it was actually one
| of the best of this type). I have also collected and implemented a lot
| of different error diffusion methods for testing purposes, you may have
| a look at them here: <http://libcaca.zoy.org/study/part3.html>. If you
| believe one of them might be interesting for ImageMagick, let me know, I
| should be able to provide reasonable patches for most of them.
|
Thanks. I'll take a look.
Anthony Thyssen ( System Programmer ) <[EMAIL PROTECTED]>
-----------------------------------------------------------------------------
How many programmers does it take to change a light bulb?
None. It's a hardware problem.
-----------------------------------------------------------------------------
Anthony's Home is his Castle http://www.cit.gu.edu.au/~anthony/
_______________________________________________
Magick-developers mailing list
Magick-developers@imagemagick.org
http://studio.imagemagick.org/mailman/listinfo/magick-developers
