《PatchMatch-A-Randomized-Correspondence-Algorithm-for-Structural-Image-Editing.pdf》由会员分享，可在线阅读，更多相关《PatchMatch-A-Randomized-Correspondence-Algorithm-for-Structural-Image-Editing.pdf（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。
1、PatchMatch: A Randomized Correspondence Algorithm for Structural Image EditingConnelly Barnes1Eli Shechtman2,3Adam Finkelstein1Dan B Goldman21Princeton University2Adobe Systems3University of Washington(a) original(b) hole+constraints(c) hole filled(d) constraints(e) constrained retarget(f) reshuffle
2、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 roofline; (c) the hole is filled in; (d) user-supplied line constraints for retargeting;(e) retargeting using constra
3、ints eliminates two columns automatically; and (f) user translates the roof upward using reshuffling.AbstractThis paper presents interactive image editing tools using a newrandomized algorithm for quickly finding approximate nearest-neighbor matches between image patches.Previous research ingraphics
4、 andvisionhasleveragedsuchnearest-neighborsearches toprovide a variety of high-level digital image editing tools. However,the cost of computing a field of such matches for an entire imagehas eluded previous efforts to provide interactive performance. Ouralgorithm offers substantial performance impro
5、vements over theprevious state of the art (20-100 x), enabling its use in interactiveediting tools.The key insights driving the algorithm are thatsome good patch matches can be found via random sampling, andthat natural coherence in the imagery allows us to propagate suchmatches quickly to surroundi
6、ng areas. We offer theoretical analysisof the convergence properties of the algorithm, as well as empiricaland practical evidence for its high quality and performance. Thisone simple algorithm forms the basis for a variety of tools imageretargeting, completion and reshuffling that can be used togeth
7、erin the context of a high-level image editing application. Finally, weproposeadditionalintuitiveconstraintsonthesynthesisprocessthatoffer the user a level of control unavailable in previous methods.CR Categories:I.3.6 Computing Methodologies: ComputerGraphicsMethodologyandTechniques; I.4.9Computing
8、Method-ologies: Image Processing and Computer VisionApplicationsKeywords: Approximate nearest neighbor, patch-based synthesis,image editing, completion, retargeting, reshuffling1IntroductionAsdigitalandcomputationalphotographyhavematured, researchershave developed methods for high-level editing of d
9、igital pho-tographs and video to meet a set of desired goals. For example,recent algorithms for image retargeting allow images to be resizedto a new aspect ratio the computer automatically produces a goodlikeness of the contents of the original image but with new dimen-sions Rubinstein et al. 2008;
10、Wang et al. 2008. Other algorithmsfor image completion let a user simply erase an unwanted portionof an image, and the computer automatically synthesizes a fill re-gion that plausibly matches the remainder of the image Criminisiet al. 2003; Komodakis and Tziritas 2007. Image reshuffling al-gorithms
11、make it possible to grab portions of the image and movethem around the computer automatically synthesizes the remain-der of the image so as to resemble the original while respecting themoved regions Simakov et al. 2008; Cho et al. 2008.In each of these scenarios, user interaction is essential, for s
12、everalreasons: First, thesealgorithmssometimesrequireuserinterventionto 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 bestcompletion algorithms offer tool
13、s to guide the result by providinghints for the computer Sun et al. 2005. These methods providesuch controls because the user is attempting to optimize a set ofgoals that are known to him and not to the computer.Second,the user often cannot even articulate these goals a priori.Theartistic process of
14、 creating the desired image demands the use oftrial and error, as the user seeks to optimize the result with respectto personal criteria specific 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
15、toolset mustprovide the flexibility 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 seesintermediate results in the process of trial and error. Most high-level editing approa
16、ches meet only one of these criteria. For ex-ample, one family of algorithms known loosely as non-parametricpatch sampling has been shown to perform a range of editing taskswhile meeting the first criterion flexibility Hertzmann et al. 2001;Wexler et al. 2007; Simakov et al. 2008. These methods are
17、basedon small (e.g. 7x7) densely sampled patches at multiple scales, andare able to synthesize both texture and complex image structuresthat qualitatively resemble the input imagery. Because of their abil-ity to preserve structures, we call this class of techniques structuralimage editing. Unfortuna
18、tely, until now these methods have failedthe second criterion they are far too slow for interactive use on allbut the smallest images. However, in this paper we will describe analgorithm that accelerates such methods by at least an order of mag-nitude, making it possible to apply them in an interact
19、ive structuralimage editing framework.To understand this algorithm, we must consider the common com-ponents of these methods:The core element of nonparamet-ric patch sampling methods is a repeated search of all patchesin one image region for the most similar patchin another image region. In other wo
20、rds, givenimages or regions A and B, find for everypatch in A the nearest neighbor in B under apatch distance metric such as Lp. We call thismapping the Nearest-Neighbor Field (NNF),illustrated schematically in the inset figure.Approaching this problem with a na ve bruteforce search is expensive O(m
21、M2) for imageregions and patches of size M and m pixels,respectively. Even using acceleration methodssuchasapproximatenearestneighbors Mountand Arya 1997 and dimensionality reduction,this search step remains the bottleneck of non-parametric patch sampling methods, preventing them from attain-ing int
22、eractive speeds. Furthermore, these tree-based accelerationstructures use memory in the order of O(M) or higher with rela-tively large constants, limiting their application for high resolutionimagery.To efficiently compute approximate nearest-neighbor fields our newalgorithm relies on three key obse
23、rvations about the problem:Dimensionality of offset space. First, although the dimensional-ity of the patch space is large (m dimensions), it is sparsely pop-ulated (O(M) patches). Many previous methods have acceleratedthe nearest neighbor search by attacking the dimensionality of thepatch space usi
24、ng tree structures (e.g., kd-tree, which can searchin O(mMlogM) time) and dimensionality reduction methods (e.g.,PCA). In contrast, our algorithm searches in the 2-D space of pos-sible patch offsets, achieving greater speed and memory efficiency.Natural structure of images.Second, the usual independ
25、entsearch for each pixel ignores the natural structure in images. Inpatch-sampling synthesis algorithms, the output typically containslarge contiguous chunks of data from the input (as observed byAshikhmin 2001). Thus we can improve efficiency by performingsearches for adjacent pixels in an interdep
26、endent manner.The law of large numbers.Finally, whereas any one randomchoice of patch assignment is very unlikely to be a good guess,some nontrivial fraction of a large field of random assignments willlikely be good guesses. As this field grows larger, the chance thatno patch will have a correct off
27、set becomes vanishingly small.Based on these three observations we offer a randomized algorithmfor computing approximate NNFs using incremental updates (Sec-tion 3). The algorithm begins with an initial guess, which may bederived from prior information or may simply be a random field.The iterative p
28、rocess consists of two phases: propagation, in whichcoherence is used to disseminate good solutions to adjacent pixelsin the field; and random search, in which the current offset vectoris perturbed by multiple scales of random offsets. We show boththeoretically and empirically that the algorithm has
29、 good conver-gence properties for tested imagery up to 2MP, and our CPU im-plementation shows speedups of 20-100 times versus kd-trees withPCA. Moreover, we propose a GPU implementation that is roughly7 times faster than the CPU version for similar image sizes. Ouralgorithm requires very little extr
30、a memory beyond the original im-age, unlike previous algorithms that build auxiliary data structuresto accelerate the search. Using typical settings of our algorithmsparameters, the runtime is O(mMlogM) and the memory usage isO(M). Although this is the same asymptotic time and memory asthe most effi
31、cient tree-based acceleration techniques, the leadingconstants are substantially smaller.In Section 4, we demonstrate the application of this algorithm in thecontext of a structural image editing program with three modes ofinteractive editing: image retargeting, image completion and imagereshuffling
32、. The system includes a set of tools that offer additionalcontrol over previous methods by allowing the user to constrain thesynthesis process in an intuitive and interactive way (Figure 1).The contributions of our work include a fast randomized approxi-mation algorithm for computing the nearest-nei
33、ghbor field betweentwo disjoint image regions; an application of this algorithm within astructural image editing framework that enables high-quality inter-active image retargeting, image completion, and image reshuffling;and a set of intuitive interactive controls used to constrain the opti-mization
34、 process to obtain desired creative results.2Related workPatch-based sampling methods have become a popular tool forimage and video synthesis and analysis.Applications includetexture synthesis, image and video completion, summarization andretargeting, image recomposition and editing, image stitching
35、 andcollages, newviewsynthesis, noiseremovalandmore. Wewillnextreview some of these applications and discuss the common searchtechniques that they use as well as their degree of interactivity.Texture synthesis and completion. Efros and Leung 1999 in-troduced a simple non-parametric texture synthesis
36、 method thatoutperformed many previous model based methods by samplingpatches from a texture example and pasting them in the synthe-sized image. Further improvements modify the search and sam-pling approaches for better structure preservation Wei and Levoy2000; Ashikhmin 2001; Liang et al. 2001; Efr
37、os and Freeman 2001;Kwatra et al. 2003; Criminisi et al. 2003; Drori et al. 2003. Thegreedy fill-in order of these algorithms sometimes introduces incon-sistencieswhencompletinglargeholeswithcomplexstructures, butWexler et al. 2007 formulated the completion problem as a globaloptimization, thus obta
38、ining more globally consistent completionsof large missing regions. This iterative multi-scale optimizationalgorithm repeatedly searches for nearest neighbor patches for allhole pixels in parallel. Although their original implementation wastypically slow (a few minutes for images smaller than 1 MP),
39、 ouralgorithm makes this technique applicable to much larger imagesat interactive rates. Patch optimization based approaches have nowbecome common practice in texture synthesis Kwatra et al. 2005;Kopf et al. 2007; Wei et al. 2008. In that domain, Lefebvre andHoppe 2005 have used related parallel upd
40、ate schemes and evendemonstrated real-time GPU based implementations. Komodakisand Tziritas 2007 proposed another global optimization formu-lation for image completion using Loopy Belief Propagation withan adaptive priority messaging scheme. Although this method pro-duces excellent results, it is st
41、ill relatively slow and has only beendemonstrated on small images.Nearest neighbor search methods.The high synthesis qualityof patch optimization methods comes at the expense of moresearch iterations, which is the clear complexity bottleneck in allof these methods.Moreover, whereas in texture synthe
42、sis thetexture example is usually a small image, in other applicationssuch as patch-based completion, retargeting and reshuffling, theinput image is typically much larger so the search problem is evenmore critical. Various speedups for this search have been proposed,generally involving tree structur
43、es such as TSVQ Wei and Levoy2000, kd-trees Hertzmann et al. 2001; Wexler et al. 2007; Kopfet al. 2007, and VP-trees Kumar et al. 2008, each of whichsupports both exact and approximate search (ANN). In synthesisapplications, approximate search is often used in conjunction withdimensionality reductio
44、n techniques such as PCA Hertzmann et al.2001; Lefebvre and Hoppe 2005; Kopf et al. 2007, becauseANN methods are much more time- and memory-efficient in lowdimensions.Ashikhmin 2001 proposed a local propagationtechnique exploiting local coherence in the synthesis process bylimiting the search space
45、for a patch to the source locations of itsneighbors in the exemplar texture. Our propagation search stepis inspired by the same coherence assumption. The k-coherencetechnique Tong et al. 2002 combines the propagation idea with aprecomputationstageinwhichthek nearestneighborsofeachpatchare cached, an
46、d later searches take advantage of these precomputedsets. Although this accelerates the search phase, k-coherence stillrequires a full nearest-neighbor search for all pixels in the input,and has only been demonstrated in the context of texture synthesis.It assumes that the initial offsets are close
47、enough that it suffices tosearch only a small number of nearest neighbors. This may be truefor small pure texture inputs, but we found that for large compleximages our random search phase is required to escape local minima.In this work we compare speed and memory usage of our algorithmagainst kd-tre
48、es with dimensionality reduction, and we show thatit is at least an order of magnitude faster than the best competingcombination (ANN+PCA) and uses significantly less memory. Ouralgorithm also provides more generality than kd-trees because itcan be applied with arbitrary distance metrics, and easily
49、 modifiedto enable local interactions such as constrained completion.Control and interactivity.One advantage of patch samplingschemes is that they offer a great deal of fine-scale control. For ex-ample, in texture synthesis, the method of Ashikhmin 2001 givesthe user control over the process by init
50、ializing the output pixelswith desired colors.The image analogies framework of Hertz-mann et al. 2001 uses auxiliary images as “guiding layers,” en-abling a variety of effects including super-resolution, texture trans-fer, artistic filters, and texture-by-numbers. In the field of imagecompletion, im
黑公网安备:91230400333293403D