ImageMagick creates incorrect histogram

[Cici]

I have the following file

Code: Select all

hexdump -C imagemagick_histogram_bug.rgba
00000000  b4 83 d1 00 b4 82 d0 00                           |........|
00000008

and create a histogram for it:

Code: Select all

convert -depth 8 -size 2x1 imagemagick_histogram_bug.rgba -format %c histogram:info:-
         2: (180,131,209,  0) #B483D100 srgba(180,131,209,0)

According to the hexdump the histogram is plain wrong.

I tested ImageMagick 6.7.7-10 2014-03-06 Q16 (shipped with the latest ubuntu release) and the latest stable SVN version ImageMagick 6.8.8-10 Q16 x86_64 2014-08-19 (r16338).

[snibgo]

The problem may be that both your pixels are entirely transparent, so the histogram software treats them as equal. If we turn the alpha off, we get the expected two pixels:

Code: Select all

F:\web\im>%IM%convert -depth 8 -size 2x1 imagemagick_histogram_bug.rgba -alpha off -format %c histogram:info:

         1: (180,130,208) #B482D0 srgb(180,130,208)
         1: (180,131,209) #B483D1 srgb(180,131,209)

(Tested with IM v6.8.9-5 on Windows 8.1)

[Cici]

The problem may be that both your pixels are entirely transparent, so the histogram software treats them as equal.

Sounds like a reasonable explanation. However, I would also consider that behavior as a bug, because the histogram should reflect the image data.

I created a second image to validate your theory:

Code: Select all

hexdump -C imagemagick_histogram_bug2.rgba
00000000  b4 83 d1 00 5f ea a5 00  b4 82 d0 00 5f e9 a4 00  |...._......._...|
00000010

Code: Select all

convert -depth 8 -size 4x1 imagemagick_histogram_bug2.rgba -format %c histogram:info:-
         1: ( 95,233,164,  0) #5FE9A400 srgba(95,233,164,0)
         1: ( 95,234,165,  0) #5FEAA500 srgba(95,234,165,0)
         2: (180,131,209,  0) #B483D100 srgba(180,131,209,0)

As you can see, not all transparent pixels are considered equal.

[snibgo]

Hmm, yes, you've blown my theory out of the water. (I note that "-alpha off" separates them, again.)

Perhaps a developer will comment.

[Cici]

I think I understand what is going on.

The histogram uses some tree-like structure and computes the child index from 1 bit of each channel (starting with the most significant bit). However, there is a limit for the tree depth (currently 8) and at the leaf nodes, the code uses a compare function to determine whether two colors are equivalent. The first issue is that, although the limit is 8, the code stops before the least significant bit (unintended, but not critical). Since the two colors from the first example only differs in the least significant bit, he compares both colors. However, as already guessed by snibgo, the compare function says "both pixels are transparent (alpha=0), so they are equivalent" (=second issue).

I guess the histogram code needs its own compare function.

[snibgo]

I should mention: I don't think there is an ideal way of handling alpha. In my own histogram software, I give the user a choice: ignore alpha entirely, or regard alpha. When alpha is regarded, a fully transparent pixel is not counted in the histogram; a 50% transparent pixel contributes half a count, etc.

Another possibility, which I don't offer the user, is to treat alpha as another colour channel.

[Cici]

On a second thought, using a limit for the maximum tree depth is also an performance issue. I generated two files with 16-bit depth, where the upper/lower 8 bit of all colors are equal: Performance Test 1, Performance Test 2.

Code: Select all

time convert -depth 16 -size 512x512 imagemagick_histogram_performance_bug1.rgba -format %c histogram:info:/dev/null
real	1m41.660s
user	1m41.074s
sys	0m0.444s

time convert -depth 16 -size 512x512 imagemagick_histogram_performance_bug2.rgba -format %c histogram:info:/dev/null
real	0m5.273s
user	0m5.201s
sys	0m0.067s

Getting rid of the tree-depth limit would fix the original problem (no comparison needed) and the performance issue as well.