基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法

朱曉臨， 陳曉冬， 朱園珠， 陳 嫚，李雪艷

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

圖像修復(fù)大體上可分為兩類：一類是針對小尺度缺損的基于結(jié)構(gòu)的算法[1-10]；另一類是針對基于大面積破損的紋理合成算法[11-19]。

近年來，人們試圖找到一種對待修復(fù)域較大且結(jié)構(gòu)相對復(fù)雜的圖像的綜合修復(fù)方法；此類算法尚屬起步階段。

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

早在2003年，Bertalmio等[22]率先提出了一種對結(jié)構(gòu)和紋理同時進(jìn)行修復(fù)的方法。該算法主要包含3個步驟：把圖像分解為結(jié)構(gòu)圖像和紋理圖像；對結(jié)構(gòu)圖像部分使用基于結(jié)構(gòu)的修復(fù)方法進(jìn)行修復(fù)；對紋理圖像部分使用紋理合成的方法進(jìn)行修復(fù)；然后進(jìn)行合成。

2008年，邵肖偉等[23]提出一種基于Poisson方程的分離型修復(fù)算法，與文獻(xiàn)[22]相仿，其結(jié)構(gòu)圖像使用 Laplacian 算子先強(qiáng)化結(jié)構(gòu)圖像的結(jié)構(gòu)信息，隨后對 Laplacian 場進(jìn)行修復(fù)處理，再使用 Poisson方程對其進(jìn)行重建；此法有一定成效，但難以克服大面積破損的待修復(fù)圖像的修復(fù)問題，且修復(fù)后的圖像會有明顯的平滑銳化痕跡，導(dǎo)致一定程度的失真。

本文對既有顯著結(jié)構(gòu)同時又包含豐富紋理的待修復(fù)圖像進(jìn)行了修復(fù)嘗試，考慮到結(jié)構(gòu)修復(fù)算法及紋理合成算法各自的優(yōu)點，以及顯著結(jié)構(gòu)對圖像修復(fù)的巨大影響，提出基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法。算法先利用形態(tài)學(xué)算子剝離待修復(fù)圖像中細(xì)小結(jié)構(gòu)與大塊區(qū)域；然后利用快速結(jié)構(gòu)修復(fù)算法對圖像進(jìn)行處理；再利用插值對待修復(fù)圖像進(jìn)行顯著結(jié)構(gòu)重構(gòu)；最后利用基于改進(jìn)優(yōu)先級的加權(quán)匹配圖像修復(fù)算法進(jìn)行后續(xù)修復(fù)。實驗結(jié)果表明，與傳統(tǒng)算法相比，本文的算法修復(fù)效果更好，耗時更少。

1 Criminisi算法簡介

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

圖1 Criminisi算法示意圖

Criminisi算法的要旨在于考慮了待修復(fù)區(qū)域的修復(fù)順序，提出了按優(yōu)先級進(jìn)行修復(fù)的思路。取

作為決定修復(fù)順序的優(yōu)先級。其中np是待修復(fù)區(qū)域Ω的邊界δΩ上點p處的法向量，?Ip⊥是已知區(qū)域Φ的邊界的梯度向量的垂直向量（即等照度線方向），α是標(biāo)準(zhǔn)歸一化因子（典型的灰度圖像中取α=255）：

C ( p)稱為置信項，即填充塊中已知信息所占的比例；D(p)稱為數(shù)據(jù)項，即結(jié)構(gòu)信息；初始時，對?p∈Ω，置信項C(p)=0；對?p∈I-Ω時，置信項C(p)=1。Ψp表示以p點為中心的小塊，Ψp表示Ψp的面積。

根據(jù)預(yù)先定義好的優(yōu)先級，在待修復(fù)域的邊界δΩ上選取一點p，然后選擇一個以p點為中心的小塊Ψp，即具有最高優(yōu)先級的待修復(fù)塊；再從已知區(qū)域Φ中尋找與Ψp最匹配的塊。若Ψq?是已知信息區(qū)域中與Ψp最匹配的塊（通常情況下，Ψq?應(yīng)完全包含在已知區(qū)域Φ中），則分別是像素和與之對應(yīng)的像素的灰度值。對于彩色圖像，其像素灰度可由其對應(yīng)像素的R、G、B的平均值代替。找到Ψq?之后，將Ψq?中相應(yīng)的圖像信息拷貝至Ψp∩Ω的位置，并更新邊界δΩ，重復(fù)上述過程直至Ω為空集。

2 本文的算法

