自適應(yīng)匹配窗口的Criminisi 圖像修復(fù)算法*

周彩月，周崇波，吳冬梅，孫 琳

（曲阜師范大學(xué)，山東 曲阜 273165）

0 引言

圖像修復(fù)的目的是填補圖像缺失部分，使圖像看起來盡可能自然。基于擴散的圖像修復(fù)算法使用偏微分的擴散來傳播等照度線或線性結(jié)構(gòu)[1-4]和變分方法[5]來計算受損區(qū)域的等照度線信息、梯度信息、曲率信息等，并通過擴散機制將周圍有用信息傳播至受損的區(qū)域內(nèi)，從而完成修復(fù)工作。基于擴散的算法主要是用于修復(fù)小尺度缺損的數(shù)字圖像，比如有劃痕、折痕或者污點一類的圖像。該類方法由于缺少紋理的合成，對于較大的缺失區(qū)域修復(fù)效果不佳。基于紋理合成的方法，適用于大面積的修復(fù)，比如目標(biāo)移除。Ciminisi 等[6]提出了一種基于樣本的經(jīng)典圖像修復(fù)算法，通過將最相似的目標(biāo)塊填充到待修復(fù)區(qū)域來達到修復(fù)的目的，取得了較好的效果。但是該算法在修復(fù)過程中因為優(yōu)先級的計算順序和樣本塊搜索的問題，導(dǎo)致紋理的錯誤延伸和結(jié)構(gòu)線斷裂。Yao 等人[7]利用生物地理學(xué)優(yōu)化算法的遷移和突變來搜索最佳匹配塊，大大地降低了計算的復(fù)雜度。Ou 等人[8]引入影響因子，提高數(shù)據(jù)項的比重，避免優(yōu)先權(quán)趨于零。Dai 等人[9]對優(yōu)先權(quán)點的計算改為分式，并縮小搜索區(qū)域進行局部搜索。Liu 等人[10]使用并行算法來進行修復(fù)，保證了修復(fù)過程的快速。一些學(xué)者提出了一系列利用圖像信息的自適應(yīng)算法[11-13]。另一類是涉及使用稀疏先驗和稀疏近似的圖像修復(fù)算法，該類方法通過對圖像的信號用一組稀疏組合來表示圖像，然后通過信號重構(gòu)的方式實現(xiàn)圖像缺失部分的恢復(fù)。Zhang等人[14]提出了基于組的稀疏表示方法，并針對每組設(shè)計了一種有效的低復(fù)雜度自適應(yīng)字典學(xué)習(xí)方法。Mo 等人[15]提出了一種自適應(yīng)相似度組的概念，在自適應(yīng)組上建立了自適應(yīng)字典和稀疏表示模型。此外還有對整個圖像執(zhí)行能量函數(shù)的全局優(yōu)化[16]的方法。

Criminisi 算法具有4 個主要的缺陷。第一，在計算優(yōu)先權(quán)的過程中，模板的數(shù)據(jù)值將隨著填充而迅速降為零，從而導(dǎo)致優(yōu)先級的計算不可靠，以及填充順序的不正確，影響最終的修復(fù)效果。第二，模板窗口的大小是固定的，不區(qū)分紋理結(jié)構(gòu)復(fù)雜還是簡單，這樣會導(dǎo)致錯誤的現(xiàn)象。假如處理紋理信息復(fù)雜的色彩豐富的圖像時，如果樣本塊大，則會導(dǎo)致修復(fù)誤差變大，使修復(fù)結(jié)果不夠理想。第三，匹配策略使用全局搜索方式來識別最佳的候補塊，搜索過程的時間大大增加。第四，用于搜索類似塊的最廣泛使用的指標(biāo)是差值平方和（Sum of Squared Difference，SSD），不考慮紋理，只考慮了待修塊與候補塊對應(yīng)位置的色差。Bugeau 等人[17]的研究表明SSD 距離度量方式偏向于從統(tǒng)一區(qū)域復(fù)制像素。

因此，為了克服Criminisi 算法的缺陷，本文提出一種新的基于Criminisi 算法的圖像修復(fù)算法，該算法包括以下三個方面的內(nèi)容：

