PatchMatch

The core PatchMatch algorithm quickly finds 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 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 formula_1 of offsets, which is over all possible matches of patch (location of patch centers) in image A, for some distance function of two patches formula_2. So, for a given patch coordinate formula_3 in image formula_4 and its corresponding nearest neighbor formula_5 in image formula_6, formula_7 is simply formula_8. However, if we search for every point in image formula_6, the work will be too hard to complete. So the following algorithm is done in a 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 use a coarse-to-fine approach by building an image pyramid to obtain the better result.
Initialization.
When initializing with random offsets, we use independent uniform samples across the full range of image formula_6. 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 local minima.
Iteration.
After initialization, the algorithm attempted to perform iterative process of improving the formula_11. 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 formula_12 using the known offsets of formula_13 and formula_14, assuming that the patch offsets
are likely to be the same. That is, the algorithm will take new value for formula_12 to be formula_16. 
So if formula_17 has a correct mapping and is in a coherent region formula_18, then all of formula_18 below and to the right of formula_17 will be filled with the correct mapping. Alternatively, on even iterations, the algorithm search for different direction, fill the new value to be formula_21.
Random search.
Let formula_22, we attempt to improveformula_17 by testing a sequence of candidate offsets at an exponentially decreasing distance from formula_24
where formula_26 is a uniform random in formula_27, formula_28 is a large window search radius which will be set to maximum picture size, and formula_29 is a fixed ratio often assigned as 1/2. This part of the algorithm allows the formula_12 to jump out of local minimum through random process.
Halting criteria.
The often used halting criteria is set the iteration times to be about 4~5. Even with low iteration, the algorithm works well.
Conclusion.
This is an efficient algorithm since it only takes a few second on a testing computer with Intel Core i5 CPU and Photoshop CS5.