2.1 改進(jìn)優(yōu)先級和加權(quán)匹配塊

Criminisi合成算法的兩大關(guān)鍵要素是：①優(yōu)先級的確定；②匹配塊的選擇。

2.1.1 改進(jìn)優(yōu)先級

針對第1個要素，因為式(1)中數(shù)據(jù)項D(p)可能為零，所以可能導(dǎo)致修復(fù)發(fā)生偏差，如圖2所示。為此，文獻(xiàn)[24]等對此做了改進(jìn)。

本文在文獻(xiàn)[13]的基礎(chǔ)上，增加考慮了圖像中對優(yōu)先級有較大影響的顯著邊緣的作用，在優(yōu)先級的計算項中增加考慮：

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

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

（3）其他突出的顯著邊緣線對優(yōu)先級的影響。

即在優(yōu)先級P(p)的計算中增加了邊緣項E ( p)(edge term)，改進(jìn)后的優(yōu)先級P(p)為

其中，λ1、λ2、λ3是非負(fù)常數(shù)。C(p)和D(p)的表達(dá)式與式(2)相同。E(p)定義如下其中，Ep是顯著邊緣。

顯然，E(p)的確定是至關(guān)重要的。顯著邊緣顧名思義是圖像中十分明顯且特別突出的邊緣特征，若能精確地提取E(p)，則能對修復(fù)效果起到明顯改善作用。而現(xiàn)有的邊緣提取算法所提取的邊緣特征幾乎包含了整幅圖像所有邊緣特征信息，因此需要剔除哪些不期待出現(xiàn)的的冗余邊緣特征。為此，應(yīng)當(dāng)做好以下幾方面，以確保能獲得無冗余的顯著邊緣特征。

圖2 Criminisi算法修復(fù)示例

首先對圖像進(jìn)行深度去噪，這樣，圖像中的噪聲點以及那些結(jié)構(gòu)相似區(qū)域（即弱邊緣區(qū)域）就會被逐步平滑，然后對所得到的圖像進(jìn)行邊緣檢測時，便只會檢測出圖像中保留下來的顯著邊緣特征；同時，為了避免因深度去噪對圖像邊緣可能產(chǎn)生的影響，保證得到的顯著邊緣精確性，本文利用曲率的知識，計算出圖像各像素點的曲率分布圖，并結(jié)合原始圖像的邊緣檢測結(jié)果，以及通過深度去噪后的邊緣圖進(jìn)行融合，從而最終達(dá)到期待的顯著邊緣特征圖E(p)，再按式(5)計算優(yōu)先級。

2.1.2 加權(quán)匹配塊

針對Criminisi合成算法的第2個關(guān)鍵要素，在充分考慮圖像各像素點的干擾機(jī)制及邊緣項E ( p)的視覺影響作用情況下，需對塊的匹配過程進(jìn)行更為合理的改進(jìn)，通過反復(fù)試驗，提出新的匹配塊控制權(quán)因子

下節(jié)的實驗結(jié)果驗證了本文提出的權(quán)因子的合理性。于是與Ψp最匹配的塊為

2.1.3 顯著邊緣重構(gòu)

傳統(tǒng)算法通常是在整幅圖像上進(jìn)行搜索，再尋找匹配塊，這樣可能因為偏差延續(xù)等問題導(dǎo)致視覺上原本不太匹配的塊被填充在待修復(fù)區(qū)域，同時耗時多。為此，人們大多采用以下兩種區(qū)域搜索方法：一是局部搜索；二是分塊修復(fù)。

選擇局部搜索與分塊修復(fù)雖然能降低修復(fù)耗時，一定程度上保證算法的效果，但有時難免會因搜索域限制難以找到合適的匹配塊，或是因分塊對完整的顯著結(jié)構(gòu)造成破壞，這樣便不能保證修復(fù)后圖像中顯著結(jié)構(gòu)在視覺上的完整性。

為此，本文利用插值對顯著邊緣特征預(yù)先進(jìn)行重構(gòu)。本文算法不但能對圖像中直線型特征進(jìn)行重構(gòu)，而且還能對曲線結(jié)構(gòu)的顯著特征進(jìn)行重構(gòu)，從而很好地避免了分塊修復(fù)對顯著結(jié)構(gòu)完整性造成的破壞。

