The generalized PatchMatch correspondence algorithm

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

389 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationComputer Vision, ECCV 2010 - 11th European Conference on Computer Vision, Proceedings
PublisherSpringer Verlag
Pages29-43
Number of pages15
EditionPART 3
ISBN (Print)364215557X, 9783642155574
DOIs
StatePublished - 2010
Event11th European Conference on Computer Vision, ECCV 2010 - Heraklion, Crete, Greece
Duration: Sep 10 2010Sep 11 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 3
Volume6313 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th European Conference on Computer Vision, ECCV 2010
Country/TerritoryGreece
CityHeraklion, Crete
Period9/10/109/11/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'The generalized PatchMatch correspondence algorithm'. Together they form a unique fingerprint.

Cite this