結合網函數插值與TV模型的圖像修復算法①

侯海娜, 戴 芳, 楊陳東

1(西安理工大學 理學院, 西安 710054)2(西安航空學院 理學院, 西安 710077)

結合網函數插值與TV模型的圖像修復算法①

侯海娜1, 戴 芳1, 楊陳東2

1(西安理工大學 理學院, 西安 710054)2(西安航空學院 理學院, 西安 710077)

TV(Total Variation)模型用于圖像修復時沒有考慮缺損區域的方向信息, 并且存在收斂速度緩慢以及修復質量較低等問題. 針對圖像上方向特征明顯的條狀缺損區域, 提出帶方向的TV圖像修復算法(ADTV). 該算法分別針對4種方向(0度、45度、90度、135度)對TV算法離散格式進行改進, 并引入方向判斷, 將缺損區域歸類到此4種方向進行修復. 實驗結果表明, 該算法充分利用了條狀缺損區域的方向信息, 有效提高了圖像修復質量.為提高修復效率, 將網函數插值分別與TV算法、ADTV算法相結合提出Net-TV算法、Net-ADTV算法. 實驗結果表明, 結合算法不但有效減少了迭代次數, 降低了時間成本, 加快了收斂速度, 而且提高了圖像修復效果.

TV模型; 網函數插值; 圖像修復

1 引言

圖像修復[1]是圖像處理的重要內容, 通過對圖像上的信息缺損區域進行填充, 使修復結果符合人眼視覺連通原理. 基于TV模型[2]的圖像修復方法由于容易實現且能夠保護圖像邊緣的優勢而成為當前應用最廣泛、最成功的修復算法之一. TV模型的思想是利用物理學中的熱擴散原理將待修復區域周圍的已知信息延伸到缺損區域內部, 通過建立能量泛函, 用變分法最小化該能量泛函, 從而對圖像的缺損區域進行修復.但該算法擴散性能低, 在修復圖像上較大的缺損區域時, 不能滿足人眼視覺連通原理, 在圖像平坦區域容易產生階梯效應, 且收斂速度緩慢. 針對TV模型擴散性能低的問題, Li等[3]通過構建高階偏微分方程提高模型擴散性能以修復較大的缺損區域, 并取得較好效果, 但計算量大、修復速度慢. 林云莉等[4]通過改進TV模型, 使算法在圖像特征明顯區域采用各向異性擴散, 而在圖像平坦區域采用各向同性擴散, 有效避免了階梯效應的產生, 但在圖像細節修復上仍不能令人滿意. Ren等[5]通過對用于求解TV模型的交替方向乘子法進行改進, 使得具體的數值求解采用快速傅里葉變換方法, 算法有效加快了修復速度. 王相海等[6]通過對TV模型的擴散項引入方向梯度和邊緣引導函數以確定待修復點紋理走向, 有效保護圖像邊緣信息,但離散過程復雜. 翟東海等[7]提出的TV雙十字算法采用待修復像素鄰域8個點的信息進行修復, 有效提高了修復后的圖像質量, 但時間成本高.

網函數插值法[8]是一種多變元函數的插值法. 網函數插值算子是借助Lagrange算子, 定義在網函數空間的線性算子. 對于網函數空間中的函數, 用網函數插值算子計算得到的值是準確值, 而且結構簡單, 便于計算機操作. 在重力勘探區域場校正[9]、植物群落種群分布格局計算機模擬[10]、圖像恢復[11]、圖像Bowtie效應修正[12]等方面網函數插值法都有著有效應用, 并顯示出其優越性.

本文針對TV修復模型收斂速度慢及修復質量較低的問題, 對缺損區域設置4種不同方向, 并推導相應的離散格式, 提出帶方向的TV改進算法, 并將其與網函數插值法相結合對缺損圖像進行修復. 本文算法能夠有效進行圖像修復, 而且收斂速度快. 實驗結果驗證了算法的有效性.

2 TV修復算法與網函數插值

2.1 TV修復算法

基于TV模型的圖像修復算法, 最先由Rudin等人將應用于圖像去噪領域的全變分模型[13]推廣得到. 其主要思想是構造一個能量泛函, 通過變分法求解此最小能量泛函對圖像的缺損區域進行修復, 能量越小, 圖像就越平滑. 不考慮噪聲時, TV模型能量函數定義為式(1):

其中,u為待修復圖像,D表示圖像缺損區域, ?u表示圖像的梯度,為圖像梯度的模值. 根據變分原理,J(u)取極小值所滿足的Euler-Lagrange方程為:

