基于顯著結構重構與紋理合成的圖像修復算法

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

（合肥工業大學數學學院，安徽 合肥 230009）

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

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

文獻[20-21]用連線的方法優先解決圖像中的顯著結構，收到一定成效，但由于其自動化程度較低，實時性效率低，且操作相對復雜，使其應用受到限制。

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

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

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

1 Criminisi算法簡介

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

圖1 Criminisi算法示意圖

Criminisi算法的要旨在于考慮了待修復區域的修復順序，提出了按優先級進行修復的思路。取

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

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

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

2 本文的算法

2.1 改進優先級和加權匹配塊

Criminisi合成算法的兩大關鍵要素是：①優先級的確定；②匹配塊的選擇。

2.1.1 改進優先級

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

本文在文獻[13]的基礎上，增加考慮了圖像中對優先級有較大影響的顯著邊緣的作用，在優先級的計算項中增加考慮：

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

（2）與修復塊內邊界某點連接的顯著邊緣線；

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

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

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

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

圖2 Criminisi算法修復示例

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

2.1.2 加權匹配塊

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

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

2.1.3 顯著邊緣重構

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

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

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

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

2.2 快速結構修復

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

2.3 算法步驟

綜上，本文提出一種基于顯著結構重構與紋理合成的圖像修復算法。該算法步驟如下：

首先，人工選取待修復區域或待移除的目標，并將待修復域置為純色；然后根據需要進行適度的掩碼膨脹找到恰當的邊界，再將待修復區域的邊界標記為設置。執行如下步驟（初始i=0）：

（1）根據形態學算子對待修復圖進行掩膜膨脹與腐蝕，剝離大塊與小線條結構；

（2）找出剝離后的線條結構的提取掩碼，利用快速結構修復算法修復；

（3）找出剝離后的待修復大塊區域的邊界δΩi，如果 Ωi=?，退出循環，修復結束；

（4）E(p)項的提取；在E(p)上用Cubic Spline完成顯著結構重構；

（6）找出具有最大優先權值的待修復區域塊Ψp，即；

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

（8）將Ψ?q中對應的圖像信息復制到Ψp∩Ω；

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

3 實驗結果

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

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

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

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

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

圖3 本文算法與其他算法修復結果的比較

圖4 本文算法與其他算法修復結果的比較

圖5 本文算法與其他算法修復結果的比較

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

4 結 束 語

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

后面的工作將致力于顯著特征的自動化重構問題，同時對修復中出現的其他問題，進行進一步探討。

[1] 張紅英,彭啟琮. 數字圖像修復技術綜述[J]. 中國圖象圖形學報,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] 邵肖偉,劉政凱,李厚強. 一種基于 Poisson 方程的分離型圖像修復方法[J]. 電路與系統學報,2008,13(6):1-6.

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