research-article

Open access

PatchMatch: a randomized correspondence algorithm for structural image editing

Authors:

Connelly Barnes,

Adam Finkelstein,

Dan B GoldmanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 28, Issue 3

Article No.: 24, Pages 1 - 11

https://doi.org/10.1145/1531326.1531330

Published: 27 July 2009 Publication History

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.

Supplementary Material

Zip (24-597.zip)

Download
43.61 MB

MP4 File (tps024_09.mp4)

Download
74.12 MB

References

[1]

Ashikhmin, M. 2001. Synthesizing natural textures. In I3D '06 Proc., ACM, 217--226.

Digital Library

[2]

Avidan, S., and Shamir, A. 2007. Seam carving for content-aware image resizing. ACM SIGGRAPH 26, 3, 10.

Digital Library

[3]

Buades, A., Coll, B., and Morel, J. M. 2005. A non-local algorithm for image denoising. In CVPR, vol. 2, 60--65.

Digital Library

[4]

Cho, T. S., Butman, M., Avidan, S., and Freeman, W. 2008. The patch transform and its applications to image editing. CVPR.

[5]

Criminisi, A., P&#233;rez, P., and Toyama, K. 2003. Object removal by exemplar-based inpainting. CVPR 2, 721.

[6]

Drori, I., Cohen-Or, D., and Yeshurun, H. 2003. Fragment-based image completion. ACM SIGGRAPH 22, 303--312.

Digital Library

[7]

Efros, A. A., and Freeman, W. T. 2001. Image quilting for texture synthesis and transfer. In ACM SIGGRAPH, ACM, 341--346.

Digital Library

[8]

Efros, A. A., and Leung, T. K. 1999. Texture synthesis by non-parametric sampling. ICCV 2, 1033.

Digital Library

[9]

Fang, H., and Hart, J. C. 2007. Detail preserving shape deformation in image editing. ACM Trans. Graphics 26, 3, 12.

Digital Library

[10]

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.

Digital Library

[11]

Fitzgibbon, A., Wexler, Y., and Zisserman, A. 2003. Image-based rendering using image-based priors. In ICCV, 1176.

Digital Library

[12]

Freeman, W., Jones, T., and Pasztor, E. 2002. Example-based super-resolution. Computer Graphics and Applications, IEEE 22, 2, 56--65.

Digital Library

[13]

Hertzmann, A., Jacobs, C. E., Oliver, N., Curless, B., and Salesin, D. 2001. Image analogies. In ACM SIGGRAPH, 327--340.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

Digital Library

[17]

Kwatra, V., Sch&#246;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.

Digital Library

[18]

Kwatra, V., Essa, I., Bobick, A., and Kwatra, N. 2005. Texture optimization for example-based synthesis. ACM SIGGRAPH 24.

Digital Library

[19]

Lefebvre, S., and Hoppe, H. 2005. Parallel controllable texture synthesis. ACM SIGGRAPH 24, 3, 777--786.

Digital Library

[20]

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.

Digital Library

[21]

Liu, F., and Gleicher, M. 2005. Automatic image retargeting with fisheye-view warping. In UIST, ACM, 153--162.

Digital Library

[22]

Mount, D. M., and Arya, S., 1997. ANN: A library for approximate nearest neighbor searching, Oct. 28.

[23]

Pavic, D., Schonefeld, V., and Kobbelt, L. 2006. Interactive image completion with perspective correction. The Visual Computer 22 (September), 671--681(11).

Digital Library

[24]

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.

Digital Library

[25]

Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A. 2006. Autocollage. ACM SIGGRAPH 25, 3, 847--852.

Digital Library

[26]

Rubinstein, M., Shamir, A., and Avidan, S. 2008. Improved seam carving for video retargeting. ACM SIGGRAPH 27, 3.

Digital Library

[27]

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.

Digital Library

[28]

Simakov, D., Caspi, Y., Shechtman, E., and Irani, M. 2008. Summarizing visual data using bidirectional similarity. In CVPR.

[29]

Sun, J., Yuan, L., Jia, J., and Shum, H.-Y. 2005. Image completion with structure propagation. In ACM SIGGRAPH, 861--868.

Digital Library

[30]

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.

Digital Library

[31]

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.

Digital Library

[32]

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.

Digital Library

[33]

Wei, L. Y., and Levoy, M. 2000. Fast texture synthesis using tree-structured vector quantization. In ACM SIGGRAPH, 479--488.

Digital Library

[34]

Wei, L.-Y., Han, J., Zhou, K., Bao, H., Guo, B., and Shum, H.-Y. 2008. Inverse texture synthesis. ACM SIGGRAPH 27, 3.

Digital Library

[35]

Wexler, Y., Shechtman, E., and Irani, M. 2007. Space-time completion of video. IEEE Trans. PAMI 29, 3 (March), 463--476.

