How to speed up creation of animated GIFs

[Saber850]

Years ago (~2006) I created an app w/ Magick++ that created animated GIFs and it worked well.
I've rebuilt it yesterday (no code change) and it runs much slower: it used to take a couple seconds, now takes over a minute. The OS is mostly the same (Gentoo Linux, so many updates since 2006, including the ImageMagick version). My hardware has gotten better since 2006 (faster CPU & more memory). Version: ImageMagick 6.7.1-0 2011-11-02 Q16; OpenMP is enabled.

The animated GIF uses transparency, contains relatively simplistic content (lines & squares, a handful of colors), 100+ generally small frames (10-15 pixels in each dimension).
If I write to a PNG (for example), ImageMagick creates a file for each frame extremely fast (a fraction of a second) which is interesting considering it's actually writing each frame to a separate file on disk. I also see that most of the time is spent in the call to writeImages.

I looked around the message board and found several suggestions. I've tried disabling transparency, setting the tree depth (using quantizeTreeDepth(4) ), the number of colors (using quantizeColors(64) ), and dithering (using quantizeDither(true) ) on all frames but none of these options (even all together) made any practical difference in the time it takes to generate the animated GIF.

I read several statements that ImageMagick uses "a sophisticated color reduction algorithm (see http://www.imagemagick.org/script/quantize.php) which looks for an optimal color palette to best represent the colors in a GIF animation sequence" so I tried specifying that the image should use a color pallete (using classType(PseudoClass) ) but that just slowed down the creation of each frame.
If the color reduction algorithm is the cause, can I turn that feature off?

Are there any other ways to speed up the generation of animated GIFs?

[fmw42]

Usually -treedepth makes quite a bit of difference in converting a (single frame) image to gif.


time convert logo: logo.gif

real 0m1.530s
user 0m0.024s
sys 0m0.030s


time convert logo: -treedepth 4 logo.gif

real 0m0.034s
user 0m0.019s
sys 0m0.013s

[Saber850]

I thought I tried setting the tree depth via quantizeTreeDepth(4) (see my original post). Is this not the proper method to use?

In my case, I am creating the frames programmatically, so I'm creating the output GIF programmatically as well (as opposed to using the pre-existing IM command-line tools).

[fmw42]

Sorry, I do not know or use any IM APIs, so cannot advise you about how to use -treedepth other than command line mode. One of the IM developers will need to help you further regarding the proper syntax.

[SineSwiper]

What's the full code of options? I've plenty of experience with anim GIFs, but on my end, it's mostly about getting the best quality of video conversion, rather than speed.

[Saber850]

What's the full code of options?

Here's the options I specify per frame:

Code: Select all

Image pic(g, transparentColor);
pic.page(g);   // set size of frame; 'g' is a Geometry object for this frame

pic.density(Geometry(72, 72) );
pic.animationDelay(10);
pic.gifDisposeMethod(1);
pic.compressType(RLECompression);

pic.transparent(transparentColor);
pic.strokeColor("black");
pic.strokeWidth(1.0);
pic.fillColor(Color() );  // Empty constructor is transparent color
pic.strokeAntiAlias(true);
pic.quantizeTreeDepth(4);
pic.quantizeColors(64);
pic.quantizeDither(true);
pic.classType(PseudoClass);   // This slows down each individual frame, and does not speed up GIF creation
pic.colorMapSize(32);   // This slows down each individual frame, and does not speed up GIF creation

The last two options (classType & colorMapSize) slow the processing down of each frame. Without these, the frames are generated very quickly, it's just writing the GIF that takes the majority of the time (w/out specific timings I'd say at least 90%).
I've also tried disabling transparency and anti-aliasing, but it did not affect the time to create the GIF.

For my application, speed is more important than quality.

I wonder if I can solve this problem in two steps. Since generating each frame is very fast (even if each frame is written to disk), I wonder if I can use IM to generate the individual frames on disk, and then use another app to put them together into a single animated GIF.

[SineSwiper]

Wait, hold on. The slowdowns make sense, and your choice of quantization parameters confuse me. First, from the manual:

classType - Image storage class. Note that conversion from a DirectClass image to a PseudoClass image may result in a loss of color due to the limited size of the palette (256 or 65535 colors).

So, this starts the color reduction. Quantization (color reduction) takes time. It has to look at the entire universal of colors in the image and pick a limited amount. And that limited amount is 32?!? A GIF can hold a lot more colors, up to 255 + one for transparency. Use them. The LOWER you go, the more CPU it takes to figure out the right ones it needs to pick. Not to mention that dithering also takes some time.