（1）穩(wěn)定的優(yōu)先級計算。為了保證圖像結(jié)構(gòu)信息的連續(xù)性，引入圖像的局部亮度特征和修復(fù)塊的邊緣信息，將其作為優(yōu)先級計算的一部分，保證圖像結(jié)構(gòu)的連續(xù)性，避免修復(fù)圖像中斷開邊界，更好地恢復(fù)對象邊界和；將傳統(tǒng)的優(yōu)先級函數(shù)乘法變換為更穩(wěn)定的加法運算，避免了優(yōu)先級值快速趨近于零。

（2）自適應(yīng)確定搜索窗口的大小。根據(jù)已修復(fù)點的統(tǒng)計信息變化，確定一種自適應(yīng)搜索范圍大小，從而減少了候選塊的數(shù)量，提高了圖像的全局一致性。與此同時，通常只搜索與已修復(fù)點相關(guān)的位置來獲取匹配塊，對于模板塊的大小變得不那么敏感，固定模板塊的大小缺陷問題也隨之解決。

（3）提出了一種新的匹配函數(shù)，在SSD 的基礎(chǔ)上將加權(quán)的巴氏距離和互信息引入公式，確保了兩個塊最小的顏色和紋理的差異。

本文引言之后的部分安排如下：第1 部分簡要地回顧傳統(tǒng)Criminisi 算法；第2 部分詳細介紹對Criminisi 算法的改進；第3 部分給出實驗結(jié)果和比較；第4 部分對全文進行總結(jié)。

1 傳統(tǒng)的Criminisi 算法

Criminisi 算法[6]的核心思想是通過優(yōu)先權(quán)計算出破損區(qū)域邊緣最先修復(fù)的待修復(fù)塊，根據(jù)待修復(fù)塊中未破損區(qū)域信息，在整幅圖像的完好區(qū)域?qū)ふ移ヅ涞臉颖緣K，利用最優(yōu)樣本塊填充待修復(fù)塊從而完成修復(fù)。Criminisi 算法修復(fù)過程主要包括3 個部分：優(yōu)先級的計算，最佳匹配塊的選擇，更新置信項。在算法過程中，沿破損邊界的待修復(fù)塊被賦予一個臨時的優(yōu)先級值，這決定了它們被填充的順序。一旦完成計算所有的優(yōu)先級，具有最高優(yōu)先級的待修復(fù)塊被找到，然后用從未受損區(qū)域提取的數(shù)據(jù)填充該待修復(fù)塊。當(dāng)待修復(fù)塊被新的像素值填充后，該區(qū)域的置信度被更新。

1.1 優(yōu)先權(quán)計算

如圖1 所示，設(shè)I為破損待修復(fù)圖像，待修復(fù)區(qū)域（白色區(qū)域）表示為Ω，未受損區(qū)域（黑色和灰色區(qū)域）表示為Φ（Φ=1-Ω），為待修復(fù)區(qū)域與未受損區(qū)域的邊界，p是位于邊界上的任意一點。Ψp以p為中心的待修復(fù)塊。

圖1 criminisi 算法符號圖

Criminisi 算法把邊界上像素點的優(yōu)先權(quán)P(p)定義為：

式中：C(p)表示置信度項，為待修復(fù)塊中的已知信息之和與待修復(fù)塊面積的比值；D(p)表示數(shù)據(jù)項，反映了圖像結(jié)構(gòu)的信息強度。它們的定義如下：

在式（2）中，|Np|為待修復(fù)塊的面積。在初始化過程中，當(dāng)q∈Φ時，C(q)=1；當(dāng)q∈Ω時，C(q)=0。在式）中，為像素點的等照度線方向，為破損邊界在點p處的單位法線向量，α為歸一化因子（一般取α=255）。

1.2 最佳匹配塊的選擇

在邊界像素點上找到優(yōu)先權(quán)最大的點p之后，然后搜索最佳樣本塊，設(shè)Ψp表示優(yōu)先級最高的待修復(fù)塊，那么完好區(qū)域的最佳樣本塊Ψp確定方式為：

式中，d表示Ψp和Ψq之間的距離。匹配準(zhǔn)則為歐式距離（SSD），代表待修復(fù)塊和匹配塊之間對應(yīng)點顏色RGB 值的方差和，計算公式具體為：

1.3 更新置信項

在找到最佳樣本塊以后，將Ψp^中的已知像素對應(yīng)復(fù)制到Ψp中破損的未知像素點。Ψp修復(fù)完畢后，更新置信項：

重復(fù)以上的步驟，直到將所有破損區(qū)域修復(fù)完為止。

