article · Communications of the ACM · 2011

The PatchMatch randomized matching algorithm for image manipulation

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

Cited by 55Abstract and details only

Abstract

This paper presents a new randomized algorithm for quickly finding approximate nearest neighbor matches between image patches. Our algorithm offers substantial performance improvements over the previous state of the art (20--100×), enabling its use in new interactive image editing tools, computer vision, and video applications. Previously, the cost of computing such matches for an entire image had eluded efforts to provide interactive performance. The key insight driving our algorithm is that the elements of our search domain---patches of image pixels---are correlated, and thus the search strategy takes advantage of these statistics. Our algorithm uses two principles: first, that good patch matches can be found via random sampling, and second, that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. Our simple algorithm allows finding a single nearest neighbor match across translations only, whereas our general algorithm additionally allows matching of k -nearest neighbors, across all rotations and scales, and matching arbitrary descriptors. This one simple algorithm forms the basis for a variety of applications including image retargeting, completion, reshuffling, object detection, digital forgery detection, and video summarization.

Cite this paper

APA 7

Barnes, C., Goldman, D. B., Shechtman, E., & Finkelstein, A. (2011). The PatchMatch randomized matching algorithm for image manipulation. Communications of the ACM, 54(11), 103–110. https://doi.org/10.1145/2018396.2018421

MLA 9

Barnes, Connelly, et al. “The PatchMatch randomized matching algorithm for image manipulation.” Communications of the ACM, vol. 54, no. 11, 2011, pp. 103–10, https://doi.org/10.1145/2018396.2018421.

Chicago

Barnes, Connelly, Dan B Goldman, Eli Shechtman, and Adam Finkelstein. 2011. “The PatchMatch randomized matching algorithm for image manipulation.” Communications of the ACM 54 (11): 103–10. https://doi.org/10.1145/2018396.2018421.

Harvard

Barnes, C. et al. (2011) ‘The PatchMatch randomized matching algorithm for image manipulation’, Communications of the ACM, 54(11), pp. 103–110. Available at: https://doi.org/10.1145/2018396.2018421.

BibTeX

@article{barnes2011patchmatch,
  title = {{The PatchMatch randomized matching algorithm for image manipulation}},
  author = {Barnes, Connelly and Goldman, Dan B and Shechtman, Eli and Finkelstein, Adam},
  journal = {Communications of the ACM},
  volume = {54},
  number = {11},
  pages = {103--110},
  year = {2011},
  doi = {10.1145/2018396.2018421}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.