1
$\begingroup$

Inspired by this question: Does a simple photograph contain more information than a complex painting? Say that I have a discrete representation of some physical object - eg an image file. What is the true degree of "unpredictableness" or the size that a potential (lossless) compression scheme might never improve upon?

I could try to measure its entropy assuming that each element is independent. Or I could try to model dependency as eg neighbour correlation (1st order or higher order), remove it and then do my entropy estimate. Or I could apply some lossless entropy coding in a black-box fashion and measure the number of bits in the output.

But for a given file where no simplified generation model is assumed, is there any way to know how many bits of information it fundamentally «contains»?

If I do a few lines of MATLAB:

rng('default'); 
N = 1e6; 
x = randi([0 255], N, 1);

I get 1MB of presumably "good entropy" pseudo randomness. I assume that most lossless encoders are going to have a hard time finding any pattern in that - the compression ratio is going to be close to 1. However, if the bitstream allowed to inject MATLAB code and the encoder somehow recognized that particular stream, it could simply send an uncompressed 49 ascii codes ala : "do_MATLAB; rng('default'); randi([0 255], 1e6, 1)"

I fail to see how such a limit can be found. The number of ways to «re-represent» a file is practically infinite. We can always make a compression algorithm that works extremely well for one particular file (by incorporating implicit/explicit features of that file in the algorithm that is know beforehand by encoder as well as decoder, but that does not tell us anything useful. The extreme being a encoder/decoder that both contains the actual image and just transmits a bit saying "reproduce the image that you know"...

So perhaps an adhoc measure where you count the summed number of bits needed to:

  1. represent the information particular to the file, as well as
  2. some code written in a generic (touring complete?) programming language to decode the first piece of information? Itself compressed using some entropy coding suited to "typical" usages of that language

That still sounds like a "near infinite" volume to search, but at least you have an approach where you can tailor your encoding to the actual content - at the price of the added entropy of that tailoring? Now, what if you also want to have the possibility of embedding custom code in order to compress the size of the first code that is used to decompress the "payload"? That sounds like a solution biting its own tail.

If we include a large library of more or less related input (such as the most prominent million images from google image search), the size in bits of a compliant general decoder (description) (to be amortized among all of those images), and any "per image" particular decoder expression like above, we would have some idea about the average unpredictability of each file under the requirement that the whole thing was/could be optimized for global compression?

Or is the solution a more mundane "capture a large dataset relevant to your domain. Split it in two. Optimize your encoder globally for the training set. Apply that codec on the remainder of the dataset. Whatever file size is achieved for each file of the latter set is as close to an entropy measure that we are currently able to make"?

Improve this question
$\endgroup$
3
  • $\begingroup$ What you describe is not compression but more a kind of information outsourcing. Without the additional "information" of MATLAB, the string would be pointless. Further: each "compressing" algorithm using a code-book does essentially the same thing. In other words: outsourcing information to other places is not by any means covered by the field of entropy coding. $\endgroup$
    – Max
    Commented Oct 5, 2022 at 11:46
  • $\begingroup$ Thanks for your comment. But is not e.g. applying a 2-d whitening filter domain-specific in a way similar to code-book? In both cases one agrees on some probable characteristic of the file(s) to encode, and agree upon tools at the encoder and decoder that can compress the stream further armed with that capability? $\endgroup$
    – Knut Inge
    Commented Oct 5, 2022 at 11:52
  • $\begingroup$ I am not sure about this. Let's look at it this way: your search for a lower information/upper entropy bound is doomed if you keep changing the information to be transmitted/stored. As you said, you can come up with infinite ways to trade "channel load", so to speak, for algorithmic load and/or memory at the sender/receiver sides. But I think these have to be accounted for when assessing the "information value". $\endgroup$
    – Max
    Commented Oct 5, 2022 at 12:24

1 Answer 1

Reset to default
0
$\begingroup$

I think what you are describing is more or less "meta data". Auxiliary information about the data that the encoder can use to make decisions around how to most efficiently encode it. There are many meta data schemes out there that can be used for this type of purpose.

The problem always seems to be "how do you reliably generate the meta data". In your example, the white noise picture could either be fully random or it could be created by an artist who deeply cares that every pixel must be exactly what it is. There is no way to tell just from looking at the data, so you have to ask. And asking a user or operator is highly unreliable.

Improve this answer
$\endgroup$
1
  • $\begingroup$ If we move into perceptually motivated lossy coding, then another layer of complexity is introduced. Therefore I limited myself to lossless encoding, where a hypothetical encoder would have to recognize the sequence as pseudo-noise that can be compactly represented, rather than true noise. Possible hinted by some upstream component with explicit knowledge (only to reduce the search space/encoding time). I guess what I am trying to confirm is that no such bound can be found until you actually make that encoder. And even then, you dont know if you are at the limit. $\endgroup$
    – Knut Inge
    Commented Oct 5, 2022 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.