基于改進(jìn)優(yōu)先級(jí)的加權(quán)匹配圖像修復(fù)算法

陳曉冬， 朱曉臨

（合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院，安徽 合肥 230009）

0 引 言

圖像修復(fù)是對(duì)圖像中信息缺損的區(qū)域進(jìn)行信息填充的過程，其目的就是對(duì)破損圖像進(jìn)行恢復(fù)，并且使觀察者無法察覺到圖像曾經(jīng)缺損或已被修復(fù)［1］。因此，人們的主觀認(rèn)知及先驗(yàn)知識(shí)對(duì)圖像修復(fù)的影響起著重要作用，故從視覺心理學(xué)的角度出發(fā)，提出了各種假設(shè)來解決該問題。

文獻(xiàn)［2］提出了基于等照度線的方法；文獻(xiàn)［3］提出了一種基于偏微分方程（partial differential equation，簡稱PDE）的修復(fù)算法；文獻(xiàn)［4］提出了基于TV模型的修復(fù)方案；文獻(xiàn)［5］在文獻(xiàn)［3］的啟發(fā)下，提出了CDD（曲率驅(qū)動(dòng)擴(kuò)散）模型的修復(fù)方法。文獻(xiàn)［6－7］對(duì)TV模型不斷地進(jìn)行改進(jìn)完善；文獻(xiàn)［8－10］分別提出了一些新的修復(fù)算法。

盡管上述算法對(duì)破損區(qū)域相對(duì)較小的結(jié)構(gòu)圖像有顯著的效果，但它們對(duì)破損區(qū)域較大的圖像修復(fù)效果不太理想。

對(duì)于破損區(qū)域較大的紋理圖像，文獻(xiàn)［11］提出紋理合成方法，該算法的思想是從圖像的已知區(qū)域中尋找與受損區(qū)域最匹配的塊進(jìn)行填充，從而實(shí)現(xiàn)圖像修復(fù)。若圖像中包含復(fù)雜結(jié)構(gòu)時(shí)，這種方法的效果不太理想。

針對(duì)這種現(xiàn)象，文獻(xiàn)［12］提出了基于樣例的目標(biāo)移除算法，隨后將其進(jìn)一步完善得到基于樣例的目標(biāo)移除與區(qū)域填充的圖像修復(fù)算法［13］。文獻(xiàn)［13］的算法在確?？梢孕迯?fù)較大破損區(qū)域的同時(shí)，在一定程度上保留了圖像的結(jié)構(gòu)和紋理信息。盡管如此，Criminisi算法［13］在處理圖像時(shí)，對(duì)較強(qiáng)的結(jié)構(gòu)信息持續(xù)優(yōu)先處理很容易造成偏差延續(xù)，導(dǎo)致修復(fù)效果出現(xiàn)較大偏差。由于這種方法是在整幅待修復(fù)圖像中搜索、復(fù)制圖像信息，然后對(duì)待修復(fù)域直接進(jìn)行填充，因此會(huì)消耗較長時(shí)間。

文獻(xiàn) ［14－19］提出了改進(jìn)方法解決偏差延續(xù)的問題，取得了一定的進(jìn)展，卻仍不夠理想。

文獻(xiàn)［20－21］提出用連接線的方法優(yōu)先解決圖像中存在的顯著結(jié)構(gòu)，收到一定成效，但由于其自動(dòng)化程度較低，實(shí)時(shí)性效率低，且操作相對(duì)復(fù)雜，使其應(yīng)用受到一定的限制。

本文從圖像修復(fù)算法中的紋理合成算法入手，在對(duì)經(jīng)典的Criminisi算法進(jìn)行深入研究和分析的基礎(chǔ)上，提出了一種基于改進(jìn)優(yōu)先級(jí)的加權(quán)匹配的圖像修復(fù)算法。

1 Criminisi算法簡介

如圖1所示，記I為待修復(fù)圖像，Ω為待修復(fù)區(qū)域，其邊界為?Ω，Φ為待修復(fù)圖像的已知信息區(qū)域。

