Finding the "right levels" for quantization with anim GIFs

[SineSwiper]

So, we're talking about a video conversion to GIF, similar to the guide here. In the last step is the color quantization process with an ordered-dither, which needs to be manually figured out. It has an example like this:

Code: Select all

convert -quiet plane.avi -ordered-dither o8x8,23 -append -format %k info:

So, through trial and error, you can figure out whether 23 is enough color levels or not. However, why waste colors on stuff like blue, which has a pretty low visibility on the human visual spectrum, compared to differences in red and green? So, we can do something like o8x8,23,23,11 with exactly half of the blue channels. Okay, that gives us more room to play with and we can start to increase until we hit o8x8,26,26,13.

My big question is about the methodology. I just (semi-)randomly picked a method of dividing blue by 2 and suddenly I have better color quantization. How would I go about finding the theoretical "best" quantization? Maybe the green level should be reduced? Maybe the animation has more red than usual? Maybe the human eye can't pick up polarizations of that color as much as another color?

Of course, we're talking about something a bit more complex than going up the scale on a single level variable (like o8x8,23). However, it seems like the tools would be there to figure it out. I have a histogram from the histogram: option, but how could you programmatically go about finding the best ratio between the three levels? Running through something like -scale 1x1\! -format '%[pixel:s]' info:- can give you an average color, but I'm not sure if that's the most accurate ratio to use?

[anthony]

The reason why much higher quantization level work is that not all the colors are used in the final image.

The problem is that at this time ordered dither an not use a random set of colors for the dithering purpose as the various error-diffusion dithers can. It is possible to allow it to do this, but the algorithm to handle this situation is slow.

For some information on the problems a palette ordered dither has to content with see...
Joel Yliluoma's arbitrary-palette positional dithering algorithm

[SineSwiper]

The reason why much higher quantization level work is that not all the colors are used in the final image.

??? I know you're going from a few million colors to 255 colors. That's the whole point of this conversation.

The problem is that at this time ordered dither an not use a random set of colors for the dithering purpose as the various error-diffusion dithers can. It is possible to allow it to do this, but the algorithm to handle this situation is slow.

I don't want it to be random! Randomness degrades the level of transparency compression you can do on a per-frame basis. This is why error diffusion dithers aren't appropriate for animations.

For some information on the problems a palette ordered dither has to content with see...
Joel Yliluoma's arbitrary-palette positional dithering algorithm

Interesting demo of various methods, but it doesn't really answer my question.

I've found a potential partial answer, but I'm not sure if it's the best one. Basically, I look at the appended image's kurtosis value for each of the RGB stats. This gives me a good idea of which channels have the "thickest peaks" in the histogram. Lower/negative numbers means that it needs a large number of channels. Here's an example:

Code: Select all

R ==> -0.760 ==>  1.000
G ==> -0.217 ==>  1.544
B ==> -0.151 ==>  1.609

Trying 8x8,9,6,5... 183 colors
Trying 8x8,9,6,6... 215 colors
Trying 8x8,10,6,6... 235 colors
Trying 8x8,10,7,6... 273 colors

So, what I'm doing above is adding 2 to the kurt value (to get it out of the negative), and subtracting the difference between Red and 1 to all of the channels. Thus, the Red:Blue ratio is 1.609:1.

EDIT: Actually, I'm having better luck running the kurt values by 2^kurt and then dividing Red against everything else. This seems to punish blue more, which seems accurate in the cases that I am seeing them in. I still recommend a minimum of 4 for any level, though. Anything less ends up being pretty noticeable.

[SineSwiper]

Hmmm, seems like 2^kurt doesn't work well with high kurt figures like the example plane.avi. Does anybody else have any other ideas around color levels? What are the mathematical "facts" around the human perception of RGB colors? A blue of 255 seems darker than 255 of Red or Green, so one would surmise that humans would have a harder time figure out the difference between, say, 240 blue vs. 240 red or green. But, what scientific evidence do we have in terms of the average human perception?

[anthony]

The problem is that at this time ordered dither an not use a random set of colors for the dithering purpose as the various error-diffusion dithers can. It is possible to allow it to do this, but the algorithm to handle this situation is slow.

I don't want it to be random! Randomness degrades the level of transparency compression you can do on a per-frame basis. This is why error diffusion dithers aren't appropriate for animations.

Not my meaning. By 'random set of colors' I mean a set of colors that was selected by some quantization algorithm to best represent the image. that is provide more colors to 'shades' and less colors to the 'single odd-colored pixels'.
But the final set of colors to use is essentially not 'ordered' or 'evenly distributed.

The ordered-dither in Image magick currently can only use a uniform distribution of colors, where really it should be using a dither or two or three 'close' colors (like error-diffusion dithers) to better color the picture, but without 'error-noise'.