Digital Library

[36]

Wolf, L., Guttmann, M., and Cohen-Or, D. 2007. Non-homogeneous content-driven video-retargeting. In ICCV.

Cited By

Ji Xunsheng 吉Zhu Yin 朱Yang Jielong 杨(2025)基于多尺度S-密度策略的三维重建方法Laser & Optoelectronics Progress10.3788/LOP24137262:4(0411002)Online publication date: 2025
https://doi.org/10.3788/LOP241372
Xu YXia MHu KZhou SWeng L(2025)Style Transfer Review: Traditional Machine Learning to Deep LearningInformation10.3390/info1602015716:2(157)Online publication date: 19-Feb-2025
https://doi.org/10.3390/info16020157
Yeo WRyu H(2025)An Integration Framework for the Inpainting and Colorization of Arbitrary Masked Grayscale ImagesApplied Sciences10.3390/app1504197815:4(1978)Online publication date: 13-Feb-2025
https://doi.org/10.3390/app15041978
Show More Cited By

Index Terms

PatchMatch: a randomized correspondence algorithm for structural image editing
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision tasks
  2. Computer graphics

Recommendations

PatchMatch: a randomized correspondence algorithm for structural image editing
SIGGRAPH '09: ACM SIGGRAPH 2009 papers

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 ...
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
Seminal Graphics Papers: Pushing the Boundaries, Volume 2

This 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

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 28, Issue 3

August 2009

750 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/1531326

Issue’s Table of Contents

Seminal Graphics Papers: Pushing the Boundaries, Volume 2
August 2023
893 pages
ISBN:9798400708978
DOI:10.1145/3596711
Editor:
Mary C. Whitton
Department of Computer Science, UNC Chapel Hill, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 2009

Published in TOG Volume 28, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Seminal Paper

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Information and Intelligent Systems

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2,022
Total Citations
View Citations
8,858
Total Downloads

Downloads (Last 12 months)872
Downloads (Last 6 weeks)92

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ji Xunsheng 吉Zhu Yin 朱Yang Jielong 杨(2025)基于多尺度S-密度策略的三维重建方法Laser & Optoelectronics Progress10.3788/LOP24137262:4(0411002)Online publication date: 2025
https://doi.org/10.3788/LOP241372
Xu YXia MHu KZhou SWeng L(2025)Style Transfer Review: Traditional Machine Learning to Deep LearningInformation10.3390/info1602015716:2(157)Online publication date: 19-Feb-2025
https://doi.org/10.3390/info16020157
Yeo WRyu H(2025)An Integration Framework for the Inpainting and Colorization of Arbitrary Masked Grayscale ImagesApplied Sciences10.3390/app1504197815:4(1978)Online publication date: 13-Feb-2025
https://doi.org/10.3390/app15041978
Jia MHu JYang ZLiu WQi JChen B(2025)Automatic Restoration of Dunhuang Murals and Process Visualization Method Based on Deep LearningApplied Sciences10.3390/app1503142215:3(1422)Online publication date: 30-Jan-2025
https://doi.org/10.3390/app15031422
Zhao RZhang YWang TWen WXiang YCao X(2025)Visual Content Privacy Protection: A SurveyACM Computing Surveys10.1145/370850157:5(1-36)Online publication date: 24-Jan-2025
https://dl.acm.org/doi/10.1145/3708501
ren cxu y(2025)Based on structure and texture dual-stream network for ancient mural restorationFifth International Conference on Signal Processing and Computer Science (SPCS 2024)10.1117/12.3052938(19)Online publication date: 3-Jan-2025
https://doi.org/10.1117/12.3052938
Huang LHuang YGuan Q(2025)Improving Image Inpainting via Adversarial Collaborative TrainingIEEE Transactions on Multimedia10.1109/TMM.2024.352180027(356-370)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TMM.2024.3521800
Li YHe YChen CDong LLi BZhou JLi X(2025)Image Copy-Move Forgery Detection via Deep PatchMatch and Pairwise Ranking LearningIEEE Transactions on Image Processing10.1109/TIP.2024.348219134(425-440)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TIP.2024.3482191
Wu CHuang ZHuang NFu CLiao YCao QZhang GPeng HDing ZFu ZLiu YXiong XCai S(2025)LF-MVS: Line Features-Assisted PatchMatch Multiview StereoIEEE Transactions on Instrumentation and Measurement10.1109/TIM.2025.352749074(1-13)Online publication date: 2025
https://doi.org/10.1109/TIM.2025.3527490
Yao YHan TJia SLyu S(2025)Dense Feature Interaction Network for Image Inpainting LocalizationIEEE Transactions on Information Forensics and Security10.1109/TIFS.2025.353110320(1636-1648)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TIFS.2025.3531103
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents