Page 1 of 2 12 LastLast
Results 1 to 30 of 40

Thread: flexiGIF - lossless GIF/LZW optimization

  1. #1
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts

    flexiGIF - lossless GIF/LZW optimization

    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 !

  2. Thanks (7):

    encode (16th September 2018),Gonzalo (16th September 2018),Jyrki Alakuijala (16th September 2018),necros (20th September 2018),nikkho (17th September 2018),schnaader (16th September 2018),Shelwien (16th September 2018)

  3. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    3,985
    Thanks
    299
    Thanked 1,311 Times in 747 Posts
    > one-step-lookahead instead of greedy match finding

    Obvious next step is full optimal parsing?

  4. #3
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    542
    Thanks
    239
    Thanked 93 Times in 73 Posts
    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.

  5. #4
    Member
    Join Date
    Mar 2016
    Location
    Croatia
    Posts
    193
    Thanks
    82
    Thanked 13 Times in 12 Posts
    can we have this in fileoptimizer, ...would be awesome

  6. #5
    Member
    Join Date
    Jul 2016
    Location
    Russia
    Posts
    26
    Thanks
    15
    Thanked 10 Times in 7 Posts
    Gonzalo for mp3 - MP3packer, lossless repackaging in VBR

  7. #6
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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

  8. Thanks (3):

    load (16th September 2018),Mike (17th September 2018),necros (20th September 2018)

  9. #7
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    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

  10. #8
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    ... 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.
    Last edited by stbrumme; 17th September 2018 at 12:24. Reason: ran full optimization

  11. #9
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    542
    Thanks
    239
    Thanked 93 Times in 73 Posts
    Quote Originally Posted by zubzer0 View Post
    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.

    Quote Originally Posted by stbrumme View Post
    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.

  12. #10
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    @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

  13. Thanks (2):

    Gonzalo (30th September 2018),nikkho (17th September 2018)

  14. #11
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    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

  15. #12
    Member
    Join Date
    Aug 2014
    Location
    Argentina
    Posts
    542
    Thanks
    239
    Thanked 93 Times in 73 Posts
    Quote Originally Posted by stbrumme View Post
    @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.

  16. #13
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    353
    Thanks
    131
    Thanked 54 Times in 38 Posts
    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.

  17. #14
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    @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

  18. #15
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    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.
    Code:
    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

  19. Thanks (2):

    Mike (23rd September 2018),stbrumme (23rd September 2018)

  20. #16
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    Hi,

    Updated results with flexiGIF 2018.09b:

    No code has to be inserted here.

    Looks good now, thanks for the modification.

    AiZ

  21. #17
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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:
    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:// )
    Last edited by stbrumme; 27th September 2018 at 01:56. Reason: URL

  22. Thanks (2):

    Gonzalo (28th September 2018),nikkho (27th September 2018)

  23. #18
    Member
    Join Date
    Jan 2017
    Location
    USA
    Posts
    10
    Thanks
    0
    Thanked 1 Time in 1 Post
    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?

  24. #19
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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

  25. Thanks (2):

    AiZ (30th September 2018),Mike (30th September 2018)

  26. #20
    Member
    Join Date
    Jan 2017
    Location
    USA
    Posts
    10
    Thanks
    0
    Thanked 1 Time in 1 Post
    Thank you for the excelellent explaination.
    I will most likely stick with the compatible mode, just to be safe. Keep up the good work!

  27. #21
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    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

  28. Thanks:

    stbrumme (5th October 2018)

  29. #22
    Member SolidComp's Avatar
    Join Date
    Jun 2015
    Location
    USA
    Posts
    353
    Thanks
    131
    Thanked 54 Times in 38 Posts
    Have you run any benchmarks against animated webp? That's your chief competitor.

  30. #23
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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)

  31. Thanks:

    AiZ (7th October 2018)

  32. #24

  33. Thanks:

    stbrumme (7th October 2018)

  34. #25
    Member
    Join Date
    Nov 2015
    Location
    -
    Posts
    53
    Thanks
    253
    Thanked 15 Times in 12 Posts
    stbrumme
    Can you optimize this Gif without a lossless?
    https://hsto.org/storage2/09e/482/07...981a596a6f.gif
    3044271 byte

  35. #26
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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.

  36. Thanks:

    xinix (8th October 2018)

  37. #27
    Member
    Join Date
    Nov 2015
    Location
    -
    Posts
    53
    Thanks
    253
    Thanked 15 Times in 12 Posts
    Quote Originally Posted by stbrumme View Post
    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!

  38. #28
    Member
    Join Date
    Nov 2011
    Location
    france
    Posts
    75
    Thanks
    8
    Thanked 40 Times in 29 Posts
    Quote Originally Posted by SolidComp View Post
    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.

  39. #29
    Member
    Join Date
    Mar 2013
    Location
    Berlin
    Posts
    47
    Thanks
    14
    Thanked 73 Times in 32 Posts
    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/

  40. Thanks (3):

    Mike (16th October 2018),nikkho (16th October 2018),xinix (16th October 2018)

  41. #30
    Member
    Join Date
    May 2009
    Location
    France
    Posts
    99
    Thanks
    13
    Thanked 75 Times in 45 Posts
    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

Page 1 of 2 12 LastLast

Similar Threads

  1. (Looking for) lossless optimization for various media formats
    By Lichtgestalt in forum Data Compression
    Replies: 3
    Last Post: 14th March 2017, 18:42
  2. Replies: 7
    Last Post: 24th June 2016, 15:07
  3. JPG,GIF,MP3 to BMP, WAV
    By necros in forum Data Compression
    Replies: 8
    Last Post: 20th March 2016, 19:49
  4. GIF optimization
    By lorents17 in forum Data Compression
    Replies: 9
    Last Post: 27th July 2013, 19:57
  5. unsupported Gif verient for Precomp
    By maadjordan in forum Data Compression
    Replies: 3
    Last Post: 16th May 2008, 21:14

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •