View source for PatchMatch

{{technical|date=June 2013}}
[[File:PatchMatch.jpg|thumbnail|Flowers at right bottom corner are removed using PatсhMatсh]]
The core '''PatchMatch''' [[algorithm]] quickly finds [[Correspondence problem|correspondences]] between small square regions (or patches) of an [[image]]. The algorithm can be used in various applications such as object removal from images, reshuffling or moving contents of images, or retargeting or changing [[Aspect ratio (image)|aspect ratios]] of images, [[optical flow]] estimation, or [[stereo correspondence]].

==Algorithm==
The goal of the [[algorithm]] is to find the patch correspondence by defining a '''nearest-neighbor field (NNF)''' as a [[Function (mathematics)|function]] <math>f  : \mathbb{R}^2 \to \mathbb{R}^2 </math> of offsets, which is over all possible matches of patch (location of patch centers) in image A, for some distance function of two patches <math>D</math>. So, for a given patch coordinate <math>a</math> in image <math>A</math> and its corresponding nearest neighbor <math>b</math> in image <math>B</math>, <math>f(a)</math> is simply <math>b - a</math>. However, if we search for every point in image <math>B</math>, the work will be too hard to complete. So the following algorithm is done in a [[Randomness|randomized]] approach in order to accelerate the [[calculation]] speed. 
The algorithm has three main components. Initially, the nearest-neighbor field is filled with either random offsets or some prior information. Next, an iterative update process is applied to the NNF, in which good patch offsets are propagated to adjacent pixels, followed by random search in the neighborhood of the best offset found so far. Independent of these three components, the algorithm also uses a coarse-to-fine approach by building an [[Pyramid (image processing)|image pyramid]] to obtain the better result.

===Initialization===
When initializing with random offsets, we use independent [[uniform]] [[Sample (statistics)|samples]] across the full range of image <math>B</math>. This algorithm avoids using an initial guess from the previous level of the pyramid because in this way the algorithm can avoid being trapped in [[Maxima and minima|local minima]]{{Clarify|date=January 2014}}.

===Iteration===
After initialization, the algorithm attempted to perform [[Iteration|iterative]] process of improving the <math>NNF</math>. The iterations examine the offsets in scan order (from left to right, top to bottom), and each undergoes '''propagation''' followed by '''random search'''.

===Propagation===
We attempt to improve <math>f(x,y)</math> using the known offsets of <math>f(x-1, y)</math> and <math>f(x, y-1)</math>, assuming that the patch offsets
are likely to be the same. That is, the algorithm will take new value for <math>f(x,y)</math> to be <math>\arg \min \limits _{(x,y)} {D(f(x, y)), D(f(x - 1, y)), D(f(x, y - 1))}</math>. 
So if <math>f(x, y)</math> has a correct mapping and is in a coherent region <math>R</math>, then all of <math>R</math> below and to the right of <math>f(x, y)</math> will be filled with the correct mapping. Alternatively, on even iterations, the algorithm search for different direction, fill the new value to be <math>\arg \min \limits _{(x,y)} \{D(f(x, y)), D(f(x + 1, y)), D(f(x, y + 1))\}</math>.

===Random search===
Let <math>v_0 = f(x, y)</math>, we attempt to improve<math>f(x, y)</math> by testing a sequence of candidate offsets at an exponentially decreasing [[distance]] from <math>v_0</math>
:<math>
u_i = v_0+w\alpha^iR_i
</math>

where <math>R_i</math> is a uniform random in <math>[-1, 1] \times [-1, 1]</math>, <math>w</math> is a large window search [[radius]] which will be set to maximum picture size, and <math>\alpha</math> is a fixed ratio often assigned as 1/2. This part of the algorithm allows the <math>f(x,y)</math> to jump out of local minimum through random process.

===Halting criterion===
The often used halting criterion is set the iteration times to be about 4~5. Even with low iteration, the algorithm works well.

==Conclusion==
{{Multiple issues|section=yes|
{{Unreferenced section|date=December 2018}}
{{Expand section|1=examples and additional citations|demospace=main|date=December 2018}}
}}
This is an efficient algorithm since it only takes a few second on a testing computer with [[Intel Core i5]] [[Central processing unit|CPU]] and [[Adobe Photoshop|Photoshop CS5]].

==See also==

* [[Nearest neighbor search]]

==References==

* Connelly Barnes, Eli Shechtman, Adam Finkelstein, Dan B Goldman(2009), [http://gfx.cs.princeton.edu/pubs/Barnes_2009_PAR/ PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing]

<!--Categories-->
[[Category:Computer vision]]