flexiGIF - lossless GIF/LZW optimization

[stbrumme]

I wrote a new program called flexiGIF:

1. reduce the filesize of GIFs
2. generate GIFs that can be loaded by any GIF decoder; stay fully compatible to this three decades old file format
3. perform lossless compression, that means the result is 100% pixel-wise identical to the original file
4. support animated GIFs, too
5. sacrify tons of CPU cycles ... flexiGIF is multitudes slower than your typical GIF encoder; it often takes a few minutes to optimize a single file

On average I can shrink GIFs by about 1 to 2%.
The program Gifsicle (https://www.lcdf.org/gifsicle/) is almost always recommended as the best GIF optimizer available. flexiGIF beats it consistently.

Basically I combine two algorithms (invented by others):

• flexible positioning of the Clear Code (which resets the LZW dictionary)
• one-step-lookahead instead of greedy match finding

These two algorithms purely optimize the LZW data inside a GIF file. Everything else is kept unchanged - palette, comments, etc. remains exactly as before.

Some examples (originally from the English Wikipedia / GIF file format: https://en.wikipedia.org/wiki/GIF , the displayed GIFs are the optimized ones):



flexiGIF
55,866 bytes

gifsicle 1.91
56,739 bytes

original
56,752 bytes





flexiGIF 2018.09a (run after Gifsicle)
339,613 bytes

gifsicle 1.91
347,919 bytes

flexiGIF 2018.09a
352,615 bytes

(original)
363,021 bytes



A few hours ago I finished my 4th Berlin Marathon (inline skating) so here is a bonus picture I took in front of the German parliament (close to start/finish line):



flexiGIF 2018.09a
167,483 bytes

gifsicle 1.91
170,958 bytes

Irfanview 4.51
171,064 bytes

You can find more details on my website https://create.stephan-brumme.com/fl...-optimization/
The source code will be published soon (probably by the end of September 2018 ); it still needs some polishing.

Please no discussion about pro and cons of the GIF file format ... but if you could recommend more LZW tricks: I'm always open for new ideas !

[Shelwien]

> one-step-lookahead instead of greedy match finding

Obvious next step is full optimal parsing?

[Gonzalo]

Well, before anything, ima give you a list of reasons why you shouldn't be wasting our time with the gif format...

Nah, just kidding... It's good to see something new. Personally, I believe that the gains are too small to justify the time, practically speaking, but that is just a very personal opinion. Anyhow, projects like this can be seen more as a scientific progress because the insight gained on them can be reused later on, on other applications.

I tried precomp on the optimized files, but it logically failed. At least didn't crash; just in case anyone is interested, I'm reporting it.

Thanks for sharing the program. It would be very interesting to see something similar for other commonly used multimedia formats, like mp3 and ogg.

[dado023]

can we have this in fileoptimizer, ...would be awesome

[zubzer0]

Gonzalo for mp3 - MP3packer, lossless repackaging in VBR

[stbrumme]

Most of you guys seem to work with Windows, therefore I compiled a Windows binary (version 2108.09a-prototype) and uploaded it to my website:
https://create.stephan-brumme.com/fl...F.2018.09a.exe
(rename to flexiGIF.exe after download; this executable has no dependencies except kernel32.dll, compiled for x32)

Basic usage:
flexiGIF INPUTFILE OUTPUTFILE

There are many options and you can view them by just running flexiGIF.exe without any parameters (same as flexiGIF --help).

By default, flexiGIF analyzes block splitting at every pixel (equivalent to -a=1).
Even a coarser block splitting such as -a=64 still produces smaller files than ImageMagick, gifsicle, IrfanView and is considerably faster than -a=1.

One-step-lookahead non-greedy parsing often reduces filesize by a few bytes. The best way is just using option -p (same as --prettygood). Be aware that sometimes the resulting files are bigger because the LZW dictionary becomes suboptimal (at least one "wasted" LZW entry). This option increases computation time by factor 2 or more !

If you just want to inspect the block splitting of an existing file (without any recompression) then enter flexiGIF -i INPUTFILE

[AiZ]

Hello,

Thanks for this tool.

Unfortunately, it seems to stumble on files generated by gifski. There's always the "ERROR: too many bits left in current block" message, sometimes only the first frame is decoded and optimized (no more animation), other times not all frames are decoded but are optimized and the resulting file is invalid.

And yes, it is f*cking slow...

AiZ

[stbrumme]

... optimizing the two animated GIFs from the Gifski homepage works flawlessly on my machine:

wget https://gif.ski/demo.gif
flexiGIF demo.gif demo2.gif -a=128
=> from 5,167,147 to 5,123,819 bytes (0.8% reduction)
EDIT: option -p => 5,108,423 bytes (1.1% reduction)

wget https://gif.ski/jazz-chromecast-ultra.gif
flexiGIF jazz-chromecast-ultra.gif jazz2.gif -a=128
=> from 14,361,147 to 14,197,956 bytes (1.1% reduction)

I choose -a=128 so that conversion finshes more quickly.
It took about 30 seconds for the first video and 2 minutes for the second.

There are no errors and IrfanView displays my optimized files without any problems.

[Gonzalo]

Gonzalo for mp3 - MP3packer, lossless repackaging in VBR

Yes, I know it. Thank you the same for the reply. Sadly, it corrupted a lot of my files. They jump abruptly at the end, stopping some seconds before they should.

Most of you guys seem to work with Windows, therefore I compiled a Windows binary (version 2108.09a-prototype) and uploaded it to my website:
https://create.stephan-brumme.com/fl...F.2018.09a.exe
(rename to flexiGIF.exe after download; this executable has no dependencies except kernel32.dll, compiled for x32)

Do you need a linux compiler? I can try and make one binary for you to publish. I have an x64 Ubuntu, with both GCC 7.3 and 8.0, and clang. Maybe PM me if you don't want to release the code yet.

[stbrumme]

@Gonzalo: most of my development is done on Linux ... but I noticed that only very few people download Linux binaries (e.g. my smallz4 project).

Anyway, here is a x64 Linux binary compiled with the -static flag, should run on most distributions:
https://create.stephan-brumme.com/fl...xiGIF.2018.09a

[AiZ]

Hi,

Opened an issue for gifski (https://github.com/ImageOptim/gifski/issues/54).

I also have the same problem with some ffmpeg generated GIFs. Will do some tests later...

AiZ

[Gonzalo]

@Gonzalo: most of my development is done on Linux ... but I noticed that only very few people download Linux binaries (e.g. my smallz4 project).

Anyway, here is a x64 Linux binary compiled with the -static flag, should run on most distributions:
https://create.stephan-brumme.com/fl...xiGIF.2018.09a

Good! It is somehow ~9% faster than the windows version (same machine using wine). Maybe different compiler? I'm reporting it just in case you decide to do some optimizations, maybe you can start with the compiling toolchain, or compiler options before anything.

[SolidComp]

Have you tried lossy compression? If you're only getting a 1-2% reduction from lossless, I'd try at least a light lossy approach (maybe "visually lossless"), or something like the "near lossless" mode that Jyrki added to webp. GIFs aren't fine art – I doubt anyone would notice some lossy compression.

GIFs will be around for a few more years because of inertia and laziness, but most browsers now support Animated PNG (Firefox, Safari, and now Chrome). If Edge adds support, there would be very little need for gifs except on older platforms, since APNG is significantly more efficient/smaller.

[stbrumme]

@Shelwien: yes, obviously full optimal parsing is the "holy grail" but it seems to be much harder in LZW than simple LZ77 (such as LZ4).

@Gonzalo: Windows => Visual Studio Express, Linux => GCC, both with full optimizations

@SolidComp: tools such as GifLossy ( https://github.com/kornelski/giflossy ) do an excellent job when it comes to lossy optimization. But they all produce sub-optimal LZW bitstreams. By the way, I noticed this patent on lossy LZW compression (submitted by Adobe): https://patents.google.com/patent/US7062088

[AiZ]

Hello,

I have made some tests with:
- FFmpeg 4.0.2 (Zeranoe windows builds)
- ImageMagick 7.0.8
- gifsicle 1.89
- gifski 0.8.5
- flexiGIF 2018.09a
- XnView 2.45
- IrfanView 4.51

I have grabbed some frames of a Fasttracker II clone playing one of my favourite demos soundtrack, using ffmpeg. Then the extracted PNG files were optimized with ECT and converted to GIF files.

ffmpeg -f gdigrab -i title="Fasttracker II clone (beta #99) - \"DT.XM\"" -c:v ffv1 grab_FT2.mkv
ffmpeg -ss 00:00:03.160 -t 3.831 -i "c:\Program Files\ffmpeg-stable\files\grab_FT2.mkv" -pix_fmt rgb24 FT2_%03d.png
ect *.png
ffmpeg -framerate 30 -i FT2_%03d.png FT2_ffmpeg.gif
convert.exe -loop 0 -delay 3 FT2_*.png FT2_IM.gif
convert.exe -loop 0 -delay 3 -layers optimize FT2_*.png FT2_IM_optimize.gif

The results:
No code has to be inserted here.

You can download all PNG et GIF files here: FT2.7z.

Have a nice day,

AiZ

[AiZ]

Hi,

Updated results with flexiGIF 2018.09b:

No code has to be inserted here.

Looks good now, thanks for the modification.

AiZ

[stbrumme]

Version 2018.09b is available on my website - incl. source code and Linux & Windows binaries:
https://create.stephan-brumme.com/fl...-optimization/

Changes:
1. full source code:

git clone https://create.stephan-brumme.com/flexigif-lossless-gif-lzw-optimization/.git

no external libs required, just plain C++11 (GCC, CLang++ or MSVC 2017)

2. reduced "too many bits" from ERROR to WARNING => the program doesn't abort anymore in that case

3. there was a bug if the minimum bit size of an animated GIF varied between frames => actually the LZW code optimization was fine but the bit size of the first frame was copied to all frames which obviously causes all kind of weird errors when displayed

Edit: the forum shortens URLs. The GIT URL is create.stephan-brumme.com/flexigif-lossless-gif-lzw-optimization/.git (and prepend https:// )

[SnakeSnoke]

Those test results with shifted 1px or some artifacts are worrying me. I get the same results with XnView (give him a note when his code is buggy?), not with IrfanView or Firefox. It is already fully safe to use?
I am impressed by the improved compression, particularly since GIF is old and there are many optimizers out there for a long time.
Typically you get the best compression with "flexiGIF.2018.09b.exe -p -n", right?

Thank you for your work.
Maybe something of this can help to improve PNG as well?

[stbrumme]

Almost all GIF encoders insert a "clear code" at the beginning of the LZW bitstream. This is not a strict requirement of the specification - it says "should", not "must" ("Encoders should output a Clear code as the first code of each image data stream.", paragraph 1 in section "Compression", page 31, https://www.w3.org/Graphics/GIF/spec-gif89a.txt ).
If you use flexiGIF's command-line switch -c (or --compatible) then this extra "clear code" is added and XnView displays the file correctly.
However, this switch also resets the dictionary as soon as it's full, so it costs more than just a byte per file:

AiZ's FT2 animated GIF with parameter -a=128 (chosen instead of -a=1 to speed up encoding, takes about a minute)
219,645 bytes => broken in XnView
and with parameters -a=128 -c (note the added "compatibility switch" -c)
219,850 bytes => works fine
FT2_gifsicle_O2.gif
220,415 byte

XnView seems to always assume that the first token of the LZW bitstream is the Clear code and skips it. However, it's already a pixel in flexiGIF's output. The visual effect is that the first line is one pixel too short and its last pixel (right-most column) is the first pixel of the second line - then the second line is missing a pixel because it was used for the first line and so on.
In my opinion, this is a bug of XnView. Unfortunately it's quite likely that several GIF decoders require the initial Clear code so I'm thinking of adding several compatibility options/levels.

@SnakeSnoke: -p always implies -n

[SnakeSnoke]

Thank you for the excelellent explaination.
I will most likely stick with the compatible mode, just to be safe. Keep up the good work!

[AiZ]

Hello,

I've made another tests with flexiGIF 2018.09b. Unfortunately, adding '-c' often generates bogus animated GIFs, they stop in Firefox and show some shifting/tearing in IrfanView: it seems to be for small values of '-a=' (7 or less) with "correct" input files and bigger values (around 64 or less) with "bad" input files, these with "too many bits left in current block" messages.

Could you have a look please?

Thanks,

AiZ

[SolidComp]

Have you run any benchmarks against animated webp? That's your chief competitor.

[stbrumme]

I don't think webp/webm will replace animated GIFs - the only "competitor" is MP4 which is already supported by pretty much every browser (incl. smartphones).
In my opinion, webp won't achieve any significance because it just doesn't have any killer feature. Yes, it's a bit better than GIF/PNG/JPEG in most aspects but not to the extent that it brings a true and obvious advantage to everyday users. Even PNG never had a real breakthrough. GIF and JPEG still rule because there are a gazillion GIF/JPEG tools and every device supports those formats.
I'm pretty sure webp animations are way smaller than my animated GIFs (maybe half the size) ... at the cost of a vastly increased complexity (and higher CPU load during playback).

But that's not the main topic of this thread ... let's go back to flexiGIF.

GZIP can obviously decompress .gz files. Lesser known is: it can decompress .Z files, too. The .Z format predates .gz and was created by the "compress" tool, released in 1984. It's LZW compression with 8 to 16 bits per LZW code. GIFs are LZW compressed, too, so I thought: let's move the LZW stuff to a separate C++ class so that flexiGIF can process .Z files, too ...
It's surprisingly hard to find any information about the very simple .Z format even though it was once really popular. All I could do is read source code (very interesting: a 256-byte decoder in C: https://www.ioccc.org/2018/mills/hint.html )

The new flexiGIF code isn't stable yet. And I found a few strange edge cases in my optimizer which cause sub-optimal encodings and/or wrong output. These problems affected GIFs, too. So please stay tuned for the next release ...

Meanwhile some preliminary results for the enwik8 test file:
46,264,513 bytes (compress 4.2)
44,997,075 bytes (flexiGIF 2018.10a -a=256 -t=200000)

And for comparison:
41,913,368 bytes (LZ4 format, smallz4 -9)
36,564,135 bytes (.gz format, gzip -6)

[AiZ]

https://encode.su/threads/214-LZW-wi...ll=1#post11312

[xinix]

stbrumme
Can you optimize this Gif without a lossless?
https://hsto.org/storage2/09e/482/07...981a596a6f.gif
3044271 byte

[stbrumme]

I've seen that animation before ...
and flexiGIF saves 136 bytes using the default settings (it took about an hour ).
Below you see my optimized version (3044135 bytes).



At first glance, the animation seemed to be an ordinary GIF with a clear code after every 4093 tokens (same interval as IrfanView).

However, the GIF was created with a much smarter Video-to-GIF-converter that carefully choose the pixels based on these restart intervals.
There are very few places where a different restart interval is better (= less bytes).
Most frames of the animation are already perfectly encoded.

[xinix]

Below you see my optimized version (3044135 bytes).

Thank you.
It is possible!
_
The question remains - what is the name of this smart converter / program?
Riddle!

[skal]

Have you run any benchmarks against animated webp? That's your chief competitor.

'gif2webp -m 6 -q 100 -min_size ...' gives WebP animated files with size 3568754 bytes (44% smaller) and 10509826 bytes (36%) respectively, for the gifski demo examples.

[stbrumme]

Today I released the new version flexiGIF 2018.10a ... major changes are:
- support decoding/encoding .Z format
- parameter -p now encodes each single block with and without greedy matching and choosing the best one (output files about 0.2% smaller)
- rewrote cost estimation code which was sometimes a bit off, new code is simpler and has less bugs
- less memory consumption if parameter -a uses a value > 1 => thus possible to compress enwik9 with about 2.5 GByte RAM
- GIFs always start with a clear code to enhance compatibility (use parameter -y to skip the clear code and save a byte => old behavior)
- removed most C++11 language features

As always: Git repo and binaries can be found on my homepage:
https://create.stephan-brumme.com/fl...-optimization/

[AiZ]

stbrumme,

Your latest version (at least Windows flexiGIF.2018.10b.exe) behaves badly, optimized files are more or less severely truncated.

Could you check please ?

AiZ