2 改進的Criminisi 算法

本部分糾正上述傳統(tǒng)Criminisi 算法的問題，提出了一種改進的Criminisi 算法。為了提高算法的性能，本文將輸入圖像移動到Y(jié)CbCr 顏色空間中提取圖像梯度，有效地提高了修復(fù)效果。在此基礎(chǔ)上，首先改進優(yōu)先權(quán)，將邊緣特征和局部亮度引入優(yōu)先權(quán)模型，尋找最優(yōu)的待修復(fù)塊。然后改進匹配策略，在這一部分，根據(jù)已修復(fù)點的統(tǒng)計信息確定搜索窗口的大小，并且將巴氏距離和互信息引入匹配公式，尋找最佳的匹配塊，重復(fù)以上步驟，重構(gòu)得到修復(fù)后的圖像。整個算法的流程如下。

{修復(fù)部分}

2.1 改進的優(yōu)先權(quán)的計算

在傳統(tǒng)的Criminisi 算法中，優(yōu)先級函數(shù)P(p)被定義為置信項C(p)和數(shù)據(jù)項D(p)的乘積。但在圖像的修復(fù)過程中，會找到一些置信項很大且數(shù)據(jù)項值為零的像素，導(dǎo)致優(yōu)先級值接近于零，導(dǎo)致填充序列不正確。為了更好地保證恢復(fù)圖像修復(fù)效果，將優(yōu)先級公式改進為更加穩(wěn)定的加法計算。通過對邊緣和局部亮度特征的提取，將Ψp內(nèi)的邊緣項A(p)和亮度方差信息L(p)引入優(yōu)先權(quán)模型。改進的優(yōu)先權(quán)為：

式中，C(p)為置信項，D(p)為數(shù)據(jù)項。α為參數(shù)，用于調(diào)整數(shù)據(jù)項D(p)所代表的結(jié)構(gòu)信息在優(yōu)先權(quán)中所占的比重。A(p)表示包含在待修復(fù)塊Ψq內(nèi)使用Canny 邊緣檢測器提取的邊緣像素的集合與待修復(fù)塊中未受損區(qū)域面積的比值，公式為：

δ(·)為指示函數(shù)，當(dāng)參數(shù)為真時返回1，否則返回0。Edge 表示使用Canny 邊緣檢測器提取邊緣像素的集合。在修復(fù)過程中，通過考慮待匹配塊中的邊緣信息，“強邊緣”的待修復(fù)塊具有更高的優(yōu)先級。這樣可以優(yōu)先處理邊緣信息，然后填充具有均勻紋理特征的塊。L(p)為局部的亮度方差，將原始圖像的rgb 格式轉(zhuǎn)變成hsv 格式，提取h分量，計算已知像素點的亮度平均值和局部亮度方差。引入局部亮度信息L(p)，使得圖像亮度均勻部分優(yōu)先處理，更好地描述局部特征。

通過對優(yōu)先權(quán)公式的改進，將原來算法的乘法改為加法，能夠有效處理D(p)的急劇下降。在修復(fù)過程中充分考慮邊緣和亮度信息，優(yōu)先修復(fù)邊緣塊，其次紋理均勻紋理部分優(yōu)先修復(fù)的概率也增加，修復(fù)過程更加合理，像素優(yōu)先級修復(fù)順序更加可靠。

2.2 匹配策略的改進

搜索范圍的大小對修復(fù)有重要影響。傳統(tǒng)的Criminisi 算法采用全局搜索，這使得搜索過程時間成本較高。由于與待修復(fù)塊相關(guān)的候補塊只存在待修復(fù)塊的周圍區(qū)域，本文利用已修復(fù)點的統(tǒng)計信息對搜索范圍和匹配公式進行了改進。在最近鄰使用較少的候選塊，雖可能不是最佳的匹配塊，但提高了局部圖像一致性，在視覺上具有更好的效果。整個匹配策略的具體的過程如下。

（1）檢查已經(jīng)修復(fù)的點，以確定圖像的哪些區(qū)域可能包含當(dāng)前處理的點的相關(guān)塊，統(tǒng)計相關(guān)塊的合集，記作O(p)。需要注意，當(dāng)前處理點的待修復(fù)塊本身也被考慮在內(nèi)。

（2）根據(jù)已修復(fù)點的統(tǒng)計信息，確定搜索窗口W的大小。窗口大小的確定為：

