Graphcut textures: image and video synthesis using graph cuts

ABSTRACT

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.

References

1. ASHIKHMIN, M. 2001. Synthesizing natural textures. 2001 ACM Symposium on Interactive 3D Graphics (March), 217--226. ISBN 1-58113-292-1.
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.
3. BOYKOV, Y., VEKSLER, O., AND ZABIH, R. 1999. Fast approximate energy minimization via graph cuts. In International Conference on Computer Vision, 377--384.
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.
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.
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.
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.
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.
9. EFROS, A., AND LEUNG, T. 1999. Texture synthesis by non-parametric sampling. In International Conference on Computer Vision, 1033--1038.
10. FORD, L., AND FULKERSON, D. 1962. Flows in Networks. Princeton University Press.
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.
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.
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.
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.
15. LI, S. Z. 1995. Markov Random Field Modeling in Computer Vision. Springer-Verlag.
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.
17. MORTENSEN, E. N., AND BARRETT, W. A. 1995. Intelligent scissors for image composition. Proceedings of SIGGRAPH 1995 (Aug.), 191--198.
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.
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.
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.
21. SEDGEWICK, R. 2001. Algorithms in C, Part 5: Graph Algorithms. Addison-Wesley, Reading, Massachusetts.
22. SOATTO, S., DORETTO, G., AND WU, Y. 2001. Dynamic textures. In Proceeding of IEEE International Conference on Computer Vision 2001, II: 439--446.
23. SOLER, C., CANI, M.-P., AND ANGELIDIS, A. 2002. Hierarchical pattern mapping. ACM Transactions on Graphics 21, 3 (July), 673--680.
24. SZUMMER, M., AND PICARD, R. 1996. Temporal texture modeling. In Proceeding of IEEE International Conference on Image Processing 1996, vol. 3, 823--826.
25. WANG, Y., AND ZHU, S. 2002. A generative method for textured motion: Analysis and synthesis. In European Conference on Computer Vision.
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.