改進(jìn)的基于樣本塊的圖像修復(fù)方法

常 晨，何建農(nóng)

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

改進(jìn)的基于樣本塊的圖像修復(fù)方法

常 晨，何建農(nóng)

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

在研究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í)間。

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

0 引言

圖像修復(fù)的本質(zhì)是通過不完整信息重新構(gòu)造出完整信息，對圖像上信息缺損區(qū)域進(jìn)行填充，恢復(fù)受損的圖像，讓觀察者無法用肉眼看出圖像曾損壞過。對圖像修復(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)，對小尺度破損的圖像的修復(fù)效果較好，但對修復(fù)破損區(qū)域較大的圖像時(shí)，計(jì)算量大，耗時(shí)長，易產(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ù)的自然順暢，其簡單有效的特點(diǎn)使其成為紋理修復(fù)的經(jīng)典算法。但是利用該算法進(jìn)行修復(fù)的圖像會(huì)產(chǎn)生冗余，出現(xiàn)結(jié)構(gòu)不連續(xù)現(xiàn)象，影響最終的修復(fù)效果。本文以Criminisi算法為基礎(chǔ)，對其不足之處進(jìn)行改進(jìn)，自適應(yīng)選擇最佳樣本塊大小，改進(jìn)優(yōu)先權(quán)公式和置信度更新方式，使紋理和結(jié)構(gòu)信息得到有效利用。通過實(shí)驗(yàn)結(jié)果對比分析，證明改進(jìn)的方法不僅能得到較好的修復(fù)結(jié)果，且能夠大幅度提高修復(fù)的速度。

1 Criminisi算法簡介

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為最佳樣本塊。

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

算法的具體步驟如下：

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

其中，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ù)量，▽Ip⊥是點(diǎn) p的等照度線方向，np是 δΩ在點(diǎn) p處的單位法向量，α是歸一化因子，一般取值為255。

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

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

（3）ψ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］知對不同的圖像，采用不同的樣本塊大小進(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ì)迅速降為零，▽u是拉普拉斯梯度，uηη與 uξξ分別表示沿著梯度方向和垂直于梯度方向的二階方向?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的對應(yīng)已知點(diǎn)的等照度線的曲率，n表示樣本塊中 ψp已知像素點(diǎn)的個(gè)數(shù)，這樣可以使得差異度小的塊有較大的置信度值，減小誤差的累積，避免冗余現(xiàn)象的產(chǎn)生。

2.4 本文算法步驟

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

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

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

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

（5）將 ψq中對應(yīng)的圖像信息復(fù)制到待修復(fù)塊 ψp中；

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

（7）重復(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.4GHz處理器，2 GB內(nèi)存。用文獻(xiàn)［4］和本文改進(jìn)的算法對四幅受損圖像進(jìn)行修復(fù)實(shí)驗(yàn)，如圖2～圖5所示，其中圖2和圖3是對受損的區(qū)域進(jìn)行填充，本文用峰值信噪比（Peak Signal to Noise Ratio，PSNR）和修復(fù)所需的時(shí)間對圖像進(jìn)行評價(jià)，見表1和表2。圖4和圖5是對目標(biāo)物的移除，在實(shí)際情況中，很難找到原始圖進(jìn)行 PSNR對比，這里主要借用人眼的觀測和消耗的時(shí)間進(jìn)行評價(jià)。

圖2 實(shí)驗(yàn)圖1

圖3 實(shí)驗(yàn)圖2

圖4 實(shí)驗(yàn)圖3

圖5 實(shí)驗(yàn)圖4

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

從表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）對人物的填充，在修復(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ù)效果。

［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］王遠(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.

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

常晨，何建農(nóng).改進(jìn)的基于樣本塊的圖像修復(fù)方法［J］.微型機(jī)與應(yīng)用，2015，34（23）：45-47.

2015-09-13）

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

何建農(nóng)（1960-），女，副教授，碩士生導(dǎo)師，主要研究方向：智能圖像處理、信息安全、網(wǎng)絡(luò) GIS。