Is it feasible to generate every possible RGB image?

Question

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent resolution then that of all the atoms we estimate are visible in our universe.

This makes sense because an image of a decent resolution (like the image displayed your computer monitor) should be able to contain every picture imaginable, every frame from every movie ever made and never made. It would contain every correct and incorrect mathematical equation. Or even every book/webpage that will exist or can exist. It's intriguing to think it would be possible to generate every possible image because it contains all knowledge but also all anti-knowledge which means there is a lot of stuff to sift through including lots of random noise.

The only other research into this topic that I could find is this art project, where they wrote some code to generate all 15x10 pixel black and white images which is estimated to take approximately 46 quinvigintillion or 4.6x10⁷⁹ years to complete.

So is it feasible to generate every possible RGB image (of a decent resolution)?

Answer 1

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably possible to enumerate all such images.)

Answer 2

TLDR;
No it is not feasible at all, the numbers you provided are small in compare with space you want to generate. So you have provided very strong hint yourself. TLDR;

You can say that $Q = 24bpp * Width * Height$ is your bits array. Since this are bits there are $2^Q$ images.
And now comes question (which I hope answers something): what will you do next and why you want to generate them all?

This number is way too huge to give you something useful, let me assume you can have it tommorow, what then?
You will not have enough time to just look at them, storage space - you do not have it. And there will be very large number of pictures that are beyond your perception are the same. If you take picture of yourself and change one pixel, you will not notice it. Even changing all pixels by 2 least significant bits will show low artifacts, lower than jpeg compression.

But assuming you have space and those images - what is next step? Looking for similarities? Trying to find your friends picture? Well, no, you ended up with enumerating all possible images (which are numbers), and now you want do to something more than posses them.
So probably, you will transform them - scale down, make grayscale and tell the program to get rid of too close pictures (since there are in your perception, the same scene), and then you try to let say find something.
Still the space is way to big to operate on, algorithms like SSIM (to compare two images) have big runtimes. So waiting for prescreened results (meaningful and interesting) is still out of reach.

This is the reason that nobody enumerated these images, do not generate all possibilities, because even under assumption you can have them, there is nothing useful there.
So the answer is no, and all projects of this type are just for fun, showing that somebody can use two nested loops and arithmetic on RGB, make show or intrigue people, but under no circumstances this is feasible.

Take natural numbers. Up to say 2^240000 which is equivalent to all 100px x 100px 24bit images - looks like quite big number. And now try to find me picture which is miniature of red-blue dragon. Would you really generate and save all possibilities on some storage and than review them?

And another thing, to make color->grayscale based on luminance it would be nice to have 2^24 precalculated colors - have you seen such array? It does not fit cache, and it takes a while to generate, while calculations on fly are in realtime.

Answer 3

It is actually more feasible then you might imagine. I've been researching this topic and surrounding ones involving images on and off for a while now. Welcome to part 1 of many parts to come of my research into the exciting area of digital images. The rest will be posted on here using the same question and answer format. An accompanying Mathematica notebook can be downloaded here: http://www29.zippyshare.com/v/6ZntKnfL/file.html

---

Getting Started

First we need to define what every possible image means more clearly. For an image to exist we need to define three things: a color space, a width, and a height. Once those three things are defined we have defined a set of images, and once we have a set of images to work with we can calculate the total possible or the total number/amount of images in that set using this Mathematica function I wrote:

totalPossibleImages[numberOfColors_, numberOfPixels_] := numberOfColors^numberOfPixels

In thinking about this problem, I figured that a lot of images that you would end up generating would be similar or the same as other images, so you don't need to generate all of them. To investigate this I started looking at small black and white images and wrote a function to generate every possible black and white image so that I could study them for patterns.

allBlackAndWhiteImages[imageWidth_, imageHeight_] :=
...continued in notebook...