Actually, you're going from X to 64 (with a F-S dither) to 32. (BTW, what is X on your image?) Also, F-S will prevent good transparency optimizations for animations (since it's a random-based dither method). Consider an ordered dither or at least time the different dither options. Of course, the main problem is the number of colors. Try a pic.quantizeColors(255) and forget the colorMapSize (it's automatic; IM already knows it's saving a GIF). Dithering also takes CPU time, but really adds to the quality of a quantize, so try both. The classType really should be PseudoClass, or at least it needs to be saved as a GIF, so that it knows to do it automatically.

You also said "Without these, the frames are generated very quickly, it's just writing the GIF that takes the majority of the time". Well, it's probably doing the color mapping and reduction at that saving step, instead of the PseudoClass step. As far as I know, the property settings don't actually do anything. It's the methods that would actually force something magical to happen. You may want to force an update (somehow; possibly with modifyImage) on each set of options, just to time it properly.

If you REALLY want a quick quantization method, play with depth (like 7-bit depth) prior to the quantize. You might even need to force an update after the depth property is set and before the quantize.

Also note that I know nothing of the class-based API, so I may be talking out of my a@@ on some of this...

[Saber850]

I'm not sure if I made this clear, but I am creating the image from scratch entirely inside my app. I am not importing an image. The images I'm creating are extremely simplistic--each frame has a line and possibly a square or a circle. There are literally 3 colors in total: black, red, blue (plus white as the transparent color).

classType - Image storage class. Note that conversion from a DirectClass image to a PseudoClass image may result in a loss of color due to the limited size of the palette (256 or 65535 colors).

So, this starts the color reduction. Quantization (color reduction) takes time. It has to look at the entire universal of colors in the image and pick a limited amount.

As I mentioned in my original post, I only attempted to specify the classType after reading that IM employs "a sophisticated color reduction algorithm (see http://www.imagemagick.org/script/quantize.php) which looks for an optimal color palette to best represent the colors in a GIF animation sequence"--this was my attempt to save IM the work of trying to generate a pallete by looking at all colors in all frames after they're generated. I was hoping that by specifying to use a pallete up front, there wouldn't be any need to perform color reduction.
The important aspect here is that the image generation is slow w/out this option--this only slows it down even more because now each frame takes longer, and the time to create the GIF is still as slow as it was.

And that limited amount is 32?!? A GIF can hold a lot more colors, up to 255 + one for transparency. Use them. The LOWER you go, the more CPU it takes to figure out the right ones it needs to pick.

I tried values other than 32 (including 16, 64, & 255) and it didn't make a difference on the time it took. 32 should be more than enough for the images I'm creating--I'm only using 3 colors.

Not to mention that dithering also takes some time.

The performance does not seem to be affected if I disable dithering.

Actually, you're going from X to 64 (with a F-S dither) to 32. (BTW, what is X on your image?)

I'm only using 3 colors in creating the image (plus a transparent background).

