H4: Texture Synthesis

The problem

Given texture I, generate texture J

• That looks like I (or differs from I in the same way as I differs from itself)

• Doesn’t show any obvious copying or tiling

Types of Textures and Techniques

• Model-based methods

  • First-order statistics (pyramidal methods)

  • Using Markov Random Fields (We don’t treat in this course)

• Tiling and patch methods

  • “Image Quilting”

  • Wang tiles

• Hybrid methods (tiling + stochastic modeling)

Pyramidal Methods (Heeger&Bergen)

Two textures are difficult to discriminate if they produce similar responses in a bank of (orientation and frequency selective) linear filters

Suitable for homogeneous stochastic textures!

Where they don’t work

Pyramidal Decomposition

Discrete Wavelet Transform (DWT)

• DWT algorithm: a filter bank iterated on the lowpass output

• The same texture synthesis concept can be applied using image pyramid or DWT or a related multiresolution image representation

Twp dimensional DWT

Histogram matching

In the context of Chapter 4 (Texture Synthesis), Histogram Matching is a core mathematical operation used in Pyramidal Methods (specifically the Heeger & Bergen method) to synthesize new textures.

The overall goal of this method is to take an initial image of random noise and iteratively force it to look like a given "example" texture by matching their statistical properties (first-order statistics) at various scales and orientations.

Here is an intuitive breakdown of how the histogram matching process works:

• Pyramidal Decomposition: First, both the example texture (I1​) and the noise image (I2​) are decomposed into a pyramid (like a Laplacian or Steerable pyramid). This breaks the images down into multiple "subbands" that isolate different resolutions (scales) and orientations.

• Analyzing the Histograms: At each level of the pyramid, the algorithm calculates the histogram of the subband coefficients. The shape of these histograms tells us important information about the texture. For instance, if a histogram has long tails, it means there are more large coefficients, which indicates the presence of stronger edges in that specific orientation and resolution.

• The Matching Process: The algorithm mathematically forces the histogram of the noise subband to match the histogram of the example subband. It does this by using their cumulative distribution functions (CDFs), denoted as F1​ and F2​:

  1. It takes a pixel value from the noise image and looks up its cumulative probability using a Look-Up Table (C2​=LUT2​(g2​)).

  2. It then uses the Inverse Look-Up Table of the example texture (ILUT1​) to find the exact pixel value in the example that corresponds to that same cumulative probability.

  3. This translates to the formula: I2​(m,n)=ILUT1​(LUT2​(I2​(m,n))).

• Iteration: This matching step (MH) is performed iteratively across every level of the pyramid. As the noise image's histograms are forced to match the example's histograms at every scale and orientation, the noise gradually transforms into a synthesized texture that visually mimics the original.

This approach is highly effective for generating homogeneous stochastic textures (like sand, bark, or rough surfaces), but struggles with highly structured or complex regular patterns where first-order statistics are not enough to capture the spatial relationships.

Pyramidal Methods: Summary

• Based on first-order statistics

• Motivated by studies of the human visual system

• Effective for homogeneous stochastic textures

Image Quilting

Step 1: position overlapping blocks sequentially

Step 2: Find optimal borders in the overlapping regions

Results:

✓ Works rather well for all texture types

But

• Computationally intensive

• The influence of the block size is difficult to define

Image Quilting and texture transfer

Image Quilting: summary

• A tiling method

• “Glues” blocks from the input texture sample

• Works for almost all texture types

• Computationally intensive

Wang tiles

• Square tiles with color-coded edges.

• Cannot be rotated in the tiling!

• This tiling was named after Hao Wang, who conjectured in 1961 that any

  set that can produce a valid tiling of the plane must also be able to

  produce a periodic tiling

  • Later showed: not true! Berger (student of Wang) disproved this in 1966.

• In the computer graphics we use sets that make periodic and not periodic

  tiling (e.g. the set of 8 tiles above)

Wang tiles

• Stochastic tiling

• If there is at least one tile for each N-W combination → correct tiling is guaranteed

• If there are at least two tiles for each N-W combination → not periodic tiling is guaranteed.

Wang Tiles:

• Tile Design by Quilting

Introducing Inhomogeneity

We learned to solve this: extending to arbitrary size, no copying or tiling obvious, but does it look natural?

• •For each tile: 2^4=16 possible corner codings

  • A set of 8 tiles extends to 8x16=128 tiles

• This can be reduced to 64 and still keeping the stochastic selection. Why? (How many corners do we need to match at each step?)

Einstein problem

Einstein problem asks about the existence of a single prototile that by itself forms an aperiodic set of prototiles; that is, a shape that can tessellate space but only in a nonperiodic way.

Wang Tiles: Summary

• The process of making tiles is complex (quilting)

• Once tiles are made, tiling very fast

• Works for almost all texture types

• Very powerful for producing non-homogeneous textures

Algemene summary

• Pyramidal methods based on first-order statistics

  • Work well for stochastic textures

  • Not for non-homogeneous textures, regular patterns and complex composites

• Image Quilting

  • Conceptually simple but computationally intensive

  • For all textures (sometimes there are artifacts)

  • Very good for texture transfer and for making Wang tiles

• Wang Tiles

  • Fast and simple, making infinitely large textures

  • Very good for complex textures

  • Making not homogeneous textures: coded corners and edges