在寻找低秩图像补全方案中遇到的patchmatch算法

参考文献：PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing

正如题目所说--A Randomized Correspondence Algorithm for Structural Image Editing ，重点在于其随机特性。

这种A和B的图像匹配来源于最初的Nearest-Neighbor Field (NNF) ，通过某种尺度找到A中每一个patch对应的B的最近邻patch。（如下图）

Region Filling and Object Removal by Exemplar-Based Image Inpainting 该论文是04年一篇图像补全的论文，此论文的核心思想是利用图像本身的冗余性。

该算法的问题是1.只适用于补全背景以低频信息和重复性纹理为主的图像，2.搜索相似的patch计算复杂度非常高，算法运行效率低。

patchmatch的作者通过观察发现了原有补全的三个重要特性并提出了使用增量更新计算NNF的随机算法针对上述算法的问题2进行优化，三个特性如下：

1.由于offset space的大小由patch决定， 之前的研究中有很多学者利用类似于pca，kd-tree这样的策略去压缩offset space。本文的算法是在2-d 的offset space中计算的。（这个是我之后可以关心的）

2.利用匹配的图像的自然结构，利用相邻像素之间的依赖性。

3.按照概率，初始化的patch很多的情况下，那么其一个都没有命中正确对应patch的概率会很小。

 *****额外基础概念

reshuffle 图像重组

reshuffle将一张图片进行重新组合，如将人工按照想要的方式使得图像看起来更自然。

在寻找低秩图像补全方案中遇到的patchmatch算法

原文：https://www.cnblogs.com/yizhifanya/p/11811027.html