The PatchMatch randomized matching algorithm for image manipulation

Abstract

This paper presents a new randomized algorithm for quickly finding approximate nearest neighbor matches between image patches. Our algorithm offers substantial performance improvements over the previous state of the art (20--100×), enabling its use in new interactive image editing tools, computer vision, and video applications. Previously, the cost of computing such matches for an entire image had eluded efforts to provide interactive performance. The key insight driving our algorithm is that the elements of our search domain---patches of image pixels---are correlated, and thus the search strategy takes advantage of these statistics. Our algorithm uses two principles: first, that good patch matches can be found via random sampling, and second, that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. Our simple algorithm allows finding a single nearest neighbor match across translations only, whereas our general algorithm additionally allows matching of k-nearest neighbors, across all rotations and scales, and matching arbitrary descriptors. This one simple algorithm forms the basis for a variety of applications including image retargeting, completion, reshuffling, object detection, digital forgery detection, and video summarization.

References

1. Ashikhmin, M. Synthesizing natural textures. In I3D Proceedings (2001). ACM, 217--226.
2. Avidan, S., Shamir, A. Seam carving for content-aware image resizing. ACM Trans. Gr. (Proc. SIGGRAPH) 26, 3 (2007), 10.
3. Baker, S., Scharstein, D., Lewis, J., Roth, S., Black, M., Szeliski, R. A database and evaluation methodology for optical flow. In Proceedings of ICCV, volume 5, 2007.
4. Barnes, C. PatchMatch: A Fast Randomized Matching Algorithm with Application to Image and Video. Ph.D. thesis. Princeton University, Princeton, NJ. May 2011.
5. Barnes, C., Goldman, D.B., Shechtman, E., Finkelstein, A. Video tapestries with continuous temporal zoom. ACM Trans. Gr. (Proc. SIGGRAPH) 29, 3 (Aug. 2010).
6. Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Gr. (Proc. SIGGRAPH) 28, 3 (2009), 24.
7. Barnes, C., Shechtman, E., Goldman, D.B., Finkelstein, A. The generalized PatchMatch correspondence algorithm. In ECCV, Sept. 2010.
8. Cho, T.S., Butman, M., Avidan, S., Freeman, W. The patch transform and its applications to image editing. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2008.
9. Efros, A.A., Leung, T.K. Texture synthesis by non-parametric sampling. IEEE ICCV 2 (1999), 1033.
10. Hertzmann, A., Jacobs, C.E., Oliver, N., Curless, B., Salesin, D. Image analogies. In ACM Transactions on Graphics (Proc. SIGGRAPH) (2001), 327--340.
11. Jain, A., Zhong, Y., Dubuisson-Jolly, M. Deformable template models: A review. Signal Process. 71, 2 (1998), 109--129.
12. Kumar, N., Zhang, L., Nayar, S.K. What is a good nearest neighbors algorithm for finding similar patches in images? In ECCV (2008), II, 364--378.
13. Liu, C., Freeman, W. A high-quality Video denoising algorithm based on reliable motion estimation. In Proceedings of the ECCV, 2010.
14. Mikolajczyk, K., Schmid, C. A performance evaluation of local descriptors. IEEE Pattern Anal. Mach. Intell. (PAMI) 27, 10 (2005), 1615--1630.
15. Mount, D.M., Arya, S. ANN: A library for approximate nearest neighbor searching. Oct. 28, 1997.
16. Muja, M., Lowe, D. Fast approximate nearest neighbors with automatic algorithm configuration. In International Conference on Computer Vision Theory and Applications (VISAPP), 2009.
17. Popescu, A., Farid, H. Exposing Digital Forgeries by Detecting Duplicated Image Regions. Technical Report. Department of Computer Science, Dartmouth College, 2004.
18. Shapira, L., Avidan, S., Shamir, A. Mode-detection via median-shift. In IEEE Computer Vision and Pattern Recognition (CVPR) (2009), IEEE, 1909--1916.
19. Simakov, D., Caspi, Y., Shechtman, E., Irani, M. Summarizing visual data using bidirectional similarity. In IEEE Computer Vision and Pattern Recognition (CVPR), Anchorage, AK, 2008.
20. Sun, J., Yuan, L., Jia, J., Shum, H.-Y. Image completion with structure propagation. In ACM Transactions on Graphics (Proc. SIGGRAPH) (2005), 861--868.
21. Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., Shum, H.-Y. Synthesis of bidirectional texture functions on arbitrary surfaces. ACM Trans. Gr. (Proc. SIGGRAPH) 21, 3 (July 2002), 665--672.
22. Wei, L.-Y., Han, J., Zhou, K., Bao, H., Guo, B., Shum, H.-Y. Inverse texture synthesis. ACM Trans. Gr. (Proc. SIGGRAPH) 27, 3 (2008).
23. Wei, L.Y., Levoy, M. Fast texture synthesis using tree-structured vector quantization. In ACM Transactions on Graphics (Proc. SIGGRAPH) (2000), 479--488.
24. Wexler, Y., Shechtman, E., Irani, M. Space-time completion of video. IEEE Pattern Anal. Mach. Intell. (PAMI) 29, 3 (2007), 463--476.
25. Wolf, L., Guttmann, M., Cohen-Or, D. Non-homogeneous content-driven video-retargeting. In IEEE ICCV, 2007.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision tasks

  • Computer graphics