PatchMatch: a randomized correspondence algorithm for structural image editing
PatchMatch: a randomized correspondence algorithm for structural image editing
复制标题
DOI：
10.1145/1576246.1531330
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
Connelly Barnes;Eli Shechtman;Adam Finkelstein;Dan B. Goldman
中科院分区：
文献类型：
--
作者：
Connelly Barnes;Eli Shechtman;Adam Finkelstein;Dan B. Goldman
本文提出了一种交互式图像编辑工具，该工具使用一种新的随机化算法来快速找到图像块之间的近似最近邻匹配。图形和视觉方面的先前研究已经利用这种最近邻搜索来提供各种高级数字图像编辑工具。然而，为整个图像计算一组这样的匹配项的成本一直未能实现之前提供交互性能的努力。我们的算法比以前的技术状态(20-100倍)提供了实质性的性能改进，使其能够在交互式编辑工具中使用。推动该算法的关键见解是，通过随机采样可以找到一些好的斑块匹配，并且图像中的自然一致性允许我们将此类匹配快速传播到周围地区。我们对该算法的收敛性质进行了理论分析，并对其高质量和高性能提供了经验和实际证据。这个简单的算法构成了各种工具的基础--图像重定目标、完成和重新洗牌--这些工具可以在高级图像编辑应用程序的上下文中一起使用。最后，我们对合成过程提出了额外的直观约束，为用户提供了以前方法所不具备的控制水平。
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.