PatchMatch

Connelly Barnes

Princeton University

Eli Shechtman

Adobe Research

Adam Finkelstein

Princeton University

Dan Goldman

Adobe Research

patchmatch_title

We have developed 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.

PatchMatch was later generalized and shown to be useful for a variety of computer vision applications like image denoising, object detection, label transfer and more.The patch synthesis capabilities shown here were later enhanced in the Image Melding project. Some of our later citations using PatchMatch as a building block can be found below.

PatchMatch is part of the Content Aware Fill feature in Photoshop CS5, the Content Aware Patch and Move tools in Photoshop CS6 (with further improvements in later versions). It was also used as a core algorithm in the Video Tapestries, Cosaliency, Regenerative Morphing and Non-Rigid Dense Correspondence research projects.

This content requires Flash To view this content, JavaScript must be enabled, and you need the latest version of the Adobe Flash Player. To view this content, JavaScript must be enabled, and you need the latest version of the Adobe Flash Player.

References

Project Publications

Image melding: Combining inconsistent images using patch-based synthesis

Darabi, S., Shechtman, E., Barnes, C., Goldman, D., Sen, P. (Aug. 5, 2012)
ACM Transactions on Graphics (Proc. SIGGRAPH'12) , 31(4), August 2012.

Non-parametric texture transfer using MeshMatch

Chen, X., Funkhouser, T., Goldman, D., Shechtman, E. (Nov. 1, 2012)
In the Adobe Technical Report 2012-2.

Non-rigid dense correspondence with applications for image enhancement

HaCohen, Y., Shechtman, E., Goldman, D., Lischinski, D. (Aug. 7, 2011)
ACM Transactions on Graphics (Proc. SIGGRAPH) , 30(4), 2011.

Optimizing Color Consistency in Photo Collections

HaCohen, Y., Shechtman, E., Goldman, D., Lischinski, D. (Jul. 21, 2013)
ACM Transactions on Graphics (Proc. of SIGGRAPH'13), 32(4), July 2013

Patch-based High Dynamic Range Video

Kalantari, N., Shechtman, E., Barnes, C., Darabi, S., Goldman, D., Sen, P. (Nov. 19, 2013)
ACM Transactions on Graphics (Proc. SIGGRAPH Asia'13), 32(5), November 2013

PatchMatch: A randomized correspondence algorithm for structural image editing

Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D. (Aug. 2, 2009)
ACM Transactions on Graphics (Proc. SIGGRAPH), 28(3), 2009.

Robust patch-based HDR reconstruction of dynamic scenes

Sen, P., Kalantari, N., Yaesoubi, M., Darabi, S., Goldman, D., Shechtman, E. (Nov. 28, 2012)
ACM Transactions on Graphics (Proc. SIGGRAPH Asia'12), 31(6), November 2012.

The generalized PatchMatch correspondence algorithm

Barnes, C., Shechtman, E., Goldman, D., Finkelstein, A. (Sep. 1, 2010)
In Proc. European Conference on Computer Vision , Crete, 2010.

The PatchMatch randomized matching algorithm for image manipulation

Barnes, C., Goldman, D., Shechtman, E., Finkelstein, A. (Nov. 1, 2011)
Communications of the ACM , 54 (11), pp 103-110, 2011. Research Highlight.