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.

REFERENCES

• 1: Andrew C. Beers , Maneesh Agrawala , Navin Chaddha, Rendering from compressed textures, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.373-378, August 1996 [doi>10.1145/237170.237276]
• 2: R Brodatz. Textures: A Photographic Album for Artists and Designers. Dover, New York, 1966.
• 3: Peter J. Burt , Edward H. Adelson, A multiresolution spline with application to image mosaics, ACM Transactions on Graphics (TOG), v.2 n.4, p.217-236, October 1983 [doi>10.1145/245.247]
• 4: Jeremy S. De Bonet, Multiresolution sampling procedure for analysis and synthesis of texture images, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.361-368, August 1997 [doi>10.1145/258734.258882]
• 5: Julie Dorsey , Alan Edelman , Henrik Wann Jensen , Justin Legakis , Hans Køhling Pedersen, Modeling and rendering of weathered stone, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.225-234, July 1999 [doi>10.1145/311535.311560]
• 6: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 7: Allen Gersho , Robert M. Gray, Vector quantization and signal compression, Kluwer Academic Publishers, Norwell, MA, 1991
• 8: R. Haralick. Statistical image texture analysis. In Handbook of Pattern Recognition and image Processing, volume 86, pages 247-279. Academic Press, 1986.
• 9: David J. Heeger , James R. Bergen, Pyramid-based texture analysis/synthesis, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.229-238, September 1995 [doi>10.1145/218380.218446]
• 10: Anil N. Hirani , Takashi Totsuka, Combining frequency and spatial domain information for fast interactive image noise removal, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.269-276, August 1996 [doi>10.1145/237170.237264]
• 11: H. Igehy , L. Pereira, Image replacement through texture synthesis, Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 3, p.186, October 26-29, 1997
• 12: Håvard Iversen , Tor Lønnestad, An evaluation of stochastic models for analysis and synthesis of gray-scale texture, Pattern Recognition Letters, v.15 n.6, p.575-585, June 1994 [doi>10.1016/0167-8655(94)90018-3]
• 13: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• 14: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 15: T. Malzbender and S. Spach. A context sensitive texture nib. In Proceedings of Computer Graphics international, pages 151-163, June 1993.
• 16: MIT Media Lab. Vision texture, http://www-white.media.mit.edu/vismod/- imagery/VisionTexture/vistex.html.
• 17: Sameer A. Nene , Shree K. Nayar, A Simple Algorithm for Nearest Neighbor Search in High Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.9, p.989-1003, September 1997 [doi>10.1109/34.615448]
• 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: Ashok Chhabedia Popat , Rosalind W. Picard, Conjoint probabilistic subband modeling, 1997
• 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: Mark Segal , Carl Korobkin , Rolf van Widenfelt , Jim Foran , Paul Haeberli, Fast shadows and lighting effects using texture mapping, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.249-252, July 1992
• 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: Jos Stam , Eugene Fiume, Depicting fire and other gaseous phenomena using diffusion processes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.129-136, September 1995 [doi>10.1145/218380.218430]
• 24: M. Szummer and R. W. Picard. Temporal texture modeling. In international Conference on image Processing, volume 3, pages 823-6, Sep 1996.
• 25: Li-Yi Wei, Deterministic Texture Analysis and Synthesis Using Tree Structure Vector Quantization, Proceedings of the XII Brazilian Symposium on Computer Graphics and Image Processing, p.207-214, October 17-20, 1999
• 26: Andrew Witkin , Michael Kass, Reaction-diffusion textures, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.299-308, July 1991
• 27: Steven Worley, A cellular texture basis function, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.291-294, August 1996 [doi>10.1145/237170.237267]
• 28: Song Chun Zhu , Yingnian Wu , David Mumford, Filters, Random Fields and Maximum Entropy (FRAME): Towards a Unified Theory for Texture Modeling, International Journal of Computer Vision, v.27 n.2, p.107-126, Mar 1998 [doi>10.1023/A:1007925832420]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Texture

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement
          Subjects: Texture

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
compression algorithms, image processing, texture synthesis