Improve best-filter-per-line heuristic used in filter mode 5

[shssoichiro]

Noted via Reddit:

Here are some benchmarks I took for this.
The sample image was http://cdn.wccftech.com/wp-content/uploads/2015/03/The-Witcher-3-Wild-Hunt.png which is a 12MB 4k file.
Time:
opt-level Oxipng Optipng
2 33.01s 48.73s
3 62.01s 80.08s
4 240.07s 296.18s
Size decrease:
opt-level Oxipng Optipng
2 131049 bytes 249706 bytes
3 131049 bytes 249706 bytes
4 283777 bytes 283777 bytes

[shssoichiro]

This is related to filter mode 5. The current heuristic for picking the best filter per line in mode 5 doesn't do as good of a job as the heuristic in optipng, and worse compression is the result.

[shssoichiro]

I am having much trouble finding how optipng determines which filter to use per line in mode 5. It seems to be in libpng, but I can't find the code that libpng is using when PNG_ALL_FILTERS is set.

[shssoichiro]

Discovered this on http://www.libpng.org/pub/png/book/chapter09.html

The approach that has by now become standard is known as the minimum sum of absolute differences heuristic and was first proposed by Lee Daniel Crocker in February 1995. In this approach, the filtered bytes are treated as signed values--that is, any value over 127 is treated as negative; 128 becomes -128 and 255 becomes -1. The absolute value of each is then summed, and the filter type that produces the smallest sum is chosen. This approach effectively gives preference to sequences that are close to zero and therefore is biased against filter type None.