Criminisi算法考慮了待修復(fù)區(qū)域的修復(fù)順序，提出了按優(yōu)先級(jí)進(jìn)行修復(fù)的思路。取P（p）作為決定修復(fù)順序的優(yōu)先級(jí)，即

其中，np是待修復(fù)區(qū)域Ω的邊界?Ω上點(diǎn)p處的法向量；是已知區(qū)域Φ邊界的梯度向量的垂直向量（即等照度線方向）；α是標(biāo)準(zhǔn)歸一化因子，在典型的灰度圖像中取255；C（p）稱為置信項(xiàng)，即填充塊中已知信息所占的比例；D（p）（p∈?Ω）稱為數(shù)據(jù)項(xiàng)，即結(jié)構(gòu)信息；當(dāng)?p∈Ω時(shí)，C（p）＝0；?p∈I－Ω時(shí)，C（p）＝1。

圖1 Criminisi算法示意圖

根據(jù)預(yù)先定義好的優(yōu)先級(jí)，在待修復(fù)域的邊界?Ω上選取點(diǎn)p，然后選擇1個(gè)以p點(diǎn)為中心的小方塊Ψp，即具有最高優(yōu)先級(jí)的待修復(fù)塊；再從已知區(qū)域Φ中尋找與Ψp最匹配的塊。若Ψ＾q是已知信息區(qū)域中與Ψp最匹配的塊（通常情況下，Ψ＾q應(yīng)完全包含在已知區(qū)域Φ中），則

2 本文算法

2.1 算法思想

Criminisi合成算法的2個(gè)關(guān)鍵要素是優(yōu)先級(jí)的確定和匹配塊的選擇。

針對(duì)第1個(gè)要素，傳統(tǒng)的Criminis算法中優(yōu)先級(jí)P（p）＝C（p）D（p）存在不足，因?yàn)槠鋽?shù)據(jù)項(xiàng)D（p）可能為0，因而可能導(dǎo)致修復(fù)發(fā)生偏差。為此，文獻(xiàn)［22］對(duì)此做了改進(jìn)。

其核心思想是在Criminisi算法提出的信任項(xiàng)C（p）和數(shù)據(jù)項(xiàng)D（p）的基礎(chǔ)上，增加邊界項(xiàng)B（p）。與文獻(xiàn)［13］相比，文獻(xiàn)［22］的修復(fù)效果有所改善。不同算法修復(fù)結(jié)果比較，如圖2所示。

傳統(tǒng)的邊緣提取算子在提取邊界時(shí)也不夠精確，導(dǎo)致待修復(fù)區(qū)域的邊界很難被精確定位（見圖2b），因而導(dǎo)致圖像在待修復(fù)區(qū)域的邊界附近得不到很好的修復(fù)；此外，優(yōu)先級(jí)出現(xiàn)錯(cuò)誤，致使預(yù)先確定的修復(fù)塊并非是真正的待修復(fù)塊，從而產(chǎn)生修復(fù)偏差（見圖2c）。

圖2 不同算法修復(fù)結(jié)果比較

雖然文獻(xiàn)［22］提出了邊界項(xiàng)B（p），改善了優(yōu)先級(jí)P（p），但未考慮原始圖像中對(duì)優(yōu)先級(jí)影響更大的顯著邊緣的作用?；诖?，本文在優(yōu)先級(jí)計(jì)算中考慮如下幾點(diǎn)：

（1）與待修復(fù)塊中心點(diǎn)連接的顯著邊緣線。

（2）與修復(fù)塊內(nèi)邊界某點(diǎn)連接的顯著邊緣線。

（3）其他突出的顯著邊緣線。

因此，在優(yōu)先級(jí)P（p）的計(jì)算中增加了邊緣項(xiàng)E（p），改進(jìn)后的優(yōu)先級(jí)P（p）為：

其中，λ1、λ2、λ3、λ4是非負(fù)常數(shù)；C（p）和D（p）的表達(dá)式與（2）式相同。B（p）和E（p）定義如下：

