inconsistency in comparing bmp files

[Antosha]

-> convert rose: -type GrayScale rose.bmp
-> convert rose: -type GrayScale +dither -treedepth 8 -colors 256 rose2.bmp
-> compare -metric mse rose.bmp rose2.bmp qq.bmp
0

Oh yes!!! It works. Thanks.

PS
Now why does it not say that in the documentation:
http://www.imagemagick.org/Usage/formats/#bmp

This should be mentioned in the description of the colors argument:
http://www.imagemagick.org/script/comma ... php#colors

BTW
1)Why is dithering applied anyway? (The system should not think that it is smarter then the user, so if i ask to reduce the number of colors -- it should do just that, nothing else -- do you agree?)

2)Why does dithering ruin the image? If all the colors of an image are found in the palette, why should the dithering process destroy some of the colors and reduce the palette? Shouldn't it keep as many of the original image colors untouched?

[magick]

We have a comprehensive discussion of the color quantization and dithering here: http://www.imagemagick.org/Usage/quantize/. If you find any concepts missing from that discussion, send Anthony e-mail and he will attend to the omission.

[Antosha]

2)Why does dithering ruin the image? If all the colors of an image are found in the palette, why should the dithering process destroy some of the colors and reduce the palette? Shouldn't it keep as many of the original image colors untouched?

[magick]

We're talking about default values here. ImageMagick, by default, sets the color reduction algorithm to reasonable values. The user is free to change them. The settings include # of colors, tree depth (1-8), dithering, and colorspace.

> If all the colors of an image are found in the palette

Determining that a truecolor image has 256 colors or less and therefore no dithering is necessary is expensive. Instead we let the user decide how the color reduction algorithm should behave. You may not agree that we choose the best default values but like we said-- you can change them with the command line options.

[Antosha]

> If all the colors of an image are found in the palette

Determining that a truecolor image has 256 colors or less and therefore no dithering is necessary is expensive. Instead we let the user decide how the color reduction algorithm should behave. You may not agree that we choose the best default values but like we said-- you can change them with the command line options.

I understand. I am asking a different thing.
Dithering is used to reproduce colors of an image that are not present in the palette.
Correct?
Then why does the dithering process change the image pixel values, that are actually present in the palette? Why does it decide to change the pixel value, when it can directly use the index from the palette? Isn't it supposed to change pixel values if only some neighbouring pixel value is not in the palette?

[magick]

Its been a while since we have visited the color reduction algorithm. You are welcome to determine exactly how the algorithm works by downloading the source and reviewing magick/quantize.c. If you improve the algorithm, post your patches here and we will consider getting them into the ImageMagick distribution.

[Antosha]

Its been a while since we have visited the color reduction algorithm. You are welcome to determine exactly how the algorithm works by downloading the source and reviewing magick/quantize.c. If you improve the algorithm, post your patches here and we will consider getting them into the ImageMagick distribution.

You mean dithering? Cause i've checked the color reduction algorithm (the exact file you mentioned), and everything up to the dithering process is OK. So, i see a problem with the dithering process: it gets an image with a proper palette (all image colors are in the palette) and after that the number of colors in the palette is reduced.

If you improve the algorithm, post your patches here and we will consider getting them into the ImageMagick distribution.

Ye i can try it. Are there any project files (like for the Kdeveloper, or whatever) available, to simplify the debugging process? Or do i have to create one myself?

[magick]

You'll need to create a KDeveloper project yourself. We just configure / make and use valgrind to prevent memory problems.

[magick]

The most promising solution for the problem is to add GrayscalePalette as an image type. The patch will be available sometime tomorrow as ImageMagick 6.4.0-11 Beta.

[Antosha]

The most promising solution for the problem is to add GrayscalePalette as an image type

Ye, but i still think that the dithering process should not change a single pixel image value, if all of the values are in the palette.

[magick]

In the mean-time we added a patch to ImageMagick 6.4.0-11 Beta such that

• convert rose: -type GrayScale rose.bmp
  convert rose: -type GrayScale -colors 256 rose2.bmp
  compare -metric mse rose.bmp rose2.bmp qq.bmp

returns an MSE of 0 as expected.

[Antosha]

I've found the "error". I has to do with the CacheShift define, that is it has to do with the cache. It is set to 2. I replaced the 2 with 0.

The ditherer caches the colors, so that it does not have to find the closest color for the same color twice. But, to be able to cache all possible colors, that is so that it can create a array of all possible colors in memory, it discard two least significant bits.

Code: Select all

i=(long) ((ScaleQuantumToChar(RoundToQuantum(pixel.red)) >> CacheShift) |
        (ScaleQuantumToChar(RoundToQuantum(pixel.green)) >> CacheShift) << 8/*6*/ |
        (ScaleQuantumToChar(RoundToQuantum(pixel.blue)) >> CacheShift) << 16/*12*/);

The code in comments /**/ is what was there before my modification.
I am not using the alpha channel, therefore i was able to modify the code, so that all bits are used. In this case the dithering is done properly.

Of course, at the moment this is a hack(It will not work with the alpha channel.)
To do this properly, i would need to know, is dithering the only one which uses the cache?
Maybe it should be replaced by a bucket structure, instead of a linear ...
Well i have to think this over.

ps.
To make this work,
the cache allocation should be done like this:

Code: Select all

length=(size_t) (1UL << (3/*4*/*(8-CacheShift)));

and

Code: Select all

#define CacheShift  0/*2*/

And the code snippet above.
It will not work with a alpha channel.

[magick]

Dithering distributes error. If no error is expected, dithering should not be performed. The best solution is to automatically turn off dithering if the number of unique colors in the image is less than the maximum number of colors specified.

[Antosha]

The best solution is to automatically turn off dithering if the number of unique colors in the image is less than the maximum number of colors specified.

Yes, this is needed in any case.