Fast texture synthesis using tree-structured vector quantization

Li-Yi WeiMarc Levoy

article2000SIGGRAPH1,750 citationsTest of Time Award (IEEE CG&A 2022)

Accelerates Markov Random Field-based texture synthesis by two orders of magnitude using tree-structured vector quantization, enabling high-quality, real-time texture generation and image editing from a single exemplar.

Listen

Texture synthesis is critical across computer graphics, image processing, and visual effects for generating seamless, repeatable surface imagery from small input samples. However, conventional techniques face a difficult trade-off: statistical feature-matching methods are fast but often distort complex structural patterns, while probabilistic Markov Random Field methods produce realistic, high-quality textures but require heavy computation that often takes hours to generate small patches. The article evaluates and demonstrates a fast, deterministic texture synthesis algorithm that combines multi-resolution image pyramids with tree-structured vector quantization to generate high-fidelity, seamlessly tileable textures.

The evaluated approach models textures under locality and stationarity assumptions, synthesizing an output image pixel by pixel from coarse to fine resolution levels. Instead of performing slow probabilistic sampling, the method treats pixel neighborhood matching as a nearest-point search in high-dimensional space and accelerates it using tree-structured vector quantization codebooks. To validate the method, the authors tested it across diverse standard texture datasets (such as the MIT VisTex collection) and applied it to advanced image editing, image hole filling, and three-dimensional motion sequences including fire, smoke, and ocean waves.

The key findings demonstrate significant performance gains and broad versatility. First, the accelerated algorithm runs roughly two orders of magnitude faster than comparable high-quality sampling methods; for example, it synthesized a sample image in 24 seconds (12 seconds of training and 12 seconds of synthesis) compared to 1,941 seconds required by an existing state-of-the-art method. Second, visual fidelity matches or exceeds prior techniques while naturally enforcing seamless tiling at image boundaries. Third, tree-structured vector quantization codebooks reduced memory demands effectively, with codebooks containing under 10 percent of the original input vectors producing visual quality comparable to exhaustive search. Fourth, extending the method with two-pass spiral processing and three-dimensional temporal neighborhoods successfully enabled artifact-free image hole filling and realistic motion texture synthesis at approximately 20 seconds per frame.

These findings mean that realistic texture synthesis can transition from an expensive offline computation into a fast, practical tool for interactive digital workflows. For organizations in graphics production, digital restoration, and simulation, this approach substantially reduces computational overhead and project timelines without sacrificing visual quality. Because the algorithm requires only a single sample image and minimal parameter tuning, it also streamlines production pipelines and expands capabilities into temporal video textures.

Organizations should consider adopting tree-structured vector quantization-based texture synthesis for graphics asset creation, hole filling in image editing, and background dynamic effects. When implementing the method, teams should tune codebook sizes and tree-traversal backtracking parameters to balance memory footprint against image sharpness. Further work is recommended to explore real-time decompression architectures, enable direct synthesis on irregular three-dimensional surface meshes, and incorporate explicit user controls over dynamic animations.

The primary limitation of this method is its fundamental reliance on the stationarity and locality assumptions of Markov Random Fields; consequently, it cannot capture non-repeating global structures, three-dimensional depth, explicit lighting changes, or complex articulated motions such as human movement. Within its intended domain of stationary two-dimensional and three-dimensional textures, the reported results demonstrate high reliability and consistent performance across diverse test cases.

  • Paper: Image quilting for texture synthesis and transfer, Alexei A. Efros et al. (2001). This work advances beyond pixel-by-pixel Markov random field synthesis to patch-based quilting, dramatically improving local structural coherence and synthesis speed.
  • Paper: Image Analogies, Aaron Hertzmann et al. (2001). This paper extends example-based multiscale texture synthesis and approximate nearest-neighbor search into a general framework for learning visual image analogies and artistic styles.
  • Paper: PatchMatch: a randomized correspondence algorithm for structural image editing, Connelly Barnes et al. (2009). This work introduces a highly efficient randomized nearest-neighbor correspondence algorithm that revolutionizes fast patch-based texture and structural image synthesis.
  • Paper: Super-resolution from a single image, Daniel Glasner et al. (2009). This research applies the principle of recurring internal texture patches across multiscale image pyramids to perform single-image super-resolution without external training sets.
  • Paper: Image inpainting, Marcelo Bertalmio et al. (2000). This paper introduces automated image inpainting for seamless region filling, providing an alternative partial-differential-equation approach to the constrained texture synthesis applications proposed by the source.
