I didn't know PNG was so simple. Encode scanlines in terms of each other, then pass the whole thing to DEFLATE... and it is effective. That's very elegant.
The other image format that's worth knowing is TIFF, because it's an insanely simple and flexible format to write out if you don't have access to a library. It lets you re-order the image data by tiles or scan lines, and lets you put various tables almost anywhere in the file, which makes it great for outputting large images from a parallel renderer: you can chop it up however is suitable for the algorithm, write out the parts to disk as you get them, and then write out a table at the end describing the order at the end of the file, without having to seek.
More details of a similar case: http://morris-photographics.com/photoshop/articles/png-gamma...
These days it's basically "what libtiff supports".
As an experiment I just opened a screenshot in Preview.app and exported to PNG with and without an alpha channel - adding alpha makes it 335KB vs 300KB. Since the alpha contains no information, there's no excuse for it to be 30KB compressed!
ffv1 or your favorite video codec with a lossless mode will produce much smaller files and decode much faster than png.
Now you've got me curious what the compression ratio would be if you just re-ordered an image's pixels using a Hilbert curve (so that in e.g. a 100x100 image, the first 100px scanline contains the first 100px of the Hilbert path through the original image) before passing it to PNG for compression.
• Lenna.png (http://i.imgur.com/pPNbiyG.png): 475KB.
• Lenna.Hilbertized.png (http://i.imgur.com/kU8C3yG.png): 709KB.
Clearly, not a good idea, at least for photographic sources.
In this case, PNG's filtering makes it kind of 2D-aware, so that probably works better on the original. But if you tried splitting it into 8x8 blocks, then predicting each one from the left-upperleft-upper neighbors, well, you'd have the basics to modern DCT codecs.
https://upload.wikimedia.org/wikipedia/commons/8/89/PNG-Grad...