常 晨，何建農

（福州大學 數(shù)學與計算機科學學院，福建 福州 350116）

改進的基于樣本塊的圖像修復方法

常 晨，何建農

（福州大學 數(shù)學與計算機科學學院，福建 福州 350116）

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

圖像修復；樣本塊；優(yōu)先權；置信度的更新

0 引言

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

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

1 Criminisi算法簡介

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

圖1 基于樣本塊算法的過程圖

算法的具體步驟如下：

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

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

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

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

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

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

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

2 改進的算法

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

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

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

2.2 優(yōu)先權的改進

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

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

2.3 置信度更新改進

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

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

2.4 本文算法步驟

（1）輸入待修復的彩色圖像，手動選擇需要修復的區(qū)域Ω；

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

（3）利用公式（8）計算待修復區(qū)域的邊界上各點的優(yōu)先權 P（p），確定待修復區(qū)域內的填充順序；

（4）在匹配區(qū)域 Φ中搜索最佳匹配塊 ψq；

（5）將 ψq中對應的圖像信息復制到待修復塊 ψp中；

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

（7）重復步驟（2）～（6），直到整個待修復區(qū)域被填充完。

3 實驗結果和分析

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

圖2 實驗圖1

圖3 實驗圖2

圖4 實驗圖3

圖5 實驗圖4

表1 兩種算法的PSNR值 （dB）

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

4 結論

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

［1］BERTALMIOm，SAPIRO G，CASELLES V，et al.Image inpainting［C］.Proceedings of the 27th Annual Conference on ComputerGraphicsand Interactive Techniques.New York：ACM Press，2000：417-424.

［2］CHAN T F，SHEN J.Mathematical models for local nontextureinpaintings［J］.SIAM Journalon 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］王遠敏，朱曉明，孫雁飛，等.基于模板的圖像修復算法優(yōu)先權的改進［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.

Improvement of image inpainting method based on sample patch

Chang Chen，He Jiannong
（College of Mathematics and Computer Science，F(xiàn)uzhou University，F(xiàn)uzhou 350116，China）

Based on the research of Criminisi repair algorithm，an improved image inpainting method based on sample block is proposed.According to the area of image restoration and texture feature，adaptively select sample block size to improve the speed of repair.New data items are used to improve the priority formula.Using new data items and the improved priority formula to avoid the step effect.The new formula of the reliability is introduced.The curvature distance is introduced to reduce the accumulated error and improve the accuracy of the sequence.Experiments show that the improved method can effectively improve the repair effect，reduce the time needed for repair.

image restoration；sample patch；priority；update of confidence term

TP391

A

1674-7720（2015）23-0045-03

常晨，何建農.改進的基于樣本塊的圖像修復方法［J］.微型機與應用，2015，34（23）：45-47.

2015-09-13）

常晨（1991-），女，碩士研究生，主要研究方向：圖像處理。

何建農（1960-），女，副教授，碩士生導師，主要研究方向：智能圖像處理、信息安全、網絡 GIS。