其中，Ep是顯著邊緣；?Ωi表示第i次（0≤i≤N）修復(fù)后待修復(fù)區(qū)域的邊界（Ω＝Ω0?Ω1?…?ΩN＝?），而｛Ωi｝是每次執(zhí)行修復(fù)之后新的待修復(fù)區(qū)域的序列集。

因此，在選取待修復(fù)域并將其置為純色后，提取掩模圖像，然后根據(jù)需要對(duì)掩碼圖像進(jìn)行適當(dāng)?shù)难谀Ｅ蛎洠垣@取精準(zhǔn)的邊界圖（見圖2d），再按（5）式計(jì)算優(yōu)先級(jí)。

針對(duì)Criminisi合成算法的第2個(gè)關(guān)鍵要素，文獻(xiàn)［23］考慮到待修復(fù)塊中各點(diǎn)與中心點(diǎn)距離的遠(yuǎn)近對(duì)匹配塊產(chǎn)生的影響，指出歐氏距離可以看作信息間的相似程度，距離越近關(guān)聯(lián)度越大，就越容易相互干擾，誤差就越明顯，因而提出了加權(quán)匹配的修復(fù)算法，對(duì)Criminisi算法中計(jì)算項(xiàng)d（Ψp，Ψq）進(jìn)行改進(jìn)，在該項(xiàng)中設(shè)置了一個(gè)權(quán)因子1／ε），即

其中，（x1，y1）、（x2，y2）分別是像素點(diǎn)的位置坐標(biāo)，此時(shí)（4）式化為加權(quán)匹配公式，即

因此，本文在考慮到邊緣項(xiàng)E（p）在待修補(bǔ)塊與匹配塊間影響作用的基礎(chǔ)上，根據(jù)實(shí)驗(yàn)反復(fù)驗(yàn)證提出了新的加權(quán)因子，即

實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的權(quán)因子的合理性，于是Ψp的最匹配塊為：

此外，傳統(tǒng)算法通常是在整幅圖像上尋找匹配塊，這樣不僅會(huì)消耗大量時(shí)間，而且可能導(dǎo)致視覺上原本不太匹配的塊被填充在待修復(fù)區(qū)域，造成偏差延續(xù)。

本文算法基于圖像結(jié)構(gòu)相似性特征，首先對(duì)圖像進(jìn)行鄰域相似分割，然后運(yùn)用上述方法進(jìn)行修復(fù)，使搜索域的選取變得更加靈活，大大縮短修復(fù)所用的時(shí)間；另一方面，可以使一些特定區(qū)域在修復(fù)時(shí)不受其他信息的干擾，避免偏差延續(xù)，從而保證修復(fù)結(jié)果更符合人們的視覺效果。

2.2 本文算法實(shí)現(xiàn)

本文提出一種改進(jìn)的基于加權(quán)匹配的快速修復(fù)算法。初始時(shí)，人工選取待修復(fù)區(qū)域或待移除的目標(biāo)，并將待修復(fù)域置為純色，然后根據(jù)需要進(jìn)行適度的掩碼膨脹找到恰當(dāng)?shù)倪吔?，再將待修?fù)區(qū)域的邊界標(biāo)記為?Ω0（＝?Ω），設(shè)置＾B（p）＝?Ω0，?p∈?Ω0。

執(zhí)行步驟如下（初始i＝0）：

（1）找出待修復(fù)區(qū)域的邊界?Ωi，如果Ωi＝?，退出循環(huán)，修復(fù)結(jié)束。如果＾B（p）∩Ωi＝?，置＾B（p）＝?Ωi，?p∈?Ωi。

（2）根據(jù)（2）式、（5）～（7）式計(jì)算優(yōu)先權(quán)P（p），?p∈?Ωi。

（4）根據(jù)（8）式、（10）～（12）式找出最匹配的塊Ψ＾q∈Φ。

（5）將Ψ＾q中對(duì)應(yīng)的圖像信息復(fù)制到Ψp∩Ω。

