自適應匹配窗口的Criminisi 圖像修復算法*

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

（曲阜師范大學，山東 曲阜 273165）

0 引言

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

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

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

（1）穩定的優先級計算。為了保證圖像結構信息的連續性，引入圖像的局部亮度特征和修復塊的邊緣信息，將其作為優先級計算的一部分，保證圖像結構的連續性，避免修復圖像中斷開邊界，更好地恢復對象邊界和；將傳統的優先級函數乘法變換為更穩定的加法運算，避免了優先級值快速趨近于零。

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

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

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

1 傳統的Criminisi 算法

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

1.1 優先權計算

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

圖1 criminisi 算法符號圖

Criminisi 算法把邊界上像素點的優先權P(p)定義為：

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

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

1.2 最佳匹配塊的選擇

在邊界像素點上找到優先權最大的點p之后，然后搜索最佳樣本塊，設Ψp表示優先級最高的待修復塊，那么完好區域的最佳樣本塊Ψp確定方式為：

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

1.3 更新置信項

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

重復以上的步驟，直到將所有破損區域修復完為止。

2 改進的Criminisi 算法

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

{修復部分}

2.1 改進的優先權的計算

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

式中，C(p)為置信項，D(p)為數據項。α為參數，用于調整數據項D(p)所代表的結構信息在優先權中所占的比重。A(p)表示包含在待修復塊Ψq內使用Canny 邊緣檢測器提取的邊緣像素的集合與待修復塊中未受損區域面積的比值，公式為：

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

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

2.2 匹配策略的改進

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

（1）檢查已經修復的點，以確定圖像的哪些區域可能包含當前處理的點的相關塊，統計相關塊的合集，記作O(p)。需要注意，當前處理點的待修復塊本身也被考慮在內。

（2）根據已修復點的統計信息，確定搜索窗口W的大小。窗口大小的確定為：

這里，|O(p)|=1 代表只包含當前處理點的待修復塊，沒有尋找到相關塊。λ為參數，用于調整W的大小?？梢?，統計信息越多，搜索窗口越小。

（3）從搜索窗口中提取出與當前處理點的相關塊，把這些相關塊看作新的待修復塊，以最初的待修復塊為搜索窗口的中心，在搜索窗口中執行匹配。

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

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

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

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

3 實驗結果與分析

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

3.1 主觀對比

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

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

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

圖2 Lena 圖像處理結果

圖3 Pigeon 圖像處理結果

3.2 客觀對比

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

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

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

表2 圖像修復后各種算法的PSNR 對比

3.3 參數的影響

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

圖4 Lena 圖像不同參數處理結果

圖5 Pigeon 圖像不同參數處理結果

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

表3 給出了不同參數α下圖4 和圖5 實驗結果的PNSR。在經驗地設置參數過程中，發現將α的值大約設置為3 時，PNSR 最大，若將α值設置的比3 大或小許多，PNSR 值變小。但是，即使將α設置的值偏離經驗最優值時，獲得的PNSR 依然較為理想，這也證明圖4 和圖5 在不同參數下實驗結果視覺效果差別不大。

表3 圖像修復后不同參數的PSNR 對比

4 結語

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