Exemplar-Based Texture Synthesis: the Efros-Leung Algorithm

Exemplar-based texture synthesis aims at creating, from an input sample, new texture images that are visually similar to the input, but are not plain copy of it. The Efros-Leung algorithm is one of the most celebrated approaches to this problem. It relies on a Markov assumption and generates new textures in a non-parametric way, directly sampling new values from the input sample. In this paper, we provide a detailed analysis and implementation of this algorithm. The code closely follows the algorithm description from the original paper. It also includes a PCA-based acceleration of the method, yielding results that are generally visually indistinguishable from the original results. To the best of our knowledge, this is the first publicly available implementation of this algorithm running in acceptable time. Even though numerous improvements have been proposed since this seminal work, we believe it is of interest to provide an easy way to test the initial approach from Efros and Leung. In particular, we provide the user with a graphical illustration of the innovation capacity of the algorithm. Experimentation often shows that the path between verbatim copy of the exemplar and garbage growing is somewhat narrow, and that in most favorable cases the algorithm produces new texture images by stitching together entire regions from the exemplar.