Micro-Texture Synthesis by Phase Randomization

This workshop may eventually be submitted and published.

Overview
References
Online Demo: Try It!
Source Code
Algorithm
Implementation
Micro-textures
Examples

Bruno Galerne, galerne@cmla.ens-cachan.fr, CMLA, ENS Cachan, CNRS, UniverSud
Yann Gousseau, gousseau@enst.fr, LTCI CNRS, Télécom ParisTech
Jean-Michel Morel, morel@cmla.ens-cachan.fr, CMLA, ENS Cachan, CNRS, UniverSud

Overview

This contribution is concerned with texture synthesis by example, the process of generating new texture images from a given example image. This field has witnessed an important number of key contributions over the last 15 years, see e.g. [2,3,4,5].

The Random Phase Noise (RPN) algorithm presented here, and first introduced in the paper [1], synthesizes a texture from an original image by randomizing its Fourier phase. It is able to reproduce textures which are characterized by their Fourier modulus, namely the random phase textures (or micro-textures). It is also able to create a random texture from any input image. It is in spirit quite close to the noise generators from computer graphics, see e.g. [6,7].

The presented algorithm deals with color images and it is able to synthesize output textures with arbitrary sizes.

The algorithm is limited to a certain class of textures, but it has the following good properties, that are particularly useful for graphic applications and are not shared by, e.g., examplar-based methods.

It is fast, since it basically only needs the computation of two FFTs.
It is perceptually stable: all the textures synthesized from the same input image are visually similar. In particular, it will never grow garbage.
It will never yield verbatim copy of the original.

References

B. Galerne, Y. Gousseau and J.-M. Morel, Random Phase Textures: Theory and Synthesis, to appear in IEEE Trans. on Image Processing, preprint CMLA N°2009-24, 2009.
Abstract and pdf file on CMLA preprint webpage.
A. A. Efros and T. K. Leung, Texture Synthesis by Non-parametric Sampling, Proceedings of ICCV, 1999.
L.-Y. Wei and M. Levoy, Fast Texture Synthesis using Tree-structured Vector Quantization, Proceedings of SIGGRAPH, 2000.
D. J. Heeger and J. R. Bergen, Pyramid-based texture analysis/synthesis, Proceedings of SIGGRAPH, 1995..
E. P. Simoncelli and J. Portilla, Texture Characterization via Joint Statistics of Wavelet Coefficient Magnitudes, Proceedings of ICIP, 98.
K. Perlin, An image synthesizer, Proceedings of SIGGRAPH, 85.
J. J. van Wijk, Spot noise texture synthesis for data visualization, Proceedings of SIGGRAPH, 1991.
L. Moisan, Periodic plus Smooth Image Decomposition, preprint MAP5, Université Paris Descartes, 2009 (submitted). Abstract and pdf file on HAL.

Online Demo: Try It!

An on-line demo of this algorithm is available.

The demo permits to upload a color texture sample and to replicate it with arbitrary size. Texture samples can be taken from existing databases, but to have still more realistic samples, you can extract them as homogeneous regions of a photograph, as shown below in What are micro-textures?

Source Code

An implementation is available for download. It is provided with an illustated html documentation:

source code zip, tar/gz;
documentation zip, tar/gz, online.

This code requires libtiff, libfftw3 and getopt. It should compile on any system since it's only ANSI C. Compilation and usage instruction are included in a README.txt file.

Algorithm

Basic RPN

By definition, the RPN of an image h is the random image obtained by adding a random phase θ to the Fourier phase of the image. By a random phase we mean a white noise image uniformly distributed over [-π,π] and that is constrained to be symmetric. Then the basic RPN algorithm consists in:

Compute a realization θ of a random phase.
Compute the discrete Fourier transform (DFT) $\hat{h}$ of h.
Add the random phase: $\hat{h}(\xi_1,\xi_2) \leftarrow \hat{h}(\xi_1,\xi_2) e^{i\theta(\xi_1,\xi_2)}.$
Return the inverse DFT of $\hat{h}$ .

Extension to Color Images