這里，|O(p)|=1 代表只包含當(dāng)前處理點的待修復(fù)塊，沒有尋找到相關(guān)塊。λ為參數(shù)，用于調(diào)整W的大小。可見，統(tǒng)計信息越多，搜索窗口越小。

（3）從搜索窗口中提取出與當(dāng)前處理點的相關(guān)塊，把這些相關(guān)塊看作新的待修復(fù)塊，以最初的待修復(fù)塊為搜索窗口的中心，在搜索窗口中執(zhí)行匹配。

（4）執(zhí)行匹配過程，尋找最佳的匹配塊。本文改進了用于匹配的距離度量，在dSSD的基礎(chǔ)上引入巴氏距離[17]和互信息（Mutual Information，MI）。匹配具體公式如下：

在式（11）中，dMI表示待修復(fù)塊和匹配塊之間的互信息計算公式。互信息（Mutual Information，MI）在信息論中是根據(jù)特征和類別共同出現(xiàn)的概率，用來度量樣本特征和類別之間的相關(guān)性，互信息越大，表示類別之間的相關(guān)程度越高。這里用來衡量匹配塊的相似度。其中，H(Ψp)和H(Ψq)分表示了待修復(fù)塊Ψp和匹配塊Ψq的信息熵值，H(Ψp,Ψq)表示了待修復(fù)塊Ψp和匹配塊Ψq之間的聯(lián)合熵值。具體的計算公式如下：

式中：Pi為待修復(fù)塊Ψp中第i個灰度等級的像素點占整體已知像素點數(shù)的概率；Qi為匹配塊Ψq中第i個灰度等級的像素點占匹配塊中計算像素點數(shù)的概率；PQi為待修復(fù)塊Ψp和匹配塊Ψq中第i個灰度等級的像素點所占的概率。通過式（11）、式（12）、式（13）、式（14），計算待修復(fù)塊和匹配塊的互信息相似程度。

式（15）中，dBC代表了巴氏距離，取值介于[0,1]之間。ρp、ρq分別代表了待修復(fù)塊塊Ψp和匹配塊Ψq的歸一化直方圖。當(dāng)待修復(fù)塊Ψp與匹配塊Ψq具有相似分布時，dBC→0，導(dǎo)致d(SSD,MI,BC)(Ψp,Ψq)→0。為了避免這種情況，使用加權(quán)的巴氏距離，使d(SSD,MI)與1+dBC相乘。

3 實驗結(jié)果與分析

本文提供了實驗結(jié)果用于驗證所提修復(fù)算法的有效性。為了驗證本文所提算法的有效性和可靠性，選取具有代表性的傳統(tǒng)Criminisi 算法[6]、文獻[9]和文獻[14]作為對照算法與本文所提算法進行主觀和客觀的對比分析。

3.1 主觀對比

主觀對比的結(jié)果常常因為評價者和評價內(nèi)容的不同而產(chǎn)生較大差異。本文根據(jù)實驗得到的圖像進行主觀對比，即針對同一幅破損圖像使用不同的算法分別完成修復(fù)，對比得到的修復(fù)效果。

圖2 和圖3 分別是本文算法和對照算法在Lena圖像和Pigeon 圖像上的視覺實驗結(jié)果。圖2（c）和圖3（c）為經(jīng)典的Criminisi 算法修復(fù)實驗結(jié)果。從修復(fù)的結(jié)果可以看出，結(jié)果中出現(xiàn)了多處匹配錯誤，修復(fù)的邊緣出現(xiàn)了明顯的斷裂現(xiàn)象，修復(fù)的結(jié)果變成了正方形，看起來非常不自然。圖2（d）和圖3（d）為文獻[9]方法的實驗結(jié)果，從修復(fù)結(jié)果可以看出，邊緣閉合度和平滑度明顯優(yōu)于Criminisi算法，但存在一些紋理信息進行了過度延伸，出現(xiàn)了很多錯位現(xiàn)象，導(dǎo)致內(nèi)部紋理不連貫。

