Comment by crazygringo | Hacker News Reader

Comment by crazygringo | Hacker News Reader

Parent Full thread

This post doesn't make any sense. First of all, the premise itself is flawed:

> Image compression algorithms are, generally, pretty good at finding patterns in images and squashing them down.

No, image compression algorithms are generally terrible at finding patterns. Lossless ones are basically just ZIP, while lossy ones don't really find patterns -- they remove certain high-frequency data and reduce color information. (There are certain patterns that PNG can efficiently detect, like repeating pixels from the line above, but those won't apply to text represented as an image.)

> Here's what it looks like when losslessly compressed to a PNG: It is slightly smaller than ZIP, and about 9 bytes larger than Brotli compression.

This is certainly entirely explained by the chosen (in this case, default) compression level of the ZIP file and PNG files. Lossless PNG generally uses the ZIP algorithm, or variants. Which is why the end result is basically identical.

> Lossless ones are basically just ZIP

Lossless image compression is a vast field with myriad different requirements and solutions, and generalizing like that is just plain wrong. Most lossless image codecs for photographic or similar rendered content don't use a Lempel-Ziv stage like PNG does, they exploit the spatial and possibly spectral correlations to form predictions, be it with simple linear predictors or more complex approaches. However, for simple non-photographic images like cartoons or some such, the LZ-based stage can provide significantly better compression than the simpler prediction-based methods.

Even if the premise of the post is flawed, it's always nice to see people interested in data compression and trying to learn more about it, so I'm all for more "nonsense" posts if it helps draw attention to the field.

I could have been more specific -- I meant the currently common lossless formats of GIF, PNG and TIFF. In other words, I was just thinking about lossless image compression available to the average user.

It's true there are newcomers. WebP is slightly more advanced in lossless mode but still follows the same basic Lempel-Ziv principles, and I've never found a good explanation of how JPEG XL implements lossless mode but that hasn't gained widespread adoption yet anyways. HEIC is sometimes advertised as having a lossless mode but it doesn't really (its "lossless" is really just "maximum possible quality lossy" from everything I've seen). And obviously there are lots of niche/experimental codecs that work along different principles such as what you describe. And PNG does have a special mode for solid-color line art that references the previous row.

But the average person encoding a photographic image losslessly is probably using something based on Lempel-Ziv probably 99.99+% of the time -- not something built on top of spatial correlations.

For JPEG XL, refer to its format overview [1]. In short its lossless mode uses a combination of multiple techniques: the rANS coding with an alias table, LZ77, reversible color transforms, a general vector quantization that subsumes palettes, a modified Haar transform and a learnable meta-adaptive decision tree for context modelling.

One good thing about JPEG XL is that its lossy mode also largely uses the same tool, with a major addition of specialized quantization and context modelling for low- and high-frequenty components.

[1] https://github.com/libjxl/libjxl/blob/main/doc/format_overvi...

The post makes sense and is good.

> Lossless ones are basically just ZIP,

Let's go down one more level of abstraction, it's crucial for understanding why it's byte-level patterns: Deflate, not ZIP. See http://www.libpng.org/pub/png/spec/1.2/PNG-Compression.html.

> image compression algorithms are generally terrible at finding patterns.

The core of deflate is pattern recognition, inter alia:

- Duplicate series of bytes (a pattern of repeated bytes in series).

- Huffman coding (a pattern of high frequency repeated bytes that could be replaced by another repeated byte string)

See https://en.wikipedia.org/wiki/Deflate

> There are certain patterns that PNG can efficiently detect, like repeating pixels from the line above

PNG uses deflate. General byte-level patterns. It does not do bespoke image-specific stuff.

> This is certainly entirely explained by the chosen (in this case, default) compression level of the ZIP file and PNG files.

Probably.

> PNG uses deflate. General byte-level patterns. It does not do bespoke image-specific stuff.

That's exactly what I meant, sorry if I wasn't clear. It's not "finding patterns in images". It's finding byte-level patterns, not visual (image) patterns -- which are inherently dimensional in a way that a stream of bytes isn't.

Which is why the post doesn't make any sense. Its entire premise is that there's something about lossless image compression which is different from zip/deflate and similar byte stream compression algorithms.

> PNG uses deflate. General byte-level patterns. It does not do bespoke image-specific stuff.

That's not quite the whole story. PNG does include simple filters to represent a line as a difference from the line above, and that may be what the original post is referring to. [1]

[1] https://en.wikipedia.org/wiki/PNG#Filtering

Reply on news.ycombinator.com