Research · September 20 – 27, 1999

A texture grown from a sample

In September 1999 at ICCV Alexei Efros and Thomas Leung of Berkeley showed texture synthesis without a model: a new image grows from a seed one pixel at a time, each pixel taken from a place in the sample whose neighbourhood resembles what has been made so far. There is one parameter, the window size.

Why it matters

Earlier methods described a texture by statistics and reproduced only random-looking samples. Here the sample itself became the model, and the same algorithm, unchanged, filled holes in a photograph. Patch-based methods of the 2000s rest on it, as does the Markov assumption that pix2pix in 2016 names outright as inherited from texture models.

ICCV 1999 proceedings, volume 2, pages 1033-1038. The conditional distribution of a pixel given its known neighbours is estimated by finding all similar neighbourhoods in the sample and picking one at random; Figure 2 shows windows of 5, 11, 15 and 23 pixels. The authors name the weaknesses themselves: the algorithm is "quite slow" and sometimes "grows garbage" or gets stuck copying the sample verbatim. The record does not claim a computing time: the paper gives no figure for it.

Event record

Event date

September 20, 1999 – September 27, 1999

Timeline date

Event date

Verification

Sources gathered automatically · September 25, 2026

Lines

Generative media

ID

evt-0803

The dates of the Seventh International Conference on Computer Vision in Kerkyra according to Crossref; the day of the talk is not given.

Sources

primary Texture Synthesis by Non-parametric Sampling (Alexei A. Efros, Thomas K. Leung), ICCV 1999, vol. 2, pp. 1033-1038
IEEE (Seventh International Conference on Computer Vision); author copy at UC Berkeley · Published September 1999

Related events

Builds on A Mathematical Theory of Communication
The paper derives its method from Shannon: his n-grams of 1948, which produce English-looking text, carried into two dimensions.
Texture Synthesis by Non-parametric Sampling (Alexei A. Efros, Thomas K. Leung), ICCV 1999, vol. 2, pp. 1033-1038
Enables pix2pix: one model for image translation
pix2pix says its discriminator models the image as a Markov random field, "the common assumption in models of texture", and cites this paper first.
Image-to-Image Translation with Conditional Adversarial Networks (arXiv:1611.07004v1)

Records that link to this one

Contrasts Inpainting: a restorers’ word for a machine
The paper names Efros and Leung’s texture synthesis as a way to fill a region with a pre-selected texture and builds a method that needs no source for the new information.
Image Inpainting (Marcelo Bertalmio, Guillermo Sapiro, Vicent Caselles, Coloma Ballester), SIGGRAPH 2000, pp. 417-424
Builds on Image Analogies: a filter from a pair of examples
The paper derives its method from texture synthesis by nearest-neighbourhood search and names Efros and Leung among its authors.
Image Analogies (Aaron Hertzmann, Charles E. Jacobs, Nuria Oliver, Brian Curless, David H. Salesin), SIGGRAPH 2001, pp. 327-340
Extends A hole in a picture filled from other photographs
The paper traces existing completion methods to Efros and Leung’s texture synthesis and drops their assumption that the material for the fill lies in the same image.
Scene Completion Using Millions of Photographs (James Hays, Alexei A. Efros), ACM Transactions on Graphics 26(3), SIGGRAPH 2007, article 4
Builds on PatchMatch: patches found at random
The paper opens its survey with Efros and Leung introducing non-parametric texture synthesis by patches from a sample in 1999, the search it speeds up.
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing (Connelly Barnes, Eli Shechtman, Adam Finkelstein, Dan B Goldman), ACM Transactions on Graphics 28(3), SIGGRAPH 2009