{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T02:33:50Z","timestamp":1780108430745,"version":"3.54.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2009,7,27]],"date-time":"2009-07-27T00:00:00Z","timestamp":1248652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0511965"],"award-info":[{"award-number":["IIS-0511965"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,7,27]]},"abstract":"<jats:p>This paper presents interactive image editing tools using a new randomized algorithm for quickly finding approximate nearest-neighbor matches between image patches. Previous research in graphics and vision has leveraged such nearest-neighbor searches to provide a variety of high-level digital image editing tools. However, the cost of computing a field of such matches for an entire image has eluded previous efforts to provide interactive performance. Our algorithm offers substantial performance improvements over the previous state of the art (20-100x), enabling its use in interactive editing tools. The key insights driving the algorithm are that some good patch matches can be found via random sampling, and that natural coherence in the imagery allows us to propagate such matches quickly to surrounding areas. We offer theoretical analysis of the convergence properties of the algorithm, as well as empirical and practical evidence for its high quality and performance. This one simple algorithm forms the basis for a variety of tools -- image retargeting, completion and reshuffling -- that can be used together in the context of a high-level image editing application. Finally, we propose additional intuitive constraints on the synthesis process that offer the user a level of control unavailable in previous methods.<\/jats:p>","DOI":"10.1145\/1531326.1531330","type":"journal-article","created":{"date-parts":[[2009,7,28]],"date-time":"2009-07-28T08:43:55Z","timestamp":1248770635000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2127,"title":["PatchMatch"],"prefix":"10.1145","volume":"28","author":[{"given":"Connelly","family":"Barnes","sequence":"first","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eli","family":"Shechtman","sequence":"additional","affiliation":[{"name":"Adobe Systems and University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adam","family":"Finkelstein","sequence":"additional","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dan B","family":"Goldman","sequence":"additional","affiliation":[{"name":"Adobe Systems"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/364338.364405"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276390"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.38"},{"key":"e_1_2_2_4_1","unstructured":"Cho T. S. Butman M. Avidan S. and Freeman W. 2008. The patch transform and its applications to image editing. CVPR.  Cho T. S. Butman M. Avidan S. and Freeman W. 2008. The patch transform and its applications to image editing. CVPR ."},{"key":"e_1_2_2_5_1","first-page":"721","article-title":"Object removal by exemplar-based inpainting","volume":"2","author":"Criminisi A., P","year":"2003","unstructured":"Criminisi , A., P &amp;#233;rez, P., and Toyama , K. 2003 . Object removal by exemplar-based inpainting . CVPR 2 , 721 . Criminisi, A., P&amp;#233;rez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 2, 721.","journal-title":"CVPR"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882267"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383296"},{"key":"e_1_2_2_8_1","first-page":"1033","article-title":"Texture synthesis by non-parametric sampling","volume":"2","author":"Efros A. A.","year":"1999","unstructured":"Efros , A. A. , and Leung , T. K. 1999 . Texture synthesis by non-parametric sampling . ICCV 2 , 1033 . Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. ICCV 2, 1033.","journal-title":"ICCV"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276392"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/358669.358692"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Fitzgibbon A. Wexler Y. and Zisserman A. 2003. Image-based rendering using image-based priors. In ICCV 1176.   Fitzgibbon A. Wexler Y. and Zisserman A. 2003. Image-based rendering using image-based priors. In ICCV 1176.","DOI":"10.1109\/ICCV.2003.1238625"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.988747"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383295"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2007.906269"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1275808.1276380"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88688-4_27"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882264"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073263"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073261"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/501786.501787"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095034.1095061"},{"key":"e_1_2_2_22_1","volume-title":"ANN: A library for approximate nearest neighbor searching, Oct. 28.","author":"Mount D. M.","year":"1997","unstructured":"Mount , D. M. , and Arya , S. , 1997 . ANN: A library for approximate nearest neighbor searching, Oct. 28. Mount, D. M., and Arya, S., 1997. ANN: A library for approximate nearest neighbor searching, Oct. 28."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0050-2"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111411.1111431"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1141911.1141965"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360615"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1149488.1149499"},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"Simakov D. Caspi Y. Shechtman E. and Irani M. 2008. Summarizing visual data using bidirectional similarity. In CVPR.  Simakov D. Caspi Y. Shechtman E. and Irani M. 2008. Summarizing visual data using bidirectional similarity. In CVPR .","DOI":"10.1109\/CVPR.2008.4587842"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073274"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70844"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566634"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1457515.1409071"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.345009"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360651"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.60"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Wolf L. Guttmann M. and Cohen-Or D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV.  Wolf L. Guttmann M. and Cohen-Or D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV .","DOI":"10.1109\/ICCV.2007.4409010"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531330","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1531326.1531330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:30:23Z","timestamp":1750239023000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1531326.1531330"}},"subtitle":["a randomized correspondence algorithm for structural image editing"],"short-title":[],"issued":{"date-parts":[[2009,7,27]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,7,27]]}},"alternative-id":["10.1145\/1531326.1531330"],"URL":"https:\/\/doi.org\/10.1145\/1531326.1531330","relation":{"is-identical-to":[{"id-type":"doi","id":"10.1145\/3596711.3596777","asserted-by":"object"}]},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,27]]},"assertion":[{"value":"2009-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}