`pngwolf` uses a genetic algorithm to find PNG scanline filter combinations that compress well
C++ Makefile CMake
Pull request Compare This branch is 62 commits ahead of hoehrmann:master.
Latest commit 952f812 Sep 4, 2016 @jibsen Bump version number
Permalink
Failed to load latest commit information.
galib @ 397b614 Add GAlib, zlib, and Zopfli as git submodules Mar 9, 2016
libdeflate @ e9a956e Update submodules Sep 4, 2016
zlib @ 5089329 Add GAlib, zlib, and Zopfli as git submodules Mar 9, 2016
zopfli @ 6818a08 Update submodules Jul 11, 2016
.gitmodules Add libdeflate Jul 12, 2016
.travis.yml
CMakeLists.txt
LICENSE Add LICENSE file with GPLv3 May 6, 2015
Makefile Update optimization flags in Makefile Sep 4, 2016
Makefile.vc
README.md
appveyor.yml Add AppVeyor config Aug 19, 2016
galib247.patch Fix misplaced space in patch Jun 2, 2015
pngwolf.cxx

README.md

pngwolf-zopfli

pngwolf-zopfli is a version of pngwolf that uses Zopfli for the final compression step.

pngwolf is a tool to minimize the size of PNG image files. There are a number of factors that affect the size of PNG image files, such as the number of colors in the image and whether the image data is stored as RGBA data or in the form of references to a color palette. The main factor is the quality of the Deflate compression used to compress the image data, which is in turn affected by the quality of the compressor and how well the data to be compressed is arranged.

The PNG format supports a number of scanline filters that transform the image data by relating nearby pixels mathematically. Choosing the right filters for each scanline can make the image data more compressible. It is, however, infeasible for non-trivial images to find the best filters so typical encoders rely on a couple of heuristics to find good filters.

pngwolf employs a genetic algorithm to find better filter combinations than traditional heuristics. It derives a couple of filter combinations heuristically, adds a couple of random combinations, and then looks how well each combination compresses. Two very different combinations may compress similarily well, for instance, one combination may be very good for the first couple of scanlines, while the other may be very good for the last couple of scanlines. So taking the beginning of one combination and the tail of the other to make a new one may result in a combination that compresses better then the original two.

That is, in essence, what pngwolf does, over and over again. Further, the most widely used PNG encoders use the zlib library for compression. The zlib library favours speed over compression ratio in some cases, so whatever filters are selected to aid compression, the result with zlib may not be the smallest possible. The Zopfli library has a Deflate encoder that favours size over speed at certain settings. So, pngwolf attempts to make use of both: a fast zlib setting is used to estimate how well some filter combination aids compression, and when it gets bored, it uses Zopfli to generate the final result.

Doing this pngwolf is able to compress some images better than other optimizers (like OptiPNG, AdvanceCOMP, pngcrush, and pngout), either because it finds better filter combinations then they do, or because it uses Zopfli's Deflate implementation. It does not attempt to make other optimizations, like converting indexed images to RGB format.

None of the tools mentioned, including pngwolf follow any kind of holistic approach to PNG optimization, so to get the best results they need to be used in combination (and sometimes applying them repeatedly or in different orders provides the best results). As far as I can tell most other tools do not try to preserve the filter combination in the original image, so pngwolf should usually be used last or second-to-last in the optimization process.

For images that are already optimized using all the other tools, there is about 1% further reduction to be expected from pngwolf for suitable images. Still, it should be rare to find images on the Web that pngwolf cannot compress a little bit further.

The tool suffers from the lack of a Deflate encoder that makes it easy store the results of data analysis (where are duplicate substrings in the data) and combine them (if you recall the earlier example where it takes the head of one combination and the tail of another, an encoder would not have to analyze all of the two parts again, only where they overlap). So it can often take a long time (as in minutes) to find the best results.

Regardless of the performance deficiency pngwolf is well-suited as a research tool to come up with better heuristics for filter selection, or to extend the genetic algorithm approach to other aspects of PNG optimization (the main thing being considered is re-arranging the entries in color palettes so the image data compresses better). The tool logs extensive information in a YAML-based machine-readable format while it attempts to optimize images which should aid in that.

It also addresses two (other) user-interface issues I had in using the other tools, namely it allows you to make it stop trying to find better optimizations at well-specified points (such as the total time used), and if you start an optimization run but grow impatient and abort the program, results should not get lost, but should be stored anyway.

How to Build

To compile pngwolf-zopfli you need four additional libraries:

Put these into galib, libdeflate, zlib, and zopfli sub-directories into the directory where pngwolf.cxx is located.

galib247.patch fixes an issue in GAlib 2.4.7 when compiling with GCC and Clang, and adds parallel evaluation using OpenMP.

If you cloned the git repository, you can use git submodule update --init --recursive to retrieve these dependencies.

Use the CMake utility on the CMakeLists.txt, use one of the supplied makefiles, or simply specify all the files specified in CMakeLists.txt as input to your compiler.

License

The original pngwolf is licensed under GPLv2-or-later. The pngwolf-zopfli version as a whole is licensed under GPLv3, to allow distribution of binaries linked with Zopfli (which is licensed under the Apache License, Version 2.0).