C++實現(xiàn)PatchMatch圖像修復算法
更新時間：2021年04月21日 17:14:51 作者：周旋_
這篇文章主要介紹了C++實現(xiàn)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 的核心思想是利用圖像的連續(xù)性（consistence）， 一個圖像A的patch_A（藍色）附近的Patch塊（紅色綠色）的最近鄰（B中的紅色綠色框）最有可能出現(xiàn)在Patch_A的最近鄰（B中的藍色框）附近，利用這種圖像的連續(xù)性大量減少搜索的范圍，通過迭代的方式保證大多數(shù)點能盡快收斂。
PatchMatch算法是對所有待修復像素迭代修復的，而不是像Criminisi或FMM算法對待修復區(qū)域像素優(yōu)先級排序后進行漸進修復的。
來看算法步驟：
![[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-nffFeKnG-1618805820395)(D:\微信公眾號圖文\視覺\手撕算法\4月圖像修復\PatchMatch算法\截圖00.jpg)]](http://img.jbzj.com/file_images/article/202104/20210421171053162.jpg)
首先是建立圖像的下采樣金字塔模型，代碼中設定為五層，建立模型后
對A的待修復區(qū)域每個patch塊隨機在B已知區(qū)域中匹配一個patch塊，即初始化偏置地圖（上圖a步驟）。
/*********************************
函數(shù)聲明：初始化偏置圖像
參數(shù)：NONE
注釋：NONE
測試：NONE
**********************************/
void PatchMatch::InitOff(Mat Mask, Mat &Off)
{
//為方便起見，將所有的都附上，要求不能賦值到非搜索區(qū)域
//初始化格式
Off = Mat(Mask.size(), CV_32FC2, Scalar::all(0));//2維無符號32位精度浮點數(shù)
for (int i = 0; i < Mask.rows; i++)
{
for (int j = 0; j < Mask.cols; j++)
{
//不考慮search區(qū)域，沒有破損，他們的最佳偏移向量當然是0，自己
if (Mask.at<uchar>(i, j) == search)
{
Off.at<Vec2f>(i, j)[0] = 0; //<Vec2f> 向量，2維，浮點數(shù)
Off.at<Vec2f>(i, j)[1] = 0;
}
else//處理hole，采用隨機偏置
{
//先初始化2個偏置數(shù)r_col,r_row
int r_col = rand() % Mask.cols; //rand（）產(chǎn)生隨機數(shù)，主要是產(chǎn)生一個偏置的初始值
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;
//為什么要有這個循環(huán)？因為一次的隨機賦值，很可能會出現(xiàn)偏置后的塊跑到破損區(qū)域，或者是超出限定搜索框的邊界
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待修復區(qū)域所有像素。當遍歷到當前像素時，執(zhí)行下面的步驟來進行修復：
步驟一：傳播（圖中b步驟）
傳播會計算原圖A當前像素塊patch_A（藍色）對應的B中的patch_B_1，patch_A上方（綠色）（奇數(shù)次迭代為下方）對應的B中的patch_B_2，patch_A左側(cè)（紅色）（奇數(shù)次迭代為右側(cè)）對應的B中的patch_B_3這三個patch塊中與patch_A相似度最高的patch塊。
計算相似度函數(shù)為
//以塊為單位，用所有像素點的相同顏色通道的差平方來簡單判斷相似度
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;
}
傳播函數(shù)：
//迭代第一步：傳播
//（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個塊最相似的塊的代表數(shù)字，用于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//奇數(shù)次迭代
{
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中，以當前像素為中心點，初始半徑區(qū)域為全圖，在此區(qū)域內(nèi)隨機找尋patch塊并與patch_A原本對應的B中的patch塊對比，若更相似則更新對應關系offset，然后以新的patch_B為中心，半徑縮小一倍，繼續(xù)搜索，直到半徑縮小為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);//獲取修復基準框，在框內(nèi)操作
//迭代指數(shù)
int attenuate = 0;
while (true)
{
//獲取隨機參數(shù)，在 [-1;1] 間
float divcol = rand() % 2000 / 1000.0f - 1.0f;
float divrow = rand() % 2000 / 1000.0f - 1.0f;
//減小框大小的公式，𝑢_𝑖=𝑣_0+𝑤*𝛼^𝑖*𝑅_𝑖
//行列分別處理，MaxWindow：原始框?qū)挾?；divcol：隨機系數(shù)；pow(A,B):A的B次方。隨迭代次數(shù)而變小的縮小系數(shù)；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個像素，沒有意義，直接結束整個循環(huán)，對下一個像素處理
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內(nèi)
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);
//取出現(xiàn)在的隨機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;
}
}
//迭代指數(shù)增加
attenuate++;
}
}
經(jīng)過該兩個步驟，本次迭代完畢。
當最終迭代完成后，就完成了整個修復過程。
算法效果
可以看到效果還是可以的，速度也比較快。
到此這篇關于C++實現(xiàn)PatchMatch圖像修復算法的文章就介紹到這了,更多相關C++ PatchMatch圖像修復算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
“地獄回調(diào)”（Callback Hell）是指在編程中使用過多嵌套回調(diào)函數(shù),導致代碼難以閱讀和維護,本文給大家介紹了C++解決回調(diào)地獄問題的方法小結,文中有相關的代碼示例供大家參考,需要的朋友可以參考下2024-07-07
今天小編就為大家分享一篇關于二叉樹中葉子節(jié)點的統(tǒng)計和樹高問題，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章介紹了C++超集C++/CLI模塊的基本用法，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
大家好，本篇文章主要講的是C語言中遞歸和排列組合詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C/C++通過SQLite SDK實現(xiàn)數(shù)據(jù)庫增刪改查操作
SQLite,作為一款嵌入式關系型數(shù)據(jù)庫管理系統(tǒng),一直以其輕量級、零配置以及跨平臺等特性而備受青睞,本文主要介紹了C++如何通過SQLite SDK實現(xiàn)數(shù)據(jù)庫增刪改查操作,感興趣的可以了解下2023-11-11
這篇文章主要介紹了C語言中的字符型數(shù)據(jù)與ASCII碼表，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
這篇文章主要給大家介紹了C/C++中寫時拷貝的相關資料，所謂寫時拷貝也就是拖延版的深拷貝，下面文章中介紹的非常清楚，需要的朋友可以參考學習，下面來一起看看吧。2017-03-03
這篇文章主要介紹了C++實現(xiàn)矩陣對稱正交化,分為python代碼和C++的eigen庫實現(xiàn)代碼，代碼簡單易懂，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
在項目開發(fā)過程中，經(jīng)常會使用到c++ 的url編碼和解碼，本文將以此問題詳細介紹使用技巧，需要的朋友可以參考下2012-11-11
這篇文章主要介紹了C++鏈表類的封裝，文章基于C++的相關資料展開主題的詳細內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-04-04