Texture synthesis

Texture synthesis is called the automatic generation of textures, so two-dimensional digital images showing the surface structures or similar content. There are two fundamentally different types of texture synthesis: Procedural texture synthesis methods create from nothing a new texture, template-based methods mimic a given original image after. The goal of both methods is to produce images that are indistinguishable from real models.

The texture synthesis, together with the texture analysis the common research area of the directions of image processing, computer graphics and computer vision, of the special properties of textures is dedicated to. In addition to the texture synthesis three problem areas are in this field examined: texture classification, the distinction between different types of texture using measurable properties, Textursegmentation, decomposing an image into uniform textured surfaces and the Shape from Texture -called instance of the more general question of Shape from X, in which a two-dimensional image on the three-dimensional shape of the imaged object to be closed.

Common applications for the texture synthesis in image processing, such as when unwanted details to be retouched unobtrusively in a digital photo or the material properties of an imaged object to be changed. In 3D computer graphics, it serves to coat three-dimensional models with as realistic looking surfaces, while reducing the memory requirements for textures.

• 3.1 Stochastic Synthesis
• 3.2 tiles
• 3.3 Synthesis by Efros and Leung
• 3.4 quilting
• 3.5 Chaos mosaic
• 3.6 Texture synthesis with binary tree -based vector quantization

Textures

People grasp the concept of texture intuitive, but a precise and machine- understandable so that formulation is difficult and is one of the unreached goals of texture analysis. A useful definition of texture is texture is the variation of data in a scale that is smaller than the magnitude for which the interested viewer. Whether an image texture or not, then is a question of scale and the position of the observer.

In the texture synthesis there are two types of texture extremes that flow into one another go: Regular or deterministic textures exhibit pronounced structures that are repeated with geometric regularity, stochastic textures show no structure, but remember to image noise. For the practical application are mainly the frequently encountered in nature almost regular and nearly stochastic textures of interest. The texture classification knows more texture and subdivided, for example, the regular textures still in geometric and color- regular textures.

Procedural methods

Procedural texture synthesis methods generate textures from scratch. The user simply selects a set of numerical parameters - hence it is also called parametric texture synthesis - which are passed to a mathematical function or algorithm and affect the output of the process.

The origin of the parametric texture synthesis is Perlin Noise, a developed in 1982 by Ken Perlin for the film Tron mathematical function that texture images more diversified by random distortion. A systematic research in this area does not take place, procedural methods are discovered by trial and error or by accident.

Instead of the actual texture only the procedure needs to be stored in the procedural texture synthesis with which the texture is generated. This saves usually extremely much space and is thus particularly suitable for such scenarios of interest, where little space is available, for example in the demo scene, where only 64 KB of memory versatile graphics to be generated from as. A second advantage is that the procedural texture synthesis sometimes very rapidly generates large textures and thus is suitable for texture generation on the fly for 3D computer games and similar applications where fast response times must be guaranteed.

Stationarity

For texture synthesis are mainly stationary textures of interest: Wherever the eye just wanders about in such an image, one always has the feeling of seeing the same thing - just as when moving the view not of the site. In technical terms, one says that the image information is spread evenly over the entire image.

Markov chains

One of the most important mathematical foundations of texture synthesis is the realization that textures can be understood as a product of a Markov chain. The statement of this model of probability theory is in the context of texture synthesis: Each pixel of a texture not only depends on the pixels in its immediate vicinity, but from the pixels outside this fixed circumscribed area. This so-called Markov property translates the property of stationarity in a tangible calculation model and is the mathematical foundation of almost all texture synthesis method.

Torus geometry

In the beginning, put the texture synthesis to the following geometric principle: An image whose right and left and top and bottom margins clean match, can be attached to each other as often with no visible seams. Because this is particularly evident when one deforms the flat image into a torus, one speaks also of toric geometry. The geometry of the planar crystallographic groups and pmm pm According to an image with edges can be any string together seamlessly by suitable mirrors. Today these geometric ideas of secondary importance.

Algorithms

Pursue all previously developed algorithms for texture synthesis either the mosaic approach or the pixel approach. In the mosaic approach, the resultant image from larger pieces of the template is assembled while it is being built at the pixel approach pixel for pixel.

A texture synthesis algorithm receives as inputs a digital image, the desired size of the output image and possibly some algorithm-specific parameters by which its operation can be specified. The output of the algorithm consists of the synthesized image.

Stochastic synthesis

In the stochastic synthesis, the output image is composed pixel for pixel. The color value of the currently considered pixel is determined by the color value of a randomly selected pixel is taken in the original image. This method is very fast, but only works with highly stochastic textures, ie when the individual parts of the texture at most one pixel in size.

Tiling

From tiles ( tiling English ) is when the template is repeatedly duplicated and joined together. This method is fast but produces a maximum in structured textures satisfactory results; and not even always there. Meets the document is not specific symmetry conditions, is in the final result clearly where the duplicates are contiguous. Since repeated the image content at regular intervals, the result is always a structured texture. Tiles is therefore entirely unsuitable for different texture classes. Although it reflects the duplicates repeated, so the boundaries between the tiles, the repetition effect remains. Tile is often used to create simple wallpapers for websites and graphical user interfaces.