Cover for Fast texture synthesis using tree-structured vector quantization

Abstract

Texture synthesis is important for many applications in computer graphics, vision, and image processing. However, it remains difficult to design an algorithm that is both efficient and capable of generating high quality results. In this paper, we present an efficient algorithm for realistic texture synthesis. The algorithm is easy to use and requires only a sample texture as input. It generates textures with perceived quality equal to or better than those produced by previous techniques, but runs two orders of magnitude faster. This permits us to apply texture synthesis to problems where it has traditionally been considered impractical. In particular, we have applied it to constrained synthesis for image editing and temporal texture generation. Our algorithm is derived from Markov Random Field texture models and generates textures through a deterministic searching process. We accelerate this synthesis process using tree-structured vector quantization.

Table of Contents

  • 1 Introduction
  • 1.1 Previous Work
  • 1.2 Overview
  • 2 Algorithm
  • 2.1 Single Resolution Synthesis
  • 2.2 Neighborhood
  • 2.3 Multiresolution Synthesis
  • 2.4 Edge Handling
  • 2.5 Initialization
  • 2.6 Summary of Algorithm
  • 3 Synthesis Results
  • 4 Acceleration
  • 4.1 TSVQ Acceleration
  • 4.2 Acceleration Results
  • 5 Applications
  • 5.1 Constrained Texture Synthesis
  • 5.2 Temporal Texture Synthesis
  • 6 Conclusions and Future Work
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — Multiresolution Deterministic Texture Synthesis Algorithm

    algorithm

    The multiresolution texture synthesis algorithm synthesizes an output texture image IsI_s of arbitrary requested dimensions from an input sample texture IaI_a. It models texture through Markov Random Fields (MRFs) using a deterministic nearest-neighbor search rather than explicit probabilistic sampling.

    Both the input image IaI_a and an initialized output noise image IsI_s are decomposed into Gaussian pyramids, denoted GaG_a and GsG_s respectively. Synthesis progresses coarse-to-fine from the lowest resolution pyramid level down to the finest level. At each pyramid level LL, output pixels p=(xs,ys)p = (x_s, y_s) are assigned sequentially in raster-scan order. For each pixel pp, a causal multiresolution neighborhood vector N(p)N(p) is constructed across the current and lower pyramid levels. The algorithm searches through all valid candidate neighborhood vectors N(pi)N(p_i) in the corresponding level of the input pyramid GaG_a to find the best match minimizing the sum of squared differences (L2L_2 norm). The color of the central pixel pip_i corresponding to the winning neighborhood is assigned directly to pp.

    function TextureSynthesis(Ia, outputSize):
        Is = Initialize(outputSize)
        Ga = BuildPyramid(Ia)
        Gs = BuildPyramid(Is)
        for each level L from coarsest to finest of Gs:
            for each pixel (xs, ys) in Gs(L) in raster-scan order:
                bestPixelValue = FindBestMatch(Ga, Gs, L, xs, ys)
                Gs(L, xs, ys) = bestPixelValue
        Is = ReconPyramid(Gs)
        return Is
    function FindBestMatch(Ga, Gs, L, xs, ys):
        Ns = BuildNeighborhood(Gs, L, xs, ys)
        bestDist = infinity
        bestValue = null
        for each pixel (xa, ya) in Ga(L):
            Na = BuildNeighborhood(Ga, L, xa, ya)
            dist = L2_Distance(Na, Ns)
            if dist < bestDist:
                bestDist = dist
                bestValue = Ga(L, xa, ya)
        return bestValue
  2. Knowl 2 — Multiresolution Causal Neighborhood Architecture

    model/method

    To represent local texture patterns while enforcing consistency across scales, the neighborhood N(p)N(p) around an output pixel p=(L,x,y)p = (L, x, y) is defined across multiple pyramid levels, denoted by the parameter tuple {R×C,k}\{R \times C, k\}, where R×CR \times C is the spatial bounding box dimension at the current level LL and kk is the total number of pyramid levels included in the neighborhood.

    At the current pyramid level LL, the neighborhood is causal, consisting strictly of an L-shaped region of pixels that precede pp in raster-scan order (i.e., pixels on preceding scanlines and pixels to the left of pp on the current scanline). Causality ensures that the neighborhood contains only already-synthesized pixel values.

    At lower-resolution pyramid levels (L+1,…,L+k−1L+1, \dots, L+k-1), the neighborhood is noncausal and symmetric, centered at the parent coordinates (L+1,⌊x/2⌋,⌊y/2⌋)(L+1, \lfloor x/2 \rfloor, \lfloor y/2 \rfloor). The spatial dimensions of the lower-resolution blocks are halved at each successive coarser level (for instance, a 5×55 \times 5 causal window at level LL combined with a 3×33 \times 3 full window at level L+1L+1). The multiresolution representation allows small spatial windows to capture large-scale structural features while lower-level pixels condition high-frequency detail generation.

  3. Knowl 3 — Nearest-Neighbor Acceleration via Tree-Structured Vector Quantization

    model/method

    Exhaustive neighborhood search has time complexity O(∣S∣)O(|S|) per pixel, where ∣S∣=NL|S| = N_L is the number of pixels in the input exemplar level Ga(L)G_a(L). Tree-Structured Vector Quantization (TSVQ) accelerates synthesis by casting neighborhood matching into an approximate nearest-neighbor query on a hierarchical binary tree codebook T(L)T(L).

    Training Phase: For each input pyramid level Ga(L)G_a(L), all valid neighborhood vectors N(pi)∈RdN(p_i) \in \mathbb{R}^d (where dd is the number of pixels across all neighborhood levels) are collected. A binary tree of codewords is constructed recursively using the Generalized Lloyd Algorithm (GLA), alternating between centroid computation and nearest-centroid data partitioning, until a targeted codebook size or error threshold is reached.

    Query Phase: During synthesis of Gs(L)G_s(L), the query vector N(p)N(p) traverses T(L)T(L) from the root in a best-first search, descending to the child node whose codeword has the smaller Euclidean distance to N(p)N(p) until reaching a leaf node. On a balanced tree, this traversal executes in O(log⁡∣S∣)O(\log |S|) time.

    To prevent over-blurring caused by greedy quantization errors, limited backtracking is permitted to visit multiple candidate leaves. When the number of visited leaves equals the total codebook size, the search becomes exact exhaustive search.

  4. Knowl 4 — Two-Pass Constrained Texture Synthesis with Spiral Traversal

    model/method

    Constrained texture synthesis (such as hole filling, scratch removal, and image extrapolation) requires seamless boundary consistency with surrounding existing texture. A standard causal raster-scan synthesizer introduces severe boundary seams at the right and bottom edges of the target replacement mask. To eliminate these boundary artifacts, synthesis is modified into a two-pass multiresolution procedure using symmetric neighborhoods and an outside-in spiral synthesis ordering:

    1. Pass 1 (Coarse Extrapolation): At each pyramid level LL, a neighborhood consisting solely of pixels from the already-synthesized lower-resolution levels (L+1,…L+1, \dots) is used. Because lower pyramid levels are completely synthesized before higher levels, a fully symmetric spatial window can be used without referencing unassigned pixels.
    2. Pass 2 (Refinement): A symmetric multiresolution neighborhood containing pixels from both the current resolution LL and lower resolutions is used to refine the assigned pixels.
    3. Spiral Traversal: Output pixels inside the masked region are synthesized in an outside-in spiral order, progressing inward layer-by-layer from the known boundary to the interior. This eliminates directional bias.
  5. Knowl 5 — Spatio-Temporal (3D) Texture Synthesis

    model/method

    The deterministic multiresolution synthesis framework extends to multi-dimensional data, notably 3D temporal textures (such as video sequences of fire, smoke, and ocean waves) that exhibit spatial and temporal stationarity and locality.

    The input motion sequence is represented as a 3D volumetric array of size X×Y×TX \times Y \times T. The 2D Gaussian pyramids and neighborhoods are replaced by their 3D equivalents:

    • 3D Gaussian Pyramids: Built by spatio-temporal filtering and downsampling in all three dimensions.
    • 3D Neighborhoods: Parameterized as {R×C×D,k}\{R \times C \times D, k\}, where R×CR \times C denotes the spatial dimensions, DD denotes the temporal depth, and kk is the number of pyramid levels.
    • Synthesis Ordering: Synthesis proceeds coarse-to-fine across pyramid levels. Within each level, the 3D volume is synthesized slice-by-slice along the time domain in raster order.

    To reduce memory overhead during TSVQ codebook training on large 3D neighborhood vectors, training can be performed on a random subset (e.g., 10%) of the total available input neighborhood vectors.

  6. Knowl 6 — Toroidal Boundary Conditions for Seamless Texture Tiling

    model/method

    To guarantee that synthesized textures tile seamlessly without visible edge discontinuities, boundary conditions on the output pyramid GsG_s are evaluated toroidally (periodically). If Gs(L,x,y)G_s(L, x, y) represents the pixel at coordinate (x,y)(x, y) of level LL with dimensions M×NM \times N (MM rows and NN columns), toroidal wrapping is applied via modular arithmetic:

    Gs(L,x,y)≡Gs(L,x mod M,y mod N)G_s(L, x, y) \equiv G_s(L, x \bmod M, y \bmod N)

    For the input sample pyramid GaG_a, toroidal wrapping is not applied if the exemplar is non-periodic, as wrapping would introduce artificial derivative discontinuities. Instead, the input sample neighborhood pool is restricted to interior blocks, discarding candidate neighborhoods that cross the boundary of GaG_a.

  7. Knowl 7 — Noise Initialization and Pyramid Histogram Equalization

    model/method

    To seed the deterministic searching process with entropy and replicate the stochastic nature of natural textures without explicit entropy maximization, the output image IsI_s is initialized with white random noise.

    To provide an initial state matching the marginal statistics of the exemplar, the pyramid histogram of the random noise GsG_s is equalized against the pyramid histogram of the input texture GaG_a. During synthesis, the random noise determines the initial state of the lowest-resolution level of GsG_s and provides pseudo-random variation to the boundary conditions of the first few rows and columns, enabling diverse outputs from different random seeds.

  8. Knowl 8 — Locality and Stationarity Assumptions for MRF Texture Modeling

    assumption

    The deterministic synthesis algorithm relies on two foundational assumptions of Markov Random Field texture models:

    1. Stationarity: A visual pattern is stationary if, under an appropriately sized observation window, the observable portion appears perceptually similar across all spatial positions in the image.
    2. Locality: A visual pattern is local if the color and intensity of each pixel are conditionally predictable given only a small set of spatially neighboring pixels, and conditionally independent of the remainder of the image given that local neighborhood.
  9. Knowl 9 — Empirical Computational Complexity and Runtime Performance

    data/table

    TSVQ acceleration reduces the search time complexity per pixel from linear in the number of exemplar pixels, O(∣S∣)O(|S|), to logarithmic, O(log⁡∣S∣)O(\log |S|). The table below presents execution times for synthesizing a 192×192192 \times 192 output texture from a 64×6464 \times 64 input texture sample on a 195 MHz SGI R10000 processor, comparing the non-parametric MRF sampling approach of Efros & Leung, the unaccelerated exhaustive searching algorithm, and the TSVQ-accelerated algorithm.

    Algorithm Training Time Synthesis Time
    Efros and Leung none 1941 seconds
    Exhaustive Searching none 503 seconds
    TSVQ acceleration 12 seconds 12 seconds

    TSVQ acceleration achieves a two orders of magnitude speedup over prior non-parametric MRF sampling, enabling texture synthesis in seconds.

  10. Knowl 10 — Limitations of TSVQ-Based MRF Texture Synthesis

    limitation

    The synthesis framework exhibits several key limitations:

    1. MRF Model Constraints: Because the algorithm assumes pure locality and stationarity, it cannot synthesize non-stationary visual cues such as perspective distortion, variable surface depth, global lighting gradients, or specular reflections.
    2. Memory Footprint: A full TSVQ tree data structure requires O(d⋅N)O(d \cdot N) memory, where dd is the neighborhood vector dimension and NN is the number of input pixels. This overhead is substantial for 3D spatio-temporal neighborhoods, requiring training vector subsampling.
    3. Quantization Blur: Greedy best-first tree traversal can yield suboptimal leaf matches, causing blurriness in the synthesized output unless tree backtracking is enabled at the cost of additional computation time.