The RPN of an RGB color image h=(h_R, h_G, h_B) is obtained in adding the same random phase to the DFT of each color channel. More precisely, step 3. of the above basic RPN algorithm is replaced by

$\left(\hat{h}_R(\xi_1,\xi_2),\hat{h}_G(\xi_1,\xi_2),\hat{h}_B(\xi_1,\xi_2)\right) \leftarrow \left(\hat{h}_R(\xi_1,\xi_2),\hat{h}_G(\xi_1,\xi_2),\hat{h}_B(\xi_1,\xi_2)\right) e^{i\theta(\xi_1,\xi_2)}.$

Adding the same random phase to the original phases of each color channel preserves the phase displacements between channels. This is important as it permits to create new textures without creating false colors.

Avoiding Artifacts Due to Non Periodicity

The RPN algorithm is based on the FFT and consequently the periodicity of the input image is a critical requirement. Indeed, as experiments show, randomizing the phase of an image which is not periodic creates strong artifacts consisting in highly contrasted horizontal and vertical waves. To avoid these artifacts the input image h is replaced by its periodic component p as defined by L. Moisan in Periodic plus Smooth Image Decomposition (Reference 2).

The periodic component p is the unique solution of the problem

$\left\{ \begin{array}{ccc} \Delta p & = & \Delta_i h, \\ \operatorname{mean}(p) & = & \operatorname{mean}(h), \end{array} \right.$ where Δ is the usual discrete periodic Laplacian (each point has four neighbors) and $\Delta_i$ is the discrete Laplacian in the interior of the image domain (points at the border of the image have only three or two neighbors).

The periodic component p of h is computed using the classic FFT-based Poisson solver:

Compute the discrete Laplacian $\Delta_i h$ of h.
Compute the DFT $\widehat{\Delta_i h}$ of $\Delta_i h$ .
Compute the DFT $\hat{p}$ of p by inversing the discrete periodic Laplacian: $\left\{ \begin{array}{ccc} \hat{p}(\xi_1,\xi_2) & = & \left(4-2\cos\left( \frac{2 \xi_1 \pi}{M} \right)-2\cos\left( \frac{2 \xi_2 \pi}{N}\right)\right)^{-1} \widehat{\Delta_i h}(\xi_1,\xi_2),\\ \hat{p}(0) & = & \sum_{(x,y)} h(x,y). \end{array} \right.$
Compute p by inverse DFT.

Note that this procedure permits to compute the DFT $\hat{p}$ of p using only one call to the FFT algorithm. Let us also precise that computing the periodic component of a color image simply consists in computing the periodic component of each color channel.

Spot Extension Technique

An important issue in texture synthesis is to synthesize textures with arbitrary large size from a given sample.

Here we propose a practical method which solves this problem for RPN textures. This is done in extending the original texture sample into an equivalent spot having a larger size, and then apply the basic RPN algorithm to this larger equivalent spot, as illustrated by the example below.

A texture image (left) and its corresponding extended spot (right)

Let us detail precisely how the extended spot is computed. First, the periodic component of the original texture sample is computed and pasted in a large constant image equals to the mean of the sample, with a previous variance normalization. The obtained image is then multiplied by a smooth transition function in order to attenuate the discontinuities along the inner frame of the spot. On the interval [0,1], the smooth transition function $\varphi_\alpha$ is defined as follows: On [0,α] the function varies as the primitive of the standard $\mathcal{C}^{\infty}$ function

$t \mapsto \exp\left(-1/\left(1-(2t/\alpha -1)^2\right)\right),$ it is symmetrically defined on the interval [1-α,1] and it is constant to 1 on the inner interval [α,1-α]. Below are both a cross section and a gray-level representation of the smooth transition function used to attenuate the spot along the border of the image.

Smooth transition function used to attenuate the extended spot along the border of the image

In addition, in order to preserve the variance of the initial spot, the smooth function is normalized so that its L²-norm equals 1. The value of the parameter α is not very sensible and for all experiments as well as for the online demo the parameter α has been fixed to α=0.1. However α is an optional parameter of the downloadable source code.

Implementation

Our implementation consists in two distinct procedures: same size RPN and increased size RPN.

Same size RPN

The whole algorithm for synthesizing a RPN texture having the same size as the original image h consists in the following steps:

Compute the DFT $\hat{p}$ of the periodic component p of the input image h.
Compute a realization θ of a random phase.
Add the random phase θ to each color channel of $\hat{p}$ .
Return the inverse DFT of the phase randomized $\hat{p}$ .

Note that this algorithm only uses two calls to the FFT algorithm.

Increased size RPN

Compute the periodic component p of the input image h.
Extend the periodic component p into an equivalent spot of larger size using the spot extension technique described above.
Compute a random phase θ having the same size as the extended spot.
Compute the RPN in adding the random phase θ to the DFT of each color channel.

This procedure is more computionally expensive than the "same size RPN" one since it makes four calls the FFT algorithm: two with the size of the original spot h for the computation of the periodic component p, and two with the larger output size for the phase randomization.

Micro-textures

What are Micro-textures

When photographed, remote homogeneous objects made of thin, small, or semitransparent objects create homogeneous regions in images. The geometric features and colors of the object's constituents are mixed, due to the blur inherent to image formation. The resulting image region is a micro-texture. Most homogeneous regions in any image should be micro-textures. The figure below shows an example. Five rectangles belonging to various homogeneous regions were picked in a high resolution landscape. These textures are displayed in pairs where the left is the original sub-image, and the right a simulation obtained by the RPN algorithm. With the exception of the clouds rectangle (which is obviously non-stationary), these samples and their simulated copies are usually considered perceptually equivalent by observers. Yet, not all homogeneous regions of an image are micro-textures. See below many examples, and the failure catalog as well.

Some emulated textures taken from an high resolution landscape

Homogeneous regions in any image made of objects at large enough distance are micro-textures, and can be emulated by RPN. Here pebbles, wet sand, and various types of waves are correctly simulated.

The samples in the above image are micro-textures. However, not all image homogeneous parts are micro-textures.

Micro-textures and Macro-textures

Many images or image parts usually termed textures do not fit to the micro-texture requisites. Typically, periodic patterns with big visible elements, such as brick walls, are not micro-textures. More generally, textures whose building elements are spatially organized, such as the branches of a tree, are not micro-textures. Yet, each textured object has a critical distance at which it becomes a micro-texture. For instance, tiles at a close distance are a macro-texture, and are not amenable to phase randomization. The smaller tiles on roofs photographed at some distance can instead be emulated.

Microtextures: tiled roofs

samples

RPN

?Tuiles.jpg

Tiles from roof 1 emulated by RPN

?tuiles2.jpg

Tiles from roof 1 emulated by RPN

A macro-texture: tiles at short range

RPN failure to simulate a macro-texture

Examples

Below are some examples of satisfyingly well reproduced textures.

Original image

RPN

stone

stone simulated

wood

wood simulated

wall paper

wall paper simulated

wall

wall simulated

Wood

Wood samples must be homogeneous in direction to be correctly emulated by RPN. Wood samples with knots or other conspicuous patterns fall logically in the failure catalog.

Wood sample	RPN simulation

More Wood Examples

Wood sample	RPN simulation

Fabric

These fabric samples were picked from several web sites. Only homogeneous fabrics, with no printed on patterns are treated. RPN turns out to work remarkably on jeans fabrics.

Fabric sample	RPN simulation

More Fabric Examples

Fabric sample	RPN simulation

Carpet

These carpet samples are taken from a single commercial website. Those with big patterns will be found in the failure catalog.

Carpet sample	RPN simulation

More Carpet Examples

Carpet sample	RPN simulation

Failure Catalog

Most failures are macro-textures. For instance:

textures containing periodic geometric patterns with large period,
textures containing strong edges, such as veins in marble or cracks in bark
textures containing definite shapes, such as knots in wood or fruit or visible leaves in foliage
strictly periodic patterns, even with small period, where phase shifts cause aliasing effects
failure also occurs when the sample texture contains different dominant directions in different areas. Then these directions are mixed by the random sampler.

Macro-texture sample	RPN simulation

More Failure Examples (Macro-textures)

Macro-texture sample	RPN simulation