如圖1所示, 待修復像素點O的4鄰域為A=｛E,N,W,S｝,A'=｛e,n,w,s｝為對應的4鄰域半像素點集合. 由差分迭代法離散(2)式得到

最終求得的uO為:

圖1 待修復點O及其鄰域像素點示

式中uP代表A=｛E,N,W,S｝四個點的像素值,up代表A'=｛e,n,w,s｝四個半像素點的像素值,uO為中心像素點O的更正值.

2.2 網函數插值

用于圖像修復的網函數插值法, 僅利用包含缺損區域最小矩形Ω的4條邊界信息, 不依賴鄰域相關性, 就可將缺損區域修復, 修復后圖像具有較好的保真度[11]. 如圖2, 記矩形Ω的4個頂點為P1(x0,y0),P2(x1,y0),P3(x1,y1),P4(x0,y1).假設Q(x,y)為Ω內任意一個點, 過點Q作矩形Ω的邊界?Ω的平行線, 平行線與Ω的四條邊相交于四個點:Q1(x,y0),Q2(x1,y),Q3(x,y1),Q4(x0,y).過點Q的平行線將矩形Ω分成四個小矩形, 小矩形的面積記作Ai（i=1,2,3,4）, 如圖2所示. 矩形Ω的面積記作A.如果f(x,y)在邊界?Ω上是已知連續的函數, 則網函數插值式為:

其中記A5≡A1.

對于相當廣泛的函數類f(x,y), 網函數插值結果F(x,y)是精確的, 其中(x,y)表示矩形內點Q的坐標.對于其它函數f(x,y),F(x,y)≈f(x,y), 即F(x,y)為f(x,y)的近似值, 且誤差與Ω的面積大小有關, Ω的面積越小, 誤差越小. 所以, 式(5)可以用于圖像數據修復, 只要所取的區域Ω的面積充分小[11]. 本文取矩形Ω為3×3的正方形,Q為正方形的中心, 這樣點Q就與圖像上待修復點O重合, 正方形邊界上各點與點O的鄰域相對應, 對應關系如圖1所示. 將待修復點鄰域8個點代入網函數插值公式(5)進行修復, 此時式(5)中Ai=1（i=1,2,3,4）,A=4, 式(5)變為下式:

經式(6)多次循環修復后, 缺損區域周圍信息擴散到缺損區域內部. 可以看出, 網函數插值只需進行2次乘法運算和7次加法運算, 計算量很小. 因此, 本文利用網函數插值對圖像缺損區域進行修復, 既可以提高運算效率, 又可以保證圖像修復效果.

圖2 矩形Ω示意圖

3 本文算法

3.1 帶方向的TV圖像修復算法

V模型在離散過程中只考慮了待修復點鄰域4個點的信息, 如式(4),uO是由鄰域四點像素值加權平均得到, 并且沒有考慮待修復區域方向信息. 由于信息較少, 其修復結果精度并不高. 事實上, 修復區域方向信息對修復結果具有很大影響. 本文針對0度、45度、90度、135度四種方向條狀待修復區域構造相應的TV離散格式, 并將其它方向條狀待修復區域歸結到此四種改進TV模型進行修復. 由于在離散過程中考慮更多的信息可以有效提高修復精度, 這四種離散格式均采用待修復點鄰域6點構造得到. 將此算法稱為帶方向的TV修復算法, 簡稱ADTV算法.

由于圖像缺損區域內部的信息是不準確的, 如果在修復過程中仍然利用這些不準確的信息對圖像缺損區域進行填充, 顯然將導致修復結果不佳. 對于不同方向的缺損區域, 可以通過設計算法巧妙地避免使用不精確點的信息. 根據缺損區域的不同方向, 分別利用待修復點周圍不同的6個點的信息對中心像素點進行修復. 針對0度、45度、90度、135度四種方向的缺損區域, 依次構造出TV0度算法、TV45度算法、TV90度算法、TV135度算法四種子算法. 此四種子算法進行修復時采用的6個點的分布情況如圖3所示.容易看出, 各個子算法所采用6個點均呈現出了明顯的方向特征. 以下對ADTV算法中4個子算法的離散格式進行詳細推導.

圖3 ADTV算法鄰域示意圖

3.1.1 ADTV算法離散方式

a. TV0度算法

對于0度方向的缺損區域,W,E兩點正處于缺損區域內部, 信息不準確, 因此在對TV模型進行離散時, 分別利用此兩點上下鄰域的像素平均值來代替其真實像素值, 即