Coverage note — None was omitted. All key contributions—including the deterministic MRF formulation, multiresolution causal neighborhood structure, TSVQ acceleration and backtracking, toroidal tiling conditions, noise initialization, two-pass spiral constrained synthesis, and 3D spatio-temporal synthesis—have been fully extracted.

References

  1. 1.A. C. Beers, M. Agrawala, and N. Chaddha. Rendering from compressed textures. Proceedings of SIGGRAPH 96, pages 373–378, August 1996.
  2. 2.P. Brodatz. Textures: A Photographic Album for Artists and Designers. Dover, New York, 1966.
  3. 3.P. J. Burt and E. H. Adelson. A multiresolution spline with application to image mosaics. ACM Transactions on Graphics, 2(4):217–236, Oct. 1983.
  4. 4.J. S. De Bonet. Multiresolution sampling procedure for analysis and synthesis of texture images. In T. Whitted, editor, SIGGRAPH 97 Conference Proceedings, Annual Conference Series, pages 361–368. ACM SIGGRAPH, Addison Wesley, Aug. 1997.
  5. 5.J. Dorsey, A. Edelman, J. Legakis, H. W. Jensen, and H. K. Pedersen. Modeling and rendering of weathered stone. Proceedings of SIGGRAPH 99, pages 225–234, August 1999.
  6. 6.A. Efros and T. Leung. Texture synthesis by non-parametric sampling. In International Conference on Computer Vision, volume 2, pages 1033–8, Sep 1999.
  7. 7.A. Gersho and R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992.
  8. 8.R. Haralick. Statistical image texture analysis. In Handbook of Pattern Recognition and Image Processing, volume 86, pages 247–279. Academic Press, 1986.
  9. 9.D. J. Heeger and J. R. Bergen. Pyramid-Based texture analysis/synthesis. In R. Cook, editor, SIGGRAPH 95 Conference Proceedings, Annual Conference Series, pages 229–238. ACM SIGGRAPH, Addison Wesley, Aug. 1995.
  10. 10.A. N. Hirani and T. Totsuka. Combining frequency and spatial domain information for fast interactive image noise removal. Computer Graphics, 30(Annual Conference Series):269–276, 1996.
  11. 11.H. Igehy and L. Pereira. Image replacement through texture synthesis. In International Conference on Image Processing, volume 3, pages 186–189, Oct 1997.
  12. 12.H. Iversen and T. Lonnestad. An evaluation of stochastic models for analysis and synthesis of gray scale texture. Pattern Recognition Letters, 15:575–585, 1994.
  13. 13.V. Krishnamurthy and M. Levoy. Fitting smooth surfaces to dense polygon meshes. Proceedings of SIGGRAPH 96, pages 313–324, August 1996. ISBN 0-201-94800-1. Held in New Orleans, Louisiana.
  14. 14.M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S. Anderson, J. Davis, J. Ginsberg, J. Shade, and D. Fulk. The Digital Michelangelo Project: 3D scanning of large statues. To appear in Proceedings of SIGGRAPH 2000.
  15. 15.T. Malzbender and S. Spach. A context sensitive texture nib. In Proceedings of Computer Graphics International, pages 151–163, June 1993.
  16. 16.MIT Media Lab. Vision texture. http://www-white.media.mit.edu/vismod/-imagery/VisionTexture/vistex.html.
  17. 17.S. Nene and S. Nayar. A simple algorithm for nearest neighbor search in high dimensions. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:989–1003, 1997.
  18. 18.R. Paget and I. Longstaff. Texture synthesis via a noncausal nonparametric multiscale Markov random field. IEEE Transactions on Image Processing, 7(6):925–931, June 1998.
  19. 19.A. C. Popat. Conjoint Probabilistic Subband Modeling. PhD thesis, Massachusetts Institute of Technology, 1997.
  20. 20.K. Popat and R. Picard. Novel cluster-based probability model for texture synthesis, classification, and compression. In Visual Communications and Image Processing, pages 756–68, 1993.
  21. 21.M. Segal, C. Korobkin, R. van Widenfelt, J. Foran, and P. E. Haeberli. Fast shadows and lighting effects using texture mapping. Computer Graphics (Proceedings of SIGGRAPH 92), 26(2):249–252, July 1992.
  22. 22.E. Simoncelli and J. Portilla. Texture characterization via joint statistics of wavelet coefficient magnitudes. In Fifth International Conference on Image Processing, volume 1, pages 62–66, Oct. 1998.
  23. 23.J. Stam and E. Fiume. Depicting fire and other gaseous phenomena using diffusion processes. Proceedings of SIGGRAPH 95, pages 129–136, August 1995.
  24. 24.M. Szummer and R. W. Picard. Temporal texture modeling. In International Conference on Image Processing, volume 3, pages 823–6, Sep 1996.
  25. 25.L. Wei. Deterministic texture analysis and synthesis using tree structure vector quantization. In XII Brazilian Symposium on Computer Graphics and Image Processing, pages 207–213, October 1999.
  26. 26.A. Witkin and M. Kass. Reaction-diffusion textures. In T. W. Sederberg, editor, Computer Graphics (SIGGRAPH ’91 Proceedings), volume 25, pages 299–308, July 1991.
  27. 27.S. P. Worley. A cellular texture basis function. In H. Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pages 291–294. ACM SIGGRAPH, Addison Wesley, Aug. 1996.
  28. 28.S. Zhu, Y. Wu, and D. Mumford. Filters, random fields and maximun entropy (FRAME) - towards a unified theory for texture modeling. International Journal of Computer Vision, 27(2):107–126, 1998.

