“Fast texture synthesis using tree-structured vector quantization” by Wei and Levoy

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.

1. A. C. Beers, M. Agrawala, and N. Chaddha. Rendering from compressed textures. Proceedings of SIGGRAPH 96, pages 373-378, August 1996.
2. R Brodatz. Textures: A Photographic Album for Artists and Designers. Dover, New York, 1966.
3. R J. Burt and E. H. Adelson. A multiresolution spline with application to image mosaics. A CM Transactions on Graphics, 2(4):217-236, Oct. 1983.
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. 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. 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. A. Gersho and R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic Publishers, 1992.
8. R. Haralick. Statistical image texture analysis. In Handbook of Pattern Recognition and image Processing, volume 86, pages 247-279. Academic Press, 1986.
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. 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. H. Igehy and L. Pereira. Image replacement through texture synthesis. In international Conference on image Processing, volume 3, pages 186-189, Oct 1997.
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. 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. 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. 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. 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. 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. A. C. Popat. Conjoint Probabilistic Subband Modeling. Phi) thesis, Massachusetts Institute of Technology, 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. M. Segal, C. Korobkin, R. van Widenfelt, J. Foran, and R E. Haeberli. Fast shadows and lighting effects using texture mapping. Computer Graphics (Proceedings of SIGGRAPH 92), 26(2):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. J. Stam and E. Fiume. Depicting fire and other gaseous phenomena using diffusion processes. Proceedings of SIGGRAPH 95, pages 129-136, August 1995.
24. M. Szummer and R. W. Picard. Temporal texture modeling. In international Conference on image Processing, volume 3, pages 823-6, Sep 1996.
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. 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. S. R Worley. A cellular texture basis function. In H. Rushmeier, editor, SIG- GRAPH 96 Conference Proceedings, Annual Conference Series, pages 291-294. ACM SIGGRAPH, Addison Wesley, Aug. 1996.
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.