Synthesis by Efros and Leung

Main article: Image Growing

This technique was presented by Alexei A. Efros and Thomas K. Leung in 1999 and is commonly " by Efros and Leung synthesis ", but occasionally also called Image Growing.

Here is a blank image with the desired dimensions is first created. In this image into the so-called seed is copied, a small, randomly selected piece of the template. Then, the image, starting from the seed, is filled in a plurality of passes pixel by pixel. In each round, initially all be determined at the pre-filled image area adjacent pixels. Then a number of pixels in the template is determined for each of these pixels, the environments around the new pixel are as similar as possible. From this, a pixel is randomly selected and assigned the color of the new pixel.

Quality of results and speed of the method are the size of the environment considered, the so-called border width, depending. The more structured is a texture, the more widely the environments of the pixels must be compared with stochastic textures contrast, the smallest possible area size is displayed in order to receive any unwanted structures. The greater is the observed environment, the slower the algorithm. If the environment size is set to zero, the method corresponds to the stochastic synthesis (see above).

Numerous follow-up work (for example ) the process have since been refined by the existing search and compare actions algorithmically optimized.

Quilting

When quilting, the resulting image is composed of patches for patches from the template. For each Flick position of the output image the image will be searched in the template whose area around the new patch is as similar as possible. Happen to be one is then selected from the determined parts. To hide the transitions between the patches, the new patch is cut before insertion, ie its edge is trimmed so that it possible blends well with the previously generated image.

Quilting is the highest quality but also time-consuming mosaic technique. It is suitable for semi-structured and teilstochastische textures and partially structured and stochastic textures. If there is an unstructured pattern texture, ie a non purely geometrically reasonable structure, so the result is only partially satisfactory: as structured objects are randomly cut and reassembled, strange effects can occur; as may be fragmented or deformed tomatoes, for example, tomatoes Grade A. Highly structured templates provide only for sufficiently large patch size satisfactory results, while highly stochastic demand templates for the smallest patch size. If the patch size is set to one pixel, this corresponds to the technique of quilting Image Growing (see below).

Chaos mosaic

Chaos mosaic was introduced in 2000 by Ying- Qing Xu, Baining Guo, Harry Shum and in a technical report by the research division of Microsoft. The technique uses a " chaotic " form of Kachelns with a freely selectable subordinate synthesis technique; the original work used the pixel-based texture synthesis by Efros and Leung.

The first step of Chaos mosaic is to create an image by tiling with the desired dimensions. In the second step of random size to randomly selected items are copied in this tile image randomly selected blocks. Without further treatment, the result would contain visible joints where the image content of the shifted mosaic piece does not fit with the ground. In each of these copy operations therefore a narrow margin is blacked out to the newly inserted mosaic tiles around. The blackened area is filled in a sub-step with the help of subordinate synthesis process. This form of chaos mosaic provides good results and requires little space. The speed is mainly determined by the subordinate synthesis method and is slow for the technology by Efros and Leung.

Xu, Guo and Shum presented thus simultaneously a modified form, to meet the demands for a rapid synthesis method for 3D computer graphics. In this variant, no Ausschwärzen and subsequent refilling is used. Instead, the edges of the mosaic pieces are smoothed with a smoothing filter, making hard edges and sharp color transitions blur. The results are worse than in the original method, but are rewarded with a significant speed boost, because filters can be applied very efficiently.

Texture synthesis with binary tree -based vector quantization

This algorithm was proposed in 2000 by Li- Yi Wei and Marc Levoy. It extends the method of Efros and Leung a multi -scale approach and uses an efficient search algorithm.

First, a picture with the desired output measure is generated with random color values ​​( white noise) is filled; hereinafter, this image is changed so that it contains the synthesized texture at the end. Now each a multi-scale pyramid is created from the template image and the noise image: Repeatedly filtering successively images are generated from the original image, each about half the size as its predecessor image; arranged according to size make this a pyramid, at the bottom of the original image. The type of filter depends on the purpose from, Wei and Levoy used a Gaussian filter, but are also conceivable Laplace or wavelet; filtering provides an overview of the item image processing.

In the synthesis of the image, the noise image pyramid to be filled with the method according to Efros Leung and from top to bottom. The neighborhood of a pixel contains not only the pixel area in the same image, but also of all pixels overlying pyramid images, which are at about the same point in the image. This comparison at several levels of resolution at the same time is the epitome of multi-scale analysis and ensures that the synthesis process independent structures of various size in the template fits.

This multi-scale approach is complemented by the binary tree -based vector quantization ( tree- structured vector quantization, TSVQ ). A central component of this process, which actually is used for data compression, is a binary tree, in which nodes vectors are housed. Each vector contains a pixel of an image of the original pyramid all the pixels around that pixel (including those on higher pyramid levels ), each node contains the mean average vector of all of his children. In this data structure can be searched much faster for similar candidates than in the original image.

Although this technique instead of individual images all images pyramids must be synthesized and before the first synthesis of the first binary tree must be built, this algorithm is significantly faster than its predecessor. He also covered by the multi-scale analysis of some types of texture better.