Citation

MLA
Wei, L.-Y., and M. Levoy. “Fast Texture Synthesis Using Tree-structured Vector Quantization”. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '00, 2000, pp. 479–88, https://doi.org/10.1145/344779.345009.
APA
Wei, L.-Y., & Levoy, M. (2000). Fast texture synthesis using tree-structured vector quantization. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '00, 479–488. https://doi.org/10.1145/344779.345009
Chicago
Wei, L.-Y., and M. Levoy. 2000. “Fast Texture Synthesis Using Tree-structured Vector Quantization”. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques - SIGGRAPH '00, 479–88. https://doi.org/10.1145/344779.345009.
Harvard
Wei, L.-Y. and Levoy, M. (2000) “Fast texture synthesis using tree-structured vector quantization”, Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00. ACM Press, pp. 479–488. Available at: https://doi.org/10.1145/344779.345009.
Vancouver
1. Wei L-Y, Levoy M (2000) Fast texture synthesis using tree-structured vector quantization. In: Proceedings of the 27th annual conference on Computer graphics and interactive techniques - SIGGRAPH '00. ACM Press, pp 479–488

BibTeX

@inproceedings{Wei_2000, series={SIGGRAPH ’00}, title={Fast texture synthesis using tree-structured vector quantization}, url={http://dx.doi.org/10.1145/344779.345009}, DOI={10.1145/344779.345009}, booktitle={Proceedings of the 27th annual conference on Computer graphics and interactive techniques  - SIGGRAPH ’00}, publisher={ACM Press}, author={Wei, Li-Yi and Levoy, Marc}, year={2000}, pages={479–488}, collection={SIGGRAPH ’00} }
Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF