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

　　關鍵詞： 圖像修復；樣本塊；優先權；置信度的更新

0 引言

　　圖像修復的本質是通過不完整信息重新構造出完整信息，對圖像上信息缺損區域進行填充，恢復受損的圖像，讓觀察者無法用肉眼看出圖像曾損壞過。對圖像修復技術的深入研究也是當前計算機視覺領域中的一個熱點。

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

1 Criminisi算法簡介

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

　　算法的具體步驟如下：

　?。?）根據圖像的特征結構，求出優先權值最高的點，確定填充的順序。優先權P（p）的計算公式為：

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

　　其中，C（p）是待修復點p的置信度，用來衡量?鬃p包含的可用信息量。D（p）是數據項，反映?鬃p的結構特征。表達如下：

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

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

　　式中的d（p，q′）是p和q′對應的已知像素點的顏色差的平方和。之后將最佳樣本塊q中對應的像素復制到待修復塊p中的未知像素點。

　　（3）p被修復后，待修復區域的范圍和邊界都發生變化，待修復區域點的置信度也有了改變，因此需要更新p內所有點的置信度：

　　重復上述3個步驟直至完成修復。

2 改進的算法

　　2.1 模板塊大小的自適應選擇

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

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

　　2.2 優先權的改進

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

　　其中置信度添加0.5，保證其不會迅速降為零，是拉普拉斯梯度，分別表示沿著梯度方向和垂直于梯度方向的二階方向導數，填充順序要考慮這兩個方向的圖像特征變化，像素變化越小的塊，具有更大的優先權，保證圖像能夠沿著邊緣處平滑擴散，避免在平滑區域產生階梯效應，在邊緣處出現信息延伸的現象。

　　2.3 置信度更新改進

　　置信度項的更新是Criminisi算法中重要的一步，因為待修復塊p被填充后，未知像素點變為已知點，置信度值發生變化，修復塊p和樣本塊q不是完全相等的，它們有一定的結構誤差，這個誤差會隨著修復過程不斷的疊加而增多，填充順序的可信度逐漸降低，最終影響圖像的修復結果。提出的改進的置信度項更新公式如下：

　　式中Ipi，Iqi分別表示待修復塊p和樣本塊q的對應已知點的等照度線的曲率，n表示樣本塊中p已知像素點的個數，這樣可以使得差異度小的塊有較大的置信度值，減小誤差的累積，避免冗余現象的產生。

　　2.4 本文算法步驟

　?。?）輸入待修復的彩色圖像，手動選擇需要修復的區域；

　?。?）按公式（6）選擇最優樣本塊的大??；

　?。?）利用公式（8）計算待修復區域的邊界上各點的優先權P（p），確定待修復區域內的填充順序；

　　（4）在匹配區域中搜索最佳匹配塊q；

　?。?）將q中對應的圖像信息復制到待修復塊p中；

　?。?）利用公式（10）更新置信度項C（p）；

　?。?）重復步驟（2）~（6），直到整個待修復區域被填充完。

3 實驗結果和分析

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

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

4 結論

　　本文在文獻[4]的基礎上進行改進。根據圖像破損的面積及其紋理特征，自適應選擇最優的樣本塊大小。引入平滑擴散因子，改進優先權計算公式，增強圖像結構特征的影響，避免因置信度的急劇衰減而導致的錯誤修復順序。提出新的置信度更新方式，減少在修復過程中，因待修復塊和樣本塊之間的結構差異而累計的誤差。實驗結果表明，本文改進的算法在提高修復速度的同時，能夠獲得更好的修復效果。

　　參考文獻

　　[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] 王遠敏，朱曉明，孫雁飛，等.基于模板的圖像修復算法優先權的改進[J].信息技術，2008（5）：64-67.

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

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

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