“Graphcut textures: image and video synthesis using graph cuts” by Bobick, Kwatra, Schödl, Essa and Turk

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.

1. ASHIKHMIN, M. 2001. Synthesizing natural textures. 2001 ACM Symposium on Interactive 3D Graphics (March), 217–226. ISBN 1-58113-292-1. Google Scholar
2. BAR-JOSEPH, Z., EL-YANIV, R., LISCHINSKI, D., AND WERMAN, M. 2001. Texture mixing and texture movie synthesis using statistical learning. IEEE Transactions on Visualization and Computer Graphics 7, 2, 120–135. Google ScholarDigital Library
3. BOYKOV, Y., VEKSLER, O., AND ZABIH, R. 1999. Fast approximate energy minimization via graph cuts. In International Conference on Computer Vision, 377–384.Google Scholar
4. BROOKS, S., AND DODGSON, N. A. 2002. Self-similarity based texture editing. ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH 2002) 21, 3 (July), 653–656. Google Scholar
5. BURT, P. J., AND ADELSON, E. H. 1983. A multiresolution spline with application to image mosaics. ACM Transactions on Graphics 2, 4, 217–236. Google ScholarDigital Library
6. CROW, F. C. 1984. Summed-area tables for texture mapping. In Proceedings of the 11th annual conference on Computer graphics and interactive techniques, 207–212. ISBN 0-89791-138-5. Google Scholar
7. DEBONET, J. S. 1997. Multiresolution sampling procedure for analysis and synthesis of texture images. Proceedings of SIGGRAPH 97 (August), 361–368. ISBN 0-89791-896-7. Held in Los Angeles, California. Google Scholar
8. EFROS, A. A., AND FREEMAN, W. T. 2001. Image quilting for texture synthesis and transfer. Proceedings of SIGGRAPH 2001 (August), 341–346. ISBN 1-58113-292-1. Google Scholar
9. EFROS, A., AND LEUNG, T. 1999. Texture synthesis by non-parametric sampling. In International Conference on Computer Vision, 1033–1038. Google Scholar
10. FORD, L., AND FULKERSON, D. 1962. Flows in Networks. Princeton University Press.Google Scholar
11. GREIG, D., PORTEOUS, B., AND SEHEULT, A. 1989. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statistical Society Series B, 51, 271–279.Google ScholarCross Ref
12. GUO, B., SHUM, H., AND XU, Y.-Q. 2000. Chaos mosaic: Fast and memory efficient texture synthesis. Tech. Rep. MSR-TR-2000-32, Microsoft Research.Google Scholar
13. HEEGER, D. J., AND BERGEN, J. R. 1995. Pyramid-based texture analysis/synthesis. Proceedings of SIGGRAPH 95 (August), 229–238. ISBN 0-201-84776-0. Held in Los Angeles, California. Google Scholar
14. KILTHAU, S. L., DREW, M., AND MOLLER, T. 2002. Full search content independent block matching based on the fast fourier transform. In ICIP02, I: 669–672.Google Scholar
15. LI, S. Z. 1995. Markov Random Field Modeling in Computer Vision. Springer-Verlag. Google Scholar
16. LIANG, L., LIU, C., XU, Y.-Q., GUO, B., AND SHUM, H.-Y. 2001. Real-time texture synthesis by patch-based sampling. ACM Transactions on Graphics Vol. 20, No. 3 (July), 127–150. Google ScholarDigital Library
17. MORTENSEN, E. N., AND BARRETT, W. A. 1995. Intelligent scissors for image composition. Proceedings of SIGGRAPH 1995 (Aug.), 191–198. Google Scholar
18. PORTILLA, J., AND SIMONCELLI, E. P. 2000. A parametric texture model based on joint statistics of complex wavelet coefficients. International Journal of Computer Vision 40, 1 (October), 49–70. Google ScholarDigital Library
19. SAISAN, P., DORETTO, G., WU, Y., AND SOATTO, S. 2001. Dynamic texture recognition. In Proceeding of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), II:58–63.Google Scholar
20. SCHÖDL, A., SZELISKI, R., SALESIN, D. H., AND ESSA, I. 2000. Video textures. Proceedings of SIGGRAPH 2000 (July), 489–498. ISBN 1-58113-208-5.Google ScholarDigital Library
21. SEDGEWICK, R. 2001. Algorithms in C, Part 5: Graph Algorithms. Addison-Wesley, Reading, Massachusetts. Google Scholar
22. SOATTO, S., DORETTO, G., AND WU, Y. 2001. Dynamic textures. In Proceeding of IEEE International Conference on Computer Vision 2001, II: 439–446.Google ScholarCross Ref
23. SOLER, C., CANI, M.-P., AND ANGELIDIS, A. 2002. Hierarchical pattern mapping. ACM Transactions on Graphics 21, 3 (July), 673–680. Google ScholarDigital Library
24. SZUMMER, M., AND PICARD, R. 1996. Temporal texture modeling. In Proceeding of IEEE International Conference on Image Processing 1996, vol. 3, 823–826.Google ScholarCross Ref
25. WANG, Y., AND ZHU, S. 2002. A generative method for textured motion: Analysis and synthesis. In European Conference on Computer Vision. Google Scholar
26. WEI, L.-Y., AND LEVOY, M. 2000. Fast texture synthesis using tree-structured vector quantization. Proceedings of SIGGRAPH 2000 (July), 479–488. ISBN 1-58113-208-5. Google ScholarDigital Library