Also, F-S will prevent good transparency optimizations for animations (since it's a random-based dither method). Consider an ordered dither or at least time the different dither options.

I'll look into it; I don't recall seeing different dithering methods in the manual. What is "F-S"?

Of course, the main problem is the number of colors. Try a pic.quantizeColors(255) and forget the colorMapSize (it's automatic; IM already knows it's saving a GIF). Dithering also takes CPU time, but really adds to the quality of a quantize, so try both.

I tried both--no difference.

The classType really should be PseudoClass, or at least it needs to be saved as a GIF, so that it knows to do it automatically.

I guess IM figures that out when writing to a GIF file. Functionally it works whether I specify the classType or not. But the perf is significantly slower (2x w/ my test data) if I specify classType(PseudoClass).

You also said "Without these, the frames are generated very quickly, it's just writing the GIF that takes the majority of the time". Well, it's probably doing the color mapping and reduction at that saving step, instead of the PseudoClass step. As far as I know, the property settings don't actually do anything. It's the methods that would actually force something magical to happen. You may want to force an update (somehow; possibly with modifyImage) on each set of options, just to time it properly.

All options except classType(PseudoClass) don't seem to have any affect on performance--my app rips through the frames (ie. no noticeable delay) and then takes ~5 sec creating the GIF. If I specify classType(PseudoClass) then each frame takes ~1/10 sec, and writing the GIF still takes ~5 sec.
Note that while 5 sec is not a show-stopper on it's own, that's the time for 60 frames (again, all of very small size, like 15px x 15px), and my app will usually be faced w/ hundreds of frames, in which case the time takes several minutes.

If you REALLY want a quick quantization method, play with depth (like 7-bit depth) prior to the quantize. You might even need to force an update after the depth property is set and before the quantize.

Assuming you're talking about quantizeTreeDepth, I've changed the depth setting to values between 1 & 8 and it didn't seem to affect perf. I don't know how to force an update though.

Also note that I know nothing of the class-based API, so I may be talking out of my a@@ on some of this...

I'm out of options short of stepping through IM in the debugger, so I definitely appreciate your attention, info, and suggestions.

I'm setting all the image's/frame's options before doing any drawing. Do you think it matters?

[SineSwiper]

Hmmm, yeah, only 3 colors changes things. BTW, F-S is Floyd-Steinberg, the type of dither. It's an error-correction dither, so it'll be random. Heck, for 3 colors, just turn off dither. No need for it.

Let's talk about frames, then. What's the frame delay? Are we talking 60 frames for 6 seconds? How many frames total?

[Saber850]

Hmmm, yeah, only 3 colors changes things. BTW, F-S is Floyd-Steinberg, the type of dither. It's an error-correction dither, so it'll be random. Heck, for 3 colors, just turn off dither. No need for it.

Ok, done (no difference in perf though).

Let's talk about frames, then. What's the frame delay? Are we talking 60 frames for 6 seconds? How many frames total?

The delay for all frames is 100ms (I call animationDelay(10); ). The total number of frames in this test case is 66 so the animation lasts ~6.6 sec, and I've confirmed it w/ the 'animate' program and Firefox.

[SineSwiper]

Yeah, 10fps is about the max you can get on a GIF, anyway. So, the main problem is the 5 seconds for 66 frames during the save? Do you have any way to isolate that down even further? Somewhat within the save process?

If not, it might be worth trying out a few different versions of IM, including one without OpenMP. (Parallel processing can be a bitch to code and debug...)

[Saber850]

So, the main problem is the 5 seconds for 66 frames during the save?

Correct.

Do you have any way to isolate that down even further? Somewhat within the save process?

I have not found a way short of stepping through IM in the debugger.

If not, it might be worth trying out a few different versions of IM, including one without OpenMP. (Parallel processing can be a bitch to code and debug...)

The last IM version that I noted to not exhibit this problem was 6.2.8.0. I could try rebuilding that version manually and using it, but that's not great from a long-term perspective.
I rebuilt IM w/ the following options and the perf improved by 1 sec (5 sec -> 4 sec): added: fftw lzma q8; removed openmp. It's an improvement, but I'm still far from where I need to be. I'll narrow down which of these was responsible for the improvement; maybe it'll provide a clue as to the direction to pursue.

Update: I narrowed it down: removing support for openmp caused the perf improvement.

[anthony]

Quantization (color reduction) takes time. It has to look at the entire universal of colors in the image and pick a limited amount. And that limited amount is 32?!? A GIF can hold a lot more colors, up to 255 + one for transparency. Use them.

This is a well know BUG, and is caused by two separated steps that were never optimized for small numbers of colors.

First quantization step, as far as I can tell actualy does generate 256 colors! (255 is transparency is needed) However when dithering is then used to change the image to use those colors it fails to find ALL the colors that were selected.

The causes for this is unclear from my experiments -- I have NOT looks at the complex code!
Theories include..

• tree-depth prevents dither matching to the exact 'nearest color' as doing so can be VERY SLOW.
  This may be due to the algorithm being designed to allow you to reduce colors to 'large numbers' of color like 1000 or so, even though more typically color reduction only reduces colors to 256.
• dither does match the colors, but then the 16->8 depth may not have been taken into account by quantization, and as such some colors are co close they become a single color in 8 bit color value depth.

Exactly WHAT is the problem is unclear, and has been a pain to me for a long long time.


Now the use of e-dithers for low color images like GIF, has also been somewhat painful. Their are new ordered dither methods which work better for GIF images (specifically animations) but can only be used with low color counts. Some published academic work has been done in this area, but it can be even slower than e-dithers, even though the quality of results is far higher.

All in all quantization and dithering in IM (for GIF images) is needing an overhaul, and we need programmer willing to do it.


Sorry for the 'rave' but this has been a problem of mine for a long time.

[SineSwiper]

This is a well know BUG, and is caused by two separated steps that were never optimized for small numbers of colors.

First quantization step, as far as I can tell actualy does generate 256 colors! (255 is transparency is needed) However when dithering is then used to change the image to use those colors it fails to find ALL the colors that were selected.

It's not just small numbers of colors, but also large number of colors as I reported in another post. It seems like the routines are solely optimized for the 256 color range.

All in all quantization and dithering in IM (for GIF images) is needing an overhaul, and we need programmer willing to do it.

Sorry for the 'rave' but this has been a problem of mine for a long time.

Can't really help there. Unfortunately, the need for color quantization seems to limited to the niche of GIFs, and they are typically only needed for GIF animations. Perhaps there is some better code from within GIMP (or SIVP or OpenCV) that we could borrow?

[Saber850]

I just tried building ImageMagick-6.2.8 but it fails due to incompatibilities w/ libpng-1.5 (structs which used to be visible are now hidden). Disabling PNG support yields some other error about atexit.
If it built and worked out of the box, I'd probably have used it as a temporary stop-gap solution. But since I need to put in more than the hour I already spent on it, I might as well look at other solutions. sigh...