摘  要： 在研究Criminisi修復(fù)算法的基礎(chǔ)上，提出了改進(jìn)的基于樣本塊的圖像修復(fù)方法。根據(jù)圖像的待修復(fù)面積及其紋理特征，自適應(yīng)選取樣本塊大小，提高修復(fù)的速度；采用新的數(shù)據(jù)項(xiàng)，改進(jìn)優(yōu)先權(quán)公式，避免階梯效應(yīng)的產(chǎn)生；重新定義置信度的更新公式，引入曲率距離，減少因置信度更新而累計(jì)的誤差，提高修復(fù)順序的準(zhǔn)確性。實(shí)驗(yàn)表明，改進(jìn)的方法能夠有效提高修復(fù)的效果，減少修復(fù)所需時(shí)間。

　　關(guān)鍵詞： 圖像修復(fù)；樣本塊；優(yōu)先權(quán)；置信度的更新

0 引言

　　圖像修復(fù)的本質(zhì)是通過不完整信息重新構(gòu)造出完整信息，對(duì)圖像上信息缺損區(qū)域進(jìn)行填充，恢復(fù)受損的圖像，讓觀察者無法用肉眼看出圖像曾損壞過。對(duì)圖像修復(fù)技術(shù)的深入研究也是當(dāng)前計(jì)算機(jī)視覺領(lǐng)域中的一個(gè)熱點(diǎn)。

　　圖像修復(fù)技術(shù)可分為兩大類：基于偏微分的修復(fù)方法[1-3]和基于紋理的修復(fù)方法[4-7]。前者是通過建立偏微分方程，將圖像中完好的信息向受損區(qū)域內(nèi)部擴(kuò)散，進(jìn)行圖像修復(fù)，這類方法能夠保留圖像的線性結(jié)構(gòu)，對(duì)小尺度破損的圖像的修復(fù)效果較好，但對(duì)修復(fù)破損區(qū)域較大的圖像時(shí)，計(jì)算量大，耗時(shí)長(zhǎng)，易產(chǎn)生模糊效應(yīng)。后者是利用圖像紋理的重復(fù)性以及規(guī)則性進(jìn)行紋理合成，填補(bǔ)丟失的信息，修復(fù)受損區(qū)域。2003年，Criminisi等人[4]提出了一種基于樣本塊的圖像修復(fù)算法，利用待修復(fù)塊在信息完整區(qū)域匹配選擇紋理塊，結(jié)合擴(kuò)散修復(fù)方法的優(yōu)點(diǎn)，按照一定的先后順序進(jìn)行填充，保證了圖像紋理修復(fù)的自然順暢，其簡(jiǎn)單有效的特點(diǎn)使其成為紋理修復(fù)的經(jīng)典算法。但是利用該算法進(jìn)行修復(fù)的圖像會(huì)產(chǎn)生冗余，出現(xiàn)結(jié)構(gòu)不連續(xù)現(xiàn)象，影響最終的修復(fù)效果。本文以Criminisi算法為基礎(chǔ)，對(duì)其不足之處進(jìn)行改進(jìn)，自適應(yīng)選擇最佳樣本塊大小，改進(jìn)優(yōu)先權(quán)公式和置信度更新方式，使紋理和結(jié)構(gòu)信息得到有效利用。通過實(shí)驗(yàn)結(jié)果對(duì)比分析，證明改進(jìn)的方法不僅能得到較好的修復(fù)結(jié)果，且能夠大幅度提高修復(fù)的速度。

1 Criminisi算法簡(jiǎn)介

　　Criminisi算法的核心是找到具有最高優(yōu)先權(quán)值的待修復(fù)點(diǎn)p，設(shè)置以p為中心的9×9像素的待修復(fù)塊，在未受損的圖像區(qū)域中尋找最佳樣本塊，將該樣本塊的信息復(fù)制到待修復(fù)塊中，待修復(fù)區(qū)域發(fā)生變化，最后更新邊界和置信度的值，其過程如圖1所示。圖中的是未受損的區(qū)域，是待修復(fù)區(qū)域，是待修復(fù)區(qū)域的邊界，p是上的一點(diǎn)，p是待修復(fù)塊，q為最佳樣本塊。

　　算法的具體步驟如下：

　?。?）根據(jù)圖像的特征結(jié)構(gòu)，求出優(yōu)先權(quán)值最高的點(diǎn)，確定填充的順序。優(yōu)先權(quán)P（p）的計(jì)算公式為：

　　P（p）=C（p）D（p）（1）

　　其中，C（p）是待修復(fù)點(diǎn)p的置信度，用來衡量?鬃p包含的可用信息量。D（p）是數(shù)據(jù)項(xiàng)，反映?鬃p的結(jié)構(gòu)特征。表達(dá)如下：

　　式中q∈時(shí)，c（q）=1，否則c（q）=0。|p|是p像素的數(shù)量，是點(diǎn)p的等照度線方向，np是在點(diǎn)p處的單位法向量，是歸一化因子，一般取值為255。

