After an evaluation, GNOME has moved from Bugzilla to GitLab. Learn more about GitLab.
No new issues can be reported in GNOME Bugzilla anymore.
To report an issue in a GNOME project, go to GNOME GitLab.
Do not go to GNOME Gitlab for: Bluefish, Doxygen, GnuCash, GStreamer, java-gnome, LDTP, NetworkManager, Tomboy.
Bug 66367 - Improved animoptimize for RLE or LZW compression
Improved animoptimize for RLE or LZW compression
Status: RESOLVED FIXED
Product: GIMP
Classification: Other
Component: Plugins
1.x
Other All
: Normal enhancement
: 2.0
Assigned To: Raphaël Quinet
Daniel Egger
Depends on:
Blocks:
 
 
Reported: 2001-12-06 16:51 UTC by Raphaël Quinet
Modified: 2003-11-26 20:27 UTC
See Also:
GNOME target: ---
GNOME version: Unversioned Enhancement


Attachments
patch against plug-ins/common/animoptimize.c from 1.2.3-pre2 (2.88 KB, patch)
2001-12-06 16:53 UTC, Raphaël Quinet
none Details | Review
simple GIF animation - not optimized: 10970 bytes (10.71 KB, image/gif)
2001-12-06 16:55 UTC, Raphaël Quinet
  Details
simple GIF animation - optimized (old plug-in): 8829 bytes (8.62 KB, image/gif)
2001-12-06 16:57 UTC, Raphaël Quinet
  Details
simple GIF animation - optimized (new plug-in): 7989 bytes (7.80 KB, image/gif)
2001-12-06 16:58 UTC, Raphaël Quinet
  Details

Description Raphaël Quinet 2001-12-06 16:51:05 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.
Comment 1 Raphaël Quinet 2001-12-06 16:53:55 UTC
Created attachment 6171 [details] [review]
patch against plug-ins/common/animoptimize.c from 1.2.3-pre2
Comment 2 Raphaël Quinet 2001-12-06 16:55:52 UTC
Created attachment 6172 [details]
simple GIF animation - not optimized: 10970 bytes
Comment 3 Raphaël Quinet 2001-12-06 16:57:11 UTC
Created attachment 6174 [details]
simple GIF animation - optimized (old plug-in): 8829 bytes
Comment 4 Raphaël Quinet 2001-12-06 16:58:00 UTC
Created attachment 6175 [details]
simple GIF animation - optimized (new plug-in): 7989 bytes
Comment 5 Raphaël Quinet 2001-12-06 17:05:56 UTC
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.
Comment 6 Adam D. Moss 2001-12-06 18:34:43 UTC
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.
Comment 7 Adam D. Moss 2001-12-06 18:42:40 UTC
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
Comment 8 Adam D. Moss 2001-12-06 18:47:52 UTC
s/color/colour/g

*grin*
Comment 9 Raphaël Quinet 2001-12-07 08:12:30 UTC
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).
Comment 10 Sven Neumann 2001-12-07 13:10:45 UTC
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...)
Comment 11 Raphaël Quinet 2001-12-07 14:27:26 UTC
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.
Comment 12 Raphaël Quinet 2001-12-07 17:40:50 UTC
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.
Comment 13 Sven Neumann 2002-11-06 20:44:55 UTC
Raphael, should I apply your changes to the HEAD branch then?
Comment 14 Raphaël Quinet 2002-11-07 13:18:37 UTC
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).
Comment 15 Sven Neumann 2002-11-07 13:24:53 UTC
I'll wait then. There are lots of things with higher priority.
Comment 16 Sven Neumann 2003-04-17 13:22:33 UTC
Is anyone working on this bug?
Comment 17 Raphaël Quinet 2003-04-22 11:35:12 UTC
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.
Comment 18 Dave Neary 2003-07-24 16:07:23 UTC
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.
Comment 19 Adam D. Moss 2003-07-24 16:12:25 UTC
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.
Comment 20 Dave Neary 2003-07-25 20:09:47 UTC
Well, OK then. Raphael, would you mind posting a 1.3.17 patch, and
we'll get this closed? 

Cheers,
Dave.
Comment 21 Raphaël Quinet 2003-08-25 09:03:27 UTC
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?
Comment 22 Dave Neary 2003-08-25 10:04:44 UTC
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.
Comment 23 Dave Neary 2003-10-21 11:44:15 UTC
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.
Comment 24 Raphaël Quinet 2003-10-21 12:12:55 UTC
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?
Comment 25 Adam D. Moss 2003-10-21 12:21:35 UTC
I like (1) or (4), with a mild leaning towards (1).
Comment 26 Adam D. Moss 2003-10-21 12:27:46 UTC
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.
Comment 27 Raphaël Quinet 2003-10-21 12:35:22 UTC
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).
Comment 28 Dave Neary 2003-11-11 13:01:59 UTC
*poke*

What's the status on this, Raphael? Ready to commit something?

Cheers,
Dave.
Comment 29 Dave Neary 2003-11-19 10:54:16 UTC
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.
Comment 30 Raphaël Quinet 2003-11-19 12:37:29 UTC
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!  ;-)
Comment 31 Raphaël Quinet 2003-11-23 01:16:53 UTC
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?
Comment 32 Adam D. Moss 2003-11-23 09:28:29 UTC
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.
Comment 33 Raphaël Quinet 2003-11-23 10:46:25 UTC
Well, I will mark this as FIXED for the moment and wait for feedback
about what to do with the stable branch.
Comment 34 Sven Neumann 2003-11-26 18:45:48 UTC
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
Comment 35 Dave Neary 2003-11-26 20:27:01 UTC
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.