6 ms·

Finally Understanding PNG (2017)

125 points by Asdrubalini 5y ago

sprash 5y ago
As additional strategy for reducing PNG sizes losslessly not mentioned in the article is the brute force optimization of the DEFLATE compression algorithm (via zopflipng). This gives you usually a few percent improvement for "free".
drsopp 5y ago
> A PNG is compressed in three steps: pre-filtering, dictionary-based coding via LZ77, and finally entropy coding according to a certain Mr. Huffman. Huffman was a Doctor of Science. Also, (2017). Edit: Couldn't OP's email. I don't have Twitter.
masklinn 5y ago
> This is due to the fact that the specification of the PNG has a sliding window of 32 kB for performance reasons. It’s a bit of a shortcut: in reality PNG uses DEFLATE, and it’s DEFLATE which has a 32kB window. And it’s not exactly performance reasons but memory budget, especially as deflate was designed for streaming, both when compressing and decompressing: when decompressing you need a buffer at least as large as the window, and when compressing you need that plus most likely an index of some sort (so you don’t have to look for matches linearly through the buffer). This is more relevant with the context that Phil Katz created deflate in 1991, high-end desktops reached high single-digit megabytes of RAM but the low end might not even be there (Windows 3.0 required 1MB to run decently). By comparison, if memory serves zstd uses a window of 8MB (or 16 depending on setting), though configurable anywhere from 1k to 512MB
- userbinator 5y ago
  ...and 32k allows the buffer to fit into a single 64k segment along with the Huffman tables, no doubt a useful property at the time. Deflate is actually very similar to LZH, and there are small extensions to both which make the window 64k; but in my experience it doesn't provide all that much extra compression (few percent.)
  - magicalhippo 5y ago
    > no doubt a useful property at the time For reference: https://en.wikipedia.org/wiki/X86_memory_segmentation#Real_mode https://en.wikipedia.org/wiki/X86_memory_segmentation#Real_m...
- jandrese 5y ago
  I find it amusing when reading the docs on compression programs and seeing statements like "Compression level of -9 should be used with caution as it can consume over 8 megabytes of main memory".
