PNG Filters
The five filters a PNG may apply to a scanline remove nothing, store nothing, and leave the data exactly as long as they found it. They are not the compression. They rewrite the bytes so that the thing which runs afterwards can do its job, and whether that worked is invisible unless you run a real compressor and look at the byte count both ways. This page runs one, the browser's own. Then it asks the question the specification quietly declines to answer about its own recommendation.
New to how lossless image compression works? Start here
A general-purpose compressor finds repetition. It shrinks a file by noticing that a run of bytes has occurred before and referring back to it instead of writing it again. That works well on text and badly on a photograph or a gradient, where almost no exact sequence of bytes ever repeats even though the picture is extremely predictable.
So a format like PNG does something before compressing. It replaces each byte with the difference between that byte and a prediction made from its neighbours, which turns a smooth gradient into a long run of the same small number. The compressor then finds exactly the repetition it is good at. The transform itself removes nothing and stores nothing; it is reversible and it is the same length. That split is what this page is about.
Only patterns can be spent
A file gets smaller for one of two reasons. Something in it repeats, so the second copy can be a note saying where the first one was. Or some symbols are commoner than others, so the common ones can be given shorter codes and the rare ones longer.
Both are spending a pattern, and a pattern can only be spent once. Compress a compressed file and nothing happens, because the first pass already took what was there. That is also why nothing compresses everything: shortening some inputs must lengthen others, and the machines here are choosing which inputs to be good at.
The machine for this idea on its own is Huffman, if you would rather press it than read about it.
The compression happens after something else has made the bytes boring
1 One scanline, put through each of the five filters the format defines
One scanline, put through each of the five filters RFC 2083 defines. The residual bytes are shown as the signed differences the specification says to read them as. Nothing has been compressed yet and nothing has been thrown away: every row below is exactly as long as the row above it.
| filter | the byte, minus | first bytes out | sum of absolute values |
|---|
2 The residual bytes those filters produce, handed to the compressor that is the only thing here that compresses anything
Now the whole image, with a filter chosen per line, handed to the only thing here that compresses anything. The deflate is your browser's own, through CompressionStream: these byte counts were produced on this device a moment ago and another browser may differ by a byte or two.
| what is compressed | bytes in | deflated to | zero-order entropy |
|---|
3 The choice of which filter to use per line, made by the specification's own heuristic and then by brute force, which do not always agree
The image is five scanlines here rather than the eight above, because every assignment of a filter to every line is 5^5 = 3,125 possibilities at five lines and 5^8 = 390,625 at eight, and only one of those is a search a phone should be asked to run. RFC 2083 recommends choosing the filter with the smallest sum of absolute values, and in the same paragraph says "it is likely that much better heuristics will be found as more experience is gained with PNG". So here is the heuristic against an exhaustive search of every assignment of a filter to every line, and then both of them handed to the real compressor.
| chosen by | filter per line | entropy | deflated to |
|---|
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every filter reverses exactly, on every image, with nothing left over | yes | 25 image-and-filter combinations filtered and reconstructed, all byte-identical to what went in |
| filtering compresses nothing: the stream is the image plus one byte per line | yes | 24 x 8 is 192 bytes and the filtered stream is 200, which is those bytes plus 8 filter-type bytes; nothing was removed and nothing stored |
| the tie-break order is load-bearing, though not at the tie the specification's note is about | yes | over 117,649 triples, breaking ties toward upper-left instead changes the prediction 1,504 times. The left-before-above tie the RFC's note names arises 0 times, because equal distances to left and above make the distance to upper-left zero, and upper-left then wins outright |
| the predictor always returns one of the three bytes it was given | yes | 140,608 triples, and the answer is always left, above or upper-left; it never averages them, which is why a decoder that has those three bytes can invert it exactly |
| the filter's whole job is to make the bytes repetitive, and that is measurable | yes | the raw gradient carries 880 bits of zero-order entropy and the filtered stream carries 164; the picture is unchanged, and the bytes describing it have become almost all one value |
| on data nothing predicts, filtering does not help and can hurt | yes | random bytes carry 1329 bits before filtering and 1375 after; there is no prediction to make, so the difference from a wrong guess is as unpredictable as what it replaced |
| no single filter is the right one, which is the reason for choosing per scanline | yes | gradient-x wants Paeth, gradient-y wants Paeth, diagonal wants Paeth, flat wants None, noise wants Sub |
| the specification's own heuristic is not the best assignment available | yes | the heuristic picks [1,1,2,2,2] and an exhaustive search of all 3125 assignments picks [4,4,4,4,4], at 157 bits against 162; the RFC says as much itself, that better heuristics will be found |
| entropy is a bound and not a file size, and the file sizes on this page come from a real compressor | yes | the numbers computed here treat each byte independently, which deflate does not: it finds repeated sequences as well. The compressed sizes shown on the page are produced by the browser's own deflate through CompressionStream, and the exhaustive search against real deflate output runs in this machine's test suite rather than here |
| these are the numbers for these images and not for photographs | yes | a gradient is the best case for filtering and random bytes are the worst; a photograph is somewhere between and nothing here measures one. No general claim about PNG compression ratios is made or implied by any figure on this page |
What is real here, and what is not
These are the numbers for these images and not for photographs
A ramp is the best case for filtering and random bytes are the worst. A photograph is somewhere in between and nothing on this page measures one, so no figure here supports any claim about PNG compression ratios in general. The images are small and synthetic on purpose, because the point being made is about the mechanism and a small image makes every intermediate byte visible.
The deflate is your browser's, and another one may give a different byte count
The compressed sizes are produced on this device by CompressionStream, which is the platform's own zlib at whatever settings the platform chose. A different browser, or the same browser next year, may produce a stream a byte or two different. Nothing on this page turns on the exact value; what it turns on is the comparison, and both sides of every comparison are compressed by the same compressor a moment apart.
Zero-order entropy is a bound, not a file size
The entropy figures treat each byte as independent, which is exactly what deflate does not do -- it finds repeated sequences too, and that is most of its advantage on filtered data. Entropy is here because it can be computed exactly and synchronously, so the exhaustive search has something to rank by. It always sits beside the real compressed size rather than standing in for it.
The exhaustive search is exhaustive over a five-line image and nothing larger
Every assignment of one of five filters to each of five lines is 3,125 possibilities, which is a search. Every assignment for a hundred-line image is a number with seventy digits in it, which is not. The page refuses to run the search above a height where it would stop being exhaustive rather than quietly sampling and calling it a search. The same comparison against real deflate output, at every one of the 3,125, runs in this machine's test suite.
Eight-bit greyscale is the simplest case and colour is not the same
With one byte per pixel, the byte to the left is the previous pixel. With three or four bytes per pixel the filters work on the byte the same distance back, so Sub compares a red to the previous red rather than to a green, and the specification is careful about it. Everything here is one byte per pixel, which makes the arithmetic legible and leaves out a real complication.
The tie-break note in the specification protects a tie that cannot happen
RFC 2083 says the Paeth tie-break order -- left, then above, then upper-left -- is critical and must not be altered, and notes it differs from Paeth's own article. Sweeping every triple of bytes shows that the left-versus-above tie the note names never arises: if those two distances are equal then the distance to upper-left is zero, so upper-left wins outright. The order that is load-bearing is where upper-left sits in the list, and changing that does change the prediction. The requirement is right; the reason given for it is not the one that bites.
Sources
- T. Boutell, ed., PNG (Portable Network Graphics) Specification, RFC 2083, March 1997; section 6 for the five filters and the PaethPredictor, section 9.6 for the recommended per-scanline heuristic.
- PNG (Portable Network Graphics) Specification Version 1.0, W3C Recommendation 01-October-1996, as mirrored by the PNG Development Group; RFC 2083 published the same specification in March 1997.
- Logical Art, the studio this belongs to.