Optimizing Animated GIFs / Contest Summary | WebReference

Optimizing Animated GIFs / Contest Summary

home / web / dev / gifanim / summary

Penguin Challenge Results Summary

The results of the Penguin Challenge are in and Web Techniques has picked the winners. Congratulations to those who won, especially Travis Anton of BoxTop Software who's 4423 byte bird flew by the other 5 bit entries (and that's hard for a penguin) and Joel Krautheim of SPG (see Figure 1). For reference on this contest see the original rules.

Figure 1: 5 bit comparison

Original Full frame animation

Original animation - 21,069 bytes

Full frame animation opt

Full frame less colors - 21,001 bytes

Joel Krautheim - 4480

Joel Krautheim's winning entry - 4480 bytes (6 frames)

Travis Anton's Winning Entry

Travis Anton's winning entry - 4423 bytes

Figure 2: Other notable entries

3649mm

Miow Lin's winning entry - 3649 bytes (12 colors/6 frames)

3976cj

Cyrinus I. Joseph - 3976 bytes (15 colors/6 frames)

4123bm

Brett McBride - 4123 bytes (22 colors/6 frames/restore to previous)

4146tk

Thomas Kurki - 4146 bytes (18 colors/6 frames)

Mass Migration

Web Techniques was besieged by a flock of over fifty tightly compressed penguins from 12 countries. Some were duplicates, no doubt repeated bombings from folks who thought they missed their target the first time. Entries ranged from 2678K (shrunk to 50 x 60 pixels) to 4838 bytes, 4 to 5 bit, 12-26 colors, and a number of interesting techniques were used to squeeze every last byte out of poor Penny's hide. I want to thank Bob Kaehms at Web Techniques for taking on the task of winnowing down this fickle flock of foul, and finding the pearls. He must have felt he was in Hitchcock's "The Birds" at times. Congratulations also to all of you who participated.

General Observations

I designed the contest to improve GIF89a compression algorithms, educate, and be fun. I think it succeeded in all three goals. Some people really got into it. In fact, a couple developers I talked to pulled all nighters just to shrink that darned bird, refine their own programs, and make the deadline. A number of programs mentioned in the original article improved their compression algorithms substantially while the contest took place.

The entries fell roughly into three groups. Four bit entries ranged from 3545-4151 bytes and were of varying quality. Five bit entries ranged from 4123 (restore to previous) to 4838 btyes. Overlapping the ends of these two groups were the "restore to previous" crowd (Figure 3), who used this disposal method to avoid the overlapping pixels necessary in the "do not dispose" method (Figure 4). Within each group there were both 6 and 7 frame versions, and variations on the number of colors, and sophistication of frame optimization, and hand tuning unnecessary pixels and colors.

Disposal Method Comparison - Frame 4

Figure 3:
"Restore to previous"

Figure 4:
"Do not dispose"

