Real-time texture synthesis by patch-based sampling

ABSTRACT

We present an algorithm for synthesizing textures from an input sample. This patch-based sampling algorithm is fast and it makes high-quality texture synthesis a real-time process. For generating textures of the same size and comparable quality, patch-based sampling is orders of magnitude faster than existing algorithms. The patch-based sampling algorithm works well for a wide variety of textures ranging from regular to stochastic. By sampling patches according to a nonparametric estimation of the local conditional MRF density function, we avoid mismatching features across patch boundaries. We also experimented with documented cases for which pixel-based nonparametric sampling algorithms cease to be effective but our algorithm continues to work well.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
	2	Michael Ashikhmin, Synthesizing natural textures, Proceedings of the 2001 symposium on Interactive 3D graphics, p.217-226, March 2001 [doi>10.1145/364338.364405]
	3	Ziv Bar-Joseph , Ran El-Yaniv , Dani Lischinski , Michael Werman, Texture Mixing and Texture Movie Synthesis Using Statistical Learning, IEEE Transactions on Visualization and Computer Graphics, v.7 n.2, p.120-135, April 2001 [doi>10.1109/2945.928165]
	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	Alexei A. Efros , William T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.341-346, August 2001 [doi>10.1145/383259.383296]
	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	Alain Fournier , Don Fussell , Loren Carpenter, Computer rendering of stochastic models, Communications of the ACM, v.25 n.6, p.371-384, June 1982 [doi>10.1145/358523.358553]
	8	Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
	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	Aaron Hertzmann , Charles E. Jacobs , Nuria Oliver , Brian Curless , David H. Salesin, Image analogies, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.327-340, August 2001 [doi>10.1145/383259.383295]
	11	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]
	12	JOLLIFE, I. T. 1986. Principal Component Analysis. Springer-Verlag, New York.
	13	John-Peter Lewis, Texture synthesis for digital painting, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.245-252, January 1984
	14	LIANG, L., LIU, C., XU,Y.Q.,GUO,B.,AND SHUM, H. Y. 2001. Real-time texture synthesis by patchbased sampling. Microsoft Research Tech. Rep. MSR-TR-2001-40, March.
	15	MOUNT, D. M. 1998. ANN Programming Manual. Department of Computer Science, University of Maryland, College Park, Maryland.
	16	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]
	17	Ken Perlin, An image synthesizer, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.287-296, Jul. 1985
	18	POPAT,K.AND PICARD, R. W. 1993. Novel cluster-based probability model for texture synthesis, classification, and compression. In Proceedings of SPIE Visual Communication and Image Processing, 756-768.
	19	PORTILLA,J.AND SIMONCELLI, E. 1999. Texture modeling and synthesis using joint statistics of complex wavelet coefficients. In Proceedings of the IEEE Workshop on Statistical and Computational Theories of Vision.
	20	Emil Praun , Adam Finkelstein , Hugues Hoppe, Lapped textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.465-470, July 2000 [doi>10.1145/344779.344987]
	21	Richard Szeliski , Heung-Yeung Shum, Creating full view panoramic image mosaics and environment maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.251-258, August 1997 [doi>10.1145/258734.258861]
	22	Greg Turk, Generating textures on arbitrary surfaces using reaction-diffusion, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.289-298, July 1991
	23	Greg Turk, Texture synthesis on surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.347-354, August 2001 [doi>10.1145/383259.383297]
	24	Li-Yi Wei , Marc Levoy, Texture synthesis over arbitrary manifold surfaces, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.355-360, August 2001 [doi>10.1145/383259.383298]
	25	Li-Yi Wei , Marc Levoy, Fast texture synthesis using tree-structured vector quantization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.479-488, July 2000 [doi>10.1145/344779.345009]
	26	Andrew Witkin , Michael Kass, Reaction-diffusion textures, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, 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	Ying Nian Wu , Song Chun Zhu , Xiuwen Liu, Equivalence of Julesz Ensembles and FRAME Models, International Journal of Computer Vision, v.38 n.3, p.247-265, July-August 2000 [doi>10.1023/A:1008199424771]
	29	XU, Y. Q., GUO,B.,AND SHUM, H. Y. 2000. Chaos mosaic: Fast and memory efficient texture synthesis. Microsoft Res. Tech. Rep. MSR-TR-2000-32, April.
	30	Lexing Ying , Aaron Hertzmann , Henning Biermann , Denis Zorin, Texture and Shape Synthesis on Surfaces, Proceedings of the 12th Eurographics Workshop on Rendering Techniques, p.301-312, June 25-27, 2001
	31	Song Chun Zhu , Xiu Wen Liu , Ying Nian Wu, Exploring Texture Ensembles by Efficient Markov Chain Monte Carlo-Toward a 'Trichromacy' Theory of Texture, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.554-569, June 2000 [doi>10.1109/34.862195]
	32	Song Chun Zhu , Ying Nian Wu , David Mumford, Minimax entropy principle and its application to texture modeling, Neural Computation, v.9 n.9, p.1627-1660, Nov. 15, 1997 [doi>10.1162/neco.1997.9.8.1627]
	33	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]
	34	ZUCKER,S.AND TERZOPOULOS, D. 1980. Finding structure in co-occurence matrices for texture analysis. Comput. Graph. Image Process. 12, 286-307.