Texture Synthesis and Asymptotical Admissibility
Suppose the green ellipse represents the Julesz 
ensemble of a texture in the image universe 
(each point is an image in a n x n dimensional  
space). The two blue regions are ensembles of two
synthesis algorithms respectively. A2 is admissible
 while A1 is not.
Click here for interesting results on texture synthesis

The objective of texture synthesis is to render texture images which are perceptually similar to the observed texture examples. This can be done by sampling a texture model, or sampling the Julesz ensemble without modeling explicitly. In fact, the task of texure synthesis is much simpler than texture analysis, and the latter demands an accurate estimation of the texture model. We analyzed the texture synthesis task by defining two measurements: admissibilty and effectiveness in a recent paper[1], under the two criteria, various algorithms can be compared[1].

Given a texture synthesis algorithm A, it is explicitly or implicitly sampling a texture ensemble $\Omega_{A}$. As long as this ensemble is a subset of the true Julesz ensemble, then we say algorithm admissible, and any instances will be similar to the observed images. The effectiveness of algorithm A is measured by the log-ratio between the volume of this ensemble and the volume of the Julesz ensemble. Thus the effectiveness reflects the richness and variety of synthesized texture instances. Most of existing algorithms are only asymptotically admissible: it is admissible as the observed image goes to infinite[1]. To achieve a certain admissibility, a good algorithm may requires smaller observations.

Click here to see some fast pasting results in texture synthesis in [1][2], this is the best result so far! It can be computed in the speed of 1 second.

Reference

[1] Y. Q. Xu, S. C. Zhu, B. N. Guo, and H. Y. Shum, "Asymptotically Admissible Texture Synthesis",
Proc. of 2nd Int'l Workshop on Statistical and Computational Theories of Vision, Vancouver, Canada, July, 2001.

[2] Y. Q. Xu, B. N. Guo, and H.Y. Shum, "Chaos Mosaic: Fast and Memory Efficient Texture Synthesis", MSR TR-2000-32, April, 2000.