王文豪++周靜波++高尚兵++嚴(yán)云洋

摘 要： 針對Criminisi算法在修復(fù)時會出現(xiàn)結(jié)構(gòu)斷裂和誤匹配問題，在原有算法基礎(chǔ)上提出一些新的改進(jìn)思想，改進(jìn)優(yōu)先級函數(shù)的計算方法，將優(yōu)先級函數(shù)表示為數(shù)據(jù)項、置信度項和鄰域相關(guān)性項的加權(quán)和，以保證圖像結(jié)構(gòu)信息的連續(xù)性。設(shè)計一種樣本塊大小可變的算法，以增強(qiáng)局部協(xié)調(diào)性和邊界的平滑性。改進(jìn)模板間相似性度量方法，融入顏色直方圖，以提高模板匹配的準(zhǔn)確性。實驗結(jié)果表明，該方法能夠彌補(bǔ)Criminisi算法的不足，獲得較好的視覺效果，提高圖像的修復(fù)質(zhì)量。

關(guān)鍵詞： Criminisi算法； 圖像修復(fù)； 可變大小樣本塊； 模塊相似性度量； 顏色直方圖

中圖分類號： TN911.73?34； TP391 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）11?0053?05

Optimization of Criminisi algorithm for image inpainting

WANG Wenhao， ZHOU Jingbo， GAO Shangbing， YAN Yunyang

（Huaiyin Institute of Technology， Huaian 223001， China）

Abstract： Since the Criminisi algorithm has the problems of structure fracture and wrong matching while making image inpainting， some new improvement thoughts are proposed on the basis of the original algorithm， with which the calculation method of the priority function is improved， and the priority function is represented as the weighted sum of the data item， confidence coefficient item and neighborhood correlation term to ensure the information continuity of the image structure. An algorithm of variable?size exemplar block was designed to enhance the local harmony and boundary smoothness. The similarity measure method for templates was improved， and integrated with color histogram to improve the accuracy of template matching. The experimental results show that the method can make up the deficiencies of Criminisi algorithm， obtain better visual effect， and improve the quality of image inpainting.

Keywords： Criminisi algorithm； image inpainting； variable?size exemplar block； module similarity measure； color histogram

0 引 言

圖像修復(fù)技術(shù)主要利用圖像受損區(qū)域的鄰域信息對受損區(qū)域按照一定的規(guī)則進(jìn)行填充，使修復(fù)后的圖像盡可能地與原圖保持一致，具有較好的視覺效果。其在文物保護(hù)、藝術(shù)品修補(bǔ)、影視特技、多余物體消除和虛擬現(xiàn)實等領(lǐng)域中具有廣泛的實際應(yīng)用價值，現(xiàn)已成為圖像處理和計算機(jī)視覺領(lǐng)域的研究熱點(diǎn)[1?2]。

目前圖像修復(fù)算法可以分為兩類：一類是基于結(jié)構(gòu)的方法[3]，這類方法主要是通過計算等照度的方向，將受損區(qū)域周圍已知信息平滑地傳進(jìn)受損區(qū)域內(nèi)部完成圖像的修復(fù)，其較為經(jīng)典的模型有BSCB[4]，TV（Total Variation）[5]，CDD（Curvature?Driven Diffusions）[6]三個模型，這類算法對修復(fù)局部狹長的區(qū)域有較好的效果，但對大面積破損和紋理豐富的圖像，修復(fù)效果較差；另一類是基于紋理合成的方法[7]，這類算法主要通過在受損區(qū)域選擇合適的紋理塊，然后從完好區(qū)域?qū)ふ遗c之最相似的塊代替該塊，這類算法中最具有代表性的是Criminisi等人提出的基于樣本塊修復(fù)算法[8]，在修復(fù)大面積受損區(qū)域時可以獲得較好的修復(fù)效果，但該算法在搜索最優(yōu)修復(fù)塊和最優(yōu)匹配塊時存在一些不足[9]。于是研究者們提出了一些改進(jìn)算法：文獻(xiàn)[10]提出一種基于樣本塊大小的自適應(yīng)圖像修復(fù)算法，根據(jù)圖像的梯度信息自適應(yīng)地調(diào)整樣本塊的大小，但極易出現(xiàn)結(jié)構(gòu)不連續(xù)現(xiàn)象。文獻(xiàn)[11]將優(yōu)先級函數(shù)中的置信度修改成指數(shù)函數(shù)形式，以避免其隨著修復(fù)過程的進(jìn)行而迅速下降為零，從而影響修復(fù)順序，但該方法修復(fù)的圖像存在邊界效應(yīng)。文獻(xiàn)[12]將優(yōu)先級函數(shù)表示為數(shù)據(jù)項和置信度的加權(quán)和，改善修復(fù)順序，但在修復(fù)邊緣處有錯層現(xiàn)象。文獻(xiàn)[13]采用局部搜索策略，縮小樣本塊的搜索范圍，提高算法運(yùn)行速度，但匹配不夠準(zhǔn)確。文獻(xiàn)[14]提出一種基于結(jié)構(gòu)傳播的圖像修復(fù)算法，取得了較好的修復(fù)效果，但算法時間復(fù)雜度較高。

