陳曉冬， 朱曉臨

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

0 引 言

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

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

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

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

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

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

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

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

1 Criminisi算法簡介

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

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

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

圖1 Criminisi算法示意圖

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

2 本文算法

2.1 算法思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文提出一種改進的基于加權(quán)匹配的快速修復(fù)算法。初始時，人工選取待修復(fù)區(qū)域或待移除的目標，并將待修復(fù)域置為純色，然后根據(jù)需要進行適度的掩碼膨脹找到恰當?shù)倪吔?，再將待修?fù)區(qū)域的邊界標記為?Ω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）式計算優(yōu)先權(quán)P（p），?p∈?Ωi。

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

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

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

3 實驗結(jié)果

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

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

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

圖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ù)時間比較見表1所列。

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

4 結(jié)束語

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

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

［1］張紅英，彭啟琮.數(shù)字圖像修復(fù)技術(shù)綜述［J］.中國圖象圖形學(xué)報，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］黃淑兵，朱曉臨，許云云，等.一種改進的基于紋理合成的圖像修復(fù)算法［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2011，34（2）：313－316，320.

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