Digital Photography/Enlarging Images

Want to erase your ex from a digital photo and refill the empty space as if nothing had ever happened? Want to make your computer imitate a small sample picture to fill up your huge desktop background? Then texture synthesis is your weapon of choice. Learn about enlarging images, an aged and slow but surprisingly powerful method of making small pictures big.

What do we want to do?

Imagine we had a small photo of a wooden surface, this size:

We'd like to make a wallpaper for our computer's desktop from this picture, meeting the following demands:

The resulting image shall be any size we want.
The resulting image shall resemble the sample.
The resulting image shall look smooth and not repetitive.

What's the problem?

Why don't we just stretch the sample? Stretching is a horrible thing to do. The picture is made up of pixels that will show up as ugly square blocks in the final image:

Why don't we use the desktop's option that says "Tile image"? This is just as horrible as stretching. Tiling means duplicating the image and pasting it next to itself over and over again. This may work alright for "pattern textures", whose borders fit to one another. With the maple burl from above, it looks boring and unfitted:

It is quite simple to satisfy the first two of our demands, but very hard to meet the last one.

What's so special about textures?

To tackle our task, it helps to take a closer look at what makes texture texture. Compare the following two rows of pictures and think about what separates texture from "normal" images:

Texture
Non-texture

Eventually, you came up with some of the following thoughts:

Texture is a kind of surface structure with some more or less regular pattern, like the wood burl that covers the table.
No matter where you direct your gaze in a texture, it looks all the same, not like a face where each part has its position.
Single objects, scaled down and repeated similarly over and over again become texture, like the single brick that becomes texture in the brick wall.

How does stationarity help us?

Texture looks the same, no matter what part of the picture you look at. This is called stationarity and it is this thought that best sums up the idea that is known by the distressing name Markov Random Field.

Imagine I'd blacken one of the pixels in our maple burl image and asked you to set the pixel's color so the resulting image looks smooth. Would you set the color to green? Obviously not, because green doesn't turn up anywhere in the image and surely wouldn't make the result look smooth. Eventually, you'd choose some sort of brown. But which shade of brown? Would you choose brown if the pixel was amidst a field of white pixels?

The random field idea is this: each pixel's color depends on the colors of its neighboring pixels only.

What's the point?

This is the central idea of the algorithm we will now take a closer look at:

Set a blackened pixel's color by searching a pixel in the sample image that has a similar neighborhood.

Develop the algorithm

Prepare the field

First of all, create an empty picture of desired width and height, the "field". In our case, this is an image that resembles the dimensions of our desktop.

Sow the seed

We will now fill the empty picture. To do so we need something to start with, a "seed". Therefore, we copy a small, randomly chosen piece of the sample image to the empty field.

Grow the image

Now, we will grow the seed, pixel by pixel, until it fills all of the image. First, make a list of all empty pixels that lie next to a pixel that is already filled. In the beginning, these are the pixels flanking the seed.

Randomly choose one pixel of this list. We will now determine the color of this pixel. Therefore we do not need the pixel itself but its neighborhood.

Find a match

Compare the neighborhood to the neighborhoods of all the pixels in the sample image, one after the other. Whenever you find a similar neighborhood, add the corresponding sample image's pixel to a list of "good matches".

Grow one pixel ...

When we have finished comparing we have a candidate list of pixels with similar neighborhoods. Now, randomly choose one of these candidates and set the empty pixel's color to the candidate's color.

... and start all over again

Proceed to the next empty pixel. If there are no more empty pixels in our list, it's time to create a new list of empty pixels and start all over again. If there are no more empty pixels in the "field", we have finished.