基于可變大小模板的改進(jìn)圖像修復(fù)算法*

張 嵩，周旭亞

(杭州電子科技大學(xué)通信工程學(xué)院，杭州 310018)

圖像修復(fù)，或者圖像補(bǔ)全，簡單地說就是利用圖像中的已知區(qū)域信息來填充待修復(fù)區(qū)域。圖像修復(fù)的概念最早由Bertalmio等人提出［1］，他們同時(shí)給出了一種有效的基于偏微分方程(PDE)的算法，即將修復(fù)轉(zhuǎn)化為求解一個(gè)特殊的偏微分方程。類似的算法還有不少［2－4］?；赑DE模型的算法對修復(fù)局部狹長的區(qū)域比較有效，但對大面積缺失或紋理信息豐富的圖像，此類算法修復(fù)效果不夠理想。非參數(shù)紋理合成是圖像修復(fù)的另外一類重要方法，其基本思想最早可追溯至Efros與 Leung 的工作［5］。在此基礎(chǔ)上，Criminisi等人［6］提出了一種全新的基于模板的圖像修復(fù)算法，被公認(rèn)為修復(fù)技術(shù)方面的重要突破，影響甚大。

但是Criminisi算法仍存在缺點(diǎn)，比如修復(fù)后圖像紋理斷層，時(shí)間復(fù)雜度較高等，對其的改進(jìn)仍然是圖像修復(fù)領(lǐng)域的一個(gè)重要研究方向。譬如，一種徹底的解決之道是所謂的全局優(yōu)化方法［7－10］，即將修復(fù)問題轉(zhuǎn)化為最小化能量泛函。不過，這類方法的復(fù)雜度太大，應(yīng)用上有不小的限制。我們認(rèn)為，Criminisi算法框架目前仍是修復(fù)效果與實(shí)現(xiàn)代價(jià)之間的最佳折衷。因此，我們在Criminisi基本算法框架之上融合了一些新的改進(jìn)元素:我們采用了基于可變大小模板的塊搜索方案；并結(jié)合改進(jìn)的修復(fù)像素信度(confidence)更新公式及局部搜索模式，以期獲得較好的算法綜合性能。仿真結(jié)果表明系統(tǒng)整體性能確實(shí)得到較大提高。

本文第二節(jié)簡單介紹Criminisi算法流程以方便后續(xù)論述，第三節(jié)具體介紹改進(jìn)方法，第四節(jié)給出實(shí)驗(yàn)結(jié)果比較，第五節(jié)給出總結(jié)與展望。

1 Criminisi算法

為了更好地介紹所提出的改進(jìn)方案，首先簡述Criminisi算法。Criminisi算法本質(zhì)上仍然屬于紋理合成方法，但卻能同時(shí)修復(fù)紋理和結(jié)構(gòu)信息。假設(shè)圖像為A，待修復(fù)區(qū)域?yàn)棣福阎?或已修復(fù))區(qū)域記為AΩ，當(dāng)前迭代次數(shù)用t表示，Criminisi算法重復(fù)以下步驟直至所有像素都被修復(fù)。

步驟1:確定當(dāng)前修復(fù)邊界?Ωt，若?Ωt=?，算法退出。

步驟2:對邊界上的每一點(diǎn)p，以點(diǎn)p為中心的待修復(fù)塊記為Ψp。對每個(gè)待修復(fù)邊界點(diǎn)計(jì)算優(yōu)先權(quán)P(p)如下:

其中，信度項(xiàng)C(p)定義為:

|Ψp|是塊或模板大小，也即模板像素總數(shù)。初始化時(shí)，對于待修復(fù)區(qū)域所有像素C(p)置0，其他已知像素則置為1。數(shù)據(jù)項(xiàng)D(p)試圖反映點(diǎn)p附近圖像結(jié)構(gòu)強(qiáng)度:

這里α是歸一化因子，np是點(diǎn)p處邊界?Ωt的法線單位向量，⊥表示向量90°旋轉(zhuǎn)。

步驟3:找出具有最大優(yōu)先權(quán)的待修復(fù)塊Ψp*。

步驟4:在已知(或已修復(fù))區(qū)域中搜索與Ψp*最相似的模板Ψq*:

步驟5:把Ψq*中相應(yīng)區(qū)域的像素值復(fù)制到Ψp*中未知區(qū)域。

步驟6:更新信度:

2 改進(jìn)方案

Criminisi算法是一種貪婪算法，本質(zhì)上是非最優(yōu)(suboptimal)的，但仍不失為兼顧性能與代價(jià)的較好選擇。本文在保持算法基本框架不變的情況下加入了一些有意義的改進(jìn)，以下進(jìn)行詳述。

