2
$\begingroup$

I want to compare what takes more space, 1,200,000 byte 800x500 image with 3 colors, or space required to store the number of all possible images that can be exist in this space(eg, if there was a hypothetical database of all possible images with a unique identifier and the address of the image, would identifying the image by the unique identifier take less space than the image takes up by itself).

For example. a 1x1 image in this format could be stored using 3 bytes (excluding the width/height at start of file which takes 4 bytes each). But this 1x1 space would contain 16,581,375(255^3) possible images(as each color pixel is a unique image), and 16,581,375 can be stored in 3 bytes as well, as 3 bytes represent 0 through 16,777,215.

How do I determine how many possible images exist in such a space beyond a 1x1 image?

$\endgroup$
3
$\begingroup$

They take up the same space. The number of images is

$$256^{800 \times 500 \times 3} = 256^{1.2 \times 10^6},$$

which can be expressed in a number $1.2$ million bytes long.

$\endgroup$
  • $\begingroup$ Actually, you need $1\,200\,001$ bytes to represent that number: The first byte is $1$, all others are $0$. $\endgroup$ – celtschk Jan 8 '16 at 20:45
  • $\begingroup$ i suspected something like this, but I wasn't sure. I typed ln(256^(800*500*3))/ln(256) in wolframalpha and it confirmed it is near 1,200,000 bytes... Although it didn't give a complete number. Thanks. $\endgroup$ – Dmitry Jan 8 '16 at 20:46
  • $\begingroup$ Well, that expression indeed gives exactly $1\,200\,000$. However, consider the number of sequences of 3 decimal digits. There are $10^3=1000$ such sequences, but the number $1000$ already has 4 digits (but $\ln 1000/\ln 10=3$). $\endgroup$ – celtschk Jan 8 '16 at 20:52
  • 1
    $\begingroup$ Looking again at the three-digit example, interpreting the digits as number gives numbers from $0$ to $999$. That are $1000$ numbers, but the number $1000$ itself is not among them; indeed, it's the first one that's too large to fit in three digits. Another way to see it is: If it were only the numbers $1$ to $999$, you'd have $999$ numbers. But additionally you've got the $0$, and thus one more. But $999$ is already the largest 3-digit number, so you get a four-digit number. BTW, to write a positive integer $n$ in base $b$, you always need $\lfloor\log n/\log b\rfloor + 1$ digits. $\endgroup$ – celtschk Jan 8 '16 at 21:08
  • 1
    $\begingroup$ Yes, as I wrote above: The most significant byte would be 1, and the 1,200,000 other bytes would be 0. However note that you only need 1,2000,000 bytes to represent $256^{800*500*3}$ different values (which would, obviously, not include the value $256^{800*500*3}$; the highest representable value in 1,200,000 bytes is $256^{800*500*3}-1$). $\endgroup$ – celtschk Jan 8 '16 at 21:27
3
$\begingroup$

Well, each byte can be one of $256$ things and may be chosen independently of the other bytes in an image - note that you've used the incorrect value of $255$ in your calculations, which possibly ignores that bytes can be $0$. In particular, this means that the number of possible images is: $$256^{1200000}=9.09\times 10^{2889887}$$ which is a very large number.

It is, however, fundamentally impossible to assign every image a shorter description than its representation as an array of pixels, since one needs to get the right number of strings, and there just aren't enough shorter strings. That said, compression algorithms operate by assigning shorter strings to some images at the expense of assigning longer strings to others.

One should note that the vast majority of this space does not contain meaningful images (i.e. it's mostly noise) and the human eye cannot discern images which are close together (e.g. if you allow for each color channel to vary by $1$ from the truth, then there are typically $3^{3\times 800\times 500}=3.20\times 10^{572545}$ indistinguishable images from a given one). Compression can take advantage of both of these facts.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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