To summarize, the function works by counting up from 0 in binary. Each count gives us an image because we interpret each 0 as a black pixel and each 1 as a white pixel as they are contained in each number as we count up. We know when to stop by taking the total number of possible images, subtracting 1, and converting it to binary (which conveniently will always be the last image we need to generate in every set, an all-white image).

Notice that this is the same algorithm that is used for generating password sets when doing a brute force password attack.

So now let's start generating some sets and see what we find.

Generating Some Image Sets

1x1 B&W

Nothing particularity surprising or out of the ordinary here. Now we will continue to increase our width, then height, by 1 and continue to investigate.

2x1 B&W

Again nothing particularly interesting here. We are essentially just visualizing counting in binary.

Notice I'm skipping 1x2 since it ends up being the same number of images as 2x1 but is shaped differently. This holds some importance later on with other equivalence cases and will be detailed in my next posting.

2x2 B&W

Take a moment to look at this set and see if you notice the beautiful pattern before reading on!

What I noticed was that the 8th and 9th images were the inverted versions of each other, then the 7th and 10th, 6th and 11th, 5th and 12th and so on. There is a line of symmetry exactly in the middle, between the 8th and 9th images. Where have we seen this pattern before? The integer number line:

The integer's number line has a line of symmetry at 0. However in our example we don't have a 0. We are effectively "subtracting" or skipping the zero. I'm not sure of the mathematical importance of skipping the zero is but it feels like it relates to the subtracting of 1 that we are always doing when performing a loop in programming (if you want to loop n times your counter counts from 0 to n-1 just like the totalPossibleImages function).

If you go back and look at the other image sets they have the same pattern and this pattern continues for any black and white image.

So then I put this integer line idea back into a new image generating function, allBlackAndWhiteImagesWithInts, and looked at the 2x2 B&W set.

2x2 B&W

What I noticed when using the integer number line is that it gives us a mathematical formula for inverting any black and white image: multiplying by -1. But we have to convert existing images to integer form first. If we compare this to the current algorithm for inverting images, it is exactly the same thing happening but it is just represented differently. The loop over each pixel is abstracted away to a mathematical, versus a computer science, operation.

This leads me to predict that there must exist other mathematical abstractions for other image operations like rotation and scaling (yet to be investigated).

Bringing this back to generating every possible image, this means that for any black and white image set, you only need to generate the first half of the set since the second half of the set can be produced by inverting any image generated in the first half and vice versa.

But the original question was whether it was feasible to generate every possible RGB image. Once we choose a different color space other than black and white then this theory of only needing to generate the first or last half of the set doesn't hold up. For example:

3x1 B&W&Red all over

Notice here I just did the permutations manually since I didn't find it intuitive to program Mathematica to use an easily calculable amount of colors like 3. Instead of rendering an image we just use the convention that 0=black, 1=red, 2=white (white is always the highest number and black is always the lowest in images). The problem here is that using 3 colors gives results in an odd amount of images meaning we can't easily just stop half way. And even if we were able to there is no symmetry near the halfway point in this set anyways.

So in order to continue we need to rethink the RGB part of the question. An RGB image is made up of 3 greyscale images which are colored in red, green, and blue. This means that every RGB image is actually made up of 3 images picked from the exact same set of greyscale images. This means that we can rephrase the question and easily eliminate a lot of images that we would need to generate in trying to answer the original question.

Is it feasible to generate every possible greyscale image?

Now that the question is framed more accurately we can investigate this much more easily. For the remainder we will be assuming a 256 bit greyscale image where 0=black and 255=white.

Since we are saying that inverted images are the same, meaning we only need to generate one of the inverted pairs in an image set, I began to think about what what the inversion process does in terms of greyscale. And all it is doing is just shifting the values of all of the pixels in the image by the same amount: ±128 (rolling over 255 to 0 and vice versa). So then what happens when we shift all of the pixels in the image by a different amount like ±1? Well then we just get a brighter or darker image respectively. So really inversion just happens to be one specific spot along this relative scale of brightness. Which means that we only need to generate images with one brightness level out of 256 possible ones in the set. That's cool but how do we know where those other brightness levels are in relation to each other when generating an image set sequentially so that we know when to stop?

