DaveKoelle.com ->  Miscellany ->  Searching a Finite Space of Possible Images

Searching a Finite Space of Possible Images
How many possible images are there in a 200x200-pixel space, and what's in those images? Anything you can imagine!

A rose garden in full bloom

I once had a unique photograph of a prize-winning English rose garden in full bloom. The clear blue sky provided a glorious backdrop for the image. In the foreground, a small rabbit was smelling one of the roses. It was a delightful picture.

Unfortunately, the picture was destroyed. I had no copies, and I had lost the negatives. It would seem that this moment, which I had intended to keep for posterity, has vanished from existence.

But I don't believe that. That image still exists. Perhaps it no longer exists on paper or film; in fact, the event is quite unable to be recreated. I could never get a wild rabbit to look just as it did in that photo; every day, the roses grow a little more, the sky may not always be as clear as it was on the day I took the picture. But I know the image still exists.

Where? You see, if you take a photograph, and think of every image which may be present within that photograph, you will realize that one of those pictures is exactly the one I took. The picture exists in the space of possible images.

The space of images

The space of images is a vast collection of every possible image which may be present within a particular frame -- in our case, the physical boundaries of the photograph. Somewhere in the space of images is a picture of the Eiffel Tower. There is a picture of the signers of the Declaration of Independence. There is the picture of that rose garden. There are also pictures of the Eiffel Tower being climbed by a gorilla; of the signers of the Declaration on a disco floor; of the rose garden, minus one petal. Any picture which can ever exist within that physically constrained frame is a valid picture. Despite all of the different types of images you can imagine being in this frame, the actual space is finite.

To make this easier to fathom, it is a good idea to make the frame more discrete. When computers display images, the result is a certain number of pixels in length and in height. Pixels can be one of a number of colors; most modern computers can render a pixel in one of up to 16.7 million colors.

Let us consider a basic configuration of pixels and colors. Suppose we have a frame which is two pixels wide and two pixels high, and each color can be one of three colors. In this case, an image isn't very exciting. The only things we can have is a variety of 2x2 patterns with three colors. The actual number of patterns possible with this configuration is 32x2, which is 81. If there were four colors per pixel, there would be 42x2, or 256, possible patterns. If we were to increase the size of the frame to 3x3 instead of 2x2, and we were to consider four colors, there would be 262,144 possible patterns -- a much larger number than 256!

This is an excellent illustration of combinations, but a 3x3 image is incredibly small, and is not able to display a picture of any significance. For our purposes, we would need a much larger area, as well as more colors if we want a picture that actually looks like anything. Let us use an 200x200 image, with 256 colors. A photograph is able to show images of much sharper quality than 200x200, and in much richer color than we can get from only 256 colors. But a 200x200 image with 256 colors can approximate a photograph sufficiently well enough for the purposes of this experiment.

The number of possible images within this frame is 256200x200 -- a very large number indeed, but definitely finite. We can use logarithms to determine that this value is nearly equal to 1096330 (in contrast, there have been approximately 1018 seconds since the accepted beginning of time, and there are an estimated 1080 atoms in the entire universe). That's a lot of images. In fact, if we are searching for a particular image, it would be senseless to look at every possible image to see if it is what we are looking for.

What can be found in this finite image space?

As stated earlier, the space we have just created can contain every image conceivable with 200x200 pixels and 256 colors. To give you a more concrete idea of how large this space is, consider that each of the following images could be contained within the space:

  • An image of every page of every book ever written. Text may be of any style, color, or combination thereof. Similarly, there are many more images of slightly incorrect text -- from totally nonsense pages to pages with one incorrect letter to pages with random little marks.
  • Every masterpiece ever painted, any image ever photographed, and any image which could ever be painted or photographed.
  • Technical specifications and drawings of everything ever created or ever to be created. Also, technical specifications and drawings which have slight imperfections, such as an incorrect value or a missing line.
  • Any of a zillion patterns of random dots.

Not only can each of these images be contained, but each of these images including a minute change may also be contained. For example, there is a picture of the Grand Canyon in this space. There are also pictures of the Grand Canyon in which one pixel is a different color than it is in another picture of the Grand Canyon. This is true for each of the 40,000 pixels in the image, and each may be 256 colors. Then, there are some pictures in which two pixels are slightly different. So there are a lot of imperfect images of the Grand Canyon.

Reducing the search space

If I had a photograph of me and you against a pure blue backdrop, I wouldn't be too bent out of shape if one pixel out of 40,000 was the wrong color. It wouldn't matter to me if a pixel the top, left of the blue backdrop was yellow, for example.

We can reduce the space of possible images by removing the ones that are so similar to another image that there isn't much of a difference between the two. This begs the question, How many images may we remove?

That depends on how much noise was can accept in an image. It also depends whether the noise is localized or distributed; if, for example, 30% of 40,000 pixels were of the wrong color (that's 12,000 pixels) but strewn throughout the image, it might not be a big deal. But if all 12,000 pixels were in a clump, that would obstruct one third of the image. Actually, having 30% of the wrong pixels always obstructs one-third of the image; it's just a matter of how close to each other the 12,000 pixels are. We can mentally reconstruct images that are slightly perturbed; we cannot reconstruct parts of images that are entirely blocked out.

Searching the space of images

If there is a particular image you would like to create, how can you find it within the space of images? For example, let's look for a yellow smiley face on a black background. How would we go about finding this image? If we were to map all of the images possible, where would this image fall, and how would it be connected to other images?

I wonder if an image is found as soon as a description of that image has been created. For example, I want to look for a particular yellow smiley face. How do I know when I get there? I must be able to compare it with a yellow smiley face. Therefore, I must create a yellow smiley face. And if I have created a smiley face, then I have, in a sense, already found it. By creating an image, I have found that image.

However, if I were less specific -- perhaps I would accept any color smiley face, and it could be any size -- I have not created an image, but I have created criteria by which an image may be compared.

Copyrighting the space of possible images

Suppose I wrote an algorithm to find all of the finite images that can be found in our 200x200, 256-color space. If I did this, I could copyright every image I generated, except for those that are exact matches for images that already exist. From that point on, any image that anyone could create -- snapshots placed on Facebook, award winners from photo competitions, and even pictures of inventions we've never seen before -- would be in violation of my copyright.