Optimizing Animated GIFs / Contest 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.
Original animation - 21,069 bytes
Full frame less colors - 21,001 bytes
Joel Krautheim's winning entry - 4480 bytes (6 frames)
Travis Anton's winning entry - 4423 bytes
Miow Lin's winning entry - 3649 bytes (12 colors/6 frames)
Cyrinus I. Joseph - 3976 bytes (15 colors/6 frames)
Brett McBride - 4123 bytes (22 colors/6 frames/restore to previous)
Thomas Kurki - 4146 bytes (18 colors/6 frames)
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.
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.
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
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).
Restore to previous (using NS 2.02, works in IE 3+)
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.
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.
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.
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
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.
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:
- File size is proportional to bit depth
- Different Frame optimization methods can save from 4-8% in file size depending on level of sophistication but removing unnecessary pixels and colors can have a greater effect
- All disposal methods are not supported
- Minimize frames, pixels, and colors
- Key frames dominate file size
- Key frame optimization can save an additional 7-10% in file size
- Watch out for color shifts
- GIF Wizard is great at shrinking GIFs but can introduce problems
- Compatibility is complicated
- Smoothing frames are easy on the eyes
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 again to the winners, and thanks to everyone who participated.
- Optimizing Animated GIFs - First published in Dec. 1996 issue of Web Techniques
- Optimizing Web Graphics - First published in June 1997 issue of Web Techniques
- BoxTop Software - GIFMation
- SPG - ColorWorks:WEB 3
- GIF Wizard
Comments are welcome
Created: Aug. 15, 1997
Revised: Aug. 9, 2000