LZ77 engine comparison for lossless image compression

[mis...@google.com]

Hi, I worked as a summer intern for Google's compression team, and compared different LZ77 engines in lossless image compression. Last week we launched brotli, a new general purpose compression algorithm, and we anticipated that people would like to know how it performs in image compression. After all, PNG is a successful format based on zlib, and replacing zlib by brotli seems like a logical thing to do.

I used WebP lossles encoder's filtering and transform stage to generate data that was consequently fed to the LZ77 engines (gzip, zopfli, xz, and brotli). Even the best of these general purpose algorithms (a customized version of brotli) degrades the WebP lossless compression density by 2.7 %, so we concluded that simple PNG or WebP derivatives with a general purpose LZ77 engine do not provide a competitive alternative.

You can read the comparison of other compression algorithms used in this experiment as well as changes I did to brotli's context modelling to be suitable for image compression in this doc:

https://docs.google.com/document/d/1dBE6SPUbORC9I1I9gtTXwvHnfjhmthkl24fJ3uyLizQ/edit?usp=sharing

--

Mislav

[Pascal Massimino]

Hi,

Thanks for the study, Mislav!

I think it's worth copying here the main finding behind this result:

The LZ77 engine in WebP lossless uses a 2d locality for codifying distances and an entropy coding scheme that has a spatial locality in the image, and these are likely to give it a small advantage over non-image specific methods[...]

 

skal/

[oX Triangle]

i think better way to have better compression in losslessmode is to include the algos from FLIF-format
http://flif.info/

[Jyrki Alakuijala]

On Thu, Oct 29, 2015 at 6:42 PM, oX Triangle <oxdos...@googlemail.com> wrote:

i think better way to have better compression in losslessmode is to include the algos from FLIF-format
http://flif.info/

We don't know the decoding speed of an optimized implementation of FLIF yet. Right now, it is probably too slow for its density gains, and unclear if it will ever be fast.

I'd like to propose that we could further improve WebP lossless' compression ratio instead (by zopflification and other means), and keep the fast decoding speed we already have.

[paul...@gmail.com]

 Is your modified cwebp available for research purposes?  Or just the crucial diffs so I'd know where to start?

[Jyrki Alakuijala]

Consider extracting the information by adding extracting code into enc/vp8l.c EncodeImageInternal function. This function is used to store not only the main rgba image, but it may be called multiple times per encoding. The optional auxilliary spatial data such as filter selection, entropy code selection, cross color correlation parameters and the palette are also stored using this function.

The image(s) come into this function as uint32_t *argb, int width, int height. Just dump the data into files and continue from there.

--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss...@webmproject.org.
To post to this group, send email to webp-d...@webmproject.org.
Visit this group at https://groups.google.com/a/webmproject.org/group/webp-discuss/.

For more options, visit https://groups.google.com/a/webmproject.org/d/optout.