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

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

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

中圖分類(lèi)號(hào)： TN911.73?34； TP391 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ū)域的鄰域信息對(duì)受損區(qū)域按照一定的規(guī)則進(jìn)行填充，使修復(fù)后的圖像盡可能地與原圖保持一致，具有較好的視覺(jué)效果。其在文物保護(hù)、藝術(shù)品修補(bǔ)、影視特技、多余物體消除和虛擬現(xiàn)實(shí)等領(lǐng)域中具有廣泛的實(shí)際應(yīng)用價(jià)值，現(xiàn)已成為圖像處理和計(jì)算機(jī)視覺(jué)領(lǐng)域的研究熱點(diǎn)[1?2]。

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

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

3 修復(fù)算法

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

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

（2） 采用9×9的模板，利用本文改進(jìn)的優(yōu)先級(jí)計(jì)算方法計(jì)算邊界上像素的優(yōu)先級(jí)，找到優(yōu)先級(jí)最高的像素點(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）步記錄的較大模塊的邊界，對(duì)其采用FMM算法再進(jìn)行一次快速修復(fù)，以消除邊界效應(yīng)。

4 仿真實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)1： 修復(fù)效果比較

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

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

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

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

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

[2] 翟東海，肖杰，魚(yú)江，等.基于自適應(yīng)模板的圖像修復(fù)算法[J].計(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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] 李?lèi)?ài)菊，鈕文良.基于改進(jìn)Criminisi算法的圖像修復(fù)[J].計(jì)算機(jī)工程與應(yīng)用，2014，50（18）：167?170.

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

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

[12] 李俊栢，黃文清，黃牧，等.改進(jìn)的Criminisi圖像修復(fù)算法[J].工業(yè)控制計(jì)算機(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.