GNOME Bugzilla – Bug 66367
Improved animoptimize for RLE or LZW compression
Last modified: 2003-11-26 20:27:01 UTC
The Animation Optimize plug-in checks if a new frame can be used in "combine" mode and then replaces all pixels that do not change in the new frame by transparent pixels. This optimizes the compression of the animation by making possible to reduce the bounding box of the new frame and replacing some areas containing various colors by transparent areas that compress well. However, in some cases it would be better to leave some pixels opaque instead of transparent if they are adjacent to a pixel of the same color. It is even better if the pixel is included between two other pixels of the same color. If the middle pixel(s) is(are) opaque, then the LZW or RLE compression will produce a smaller file because it will find a continuous line of pixels with the same color instead of having that line broken by transparent pixels. Here is an ASCII art description of that example. All "C" characters are pixels of the same colors. All dots are transparent pixels and all question marks are pixels of undefined colors: with the current animoptimize: opti_frame: ? C C . . . C ? last_frame: ? ? ? C C C ? ? with a better version that favors continuous lines: opti_frame: ? C C C C C C ? last_frame: ? ? ? C C C C ? In the second case, the line of pixels of the same color will compress better. This feature can be implemented in the animoptimize plug-in by checking all transparent pixels after the optimization pass. If these pixels could have the same color as the pixel at (x+1,y) or (x-1,y) then they should be opaque instead of being transparent. Here are the two cases in which a transparent pixel (".") should be replaced by the color ("C") from the last frame: - (x,y) would have the same color as (x+1,y): opti_frame: . C last_frame: C ? - (x,y) would have the same color as (x-1,y): opti_frame: C . last_frame: ? C These changes should be propagated forward and backwards on the same line in order to have the longest possible sequence of pixels with the same color. This improves the RLE or LZW compression, which is the primary target of this plug-in. A patch that implements this extra pass over the transparent pixels is included below. I have also included a test image that shows the different results between the current animoptimize and the new one.
Created attachment 6171 [details] [review] patch against plug-ins/common/animoptimize.c from 1.2.3-pre2
Created attachment 6172 [details] simple GIF animation - not optimized: 10970 bytes
Created attachment 6174 [details] simple GIF animation - optimized (old plug-in): 8829 bytes
Created attachment 6175 [details] simple GIF animation - optimized (new plug-in): 7989 bytes
To see the differences between the three images, open them and hide the background layer. The differences will be obvious. This small test image was created only for demonstrating the effect described here but I have also seen significant gains with other animations that have continuous regions of the same color.
I haven't had time to verify the patch, but I trust your code :) and the optimization had occurred to me before as valid -- I say go for it.
Oh yeah, this should probably go in 1.3 (leave well enough alone... stability, stability) and I'd prefer the run-length-glomming to be optional but on by default (sometimes I /really/ want only the image diff), but I'd recommend that you use this 1.2-based code and simply replace the 1.3 tree's animoptimize plugin with it (except for the GTK-1.4-ported UI code) because the 1.3 tree's plugin contains a couple of new features that I never had time to make work completely so I'd be backing out some time anyway (unless you feel like fixing them!). Ta, --Adam
s/color/colour/g *grin*
I understand your point about 1.2 vs 1.3 (1.2 is for bug fixes only) but it would be interesting to make the patched plug-in available in order to help those who want to squeeze the last bits out of their animated GIFs and are using 1.2. Maybe it could be put in the registry if it is not part of the stable distribution? Regarding the UI, I agree that it would make sense to make this additional step optional. This is one of the reasons why I did not merge this with the main optimization loop (it would have been easy to do that, at least for the left-to-right pass). If there is a dialog box added to this plug-in, then it could also be used to toggle other options. For example, instead of trying to maximize the number of adjacent pixels with the same value, the plug-in could try to maximize the number of repeating patterns (also good for LZW compression). There could also be a lossy compression mode that uses a threshold value to merge similar colors instead of only testing for identical colors (threshold = 0).
I wouldn't put too much effort into this if I was you. IMHO gifsicle does a perfectly fine job on optimizing and unoptimizing GIFs: original size: 10970 bytes (your example) gifsicle --optimize -> 8705 bytes gifsicle --optimize=2 -> 7788 bytes Since the animoptimize plug-in is very much GIF-specialised it does not even make much sense to ship it with a standard GIMP distribution. People that need to work with GIFs should get the command-line tools and use them. IMHO it is also much more convenient to optimize all GIFs on a site from a script than searching the menu entry in The GIMP for each one of them. I do think however that the anim-unoptimize feature makes sense but it should probably be part of the GIF load plug-in. Just my two Pfennige (not much time left to spend them...)
If we remove the GIF plug-in from the main distribution and put it in a separate package ("web plug-ins"?) then it could make sense to put the animoptimize in the same package. But otherwise I think that animoptimize is a very useful part of the Gimp distribution. For me, optimizing an animation is an iterative process and it is more convenient to repeat the steps without having to leave the Gimp. For example, I often start by optimizing a first version of an animation, then I check if I can remove some unimportant pixels from one of the diff frames. If this is not sufficient, then I unoptimize and I try to convert to indexed mode with a smaller color palette. After that, I optimize again and I check if more can be done with the diff frames. Having to save-gifsicle-reload the image several times would be quite annoying, even if gifsicle may give a better compression in the end. But for the intermediate steps, the animoptimize plug-in is very useful.
One thing that I forgot to mention: I use animoptimize as often in RGB more as in indexed mode. I prefer to do the first steps of the optimization in RGB mode because I can then use all the tools and plug-ins easily. I do the final iterations in indexed mode, when the image is almost ready to be used. The operations in RGB mode could not be done with tools like gifsicle.
Raphael, should I apply your changes to the HEAD branch then?
Well, yes you can try to apply it to the HEAD branch, although Adam mentioned that some of the code that is currently in HEAD should be removed first. I cannot do a diff between the branches for the moment, so I do not know how much has changed. The patch was made for the stable branch and I do not know if it can be applied cleanly to HEAD. Also, this improvement is unconditional. Adam said that he would prefer to make it optional (on by default) but then the plug-in would need to have its own dialog. I cannot work on the new user interface right now because I do not even have a working version of GTK+ 2.x for Solaris. So I leave it up to you to decide if you prefer to apply the patch now or wait until I can re-write the plug-in with a new user interface (and some of the other improvements discussed above, such as a threshold for the color difference).
I'll wait then. There are lots of things with higher priority.
Is anyone working on this bug?
I haven't done any real work on this since I posted the patch. But I still apply the patch to my local 1.2 source tree and to any 1.2-pre* tarball that I download, because it is very useful for me. I also point other people to it when they mention that they would like to compress their GIF images a bit better without requiring external programs. The patch could be applied to 1.2 without problems. For 1.3, my build tree is broken because of the gtk-2.2 dependencies and I will probably not be able to fix it before mid-May. After that, I could start working on a version for 1.3 and add an option for enabling or disabling the LZW-optimized feature.
Any chance of getting the patch updated for inclusion in 1.3.18? Seing as there's a patch there, and it seems to have had some field testing, it'd be a shame not to apply it. Dave.
As far as I'm concerned this is probably fine to go into 1.3.x. There's heaps of cruft in animoptimize at the moment but I can scrape that out at some future date whether this patch is in or not really.
Well, OK then. Raphael, would you mind posting a 1.3.17 patch, and we'll get this closed? Cheers, Dave.
Sorry for not commenting on this earlier. The notification mail for this bug report got lost among the 1000+ Bugzilla notifications that I got while I was on vacation just before GimpCon... Anyway, I can try to submit a patch or to commit directly to CVS HEAD (if you trust me ;-)). But this will take a bit more work than the old 1.2 patch, because making this feature optional will require adding a GUI to the plug-in. Another solution would be to have no UI and register the plug-in twice in the menu: once as "Optimize for GIF or MNG" and once as "Optimize (difference only)". What do you think?
If the optimisation is a valid one (and everyone seems to think that it is), then I think it would be best to avoid a preference, and just have it done this way by default. Dave.
Raphael, can I have a status report? Unless there is a patch ready to commit, I'd suggest bumping this to 2.2 (or even closing it as WONTFIX). Dave.
I'd like to ask Adam (or any others who have an opinion on this) what would be the best solution: 1) Register the plug-in twice, as described in my previous comment: once with the optimization, once without. 2) Always use the optimization by default. 3) Keep the old version, do not change anything. 4) Add a new user interface for this plug-in and allow the user to select if any kind of optimization should be used. I think that (4) is the best long-term solution, although (1) may be sufficient. But I would really like to get this done in 2.0, so maybe implementing (2) or (1) would be the best short-term solutions. Any comments?
I like (1) or (4), with a mild leaning towards (1).
I suppose I should back that up. I don't want (3) because this is a neat and valid optimization, and I don't want (2) because the plugin's current mode is useful not only as an optimization but for a visual verification that I only changed the pixels between frames that I intended to -- the LZW optimization would mask that.
OK, thanks for the quick comments. I will try to implement (1) ASAP. Although (4) may be nicer and more extensible if we think about new options that could be added later, this is also the solution that requires the largest amount of changes to the existing code. So I will go for (1).
*poke* What's the status on this, Raphael? Ready to commit something? Cheers, Dave.
It's been a months since I've heard from Raphael on this. In the absence of a patch to apply in the next week or so, I vote for bumping this to 2.2, since I would still like to see a 2.0 by Christmas, and this is hardly essential (would there be any objections to applying this in a post-2.0 stable branch?) Dave.
It is an interesting coincidence that you send one more query about this bug just when I come out of my virtual black hole (caused by a dead fan in my PC, combined with three weeks of severe overload at work that prevented me from replacing it quickly). I did a cvs update yesterday and I am now going through the huge backlog of messages that I received in the meantime. I hope to be able to commit a patch very soon. Maybe not today, but at least before next week. If I do not manage to do it in time, feel free to bump the target milestone to a later release. Hey, and it was not one month yet! ;-)
2003-11-23 Raphael Quinet <quinet@gamers.org> * plug-ins/common/animoptimize.c: Allow the plug-in to register itself twice: once for the old mode (difference only) and once for the new mode that improves the 'combine' frames by trying to maximize the number of adjacent pixels of the same color. This gives a better compression for GIF, MNG and other formats that work on a line-by-line basis (bug #66367). Is it OK to backport this to the stable branch (for the hypotetical 1.2.6 release) and mark this bug as FIXED?
Thanks for the work. I think it's probably markable as fixed now (if someone can test it). Pretty neutral about backporting to the 'stable' branch, since this is strictly a feature-fix.
Well, I will mark this as FIXED for the moment and wait for feedback about what to do with the stable branch.
The change you did causes the following compiler warnings on gcc-3.3.2: animoptimize.c: In function `do_optimizations': animoptimize.c:972: warning: deprecated use of label at end of compound statement animoptimize.c:1012: warning: deprecated use of label at end of compound statement
I added noops after the labels to quieten the warnings. 2003-11-26 Dave Neary <bolsh@gimp.org> * plug-ins/common/animoptimize.c: Quieten a couple of harmless warnings. See bug #66367.