图像修复算法PatchMatch的研究与优化

这个东西是个非常古老的算法了，大概是2008年的东西，参考资料也有很多，不过基本上都是重复的。最近受一个朋友的需求，前后大概用了二十多天时间去研究，也有所成果，在这里简单的予以记录。

图像修复这个东西目前流行的基本都是用深度学习来弄了，而且深度学习的效果还是非常不错的（大部分情况下优于传统算法）。

PatchMatch本身并不是图像修复的算法，他只是描述了一套流程用于快速在两幅图之间找到近似的相似的块，主要包括随机初始化，然后传播，再随机搜索三个步骤，关于这部分描述可以直接看论文或者在百度上搜索PatchMatch，有一大堆相关的解释，我这里不想过多描述。

关于这个论文，大家可以搜索文章： PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing

而图像修复本身的过程除了PatchMatch外，还有很多其他的东西。一般情况下，这种应用场景都是客户手工指定一个区域，我们需要把这个区域的东西去掉并填充（不管原来这里是什么样子的，区域内部原有的信息完全不考虑），填充后的结果要和周边的环境自然的融为一体。关于这方面的步骤，论文里本身描述的不多，但是相关的代码可以在github上找到很多，我这里提供几个链接供大家参考：

https://github.com/vacancy/PyPatchMatch

https://github.com/liqing7/Inpaint/tree/master/Inpaint

github里一堆这样的代码，但是翻来翻去其实都是一个娘生的，里面的实现方式大同小异，而且基本上都是基于opencv实现的，里面的代码呢也是绕来绕去，重实现，不重流程和效率。我的工程也是参考了这些东西，并且使用C++脱离opencv独立予以实现，因此工作量大了很多。

我这里就我在提取并稍作优化这个算法的一些过程予以记录和描述，免得时间久了后自己都不太记得是怎么回事了。

一、Inpaint的基本流程。

1、用户标记的区域视为孔洞，里面没有任何的信息了，那要从现有的周边像素填充这个孔洞，采用的办法是，建立图像金字塔，在金字塔下采样的过程中，图像变小，孔洞也在变小，下采样就涉及到领域，当领域覆盖了孔洞边缘时，也必然有部分领域涉及到了孔洞周边的有效像素区域，此时以有效像素区域的信息加权填充缩小后的孔洞，这样不断的侵蚀，直到所有的孔洞在金字塔图像中都消失了，这个金字塔的层数就足够了（不管孔洞有多大，当金字塔在变为大小2像素、1像素的过程中孔洞肯定会消失）。

2、由最小的金字塔层开始，目标和源都设置为相同值，然后随机初始化PatchMatch里的NNF场，接着使用传播和随机扩散最小化NNF的误差，这个时候就可以利用这个NNF来初步构建目标图像（是个迭代过程，叫做EM迭代）。

3、在迭代的最后一步，做个上采样，并且做点精细化的工作（权重累加），然后到金字塔的上一层，在这一层时，初始的NNF就不要随机化了，而是可以有下一层的NNF通过最近邻插值获取，这样获取的数据比随机初始化的要更为接近理论的结果，就要就可以减少这一层的传播和随机扩散的迭代次数。

4、就这样一层一层的往上处理，得到最终的结果。

二、参考代码中一些细节

1、删除不必要的过程

我们贴一下论文里的一些描述先：