基于閾值分界和區(qū)域劃分的Criminisi 改進(jìn)算法的圖像修復(fù)*

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

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

（2.南京信息工程大學(xué)江蘇省大氣環(huán)境與裝備技術(shù)協(xié)同創(chuàng)新中心 南京 210044）

1 引言

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

2 Criminisi算法原理

Criminisi 算法作為圖像修復(fù)中的經(jīng)典算法，其基于圖像樣本塊進(jìn)行圖像修復(fù)。該算法主要按照邊界樣本塊的優(yōu)先級(jí)順序，在圖像信息完好區(qū)域中匹配與待修復(fù)樣本塊相似的目標(biāo)塊，然后將匹配最佳的樣本塊填充到待修復(fù)的破損區(qū)域，至待修復(fù)圖像的破損區(qū)域被填充完全為止。

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

圖1 Criminisi算法原理圖

Criminisi算法的基本步驟如下。

2.1 優(yōu)先權(quán)函數(shù)

Criminisi 算法先通過優(yōu)先權(quán)函數(shù)計(jì)算區(qū)域邊界的所有樣本塊優(yōu)先級(jí)來得到樣本塊修復(fù)的優(yōu)先順序，優(yōu)先權(quán)函數(shù)由置信度項(xiàng)C(p)和數(shù)據(jù)項(xiàng)D(p)組成，其表達(dá)式如式（1）所示：

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

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

2.2 最佳匹配準(zhǔn)則

在計(jì)算完所有輪廓邊界樣本塊的優(yōu)先權(quán)函數(shù)后，選取其數(shù)值最大的樣本塊作為待修復(fù)塊，運(yùn)用SSD 像素差平方作為匹配準(zhǔn)則，采用全局搜索的方式從信息完整區(qū)域選擇最佳匹配塊用以修復(fù)圖像。

SSD匹配準(zhǔn)則如式（4）所示：

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

其中，IR、IG、IB和IR'、IG'、IB'分別為樣本塊和匹配塊的像素點(diǎn)，且分別對(duì)應(yīng)三基色通道。

2.3 更新置信度

在最佳匹配的樣本塊被填充到邊界待修復(fù)塊時(shí)，輪廓邊界會(huì)發(fā)生變化，邊界樣本塊的優(yōu)先權(quán)函數(shù)值也隨之改變，因此需要更新邊界待修復(fù)塊的中心像素點(diǎn)置信度。其公式如式（6）所示：

通過重復(fù)以上算法步驟，至所有待修復(fù)區(qū)域?yàn)榱悖赐瓿烧鶊D像的圖像修補(bǔ)。

3 改進(jìn)的Criminisi算法

3.1 優(yōu)先權(quán)函數(shù)的改進(jìn)

Criminisi 算法的優(yōu)先權(quán)函數(shù)是采用乘積的形式進(jìn)行計(jì)算，置信度項(xiàng)和數(shù)據(jù)項(xiàng)之間數(shù)據(jù)相互抑制，在平衡穩(wěn)定中進(jìn)行圖像修復(fù)。但隨著迭代次數(shù)的增加，置信度項(xiàng)會(huì)逐漸下降乃至趨近于零，使得優(yōu)先權(quán)函數(shù)效果降低，圖像塊修復(fù)順序不合理，最終導(dǎo)致圖像修復(fù)效果差。

針對(duì)該問題，本文算法對(duì)置信度項(xiàng)進(jìn)行改進(jìn)，當(dāng)其在迭代過程中衰減到指定閾值時(shí)，置信度項(xiàng)將被設(shè)置為常量，整個(gè)優(yōu)先權(quán)函數(shù)由數(shù)據(jù)項(xiàng)主導(dǎo)來優(yōu)先修復(fù)結(jié)構(gòu)部分，其改進(jìn)后的表達(dá)式如式（7）所示：

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

同時(shí)，在計(jì)算數(shù)據(jù)項(xiàng)時(shí)引入結(jié)構(gòu)張量，結(jié)構(gòu)張量能夠獲取圖像的局部結(jié)構(gòu)信息和方向信息，相較于梯度向量在修復(fù)圖像時(shí)可更好地保持圖像的結(jié)構(gòu)連貫性。結(jié)構(gòu)張量Sρ的定義如下式所示：