2.1 基于可變大小模板的匹配搜索

對基于紋理合成的串行修復(fù)算法來說，前面模塊的匹配搜索精度直接影響到后續(xù)塊的修復(fù)效果。這其中模板大小是一個(gè)很關(guān)鍵的參數(shù)。單從匹配精度而言，應(yīng)當(dāng)選擇較小的模板；而從圖像正則性及算法復(fù)雜性角度，則希望選擇較大的模板。Criminisi算法采用固定模板大小，但要設(shè)定折衷上述各點(diǎn)并適應(yīng)不同圖像特征的模板大小參數(shù)實(shí)際上是不可能的，這就構(gòu)成了Criminisi算法的一個(gè)重要不足。本文針對性地提出可變大小模板搜索框架，并對具體的搜索程序進(jìn)行了細(xì)致設(shè)計(jì)。

圖1 可變大小模板的匹配

如圖1所示，p*為當(dāng)前修復(fù)像素，q為目標(biāo)像素。我們從某一最小模板大小PSmin(比如5×5)開始進(jìn)行當(dāng)前模塊與目標(biāo)模板之間的匹配，然后逐漸增大模板大小，從5×5到7×7，9×9 等等，直到獲得最佳匹配效果。由于相鄰大小模板或塊成嵌套關(guān)系，因此在模板增大匹配過程中，每次只需對圖1中的環(huán)狀區(qū)域進(jìn)行增量計(jì)算，而勿需對共同部分重復(fù)處理。另外，因模板大小是可變的，我們采用均方誤差(MSD)而不是誤差平方和(SSD)作為相異性測度:

其中n表示當(dāng)前模板尺寸，|Σn|是塊Ψp*中的已知像素個(gè)數(shù)?？紤]到圖像正則性與計(jì)算代價(jià)，我們還在相異性測度中結(jié)合了與模板大小相關(guān)的項(xiàng)，如下定義:

引入logn項(xiàng)的目的是鼓勵(lì)大模板匹配，由此形成的廣義測度有點(diǎn)類似于時(shí)間序列建模中的Akaike準(zhǔn)則。兩點(diǎn)間的匹配過程可由以下的偽代碼緊湊描述:

其中PSmax為設(shè)定的最大模板大小。第四行中的條件語句意味著，一旦發(fā)現(xiàn)模板匹配效果有下降的趨勢就終止模板擴(kuò)大過程，這樣能達(dá)到精度與計(jì)算復(fù)雜度的較好平衡。匹配結(jié)束后得到的最優(yōu)相異性測度記為M(Ψq，Ψp*)。

通過對已知區(qū)域進(jìn)行搜索，得到最優(yōu)匹配模板:

所定義的廣義相異性測度使不同目標(biāo)點(diǎn)之間匹配效果的合理比較成為可能。

2.2 信度更新方式的修正

Criminisi算法在更新信度時(shí)，直接用C(p*)更新本次修復(fù)像素的信度。這樣做沒有考慮到本次模板匹配的精度，明顯有缺陷。我們將信度更新的方式修正為:

也即匹配效果越差，修復(fù)信度也應(yīng)越小，反之亦然。

2.3 模板局部匹配搜索

Criminisi算法的時(shí)間代價(jià)主要是最優(yōu)匹配模板的搜索。為了減小時(shí)間復(fù)雜度，我們采用局部搜索，也即將搜索區(qū)域限制在以當(dāng)前待修復(fù)點(diǎn)為中心的一個(gè)窗口中。這樣做能使計(jì)算復(fù)雜度大幅減少，而修復(fù)精度的損失并不大。

3 實(shí)驗(yàn)結(jié)果

本文在VC++下進(jìn)行實(shí)驗(yàn)，修復(fù)試驗(yàn)包括全彩自然圖像的物體去除(object removal)以及已知圖像的修復(fù)仿真。處理器平臺為3GHZ的Pentium Dual-Core E5700 CPU。所有實(shí)驗(yàn)中，PSmin設(shè)為 5×5，PSmax為17×17；局部搜索窗口大小定為51×51。需要說明的是，在計(jì)算邊界?Ωt上的像素點(diǎn)修復(fù)優(yōu)先權(quán)時(shí)，我們采用固定的模板大小(9×9)。

3.1 修復(fù)效果比較

