3 ms·

I would love to see an estimation of how small real world images would get if we could calculate their Kolmogorov complexity. Aka if we could find the shortest

by mg 4y ago

I would love to see an estimation of how small real world images would get if we could calculate their Kolmogorov complexity. Aka if we could find the shortest program that produces the image as output. Some images obviously would become very small. For example an image that is all blue, a spiral, the flag of the United States, the Mandelbrot set ... But what about the average portrait for example?

4pkjai 4y ago
Yes I’ve often thought of this too. Also a lot of images are screenshots of text or UIs.
SR2Z 4y ago
You cannot calculate Kolmogorov complexity in all cases because that would involve solving the halting problem. It is worth pointing out that certain formats like AVIF do sort of do this: they use a few different algorithms, see which combination of algo/block split removes the most entropy, and then compress _that_. In practice, this is pretty good for most non-noisy images.
- l33t2328 4y ago
  Wouldn’t you want entropy to increase when you compress?
  - hinkley 4y ago
    Entropy can be considered on a per-byte or per message basis, and it seems that people who are talking about data at rest (compressed pictures, archives, etc) almost always talk about the per-message numbers. I don't think I've ever seen Kolmogorov complexity applied to a bitstream. It's always been per message. In which case entropy is exactly conserved, unless the encoding is lossy.
    - raxxorraxor 4y ago
      The term is a mess in computer science. The standalone definition almost works reverse to the definition in thermodynamics. There is also entropy coding, which is a compression through a set of prefixes and entropy compression which is about the termination of processes. I am sure there are many more... Most practical approach is to read the meaning through the respective context and sometimes to ignore the sign... That said, I believe the parent is correct. Compressed data certainly has a higher entropy. But any additional bit from an image or sound is rarely independent in the first place like Shannon demanded it to be the case for the definition of entropy. That they are not independent is precisely the attack vector of many forms of compression. For example the base frequency of a JPG has more entropy if we use the literal definition than higher frequencies that get removed because they lack entropy in a information technical sense.
  - lmm 4y ago
    If you're doing some kind of "pre-compression" stage then you want to reduce entropy as much as possible so as to make the "real" compression more effective.
xigoi 4y ago
I wonder how much could be achieved just using a vector format with basic programming constructs like for loops.

by mg 4y ago

4pkjai 4y ago

Yes I’ve often thought of this too. Also a lot of images are screenshots of text or UIs.

SR2Z 4y ago

You cannot calculate Kolmogorov complexity in all cases because that would involve solving the halting problem. It is worth pointing out that certain formats like AVIF do sort of do this: they use a few different algorithms, see which combination of algo/block split removes the most entropy, and then compress _that_. In practice, this is pretty good for most non-noisy images.

l33t2328 4y ago
Wouldn’t you want entropy to increase when you compress?
- hinkley 4y ago
  Entropy can be considered on a per-byte or per message basis, and it seems that people who are talking about data at rest (compressed pictures, archives, etc) almost always talk about the per-message numbers. I don't think I've ever seen Kolmogorov complexity applied to a bitstream. It's always been per message. In which case entropy is exactly conserved, unless the encoding is lossy.
  - raxxorraxor 4y ago
    The term is a mess in computer science. The standalone definition almost works reverse to the definition in thermodynamics. There is also entropy coding, which is a compression through a set of prefixes and entropy compression which is about the termination of processes. I am sure there are many more... Most practical approach is to read the meaning through the respective context and sometimes to ignore the sign... That said, I believe the parent is correct. Compressed data certainly has a higher entropy. But any additional bit from an image or sound is rarely independent in the first place like Shannon demanded it to be the case for the definition of entropy. That they are not independent is precisely the attack vector of many forms of compression. For example the base frequency of a JPG has more entropy if we use the literal definition than higher frequencies that get removed because they lack entropy in a information technical sense.
- lmm 4y ago
  If you're doing some kind of "pre-compression" stage then you want to reduce entropy as much as possible so as to make the "real" compression more effective.

xigoi 4y ago

I wonder how much could be achieved just using a vector format with basic programming constructs like for loops.