　　（2）在已知區(qū)域?椎中尋找與?鬃p最相近的樣本塊q，要求q滿足：

　　式中的d（p，q′）是p和q′對(duì)應(yīng)的已知像素點(diǎn)的顏色差的平方和。之后將最佳樣本塊q中對(duì)應(yīng)的像素復(fù)制到待修復(fù)塊p中的未知像素點(diǎn)。

　?。?）p被修復(fù)后，待修復(fù)區(qū)域的范圍和邊界都發(fā)生變化，待修復(fù)區(qū)域點(diǎn)的置信度也有了改變，因此需要更新p內(nèi)所有點(diǎn)的置信度：

　　重復(fù)上述3個(gè)步驟直至完成修復(fù)。

2 改進(jìn)的算法

　　2.1 模板塊大小的自適應(yīng)選擇

　　原始算法中，Criminisi經(jīng)過多次試驗(yàn)分析和比較，最終選擇修復(fù)模板塊的大小固定為9×9。由文獻(xiàn)[7]知對(duì)不同的圖像，采用不同的樣本塊大小進(jìn)行處理，會(huì)得到不同的修復(fù)效果，但過小的模板塊影響修復(fù)的速度，在不影響修復(fù)效果的情況下選取較大的模板塊，能夠提高修復(fù)的效率。為選取最優(yōu)樣本塊，本文利用圖像紋理特征[8]及破損面積自適應(yīng)選擇樣本塊的大小r，通過大量實(shí)驗(yàn)數(shù)據(jù)的擬合，得到式（6）中樣本塊大小選擇和它們之間的關(guān)系：

　　其中，S是圖像受損面積占整幅圖像的百分比，待修復(fù)區(qū)域越大，用較大的樣本塊去修復(fù)，運(yùn)行的速度和修復(fù)的質(zhì)量都有所提高。T建立圖像幾種紋理特征與r選取的關(guān)系，其中I是圖像的粗糙度，G是圖像的熵均值，L是圖像的能量慣性矩。

　　2.2 優(yōu)先權(quán)的改進(jìn)

　　計(jì)算優(yōu)先權(quán)，確定填充順序，使得修補(bǔ)過程有序進(jìn)行，但原始算法采用C（p）和D（p）直接相乘的形式，當(dāng)C（p）急劇下降直趨近為零時(shí)，無論D（p）值多大，都可能會(huì)導(dǎo)致優(yōu)先權(quán)函數(shù)值接近為零，圖像中的結(jié)構(gòu)信息無法作為填充順序的參考，使得圖像填充順序變得不準(zhǔn)確，影響圖像修復(fù)的效果。數(shù)據(jù)項(xiàng)D（p）采用受損邊緣梯度向量垂直的等照度線向量和法線向量相乘的形式，不能有效提取圖像結(jié)構(gòu)信息，本文引入基于偏微分模型中的平滑擴(kuò)散因子D1和D2[5]，將其作為數(shù)據(jù)項(xiàng)，定義新的優(yōu)先權(quán)公式如下：

　　其中置信度添加0.5，保證其不會(huì)迅速降為零，是拉普拉斯梯度，分別表示沿著梯度方向和垂直于梯度方向的二階方向?qū)?shù)，填充順序要考慮這兩個(gè)方向的圖像特征變化，像素變化越小的塊，具有更大的優(yōu)先權(quán)，保證圖像能夠沿著邊緣處平滑擴(kuò)散，避免在平滑區(qū)域產(chǎn)生階梯效應(yīng)，在邊緣處出現(xiàn)信息延伸的現(xiàn)象。

　　2.3 置信度更新改進(jìn)

　　置信度項(xiàng)的更新是Criminisi算法中重要的一步，因?yàn)榇迯?fù)塊p被填充后，未知像素點(diǎn)變?yōu)橐阎c(diǎn)，置信度值發(fā)生變化，修復(fù)塊p和樣本塊q不是完全相等的，它們有一定的結(jié)構(gòu)誤差，這個(gè)誤差會(huì)隨著修復(fù)過程不斷的疊加而增多，填充順序的可信度逐漸降低，最終影響圖像的修復(fù)結(jié)果。提出的改進(jìn)的置信度項(xiàng)更新公式如下：

　　式中Ipi，Iqi分別表示待修復(fù)塊p和樣本塊q的對(duì)應(yīng)已知點(diǎn)的等照度線的曲率，n表示樣本塊中p已知像素點(diǎn)的個(gè)數(shù)，這樣可以使得差異度小的塊有較大的置信度值，減小誤差的累積，避免冗余現(xiàn)象的產(chǎn)生。

　　2.4 本文算法步驟

　?。?）輸入待修復(fù)的彩色圖像，手動(dòng)選擇需要修復(fù)的區(qū)域；

　　（2）按公式（6）選擇最優(yōu)樣本塊的大??；

　?。?）利用公式（8）計(jì)算待修復(fù)區(qū)域的邊界上各點(diǎn)的優(yōu)先權(quán)P（p），確定待修復(fù)區(qū)域內(nèi)的填充順序；

