C++实现PatchMatch图像修复算法
PatchMatch算法出自Barnes的论文
PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing
PatchMatch 算法就是一个找近似最近邻(Approximate Nearest neigbhor)的方法,要比其他ANN算法快上10倍+。
将下面的图理解了,就基本理解了整个算法。
看上图时,我们以蓝色为主颜色。A代表原图像,矩形框代表待修复的patch块,要修复patch_A块就需要在B(也是原图)中搜索一个最合适的块patch_B,而从patch_A到patch_B的偏移量,就是上图箭头,也就是offset。
蓝色为主patch块,红色是蓝色向左移一个像素,绿色是蓝色向上移一个像素。
上图 (a):随机初始化 (b):传播 ©:随机扰动搜索
PatchMatch 的核心思想是利用图像的连续性(consistence), 一个图像A的patch_A(蓝色)附近的Patch块(红色绿色)的最近邻(B中的红色绿色框)最有可能出现在Patch_A的最近邻(B中的蓝色框)附近,利用这种图像的连续性大量减少搜索的范围,通过迭代的方式保证大多数点能尽快收敛。
PatchMatch算法是对所有待修复像素迭代修复的,而不是像Criminisi或FMM算法对待修复区域像素优先级排序后进行渐进修复的。
来看算法步骤:
首先是建立图像的下采样金字塔模型,代码中设定为五层,建立模型后
对A的待修复区域每个patch块随机在B已知区域中匹配一个patch块,即初始化偏置地图(上图a步骤)。
/********************************* 函数声明:初始化偏置图像 参数:NONE 注释:NONE 测试:NONE **********************************/ void PatchMatch::InitOff(Mat Mask, Mat &Off) { //为方便起见,将所有的都附上,要求不能赋值到非搜索区域 //初始化格式 Off = Mat(Mask.size(), CV_32FC2, Scalar::all(0));//2维无符号32位精度浮点数 for (int i = 0; i < Mask.rows; i++) { for (int j = 0; j < Mask.cols; j++) { //不考虑search区域,没有破损,他们的最佳偏移向量当然是0,自己 if (Mask.at<uchar>(i, j) == search) { Off.at<Vec2f>(i, j)[0] = 0; //<Vec2f> 向量,2维,浮点数 Off.at<Vec2f>(i, j)[1] = 0; } else//处理hole,采用随机偏置 { //先初始化2个偏置数r_col,r_row int r_col = rand() % Mask.cols; //rand()产生随机数,主要是产生一个偏置的初始值 int r_row = rand() % Mask.rows; r_col = r_col + j < Mask.cols ? r_col : r_col - Mask.cols;//边界检测 r_row = r_row + i < Mask.rows ? r_row : r_row - Mask.rows; //为什么要有这个循环?因为一次的随机赋值,很可能会出现偏置后的块跑到破损区域,或者是超出限定搜索框的边界 while ( !(Mask.at<uchar>(r_row + i, r_col + j) == search //这里加上I,j,是因为他是A投影到B中的搜索偏置 && abs(r_row) < searchrowratio*Mask.rows)) //searchrowratio=0.5,搜索的时候,确保r_row偏置不会太远,一定是在原图像的大小里 { r_col = rand() % Mask.cols; r_row = rand() % Mask.rows; //边界检测 r_col = r_col + j < Mask.cols ? r_col : r_col - Mask.cols; r_row = r_row + i < Mask.rows ? r_row : r_row - Mask.rows; } //赋偏置值 Off.at<Vec2f>(i, j)[0] = r_row; Off.at<Vec2f>(i, j)[1] = r_col; } } } }
之后从低分辨率开始,对于每一层金字塔模型进行迭代:
每一次迭代都会遍历原图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块。
计算相似度函数为
//以块为单位,用所有像素点的相同颜色通道的差平方来简单判断相似度 float PatchMatch::Distance(Mat Dst, Mat Src) { float distance = 0; for (int i = 0; i < Dst.rows; i++) { for (int j = 0; j < Dst.cols; j++) { for (int k = 0; k < 3; k++)//K=3个颜色通道 { int tem = Src.at < Vec3b >(i, j)[k] - Dst.at < Vec3b >(i, j)[k]; distance += tem * tem;//差平方 } } } return distance; }
传播函数:
//迭代第一步:传播 //(now_row, now_col):patch里的像素 //odd:当前迭代次 void PatchMatch::Propagation(Mat Dst, Mat Src, Mat Mask, Mat &Off, int row, int col,int odd) { Mat DstPatch = GetPatch(Dst, row, col);//获取长度为 patchsize = 3 的边界框, (row, col)代表的是中心像素点坐标 if (odd % 2 == 0)//偶次迭代 { //提取(row, col)的match块 Mat SrcPatch = GetPatch(Src, row + Off.at < Vec2f >(row, col)[0], col + Off.at < Vec2f >(row, col)[1]); //提取(row, col-1)的match块 Mat LSrcPatch = GetPatch(Src, row + Off.at < Vec2f >(row, col - 1)[0], col - 1 + Off.at < Vec2f >(row, col - 1)[1]); //提取(row-1, col)的match块 Mat USrcPatch = GetPatch(Src, row - 1 + Off.at < Vec2f >(row - 1, col)[0], col + Off.at < Vec2f >(row - 1, col)[1]); //返回上面4个块最相似的块的代表数字,用于switch判断 int location = GetMinPatch1(DstPatch, SrcPatch, LSrcPatch, USrcPatch); //利用上面的信息更新像素点的偏置地图 switch (location) { //若是1则不更新 case 2: Off.at < Vec2f >(row, col)[0] = Off.at < Vec2f >(row, col - 1)[0]; Off.at < Vec2f >(row, col)[1] = Off.at < Vec2f >(row, col - 1)[1] - 1; break; case 3: Off.at < Vec2f >(row, col)[0] = Off.at < Vec2f >(row - 1, col)[0] - 1; Off.at < Vec2f >(row, col)[1] = Off.at < Vec2f >(row - 1, col)[1]; break; } } else//奇数次迭代 { Mat SrcPatch = GetPatch(Src, row + Off.at < Vec2f >(row, col)[0], col + Off.at < Vec2f >(row, col)[1]); Mat RSrcPatch = GetPatch(Src, row + Off.at < Vec2f >(row, col + 1)[0], col + 1 + Off.at < Vec2f >(row, col + 1)[1]); Mat DSrcPatch = GetPatch(Src, row + 1 + Off.at < Vec2f >(row + 1, col)[0], col + Off.at < Vec2f >(row + 1, col)[1]); int location = GetMinPatch1(DstPatch, SrcPatch, RSrcPatch, DSrcPatch); switch (location) { case 2: Off.at < Vec2f >(row, col)[0] = Off.at < Vec2f >(row, col + 1)[0]; Off.at < Vec2f >(row, col)[1] = Off.at < Vec2f >(row, col + 1)[1] + 1; break; case 3: Off.at < Vec2f >(row, col)[0] = Off.at < Vec2f >(row + 1, col)[0] + 1; Off.at < Vec2f >(row, col)[1] = Off.at < Vec2f >(row + 1, col)[1]; break; } } }
步骤二:随机扰动搜索(图中c步骤)
为了避免陷入局部极值,再额外再随机生成几个patch位置作为候选patch块,若小于当前patch,则更新。
随机扰动会在原图A中,以当前像素为中心点,初始半径区域为全图,在此区域内随机找寻patch块并与patch_A原本对应的B中的patch块对比,若更相似则更新对应关系offset,然后以新的patch_B为中心,半径缩小一倍,继续搜索,直到半径缩小为1,更新完毕。
//迭代第二步:随机搜索 //(row,col)=(now_row, now_col):修复patch里的像素 void PatchMatch::RandomSearch(Mat Dst, Mat Src, Mat Mask, Mat &Off, int row, int col) { Mat DstPatch = GetPatch(Dst, row, col);//获取修复基准框,在框内操作 //迭代指数 int attenuate = 0; while (true) { //获取随机参数,在 [-1;1] 间 float divcol = rand() % 2000 / 1000.0f - 1.0f; float divrow = rand() % 2000 / 1000.0f - 1.0f; //减小框大小的公式,𝑢_𝑖=𝑣_0+𝑤*𝛼^𝑖*𝑅_𝑖 //行列分别处理,MaxWindow:原始框宽度;divcol:随机系数;pow(A,B):A的B次方。随迭代次数而变小的缩小系数;RandomAttenuation=0.5; float veccol = MaxWindow * pow(RandomAttenuation, attenuate)* divcol; float vecrow = MaxWindow * pow(RandomAttenuation, attenuate)* divrow; float length = sqrt(veccol * veccol + vecrow * vecrow); //如果低于1个像素,没有意义,直接结束整个循环,对下一个像素处理 if (length < 1) break; //x方向,前2项指向(row, col)的match块,后面是公式的后一项 int nowrow = row + Off.at < Vec2f >(row, col)[0] + vecrow; //y方向 int nowcol = col + Off.at < Vec2f >(row, col)[1] + veccol; //判断随机搜索的patch不越界,在search内 if (nowcol >= 0 && nowcol <= Off.cols - 1 && nowrow >= 0 && nowrow <= Off.rows - 1 && Mask.at < uchar >(nowrow, nowcol) == search && abs(nowrow - row) < searchrowratio * Mask.rows)//abs:绝对值 { //取出原来的match块 Mat SrcPatch1 = GetPatch(Src, Off.at < Vec2f >(row, col)[0] + row, Off.at < Vec2f >(row, col)[1] + col); //取出现在的随机match块 Mat SrcPatch2 = GetPatch(Src, nowrow, nowcol); //对比相似性,找出最好的块 int location = GetMinPatch2(DstPatch, SrcPatch1, SrcPatch2); //结合最好的相似块给像素新的偏置值 switch (location) { case 2: Off.at < Vec2f >(row, col)[1] = nowcol - col; Off.at < Vec2f >(row, col)[0] = nowrow - row; break; } } //迭代指数增加 attenuate++; } }
经过该两个步骤,本次迭代完毕。
当最终迭代完成后,就完成了整个修复过程。
算法效果
可以看到效果还是可以的,速度也比较快。
到此这篇关于C++实现PatchMatch图像修复算法的文章就介绍到这了,更多相关C++ PatchMatch图像修复算法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 作者:Sabine 【导读】本文介绍了C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序 冒泡排序 using System; namespace BubbleSorter { public class Bubb...2020-06-25
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25