基于閾值分界和區域劃分的Criminisi 改進算法的圖像修復*

周先春 陳 璟 張 婕 殷新鵬 郭亮可

（1.南京信息工程大學電子與信息工程學院 南京 210044）

（2.南京信息工程大學江蘇省大氣環境與裝備技術協同創新中心 南京 210044）

1 引言

圖像修復［1~3］是通過數字圖像的原有部分信息來獲取缺失信息的圖像處理技術。目前主流的圖像修復算法主要為兩類：一類是基于偏微分方程［4~7］的圖像修復算法，最早Bertalmio［8］等提出等照度線方向擴散的BSCB 圖像修復模型，其后CHAN［9］等將全變分模型（TV）和曲率驅動模型（CDD）［10］作為算法模型進行圖像修改，這類方法對較大區域破損圖像具有較好的修復效果；另一類是基于紋理合成［11~12］的圖像修復算法，其中Criminisi［13］等提出的Criminisi 算法就是最經典的算法之一。后來的很多學者在其基礎之上進行了更深層次的研究，崔天卿［14］等將Sobel算子的邊緣檢測項引入優先權函數的模型構造中，提升算法對邊緣輪廓的識別能力，彌補了邊緣延伸的缺陷。PATEL［15］等通過鄰域檢索的方式改進搜素策略來提升模型的匹配效率。LIANG［16］等將優先權函數由乘法模型變更為加權求和的形式，且引入正則化因子，更好地修復圖像紋理特征。REN［17］等結合邊緣結構和紋理信息，通過引入差分因子對算法進行改進，有效緩解原算法紋理延伸的現象。曾接賢［18］等將棋盤距離取代優先權函數中的匹配準則，減少修復順序不合理導致的錯誤匹配現象。WANG［19］等提出用結構一致的塊匹配來優化匹配準則，并引入傅里葉變換全局搜索策略，在結構相似性上有顯著提升。王鳳隨［20］等將信息熵和梯度因子引入優先權函數，更合理地找到最優樣本塊來達到更好的視覺效果。周先春［21］等引入結構相似性到優先權函數構造中，且加入HSV 顏色空間來解決原算法模型匹配準則單一化的問題。

2 Criminisi算法原理

Criminisi 算法作為圖像修復中的經典算法，其基于圖像樣本塊進行圖像修復。該算法主要按照邊界樣本塊的優先級順序，在圖像信息完好區域中匹配與待修復樣本塊相似的目標塊，然后將匹配最佳的樣本塊填充到待修復的破損區域，至待修復圖像的破損區域被填充完全為止。

如圖1 所示，是Criminisi 算法的基本原理。其中，Ω 表示圖像待修復的破損區域，Φ 表示圖像的信息完好區域，?Ω 表示兩區域邊界輪廓；p表示目標像素點，ψp表示以p為中心的樣本塊；np為待修復破損區域的單位法矢量；為p的等照度矢量，其與p的梯度矢量大小相同，方向相反。

圖1 Criminisi算法原理圖

Criminisi算法的基本步驟如下。

2.1 優先權函數

Criminisi 算法先通過優先權函數計算區域邊界的所有樣本塊優先級來得到樣本塊修復的優先順序，優先權函數由置信度項C(p)和數據項D(p)組成，其表達式如式（1）所示：

其中，置信度項C(p)表示待修復的樣本塊ψp中已知像素信息所占比重，已知像素信息較多的樣本塊可靠性越好，其優先級越高，則應該優先修復；數據項D(p)表示樣本塊的結構強度信息，數據項的值較大說明邊緣紋理特征信息較多，其可能處于結構邊界處，優先修復可以較好保留圖像結構特征的整體連貫性。置信度項C(p)和數據項D(p)如式（2）和式（3）所示：

其中，α為歸一化因子，一般取值為255。

2.2 最佳匹配準則

在計算完所有輪廓邊界樣本塊的優先權函數后，選取其數值最大的樣本塊作為待修復塊，運用SSD 像素差平方作為匹配準則，采用全局搜索的方式從信息完整區域選擇最佳匹配塊用以修復圖像。

SSD匹配準則如式（4）所示：

其中d(ψp′,ψq)表示待修復樣本塊ψp′與匹配塊ψq對應像素的差值平方和，表達式如式（5）所示：

其中，IR、IG、IB和IR'、IG'、IB'分別為樣本塊和匹配塊的像素點，且分別對應三基色通道。

