Frame Optimization

Optimizing Animated GIFs

Frame optimization refers to the optimization method used to handle interframe changes. There are three increasingly sophisticated ways to save changes between frames. GIFBuilder uses the minimum bounding rectangle method, GIF Animator, GIFMation and Debabelizer (manual), and ImageReady use frame differencing, and SuperGIF, GIF Wizard, WebPainter 3.0 and Fireworks use Lempel-Ziv-Welch (LZW) interframe optimization.

Frame Optimization Method Comparison

Fig. 5: Full frame (no optimization) = 3259 bytes

Fig. 6: Min. Bounding Rectangle = 485 bytes

Fig. 7: Frame differencing = 423 bytes

Fig. 8: LZW optimization = 412 bytes

Minimum Bounding Rectangle

I first tried GIFBuilder's "frame optimization" feature, which crops motion frames to the rectangle that bounds only the changed pixels. This cut our penguin's file size by a factor of four; see Figure 6.

Frame Differencing

By saving only the pixels that change from frame to frame you can save even more. For the Mac, GIFMation 2.1 makes frame differencing a snap. The new "Export Optimized..." feature performs "intelligent frame differencing" automatically. The BoxTop folks say that intelligent frame differencing uses an adaptive hybrid approach that's halfway between straight frame differencing and LZW optimization. GIFMation 2.1 is the first Mac product to automate the frame differencing process.

ImageReady 3.0 performs frame differencing, if you check the transparency option in the optimize dialog box. Without transparency (the default) ImageReady performs minimum bounding box optimization. The "lossy GIF" feature saves even more file size by preprocessing the image data to optimize LZW compression. ImageReady doesn't optimize on file export like the others, you can tweak in real time using the optimize dialog palette (see next page for full interface).

Debabelizer also makes frame differencing possible, but it is a manual process. Its "compare" feature lets you create images containing only the pixels that change from one frame to another. Combining these "difference frames" with an initial full-size "background" image yields highly optimized GIF animations (more on this later). Debabelizer 3.0 was released recently, and has a much improved interface, but still requires a script to read in animated GIFs.

Windows users can achieve the same effect using Ulead's GIF Animator. GIF Animator was the first client side program to remove redundant pixels automatically, with its "GIF Optimization" feature. All frame differencing - automated or manual - saves an additional 4 to 6 percent in file size; see Figure 7.

LZW Inter-frame Optimization

LZW is the compression algorithm used by Unisys' GIF89a format, and also in the popular PKZip compression program. LZW stands for the inventors, Lempel, Ziv, and Welch. Like TIFF (Tag Image File Format) GIF uses LZW compression, but unlike TIFF, GIF can handle only 256 colors. LZW, a lossless compression algorithm, works by substituting strings of data for patterns.

Here's how it works, LZW starts with the first pixel in the upper left and builds up a table of patterns it has seen before. It initializes the table by assigning entries 0...n to a pixel's potential colors, n is determined by the size of the color table. Actual patterns are represented with the next higher number of bits. Thus if a palette has 256 colors (8 bits), the first pattern will have a code 9 bits long. If the palette is 16 colors (4 bits), the initial code size will be 5 bits. This is why the number of colors has such an impact on GIF file size.

Once a pattern has been recognized and is in the table, any subsequent occurrences of the pattern are represented by the current code size, which can go up to 12 bits. Potentially a pattern of up to 256 pixels could be represented by a single code if it has already been seen. That's why consistent patterns save file space.

LZW Optimization

You can take advantage of LZW's pattern recognition and preprocess your frames to make LZW more efficient. The idea is to even our similar patterns to minimize the number of unique codes. In some cases lengthening lines actually reduces the size of the file.

SuperGIF 1.0

BoxTop Software's new SuperGIF employs LZW inter-frame optimization and a unique re-dithering algorithm that subtly rearranges pixels to increase compressibility. The effect is not discernible to the eye but LZW works slightly better with this new technique. SuperGIF's interface couldn't be simpler, just drag and drop.

WebPainter 3.0

Totally Hip's WebPainter 3.0 adds frame differencing and hybrid LZW inter-frame optimization to version 2.0. WebPainter's interface is very easy to use, and features Photoshop-like editing palettes, filters, onion skinning etc. for easy animated GIF and banner creation. WebPainter is also one of the few programs to work on both the Mac and the PC.

WebPainter Export Dialog

Fireworks 3

Macromedia's Fireworks features LZW inter-frame optimization and lossy pre-processing. Fireworks 3 integrates optimization into a palette, make optimizing animated GIFs easy. Fireworks 3 defaults to minimize the number of colors and optimize using LZW inter-frame optimization: it automatically optimizes your superpalette, and auto crops and differences, performs LZW optimization, and removes all comments.

Fireworks 3

GIF Wizard

GIF Wizard was the first graphics optimization product to employ LZW optimization. A token-based on-line GIF reduction service at http://www.gifwizard.com GIF Wizard is the brainchild of Tom Kirchman, an innovative Unix guru who knows the insides of a GIF like the back of his hand.

After I used GIF Wizard's "remove redundant colors" feature I started poking around inside the resulting frames. Kirchman was definitely up to something! The files were smaller but the lines in the frames were actually longer, and appeared to be squared off and equalized. I realized that he was employing a form of LZW optimization (see Figure 8).

Tom wouldn't reveal all his secrets, but he acknowledged that GIF Wizard uses LZW optimization by "minimizing the frequency of changes in pixel patterns." Kirchman deftly combines colors with different Web-friendly palettes, and offers various bit depths to choose from. GIF Wizard is the first product that combines the three frame optimization methods: minimum bounding rectangle, frame differencing, and LZW optimization.

10-22-98 - Tom says he's squeezed about as much he can out of GIF89as, and my tests show he's improved his algorithm. GIFWizard beat its own previous record of 4834 bytes to 4827 bytes.

Problems - GIF Wizard is not without its problems though, animations optimized beyond the "clean GIF" step using the "remove redundant colors" step (which performs the LZW optimization among other things), can create artifacts on the first loop of the animation, if the animation "expands." This is only seen in Internet Explorer 2.1+, which is notorious in it's spotty GIF89a support. Reload the animated chest below for an example. Also, animations optimized in GIF Wizard tend to turn black when viewed alone in Windows using Netscape 3.

GIF Wizard Optimized Chest - By Robert Polevoi

Performing LZW optimization after the difference method reduces file size by an additional 1.7 to 2%.