【工程应用十一】基于PatchMatch算法的图像修复研究（inpaint）。

  这个东西是个非常古老的算法了，大概是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、删除不必要的过程

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

    void init_kDistance2Similarity() {
        double base[11] = {1.0, 0.99, 0.96, 0.83, 0.38, 0.11, 0.02, 0.005, 0.0006, 0.0001, 0};
        int length = (PatchDistanceMetric::kDistanceScale + 1);
        kDistance2Similarity.resize(length);
        for (int i = 0; i < length; ++i) 
        {
            double t = (double) i / length;
            int j = (int) (100 * t);
            int k = j + 1;
            double vj = (j < 11) ? base[j] : 0;
            double vk = (k < 11) ? base[k] : 0;
            kDistance2Similarity[i] = 1;// vj + (100 * t - j) * (vk - vj);
        }
    }

   mptry[j] = (ptry1[j] / 2 - ptry2[j] / 2) + 128;
   mptrx[j] = (ptrx1[j] / 2 - ptrx2[j] / 2) + 128;