2.3 更新置信度

在最佳匹配的樣本塊被填充到邊界待修復塊時，輪廓邊界會發生變化，邊界樣本塊的優先權函數值也隨之改變，因此需要更新邊界待修復塊的中心像素點置信度。其公式如式（6）所示：

通過重復以上算法步驟，至所有待修復區域為零，即完成整幅圖像的圖像修補。

3 改進的Criminisi算法

3.1 優先權函數的改進

Criminisi 算法的優先權函數是采用乘積的形式進行計算，置信度項和數據項之間數據相互抑制，在平衡穩定中進行圖像修復。但隨著迭代次數的增加，置信度項會逐漸下降乃至趨近于零，使得優先權函數效果降低，圖像塊修復順序不合理，最終導致圖像修復效果差。

針對該問題，本文算法對置信度項進行改進，當其在迭代過程中衰減到指定閾值時，置信度項將被設置為常量，整個優先權函數由數據項主導來優先修復結構部分，其改進后的表達式如式（7）所示：

其中C(p)表示待修復塊中像素個數占總像素個數的比例，取值范圍0 ≤C(p)≤1，隨著迭代次數增加，C(p)有快速下降的趨勢，一方面通過使用具有平滑特性的對數函數來緩解下降趨勢，另一方面當C(p)值小于閾值T時，將C(p)值設置為常量。

同時，在計算數據項時引入結構張量，結構張量能夠獲取圖像的局部結構信息和方向信息，相較于梯度向量在修復圖像時可更好地保持圖像的結構連貫性。結構張量Sρ的定義如下式所示：

其中，?I為圖像梯度矢量，Ix和Iy分別為兩個方向的偏導數，Gρ為標準差為ρ的高斯核函數，?為卷積操作。λ1和λ2分別代表了結構張量在該像素點處的最大特征值和最小特征值，通過其取值情況可以獲得該處的結構信息。其表達式如式（10）所示：

當λ1和λ2值較小時，說明像素點周圍灰度變化較小，其處于平坦區域；當λ1和λ2值一個較大一個較小時，說明像素點周圍變化較大，其處于邊緣區域；當λ1和λ2值都較大時，說明像素點周圍灰度變化很大，其處于角點區域。

改進后的優先權函數如式（11）所示：

其中，S(p) 表示結構張量，α和β分別為數據項和結構張量的權重系數。

3.2 最佳匹配準則的改進

選取合適的匹配準則是Criminisi 算法的關鍵步驟，原算法使用單一的SSD匹配準則在匹配時只考慮待修復塊與樣本塊的像素間距離，而沒有考慮顏色、形狀和結構等特征信息，易出現錯誤匹配的“塊狀效應”和混亂的紋理現象。本文將Jaccard 距離引入匹配準則，將待修復塊和匹配塊的像素作為集合，計算其Jaccard 距離和SSD 準則相互作用來獲取更合理的匹配塊。

Jaccard 指數是有限樣本集合之間相似性的一種衡量指標，其定義為

式（12）中，A和B為兩個集合，定義A和B為空集合時J(A,B)=1，其取值范圍0 ≤J(A,B)≤1。Jaccard距離和Jaccard指數互為補充，定義如下：

兩個集合的Jaccard 距離取值越小，則兩者相似度越高。改進后的最佳匹配準則為

其中，η為Jaccard距離的權重指數。

3.3 樣本塊大小的改進

Criminisi 算法的樣本塊采用固定的9×9 像素大小，但這樣不考慮圖像紋理的局部情況，樣本塊過大會導致修復延伸，影響修復效果；樣本塊過小會使得修復時間過長，降低修復效率，因此本文提出自適應的樣本塊大小來匹配不同像素點的紋理情況，其樣本塊大小M如式（15）所示：當像素點處于角點區域，使用5×5 大小樣本塊；當像素點處于邊緣區域，使用7×7 大小樣本塊；當像素點處于平坦區域，使用11×11 大小樣本塊；其他情況使用原來的9×9 大小樣本塊。

式中，λ1和λ2為結構張量的兩個特征值。

3.4 搜索策略的改進