上述文獻(xiàn)沒有很好地解決結(jié)構(gòu)連續(xù)性和誤匹配問題。本文在Criminisi算法的基礎(chǔ)上加入一些有意義的改進(jìn)，通過增加鄰域相關(guān)性項改進(jìn)優(yōu)先級計算方法，使得修復(fù)順序更加可靠；利用鄰域相關(guān)信息自動調(diào)整樣本塊大小，以適應(yīng)不同紋理和結(jié)構(gòu)的修復(fù)；在模塊相似性計算中融入顏色直方圖，提高匹配的準(zhǔn)確性。實驗表明該方法能取得較好的修復(fù)效果。

3 修復(fù)算法

綜合第2節(jié)講述的改進(jìn)方法，最終的改進(jìn)算法流程如下：

（1） 讀入受損圖像并進(jìn)行預(yù)處理，確定修復(fù)邊界

（2） 采用9×9的模板，利用本文改進(jìn)的優(yōu)先級計算方法計算邊界上像素的優(yōu)先級，找到優(yōu)先級最高的像素點(diǎn)；

（3） 利用本文提出的樣本塊大小可變算法確定以點(diǎn)為中心的樣本塊的最大尺寸，若該尺寸大于13，記錄其邊界；

（4） 按照本文改進(jìn)的模板相似性度量準(zhǔn)則搜索最優(yōu)匹配塊；

（5） 將最優(yōu)模塊的像素信息復(fù)制到相應(yīng)的待修復(fù)模塊中的未知部分，并更新置信度和優(yōu)先權(quán)等信息；

（6） 若邊界不為空，轉(zhuǎn)到第（2）步繼續(xù)執(zhí)行；否則，轉(zhuǎn)到下一步；

（7） 根據(jù)第（3）步記錄的較大模塊的邊界，對其采用FMM算法再進(jìn)行一次快速修復(fù)，以消除邊界效應(yīng)。

4 仿真實驗結(jié)果與分析

為了驗證算法的有效性，本文在內(nèi)存2 GB、主頻2.93 GHz的雙核奔騰處理器上，使用VC++和OpenCV編程進(jìn)行仿真實驗，并與Criminisi，文獻(xiàn)[12，14]修復(fù)結(jié)果比較，實驗中，文中的一些參數(shù)由實驗經(jīng)驗得出，其取值分別為：。

實驗1： 修復(fù)效果比較

圖8和圖9是兩組實驗結(jié)果比較圖。圖8為“十”字型的待修復(fù)區(qū)域，結(jié)構(gòu)信息較為復(fù)雜。圖8（c）為Criminisi算法修復(fù)結(jié)果，可以看出，有明顯的裂縫和錯誤匹配情形，這主要是由修復(fù)順序出現(xiàn)偏差和匹配方式單一導(dǎo)致的。圖8（d）為文獻(xiàn)[12]的修復(fù)結(jié)果，該算法雖然改進(jìn)了優(yōu)先級的計算方式，但由于沒有考慮待修復(fù)區(qū)域周邊的信息和圖像特征信息，以致于還出現(xiàn)了斷裂和錯誤匹配；圖8（e）為文獻(xiàn)[14]修復(fù)結(jié)果，效果較好，但時間復(fù)雜度較高。圖8（f）為本文方法的修復(fù)效果，可以看出，雖然存在少許錯誤匹配，豎著的窗框上也存在修復(fù)痕跡，但總體效果而言比圖8（c）、圖8（d）的修復(fù)效果要好，與圖8（f）相差無幾。這主要是因為該算法能夠根據(jù)待修復(fù)區(qū)域周邊的信息，自動調(diào)整樣本塊的大小、改變修復(fù)順序，在模板匹配時，考慮了更多的因素。

