Adaptive PNG filtering made my animations 2.4x bigger

I added adaptive per-scanline filtering to an APNG encoder, because that is what
you are supposed to do. PNG lets every row pick one of five filters, the spec
suggests picking the one that minimises the sum of absolute differences, and
every PNG optimiser I have read does exactly that.

It made seven of eight real animations bigger. The worst went up 2.41x.

Here is the whole set. Same frames, same zlib level, same encoder; the only
difference is whether each scanline gets a filter chosen for it or is left at
filter None.

file	frames	canvas	None	adaptive	ratio
Cicada molting	51	320x512	6142.9 KB	14786.8 KB	2.41x
Zipper	15	320x320	278.9 KB	520.0 KB	1.86x
Foucault pendulum	288	180x240	5953.8 KB	10492.0 KB	1.76x
Universal joint	60	280x164	678.1 KB	1148.0 KB	1.69x
Lockstitch	18	419x500	197.3 KB	311.9 KB	1.58x
Gun turret	70	700x600	1108.6 KB	1590.2 KB	1.43x
Muybridge race horse	15	300x200	687.0 KB	731.9 KB	1.07x
Lunar libration	56	640x642	10939.2 KB	9129.3 KB	0.83x

Eight animations from Wikimedia, decoded to full-canvas RGBA and re-encoded as
APNG. One file got smaller. Seven got bigger, and Cicada molting went from
6 MB to 14.5 MB.

Three explanations that sound right

The first thing I did was write down why, which in hindsight was the mistake.
The story I wrote into the source comment was this: flat art has whole scanlines
that repeat, filter None leaves those repeats byte-identical so LZ77 can match
one row against another across the image, and mixing filter types per row
rewrites identical rows into different bytes and destroys the long matches.

It is a good story. It is also wrong, and it took one number to find out. I
measured the fraction of scanlines that are byte-identical to the row above
them:

file	repeated rows	ratio
Lockstitch	39.1%	1.58x
Gun turret	20.2%	1.43x
Lunar libration	11.2%	0.83x
Universal joint	4.8%	1.69x
Cicada molting	0.0%	2.41x
Foucault pendulum	0.0%	1.76x
Muybridge race horse	0.0%	1.07x
Zipper	0.0%	1.86x

The worst file in the set has no repeated scanlines at all. Across all 28 pairs
of files, "more repeated rows" predicted "worse adaptive result" in 6 of them —
a rule that explains nothing lands near 14.

Two more candidates went the same way. Palette size, on the theory that flat art
means few colours: 10 of 28 pairs, and the best and worst files sit at 190 and
183 colours. How much the heuristic switches filter type between adjacent rows,
on the theory that the thrashing is what costs: 14 of 28, which is exactly
chance.

At that point I had a real result and three dead explanations, which is a
reasonable place to stop guessing and run an experiment.

The experiment that settles it

If the damage comes from choosing differently per row, then holding one filter
constant for the whole image should be fine. If the damage comes from
differencing at all, then any fixed filter loses too.

So I forced each of the five filters on every scanline:

file	None	Sub	Up	Average	Paeth	heuristic
Cicada molting	1.00x	1.59x	1.83x	2.43x	2.22x	2.41x
Zipper	1.00x	1.48x	1.63x	2.08x	1.75x	1.86x
Foucault pendulum	1.00x	1.39x	1.72x	2.28x	1.74x	1.76x
Universal joint	1.00x	1.48x	1.74x	2.12x	1.79x	1.69x
Gun turret	1.00x	1.42x	1.37x	2.09x	1.46x	1.43x
Muybridge race horse	1.00x	1.07x	1.10x	1.07x	1.06x	1.07x
Lunar libration	1.00x	0.90x	0.86x	0.83x	0.86x	0.83x

Every fixed filter loses on the same seven files, by roughly as much as the
heuristic does. It is not the switching. It is the differencing.

And look at the last row. On Lunar libration — the one continuous-tone source in
the set — every single differencing filter wins. The textbook advice is not
wrong. It is right about a kind of image, and seven of these eight are the other
kind.

Why the heuristic cannot see this

Minimum sum of absolute differences scores byte magnitude. DEFLATE pays for
repetition. On these frames those two things point in opposite directions.

A run of identical pixels under filter None is a run of identical bytes, which
is the single thing LZ77 is best at. Under Sub it becomes a run of zeros, which
also compresses, but the moment the run ends the boundary value depends on
whatever came before, and across an image made of flat regions with hard edges
you end up with many small, varying values instead of a few long, identical
runs. Small varying bytes win on sum-of-absolute-differences. Long identical
runs win on file size.

The heuristic never finds out, because it is not measuring file size. Its
preference is visible in how often it leaves a row alone:

rows the heuristic assigned filter None: 0.0% to 0.2%

Zero to two rows in a thousand, on files where keeping every row at None is
2.4x smaller. The rule is not slightly miscalibrated. It essentially never
selects the winning option, because the winning option almost never has the
lowest sum of absolute differences.

The fix

One extra compression per animation. Encode frame 0 both ways, keep the
strategy that produced fewer bytes, use it for every frame:

const probe = frames[0];
const adaptive =
  compress(probe.data, width, height, level, true).length <
  compress(probe.data, width, height, level, false).length;

Not per frame. The frames of one animation are the same kind of picture, so the
winner on the first is the winner throughout, and paying double on every frame
to re-confirm that is the expensive way to learn nothing. Cost: one additional
compress of one frame.

This also keeps the win where the win is real. Lunar libration still gets its
0.83x, because the probe finds it.

The bug in the measurement, which is the part I would want to read

The forced-filter table above did not work the first time. It came out like
this:

every row forced to one filter:
  None 1.43x  Sub 1.43x  Up 1.43x  Average 1.43x  Paeth 1.43x

Five identical numbers. It would have been easy to squint at that and write
something about how the filter choice barely matters — except that the first
column cannot be 1.43x. Forcing filter None is the None encoder. That column
is 1.00x by definition, and any other value means the measurement is not
measuring what it says.

The cause: the harness builds each variant by copying the encoder to a temp file
with one line replaced, and all five forced variants were written to the same
filename. Node caches modules by URL, so the second import never sees the new
bytes. Every column was the same build.

The fix was a unique filename. The lesson was the assertion that now runs before
anything is printed:

if (Math.abs(fixed[0] / n - 1) > 0.001) {
  console.error(`forcing did not take: forced-None is ${fixed[0] / n}x of None`);
  process.exit(3);
}

A measurement harness should contain at least one case whose answer you already
know, and it should refuse to report anything if that case comes out wrong. This
one produced a plausible, publishable, completely fictitious result until it had
one.

What I would take from this

Three things, in order of how much they cost me:

1. A mechanism you have not measured is a guess with a diagram. I wrote the LZ77-across-identical-scanlines explanation into a source comment as fact. The worst file in the set has 0.0% identical scanlines. It sat there being confidently wrong until something made me check it.
2. When two explanations disagree, force each one and see. Three correlational metrics gave me nothing. One experiment — hold the filter constant — answered it in a single run.
3. Optimisation folklore is usually true about a specific input distribution and silent about which one. Adaptive PNG filtering is right for photographs and wrong for palette art, and nothing in the advice says so.

The encoder runs in the browser, in the GIF tools on
Image Machine — the measurements above come from
the GIF to APNG converter,
where a 6 MB upload coming back as 14.5 MB is the kind of thing a user notices
immediately. Nothing is uploaded; the whole pipeline is client side, which is
also why the encoder's own efficiency is the only lever there is.