《PatchMatch：一种随机对应算法在结构图像编辑中的应用》
本文提出了一种新的随机算法——PatchMatch，用于快速寻找图像区域之间的近似最近邻匹配，从而实现互动式的图像编辑工具。这一算法解决了以往计算整个图像中匹配字段时性能瓶颈的问题，相比先前的技术，其性能提升了20到100倍，使得在实时编辑工具中应用成为可能。
PatchMatch算法的核心思想是通过随机采样找到一些良好的区域匹配，并利用图像内在的自然连贯性迅速传播这些匹配到周围区域。算法的收敛性质经过了理论分析，同时实验结果和实践证明了其高质量和高性能。这一简单算法不仅为图像重定向、完成和重新排列等多样工具提供了基础，而且在高级图像编辑应用中可以协同使用。
在结构图像编辑中，例如图1所示的案例，从左到右分别是原始图像、标记的洞口（用洋红色表示）以及用来改善屋顶线条连续性的线约束（红绿蓝），然后是洞口被填充，用户提供的线约束用于重定向，使用约束的重定向自动消除两列，最后是用户通过重新排列将屋顶向上移动。这些示例展示了PatchMatch算法如何在用户交互下有效地进行图像编辑。
PatchMatch算法的优势在于，它能够快速生成全局的匹配场，即使在复杂图像结构中也能保持良好的连续性和一致性。这极大地提高了编辑效率，用户可以在短时间内看到编辑效果，增强了编辑过程的即时反馈和用户体验。
此外，论文还提出了对合成过程的额外直观约束，让用户能够在编辑过程中拥有更高的控制水平，这是以往技术所无法提供的。这些约束可能包括颜色一致性、纹理平滑度或形状相似性等，使用户在编辑过程中可以根据自己的需求进行精细调整。
PatchMatch算法的出现，为图像处理和计算机视觉领域带来了革命性的改变，特别是在立体匹配和双目视觉应用中，它不仅提升了算法的运行速度，而且提高了编辑的精度和用户体验。通过结合用户提供的约束，它能够实现更加自然且符合预期的图像编辑结果，为数字图像编辑工具的发展开辟了新的道路。
