PatchMatch: a randomized correspondence algorithm for structural image editing

ABSTRACT

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.

REFERENCES

• 1: Michael Ashikhmin, Synthesizing natural textures, Proceedings of the 2001 symposium on Interactive 3D graphics, p.217-226, March 2001 [doi>10.1145/364338.364405]
• 2: Shai Avidan , Ariel Shamir, Seam carving for content-aware image resizing, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 3: Antoni Buades , Bartomeu Coll , Jean-Michel Morel, A Non-Local Algorithm for Image Denoising, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.60-65, June 20-26, 2005 [doi>10.1109/CVPR.2005.38]
• 4: Cho, T. S., Butman, M., Avidan, S., and Freeman, W. 2008. The patch transform and its applications to image editing. CVPR.
• 5: Criminisi, A., Pérez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 2, 721.
• 6: Iddo Drori , Daniel Cohen-Or , Hezy Yeshurun, Fragment-based image completion, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 7: Alexei A. Efros , William T. Freeman, Image quilting for texture synthesis and transfer, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.341-346, August 2001 [doi>10.1145/383259.383296]
• 8: Alexei A. Efros , Thomas K. Leung, Texture Synthesis by Non-Parametric Sampling, Proceedings of the International Conference on Computer Vision-Volume 2, p.1033, September 20-25, 1999
• 9: Hui Fang , John C. Hart, Detail preserving shape deformation in image editing, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 10: Martin A. Fischler , Robert C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Communications of the ACM, v.24 n.6, p.381-395, June 1981 [doi>10.1145/358669.358692]
• 11: Andrew Fitzgibbon , Yonatan Wexler , Andrew Zisserman, Image-based rendering using image-based priors, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.1176, October 13-16, 2003
• 12: William T. Freeman , Thouis R. Jones , Egon C Pasztor, Example-Based Super-Resolution, IEEE Computer Graphics and Applications, v.22 n.2, p.56-65, March 2002 [doi>10.1109/38.988747]
• 13: Aaron Hertzmann , Charles E. Jacobs , Nuria Oliver , Brian Curless , David H. Salesin, Image analogies, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.327-340, August 2001 [doi>10.1145/383259.383295]
• 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.
• 15: Johannes Kopf , Chi-Wing Fu , Daniel Cohen-Or , Oliver Deussen , Dani Lischinski , Tien-Tsin Wong, Solid texture synthesis from 2D exemplars, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 16: Neeraj Kumar , Li Zhang , Shree Nayar, What Is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?, Proceedings of the 10th European Conference on Computer Vision: Part II, October 12-18, 2008, Marseille, France [doi>10.1007/978-3-540-88688-4_27]
• 17: Vivek Kwatra , Arno Schödl , Irfan Essa , Greg Turk , Aaron Bobick, Graphcut textures: image and video synthesis using graph cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 18: Vivek Kwatra , Irfan Essa , Aaron Bobick , Nipun Kwatra, Texture optimization for example-based synthesis, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 19: Sylvain Lefebvre , Hugues Hoppe, Parallel controllable texture synthesis, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 20: Lin Liang , Ce Liu , Ying-Qing Xu , Baining Guo , Heung-Yeung Shum, Real-time texture synthesis by patch-based sampling, ACM Transactions on Graphics (TOG), v.20 n.3, p.127-150, July 2001 [doi>10.1145/501786.501787]
• 21: Feng Liu , Michael Gleicher, Automatic image retargeting with fisheye-view warping, Proceedings of the 18th annual ACM symposium on User interface software and technology, October 23-26, 2005, Seattle, WA, USA [doi>10.1145/1095034.1095061]
• 22: Mount, D. M., and Arya, S., 1997. ANN: A library for approximate nearest neighbor searching, Oct. 28.
• 23: Darko Pavić , Volker Schönefeld , Leif Kobbelt, Interactive image completion with perspective correction, The Visual Computer: International Journal of Computer Graphics, v.22 n.9, p.671-681, September 2006 [doi>10.1007/s00371-006-0050-2]
• 24: Guodong Rong , Tiow-Seng Tan, Jump flooding in GPU with applications to Voronoi diagram and distance transform, Proceedings of the 2006 symposium on Interactive 3D graphics and games, March 14-17, 2006, Redwood City, California [doi>10.1145/1111411.1111431]
• 25: Carsten Rother , Lucas Bordeaux , Youssef Hamadi , Andrew Blake, AutoCollage, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 26: Michael Rubinstein , Ariel Shamir , Shai Avidan, Improved seam carving for video retargeting, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 27: Vidya Setlur , Saeko Takagi , Ramesh Raskar , Michael Gleicher , Bruce Gooch, Automatic image retargeting, Proceedings of the 4th international conference on Mobile and ubiquitous multimedia, December 08-10, 2005, Christchurch, New Zealand [doi>10.1145/1149488.1149499]
• 28: Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In CVPR.
• 29: Jian Sun , Lu Yuan , Jiaya Jia , Heung-Yeung Shum, Image completion with structure propagation, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 30: Richard Szeliski , Ramin Zabih , Daniel Scharstein , Olga Veksler , Vladimir Kolmogorov , Aseem Agarwala , Marshall Tappen , Carsten Rother, A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.30 n.6, p.1068-1080, June 2008 [doi>10.1109/TPAMI.2007.70844]
• 31: Xin Tong , Jingdan Zhang , Ligang Liu , Xi Wang , Baining Guo , Heung-Yeung Shum, Synthesis of bidirectional texture functions on arbitrary surfaces, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 32: Yu-Shuen Wang , Chiew-Lan Tai , Olga Sorkine , Tong-Yee Lee, Optimized scale-and-stretch for image resizing, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore
• 33: Li-Yi Wei , Marc Levoy, Fast texture synthesis using tree-structured vector quantization, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.479-488, July 2000 [doi>10.1145/344779.345009]
• 34: Li-Yi Wei , Jianwei Han , Kun Zhou , Hujun Bao , Baining Guo , Heung-Yeung Shum, Inverse texture synthesis, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 35: Yonatan Wexler , Eli Shechtman , Michal Irani, Space-Time Completion of Video, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.3, p.463-476, March 2007 [doi>10.1109/TPAMI.2007.60]
• 36: Wolf, L., Guttmann, M., and Cohen-Or, D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.9 Applications

Keywords:
approximate nearest neighbor, completion, image editing, patch-based synthesis, reshuffling, retargeting