Texture synthesis is an interesting avenue of computer graphics concerned with the intelligent creation or augmentation of images. To quote Li-Yi Wei,

"The problem of texture synthesis can be stated as follows: Given a texture sample, synthesize a new texture that, when perceived by a human observer, appears to be generated by the same underlying stochastic process."

The example below shows the creation of a larger texture based on synthesizing the original texture patch. The algorithm allows the user to create a large texture of any dimensions based on the single source patch.

Although tiling artifacts and repetition are visible if you look closely, this approach to producing larger detailed textures can produce far superior results than just tiling alone - The human eye can pick out regular patterns or image seams far quicker than the irregular and non-linear artifacts present above.

Plain texture tiling a texture produces visible and undesirable seams, as shown below:

The following is another example of the same algorithm, running with a different type of input patch (patch has been slightly cropped):

These examples show one use for texture synthesis - creating more of an image without much effort. Of course the algorithm in use does not work on every type of image; in this case the textures that synthesize best are those with "arrangements of small objects of familiar but irregular size"; tree bark, grass, gravel and rocks, caustics, etc. Other approaches work better on smoother patterns, such as clouds.

The algorithm in use in the above examples is based on the work done by Michael Ashikhmin in his paper "Synthesizing Natural Textures", available here.

I wrote a little application to play around with some of the texture synthesis ideas available. The application contains implementations of both the Ashikhmin and one of Wei-Levoy's algorithms, the non-hierarchical "brute force search" detailed here. Li-Yi Wei has a list of other synthesis resources on his page at Stanford.

Both of the algorithms use a data structure called a 'Texton', a small L-shaped block that encodes the colour of the central pixel as well as it's surrounding neighbours, thus:

This gives us a nice, simple way to encode a texture fragment that can be compared to other textons in a variety of ways. The L-shape comes from the algorithm designs that we're using - we will create new texture from left-to-right, top-to-bottom; the search does not utilise any data beyond the pixel being synthesised.

In my example we compare textons by summing the squared differences between textons colour values, including a fall-off that weights the more central pixels to be more important. This lets us, given an input texton, find the most visually similar texton(s) from a large input set (eg. a source image).

Although I haven't done so in this example, it would be correct to change the weighting across each of the colour channels to weight green higher than red, and red higher than blue, because 'your eyes suck at blue'.


About the example application

The application uses DevIL to load images to process and OpenMP to supply simple yet effective multi-threading optimizations (see notes below)

The application, its source code and some sample images can be downloaded here. It requires Visual Studio 2005 to build and run.

By default the application synthesizes using the Ashikhmin technique. There are numerous command line toggles that can be used to configure its behaviour. Examine 'TSynth.cpp' for details.


Notes on Threading and Post-Processing

With these particular algorithms, running multiple worker threads can double the performance of the synthesis with minimal quality degradation.

However, because the algorithm uses the results of proceeding scanlines during its search loop, calculating the buffers independently leaves a seam between each of the buffers that would require either ignoring or a bit of post-process fix-up.

I put a routine into my application that, if multi-threading is enabled, reprocesses the seam lines and gradually blends them back into the existing image.

The above image (left side) is a magnification of a seam line caused by multi-threaded buffer synthesis; the right shows a similar area but with the post-process blending applied.