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算法對待修復區域像素優先級排序後進行漸進修復的。

來看算法步驟:

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-nffFeKnG-1618805820395)(D:\微信公眾號圖文\視覺\手撕算法\4月圖像修復\PatchMatch算法\截圖00.jpg)]

首先是建立圖像的下采樣金字塔模型,代碼中設定為五層,建立模型後

對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圖像修復算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀:

    None Found