size     disp  frames
init   opt    cols IE2.1 NS2.02  description
----------------------------------------------
3545sm MB  N  12 6  N      N     transp (occasional white penguin), movement in ice, mottled)
3649mm LZ  N  12 7  Y      Y     appears slightly mottled
3797me MB  N  12    N      Y     bombs IE 2.1, water moves vertically
3976cj FD  U  15 6  Y      Y     looks best of 16 color versions
4086az LZ  N  16 6  Y      Y     omitted 2nd frame, not 7th
4123bm FD  P  22 6  N      N     uses restore to previous* to great advantage
4126jm MB  N  21 6  Y      Y     dithered in lower left of ice hole, edge of ice and ltrs jagged
4146tk FD  N  18 6  Y      Y     looks nearly as good as 5 bit orig
4151cj FD  N  15 7  Y      Y     used light brown in ice for transp, full frame #5
4315tb                           bombs IE 2.1, garbles in NS 2.02
4318si FD  P  26 7@ N      N     restore to previous*, has smoothing frame
4423ta FD  N  21 7  Y      Y     looks identical to original, smallest 7 frame 5 bit gif
4451bm LZ  N  22 7  Y      Y     uses lzw optimization, lower left hole edge moves
4480jk FD  N  23 6  Y      Y
4591az LZ  N  22 6  Y      Y     omitted 2nd frame, not 7th
4594nh LZ  N  22 6  Y      Y
4601im LZ  PN 22 6  Y      Y     restore to previous on frame 2, N on rest for disposal
4611tl LZ  N  22 6  Y      Y
4629jf FD  U  21 6  Y      Y     5th frame full, green transp
4636nh FD  U  22 6  Y      Y     interframe delay changed to 30,20...15
4638jk FD  N  22 7  Y      Y     
4641pd FD  U  22 6  Y      Y     5th frame full, green transp
4647cj FD  N  21 6  Y      Y     uses ice tan for transparency color
4647mh FD  N  21 6  Y      Y     used ice tan for transparency color
4649jk                           white-backed penguin
4705mt                           blue shadow, penguin shows through shadow in NS 2.02
4745mt                           white box in IE 2.1, NS 2.02 works
4754at LZ  N  20 7  Y      Y
4755az FD  N  22 6  Y      Y     omitted 2nd frame, not 7th
4779rf                           mottled, used non-dithering colors?
4806mm LZ  N  25 7  Y      Y
4823ac FD  N  26 7  Y      Y     5th frame full, green transp
4826jj LZ  N  22 7  Y      Y       
4826jw LZ  N  22 7  Y      Y  
4829jc LZ  N  22 7  Y      Y  
4831ak LZ  N  22 7  Y      Y
4834jw LZ  N  22 7  Y      Y 
4838jk FD  N  23 7               white backed penguin
* gives 5 overlapping penguins in IE 2.1 and NS 2.02
@ 7th frame is a 1-pixel smoothing frame
Size   = file size
init   = initials of contestant
cols   = exact number of colors in palette (note, gif wizard-optimized
  gifs have a subtle black of RGB=4,5,6 used as transparency color,
  don't be fooled by two nearly identical blacks, they are different
  colors).
opt    = optimization method
    FD = Frame Differencing
    LZ = LZW optimization,
    MB = Minimum Bounding rectangle
disp   = disposal method
    N  = do Not dispose
    P  = restore to Previous
    U  = Unspecified
frames = number of frames
IE2.1  = works in Internet Explorer 2.1 Mac
NS 2.02= works in Netscape 2.02 Mac

Compatibility Problems

People went to great lengths to to shrink the penguin. Some removed the second frame instead of the seventh. Some used a stripped down penguin for the fifth frame and "restore to previous" and some were so fanatical about reducing colors they made the black used in the penguin the transparency color, which created the occasional "naked penguin" that you can see in the smallest winning entry (Figure 5).

Figure 5: Problem Birds rendered in NS 2.02

Naked penguin

Naked penguin

4123 - Restore to previous

Restore to previous (using NS 2.02, works in IE 3+)

4315 Corrupted

Corrupted penguin

White-backed penguin

White-backed penguin

Mottled penguin

Mottled penguin (non-dithering colors?)

Web Techniques found judging to be difficult, as many of the entries had some sort of problem with one or more hardware/browser combinations. Many of the GIF Wizard optimized animations "turned black" when viewed alone, some animations had transparency problems, and some had color shifts in the sky and water and appeared dithered.

Figure 6: Curves

Curves

Curve Balls

Many entrants caught the subtle curves I threw into the original animation. These deliberate additions were included to graphically illustrate common problems with many animations on the Web, namely unnecessary frames vs. smoothness, and unnecessary colors.

Unnecessary Colors

The original 21K animation had what some contestants called a "blob" of nearly indistinguishable but different color blue in the middle of the sky (Figure 6, blob made white for legibility). Some contestants caught this extra unnecessary color, and eliminated it, the results are virtually indistinguishable from the original. This example illustrates one common error in many animations now on the Web, unnecessary colors.

The second curve I included was a small 2-pixel patch of blue in the lower left corner of the ice hole (Figure 6). Eliminating this plus the above blob from all the frames, and reassembling in GIFBuilder gives a file size of 21,001 bytes (Figure 1).

Some contestants went even further, and reduced the key frame even more. Although we wanted a level playing field, some of the entries did an amazing job reducing the key frame to 18, 16, even 12 colors, and some looked nearly identical to the original (Figure 2). Reducing the key frame's entropy (more on this later) was actually was a key factor in some of the winning entries.

"Unnecessary" Frames vs. Smoothness

