3 ms·

I don't think that it's truly universal, but quite a few image compression schemes have a similar structure if you stand back and squint: 1. Use a reversible l

by wiml 3y ago

I don't think that it's truly universal, but quite a few image compression schemes have a similar structure if you stand back and squint: 1. Use a reversible linear transform to transform the image into some other space. (It'll still require the same amount of data to represent) 2. Throw away a bunch of the values (set them to zero, or round them to low precision, etc) 3. Now that there are some repetitive zeroes or whatever, a conventional data compression algorithm (like LZW, Huffman, or interval/arithmetic) can make it smaller Even simple things like resizing an image smaller can be fit into this framework: step 1 is a simple blur, step 2 sets a bunch of pixels to zero, step 3 discards them. (I don't think fractal compression can be fit into this framework, but I could be wrong. That's the only exception I can think of offhand.)

vitus 3y ago
Broadly, the entire space of (lossy, lossless) compression falls under the purview of information theory, which tells us that almost all [0] encoding schemes with sufficient codebook entropy can achieve the desired capacity / compression subject to constraints on distortion. Unfortunately, this isn't directly useful since the proof is nonconstructive, but it suggests (to me, at least) that there is an infinitude of compression schemes that don't have to have any common given structure. The special thing that image compression gets to rely on is that human vision is inherently lossy, so we can crush color spaces, or throw away tiny details, or even clone regions wholesale (JBIG2, anyone?). And unless you're looking very closely, you probably won't notice a thing. [0] See: typical sets. https://en.wikipedia.org/wiki/Typical_set https://en.wikipedia.org/wiki/Typical_set
derf_ 3y ago
> (I don't think fractal compression can be fit into this framework, but I could be wrong. That's the only exception I can think of offhand.) See https://ieeexplore.ieee.org/abstract/document/660992 https://ieeexplore.ieee.org/abstract/document/660992 for the connection between fractal image coding and wavelets + vector quantization.
- peter_d_sherman 3y ago
  An excellent link! Thank you very much! Let's just transcribe the name of this paper here on HN (should links be broken in the future), for posterity: "A Wavelet-Based Analysis of Fractal Image Compression" by Geoffrey M. Davis, 1997, IEEE Transactions On Image Processing Vol. 7 Issue 2. Incidentally, I found a non-paywalled version: https://www.geoffdavis.net/papers/ieee.pdf https://www.geoffdavis.net/papers/ieee.pdf

by wiml 3y ago

vitus 3y ago

Broadly, the entire space of (lossy, lossless) compression falls under the purview of information theory, which tells us that almost all [0] encoding schemes with sufficient codebook entropy can achieve the desired capacity / compression subject to constraints on distortion. Unfortunately, this isn't directly useful since the proof is nonconstructive, but it suggests (to me, at least) that there is an infinitude of compression schemes that don't have to have any common given structure. The special thing that image compression gets to rely on is that human vision is inherently lossy, so we can crush color spaces, or throw away tiny details, or even clone regions wholesale (JBIG2, anyone?). And unless you're looking very closely, you probably won't notice a thing. [0] See: typical sets. https://en.wikipedia.org/wiki/Typical_set https://en.wikipedia.org/wiki/Typical_set

derf_ 3y ago

> (I don't think fractal compression can be fit into this framework, but I could be wrong. That's the only exception I can think of offhand.) See https://ieeexplore.ieee.org/abstract/document/660992 https://ieeexplore.ieee.org/abstract/document/660992 for the connection between fractal image coding and wavelets + vector quantization.

peter_d_sherman 3y ago
An excellent link! Thank you very much! Let's just transcribe the name of this paper here on HN (should links be broken in the future), for posterity: "A Wavelet-Based Analysis of Fractal Image Compression" by Geoffrey M. Davis, 1997, IEEE Transactions On Image Processing Vol. 7 Issue 2. Incidentally, I found a non-paywalled version: https://www.geoffdavis.net/papers/ieee.pdf https://www.geoffdavis.net/papers/ieee.pdf