離散過程與原TV模型一致. 將式(7)代入式(4),可以推導出TV0度算法公式:

由式(8)可以看出, TV0度算法公式是采用{NW,N,NE,SW,S,SE}6個點的信息對待修復點O進行修復, 并且利用缺損區域的方向信息有效地避免了不精確點W,E對結果的影響.

b. TV90度算法

對于90度方向的缺損區域, 與0度方向的情況類似. 由于N,S信息不準確, 分別用其左右鄰域的像素平均值來代替其真實像素值, 即

從而推導出TV90度算法公式:

由式(10)可以看出, TV90度算法公式是采用｛NW,W,SW,NE,E,SE｝ 6個點的信息對待修復點O進行修復, 避免了不精確點N,S對結果的影響.

c. TV45度算法

對于45度方向的缺損區域,NE,SW兩點的信息往往不準確, 因此利用｛NW,N,W,S,E,SE｝這6個像素點對O點進行修復.

定義NW,NE,SE,SW四個點的半像素點分別為nw,ne,se,sw, 此四個半像素點均為虛擬點,nw/2,ne/2,se/2,sw/2為其對應的半像素點(對應圖4中最內側小正方形的四個頂點), 各點分布情況如圖4所示. 采用式(11)進行近似:

圖4 待修復點O及鄰域虛擬點示意圖

利用nw,ne,se,sw四點對TV算法進行離散, 具體而言, 令由差分表示為:

其中

的離散方式與Jne/2相同. 將式(11), 式(13)與式(14)代入式(12)得

d. TV135度算法

對于135度方向的缺損區域,NW,SE兩點信息往往不準確, 在離散過程中采用｛NE,N,E,S,W,SW｝這6個像素點的信息. 離散過程與TV45度算法類似, 可得到TV135度算法公式:

3.1.2 ADTV算法步驟

在進行實驗時, 通常先人為地破壞原始圖像, 即用戶給定缺損區域的掩碼信息, 然后根據缺損區域周圍的信息, 利用圖像修復算法自動填充缺損區域. ADTV算法的4個子算法是基于方向特征的圖像修復算法, 適于修復具有明顯方向特征的條狀缺損區域.因此需要先對實驗圖進行條狀劃痕破壞, 使每條劃痕均呈現出較為明顯的方向特征. 在利用ADTV算法進行圖像修復之前, 需要先判斷出圖像上各缺損區域的方向.

本文采取的判斷方向的方法是: 找出每個缺損區域的質心, 再分別計算質心沿四個方向的線段長度,取最長線段對應的角度作為該缺損區域的方向. 這樣處理可以使得所有的條狀缺損區域都歸結于0°, 45°, 90°, 135°四個方向. 計算質心）的公式如下:

其中（xi,yj）表示缺損區域內點(i,j)的坐標. ADTV算法步驟如下:

Step1: 讀入缺損圖像u及原始圖像u0, 確定缺損區域.

Step2: 判斷圖像上每一個缺損區域的方向.

Step3: 根據當前待修復點所在缺損區域的方向,選用相應的子算法進行修復. 例如, 缺損區域方向為45度, 則選用式(16)對像素值進行更新, 并保存到新圖像中.

Step4: 判斷是否達到最大迭代次數, 若是, 繼續修復下一個缺損區域, 否則, 返回執行Step3.

3.2 結合網函數插值與TV模型的圖像修復算法

考慮到TV算法與第3.1節提出的ADTV算法雖然可以有效地保護圖像邊緣, 但需要多次循環后方能達到較好效果, 時間成本高. 而網函數插值法時間成本低, 但不能有效保護圖像邊緣. 因此, 研究此兩種算法的結合算法, 使其同時具有修復效果好和收斂速度快的特點是十分必要的. 本文將網函數插值法分別與TV模型、ADTV算法相結合, 提出Net-TV算法與Net-ADTV算法.

Net-TV算法在每一次迭代過程中, 都是對圖像缺損區域內每一個點先執行網函數插值式(6), 再執行TV算法式(4). 結合算法可以利用網函數插值計算量小的特點, 快速完成初步填充, 然后利用TV算法進行各向異性擴散, 完善圖像細節. 這樣迭代一次后, 得到的更為精確的點, 可以在下次迭代中得到進一步的矯正. 從而經多次迭代后, 得到更好的修復效果.

Net-TV算法的偽代碼如下:

