“PatchMatch: a randomized correspondence algorithm for structural image editing” by Barnes, Shechtman, Finkelstein and Goldman

This paper presents interactive image editing tools using a new randomized algorithm for quickly finding approximate nearest-neighbor matches between image patches. Previous research in graphics and vision has leveraged such nearest-neighbor searches to provide a variety of high-level digital image editing tools. However, the cost of computing a field of such matches for an entire image has eluded previous efforts to provide interactive performance. Our algorithm offers substantial performance improvements over the previous state of the art (20-100x), enabling its use in interactive editing tools. The key insights driving the algorithm are that some good patch matches can be found via random sampling, and that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. We offer theoretical analysis of the convergence properties of the algorithm, as well as empirical and practical evidence for its high quality and performance. This one simple algorithm forms the basis for a variety of tools — image retargeting, completion and reshuffling — that can be used together in the context of a high-level image editing application. Finally, we propose additional intuitive constraints on the synthesis process that offer the user a level of control unavailable in previous methods.

1. Ashikhmin, M. 2001. Synthesizing natural textures. In I3D ’06 Proc., ACM, 217–226. Google ScholarDigital Library
2. Avidan, S., and Shamir, A. 2007. Seam carving for content-aware image resizing. ACM SIGGRAPH 26, 3, 10. Google ScholarDigital Library
3. Buades, A., Coll, B., and Morel, J. M. 2005. A non-local algorithm for image denoising. In CVPR, vol. 2, 60–65. Google ScholarDigital Library
4. Cho, T. S., Butman, M., Avidan, S., and Freeman, W. 2008. The patch transform and its applications to image editing. CVPR.Google Scholar
5. Criminisi, A., Pérez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 2, 721.Google Scholar
6. Drori, I., Cohen-Or, D., and Yeshurun, H. 2003. Fragment-based image completion. ACM SIGGRAPH 22, 303–312. Google ScholarDigital Library
7. Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In ACM SIGGRAPH, ACM, 341–346. Google ScholarDigital Library
8. Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. ICCV 2, 1033. Google ScholarDigital Library
9. Fang, H., and Hart, J. C. 2007. Detail preserving shape deformation in image editing. ACM Trans. Graphics 26, 3, 12. Google ScholarDigital Library
10. Fischler, M. A., and Bolles, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6, 381–395. Google ScholarDigital Library
11. Fitzgibbon, A., Wexler, Y., and Zisserman, A. 2003. Image-based rendering using image-based priors. In ICCV, 1176. Google ScholarDigital Library
12. Freeman, W., Jones, T., and Pasztor, E. 2002. Example-based super-resolution. Computer Graphics and Applications, IEEE 22, 2, 56–65. Google ScholarDigital Library
13. Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. 2001. Image analogies. In ACM SIGGRAPH, 327–340. Google ScholarDigital Library
14. Komodakis, N., and Tziritas, G. 2007. Image completion using efficient belief propagation via priority scheduling and dynamic pruning. IEEE Transactions on Image Processing 16, 11, 2649–2661. Google ScholarDigital Library
15. Kopf, J., Fu, C.-W., Cohen-Or, D., Deussen, O., Lischinski, D., and Wong, T.-T. 2007. Solid texture synthesis from 2d exemplars. ACM SIGGRAPH 26, 3, 2:1–2:9. Google ScholarDigital Library
16. Kumar, N., Zhang, L., and Nayar, S. K. 2008. What is a good nearest neighbors algorithm for finding similar patches in images? In European Conference on Computer Vision (ECCV), II: 364–378. Google ScholarDigital Library
17. Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM SIGGRAPH 22, 3 (July), 277–286. Google ScholarDigital Library
18. Kwatra, V., Essa, I., Bobick, A., and Kwatra, N. 2005. Texture optimization for example-based synthesis. ACM SIGGRAPH 24. Google ScholarDigital Library
19. Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM SIGGRAPH 24, 3, 777–786. Google ScholarDigital Library
20. Liang, L., Liu, C., Xu, Y.-Q., Guo, B., and Shum, H.-Y. 2001. Real-time texture synthesis by patch-based sampling. ACM Trans. Graphics 20, 3, 127–150. Google ScholarDigital Library
21. Liu, F., and Gleicher, M. 2005. Automatic image retargeting with fisheye-view warping. In UIST, ACM, 153–162. Google ScholarDigital Library
22. Mount, D. M., and Arya, S., 1997. ANN: A library for approximate nearest neighbor searching, Oct. 28.Google Scholar
23. Pavic, D., Schonefeld, V., and Kobbelt, L. 2006. Interactive image completion with perspective correction. The Visual Computer 22 (September), 671–681(11). Google ScholarDigital Library
24. Rong, G., and Tan, T.-S. 2006. Jump flooding in GPU with applications to Voronoi diagram and distance transform. In I3D ’06 Proc., 109–116. Google ScholarDigital Library
25. Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. ACM SIGGRAPH 25, 3, 847–852. Google ScholarDigital Library
26. Rubinstein, M., Shamir, A., and Avidan, S. 2008. Improved seam carving for video retargeting. ACM SIGGRAPH 27, 3. Google ScholarDigital Library
27. Setlur, V., Takagi, S., Raskar, R., Gleicher, M., and Gooch, B. 2005. Automatic image retargeting. In MUM, ACM, M. Billinghurst, Ed., vol. 154 of ACM International Conference Proc. Series, 59–68. Google ScholarDigital Library
28. Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In CVPR.Google Scholar
29. Sun, J., Yuan, L., Jia, J., and Shum, H.-Y. 2005. Image completion with structure propagation. In ACM SIGGRAPH, 861–868. Google ScholarDigital Library
30. Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., and Rother, C. 2008. A comparative study of energy minimization methods for markov random fields with smoothness-based priors. IEEE PAMI 30, 6, 1068–1080. Google ScholarDigital Library
31. Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., and Shum, H.-Y. 2002. Synthesis of bidirectional texture functions on arbitrary surfaces. ACM SIGGRAPH 21, 3 (July), 665–672. Google ScholarDigital Library
32. Wang, Y.-S., Tai, C.-L., Sorkine, O., and Lee, T.-Y. 2008. Optimized scale-and-stretch for image resizing. In ACM SIGGRAPH Asia, ACM, New York, NY, USA, 1–8. Google ScholarDigital Library
33. Wei, L. Y., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In ACM SIGGRAPH, 479–488. Google ScholarDigital Library
34. Wei, L.-Y., Han, J., Zhou, K., Bao, H., Guo, B., and Shum, H.-Y. 2008. Inverse texture synthesis. ACM SIGGRAPH 27, 3. Google ScholarDigital Library
35. Wexler, Y., Shechtman, E., and Irani, M. 2007. Space-time completion of video. IEEE Trans. PAMI 29, 3 (March), 463–476. Google ScholarDigital Library
36. Wolf, L., Guttmann, M., and Cohen-Or, D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV.Google Scholar