Princeton > CS Dept > PIXL > Graphics > Publications Local Access 

The Generalized PatchMatch Correspondence Algorithm
European Conference on Computer Vision, September 2010

Connelly Barnes, Eli Shechtman, Dan B Goldman,
Adam Finkelstein

Denoising using Generalized PatchMatch. Ground truth (a) is corrupted by Gaussian noise (b). Buades et al. [2] (c) denoise by averaging similar patches in a small local window: PSNR 28.93. Our method (d) uses PatchMatch for nonlocal search, improving repetitive features, but uniform regions remain noisy, as we use only k = 16 nearest neighbors: PSNR 29.11. Weighting matches from both algorithms (e) gives the best overall result: PSNR 30.90.


PatchMatch is a fast algorithm for computing dense approximate nearest neighbor correspondences between patches of two image regions [1]. This paper generalizes PatchMatch in three ways: (1) to fi nd k nearest neighbors, as opposed to just one, (2) to search across scales and rotations, in addition to just translations, and (3) to match using arbitrary descriptors and distances, not just sum-of-squared differences on patch colors. In addition, we offer new search and parallelization strategies that further accelerate the method, and we show performance improvements over standard kd-tree techniques across a variety of inputs. In contrast to many previous matching algorithms, which for efficiency reasons have restricted matching to sparse interest points, or spatially proximate matches, our algorithm can efficiently find global, dense matches, even while matching across all scales and rotations. This is especially useful for computer vision applications, where our algorithm can be used as an efficient general-purpose component. We explore a variety of vision applications: denoising, finding forgeries by detecting cloned regions, symmetry detection, and object detection.

Citation (BibTeX)

Connelly Barnes, Eli Shechtman, Dan B Goldman, and Adam Finkelstein. The Generalized PatchMatch Correspondence Algorithm. European Conference on Computer Vision, September 2010.

  Paper (7 MB PDF)
  Supplemental (1 MB PDF)

See Also
  PatchMatch - Website for the original paper
  Source Code - Core matching algorithms only for PatchMatch + Generalized PatchMatch. Version 2.0, a MATLAB mex. Synthesis applications not included. Licensed by Adobe for noncommercial research use only.