{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:18:04Z","timestamp":1763468284217,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T00:00:00Z","timestamp":1437955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2015,7,27]]},"abstract":"<jats:p>This paper presents a data structure that reduces approximate nearest neighbor query times for image patches in large datasets. Previous work in texture synthesis has demonstrated real-time synthesis from small exemplar textures. However, high performance has proved elusive for modern patch-based optimization techniques which frequently use many exemplar images in the tens of megapixels or above. Our new algorithm, PatchTable, offloads as much of the computation as possible to a pre-computation stage that takes modest time, so patch queries can be as efficient as possible. There are three key insights behind our algorithm: (1) a lookup table similar to locality sensitive hashing can be precomputed, and used to seed sufficiently good initial patch correspondences during querying, (2) missing entries in the table can be filled during pre-computation with our fast Voronoi transform, and (3) the initially seeded correspondences can be improved with a precomputed k-nearest neighbors mapping. We show experimentally that this accelerates the patch query operation by up to 9\u00d7 over k-coherence, up to 12\u00d7 over TreeCANN, and up to 200\u00d7 over PatchMatch. Our fast algorithm allows us to explore efficient and practical imaging and computational photography applications. We show results for artistic video stylization, light field super-resolution, and multi-image editing.<\/jats:p>","DOI":"10.1145\/2766934","type":"journal-article","created":{"date-parts":[[2015,7,28]],"date-time":"2015-07-28T12:26:38Z","timestamp":1438086398000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":48,"title":["PatchTable"],"prefix":"10.1145","volume":"34","author":[{"given":"Connelly","family":"Barnes","sequence":"first","affiliation":[{"name":"University of Virginia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fang-Lue","family":"Zhang","sequence":"additional","affiliation":[{"name":"TNList, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liming","family":"Lou","sequence":"additional","affiliation":[{"name":"University of Virginia and Shandong University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xian","family":"Wu","sequence":"additional","affiliation":[{"name":"TNList, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shi-Min","family":"Hu","sequence":"additional","affiliation":[{"name":"TNList, Tsinghua University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2010.105"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/364338.364405"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531330"},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Barnes C. Shechtman E. Goldman D. B. and Finkelstein A. 2010. The generalized PatchMatch correspondence algorithm. In ECCV. 29--43. Barnes C. Shechtman E. Goldman D. B. and Finkelstein A. 2010. The generalized PatchMatch correspondence algorithm. In ECCV. 29--43.","DOI":"10.1007\/978-3-642-15558-1_3"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.62"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461929"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/344779.344972"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Boominathan V. Mitra K. and Veeraraghavan A. 2014. Improving resolution and depth-of-field of light field cameras using a hybrid imaging system. In IEEE ICCP 1--10. Boominathan V. Mitra K. and Veeraraghavan A. 2014. Improving resolution and depth-of-field of light field cameras using a hybrid imaging system. In IEEE ICCP 1--10.","DOI":"10.1109\/ICCPHOT.2014.6831814"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301330"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276507"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2004.833105"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/964965.808600"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185578"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383296"},{"key":"e_1_2_2_16_1","volume-title":"IEEE ICCV","volume":"2","author":"Efros A. A.","unstructured":"Efros , A. A. , and Leung , T. K . 1999. Texture synthesis by non-parametric sampling . In IEEE ICCV , vol. 2 . Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In IEEE ICCV, vol. 2."},{"volume-title":"Image Analysis","author":"Farneb\u00e4ck G.","key":"e_1_2_2_17_1","unstructured":"Farneb\u00e4ck , G. 2003. Two-frame motion estimation based on polynomial expansion . In Image Analysis . Springer , 363--370. Farneb\u00e4ck, G. 2003. Two-frame motion estimation based on polynomial expansion. In Image Analysis. Springer, 363--370."},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Felzenszwalb P. F. and Huttenlocher D. P. 2012. Distance transforms of sampled functions. Theory of computing 8 1 415--428. Felzenszwalb P. F. and Huttenlocher D. P. 2012. Distance transforms of sampled functions. Theory of computing 8 1 415--428.","DOI":"10.4086\/toc.2012.v008a019"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.988747"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461997"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Hashimoto R. Johan H. and Nishita T. 2003. Creating various styles of animations using example-based filtering. In IEEE Computer Graphics International 312--317. Hashimoto R. Johan H. and Nishita T. 2003. Creating various styles of animations using example-based filtering. In IEEE Computer Graphics International 312--317.","DOI":"10.1109\/CGI.2003.1214488"},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"He K. and Sun J. 2012. Computing nearest-neighbor fields via propagation-assisted kd-trees. In IEEE CVPR 111--118. He K. and Sun J. 2012. Computing nearest-neighbor fields via propagation-assisted kd-trees. In IEEE CVPR 111--118.","DOI":"10.1109\/CVPR.2012.6247665"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/383259.383295"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508381"},{"key":"e_1_2_2_25_1","volume-title":"-K","author":"Hwang Y.","year":"2012","unstructured":"Hwang , Y. , Han , B. , and Ahn , H . -K . 2012 . A fast nearest neighbor search algorithm by nonlinear embedding. In IEEE CVPR , 3053--3060. Hwang, Y., Han, B., and Ahn, H.-K. 2012. A fast nearest neighbor search algorithm by nonlinear embedding. In IEEE CVPR, 3053--3060."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508402"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276380"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2011.6126421"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321910"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073261"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Lefebvre S. and Hoppe H. 2006. Appearance-space texture synthesis. 541--548. Lefebvre S. and Hoppe H. 2006. Appearance-space texture synthesis. 541--548.","DOI":"10.1145\/1141911.1141921"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2003.1177156"},{"key":"e_1_2_2_34_1","unstructured":"Muja M. and Lowe D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP(1) 331--340. Muja M. and Lowe D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP(1) 331--340."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33765-9_43"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/1049-9660(92)90050-D"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321357"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12056"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Simakov D. Caspi Y. Shechtman E. and Irani M. 2008. Summarizing visual data using bidirectional similarity. In IEEE CVPR 1--8. Simakov D. Caspi Y. Shechtman E. and Irani M. 2008. Summarizing visual data using bidirectional similarity. In IEEE CVPR 1--8.","DOI":"10.1109\/CVPR.2008.4587842"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566634"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661229.2661278"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.60"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.226"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601145"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2766934","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2766934","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:56:02Z","timestamp":1750272962000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2766934"}},"subtitle":["efficient patch queries for large datasets and applications"],"short-title":[],"issued":{"date-parts":[[2015,7,27]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,7,27]]}},"alternative-id":["10.1145\/2766934"],"URL":"https:\/\/doi.org\/10.1145\/2766934","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2015,7,27]]},"assertion":[{"value":"2015-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}