PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
ACM Transactions on Graphics (Proc. SIGGRAPH), August 2009

Connelly Barnes, Eli Shechtman, Adam Finkelstein,
Dan B Goldman

Structural image editing. Left to right: (a) the original image; (b) a hole is marked (magenta) and we use line constraints (red/green/blue) to improve the continuity of the roofline; (c) the hole is filled in; (d) user-supplied line constraints for retargeting; (e) retargeting using constraints eliminates two columns automatically; and (f) user translates the roof upward using reshuffling.

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.

Citation (BibTeX)

Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan B Goldman. PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. ACM Transactions on Graphics (Proc. SIGGRAPH). 28(3) August 2009.

Files
Paper (7 MB PDF)
Download Video (Long, 5 minutes) (46 MB MPEG-4)
Streaming Video (Short, 3 minutes)

Additional Links
Adobe Website

Photoshop CS5向用户展示了说服其升级的理由：Photoshop团队产品经理Bryan O’Neil-Hughes在演示视频中介绍了一个令人眼前一亮的新特性——内 容感知填充。

利用这项功能，用户可以很容易消除图像中的镜头光斑；把原本有零零碎碎垃圾的地面变成完美的草坪；从画面中移除一棵大树，让Photoshop 自动的替换上草和天空，使整个画面浑然一体。

强大的PS工具将让人无法区分什么是真实，什么又被修改过了。演示视频发表在Youtube，这项神奇功能背后的算法来自普林斯顿大学的计算机 科学家，他们在去年的SIGGRAPH上演示 了该功能。

查看： 论 文（PDF），视 频（MP4）