The original animation had seven frames, the first and seventh frames were identical. There are two reasons for this "extra" seventh frame, one, it makes the penguin appear to completely leave the screen, stage left. Two, on some browsers, namely Netscape, the penguin hesitates on the final frame while the browser accesses its cache. While many contestants removed the final frame saying it was a duplicate, I liked the effect it had on smoothing out the animation. One contestant, Brett McBride, who used the "restore to previous" disposal method used what he called a "smoothing frame" consisting of a single pixel. Using the conventional (and universal) "do not dispose" method I used the seventh frame as a smoothing frame. This extra frame illustrates that not all frames are necessary (minimize the number of frames), but some are esthetically pleasing.

Brett correctly points out in his thorough letter that you could create two animations, one optimized for Internet Explorer 3+ that uses the "restore to previous" disposal method (and can be up to 20% smaller), and another that uses the "do not dispose" disposal method. You could automatically deliver a browser-optimized animation with JavaScript and/or frames, or a client side cgi script. This would of course mean maintaining two versions of the graphics and/or pages.

Decrease Entropy and Avoid the Aging Process

Entropy is a mathematical measure used in Thermodynamics and Information Theory. The phrase "entropy always increases" is a simplified version of the second law of thermodynamics. Entropy in thermo means a measure of the unavailable energy in a thermodynamic system. In information theory, which is what we're concerned with, entropy is a measure of the amount of information content or "uncertainty" of x. The higher the entropy in a GIF, the larger the file size. You could think of entropy as the amount of change or complexity in a particular graphic. So to really shrink down our key frame, we need to reduce its entropy. How do I decrease entropy?

On reflection, the best time to reduce entropy is in the design phase, when you're planning and creating your graphics. Using large flat (and in the case of GIFs, horizontal) areas of color, and fewer colors to start out with, will make a nice low entropy (or less graphically complex) image that will compress better than a more colorful and complex image. But we wanted to break the rules with Cool Central, so we decided to try and simulate ice. We realized that it would make for a larger image, but we knew we could reduce and trim it later.

Key Frame Optimization

A few of the contestants reduced the entropy of the key frame to their advantage. Remember that the rules said "appear identical" so any change is OK as long as it still looks the same. They realized that after frame optimization, the key frame took up over 50% of the entire animtion's file size (2910/4823 bytes), so a reduction in the size of this full-sized frame would have a greater effect than on all the others combined.

To reduce the entropy of the key frame (which is a high entropy image) you need to reduce the number of colors and the number of color changes within the image. Some contestants simply reduced the colors using the built-in quantization algorithms of the GIF animation program they used. This works fine for smaller number of colors removed, but for larger reductions the change became apparent. Some caught the curves I threw in and lowered the entropy by eliminating the three off-color blue areas. A few contestants went even further, and hand tuned the key frame.

Travis Anton removed 361 bytes from the key frame by making a few changes to reduce its entropy. This is a 7.5% decrease in total file size (361/4784 bytes), about the same amount that LZW frame optimization can yield over the minimum bounding rectangle method. Travis skillfully reduced the key frame from 19 colors to 16, with no apparent change in quality. He did it by:

  • Removing infrequent colors
  • Merging similar colors
  • Removing stray pixels that break up flat areas
  • Hand tuning the image

Wish List

A color histogram (a graph that shows the distribution of color among the pixels in your image) would be a useful tool to see which colors are the most infrequent in an image. I'd like to see the GIF Animation programs add features like this to make hand tuning images easier.

Lessons Learned

While the feathers settle let's reflect on what we've learned during this contest. Here's a summary of what we learned during this contest:

Conclusions

Optimizing animated GIFs is a delicate balance between file size, the number of colors and frames, and compatibility. Those that walked that fine line the most effectively were rewarded. It turns out that hand trimming unnecessary pixels, and reducing the number of colors, especially in the key frame, had a greater effect than the frame optimization method used. The winners combined all three techniques to their advantage. There's still room for improvement, some of the winners used frame differencing and the minimum bounding rectangle method, and LZW optimization would yield even smaller results.

While file size is important, compatibility is also a big issue with professional designers. You want to find a method that works on the most browsers possible. Look for a GIF animation program that has browser compatibility checking built-in, like GIFMation. GIFMation had the least compatibility problems of the programs used. Animations created with it were virtually glitch-free.

Congratulations!

Congratulations again to the winners, and thanks to everyone who participated.

References

Comments are welcome


Created: Aug. 15, 1997
Revised: Aug. 9, 2000

URL: http://webreference.com/dev/gifanim/summary.html