【手撕算法】PatchMatch图像修复算法C++实现

PatchMatch图像修复算法

PatchMatch算法出自Barnes的论文

PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing

PatchMatch 算法就是一个找近似最近邻（Approximate Nearest neigbhor)的方法，要比其他ANN算法快上10倍+。

将下面的图理解了，就基本理解了整个算法。

首先是建立图像的下采样金字塔模型，代码中设定为五层，建立模型后

对A的待修复区域每个patch块随机在B已知区域中匹配一个patch块，即初始化偏置地图（上图a步骤）。

之后从低分辨率开始，对于每一层金字塔模型进行迭代：

每一次迭代都会遍历原图A待修复区域所有像素。当遍历到当前像素时，执行下面的步骤来进行修复：

步骤一：传播（图中b步骤）

传播会计算原图A当前像素块patch_A（蓝色）对应的B中的patch_B_1，patch_A上方（绿色）（奇数次迭代为下方）对应的B中的patch_B_2，patch_A左侧（红色）（奇数次迭代为右侧）对应的B中的patch_B_3这三个patch块中与patch_A相似度最高的patch块。

计算相似度函数为

传播函数：

步骤二：随机扰动搜索（图中c步骤）

为了避免陷入局部极值，再额外再随机生成几个patch位置作为候选patch块，若小于当前patch，则更新。

随机扰动会在原图A中，以当前像素为中心点，初始半径区域为全图，在此区域内随机找寻patch块并与patch_A原本对应的B中的patch块对比，若更相似则更新对应关系offset，然后以新的patch_B为中心，半径缩小一倍，继续搜索，直到半径缩小为1，更新完毕。

经过该两个步骤，本次迭代完毕。

当最终迭代完成后，就完成了整个修复过程。

算法效果

可以看到效果还是可以的，速度也比较快。

THE END

立个小目标，做机器视觉算法与软件开发工程师~

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35168 人正在系统学习中