PatchTable: Efficient Patch Queries for Large Datasets and Applications

摘要

This paper presents a data structure that reduces approximate nearestrnneighbor query times for image patches in large datasets. Previousrnwork in texture synthesis has demonstrated real-time synthesisrnfrom small exemplar textures. However, high performancernhas proved elusive for modern patch-based optimization techniquesrnwhich frequently use many exemplar images in the tens of megapixelsrnor above. Our new algorithm, PatchTable, offloads as muchrnof the computation as possible to a pre-computation stage thatrntakes modest time, so patch queries can be as efficient as possible.rnThere are three key insights behind our algorithm: (1) a lookuprntable similar to locality sensitive hashing can be precomputed, andrnused to seed sufficiently good initial patch correspondences duringrnquerying, (2) missing entries in the table can be filled during precomputationrnwith our fast Voronoi transform, and (3) the initiallyrnseeded correspondences can be improved with a precomputed knearestrnneighbors mapping. We show experimentally that this acceleratesrnthe patch query operation by up to 9× over k-coherence,rnup to 12× over TreeCANN, and up to 200× over PatchMatch. Ourrnfast algorithm allows us to explore efficient and practical imagingrnand computational photography applications. We show resultsrnfor artistic video stylization, light field super-resolution, and multiimagernediting.