Net-ADTV算法是先判斷缺損區域的方向, 并根據方向選取相應的ADTV子算法. 同樣地, Net-ADTV算法在每一次迭代過程中, 都是對圖像缺損區域內每一個點先執行網函數插值式(6), 再執行相應的ADTV子算法. 具體算法流程如圖5.

設置最大迭代次數T, 對待修復圖像的每一個缺損區域按圖5的流程進行修復. 判斷圖像上缺損區域方向的方法與ADTV算法一致.

圖5 Net-ADTV算法流程圖

由3.1節內容可以看到, ADTV算法比較適于修復圖像上方向特征明顯的條狀缺損區域, 局限性強. 事實上, 圖像上的缺損區域往往并不是規則的, 對于這一類含任意方向缺損區域的圖像, 顯然ADTV算法無法直接應用. 若是先對缺損區域進行分段, 用折線逼近, 再根據各段的方向, 利用ADTV算法解決, 可以作為對ADTV算法的一種擴展. 當然該方法仍有局限,預處理耗時多, 不容易滿足圖像處理的實時性要求.而Net-TV算法對圖像的缺損區域形狀沒有限制, 因此對于包含非規則條狀缺損區域的圖像, 可以采用Net-TV算法進行修復處理.

4 實驗結果及分析

本文實驗環境: 2.70GHz Pentium(R) Dual-Core處理器、1.87GB內存、Windows XP操作系統、MATLAB2010(a)開發環境. 為驗證本文提出的ADTV算法、Net-TV算法與Net-ADTV算法的修復效果, 將此3種算法與經典的TV算法、文獻[7]中的雙十字TV算法進行對比實驗. 對圖6中的兩幅缺損圖像分別采用五種算法迭代相同次數進行修復, 修復結果如圖7和圖8所示, 各算法修復后圖像相應的PSNR值如表1所示. 圖7、圖8的1至5行分別表示TV算法、雙十字TV算法、ADTV算法、Net-TV算法、Net-ADTV算法迭代30次、50次、100次、300次時的修復效果.可以看出, 采用TV模型修復后的圖像, 經多次迭代后圖像上仍然殘留有部分難以去除的痕跡, 影響視覺效果, 而且收斂速度緩慢. 雙十字TV算法是兩個TV算法的疊加, 修復后圖像較TV算法有更好的效果. Net-TV算法單次迭代效率高, 與雙十字TV算法修復效果相當. ADTV算法不但可以很好地去除圖像中的劃痕,而且比TV模型修復時收斂速度更快, 但可以明顯地看到ADTV算法在修復斜向區域時要比修復橫向或縱向缺損區域收斂速度慢. 而Net-TV算法、Net-ADTV算法在修復圖像時有效地解決了這一問題, 甚至Net-ADTV算法只迭代50次就達到了很好的效果.

圖6 原圖像及缺損圖

從表1可以看出, ADTV算法與Net-TV算法比TV算法修復效果好, 同時, 在達到相同修復效果時比TV算法迭代次數要少. 而Net-ADTV算法在保持修復效果的情況下, 進一步減少了迭代次數, 明顯優于雙十字TV算法.

由于各個算法計算復雜度不盡相同, 迭代次數的多少不能完全說明算法修復效率的高低, 因此需要引入時間成本對各算法進行比較. 圖9和圖10分別為各算法在對兩幅圖像修復過程中, 消耗時間隨迭代次數變化曲線以及PSNR隨時間變化曲線. 在圖9中, TV算法與ADTV算法單次迭代時間相差不大, 而Net-TV算法與Net-ADTV算法單次迭代時間略高于其它兩種算法, 這是算法結合網函數插值的必然結果, 但仍然遠低于雙十字TV算法單次迭代的時間. 從圖10中可以看出, 在相同時間成本下, Net-ADTV算法PSNR高于其它算法. 與此同時, 當PSNR達到同一水平時, Net-ADTV算法用時最短, 這是由于Net-ADTV算法只需要迭代較少的次數就可以得到較高的質量. 由于ADTV算法與Net-ADTV算法修復前需要判斷缺損區域方向信息, 所以圖10中曲線起初與橫軸保持平行,之后快速上升. 綜上所述, Net-ADTV算法雖然是通過增加單次迭代時間成本以提高修復質量, 但只需要較少的迭代次數, 從而降低了總體時間成本. 這表明, Net-ADTV算法不但修復效果好, 而且修復效率高.

5 結語