其中，?I為圖像梯度矢量，Ix和Iy分別為兩個(gè)方向的偏導(dǎo)數(shù)，Gρ為標(biāo)準(zhǔn)差為ρ的高斯核函數(shù)，?為卷積操作。λ1和λ2分別代表了結(jié)構(gòu)張量在該像素點(diǎn)處的最大特征值和最小特征值，通過其取值情況可以獲得該處的結(jié)構(gòu)信息。其表達(dá)式如式（10）所示：

當(dāng)λ1和λ2值較小時(shí)，說明像素點(diǎn)周圍灰度變化較小，其處于平坦區(qū)域；當(dāng)λ1和λ2值一個(gè)較大一個(gè)較小時(shí)，說明像素點(diǎn)周圍變化較大，其處于邊緣區(qū)域；當(dāng)λ1和λ2值都較大時(shí)，說明像素點(diǎn)周圍灰度變化很大，其處于角點(diǎn)區(qū)域。

改進(jìn)后的優(yōu)先權(quán)函數(shù)如式（11）所示：

其中，S(p) 表示結(jié)構(gòu)張量，α和β分別為數(shù)據(jù)項(xiàng)和結(jié)構(gòu)張量的權(quán)重系數(shù)。

3.2 最佳匹配準(zhǔn)則的改進(jìn)

選取合適的匹配準(zhǔn)則是Criminisi 算法的關(guān)鍵步驟，原算法使用單一的SSD匹配準(zhǔn)則在匹配時(shí)只考慮待修復(fù)塊與樣本塊的像素間距離，而沒有考慮顏色、形狀和結(jié)構(gòu)等特征信息，易出現(xiàn)錯(cuò)誤匹配的“塊狀效應(yīng)”和混亂的紋理現(xiàn)象。本文將Jaccard 距離引入匹配準(zhǔn)則，將待修復(fù)塊和匹配塊的像素作為集合，計(jì)算其Jaccard 距離和SSD 準(zhǔn)則相互作用來獲取更合理的匹配塊。

Jaccard 指數(shù)是有限樣本集合之間相似性的一種衡量指標(biāo)，其定義為

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

兩個(gè)集合的Jaccard 距離取值越小，則兩者相似度越高。改進(jìn)后的最佳匹配準(zhǔn)則為

其中，η為Jaccard距離的權(quán)重指數(shù)。

3.3 樣本塊大小的改進(jìn)

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

式中，λ1和λ2為結(jié)構(gòu)張量的兩個(gè)特征值。

3.4 搜索策略的改進(jìn)

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

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

其中，Ni是中像素點(diǎn)數(shù)量，‖ ?j‖ 為像素點(diǎn)的強(qiáng)度梯度大小，μ為調(diào)節(jié)梯度信息比重的權(quán)重系數(shù)。兩個(gè)相似區(qū)域Sx和Sy合并為Sxy需要滿足式（17），Qx,y是兩區(qū)域的相似分?jǐn)?shù)，Vx和Vy為對(duì)應(yīng)區(qū)域的強(qiáng)度矢量。

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

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

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

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

3.5 改進(jìn)后算法流程

改進(jìn)后算法流程如圖2所示。

圖2 改進(jìn)后算法流程圖

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出算法的有效性，在計(jì)算機(jī)上利用Matlab2016 平臺(tái)進(jìn)行算法仿真試驗(yàn)。本文算法中參數(shù)的設(shè)置由大量實(shí)驗(yàn)測試獲得，其中為α為0.7，β為0.3，η為0.5，T為0.5。評(píng)價(jià)標(biāo)準(zhǔn)是通過主客觀結(jié)合進(jìn)行比較，客觀評(píng)價(jià)指標(biāo)為峰值信噪比（PSNR）和結(jié)構(gòu)相似性（SSIM）。

算法仿真的實(shí)驗(yàn)效果圖如圖3~5所示。

圖3 Lena圖像修復(fù)效果圖

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

圖4 dxy圖像修復(fù)效果圖

圖5 海景圖像修復(fù)效果圖

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

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

表2 各算法仿真結(jié)構(gòu)相似性值

5 結(jié)語

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