PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing Connelly Barnes1Eli Shechtman2,3Adam Finkelstein1Dan B Goldman2 1Princeton University2Adobe Systems3University of Washington (a) original(b) hole+constraints (c) hole fi lled(d) constraints(e) constrained retarget (f) reshuffl e Figure 1: Structural image editing. Left to right: (a) the original image; (b) a hole is marked (magenta) and we use line constraints (red/green/blue) to improve the continuity of the roofl ine; (c) the hole is fi lled in; (d) user-supplied line constraints for retargeting; (e) retargeting using constraints eliminates two columns automatically; and (f) user translates the roof upward using reshuffl ing. Abstract This paper presents interactive image editing tools using a new randomized algorithm for quickly fi nding approximate nearest- neighbor matches between image patches.Previous research in graphics andvisionhasleveragedsuchnearest-neighborsearches to provide a variety of high-level digital image editing tools. However, the cost of computing a fi eld 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 reshuffl ing that can be used together in the context of a high-level image editing application. Finally, we proposeadditionalintuitiveconstraintsonthesynthesisprocessthat offer the user a level of control unavailable in previous methods. CR Categories:I.3.6 Computing Methodologies: Computer GraphicsMethodologyandTechniques; I.4.9ComputingMethod- ologies: Image Processing and Computer VisionApplications Keywords: Approximate nearest neighbor, patch-based synthesis, image editing, completion, retargeting, reshuffl ing 1Introduction Asdigitalandcomputationalphotographyhavematured, researchers have developed methods for high-level editing of digital pho- tographs and video to meet a set of desired goals. For example, recent algorithms for image retargeting allow images to be resized to a new aspect ratio the computer automatically produces a good likeness of the contents of the original image but with new dimen- sions Rubinstein et al. 2008; Wang et al. 2008. Other algorithms for image completion let a user simply erase an unwanted portion of an image, and the computer automatically synthesizes a fi ll re- gion that plausibly matches the remainder of the image Criminisi et al. 2003; Komodakis and Tziritas 2007. Image reshuffl ing al- gorithms make it possible to grab portions of the image and move them around the computer automatically synthesizes the remain- der of the image so as to resemble the original while respecting the moved regions Simakov et al. 2008; Cho et al. 2008. In each of these scenarios, user interaction is essential, for several reasons: First, thesealgorithmssometimesrequireuserintervention to obtain the best results.Retargeting algorithms, for example, sometimes provide user controls to specify that one or more regions (e.g., faces) should be left relatively unaltered. Likewise, the best completion algorithms offer tools to guide the result by providing hints for the computer Sun et al. 2005. These methods provide such controls because the user is attempting to optimize a set of goals that are known to him and not to the computer.Second, the user often cannot even articulate these goals a priori.The artistic process of creating the desired image demands the use of trial and error, as the user seeks to optimize the result with respect to personal criteria specifi c to the image under consideration. The role of interactivity in the artistic process implies two prop- erties for the ideal image editing framework: (1) the toolset must provide the fl exibility to perform a wide variety of seamless edit- ing operations for users to explore their ideas; and (2) the perfor- mance of these tools must be fast enough that the user quickly sees intermediate results in the process of trial and error. Most high- level editing approaches meet only one of these criteria. For ex- ample, one family of algorithms known loosely as non-parametric patch sampling has been shown to perform a range of editing tasks while meeting the fi rst criterion fl exibility Hertzmann et al. 2001; Wexler et al. 2007; Simakov et al. 2008. These methods are based on small (e.g. 7x7) densely sampled patches at multiple scales, and are able to syn