在對重構(gòu)后的圖像進(jìn)行修復(fù)時，本文采用全局與局部相結(jié)合的方法來進(jìn)行修復(fù)。首先對重構(gòu)后顯著邊緣與待修復(fù)域相交處進(jìn)行修復(fù)。因為此處特征變化劇烈，所以采用全局搜索；待圖像中變化劇烈的地方修復(fù)完成，剩余的部分變化相對比較平緩，故而后續(xù)修復(fù)只需采用局部搜索便可以確保修復(fù)效果、省時。

2.2 快速結(jié)構(gòu)修復(fù)

雖然紋理修復(fù)算法可以修復(fù)大面積破損的圖像，但是在一幅圖像中，除大破損區(qū)域外，可能還有諸多紛亂無序的小尺度破損。如果僅利用紋理修復(fù)技術(shù)對此圖像進(jìn)行修復(fù)，一方面，由于小破損域也需要利用塊搜索匹配的思想，必將浪費很長的時間；另一方面，由于破損處過多，有時難以找到一個完全包含在已知區(qū)域內(nèi)的塊來對圖像進(jìn)行填充，必然會導(dǎo)致修復(fù)效果發(fā)生嚴(yán)重偏差。為此，本文預(yù)先利用快速結(jié)構(gòu)修復(fù)算法對細(xì)小破損處進(jìn)行修復(fù)，然后再利用紋理合成算法進(jìn)行大面積填充，實驗結(jié)果證明了改進(jìn)算法的優(yōu)越性。

2.3 算法步驟

綜上，本文提出一種基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法。該算法步驟如下：

首先，人工選取待修復(fù)區(qū)域或待移除的目標(biāo)，并將待修復(fù)域置為純色；然后根據(jù)需要進(jìn)行適度的掩碼膨脹找到恰當(dāng)?shù)倪吔?，再將待修?fù)區(qū)域的邊界標(biāo)記為設(shè)置。執(zhí)行如下步驟（初始i=0）：

（1）根據(jù)形態(tài)學(xué)算子對待修復(fù)圖進(jìn)行掩膜膨脹與腐蝕，剝離大塊與小線條結(jié)構(gòu)；

（2）找出剝離后的線條結(jié)構(gòu)的提取掩碼，利用快速結(jié)構(gòu)修復(fù)算法修復(fù)；

（3）找出剝離后的待修復(fù)大塊區(qū)域的邊界δΩi，如果 Ωi=?，退出循環(huán)，修復(fù)結(jié)束；

（4）E(p)項的提?。辉贓(p)上用Cubic Spline完成顯著結(jié)構(gòu)重構(gòu)；

（6）找出具有最大優(yōu)先權(quán)值的待修復(fù)區(qū)域塊Ψp，即；

（7）根據(jù)式(6)、(7)、(8)、(9)、(10)找出最匹配的塊Ψ?q∈Φ；

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

（9）令i=i+1，重復(fù)步驟(3)～(8)。

3 實驗結(jié)果

本文實驗用MATLAB 7.10作為工具，在Intel酷睿I3雙核處理器(2.6 GHz)、2 G內(nèi)存的PC機(jī)上實現(xiàn)。圖3～5是文獻(xiàn)[24]及與本文算法之間修復(fù)結(jié)果的比較。

圖3第一組，從修復(fù)效果上來看，本文算法所得的修復(fù)效果(d1)不僅滿足視覺上要求，相較其他修復(fù)結(jié)果(b1)和(c1)，在河堤與河面交匯處也更為自然流暢，同時也大大縮短了修復(fù)時間（見表1）。圖3第二組，文獻(xiàn)[24]算法與 Criminisi算法的修復(fù)效果與本文算法相比差別比較明顯；其中圖(b2)和(c2)存在嚴(yán)重的偏差延續(xù)情況，出現(xiàn)大面積的崩潰。

從圖4的兩組結(jié)果來看，本文算法與傳統(tǒng)算法相比，修復(fù)結(jié)果差異相當(dāng)明顯。本文算法修復(fù)效果(d1)和(d2)，具有更強(qiáng)的魯棒性，保證了相對復(fù)雜的破損圖像的修復(fù)效果。而文獻(xiàn)[24]算法與Criminisi算法的修復(fù)效果圖出現(xiàn)了明顯的偏差延續(xù)狀況，圖像右下角都不同程度出現(xiàn)了較為明顯的斷痕，而且所耗時間為本文算法的7倍左右（見表1）。

同圖4的兩組結(jié)果相似，本文算法具有良好的魯棒性，修復(fù)效果也明顯好于傳統(tǒng)算法。Criminisi算法與文獻(xiàn)[24]算法修復(fù)結(jié)果在圍墻處存在明顯不銜接，甚至破損的現(xiàn)象；而本文算法修復(fù)后的圖像視覺效果卻自然流暢，而且耗時較之其他算法要少（見表1）。