圖2～圖6是對幾幅自然圖像進(jìn)行物體去除試驗(yàn)的結(jié)果。圖2是經(jīng)典的Bungee圖像，可以看出，改進(jìn)算法在修復(fù)視覺效果方面有明顯提高。對照圖2(c)與圖2(d)，Criminisi算法修復(fù)結(jié)果中的贗像，譬如不連續(xù)的屋頂及延伸到水中的植被等通過改進(jìn)算法基本得到消除。圖3和圖4分別是Criminisi算法和改進(jìn)算法的修復(fù)過程。圖5與圖6是另外兩幅典型圖像的修復(fù)效果，改進(jìn)算法都表現(xiàn)出類似的優(yōu)越性。

圖2

圖3 Criminisi算法修復(fù)過程

圖4 改進(jìn)算法修復(fù)過程

圖7是對已知圖像進(jìn)行修復(fù)仿真實(shí)驗(yàn)的結(jié)果。對這種情況還可計(jì)算修復(fù)客觀效果，也即結(jié)果圖像與原圖像間的PSNR，具體數(shù)據(jù)見表1，同樣證明了修復(fù)效果的提升。

圖5

圖6

圖7

3.2 時(shí)間復(fù)雜度比較

表1同時(shí)列出了Criminisi算法和改進(jìn)算法的時(shí)間成本?？梢钥闯?，改進(jìn)算法的時(shí)間復(fù)雜度也明顯比原算法低，綜合性能的改善十分顯著。

表1 時(shí)間成本和PSNR

4 結(jié)論

本文在保持Criminisi圖像修復(fù)算法基本框架不變的情況下，提出了一些較新穎的改進(jìn)方案。我們的主要工作是設(shè)計(jì)了基于可變大小模板的高效塊匹配程序，并結(jié)合信度更新修正和局部搜索以提高算法的綜合性能。實(shí)驗(yàn)結(jié)果表明了改進(jìn)措施的有效性。

我們下一步的工作希望將改進(jìn)方案與多分辨率修復(fù)框架［11－12］進(jìn)行結(jié)合。此外，探索結(jié)合圖像結(jié)構(gòu)的模板廣義相異性測度［8，13］和圖像分割［14］亦是很有意義的研究方向。

［1］Bertalmio M，Sapiro G，Ballester C，et al，Image Inpainting［C］//ACM SIGGRAPH，2000，417－424.

［2］Chan T，Shen J.Local Inpainting Models and TV Inpainting［J］.SIAM J.Appl Math，2001，62:1019－1043.

［3］Chan T，Shen J.Non-Texture Inpainting by Curvature Driven Diffusion(CDD)［J］.J Visual Comm Image Rep，2001，12(4):436－449.

［4］Chan T，Kang S，Shen J.Euler’s Elastica and Curvature Based Inpainting［J］.SIAM J Appl Math，2002，63(2):564－592.

［5］Efros A，Leung T.Texture Synthesis by Non-Parametric Sampling［C］//Proc IEEE Int Conf Computer Vision，1999，2，1033－1038.

［6］Criminisi A，Perez P，Toyama K.Region Filling and Object Removal by Exemplar-Based Image Inpainting［J］.IEEE Trans Image Process，Sep 2004，13(9):1200－1212.

［7］Komodakis N，Tziritas G.Image Completion Using Global Optimization［C］//Proc IEEE Computer Soc Conf Computer Vision and Pattern Recognition，2006，442－452.

［8］Bugeau A，Bertalmio M，Caselles V，et al，A Comprehensive Framework for Image Inpainting［J］.IEEE Trans Image Process，2010，19(10):2634－2645.

［9］Hsin H F，Leou J J，Lin C S，et al.Image Inpainting Using Structure-Guided Priority Belief Propagation and Label Transformations［C］//Pattern Recognition(ICPR)，2010 20th International Conference on，2010，4492－4495.

［10］Wohlberg B.Inpainting by Joint Optimization of Linear Combinations of Exemplars.Signal Processing Letters［J］.Signal Processing Letters，IEEE，2011，18(1):75－78.

［11］Fang C W，Lien J J.Rapid Image Completion System Using Multiresolution Patch-Based Directional and Nondirectional Approaches［J］.IEEE Trans Image Process，2009，18(12):2769－2779.

［12］蔡念，張海員，張楠.基于Contourlet的改進(jìn)雙線性插值圖像超分辨率算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24(1):59－64.

［13］朱良銷，余學(xué)才，陳濤，等.一種擴(kuò)展動(dòng)態(tài)范圍的圖像處理算法［J］.傳感技術(shù)學(xué)報(bào)，2011，24(1):65－67.

［14］Ojeda S，Vallejos R，Bustos O.A New Image Segmentation Algorithm with Applications to Image Inpainting［J］.Comput Stat Data Anal，2010，54(9):2082－2093.