The real problem with doing it 'by level' is that the levels divide up the channels in the image, but GIF counts unique colors, which are very different things. It is just a odd (and not very good) quantization method. Not all the colors creating by 'using a uniform colormap' gets used by the image, so you add more levels to generate more colors.

One improvement would be to do all this with gamma correction. That is map the image to a 'linear' color map, do the quantization-dither then map back. You may even be able to get better results as you will get more 'bright' color levels
where you need them. Even Joel Yliluoma's algorithm does this aspect.

See Uniform Color Maps (which is the quantization the ordered dither is doing)
http://www.imagemagick.org/Usage/quanti ... _colormaps

For some information on the problems a palette ordered dither has to content with see...
Joel Yliluoma's arbitrary-palette positional dithering algorithm

Interesting demo of various methods, but it doesn't really answer my question.

I've found a potential partial answer, but I'm not sure if it's the best one. Basically, I look at the appended image's kurtosis value for each of the RGB stats. This gives me a good idea of which channels have the "thickest peaks" in the histogram. Lower/negative numbers means that it needs a large number of channels. Here's an example:

Code: Select all

R ==> -0.760 ==>  1.000
G ==> -0.217 ==>  1.544
B ==> -0.151 ==>  1.609

Trying 8x8,9,6,5... 183 colors
Trying 8x8,9,6,6... 215 colors
Trying 8x8,10,6,6... 235 colors
Trying 8x8,10,7,6... 273 colors

So, what I'm doing above is adding 2 to the kurt value (to get it out of the negative), and subtracting the difference between Red and 1 to all of the channels. Thus, the Red:Blue ratio is 1.609:1.

EDIT: Actually, I'm having better luck running the kurt values by 2^kurt and then dividing Red against everything else. This seems to punish blue more, which seems accurate in the cases that I am seeing them in. I still recommend a minimum of 4 for any level, though. Anything less ends up being pretty noticeable.

Interesting idea.

[anthony]

After looking at your related thread
viewtopic.php?f=2&t=20089

I see no reason why you can not do your ordered dither quantization in LAB color space.
Just convert the image into LAB colorspace, apply the quantization/dither and convert back.

Ordered dither does not make any check (other than channel limitations) with regards to what colorspace or gamma correction is being used. It dithers using uniform 'levels' based purely on the data within the image.

[SineSwiper]

Not my meaning. By 'random set of colors' I mean a set of colors that was selected by some quantization algorithm to best represent the image. that is provide more colors to 'shades' and less colors to the 'single odd-colored pixels'.
But the final set of colors to use is essentially not 'ordered' or 'evenly distributed.

Could this be achieved by doing a error-diffusion on a "copy" image, setting the palette of that copy image to the real image, and doing the ordered dither? Actually, I'm not sure if that would work, as the palette can't just be "changed" without the OD at the same time. Can the palette be somehow "passed" to the OD function?

The ordered-dither in Image magick currently can only use a uniform distribution of colors, where really it should be using a dither or two or three 'close' colors (like error-diffusion dithers) to better color the picture, but without 'error-noise'.

Hmm, is this a threshold map problem or an ordered-dither problem? Does having "close colors" defeat the purpose of a "dispersed" dither?

Speaking of threshold maps, I wrote a smallish C-based map generator for ALL sizes of dispersed dither, including proper "void-and-cluster" dispersed maps for oddly shaped (or oddly powered) maps. I'm running some filesize vs. color tests on a bunch of various sizes right now to see if I see any that produce "bang-for-my-buck" on both. Got powers of 2 up to 32x32, including all sizes of P2 rectangles, and two "widescreen" versions (16x9 and 32x18). The quality differences on Lenna seem to be pretty slight, but I'm hoping they might pay off in GIF compression.

The real problem with doing it 'by level' is that the levels divide up the channels in the image, but GIF counts unique colors, which are very different things. It is just a odd (and not very good) quantization method. Not all the colors creating by 'using a uniform colormap' gets used by the image, so you add more levels to generate more colors.

Yeah, it's a very long process having a Perl script run through these different combinations to get a full color palette. At least with LAB, I can focus on L and just a 11-to-13 spread of AB. What kind of time commitment would it be for you to implement a better quantization method for OD?

One improvement would be to do all this with gamma correction. That is map the image to a 'linear' color map, do the quantization-dither then map back. You may even be able to get better results as you will get more 'bright' color levels where you need them. Even Joel Yliluoma's algorithm does this aspect.

You mean LAB? :)

Interesting idea.

"It's a wonderful idea......... but it doesn't work."

I see no reason why you can not do your ordered dither quantization in LAB color space.
Just convert the image into LAB colorspace, apply the quantization/dither and convert back.