Criminisi 算法通過全局搜索策略來尋找最佳匹配塊，算法的時間復雜度較高。本文通過基于紋理分割的方式來劃分圖像區域，在各區域內對應尋找最佳匹配塊，這種局部搜索的方式一方面減少匹配時間來提升效率，另一方面提升匹配的準確率。首先通過無監督分割算法將待修復圖像進行分割，然后通過顏色直方圖特性合并區域，最后通過相似塊匹配準則確定搜索區域來進行相似塊搜索。

合并區域時，圖像中會存在物體相交和間斷的情況，如電線桿會將墻面分割成幾個部分，或是物體間錯亂陳列，因此將這些區域合并需要通過顏色和梯度特征進行分組。通過引入圖像強度導數的統計特征來測量各區域顏色和圖像特征。對于區域Si(i≠0 )計算其M+1 維強度矢量，前面M維部分代表強度矢量Vi(1 ) ~Vi(M)，即區域i的直方圖，最后的Vi(M+1) 定義如式（16）所示：

其中，Ni是中像素點數量，‖ ?j‖ 為像素點的強度梯度大小，μ為調節梯度信息比重的權重系數。兩個相似區域Sx和Sy合并為Sxy需要滿足式（17），Qx,y是兩區域的相似分數，Vx和Vy為對應區域的強度矢量。

在圖像區域合并后，引入圖像塊p的信息熵來度量待修復樣本塊的復雜度來縮小搜索范圍，其定義如式（18）所示：

其中，pi表示圖像樣本庫中灰度值為i的像素點比例。若是彩色圖像則RGB 三通道信息熵的均值為其圖像信息熵。

本文通過利用匹配塊和待修復塊之間的方差來體現兩者之間的相似性，最終的相似塊度量準則由信息熵和方差共同決定：

其中，μ+ν=1且均取值0.5。

3.5 改進后算法流程

改進后算法流程如圖2所示。

圖2 改進后算法流程圖

4 實驗結果與分析

為了驗證本文提出算法的有效性，在計算機上利用Matlab2016 平臺進行算法仿真試驗。本文算法中參數的設置由大量實驗測試獲得，其中為α為0.7，β為0.3，η為0.5，T為0.5。評價標準是通過主客觀結合進行比較，客觀評價指標為峰值信噪比（PSNR）和結構相似性（SSIM）。

算法仿真的實驗效果圖如圖3~5所示。

圖3 Lena圖像修復效果圖

圖3、圖4 和圖5 是分別對Lena 圖的劃痕和dxy圖像的樓宇屋頂處，以及海景圖像的地板進行圖像修復，并將本文的算法同傳統的Criminisi算法以及文獻［18］提到的改進算法進行比較。通過對圖3（a）、圖3（b）和圖3（c）的恢復圖像進行對比，傳統的Criminisi 算法對小區域的劃痕已經具有較好的處理效果，但其在劃痕周圍存在紋理延伸的現象，修復后仍能看見比較明顯的處理痕跡；文獻［18］通過棋盤距離替代傳統的數據項，對細小破損具有較好的修復效果；本文改進算法在恢復圖像信息時更好地保留了原始圖像的邊緣結構信息。通過圖4可以看出，Criminisi算法在修復屋頂時因為優先權函數的不合理性，出現錯誤匹配的結果而導致圖像修復錯誤；而圖4（d）可以看出文獻［18］改進的算法在邊緣修復上存在一些邊緣不平滑連貫的現象；而本文提出的算法則可以較好地保持圖像恢復后的連貫性。通過圖5（c）可以看出Criminisi 算法對大區域破損圖像修復效果一般，紋理細節信息處理不好；而文獻［18］通過優化優先權函數更好地恢復了地板的紋理結構；本文提到的算法在處理后結構信息更加完善，地板縫隙更加清晰，具有較好的視覺效果。

圖4 dxy圖像修復效果圖

圖5 海景圖像修復效果圖

從表1和表2可知本文提出的算法模型在峰值信噪比上較原算法提升了約0.8dB，而在結構相似性上也有所提升，說明其結構紋理也得到更好保留。

表1 各算法仿真峰值信噪比值

表2 各算法仿真結構相似性值

5 結語

本文通過對Criminisi 算法的優先權函數進行閾值劃分和結構張量的改進，并結合最佳匹配準則和搜索策略的優化，在算法的效率上有了明顯提升，修復后的圖像邊緣信息和紋理結構得到清晰保留，圖像的具有較好的整體連貫性，其峰值信噪比和結構相似性的數值也得到顯著增加。