PatchMatch: patches found at random
In August 2009 at SIGGRAPH Connelly Barnes, Eli Shechtman, Adam Finkelstein and Dan Goldman (Princeton, Adobe) described PatchMatch, a search for similar patches in an image 20 to 100 times faster than kd-trees: random matches first, then good ones are passed to neighbours and refined by random search.
Why it matters
Patch-based editing gave good results but took minutes, so it could not be used interactively. PatchMatch brought it down to seconds: filling a hole, changing proportions and moving parts of an image could now be done and adjusted while working, which had not been possible before.
ACM Transactions on Graphics 28(3). The 20-100x speed-up is against kd-trees with PCA on 7 x 7 patches, with about twenty times less memory; a graphics card version is roughly 7 times faster again than the processor one. Convergence was tested on images up to 2 megapixels. The paper’s tools are retargeting, completion and reshuffling under user constraints (lines that must stay straight). Photoshop is not mentioned in the paper; that the method became Content-Aware Fill in Photoshop CS5 the authors would state in Communications of the ACM in 2011.