Connelly Barnes
Dan B Goldman
Abstract
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.
Supplemental Material
Available for Download
- Ashikhmin, M. 2001. Synthesizing natural textures. In I3D '06 Proc., ACM, 217--226. Google Scholar
Digital Library
- Avidan, S., and Shamir, A. 2007. Seam carving for content-aware image resizing. ACM SIGGRAPH 26, 3, 10. Google ScholarDigital Library
- Buades, A., Coll, B., and Morel, J. M. 2005. A non-local algorithm for image denoising. In CVPR, vol. 2, 60--65. Google ScholarDigital Library
- Cho, T. S., Butman, M., Avidan, S., and Freeman, W. 2008. The patch transform and its applications to image editing. CVPR.Google Scholar
- Criminisi, A., Pérez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 2, 721.Google Scholar
- Drori, I., Cohen-Or, D., and Yeshurun, H. 2003. Fragment-based image completion. ACM SIGGRAPH 22, 303--312. Google ScholarDigital Library
- Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In ACM SIGGRAPH, ACM, 341--346. Google ScholarDigital Library
- Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. ICCV 2, 1033. Google ScholarDigital Library
- Fang, H., and Hart, J. C. 2007. Detail preserving shape deformation in image editing. ACM Trans. Graphics 26, 3, 12. Google ScholarDigital Library
- Fischler, M. A., and Bolles, R. C. 1981. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Commun. ACM 24, 6, 381--395. Google ScholarDigital Library
- Fitzgibbon, A., Wexler, Y., and Zisserman, A. 2003. Image-based rendering using image-based priors. In ICCV, 1176. Google ScholarDigital Library
- Freeman, W., Jones, T., and Pasztor, E. 2002. Example-based super-resolution. Computer Graphics and Applications, IEEE 22, 2, 56--65. Google ScholarDigital Library
- Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. 2001. Image analogies. In ACM SIGGRAPH, 327--340. Google ScholarDigital Library
- Komodakis, N., and Tziritas, G. 2007. Image completion using efficient belief propagation via priority scheduling and dynamic pruning. IEEE Transactions on Image Processing 16, 11, 2649--2661. Google ScholarDigital Library
- Kopf, J., Fu, C.-W., Cohen-Or, D., Deussen, O., Lischinski, D., and Wong, T.-T. 2007. Solid texture synthesis from 2d exemplars. ACM SIGGRAPH 26, 3, 2:1--2:9. Google ScholarDigital Library
- Kumar, N., Zhang, L., and Nayar, S. K. 2008. What is a good nearest neighbors algorithm for finding similar patches in images? In European Conference on Computer Vision (ECCV), II: 364--378. Google ScholarDigital Library
- Kwatra, V., Schödl, A., Essa, I., Turk, G., and Bobick, A. 2003. Graphcut textures: Image and video synthesis using graph cuts. ACM SIGGRAPH 22, 3 (July), 277--286. Google ScholarDigital Library
- Kwatra, V., Essa, I., Bobick, A., and Kwatra, N. 2005. Texture optimization for example-based synthesis. ACM SIGGRAPH 24. Google ScholarDigital Library
- Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM SIGGRAPH 24, 3, 777--786. Google ScholarDigital Library
- Liang, L., Liu, C., Xu, Y.-Q., Guo, B., and Shum, H.-Y. 2001. Real-time texture synthesis by patch-based sampling. ACM Trans. Graphics 20, 3, 127--150. Google ScholarDigital Library
- Liu, F., and Gleicher, M. 2005. Automatic image retargeting with fisheye-view warping. In UIST, ACM, 153--162. Google ScholarDigital Library
- Mount, D. M., and Arya, S., 1997. ANN: A library for approximate nearest neighbor searching, Oct. 28.Google Scholar
- Pavic, D., Schonefeld, V., and Kobbelt, L. 2006. Interactive image completion with perspective correction. The Visual Computer 22 (September), 671--681(11). Google ScholarDigital Library
- Rong, G., and Tan, T.-S. 2006. Jump flooding in GPU with applications to Voronoi diagram and distance transform. In I3D '06 Proc., 109--116. Google ScholarDigital Library
- Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. ACM SIGGRAPH 25, 3, 847--852. Google ScholarDigital Library
- Rubinstein, M., Shamir, A., and Avidan, S. 2008. Improved seam carving for video retargeting. ACM SIGGRAPH 27, 3. Google ScholarDigital Library
- Setlur, V., Takagi, S., Raskar, R., Gleicher, M., and Gooch, B. 2005. Automatic image retargeting. In MUM, ACM, M. Billinghurst, Ed., vol. 154 of ACM International Conference Proc. Series, 59--68. Google ScholarDigital Library
- Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In CVPR.Google Scholar
- Sun, J., Yuan, L., Jia, J., and Shum, H.-Y. 2005. Image completion with structure propagation. In ACM SIGGRAPH, 861--868. Google ScholarDigital Library
- Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., and Rother, C. 2008. A comparative study of energy minimization methods for markov random fields with smoothness-based priors. IEEE PAMI 30, 6, 1068--1080. Google ScholarDigital Library
- Tong, X., Zhang, J., Liu, L., Wang, X., Guo, B., and Shum, H.-Y. 2002. Synthesis of bidirectional texture functions on arbitrary surfaces. ACM SIGGRAPH 21, 3 (July), 665--672. Google ScholarDigital Library
- Wang, Y.-S., Tai, C.-L., Sorkine, O., and Lee, T.-Y. 2008. Optimized scale-and-stretch for image resizing. In ACM SIGGRAPH Asia, ACM, New York, NY, USA, 1--8. Google ScholarDigital Library
- Wei, L. Y., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In ACM SIGGRAPH, 479--488. Google ScholarDigital Library
- Wei, L.-Y., Han, J., Zhou, K., Bao, H., Guo, B., and Shum, H.-Y. 2008. Inverse texture synthesis. ACM SIGGRAPH 27, 3. Google ScholarDigital Library
- Wexler, Y., Shechtman, E., and Irani, M. 2007. Space-time completion of video. IEEE Trans. PAMI 29, 3 (March), 463--476. Google ScholarDigital Library
- Wolf, L., Guttmann, M., and Cohen-Or, D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV.Google Scholar
Index Terms
- PatchMatch: a randomized correspondence algorithm for structural image editing
Recommendations
PatchMatch: a randomized correspondence algorithm for structural image editing
SIGGRAPH '09: ACM SIGGRAPH 2009 papersThis 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 ...
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
Seminal Graphics Papers: Pushing the Boundaries, Volume 2This paper presents interactive image editing tools using a new randomized algorithm for quickly finding approximate nearestneighbor matches between image patches. Previous research in graphics and vision has leveraged such nearest-neighbor searches to ...
Artist friendly facial animation retargeting
This paper presents a novel facial animation retargeting system that is carefully designed to support the animator's workflow. Observation and analysis of the animators' often preferred process of key-frame animation with blendshape models informed our ...
Comments