（6）令i＝i＋1，重復(fù)步驟（1）～（5）。

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

采用Matlab 7.10作為工具，在Intel酷睿I3雙核處理器（2.0GHz）、2G內(nèi)存的PC機(jī)上進(jìn)行實(shí)驗(yàn)。

圖3～圖5所示為本文算法與文獻(xiàn)［13］Criminisi算法、文獻(xiàn)［22］算法、文獻(xiàn)［23］加權(quán)匹配算法修復(fù)結(jié)果的比較；圖6所示為本文算法與傳統(tǒng)TV算法的比較。

由圖3可見，這是紋理修復(fù)常規(guī)比較的經(jīng)典蹦極圖像，圖3c出現(xiàn)偏差延續(xù)的情況，存在明顯的斷痕。從圖3d和圖3e中看出，屋檐上下也存在一定的偏差延續(xù)情況，不能自然流暢地體現(xiàn)屋檐的特征。而從圖3f看出，本文算法很好地解決了以上的諸多問題。

圖3 本文算法與其他算法修復(fù)結(jié)果比較（一）

由圖4可見，圖4c和圖4e出現(xiàn)了偏差延續(xù)的情況，存在明顯的斷痕。圖4d比圖4c和圖4e有所改善，但仍然可以看出圍墻頂面存在偏差延續(xù)的情況。而圖4f顯示本文的修復(fù)算法結(jié)果比其他算法視覺效果有了明顯改觀，且更加自然流暢。

由圖5可見，圖5c是因?yàn)槲墨I(xiàn)［13］中的算法強(qiáng)調(diào)強(qiáng)邊緣延續(xù)，導(dǎo)致草坪區(qū)域被路的顏色信息蔓延覆蓋。圖5e盡管沒有大面積的崩潰，但由于文獻(xiàn)［23］權(quán)因子自身存在的弱點(diǎn)，也導(dǎo)致了修復(fù)結(jié)果的偏差。圖5d保證了圖像在大范圍上的視覺效果，但其右下角稍有瑕疵。而圖5f顯示本文算法很好地克服了上述存在的種種瑕疵，視覺效果最好。

在此例中，修復(fù)塊的大小都是9×9，根據(jù)不同的強(qiáng)邊緣圖，在（5）式中選取不同的參數(shù)，λ1＝0，λ2＝1，λ3＝3.8，λ4＝1或λ1＝0.5，λ2＝1，λ3＝3.8，λ4＝0.5，模型相對(duì)靈活。

圖4 本文算法與其他算法修復(fù)結(jié)果比較（二）

圖5 本文算法與其他算法修復(fù)結(jié)果比較（三）

由圖6可見，圖6c為經(jīng)典的TV算法修復(fù)結(jié)果，其左側(cè)的豎條修復(fù)后出現(xiàn)了模糊。由圖6d可以看出，本文算法不僅可以適用于結(jié)構(gòu)圖像，而且修復(fù)效果比TV模型還要好。其中，修復(fù)塊的大小取7×7。

圖6 本文算法與TV模型修復(fù)結(jié)果比較

修復(fù)時(shí)間比較見表1所列。

表1 修復(fù)時(shí)間的比較 s

4 結(jié)束語

本文通過分析一些圖像修復(fù)算法在修復(fù)某些圖像時(shí)，視覺效果產(chǎn)生偏差的原因，提出了改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法不僅可以有效修復(fù)破損區(qū)域較大的圖像，對(duì)破損區(qū)域較小的結(jié)構(gòu)圖像也有顯著的修復(fù)效果，而且優(yōu)先權(quán)計(jì)算更加精準(zhǔn)，搜索范圍更加靈活，匹配塊更加合理，適用范圍更廣，修復(fù)效果更好。

本文方法對(duì)于待修復(fù)區(qū)域過大或已知區(qū)域中不存在與待修復(fù)區(qū)域中相近似的塊的圖像，修復(fù)效果不是很理想。