Yep, that's what I'm doing currently, and the dither is just plain better than doing it in RGB space. Furthermore, colors can be subtracted by taking that LAB space and going into sRGB space. I've noticed that since resizing an image (smaller) increases the number of colors by ten billion, I've had to trim down the colors prior to the OD operation. Otherwise, the dither looks like crap, as it's too much to go from 9 million colors to a OD of ~256 colors.

This is why I put in that bug report about the --colors option. The standard color quantizer just can't seem to decide on the right ones if it's presented with huge limits. Yet, it can lossy switch between colorspaces pretty easy. So, I end up with a mile-long command line like this:

Code: Select all

convert anim.pam -colorspace YIQ -resize 300x169 miff:- | convert miff:- -depth 7 miff:- | convert miff:- -colorspace sRGB miff:- | convert miff:- -depth 32 -colorspace Lab -format "%o[%p/%n] %m %G %g %z-bit %r %kc -identify miff:anim.miff
(ordered dither command would follow)

Also, ImageMagick seems to "hang on" to as much detail about the colors as possible to prevent information/color loss, instead of just following what I say in the order I say it. Hence, I have to do this pipe operation. If combined, it would simply convert to 32-bit Lab and resize everything, ignoring everything else.

Regardless, LAB is a wonderful, wonderful thing. You should broadcast it more. It should be used in every quantization, since every image is going to be quantized to look good by human eyes. And for that matter, the LAB->sRGB conversion saves on color space, since a grand majority of images are only going to be shown on a sRGB capable output device. It would be awesome if there was a "LAB times sRGB" space that only covers the sRGB colors, but still has the mathematical scale to human perception.

[anthony]

Also, ImageMagick seems to "hang on" to as much detail about the colors as possible to prevent information/color loss, instead of just following what I say in the order I say it. Hence, I have to do this pipe operation. If combined, it would simply convert to 32-bit Lab and resize everything, ignoring everything else.

The problem is that -depth is only an input/output setting. It should not effect colors of the image in memory. Though their is a bug where it does for some unknown reason. If we wanted an operation for depth reducion of in-memory colors then a new option should be added. May be useful for use with HDRI versions of ImageMagick too.


Recentally their was someone who wanted to merge the bit patterns of image color values together.
This involved using '&' inside a -fx expression. This could be used to have the same effect as color reducion.

On the other hand you can also do this using -level in non-HDRI versions of IM -- I even have an example...
http://www.imagemagick.org/Usage/basics ... um_effects

This is a very very sever color reduction, but you can basically do it to any 'depth level' you like, not just 8 bit!

This is also just like setting the number of greyscale 'levels' in order-dither. Just using a 'threshold' dithering thresholds map instead of a diffused pixel threshold map.

[SineSwiper]

Also, ImageMagick seems to "hang on" to as much detail about the colors as possible to prevent information/color loss, instead of just following what I say in the order I say it. Hence, I have to do this pipe operation. If combined, it would simply convert to 32-bit Lab and resize everything, ignoring everything else.

The problem is that -depth is only an input/output setting. It should not effect colors of the image in memory. Though their is a bug where it does for some unknown reason. If we wanted an operation for depth reducion of in-memory colors then a new option should be added. May be useful for use with HDRI versions of ImageMagick too.

So, is -colorspace an input/output setting as well, or is it a direct action? If I had multiple colorspace options, would IM only take one of them or convert them in order?

[anthony]

colorspace setting is used to define how the image data should be interpreted.

-colorspace will convert the data to the given dataspace (In IMv6 the exception is sRGB which converts non-linear RGB to linear RGB)

-set colorspace just changes the setting but NOT the image data itself.


See examples...
Color Channels
http://www.imagemagick.org/Usage/color_basics/#channels
Gradients in other Colorspaces
http://www.imagemagick.org/Usage/canvas ... colorspace
Resizing with colorspace correction
http://www.imagemagick.org/Usage/resize ... colorspace

[SineSwiper]

Yes, but if I had "-colorspace sRGB -colorspace Lab", would that convert the input image from RGB to sRGB to Lab, or just RGB to Lab?

Also, were you interested in that C program for creating perfect ordered-dither maps of any shape?

[anthony]

I would assume just RGB to LAB.

I have not been involved in the current 'colorspace' decisions, only in discovering the results of those decisions, and documenting them.

I am hoping that IMv7 will see a more integrated colorspace handling with options to declare if the incoming or outgoing image is to be thought as being linear-RGB (used for mathematical data and masking) or non-linear sRGB (used for images). That is what the default 'RGB' of an image means.

Also a correction so that a colorname (typically defined using 8-bit sRGB) will be correct when when you do drawing or annotating correctly in linear RGB. That is a closer look at correct colorspace handling.

NOTE: for proper colorspace handling at least a Q16 version of IM should be used. How to do it correctly with Q8 versions is much more difficult!