本章通過對圖像缺損區域方向信息設置4種不同方向, 提出帶方向的TV圖像修復算法, 即ADTV算法,該算法繼承了TV算法能夠保護圖像邊緣等優點, 同時綜合缺損區域方向信息和待修復點鄰域6個點的信息, 有效提高了修復質量, 但在修復斜向缺損區域時的收斂速度相對于橫向和縱向時慢了許多. 針對該問題, 本文將TV算法、ADTV算法分別與網函數插值相結合提出Net-TV算法、Net-ADTV算法. 此兩種算法將網函數插值運算效率高的特點很好地融合在TV算法與ADTV算法中, 在保持TV算法與ADTV算法修復效果的前提下, 有效減少了迭代次數, 降低了時間成本, 從而加快了收斂速度. 但ADTV算法是基于四種方向的離散格式提出的, 只適合修復方向特征明顯的條狀缺損區域, 受圖像缺損區域形狀限制較大, 因此對于圖像上非規則的缺損區域, 可采用Net-TV算法進行修復.

圖7 各算法對缺損圖像B的修復效果比較

表1 各算法對缺損圖像A、B、C修復后PSNR結果

圖8 各算法對缺損圖像A的修復效果比較

圖9 各算法消耗時間隨迭代次數變化曲線

圖10 各算法PSNR隨時間變化曲線

1 Bertalmio M, Sapiro G, Caselles V, et al. Image inpainting. Annual Conference on Computer Graphics and Interactive Techniques. 2000. 417–424.

2 Shen J, Chan TF. Mathematical models for local nontexture inpaintings. SIAM Journal on Applied Mathematics, 2002, 62(3): 1019–1043.

3 Li P, Li SJ, Yao ZA, et al. Two anisotropic fourth-order partial differential equations for image inpainting. IET Image Processing, 2013, 7(3): 260–269.

4 林云莉,趙俊紅,朱學峰,等.改進的TV 模型圖像修復算法.計算機工程與設計,2010,(4):776–779.

5 Ren D, Zhang H, Zhang D, et al. Fast total-variation based image restoration based on derivative alternated direction optimization methods. Neurocomputing, 2015, 170: 201–212.

6 王相海,王爽,方玲玲.圖像修復的方向梯度TV模型研究.吉林師范大學學報(自然科學版),2012,5(2):1–7.

7 翟東海,段維夏,魚江.基于雙十字TV模型的圖像修復算法.電子科技大學報,2014,43(3):432–436.

8 邱佩璋,陳啟宏.網函數插值理論及其應用.上海:上海科學技術出版社,2007.

9 邱佩璋,楊真榮,崔力科.網函數插值法在重力場區域校正中的應用.石油物探,1991,30(2):83–88.

10 楊持,郝敦元,楊在中.羊草草原群落水平格局研究.生態學報,1984,4(4):345–353.

11 戴芳,許曉革,邱佩璋.Coons 型分形曲面片在靜止圖像恢復中的應用.工程圖學學報,2002,23(3):165–168.

12 宋莎莎,張杰,孟俊敏.基于網函數插值的MODIS Level 1B圖像Bowtie效應修正.遙感技術與應用,2010,(4):552–559.

13 Rudin LI, Osher S, Fatemi E. Nonlinear total variation based noise removal algorithms. Physica D: Nonlinear Phenomena, 1992, 60(1): 259–268.

Image Inpainting Based on Net Function Interpolation and TV Model

HOU Hai-Na1, DAI Fang1, YANG Chen-Dong212
(School of Science, Xi’an University of Technology, Xi’an 710054, China) (School of Science, Xi’an Aeronautical University, Xi’an 710077, China)

TV(Total Variation) model is used for image inpainting without taking the direction of damaged areas into account, while its slow convergent rate and low inpainting quality are either not as good as expected. To handle these problems, Additional Direction Total Variation (ADTV) algorithm is proposed, which aims at the strip damaged areas with obvious direction characteristic in the image. In this algorithm, discrete formats of TV model are improved in corresponding four directions (0°, 45°, 90°, 135°). The damaged areas will be inpainted in the four types by judging their directions. The experimental results show that the method makes full use of the direction information of the strip damaged areas, and effectively improves the inpainting quality. Finally, in order to improve the efficiency of inpainting, Net-TV algorithm and Net-ADTV algorithm are proposed by combining net function interpolation with TV model and ADTV algorithm respectively. The experimental results show that the combined algorithm not only effectively reduces the number of iterations and time cost, speeds up the convergence rate, but also improves the quality of image inpainting.

TV model; net function interpolation; image inpainting

陜西省工業科技攻關項目(2015GY004)

2016-03-13;收到修改稿時間:2016-05-03

10.15888/j.cnki.csa.005495