［1］張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述［J］.中國圖象圖形學(xué)報(bào)，2007，12（1）：1－10.

［2］Masnou S，Model J.Level lines based disocclusion［C］／／International Conference on Information Processing，1998：259－263.

［3］Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting［C］／／Proceedings of International Conference on Computer Graphics and Interactive Techniques，New Orleans，Louisiana，USA，2000：417－424.

［4］Chan T F，Shen J.Non－texture inpainting by curvaturedriven diffusions（CDD）［J］.Joumal of Visual Communication and Image Representation，2001，12（4）：436－449.

［5］Chan T F，Shen J.Mathematical models for local nontexture inpaintings［J］.SIAM Journal on Applied Math，2001，62（3）：1019－1043.

［6］Lu Xiaobao，Wang Weilan，Duojie Zhuoma.A fast image inpainting algorithm based on TV model［C］／／Preceeding of the International MultiConference of Engineers and Computer Scientists，Hong Kong，March，2010：1457－1460.

［7］Li Fang，Shen Chaomin，Liu Ruihua，et al.A fast implementation algorithm of TV inpainting model based on operator splitting method［J］.Computers and Electrical Engineering，2011，37：782－788.

［8］Li Fang，Bao Zheng，Liu Ruihua，et al.Fast image inpainting and colorization by，Chambolle’s dual method［J］.J Vis Commun Image R，2011，22：529－542.

［9］Lin Chang，Yu Chongxiu.New interpolation algorithm for image inpainting ［J］. Physics Procedia，2011，22：107－111.

［10］Li Qia，Shen Lixin，Yang Lihua.Split－bregman iteration for framelet based image inpainting［J］.Appl Comput Harmon Ana，2012，32：145－154.

［11］Efros A，Leung T.Texture synthesis by non－parametric sampling［C］／／Proc Int Con Computer Vision，Kerkyra，Greece，September，1999：1033－1038.

［12］Criminisi A，Perez P，Toyama K.Object removal by exemplar－based inpainting［C］／／Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition，Vol 2，2003：721－728.

［13］Criminisi A，Perez P，Toyama K.Region filling and ob－ject removal by exemplar－based image inpainting［J］.IEEE Transactions on Image Processing，2004，13（9）：1200－1212.

［14］Sarawut T S，Akinori N.Iterative gradient－driven patchbased inpainting［C］／／Ho Y S.PSIVT，2011：71－81.

［15］Wu X，Zeng W，Li Z.Exemplar－based image inpainting with collaborative filtering［C］／／Sixth International Conference on Image and Graphics，Hefei，Anhui，China，Aug，2011：8－11.

［16］Tae－o－sot S，Nishihara A.Exemplar－based image inpainting with patch shifting scheme［C］／／17th International Conference on Digital Signal Processing，2011：1－5.

［17］Wang Minqin.A novel image inpainting method based on image decomposition［J］.Procedia Engineering，2011，15：3733－3738.

［18］Florinabel D J，Juliet S E，Sadasivam V.Combined frequency and spatial domain－based patch propagation for image completion［J］.Computers ＆ Graphics，2011，35：1051—1062.

［19］Sangeetha K，Sengottuvelan P，Balamurugan E.Combined structure and texture image inpainting algorithm for natural scene image completion［J］.Journal of Information Engineering and Applications，2011，1（1）：7－12.

［20］Huan Xiaoli，Murali B，Ali A L.Image restoration based on the fast marching method and block based sampling［J］.Computer Vision and Image Understanding，2010，114（8）：847—856.

［21］Li Shutao，Zhao Ming.Image inpainting with salient structure completion and texture propagation［J］.Pattern Recognition Letters，2011，32：1256－1266.

［22］黃淑兵，朱曉臨，許云云，等.一種改進(jìn)的基于紋理合成的圖像修復(fù)算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（2）：313－316，320.

［23］劉麗萍.基于加權(quán)匹配的圖像修復(fù)方法［D］.上海：上海華東師范大學(xué)，2009.