To figure this out I looked back at the 3x1, black & white & red all over set.

Then I derived this algorithm to reorganize the appearance of the set into the different relative brightness levels.

Start at the leftmost column, 000, and make this the number we are working on.

1. Increase all of the digits by 1 resulting in a new number (if the digit is a 2 then it wraps around to a 0)
2. Find this new number in the columns and cross it off
3. Write this new number underneath the number we are working on
4. Make this new number the number we are working on and repeat step 1 to get another number
    a. If this other number doesn't exist in the column we are working on then repeat steps 2-4
    b. If this other number does exist in the column we are working on then make the number in the next column the number we are working on and go to step 1

Which gave me the resulting table:

There are a few interesting things to notice here.

• The first digit in each number:
  • is the logical index of what row it is in
  • is used to define all of the shades for an image set
• The last two rows don't have any immediately recognizable patterns as sets on their own (I assume there is a pattern, need to investigate more)
• Finally, we were getting a 1/3 reduction in the total number of images that we needed to generate (3 being the number of colors in the image set)

This reduction is much larger than the half reduction we got from looking at the inversion which we would expect since we are getting rid of more information.

Conclusion

So if we want to generate every possible image, the amount of images we need to generate becomes too large to compute as we reach a decent enough resolution to see the detail we would like. In order to reduce how many possible images we would need to generate for a given set of images, we need to be able to efficiently eliminate images that are equivalent (or can be non-destructively transformed into other images in the set - hence they don't need to be generated). The first case where we noticed this was possible was color inversion of an image; however the algorithm for doing so didn't easily apply to different image sets. From there we realized that inversion was really just one step on the scale of changing the relative brightness level of all the pixels in the image. Then from organizing a small image set into its relative brightness levels we could see how when we generate the images sequentially, the relative brightness level equivalent images are generated in a predicable enough way that we know exactly when to stop generating images so that we can eliminate them effectively: 1/(number of colors) the way through generating every possible image. And we know how many possible images we need to generate by taking numberOfColors^numberOfPixels in the set. So if we only want to generate 1/(number of colors) of numberOfColors^numberOfPixels total possible images in the set, we can simplify that down to generating numberOfColors^(numberOfPixels-1) which we can read simply as skipping the last exponentiation when generating the entire set.

Looking back at the original example of generating every possible 320x240 RGB image we can use a cop-out and make ourselves feel good and get an instant 1/3 reduction by saying we can only look at every possible 320x240 greyscale image. Then we can reduce that further buy skipping the last exponentiation when generating every possible image. But this still leaves way to many images to generate.

---

What we have done is eliminate an equivalence case: relative brightness of an image. But what other equivalence cases can we come up with? Can we eliminate them? Can we eliminate enough so that it becomes feasible to generate every possible "usable" image in a set of a decent resolution so that we can find extraordinary information?

This is where my affirmative results for this question end. I am currently researching other equivalence cases that can be eliminated and will publish them here when I have some results.

---

And again here is the Mathematica Notebook. It also contains some history on how I became interested in this problem in the first place and a few extra details here and there. http://www29.zippyshare.com/v/6ZntKnfL/file.html

Answer 4

A perhaps more interesting question is:

Can we generate all RGB images up to "indistinguishability"?

That is, if two images "look the same", it's enough to generate one of them.

To answer this question, let's assume that JPEG does a decent job of compressing images. That is, two images which compress to different JPEG files are "distinguishable". Let's also assume that the average JPEG image takes up B bytes. Then the number of different images is at least $256^B$ (this is what we would get if all JPEG images where exactly $B$ bytes; other distributions with expectation $B$ are even worse).

To estimate $B$ (which depends on image resolution and the threshold of distinguishability), I looked at this page and concluded that $B \geq 10000$. In particular, there are at least $256^{10000}$ images, which is a huge number.

(For more, you might want to look up rate-distortion theory.)