Texture synthesis
Texture synthesis is the name given to the automatic generation of textures , i.e. two-dimensional digital images that show surface structures or comparable content. There are two fundamentally different types of texture synthesis: procedural texture synthesis processes create a new texture out of nothing, template-based processes imitate a given image template. The aim of both methods is to create images that cannot be distinguished from real models.
Texture synthesis and texture analysis form the joint research area in the fields of image processing , computer graphics and machine vision , which is dedicated to the special properties of textures. In addition to texture synthesis, three other problem areas are investigated in this department: texture classification , the differentiation of different types of textures on the basis of measurable properties, texture segmentation , the decomposition of an image into uniformly textured surfaces and the instance of the more general question Shape from X , called Shape from Texture two-dimensional image to infer the three-dimensional shape of the depicted object.
Texture synthesis is used in image processing , e.g. B. if unwanted details in a digital photo should be retouched inconspicuously or the material properties of an object depicted should be changed. In 3D computer graphics, it is used to cover three-dimensional models with surfaces that appear as realistic as possible and at the same time to reduce the memory requirement for textures.
Textures
People understand the concept of texture intuitively, but a precise and therefore machine-understandable formulation is difficult and is one of the still unachieved goals of texture analysis. A useful definition of texture is: Texture is the fluctuation of data on an order of magnitude smaller than the order of magnitude the viewer is interested in . Whether an image is texture or not is a question of the scale and the point of view of the observer.
In texture synthesis, a distinction is made between two types of texture extremes that flow smoothly into one another: regular or deterministic textures show pronounced structures that are repeated with geometric regularity, stochastic textures show no structure at all, but are reminiscent of image noise . For practical application, the almost regular and almost stochastic textures that are often found in nature are of particular interest. The texture classification knows other types of textures and, for example, divides the regular textures into geometrically and color-regular textures.
Procedural procedures
Procedural texture synthesis processes create textures from scratch. The user simply selects a series of numerical parameters - one speaks therefore also of parametric texture synthesis - which are passed to a mathematical function or an algorithm and influence the output of the method.
The origin of parametric texture synthesis is Perlin noise , a mathematical function developed by Ken Perlin in 1982 for the film Tron , which creates more varied texture images through random distortion. There is no systematic research in this area; procedural methods are discovered through trial and error or by chance.
Instead of the actual texture, only the procedure with which the texture is generated needs to be saved in procedural texture synthesis. This usually saves a lot of storage space and is therefore of particular interest for scenarios in which only little storage is available, e.g. B. in the demo scene , where the most versatile graphics are to be generated from only 64 KB of memory. A second plus point is that the procedural texture synthesis sometimes generates large textures very quickly and is therefore suitable for texture generation on the fly for 3D computer games and similar applications where fast response times have to be guaranteed.
Stationarity
For texture synthesis, stationary textures are mainly of interest: wherever the gaze wanders around in such an image, one always has the feeling of seeing the same thing - just as if the gaze was not moving at all. In technical jargon, it is said that the image information is evenly distributed over the entire image.
Markov chains
One of the most important mathematical foundations of texture synthesis is the knowledge that textures can be understood as the product of a Markov chain . The statement of this model of probability theory in the context of texture synthesis reads: Each pixel of a texture depends only on the pixels in its immediate vicinity, but not on the pixels outside of this fixed area. This so-called Markov property translates the property of steadiness into a solid calculation model and is the mathematical foundation of almost all texture synthesis methods.
Torus geometry
In the early days, texture synthesis relied on the following geometric principle: an image whose right and left as well as upper and lower edges fit together properly can be joined together as often as desired without visible seams. Because this is particularly evident when the flat image is deformed into a torus , this is also referred to as torus geometry . According to the geometry of the planar crystallographic groups pm and pmm , an image with arbitrary edges can also be seamlessly strung together by suitable mirroring. Today these geometric ideas are of secondary importance.
Algorithms
All algorithms for texture synthesis developed so far follow either the mosaic approach or the pixel approach. With the mosaic approach, the resulting image is composed of larger pieces of the original, while with the pixel approach it is built up pixel by pixel.
A texture synthesis algorithm receives as inputs a digital image , the desired size of the output image and possibly some algorithm-specific parameters with which its functioning can be determined in more detail. The output of the algorithm consists of the synthesized image.
Stochastic synthesis
In the case of stochastic synthesis, the output image is put together pixel by pixel. The color value of the pixel currently being viewed is determined by adopting the color value of a randomly selected pixel in the original image. This method is very fast, but only works with highly stochastic textures, i.e. H. if the individual parts of the texture are at most one pixel in size.
Tiles
Of tiles ( English tiling ) occurs when the template is repeatedly duplicated and joined together. This method is fast, but only produces satisfactory results with structured textures; and not even there ever. If the template does not meet special symmetry conditions, the end result clearly shows where the duplicates adjoin each other. Since the image content is repeated at regular intervals, the result is always a structured texture. Tiling is therefore completely unsuitable for other texture classes. If you mirror the duplicates repeatedly, the boundaries between the tiles disappear, but the repetition effect remains. Tiling is widely used to create simple background images for websites and graphical user interfaces.
Synthesis according to Efros and Leung
This technique was introduced in 1999 by Alexei A. Efros and Thomas K. Leung and is commonly referred to as "Synthesis according to Efros and Leung", but sometimes also called image growing .
Here an empty image with the desired dimensions is first created. The so-called seed , a small, randomly selected piece of the template, is copied into this image . Then, starting from the seed, the image is filled pixel by pixel in several passes. In each pass, all pixels adjoining the already filled image area are first determined. A series of image points is then determined in the original for each of these pixels, the surroundings of which are as similar as possible to the surroundings of the new image point. A pixel is randomly selected from these and its color is assigned to the new pixel.
The quality of the results and the speed of the process depend on the size of the environment under consideration, the so-called edge width . The more structured a texture is, the more extensive the surroundings of the image points have to be compared; in the case of stochastic textures, on the other hand, the smallest possible surrounding size is indicated in order to avoid undesired structures. The larger the environment under consideration, the slower the algorithm is. If the environment size is set to zero, the procedure corresponds to stochastic synthesis (see above).
Numerous follow-up work (e.g.) have since refined the process by algorithmically optimizing the existing search and comparison actions.
Quilting
When quilting, the resulting image is put together from the template, patch by patch. For each patch position of the output image, image parts are sought in the template whose surroundings are as similar as possible to the surroundings of the new patch. One of the parts identified is then selected at random. In order to hide the transitions between the patches, the new patch is cut to size before it is pasted, that is, its edge is trimmed so that it blends in as well as possible with the image created so far.
Quilting is the highest quality but also the most time-consuming mosaic technique. It is suitable for partially structured and partially stochastic textures as well as partially for structured and stochastic textures. If there is an unstructured pattern texture, i.e. one with a structure that is not purely geometrically based, the result will only be satisfactory to a limited extent: Since structured objects are arbitrarily cut up and reassembled, strange effects can arise; For example, grade A tomatoes may be made into chopped or overgrown tomatoes. Highly structured templates only deliver satisfactory results if the patch size is sufficiently large, while highly stochastic templates require the smallest possible patch size. If the patch size is set to a single pixel, quilting corresponds to the technique of image growing (see below).
Chaos mosaic
Chaos Mosaic was presented in 2000 by Ying-Qing Xu, Baining Guo and Harry Shum in a technical report from the Microsoft research department . The technique uses a “chaotic” form of tiles with a freely selectable subordinate synthesis technique; the original work used the pixel-based texture synthesis according to Efros and Leung.
The first step of Chaos Mosaic is to create an image with the dimensions you want by tiling. In the second step, randomly selected blocks of random size are copied to randomly selected positions in this tile image. Without further treatment, the result would contain visible joints, where the image content of the moved mosaic piece does not match the substrate. With each of these copying processes, a narrow edge is blackened out around the newly inserted mosaic tile. The blackened area is filled in in a sub-step with the help of the subordinate synthesis process. This form of chaos mosaic delivers good results and requires little storage space. The speed is mainly determined by the secondary synthesis process and is slow for the Efros and Leung technique.
Xu, Guo and Shum therefore presented a modified form at the same time to meet the demands for a fast synthesis process for 3D computer graphics. In this variant, no blackout and subsequent refilling are used. Instead, the edges of the mosaic parts are smoothed with a smoothing filter, which blurs hard edges and sharp color transitions. The results are worse than in the original method, but are rewarded with a considerable increase in speed, since filters can be applied very efficiently.
Texture synthesis with binary tree-based vector quantization
This algorithm was proposed by Li-Yi Wei and Marc Levoy in 2000. It extends the Efros and Leung method by a multi-scale approach and uses a more efficient search algorithm.
First, an image with the desired output dimensions is generated, which is filled with random color values ( white noise ); in the following this picture is changed so that it contains the synthesized texture at the end. A multiscale pyramid is now created from the original image and the noise image : Repeated filtering is used to successively generate images from the original image that are each about half the size of their predecessor image; Arranged according to their size, they form a pyramid with the original image at the bottom. The type of filter depends on the application, Wei and Levoy used a Gaussian filter, but Laplace or wavelet filters are also conceivable; The article image processing provides an overview of filtering .
During the synthesis, the images of the noise pyramid are filled from top to bottom using the Efros and Leung method. The surroundings of a pixel include not only the pixel surroundings in the same image, but also pixels of all overlying pyramid images that are at roughly the same point in the image. This comparison on several resolution levels at the same time is the epitome of multi- scale analysis and ensures that the synthesis process automatically adapts to structures of different sizes in the template.
This multi-scale approach is supplemented by the binary tree-based vector quantization ( tree-structured vector quantization , TSVQ). The central component of this process, which actually serves to compress data, is a binary tree with vectors in its nodes. In addition to one pixel of an image of the template pyramid, each vector contains all pixels in the vicinity of this pixel (including those on higher pyramid levels), each node contains the mean average vector of all its children. Similar candidates can be searched for in this data structure much faster than in the original image.
Although with this technique, instead of individual images, entire image pyramids have to be synthesized and the binary tree has to be built before the first synthesis, this algorithm is considerably faster than its predecessor. In addition, it covers some types of textures better thanks to the multi-scale analysis.
Web links
- Texture Synthesis by Non-parametric Sampling - Homepage of AA Efros and TK Leung with additional information and sample images
- Revolution of the Virtual Worlds - Procedural Textures - Article on the use of procedural texture methods in applications with interactive examples
Individual evidence
- ↑ a b M. Tuceryan, AK Jain: Texture Analysis. In: CH Chen, LF Pau, PSP Wang (editors): The Handbook of Pattern Recognition and Computer Vision (2nd Edition). World Scientific Publishing Co., 1998, Chapter 2.1, pp. 207-248.
- ↑ a b M. Petrou, PG Seville: Image Processing: Dealing With Texture. Wiley, 2006. ISBN 0-470-02628-6
- ↑ Y. Liu, W.-C. Lin, J. Hays: Near-Regular Texture Analysis and Manipulation. 2004
- ^ AA Efros, TK Leung: Texture Synthesis by Non-parametric Sampling. In: Proceedings of IEEE International Conference on Computer Vision, Corfu, Greece, September 1999. PDF 1 MB
- ↑ M. Ashikhmin: Synthesizing Natural Textures. (PDF; 2 MB) In: The proceedings of 2001 ACM Symposium on Interactive 3D Graphics, Research Triangle Park, North Carolina March 19-21. Pp. 217-226
- ↑ Image Quilting for Texture Synthesis and Transfer , Alexei A. Efros en Willian T. Freeman (English)
- ↑ B. Guo, H. Shum, Y.-Q. Xu: Chaos Mosaic: Fast and Memory Efficient Texture Synthesis. Microsoft Research MSR-TR-2000-32, April 2000. PDF 8 MB
- ↑ L.-Y. Wei, M. Levoy: Fast Texture Synthesis using Tree-structured Vector Quantization. (PDF; 4.7 MB)