The Generalized PatchMatch Correspondence Algorithm
European Conference on Computer Vision, September 2010
Abstract
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 find 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.
Files
- 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.
Citation
Connelly Barnes, Eli Shechtman, Dan B Goldman, and Adam Finkelstein.
"The Generalized PatchMatch Correspondence Algorithm."
European Conference on Computer Vision, September 2010.
BibTeX
@inproceedings{Barnes:2010:TGP, author = "Connelly Barnes and Eli Shechtman and Dan B Goldman and Adam Finkelstein", title = "The Generalized {PatchMatch} Correspondence Algorithm", booktitle = "European Conference on Computer Vision", year = "2010", month = sep }