very slow +dither on IM 6.6.7.7 Q16

[fmw42]

I am seeing quite slow times for +dither in the following command compared to when it is removed:





time convert "CWLBCRMU.jpg" +dither -remap netscape: CWLBCRMU_tmp.mpc

real 0m7.627s
user 0m7.232s
sys 0m0.057s
freds-mac-mini:~ fred$ time convert "CWLBCRMU.jpg" -remap netscape: CWLBCRMU_tmp.mpc

real 0m1.984s
user 0m1.765s
sys 0m0.056s


I am reporting this as it seems excessive for no dither. Furthermore, a client reported to me about the speed of a script I wrote for them using the above (like) command when run from IM 6.6.7-7 (about 7 seconds) compared to IM 6.5.9-3 (about 2 seconds).

Thanks

Fred

[magick]

See viewtopic.php?f=3&t=17623. Generating a uniform colorspace required searching higher in the color cube tree. Increasing the search space slows down the dithering process. We considered this trade off years ago and decided on less accurate colors for better performance. However, the less accurate colors caused a number of problems reports to Anthony.

[fmw42]

See viewtopic.php?f=3&t=17623. Generating a uniform colorspace required searching higher in the color cube tree. Increasing the search space slows down the dithering process. We considered this trade off years ago and decided on less accurate colors for better performance. However, the less accurate colors caused a number of problems reports to Anthony.

Sorry, I don't see the connection of what you are saying to the dither issue, especially as +dither means no dithering, if I am not mistaken.


1) At what release was this change made? Is this a change in v6.6.7.7 per:

2011-02-08 6.6.7-7 Cristy <quetzlzacatenango@image...>
Posterize now distributes color uniformally (reference viewtopic.php?f=3&t=17623).



2) Is there any workaround for my client other than backing down to an earlier version and if that is it, what version per the above?


3) In my application I do:

convert someimage +dither -remap netscape: tmp.mpc

then I get the histogram from which I find the 6 most frequent colors.

If I remove the +dither, will that change the histogram or at least the 6 most frequent colors?

[magick]

The larger search space applies to both dithering and non-dithering. You can always speed up color reduction with the -treedepth option. Try -treedepth 4, for example. In the mean-time we're looking at using OpenMP to speed up color reduction.

[fmw42]

The larger search space applies to both dithering and non-dithering. You can always speed up color reduction with the -treedepth option. Try -treedepth 4, for example. In the mean-time we're looking at using OpenMP to speed up color reduction.

1) That does not seem to explain why no dithering (+dither) is so much slower than using dither (by removing +dither) when using -remap. Seems counter-intuitive to me.

2) If I keep the +dither and use -treedepth, will that change the histogram or at least the 6 most frequent colors? Nevertheless, using -treedepth does not seem to speed up my command:

time convert "CWLBCRMU.jpg" \
-treedepth 4 +dither -remap netscape: CWLBCRMU_tmp.mpc

Still about 8 seconds.

3) Does dithering vs no dithering change the histogram? If not, then I can just remove the +dither and get the speed back to what it was in earlier releases!

EDIT: Seems that a test with and with out +dither does change the histogram, though for this image, the first 7 colors remain in the same order.


So it would seem that the only current solution is to back down to a release where this change had not been made. What release would I go to?

[magick]

For each pixel in the image, we find the deepest node in the color cube. We then move to its parent and search any child nodes (up to for the closest color in the final gamut. To get uniform colors, we move up to its parent and we now have up to 64 nodes to check for the closest color. We just added support for OpenMP and got comparable results to the old method.

[fmw42]

We just added support for OpenMP and got comparable results to the old method.

That is good. But what about people with only one processor?

So it would seem that the only current foolproof solution for my script is to back down to a release where this change had not been made.

What release would I suggest my client go to if they do not have a multi-processor system?

For each pixel in the image, we find the deepest node in the color cube. We then move to its parent and search any child nodes (up to for the closest color in the final gamut. To get uniform colors, we move up to its parent and we now have up to 64 nodes to check for the closest color.

But should this really affect -remap with or without +dither? What does uniform colors have to do with -remap

If this is really the case, then is it practical to have some switch (-set or -define) to either switch back to the old way or set some tree-depth-like parameter to make it equivalent to what it was before?

[magick]

We have a fix for the speed problem and we get uniform colors for -posterize. Look for it in ImageMagick 6.6.7-8 by sometime tomorrow.

[fmw42]

We'll need to wait for Anthony. He is the one that suggested the change to fix a number of bug reports he was getting. We'll also investigate if there is a way to get uniform colors for posterize while not decreasing the algorithm performance.

Thanks. (My client and) I appreciate the investigation and look forward to Anthony's input.

Fred

[magick]

Turns out we don't need Anthony. I found another way to create uniform posterize colors without penalizing the existing color reduction algorithm.

[fmw42]

Turns out we don't need Anthony. I found another way to create uniform posterize colors without penalizing the existing color reduction algorithm.

Wonderful. Let me know if I can test anything for you in a beta.

Thanks

Fred

[anthony]

Turns out we don't need Anthony. I found another way to create uniform posterize colors without penalizing the existing color reduction algorithm.

Yes you can implement posterize with a uniform color map. BUT then posterize will not dither when no +dither option is given. That is something else I then reported as a bug! It wasn't posterize I was complaining about, but the color selection in ALL or ANY of the dithering methods not being RIGHT!

It is vary important that BOTH +dither and -dither methods do select the correct closest color, otherwise you are compromising the selection of those colors by the Color Quantization function. This was the problem I have been continually reporting, but you can only see it is a problem when you try to use the simple +dither or -dither none case.

Essentially but only using a fast 'near enough is good enough' type color selection, you end up never selecting some important colors that were discovered by the Color Quantization. For example the color quantizer finds say 250 color but then only 63 color set actually used!!!

To me that results in poor quality GIF images, and quality is important.

Perhaps we can offer both with some expert option to select between, OR find out why the current color tree is so slow in finding the actual 'closest color'. I myself do not understand the color tree.

[anthony]

Cristy, is there some way of getting IM to report the actual color map, the color quantization rouitne determined, RATHER than the colors that were later 'dithered' into the image?

This internal intermediate list of colors would be very useful, even if some of the colors don't actually get used in the final image.

[magick]

• Is there some way of getting IM to report the actual color map?

Not sure what your asking. If you dither to a GIF and use identify -verbose to dump the colormap, it reports all the colors used in the dither process. Were you looking for something else?

[anthony]

Is there some way of getting IM to report the actual color map?

Not sure what your asking. If you dither to a GIF and use identify -verbose to dump the colormap, it reports all the colors used in the dither process. Were you looking for something else?

Color reduction is typically a two stage process.

Reduce (quantize) the colors to a smaller pallette, then use (dither) those colors on the image.

however dithering may not actually use all the colors that quantization worked out (and is stored in some complex internal data structure).

Is there some way of getting the actual list of colors from the color quantization, rather than the actual colors that were later 'dithered' into the image. That is get the palette of colors that was determined, rather than the actual colors used in the image?