Texture synthesis
Encyclopedia
Texture synthesis is the process of algorithm
ically constructing a large digital image
from a small digital sample image by taking advantage of its structural content. It is object of research to computer graphics
and is used in many fields, amongst others digital image editing, 3D computer graphics
and post-production of films.
Texture synthesis can be used to fill in holes in images (as in inpainting
), create large non-repetitive background images and expand small pictures.
See "SIGGRAPH 2007 course on Example-based Texture Synthesis" for more details.
"Texture" is an ambiguous word and in the context of texture synthesis may have one of the following meanings:
Texture can be arranged along a spectrum going from stochastic to regular:
These extremes are connected by a smooth transition, as visualized in the figure below from "Near-regular Texture Analysis and Manipulation." Yanxi Liu, Wen-Chieh Lin, and James Hays. SIGGRAPH 2004
Like most algorithms, texture synthesis should be efficient in computation time and in memory use.
The result is an acceptable texture image, which is not too repetitive and does not contain too many artifacts. Still, this method is unsatisfactory because the smoothing in step 3 makes the output image look blurred.
, to perform many interesting tasks. They are typically accelerated with some form of Approximate Nearest Neighbor method since the exhaustive search for the best pixel is somewhat slow. The synthesis can also be performed in multiresolution, such as "Texture synthesis via a noncausal nonparametric multiscale Markov random field." Paget and Longstaff, IEEE Trans. on Image Processing, 1998.
to manually synthesize a texture. "Image Quilting." Efros and Freeman. SIGGRAPH 2001 and "Graphcut Textures: Image and Video Synthesis Using Graph Cuts." Kwatra et al. SIGGRAPH 2003 are the best known patch-based texture synthesis algorithms. These algorithms tend to be more effective and faster than pixel-based texture synthesis methods.
The method works by constructing a pattern database. It will then use multi-dimensional scaling, and kernel methods to cluster the patterns into similar group. During the simulation, it will find the most similar cluster to the pattern at hand, and then, randomly selects a pattern from that cluster to paste it on the output grid. It continues this process until all the cells have been visited.
chemical reactions within fluids, namely Reaction-diffusion systems. It is believed that these systems show behaviors which are qualitatively equivalent to real processes (Morphogenesis
) found in the nature, such as animal markings (shells, fishs, wild cats...).
:
A pixel-based texture synthesis implementation:
Patch-based texture synthesis using Graphcut:
although there was also earlier work on the subject, such as
(The latter algorithm has some similarities to the Chaos Mosaic approach).
The non-parametric sampling approach of Efros-Leung is the first approach that can easily synthesis most types of texture, and it has inspired literally hundreds of follow-on papers in computer graphics. Since then, the field of texture synthesis has rapidly expanded with the introduction of 3D graphics accelerator cards for personal computers. It turns out, however, that Scott Draves
first published the patch-based version of this technique along with GPL code in 1993 according to Efros.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
ically constructing a large digital image
Digital image
A digital image is a numeric representation of a two-dimensional image. Depending on whether or not the image resolution is fixed, it may be of vector or raster type...
from a small digital sample image by taking advantage of its structural content. It is object of research to computer graphics
Computer graphics
Computer graphics are graphics created using computers and, more generally, the representation and manipulation of image data by a computer with help from specialized software and hardware....
and is used in many fields, amongst others digital image editing, 3D computer graphics
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
and post-production of films.
Texture synthesis can be used to fill in holes in images (as in inpainting
Inpainting
Inpainting is the process of reconstructing lost or deteriorated parts of images and videos. For instance, in the case of a valuable painting, this task would be carried out by a skilled image restoration artist...
), create large non-repetitive background images and expand small pictures.
See "SIGGRAPH 2007 course on Example-based Texture Synthesis" for more details.
Textures
- In common speech, "texture" used as a synonym for "surface structure". Texture has been described by five different properties in the psychology of perception: coarseness, contrast, directionality, line-likeness and roughness .
- In 3D computer graphics3D computer graphics3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...
, a texture is a digital image applied to the surface of a three-dimensional model by texture mappingTexture mappingTexture mapping is a method for adding detail, surface texture , or color to a computer-generated graphic or 3D model. Its application to 3D graphics was pioneered by Dr Edwin Catmull in his Ph.D. thesis of 1974.-Texture mapping:...
to give the model a more realistic appearance. Often, the image is a photograph of a "real" texture, such as wood grainWood grainIn speaking of wood the term grain refers to the alternating regions of relatively darker and lighter wood resulting from the differing growth parameters occurring in different seasons . The term is used in several ways. Perhaps most important is that in woodworking techniques...
. - In image processingImage processingIn electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
, every digital image composed of repeated elements is called a "texture." For example, see the images below.
Texture can be arranged along a spectrum going from stochastic to regular:
- Stochastic textures. Texture images of stochastic textures look like noise: colour dots that are randomly scattered over the image, barely specified by the attributes minimum and maximum brightness and average colour. Many textures look like stochastic textures when viewed from a distance. An example of a stochastic texture is roughcast.
- Structured textures. These textures look like somewhat regular patterns. An example of a structured texture is a stonewall or a floor tiled with paving stones.
These extremes are connected by a smooth transition, as visualized in the figure below from "Near-regular Texture Analysis and Manipulation." Yanxi Liu, Wen-Chieh Lin, and James Hays. SIGGRAPH 2004
Goal
Texture synthesis algorithm are intended to create an output image that meets the following requirements:- The output should have the size given by the user.
- The output should be as similar as possible to the sample.
- The output should not have visible artifacts such as seams, blocks and misfitting edges.
- The output should not repeat, i. e. the same structures in the output image should not appear multiple places.
Like most algorithms, texture synthesis should be efficient in computation time and in memory use.
Methods
The following methods and algorithms have been researched or developed for texture synthesis:Tiling
The simplest way to generate a large image from a sample image is to tile it. This means multiple copies of the sample are simply copied and pasted side by side. The result is rarely satisfactory. Except in rare cases, there will be the seams in between the tiles and the image will be highly repetitive.Stochastic texture synthesis
Stochastic texture synthesis methods produce an image by randomly choosing colour values for each pixel, only influenced by basic parameters like minimum brightness, average colour or maximum contrast. These algorithms perform well with stochastic textures only, otherwise they produce completely unsatisfactory results as they ignore any kind of structure within the sample image.Single purpose structured texture synthesis
Algorithms of that family use a fixed procedure to create an output image, i. e. they are limited to a single kind of structured texture. Thus, these algorithms can both only be applied to structured textures and only to textures with a very similar structure. For example, a single purpose algorithm could produce high quality texture images of stonewalls; yet, it is very unlikely that the algorithm will produce any viable output if given a sample image that shows pebbles.Chaos mosaic
This method, proposed by the Microsoft group for internet graphics, is a refined version of tiling and performs the following three steps:- The output image is filled completely by tiling. The result is a repetitive image with visible seams.
- Randomly selected parts of random size of the sample are copied and pasted randomly onto the output image. The result is a rather non-repetitive image with visible seams.
- The output image is filtered to smooth edges.
The result is an acceptable texture image, which is not too repetitive and does not contain too many artifacts. Still, this method is unsatisfactory because the smoothing in step 3 makes the output image look blurred.
Pixel-based texture synthesis
These methods, such as "Texture synthesis via a noncausal nonparametric multiscale Markov random field." Paget and Longstaff, IEEE Trans. on Image Processing, 1998, "Texture Synthesis by Non-parametric Sampling." Efros and Leung, ICCV, 1999, "Fast Texture Synthesis using Tree-structured Vector Quantization" Wei and Levoy SIGGRAPH 2000 and "Image Analogies" Hertzmann et al. SIGGRAPH 2001. are some of the simplest and most successful general texture synthesis algorithms. They typically synthesize a texture in scan-line order by finding and copying pixels with the most similar local neighborhood as the synthetic texture. These methods are very useful for image completion. They can be constrained, as in image analogiesImage analogy
An "image analogy" is a method of creating an image filter automatically from training data. In an image analogy process, the transformation between two images A and A' is "learned"...
, to perform many interesting tasks. They are typically accelerated with some form of Approximate Nearest Neighbor method since the exhaustive search for the best pixel is somewhat slow. The synthesis can also be performed in multiresolution, such as "Texture synthesis via a noncausal nonparametric multiscale Markov random field." Paget and Longstaff, IEEE Trans. on Image Processing, 1998.
Patch-based texture synthesis
Patch-based texture synthesis creates a new texture by copying and stitching together textures at various offsets, similar to the use of the clone toolClone tool
The clone tool, as it is known in Adobe Photoshop, GIMP, and Corel PhotoPaint, is used in digital image editing to replace information for one part of a picture with information from another part...
to manually synthesize a texture. "Image Quilting." Efros and Freeman. SIGGRAPH 2001 and "Graphcut Textures: Image and Video Synthesis Using Graph Cuts." Kwatra et al. SIGGRAPH 2003 are the best known patch-based texture synthesis algorithms. These algorithms tend to be more effective and faster than pixel-based texture synthesis methods.
Pattern-based texture modeling
In pattern-based modeling a training image consisting of stationary textures are provided. The algorithm performs stochastic modeling, similar to the patch-based texture synthesis, to reproduce the same spatial behavior.The method works by constructing a pattern database. It will then use multi-dimensional scaling, and kernel methods to cluster the patterns into similar group. During the simulation, it will find the most similar cluster to the pattern at hand, and then, randomly selects a pattern from that cluster to paste it on the output grid. It continues this process until all the cells have been visited.
Chemistry based
Realistic textures can be generated by simulations of complexchemical reactions within fluids, namely Reaction-diffusion systems. It is believed that these systems show behaviors which are qualitatively equivalent to real processes (Morphogenesis
Morphogenesis
Morphogenesis , is the biological process that causes an organism to develop its shape...
) found in the nature, such as animal markings (shells, fishs, wild cats...).
Implementations
Some texture synthesis implementations exist as plug-ins for the free image editor GimpGimp
Gimp may refer to:* GIMP, the GNU Image Manipulation Program* Gimp , a type of sexual submissive in BDSM who may wear a bondage suit* Gimp , an ornamental trim used in sewing or embroidery...
:
A pixel-based texture synthesis implementation:
Patch-based texture synthesis using Graphcut:
Literature
Several of the earliest and most referenced papers in this field include:- Popat in 1993 - "Novel cluster-based probability model for texture synthesis, classification, and compression".
- Heeger-Bergen in 1995 - "Pyramid based texture analysis/synthesis".
- Paget-Longstaff in 1998 - "Texture synthesis via a noncausal nonparametric multiscale Markov random field"
- Efros-Leung in 1999 - "Texture Synthesis by Non-parameteric Sampling".
- Wei-Levoy in 2000 - "Fast Texture Synthesis using Tree-structured Vector Quantization"
although there was also earlier work on the subject, such as
- Gagalowicz and Song De Ma in 1986 , "Model driven synthesis of natural textures for 3-D scenes",
- Lewis in 1984, "Texture synthesis for digital painting".
(The latter algorithm has some similarities to the Chaos Mosaic approach).
The non-parametric sampling approach of Efros-Leung is the first approach that can easily synthesis most types of texture, and it has inspired literally hundreds of follow-on papers in computer graphics. Since then, the field of texture synthesis has rapidly expanded with the introduction of 3D graphics accelerator cards for personal computers. It turns out, however, that Scott Draves
Scott Draves
Scott Draves is the inventor of Fractal Flames and the leader of the distributed computing project Electric Sheep. He also invented patch-based texture synthesis and published the first implementation of this class of algorithms...
first published the patch-based version of this technique along with GPL code in 1993 according to Efros.
See also
- Granular synthesisGranular synthesisGranular synthesis is a basic sound synthesis method that operates on the microsound time scale.It is based on the same principle as sampling. However, the samples are not played back conventionally, but are instead split into small pieces of around 1 to 50ms. These small pieces are called grains...
, a similar technique for audio rather than images - InpaintingInpaintingInpainting is the process of reconstructing lost or deteriorated parts of images and videos. For instance, in the case of a valuable painting, this task would be carried out by a skilled image restoration artist...
- Seam carvingSeam carvingSeam carving , is an algorithm for image resizing, developed by Shai Avidan, of Mitsubishi Electric Research Labs , and Ariel Shamir, of the Interdisciplinary Center and MERL...
External links
- texture synthesis
- texture synthesis
- texture movie synthesis
- Texture2005
- Near-Regular Texture Synthesis
- The Texture Lab
- Nonparametric Texture Synthesis
- Examples of reaction-diffusion textures
- Implementation of Efros & Leung's algorithm with examples
- Micro-texture synthesis by phase randomization, with code and online demonstration