In this paper we introduce a new algorithm for image and video texture synthesis. In our approach, patch regions from a sample image or video are transformed and copied to the output and then stitched together along optimal seams to generate a new (and typically larger) output. In contrast to other techniques, the size of the patch is not chosen a-priori, but instead a graph cut technique is used to determine the optimal patch region for any given offset between the input and output texture. Unlike dynamic programming, our graph cut technique for seam optimization is applicable in any dimension. We specifically explore it in 2D and 3D to perform video texture synthesis in addition to regular image synthesis. We present approximative offset search techniques that work well in conjunction with the presented patch size optimization. We show results for synthesizing regular, random, and natural images and videos. We also demonstrate how this method can be used to interactively merge different images to generate new scenes.

Acknowledgements (from the paper):

We would like to thank Professor Ramin Zabih and his students at Cornell University for sharing their code for computing graph min-cut. Thanks also to the authors of  Image Quilting (Alyosha Efros and Bill Freeman), Li-Yi Wei and Marc Levoy, and Ziv BarJoseph et al. for sharing their raw footage and results via their respective web sites to facilitate direct comparisons. Thanks also to Rupert Paget for maintaining an excellent web page on texture research and datasets, and to Martin Szummer for the MIT temporal texture database. Thanks also to the following for contributing their images or videos: East West Photo, Jens Grabenstein, Olga Zhaxybayeva, Adam Brostow, Brad Powell, Erskine Wood, Tim Seaver and Artbeats Inc.. Finally, we would like to thank our collaborators Gabriel Brostow, James Hays, Richard Szeliski and Stephanie Wojtkowski for their insightful suggestions and help with the production of this work. Arno Schö dl is now at think-cell Software GmbH in Berlin, Germany.

This work was funded in part by grants from NSF (IIS-9984847, ANI-0113933 and CCR-0204355) and DARPA (F49620-001-0376), and funds from Microsoft Research.