“PatchTable: efficient patch queries for large datasets and applications” by Barnes
Conference:
Type(s):
Title:
- PatchTable: efficient patch queries for large datasets and applications
Session/Category Title: Image Similarity & Search
Presenter(s)/Author(s):
Moderator(s):
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 9× over k-coherence, up to 12× over TreeCANN, and up to 200× 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.
References:
1. Arietta, S., and Lawrence, J. 2011. Building and using a database of one trillion natural-image patches. IEEE computer graphics and applications 31, 1, 9–19. Google ScholarDigital Library
2. Ashikhmin, M. 2001. Synthesizing natural textures. In ACM symposium on Interactive 3D graphics, 217–226. Google ScholarDigital Library
3. Barnes, C., Shechtman, E., Finkelstein, A., and Goldman, D. 2009. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Transactions on Graphics 28, 3, 24:1–24:10. Google ScholarDigital Library
4. Barnes, C., Shechtman, E., Goldman, D. B., and Finkelstein, A. 2010. The generalized PatchMatch correspondence algorithm. In ECCV. 29–43. Google ScholarDigital Library
5. Ben-Artzi, G., Hel-Or, H., and Hel-Or, Y. 2007. The gray-code filter kernels. IEEE TPAMI 29, 3, 382–393. Google ScholarDigital Library
6. Bénard, P., Cole, F., Kass, M., Mordatch, I., Hegarty, J., Senn, M. S., Fleischer, K., Pesare, D., and Breeden. 2013. Stylizing animation by example. ACM Transactions on Graphics 32, 119:1–119:9. Google ScholarDigital Library
7. Bertalmio, M., Sapiro, G., Caselles, V., and Ballester, C. 2000. Image inpainting. In ACM Computer graphics and interactive techniques, 417–424. Google ScholarDigital Library
8. 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.Google Scholar
9. Borodin, A., Ostrovsky, R., and Rabani, Y. 1999. Lower bounds for high dimensional nearest neighbor search and related problems. In ACM symposium on Theory of computing. Google ScholarDigital Library
10. Bousseau, A., Neyret, F., Thollot, J., and Salesin, D. 2007. Video watercolorization using bidirectional texture advection. In ACM Transactions on Graphics, vol. 26, 104:1–104:10. Google ScholarDigital Library
11. Criminisi, A., Pérez, P., and Toyama, K. 2004. Region filling and object removal by exemplar-based image inpainting. IEEE Transactions on Image Processing 13, 9, 1200–1212. Google ScholarDigital Library
12. Crow, F. C. 1984. Summed-area tables for texture mapping. ACM SIGGRAPH 18, 3, 207–212. Google ScholarDigital Library
13. Darabi, S., Shechtman, E., Barnes, C., Goldman, D. B., and Sen, P. 2012. Image melding: combining inconsistent images using patch-based synthesis. ACM Transactions on Graphics 31, 4, 82:1–82:12. Google ScholarDigital Library
14. Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. 2004. Locality-sensitive hashing scheme based on p-stable distributions. In ACM symp. on Computational geometry. Google ScholarDigital Library
15. Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In ACM SIGGRAPH, 341–346. Google ScholarDigital Library
16. Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. In IEEE ICCV, vol. 2. Google ScholarDigital Library
17. Farnebäck, G. 2003. Two-frame motion estimation based on polynomial expansion. In Image Analysis. Springer, 363–370. Google ScholarDigital Library
18. Felzenszwalb, P. F., and Huttenlocher, D. P. 2012. Distance transforms of sampled functions. Theory of computing 8, 1, 415–428.Google Scholar
19. Freeman, W. T., Jones, T. R., and Pasztor, E. C. 2002. Example-based super-resolution. IEEE Computer Graphics and Applications 22, 2, 56–65. Google ScholarDigital Library
20. HaCohen, Y., Shechtman, E., Goldman, D. B., and Lischinski, D. 2013. Optimizing color consistency in photo collections. ACM Transactions on Graphics 32, 4, 38:1–38:10. Google ScholarDigital Library
21. Hashimoto, R., Johan, H., and Nishita, T. 2003. Creating various styles of animations using example-based filtering. In IEEE Computer Graphics International, 312–317.Google Scholar
22. He, K., and Sun, J. 2012. Computing nearest-neighbor fields via propagation-assisted kd-trees. In IEEE CVPR, 111–118. Google ScholarDigital Library
23. Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. H. 2001. Image analogies. In Proc. ACM SIGGRAPH. Google ScholarDigital Library
24. Hu, S.-M., Zhang, F.-L., Wang, M., Martin, R. R., and Wang, J. 2013. PatchNet: a patch-based image representation for interactive library-driven image editing. ACM Transactions on Graphics 32, 6, 196:1–196:11. Google ScholarDigital Library
25. Hwang, Y., Han, B., and Ahn, H.-K. 2012. A fast nearest neighbor search algorithm by nonlinear embedding. In IEEE CVPR, 3053–3060. Google ScholarDigital Library
26. Jegou, H., Douze, M., and Schmid, C. 2011. Product quantization for nearest neighbor search. IEEE TPAMI 33, 1. Google ScholarDigital Library
27. Kalantari, N. K., Shechtman, E., Barnes, C., Darabi, S., Goldman, D. B., and Sen, P. 2013. Patch-based high dynamic range video. ACM Transactions on Graphics 32, 6, 202:1–202:11. Google ScholarDigital Library
28. Kopf, J., Fu, C.-W., Cohen-Or, D., Deussen, O., Lischinski, D., and Wong, T.-T. 2007. Solid texture synthesis from 2d exemplars. ACM Transactions on Graphics 26, 3, 2:1–2:9. Google ScholarDigital Library
29. Korman, S., and Avidan, S. 2011. Coherency sensitive hashing. In IEEE ICCV. Google ScholarDigital Library
30. Kung, H.-T., Luccio, F., and Preparata, F. P. 1975. On finding the maxima of a set of vectors. Journal of the ACM 22. Google ScholarDigital Library
31. Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM Transactions on Graphics 24, 3, 777–786. Google ScholarDigital Library
32. Lefebvre, S., and Hoppe, H. 2006. Appearance-space texture synthesis. 541–548.Google Scholar
33. Maurer, C. R., Qi, R., and Raghavan, V. 2003. A linear time algorithm for computing exact euclidean distance transforms of binary images in arbitrary dimensions. IEEE TPAMI 25, 2, 265–270. Google ScholarDigital Library
34. Muja, M., and Lowe, D. G. 2009. Fast approximate nearest neighbors with automatic algorithm configuration. In VISAPP(1), 331–340.Google Scholar
35. Olonetsky, I., and Avidan, S. 2012. TreeCANN-kd tree coherence approximate nearest neighbor algorithm. In ECCV. Springer, 602–615. Google ScholarDigital Library
36. Ragnemalm, I. 1992. Neighborhoods for distance transformations using ordered propagation. CVGIP 56, 3, 399–409. Google ScholarDigital Library
37. Rosenfeld, A., and Pfaltz, J. L. 1966. Sequential operations in digital picture processing. Journal of the ACM 13, 4, 471–494. Google ScholarDigital Library
38. Ruiters, R., Schwartz, C., and Klein, R. 2013. Example-based interpolation and synthesis of bidirectional texture functions. In Computer Graphics Forum, vol. 32, 361–370.Google ScholarCross Ref
39. Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In IEEE CVPR, 1–8.Google Scholar
40. Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., and Shum, H.-Y. 2002. Synthesis of bidirectional texture functions on arbitrary surfaces. ACM Transactions on Graphics 21, 3, 665–672. Google ScholarDigital Library
41. Wang, M., Liang, Y.-K. L. Y., Martin, R. R., and Hu, S.-M. 2014. BiggerPicture: data-driven image extrapolation using graph matching. ACM Transactions on Graphics 33, 6, 173:1–173:12. Google ScholarDigital Library
42. Wexler, Y., Shechtman, E., and Irani, M. 2007. Space-time completion of video. IEEE TPAMI 29, 3, 463–476. Google ScholarDigital Library
43. Xiao, C., Liu, M., Yongwei, N., and Dong, Z. 2011. Fast exact nearest patch matching for patch-based image editing and processing. IEEE TVCG 17, 8. Google ScholarDigital Library
44. Zhu, J.-Y., Lee, Y. J., and Efros, A. A. 2014. AverageExplorer: Interactive exploration and alignment of visual data collections. ACM Transactions on Graphics 33, 4, 160:1–160:11. Google ScholarDigital Library
