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图像修复算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现抢红包算法

    本文实例为大家分享了C语言实现抢红包的具体代码,供大家参考,具体内容如下 1.算法背景: 大家知道,微信拼手气红包和普通红包两种.普通红包每个人抢到的金额是固定的(总额的平均数),拼手气红包是随机金额(每个人抢到的是随机的,差别可能非常大,有的人抢到的是1分,有的抢到的可能是几元.十几元.几十元),目前的抢红包算法只能输入两个参数,即总金额.总人数. 2.算法要求: 现要求同学们设计一个改进的抢红包算法,可以设定总金额(total).总人数(num).抢到的最低金额(min)和最高金额(max)

  • C语言实现九大排序算法的实例代码

    直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分.从无序部分中依次取出元素插入到有序部分中.过程就是遍历有序部分,实现起来比较简单. #include <stdio.h> void insertion_sort(int arr[], int array_length) { for (int i = 0; i < array_length; ++i) { int data = arr[i]; int j = 0; while (arr[j] < arr[i]) { j

  • C++实现四叉树效果(附源码下载)

    什么是四叉树? 如图,设想, 红框表示地图,星星表示单位,黄框表现范围, 要处理地图中范围内的单位,最直接的做法是筛选所有单位. 通过上图可以看到一个显而易见的问题,大部分单位都不需要被处理. 如果把地图分成块,只筛选范围覆盖的块中的单位,这样就可以减少很多不必要的筛选. 四叉树可以有效解决这个问题. 树的每一层都把地图划分四块,根据地图尺寸来决定树的层数,层数越大划分越细. 当需要对某一范围的单位筛选时,只需要定位到与范围相交的树区域,再对其区域内的对象筛选即可. 四叉树的实现 #pragma

  • C语言实现页面置换算法

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时

  • 详解C语言实现空间索引四叉树

    前言 作为程序员,应该都对二叉树都不陌生,我们都知道二叉树的变体二叉查找树,非常适合用来进行对一维数列的存储和查找,可以达到 O(logn) 的效率:我们在用二叉查找树进行插入数据时,根据一个数据的值和树结点值的对比,选择二叉树的两个叉之一向下,直到叶子结点,查找时使用二分法也可以迅速找到需要的数据. 但二叉树只支持一维数据,如一个标量数值,对地图上的位置点这种有xy两个方向上的信息却无能为力,那么是否有一种树能够支持二维数据的快速查询呢? 四叉树 介绍 四元树又称四叉树是一种树状数据结构,在每

  • C++迷宫问题的求解算法

    本文实例为大家分享了C++实现迷宫的具体代码,供大家参考,具体内容如下 一. 实验目的: (1) 熟练掌握链栈的基本操作及应用. (2) 利用链表作为栈的存储结构,设计实现一个求解迷宫的非递归程序. 二.实验内容: [问题描述] 以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍.设计一个程序,对信任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. [基本要求] 首先实现一个链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序.求得的通路以三元组(i,j,d)的形

  • c++ STL常用遍历算法

    需要引入头文件#include<algorithm> 1.for_each #include<iostream> using namespace std; #include <vector> #include <algorithm> class MyPrint { public: void operator()(int val) const{ cout << val << " "; } }; void printV

  • c++如何实现Base64算法

    Base64用途 1.用于对SOHO级路由器(网关设备)管理员帐户密码的加密 2.流媒体网站对于播放的流媒体文件的路径的加密 3.迅雷等下载软件对下载链接地址的加密 Base64算法 Base64编码要求把3个8位字节(3*8=24)转化为4个6位的字节(4*6=24),之后在6位的前面补两个0,形成8位一个字节的形式. Base64类 函数: unsigned int CreateMatchingEncodingBuffer (unsigned int p_InputByteCount, ch

  • C/C++实现快速排序算法的思路及原理解析

    快速排序 1. 算法思想 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序. 2. 实现原理 2.1.设置两个变量 low.high,排序开始时:low=0,high=size-1. 2.2.整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 默认数组的第一个数为基准数据,赋值给key,即key=array[low]. 因为默认数组的第一个

  • C++实现PatchMatch图像修复算法

    PatchMatch算法出自Barnes的论文 PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing PatchMatch 算法就是一个找近似最近邻(Approximate Nearest neigbhor)的方法,要比其他ANN算法快上10倍+. 将下面的图理解了,就基本理解了整个算法. 看上图时,我们以蓝色为主颜色.A代表原图像,矩形框代表待修复的patch块,要修复patch_A块就需要

  • python 用opencv实现图像修复和图像金字塔

    我们将学习如何通过一种称为修复的方法去除旧照片中的小噪音,笔画等.基本思路很简单:用相邻像素替换那些坏标记,使其看起来像邻域. cv2.inpaint() cv2.INPAINT_TELEA cv2.INPAINT_NS import numpy as np import cv2 as cv img = cv.imread('messi_2.jpg') mask = cv.imread('mask2.png',0) dst = cv.inpaint(img,mask,3,cv.INPAINT_T

  • Android基于OpenCV实现图像修复

    目录 API 操作 图像修复 实际应用中,图像常常容易受损,如存在污渍的镜头.旧照片的划痕.人为的涂画(比如马赛克),亦或是图像本身的损坏.将受到损坏的图像尽可能还原成原来的模样的技术,称之为图像修复.所谓修复,就代表图像大部分内容是完好的,所以,图像修复的原理,就是用完好的部分去推断受损部分的信息,特别是完好部分与受损部分的交界处,即受损区域的边缘,在这个推断过程中尤为重要. OpenCV给我们提供了inpaint方法来实现这个功能,并提供了两种图像修复的算法: 基于Navier-Stokes

  • OpenCV图像修复cv2.inpaint()的使用

    目录 1. 效果图 2. 原理 3. 源码 这篇博客将介绍如何通过OpenCV中图像修复的技术--cv2.inpaint() 去除旧照片中的小噪音.笔划等.并提供一个可交互式的程序,利用OpenCV的快速行进和流体力学俩种修复算法对自己的图片进行修复. 大多数人家里都会有一些旧的老化照片,上面有一些黑点.笔划等.如何复原呢? 在绘制工具中擦除:将简单地用无用的白色结构替换黑色结构,效果并不理想.OpenCV中图像修复的技术--基本思想很简单:用相邻像素替换这些坏标记,使其看起来像邻居. cv2.

  • python中PS 图像调整算法原理之亮度调整

    亮度调整 非线性亮度调整: 对于R,G,B三个通道,每个通道增加相同的增量. 线性亮度调整: 利用HSL颜色空间,通过只对其L(亮度)部分调整,可达到图像亮度的线性调整.但是,RGB和HSL颜色空间的转换很繁琐,一般还需要浮点数的运算,不仅增加了代码的复杂度,更重要的是要逐点将RGB转换为HSL,然后确定新的L值,再将HSL转换为RGB,运行速度可想而知是很慢的.要想提高图像亮度线性调整的速度,应该从三方面考虑,一是变浮点运算为整数运算,二是只提取HSL的L部分进行调整,三是采用汇编代码,在De

  • Python 人工智能老照片修复算法学习

    目录 前言 项目环境搭建 conda虚拟环境创建 激活环境 Pytorch安装 Synchronized-BatchNorm-PyTorch repository安装 Global目录Synchronized-BatchNorm-PyTorch项目部署 检测预处理模型下载 下载脸部增强模型文件 下载依赖 完整部署后项目结构 项目使用 验证一下 总结 前言 老旧或者破损的照片如何修复呢?本文主要分享一个博主使用后非常不错的照片恢复开源项目:Bringing-Old-Photos-Back-to-L

  • C++ OpenCV实现图像双三次插值算法详解

    目录 前言 一.图像双三次插值算法原理 二.C++ OpenCV代码 1.计算权重矩阵 2.遍历插值 3. 测试及结果 前言 近期在学习一些传统的图像处理算法,比如传统的图像插值算法等.传统的图像插值算法包括邻近插值法.双线性插值法和双三次插值法,其中邻近插值法和双线性插值法在网上都有很详细的介绍以及用c++编写的代码.但是,网上关于双三次插值法的原理介绍虽然很多,也有对应的代码,但是大多都不是很详细.因此基于自己对原理的理解,自己编写了图像双三次插值算法的c++ opencv代码,在这里记录一

  • OpenCV图像分割之分水岭算法与图像金字塔算法详解

    目录 前言 一.使用分水岭算法分割图像 1.cv2.distanceTransform()函数 2.cv2.connectedComponents()函数 3.cv2.watershed()函数 二.图像金字塔 1.高斯金字塔向下采样 2.高斯金字塔向上采样 3.拉普拉斯金字塔 4.应用图像金字塔实现图像的分割和融合 前言 主要介绍OpenCV中的分水岭算法.图像金字塔对图像进行分割的方法. 一.使用分水岭算法分割图像 分水岭算法的基本原理为:将任意的灰度图像视为地形图表面,其中灰度值高的部分表

  • C++ OpenCV实现图像修复功能

    目录 前言 一.OpenCV inpaint 二.源码 三.效果显示 前言 本文将使用OpenCV C++ 对有瑕疵的图像进行修复.OpenCV 提供了inpaint API可进行图像修复. 一.OpenCV inpaint 原图如图所示.本案例的需求是希望能够将图像上的红线给消除.OpenCV 提供的inpaint API能够实现这个效果. void inpaint( InputArray src, 原图 InputArray inpaintMask, 二进制掩模,指示要修复的像素 Outpu

  • Python中八大图像特效算法的示例详解

    目录 0写在前面 1毛玻璃特效 2浮雕特效 3油画特效 4马赛克特效 5素描特效 6怀旧特效 7流年特效 8卡通特效 0 写在前面 图像特效处理是基于图像像素数据特征,将原图像进行一定步骤的计算——例如像素作差.灰度变换.颜色通道融合等,从而达到期望的效果.图像特效处理是日常生活中应用非常广泛的一种计算机视觉应用,出现在各种美图软件中,这些精美滤镜背后的数学原理都是相通的,本文主要介绍八大基本图像特效算法,在这些算法基础上可以进行二次开发,生成更高级的滤镜. 本文采用面向对象设计,定义了一个图像

随机推荐