PatchTable: efficient patch queries for large datasets and applications

Barnes, Connelly, Zhang, Fang-Lue, Lou, Liming, Wu, Xian and Hu, Shi-Min ORCID: https://orcid.org/0000-0001-7507-6542 2015. PatchTable: efficient patch queries for large datasets and applications. ACM Transactions on Graphics 34 (4) , 97. 10.1145/2766934

Preview

PDF - Accepted Post-Print Version Download (10MB) | Preview

Abstract

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 9x over k-coherence, up to 12x over TreeCANN, and up to 200x 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 inpainting.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Association for Computing Machinery (ACM)
ISSN:	0730-0301
Date of First Compliant Deposit:	6 September 2016
Date of Acceptance:	31 March 2015
Last Modified:	07 Nov 2023 05:42
URI:	https://orca.cardiff.ac.uk/id/eprint/94251

Citation Data

Cited 50 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item