Stefan's Site

On the Vast Number of Finitely Possible Images - Part 1

In my youth, around 25 years ago, I realized that a single digital image can be represented as a number. A 4-bit number has \(2^4 = 16\) different combinations

4-bit patterns

and rearranging these patterns into 2x2 matrices yields

4-bit patterns

which can be interpreted as images where 0 is the first color index in a palette and 1 the second color index.

4-bit squares

There is not an awful lot of information in these 16 tiles, but we can conclude the following principal patterns:

  1. 12.5% are entirely filled (black or white).
  2. 50% of the squares have one single pixel set in a corner.
  3. 12.5% show checkered patterns.
  4. 25% are horizontally half filled.

For 2x2 matrices this analysis is trivial. If we still assume a two color palette and increase the resolution the number of combinations increase according to \(2^n\) we realize that the task of categorizing the different images quickly becomes very complicated. The plot below shows the number of combinations for different resolutions.

2n combinations

Already for an 8x8 matrix with two colors, there is an insane amount of possible combinations.

But images with two colors are not very exciting. What about looking at images with 16 shades of gray?

16n combinations

The are so many combinations possible ruling out any brute force investigations (I naïvely tried brute force on my Amiga 1200 back in the 90's, but realized that the task was impossible after just 15 minutes).

As a reference, the estimated number of atoms in the known universe is around \(10^{78}\) to \(10^{82}\) and the Shannon number for chess is \(10^{120}\).

Each frame on a full HD-screen (1920x1080 = 2,073,600 pixels) with 24-bit colors (16,777,216 possibilities) can be combined in (\(16777216^{2073600} \approx 1.5 \times 10^{14981179}\)) different ways.

Now to the philosophical question. Given a matrix with a particular size and a set of colors for each pixel, how many percents of the representations is pure uninterpretable nonsense (pure noise)? A subset of all possible images also shows an individual object (like a person) from all possible angles doing all possible (and impossible) sorts of stuff in any environment.

I have not been able to find any work where the magnitude of subsets is approximated on these types of things. Noise should be the easiest to determine since it is relatively straightforward to describe mathematically in comparison to describing all possible images of for example my office desk.

Being able to estimate the magnitude of various subsets of a set with finite magnitude could be useful to understand the complexity of some problems. But it can be tremendously difficult if the characterization of the subset is complex. Nevertheless, thinking about the number of possible combinations in images is an almost religious experience. The description of the set is so simple, but the set of all images is enormous and becomes large very quickly.