　?。?）在匹配區(qū)域中搜索最佳匹配塊q；

　?。?）將q中對(duì)應(yīng)的圖像信息復(fù)制到待修復(fù)塊p中；

　?。?）利用公式（10）更新置信度項(xiàng)C（p）；

　?。?）重復(fù)步驟（2）~（6），直到整個(gè)待修復(fù)區(qū)域被填充完。

3 實(shí)驗(yàn)結(jié)果和分析

　　本文算法是以MATLAB7.1為仿真平臺(tái)實(shí)現(xiàn)的，硬件環(huán)境是Intel（R）Core（TM）i5-2430M 2.4 GHz處理器，2 GB內(nèi)存。用文獻(xiàn)[4]和本文改進(jìn)的算法對(duì)四幅受損圖像進(jìn)行修復(fù)實(shí)驗(yàn)，如圖2~圖5所示，其中圖2和圖3是對(duì)受損的區(qū)域進(jìn)行填充，本文用峰值信噪比（Peak Signal to Noise Ratio，PSNR）和修復(fù)所需的時(shí)間對(duì)圖像進(jìn)行評(píng)價(jià)，見表1和表2。圖4和圖5是對(duì)目標(biāo)物的移除，在實(shí)際情況中，很難找到原始圖進(jìn)行PSNR對(duì)比，這里主要借用人眼的觀測(cè)和消耗的時(shí)間進(jìn)行評(píng)價(jià)。

　　從表1和表2可以看出，實(shí)驗(yàn)圖1和實(shí)驗(yàn)圖2改進(jìn)算法的PSNR值比文獻(xiàn)[4]要高，而四個(gè)實(shí)驗(yàn)的修復(fù)速度基本上提高了30%~50%。從視覺上比較可以看出：圖2（c）出現(xiàn)塊匹配錯(cuò)誤，使得圖像有明顯修復(fù)痕跡，圖2（d）減弱了修復(fù)的錯(cuò)誤匹配，避免了修復(fù)區(qū)域不均的現(xiàn)象。圖3（c）中圖像明顯沒有很好地進(jìn)行填充修復(fù)，圖3（c）從視覺上看基本與原圖無差。圖4（c）對(duì)人物的填充，在修復(fù)的邊緣處，有明顯的紋理延伸，房頂沒有得到較好修復(fù)，陸地上的草延伸至水中，圖4（d）修復(fù)的結(jié)果在邊緣處能夠平滑過渡，獲得較好修復(fù)效果。圖5（c）明顯沒有修復(fù)完全，有殘余的飛機(jī)尾翼未被填充，而圖5（d）的結(jié)果更為自然。

4 結(jié)論

　　本文在文獻(xiàn)[4]的基礎(chǔ)上進(jìn)行改進(jìn)。根據(jù)圖像破損的面積及其紋理特征，自適應(yīng)選擇最優(yōu)的樣本塊大小。引入平滑擴(kuò)散因子，改進(jìn)優(yōu)先權(quán)計(jì)算公式，增強(qiáng)圖像結(jié)構(gòu)特征的影響，避免因置信度的急劇衰減而導(dǎo)致的錯(cuò)誤修復(fù)順序。提出新的置信度更新方式，減少在修復(fù)過程中，因待修復(fù)塊和樣本塊之間的結(jié)構(gòu)差異而累計(jì)的誤差。實(shí)驗(yàn)結(jié)果表明，本文改進(jìn)的算法在提高修復(fù)速度的同時(shí)，能夠獲得更好的修復(fù)效果。

　　參考文獻(xiàn)

　　[1] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting[C]. Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM Press，2000：417-424.

　　[2] CHAN T F，SHEN J. Mathematical models for local  non-texture inpaintings[J]. SIAM Journal on Applied Math， 2001，62（3）：1019-1043.

　　[3] DRORI I， DANIEL C-O， YESHURUN H. Fragment based image completion[J]. ACM Transactions on Graphics， 2003，22（3）： 303-312.

　　[4] CRIMINISI A， PEREZ P， TOYAMA K. Region filling and object removal by exemplar-based image inpainting[J]. IEEE transactions on image processing，2004，13（9）：1200-1212.

　　[5] 王遠(yuǎn)敏，朱曉明，孫雁飛，等.基于模板的圖像修復(fù)算法優(yōu)先權(quán)的改進(jìn)[J].信息技術(shù)，2008（5）：64-67.

　　[6] 張偉偉，何凱，孟春芝.自適應(yīng)選取樣本塊大小的紋理合成方法[J].計(jì)算機(jī)工程與應(yīng)用，2012：48（17）：170-173.

　　[7] 潘姣君，謝伙生.結(jié)合灰度共生矩陣和熵的圖像修復(fù)算法[J].微型機(jī)與應(yīng)用，2012，31（21）：44-46.

　　[8] 賀雙雙，戴青云.綜合紋理和形狀特征的外觀專利圖像檢索算法研究[J].微型機(jī)與應(yīng)用，2013，32（4）：42-44，47.