acqq 5y ago
I'm old enough to find that it must be noted: "HDD" was never used for diskettes, even the "high density" ones. HDD: https://en.wikipedia.org/wiki/Hard_disk_drive https://en.wikipedia.org/wiki/Hard_disk_drive Diskettes: https://en.wikipedia.org/wiki/Floppy_disk#3+1%E2%81%842-inch_disk https://en.wikipedia.org/wiki/Floppy_disk#3+1%E2%81%842-inch... I'm commenting "HDD" as written in: "1.44 MB. This is also pretty much the size of an uncompressed BMP image (and incidentally the size of a 3.5 " HDD ... for all who can still remember" in the current text of the article.
- H8crilA 5y ago
  Low quality/tangential comment: It was a floppy disk, not a hard disk. The magnetic surface in an FDD disk is floppy the magnetic surface in a HDD is hard (rigid).
  - afavour 5y ago
    > The magnetic surface in an FDD disk is floppy the magnetic surface in a HDD is hard Maybe I'm wrong but I was under the impression that a "floppy" was called that because the original ones - 5.25", were floppy.
    - H8crilA 5y ago
      The 3.5" also had a floppy disk inside, only surrounded with a plastic rigid case.
    - pansa2 5y ago
      > the original ones - 5.25" Nitpick: The first floppy disks were 8" in size.
    - tym0 5y ago
      Even the 3.5" were floppy inside, they just had a hard case around it.
    - lonelygirl15a 5y ago
      "Floppy" refers to the media, not the packaging; some (3.5") had harder plastic shells, but inside was the same floppy plastic material. Hard disk platters were/are rigid (metal or glass).
blowski 5y ago
I learned a lot from that, thank you. I wonder how much bandwidth I've wasted for people over the years because I've saved poorly optimised versions from Photoshop. Are there automated tools that can be included in a CI pipeline to help with this?
- karim79 5y ago
  The https://kraken.io https://kraken.io service has an API, and there's a gulp and grunt plugin and a bunch of other stuff here: https://kraken.io/docs/integration-libraries https://kraken.io/docs/integration-libraries
  - blowski 5y ago
    That looks perfect, except for it being a SaaS product with a minimum monthly spend. Is there a similar pay-as-you-go model, or ideally self-hosted?
    - karim79 5y ago
      Good question - not at the moment, but we're evaluating the idea. Perhaps the answer would be to just make the build pipeline tools free for developers to a certain limit.
    - aargh_aargh 5y ago
      Wait, why not optipng [1], pngcrush [2] or any other of the handful of locally running lossless PNG optimizers [3]? [1] https://packages.debian.org/unstable/optipng [2] https://packages.debian.org/unstable/pngcrush [3] http://www.olegkikin.com/png_optimizers/
      - blowski 5y ago
        Do they do what the article is recommending? Genuine question, I don't know the answer.
        5y ago
deleted 5y ago
[deleted]
TonyTrapp 5y ago
> These filters are the reason why the PNG is a nose ahead of the GIF format and is therefore almost always smaller Not really. I found that for many many many pictures, not using a filter turns out to be the smallest option. It's really just that DEFLATE is much better than LZW as used by GIF.
nayuki 5y ago
This article talks about understanding the PNG pixel data and compression, which is wonderful. Recently I made a tool to understand another aspect of the PNG file format, which is the full list of chunks, metadata chunks, and chunk fields. https://www.nayuki.io/page/png-file-chunk-inspector https://www.nayuki.io/page/png-file-chunk-inspector
userbinator 5y ago
Finding the optimal filter for each line is a science in itself, which, of course, could be approached with brute computer power. But since you probably do not want to wait a week in front of your computer, until the PNG is finally calculated, the filters are selected by experience values and assumptions. That paragraph makes it sound like this article was written two decades ago. pngcrush, which does bruteforce, still takes only a minute or two on average (less than screen-sized) files.
- tialaramex 5y ago
  pngcrush doesn't actually brute force, for exactly the reason the article gives, it would take too long. Instead, pngcrush is using yet more heuristics to guess what else is likely to work and then trying some of the other options that wouldn't be picked by the defaults. By default it only tries a few approaches that it deems most likely to work, but even with the "brute" parameter it does not truly try everything, again, that would take too long, and pngcrush "brute" is already very slow, it just tries all the methods it would ever have used on any image. Actual brute force of a relatively tiny 32x32 image would require trying all five filters for each line in combination with each such filter for each other line or else you might miss a combination which, astonishingly, was smaller even though it wasn't immediately obvious why. I think that's 5 raised to the power 32 combinations.
  - magicalhippo 5y ago
    It could also use a look-ahead scheme. That is, cloning the compression state, compressing the current line for each of the different filters, retaining the state that lead to the highest compression and discarding the others. This could be trivially extended to multiple lines of look-ahead, though at exponential memory and CPU cost. Probably dog slow though.
    - tialaramex 5y ago
      The simplest of these schemes is pretty fast, only five times slower than the naive approach. But it absolutely doesn't give you the benefit from trying all the combinations and I expect it will produce worse results than existing tools. The problem is, while you know which outputs compressed best so far you can't be sure which will compress best in combination with future outputs you haven't as yet filtered. Imagine for example that one filter for the current row gives what seems like a random sequence that doesn't compress very well. Your proposed scheme rejects this filter, it compressed poorly, so don't use it. But, what if it turns out that every future row can be compressed to the exact same sequence with some other filter? Deflate can compress the rows extremely well together, even though the first one on its own did not compress.
UglyToad 5y ago
At some point I'm going to get round to adding heuristic filter selection to my PNG library BigGustave [0]. I have a TODO note for how to start implementing it. Though to be honest using Palette for colors tends to produce a huge saving for a lot of image types (those with 256 or fewer colors, so documents, not natural scenes) making filter selection a small added bonus. [0]: https://github.com/EliotJones/BigGustave/blob/master/src/BigGustave/PngBuilder.cs#L504 https://github.com/EliotJones/BigGustave/blob/master/src/Big...
ericpauley 5y ago
Nit: it was somewhat disingenuous that the first two images aren't actually encoding the same results, since noise was added to the right image to accentuate the paletting effects. If the image on the right didn't have noise the effect would be far less pronounced.
Hamuko 5y ago
Fun PNG fact: the official pronunciation of "PNG" is actually "ping": http://www.libpng.org/pub/png/spec/iso/index-object.html#1Scope http://www.libpng.org/pub/png/spec/iso/index-object.html#1Sc... I imagine there won't be a mainstream culture war over it like there is with GIF and JIF though.
huachimingo 5y ago
Pico-8 has its cartridge format on a custom PNG.
the2ndfloorguy 5y ago
Wonderful article.
ferrar65 5y ago
OMG, your post was very interesting.
ferrar65 5y ago
Thanks, your post was very interesting.

125 points by Asdrubalini 5y ago

As additional strategy for reducing PNG sizes losslessly not mentioned in the article is the brute force optimization of the DEFLATE compression algorithm (via zopflipng). This gives you usually a few percent improvement for "free".

drsopp 5y ago

> A PNG is compressed in three steps: pre-filtering, dictionary-based coding via LZ77, and finally entropy coding according to a certain Mr. Huffman. Huffman was a Doctor of Science. Also, (2017). Edit: Couldn't OP's email. I don't have Twitter.

masklinn 5y ago

> This is due to the fact that the specification of the PNG has a sliding window of 32 kB for performance reasons. It’s a bit of a shortcut: in reality PNG uses DEFLATE, and it’s DEFLATE which has a 32kB window. And it’s not exactly performance reasons but memory budget, especially as deflate was designed for streaming, both when compressing and decompressing: when decompressing you need a buffer at least as large as the window, and when compressing you need that plus most likely an index of some sort (so you don’t have to look for matches linearly through the buffer). This is more relevant with the context that Phil Katz created deflate in 1991, high-end desktops reached high single-digit megabytes of RAM but the low end might not even be there (Windows 3.0 required 1MB to run decently). By comparison, if memory serves zstd uses a window of 8MB (or 16 depending on setting), though configurable anywhere from 1k to 512MB

userbinator 5y ago
...and 32k allows the buffer to fit into a single 64k segment along with the Huffman tables, no doubt a useful property at the time. Deflate is actually very similar to LZH, and there are small extensions to both which make the window 64k; but in my experience it doesn't provide all that much extra compression (few percent.)
- magicalhippo 5y ago
  > no doubt a useful property at the time For reference: https://en.wikipedia.org/wiki/X86_memory_segmentation#Real_mode https://en.wikipedia.org/wiki/X86_memory_segmentation#Real_m...
jandrese 5y ago
I find it amusing when reading the docs on compression programs and seeing statements like "Compression level of -9 should be used with caution as it can consume over 8 megabytes of main memory".

acqq 5y ago

I'm old enough to find that it must be noted: "HDD" was never used for diskettes, even the "high density" ones. HDD: https://en.wikipedia.org/wiki/Hard_disk_drive https://en.wikipedia.org/wiki/Hard_disk_drive Diskettes: https://en.wikipedia.org/wiki/Floppy_disk#3+1%E2%81%842-inch_disk https://en.wikipedia.org/wiki/Floppy_disk#3+1%E2%81%842-inch... I'm commenting "HDD" as written in: "1.44 MB. This is also pretty much the size of an uncompressed BMP image (and incidentally the size of a 3.5 " HDD ... for all who can still remember" in the current text of the article.

H8crilA 5y ago
Low quality/tangential comment: It was a floppy disk, not a hard disk. The magnetic surface in an FDD disk is floppy the magnetic surface in a HDD is hard (rigid).
- afavour 5y ago
  > The magnetic surface in an FDD disk is floppy the magnetic surface in a HDD is hard Maybe I'm wrong but I was under the impression that a "floppy" was called that because the original ones - 5.25", were floppy.
  - H8crilA 5y ago
    The 3.5" also had a floppy disk inside, only surrounded with a plastic rigid case.
  - pansa2 5y ago
    > the original ones - 5.25" Nitpick: The first floppy disks were 8" in size.
  - tym0 5y ago
    Even the 3.5" were floppy inside, they just had a hard case around it.
  - lonelygirl15a 5y ago
    "Floppy" refers to the media, not the packaging; some (3.5") had harder plastic shells, but inside was the same floppy plastic material. Hard disk platters were/are rigid (metal or glass).

blowski 5y ago

I learned a lot from that, thank you. I wonder how much bandwidth I've wasted for people over the years because I've saved poorly optimised versions from Photoshop. Are there automated tools that can be included in a CI pipeline to help with this?

karim79 5y ago
The https://kraken.io https://kraken.io service has an API, and there's a gulp and grunt plugin and a bunch of other stuff here: https://kraken.io/docs/integration-libraries https://kraken.io/docs/integration-libraries
- blowski 5y ago
  That looks perfect, except for it being a SaaS product with a minimum monthly spend. Is there a similar pay-as-you-go model, or ideally self-hosted?
  - karim79 5y ago
    Good question - not at the moment, but we're evaluating the idea. Perhaps the answer would be to just make the build pipeline tools free for developers to a certain limit.
  - aargh_aargh 5y ago
    Wait, why not optipng [1], pngcrush [2] or any other of the handful of locally running lossless PNG optimizers [3]? [1] https://packages.debian.org/unstable/optipng [2] https://packages.debian.org/unstable/pngcrush [3] http://www.olegkikin.com/png_optimizers/
    - blowski 5y ago
      Do they do what the article is recommending? Genuine question, I don't know the answer.
      - 5y ago

deleted 5y ago

[deleted]

TonyTrapp 5y ago

> These filters are the reason why the PNG is a nose ahead of the GIF format and is therefore almost always smaller Not really. I found that for many many many pictures, not using a filter turns out to be the smallest option. It's really just that DEFLATE is much better than LZW as used by GIF.

nayuki 5y ago

This article talks about understanding the PNG pixel data and compression, which is wonderful. Recently I made a tool to understand another aspect of the PNG file format, which is the full list of chunks, metadata chunks, and chunk fields. https://www.nayuki.io/page/png-file-chunk-inspector https://www.nayuki.io/page/png-file-chunk-inspector

userbinator 5y ago

Finding the optimal filter for each line is a science in itself, which, of course, could be approached with brute computer power. But since you probably do not want to wait a week in front of your computer, until the PNG is finally calculated, the filters are selected by experience values and assumptions. That paragraph makes it sound like this article was written two decades ago. pngcrush, which does bruteforce, still takes only a minute or two on average (less than screen-sized) files.

tialaramex 5y ago
pngcrush doesn't actually brute force, for exactly the reason the article gives, it would take too long. Instead, pngcrush is using yet more heuristics to guess what else is likely to work and then trying some of the other options that wouldn't be picked by the defaults. By default it only tries a few approaches that it deems most likely to work, but even with the "brute" parameter it does not truly try everything, again, that would take too long, and pngcrush "brute" is already very slow, it just tries all the methods it would ever have used on any image. Actual brute force of a relatively tiny 32x32 image would require trying all five filters for each line in combination with each such filter for each other line or else you might miss a combination which, astonishingly, was smaller even though it wasn't immediately obvious why. I think that's 5 raised to the power 32 combinations.
- magicalhippo 5y ago
  It could also use a look-ahead scheme. That is, cloning the compression state, compressing the current line for each of the different filters, retaining the state that lead to the highest compression and discarding the others. This could be trivially extended to multiple lines of look-ahead, though at exponential memory and CPU cost. Probably dog slow though.
  - tialaramex 5y ago
    The simplest of these schemes is pretty fast, only five times slower than the naive approach. But it absolutely doesn't give you the benefit from trying all the combinations and I expect it will produce worse results than existing tools. The problem is, while you know which outputs compressed best so far you can't be sure which will compress best in combination with future outputs you haven't as yet filtered. Imagine for example that one filter for the current row gives what seems like a random sequence that doesn't compress very well. Your proposed scheme rejects this filter, it compressed poorly, so don't use it. But, what if it turns out that every future row can be compressed to the exact same sequence with some other filter? Deflate can compress the rows extremely well together, even though the first one on its own did not compress.

UglyToad 5y ago

At some point I'm going to get round to adding heuristic filter selection to my PNG library BigGustave [0]. I have a TODO note for how to start implementing it. Though to be honest using Palette for colors tends to produce a huge saving for a lot of image types (those with 256 or fewer colors, so documents, not natural scenes) making filter selection a small added bonus. [0]: https://github.com/EliotJones/BigGustave/blob/master/src/BigGustave/PngBuilder.cs#L504 https://github.com/EliotJones/BigGustave/blob/master/src/Big...

ericpauley 5y ago

Nit: it was somewhat disingenuous that the first two images aren't actually encoding the same results, since noise was added to the right image to accentuate the paletting effects. If the image on the right didn't have noise the effect would be far less pronounced.

Hamuko 5y ago

Fun PNG fact: the official pronunciation of "PNG" is actually "ping": http://www.libpng.org/pub/png/spec/iso/index-object.html#1Scope http://www.libpng.org/pub/png/spec/iso/index-object.html#1Sc... I imagine there won't be a mainstream culture war over it like there is with GIF and JIF though.

huachimingo 5y ago

Pico-8 has its cartridge format on a custom PNG.

the2ndfloorguy 5y ago

Wonderful article.

ferrar65 5y ago

OMG, your post was very interesting.

ferrar65 5y ago

Thanks, your post was very interesting.