圖9是去除較大物體之后的背景修復(fù)，該圖的紋理和非結(jié)構(gòu)都較復(fù)雜，本文的修復(fù)效果如圖9（f）所示，沒有出現(xiàn)紋理不和諧的地方，而Criminisi算法修復(fù)的結(jié)果在草地上出現(xiàn)欄桿的一部分，文獻(xiàn)[12]修復(fù)的結(jié)果有明顯的修復(fù)痕跡，文獻(xiàn)[14]修復(fù)的結(jié)果與本文相當(dāng)。

實驗2： 算法運(yùn)行時間比較

表1是各個算法在上述實驗結(jié)果耗費(fèi)的時間對比。從表1中可以看出，文獻(xiàn)[12]與Criminisi算法運(yùn)行時間相差無幾，這是因為文獻(xiàn)[12]只是將Criminisi算法的優(yōu)先權(quán)的計算方式由乘法改為加法。本文方法由于在確定樣本塊大小、優(yōu)先極計算和樣本塊匹配時需要花費(fèi)額外的時間，因此時間復(fù)雜度比Criminisi算法高一些，然而修復(fù)質(zhì)量卻有較大提高。文獻(xiàn)[14]雖然修復(fù)效果較好，然而其時間復(fù)雜度太高。

從以上兩組實驗比較結(jié)果可以看出，不論是修復(fù)受損區(qū)域，還是去除較大的多余目標(biāo)，改進(jìn)算法比Criminisi算法具有更好的修復(fù)效果，但算法耗費(fèi)的時間比Criminisi算法多。

5 結(jié) 語

本文在分析Criminisi算法的基礎(chǔ)上，針對其存在的缺陷，通過引入待修復(fù)塊周邊像素的信息和顏色直方圖，對Criminisi算法的優(yōu)先級計算方式、樣本塊大小和相似性度量等方面進(jìn)行了一些有意義的改進(jìn)，實驗結(jié)果表明，本文的方法比Criminisi算法可以獲得更好的視覺效果，但對于具有曲線邊界的物體，修復(fù)效果還有待提高。

參考文獻(xiàn)

[1] 韓明珠，郭樹旭，臧玲玲，等.基于樣本塊的圖像修復(fù)改進(jìn)算法[J].計算機(jī)工程與應(yīng)用，2015，51（16）：192?194.

[2] 翟東海，肖杰，魚江，等.基于自適應(yīng)模板的圖像修復(fù)算法[J].計算機(jī)應(yīng)用，2013，33（10）：2891?2894.

[3] CHAN T， SHEN J. Mathematical models for local non?texture inpaintings [J]. SIAM journal on applied mathematics， 2001， 62（3）： 1019?1043.

[4] BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting [C]// Proceedings of 2000 ACM Computer Graphics， Annual Conference Series. New Orleans： ACM， 2000： 417?424.

[5] CHAN T F， SHEN J H. Mathematical models for local non?texture inpainting [J]. Journal of applied mathematics， 2001， 62（3）： 1019?1043.

[6] CHAN T F， SHEN J H. Non?texture inpainting by curvature?driven diffusions （CDD） [J]. Journal of visual communication and image representation， 2001， 12（4）： 436?449.

[7] 任澍，唐向宏，康佳倫.紋理和邊緣特征相結(jié)合的圖像修復(fù)算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2013，25（11）：1682?1693.

[8] 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.

[9] 李愛菊，鈕文良.基于改進(jìn)Criminisi算法的圖像修復(fù)[J].計算機(jī)工程與應(yīng)用，2014，50（18）：167?170.

[10] 孟春芝，何凱，焦青蘭.自適應(yīng)樣本塊大小的圖像修復(fù)方法[J].中國圖象圖形學(xué)報，2012，17（3）：237?241.

[11] 劉業(yè)妃，王福龍，奚祥艷，等.改進(jìn)的Criminisi圖像修復(fù)算法[J].小型微型計算機(jī)系統(tǒng)，2014，35（12）：2754?2758.

[12] 李俊栢，黃文清，黃牧，等.改進(jìn)的Criminisi圖像修復(fù)算法[J].工業(yè)控制計算機(jī)，2014，27（7）：127?129.

[13] ZHOU H， ZHANG J. Adaptive patch size determination for patch?based image completion [C]// Proceedings of 2010 IEEE 17th International Conference on Image Processing. [S.l.]： IEEE， 2010： 421?424.

[14] SUN Jian， YUAN Lu， JIA Jiaya， et al. Image completion with structure propagation [J]. ACM transactions on graphics， 2005， 24（3）： 861?868.

[15] TELA A. An image inpainting technique based on the fast marching method [J]. Journal of graphics tools， 2004， 9（1）： 23?33.