表1列出了圖3～5，Criminisi算法、文獻(xiàn)[24]算法和本文算法的修復(fù)時間的比較。

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

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

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

表1 不同算法修復(fù)時間比較(s)

4 結(jié) 束 語

傳統(tǒng)算法在對修復(fù)域面積較大且結(jié)構(gòu)相對復(fù)雜的圖像進(jìn)行修復(fù)時，難以克服修復(fù)效果上的偏差以及耗時問題。本文針對上述問題提出了基于顯著結(jié)構(gòu)重構(gòu)與紋理合成的圖像修復(fù)算法。算法將形態(tài)學(xué)、數(shù)學(xué)、圖像自身的特征、以及人類視覺等基本原理有機(jī)地結(jié)合起來，為結(jié)構(gòu)復(fù)雜紋理豐富的破損圖像修復(fù)提供了一種解決思路，并通過實驗驗證了思路的可行性，效果的優(yōu)越性。

后面的工作將致力于顯著特征的自動化重構(gòu)問題，同時對修復(fù)中出現(xiàn)的其他問題，進(jìn)行進(jìn)一步探討。

[1] 張紅英,彭啟琮. 數(shù)字圖像修復(fù)技術(shù)綜述[J]. 中國圖象圖形學(xué)報,2007,12(1): 1-10.

[2] Masnou S,Model J-M. Level lines based disocclusion[C]//Image Processing,1998. ICIP 98. Proceeding. 1998,International Conference on,1998,3: 259-263.

[3] Bertalmio M,Sapiro G,Caselles V,Ballester C. 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 Jianhong. Non-texture inpainting by curvature-driven diffusions (CDD) [J]. Journal of Visual Communication and Image Representation,2001,12(4): 436-449.

[5] Chan T F,Shen Jianhong. Mathematical models for local nontexture inpaintings [J]. SIAM Journal on Applied Math,2001,62(3): 1019-1043.

[6] Lu Xiaobao,Wang Weilan,Duo Jie,Zhuo Ma. A fast image inpainting algorithm based on TV model [C]//Proceeding of the International MultiConference of Engineers and Computer Scientists. Hong Kong,March,2010: 1457-1460.

[7] Li Fang,Shen Chaomin,Liu Ruihua,Fan Jinsong. A fast implementation algorithm of TV inpainting model based on operator splitting method [J]. Computers and Electrical Engineering,2011,37(5): 782-788.

[8] Li Fang,Bao Zheng,Liu Ruihua,Zhang Guixu . Fast image inpainting and colorization by Chambolle’s dual method [J]. Journal of Visual Communication and Image Representation,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].Applied Computional Harmonic Analysis,2012,32(1): 145-154.

[11] Efros A A,Leung T K. Texture synthesis by non parametric sampling [C]//Computer Vision 1999. The Proceedings of the Seventh IEEE International Conference on,Kerkyra,Greece,1999,2: 1033-1038.

[12] Criminisi A,P′erez P,Toyama K. Object removal by exemplar-based inpainting [C]//Madison,Wiscons Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2003:721-728.

[13] Criminisi A,Perez P,Toyama K. Region filling and object removal by exemplar-based image inpainting [J].IEEE Transactions on Image Processing,2004,9(13):1200-1212.

[14] Tae-o-sot S,Nishihara A. Iterative gradient-driven patch-based inpainting [C]//Y-S Ho(Ed),PSIVT 2011,Part II ,LNCS,2011:71-81.

[15] Wu Xinran,Wei Zeng,Li Zhenzhou. Exemplar-based image inpainting with collaborative filtering [C]//Image and Graphics (ICIG),2011 Sixth International Conference on,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 Dr 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 Beddhu,Ali Adel 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] Bertalmio M,Vese L,Sapiro G,Osher S. Simultaneous texture and structure image inpainting [J]. IEEE Transaction on Image Processing,2003,12(8):882-889.

[23] 邵肖偉,劉政凱,李厚強(qiáng). 一種基于 Poisson 方程的分離型圖像修復(fù)方法[J]. 電路與系統(tǒng)學(xué)報,2008,13(6):1-6.

[24] 黃淑兵,朱曉臨,許云云,朱 坤. 一種改進(jìn)的基于紋理合成的圖像修復(fù)算法[J]. 合肥工業(yè)大學(xué)學(xué)報(自然科學(xué)版),2011,34(2): 313-316,320.