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
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
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.
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.
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
n-1 just like the
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.
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
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
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
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.
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