圖2（e）和圖3（e）為文獻[14]方法的實驗結(jié)果，該算法減少了圖像結(jié)構(gòu)的斷裂現(xiàn)象和紋理的錯誤延伸現(xiàn)象，但修復(fù)部分存在模糊。而圖2（f）和圖3（f）為本文中該方法的修復(fù)結(jié)果，可以看出視覺效果優(yōu)于上述算法，修復(fù)結(jié)果無明顯的塊匹配誤差，修復(fù)區(qū)域分布均勻，邊緣比上述其他算法平滑。本文算法對結(jié)構(gòu)信息和紋理信息進行了正確的修復(fù)，達到了理想的修復(fù)效果，說明本文對Criminisi 算法的改進是有效的。改進的算法能對損壞區(qū)域進行較好的修復(fù)，能提供更加完整、視覺效果更優(yōu)的修復(fù)結(jié)果。

圖2 Lena 圖像處理結(jié)果

圖3 Pigeon 圖像處理結(jié)果

3.2 客觀對比

客觀評價方法是指采用合理的客觀評價算子對修復(fù)質(zhì)量進行評價。本文選擇峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）作為客觀評價算子對修復(fù)質(zhì)量進行評價，其計算公式為：

式中，f(i,j)和分別表示原圖和修復(fù)后的圖像，其大小為M×N。

表2 給出圖2 和圖3 實驗結(jié)果的PNSR 量化指標(biāo)。從表2 可以看出，本文方法修復(fù)后的圖像PSNR 均大于3 種比較算法，Lena 圖像的PSNR 最大差值為7.05，最小差值為0.59。Pigeon 圖像的PSNR 最大差值為17.09，最小差值為7.04。根據(jù)客觀評價值，本文算法能較大程度地恢復(fù)破損圖像的紋理和結(jié)構(gòu)，從而更好地保持圖像結(jié)構(gòu)的一致性。

表2 圖像修復(fù)后各種算法的PSNR 對比

3.3 參數(shù)的影響

為了全面衡量本文的改進算法，本文提供了不同參數(shù)α對應(yīng)的實驗結(jié)果。實驗中，經(jīng)驗地選擇了多組α參數(shù)都獲得了較為滿意的實驗結(jié)果。圖4 和圖5 給出了不同參數(shù)下Lena 和Pigeon 圖像的視覺修復(fù)結(jié)果。

圖4 Lena 圖像不同參數(shù)處理結(jié)果

圖5 Pigeon 圖像不同參數(shù)處理結(jié)果

從圖4 和圖5 可以看出，兩個實驗圖像在不同參數(shù)下的修復(fù)結(jié)果無明顯的塊匹配誤差，修復(fù)區(qū)域分布均勻，修復(fù)效果能滿足人類視覺的需要。但對于圖4，由于Lena 圖像的紋理和色彩豐富，其結(jié)果在α=1,5,7 時，存在少量細微的色差點。對于圖5，Pigeon 圖像相比于Lena 圖像，其紋理和色彩比較單一，因此不同參數(shù)上的修復(fù)效果在視覺上無明顯的差別。

表3 給出了不同參數(shù)α下圖4 和圖5 實驗結(jié)果的PNSR。在經(jīng)驗地設(shè)置參數(shù)過程中，發(fā)現(xiàn)將α的值大約設(shè)置為3 時，PNSR 最大，若將α值設(shè)置的比3 大或小許多，PNSR 值變小。但是，即使將α設(shè)置的值偏離經(jīng)驗最優(yōu)值時，獲得的PNSR 依然較為理想，這也證明圖4 和圖5 在不同參數(shù)下實驗結(jié)果視覺效果差別不大。

表3 圖像修復(fù)后不同參數(shù)的PSNR 對比

4 結(jié)語

本文在Criminisi 算法的基礎(chǔ)上，提出了一種改進的優(yōu)先級函數(shù)，以解決Criminisi 圖像修復(fù)算法中圖像結(jié)構(gòu)不連續(xù)的問題。本文算法增加了結(jié)構(gòu)信息優(yōu)先級的比例、邊緣信息和局部亮度特征，使其在填充圖像結(jié)構(gòu)信息時更加考慮其一致性，并提出了一種自適應(yīng)搜索范圍的方法，避免了固定樣本容量對修復(fù)效果的影響。在尋找最優(yōu)匹配塊時，結(jié)合候選塊和修復(fù)塊的結(jié)構(gòu)相似程度，采用基于像素和統(tǒng)計度量，可更準(zhǔn)確地找到最優(yōu)匹配塊，并將該方法與基于其他方法的分析結(jié)果進行了對比。主觀上，該方法可以保持視覺上的連通性。客觀上，峰值信噪比（PSNR）值高于其他方法。