基于各向異性插值模型的快速圖像修復方法

(1.河海大學 土木工程學院， 南京 210098;2.南京信息工程大學 遙感學院， 南京 210044)

摘 要：基于偏微分方程的圖像修復算法運行緩慢，且無法恢復紋理細節，實用性較差。基于地統計學思想，提出一種簡單有效的基于各向異性插值模型的圖像修復方法。實驗表明該方法具有計算復雜度低和能夠恢復圖像紋理細節的優點，對于圖像小區域劃痕具有很好的修復效果，具有較高的實用價值。

關鍵詞：圖像修復；插值；各向異性

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2009)04-1554-03

Fast image inpainting algorithm based on anisotropic interpolation model

CHEN Ren-xi1，LI Xin-hui2

(1.College of Civil Engineering， Hohai University， Nanjing 210098， China;2.School of Remote Sensing， Nanjing University of Information Science Technology， Nanjing 210044， China)Abstract:Partial differential equation based image inpainting algorithms have disadvantage of high time consuming and are not practical. Based on the thinking of spatial statistic，this paper presented an inpainting algorithm using an anisotropic interpolation model. Experiment results show that the algorithm has the advantages of low computation cost and texture preserved ability.The algorithm is suitable for restoring missing information in small regions such as scribed gaps and is practicable in applications.

Key words:image inpainting;interpolation;anisotropic

0 引言

數字圖像修復是目前新穎而前沿的研究熱點，在照片潤飾、視頻文字去除、圖像目標隱藏、圖像壓縮、印刷出版等方面具有廣闊的應用前景。圖像修復的目的是恢復圖像中缺失的信息。根據待處理區域的大小，圖像修復總體上分成兩大類：基于圖像幾何模型的修復方法(inpainting)，主要適用于劃痕等小區域的處理；基于紋理的圖像補全技術(completion)，適合于大面積缺失區域的恢復[1]。這兩類方法各有優缺點，適合于不同的情況。其中，inpainting最早由Bertalmio等人[2]提出，他們采用基于偏微分方程(partial differential equation，PDE)的算法，利用擴散方程，將待修復區域外圍的信息沿著等照度線(isophote)方向向內傳播，達到恢復丟失信息的目的；Chan等人[3]提出基于總變分(total variation)的修復方法;張紅英等人[4]提出p-Laplace各向異性擴散算法。這些基于PDE的方法取得了一定的成果，但在實際應用中還存在一些缺陷：

a)需要大量迭代運算，處理速度非常慢，實用性不夠強；

b)不能恢復某些紋理細節，造成修復區域的模糊現象。

為了克服這些缺陷，本文仍針對圖像劃痕等小面積修復的問題，將圖像看做三維曲面，模擬三維局部曲面重建，力圖找出一種簡單而有效的解決方法。通過將地統計學(geostatistic)的思想引入其中，提出一種簡單快速的各向異性插值修復模型，并進行了算法實驗，取得了較好的結果。

1 修復模型

1.1 圖像的各向異性分析

在自然界，某些自然現象具有各向異性的空間分布特性，如礦產分布、空氣污染、地貌等。對于圖像的灰度值，通過觀察發現也具有相似的分布特性，特別在圖像邊緣或方向性紋理區域，灰度值并不是在各個方向上具有相同的分布規律，而具有各向異性。在地學領域，分析這種各向異性現象的強大工具是地統計學。地統計學通過變異函數來定量地描述空間變異性，變異函數中三個重要的參數是變程、基臺值和塊金值［5］。

將地統計學工具應用于圖像分析，通過對圖像局部區域計算各個方向的變異函數曲線發現：沿著紋理方向和邊緣方向，變異函數曲線具有較小的變程和基臺值，根據地統計學原理，說明該方向上像素的變異程度最小，像素間的相關性最大。這與對圖像的觀察結果一致，為各向異性插值模型提供了理論支持。

1.2 插值模型

通過以上分析，認為在圖像局部區域，灰度值具有各向異性分布特征，據此提出一種各向異性插值模型（圖1）。設圖像正常區域記為Φ，缺損區域記為Ω，缺損區域的邊界記為Ω。假設當前需要修補的像素位于邊界Ω上的p點，取p點的一個橢圓鄰域Na，b(p)。其中：a表示橢圓的長半軸；b表示橢圓的短半軸。橢圓的長半軸方向與該局部區域的紋理走向(或邊緣方向)相同。本文認為p的像素灰度值取決于橢圓鄰域Na，b(p)中的像素值，理論上可以采用基于地統計學原理的克里金(Kriging)插值方法來估計p的灰度值。

本文采用橢圓鄰域窗口來取代傳統的圓形鄰域窗口，并且橢圓長軸方向自適應性地保持與圖像局部邊緣走向一致。沿著紋理方向，像素具有更大的相關性；而垂直于紋理方向，像素具有較小的相關性。因此，橢圓鄰域窗口充分考慮到數據空間分布的特點，顧及到圖像的邊緣和紋理方向，具有更大的合理性。

基于地統計學原理的克里金插值本質上也是一種加權平均插值法，不過它能夠充分考慮數據空間場的分布規律，在插值過程中能夠反映空間場的各向異性，并能充分利用數據點之間的相關性。若直接采用克里金插值來修復圖像，則計算量比較大。首先需要統計局部區域的半變異函數值，然后選擇合適的半變異函數模型進行參數擬合，涉及到比較復雜的計算過程。另外，對每個未知點進行插值時，需要進行線性方程組的求解，當插值的未知像素比較多時，需要大量的計算時間。為了簡化插值過程，基于地統計學的思想，采用一種簡易的各向異性插值模型(圖2)。

假設點p(x0，y0)是當前需要插值的點，且該點的方向矢量(即邊緣走向)E=(Ex，Ey)。以p(x0，y0)為中心點，確定一個矩形窗口(橢圓窗口的簡化)，窗口的長軸方向與方向矢量E相同，矩形大小為a×b(且a>b)。采用矩形窗口內部的已知像素點對未知點p(x0，y0)進行插值，其灰度值G(x0，y0)由窗口內已知像素的灰度值加權平均來估計：

G(x0，y0)=Ni=1wiG(xi，yi)/Ni=1wi(1)

其中：N為窗口內已知像素的總數；權值wi的計算主要考慮已知點與p(x0，y0)之間的距離和方向兩個因素。另設p(x1，y1)為窗口內的某個已知點，p(x0，y0)與p(x1，y1)間的歐式距離為

dist=(x0-x1)2+(y0-y1)2(2)

點p(x0，y0)與p(x1，y1)之間的向量為

V=(Vx，Vy)=(x1-x0，y1-y0)(3)

向量V與方向矢量E之間的夾角記為θ：

cos(θ)=‖V#8226;E‖/‖V‖#8226;‖E‖(4)

則點p(x1，y1)的權值計算如下：

w1=1/(1+dist）(1+|cos(θ)|)(5)

從式(5)可知，這種權值計算方法同時考慮到數據點的空間距離和分布方向兩個因素。若該點距離待插點越遠，則貢獻越小，權值較小；若該點的方向越靠近主軸方向(方向矢量的方向)，則權值越大。根據前面的空間統計分析，位于主軸方向的像素與待插點具有更大的相似性，賦予較大的權值是合理的。

根據實驗表明，矩形窗口的長軸a和短軸b一般不能太大，否則影響插值效果。一般情況下，取a=5~7像素，b=3~5像素時能夠較好地保持紋理細節，若再增大窗口的尺寸會帶來一些模糊效應。

2 算法實現

2.1 預處理

本文算法需要計算圖像邊緣方向場，宏觀反映圖像邊緣和紋理走向。然而圖像噪聲往往影響計算的穩定性，為此，先對圖像進行平滑去噪。通常的平滑算子易造成圖像邊緣模糊現象，考慮采用能夠保持邊緣的平滑方法，如反梯度平均的卷積方法[6]。在計算卷積模板時，每個像素處的權值根據反梯度值來計算，其思想是區域內部的亮度變化一般比相鄰區域間要小。設卷積模板(模板一般為奇數大小，如3×3、5×5)中心像素坐標為(p， q)，則模板中的點(i， j)相對于中心點(p， q)的反梯度值為：

δ(i， j)=1/|g(p，q)-g(i， j)|當g(p，q)≠g(i， j)

2當g(p，q)=g(i， j)(6)

對于N×N大小的卷積模板h，需要進行歸一化處理，其中每個點(中心位置除外)的數值計算如下：

h(i， j)=0.5×δ(i， j)/Ni=1

Nj=1δ(i， j)(7)

另外，模板中心位置的數值取為0.5。當采用模板h對圖像進行平滑時，區域中孤立噪聲具有小的權值，采用鄰域點平均時噪聲得到消除，且能夠保持圖像邊緣不被模糊。

2.2 方向場的計算

把圖像中每個像素所在的邊緣走向(即邊緣的切線方向)定義為方向矢量，則全圖形成一個方向矢量場，反映圖像紋理和邊緣的方向。切線方向往往可以根據梯度(gradient)來計算，因為梯度與切線的方向具有互相垂直的關系。

對于每個像素點(i， j)，采用如圖3所示的梯度算子來計算該點的梯度值G(i， j)，然后將G(i， j)旋轉90°或者-90°，作為邊緣矢量E(i， j)。

采用上述方法直接計算得到的圖像方向場，結果不太理想，矢量方向不穩定，存在局部擺動 (圖4(a))。實際上，某點的方向矢量應該由該點周圍鄰域的所有像素的方向矢量共同決定，因此，采用鄰域加權平均的方法來重新計算每個像素點的方向矢量。假設一個以點(p， q)為中心的(2n+1)×(2n+1)大小的一個鄰域窗口，對于窗口中的每個像素位置(i， j)，采用“距離+1”的倒數作為該點的權值：

w(i， j)=1/[1+(p-i)2+(q-j)2](8)

實驗表明，采用3×3、5×5大小的鄰域窗口已經足夠，若增大窗口，效果不再改變，反而增加計算量。圖4（b）是采用3×3窗口對方向場進行平滑后的結果。

2.3 插值修復

完成前面的步驟后，最后進行圖像像素的修復，分為兩步進行：

a）進行方向場的恢復，以便后面的各向異性灰度插值。方向場插值可以直接采用加權平均插值方法：以待插點為中心選擇7×7大小的窗口，利用窗口內已知點上的方向矢量來估計待插點處的方向矢量，權值可采用距離倒數法。插值時從缺損區域邊界逐層向內進行。圖5是對缺失區域方向場重建的示例。

b)進行灰度值的恢復，利用前述的各向異性插值模型完成缺失區域的灰度值重建。處理順序與方向場插值一樣，由邊界向內逐層進行。

3 實驗

根據前面提出的各向異性圖像修復模型，采用C++實現了本文的算法。為了與其他的圖像修復算法進行比較，同時也實現了Bertalmio[2]和Oliveira算法[7]。另外，為了比較基于地統計學思想的各向異性插值方法和一般的插值方法的優劣，同時也采用了反距離加權平均(inverse distance weight，IDW)的插值方法對圖像進行修復。本文采用不同的方法對不同類別的圖像進行了大量的修復實驗。實驗中，在進行方向場計算時，采用5×5的鄰域窗口；在進行灰度值各向異性插值時，矩形窗口的大小選為a=7，b=3。

圖6是采用不同的方法對遙感影像上紋理區域進行修復的結果，其劃痕寬度在7~8個像素。顯而易見，采用各向異性插值方法能夠恢復精細的紋理細節，而其他方法則存在不同程度的模糊現象。

圖7是對受損的遙感影像的修復實驗，劃痕寬度在8~12個像素。從實驗結果可以看出，Bertalmio、Oliveira修復方法對于邊緣的修復效果不太好，存在比較嚴重的模糊現象；IDW插值方法也不能很好地恢復斷裂邊緣；本文的方法對斷裂邊緣的修補效果較好。

表1統計了不同修復方法的運行時間。從表中可以看出，Bertalmio算法非常耗時，遠遠超過其他方法的運行時間，因為該算法需要進行反復的迭代(本實驗中迭代1 000次)。本文的方法運行速度很快，與Oliveira快速圖像修復方法和IDW插值方法相當。

表1 圖像修復時間統計

圖像Bertalmio/minOliveira/sIDW/s本文方法/s

圖67233

圖72122

為了進一步定量地評價該算法的效果，采用三種不同類型的彩色圖像（自然風景圖像rock.bmp中國畫paint.bmp、遙感圖像RS.bmp）進行模擬實驗。先對正常圖像添加人工劃痕，模擬圖像受損，然后采用不同的修復方法對缺損區域進行修復，再比較修復后的圖像與原始正常圖像之間的誤差。這里采用均方誤差(MSE)來進行衡量，對于彩色圖像分R、G、B三個通道分別計算。 表2列出了相應的MSE統計數據(修復結果圖略)，從表中可見本文方法的MSE最小。

表2 圖像修復均方差(MSE)統計結果

圖像通道BertalmioOliveiraIDW本文方法

rock.bmpR295.92360.23406.34250.79

G291.05340.14375.89241.90

B288.57300.92332.27229.68

paint.bmp

R650.56526.85572.95437.34

G490.16474.50492.52387.20

B402.32437.26438.15346.08

RS.bmp

R2 118.201 067.841 197.05802.42

G1 981.72943.871 189.40816.01

B1 619.74734.78954.24614.96

通過以上實驗表明，從主觀視覺效果來看，本文方法能夠較好地連接圖像中的斷裂邊緣，恢復紋理結構；從定量統計結果來看，本文方法對于圖像缺損區域重建的誤差較小。

4 結束語

本文針對圖像上小區域缺失信息的修復問題，提出一種簡單高效的處理算法。該方法基于圖像像素的各向異性分布特征，采用一種各向異性插值模型，充分顧及到像素的空間分布規律，能夠較好地恢復圖像邊緣和紋理。該方法克服了PDE修復方法計算量大的缺陷，也避免了傳統IDW插值方法和Oliveira快速修復方法帶來的模糊問題，不失為一種簡單高效的解決方案。

參考文獻：

［1］張紅英，彭啟琮.數字圖像修復技術綜述[J].中國圖象圖形學報，2007，12(1):1-10.

[2]BERTALMIO M，SAPIRO G，CASELLES V，et a1.Image inpainting[C]//Proc of the ACM SIGGRAPH Conference on Computer Gra-phics.New York：ACM Press，2000：417-424.

[3]CHAN T F，SHEN J H.Mathematical models for local nontexture inpainting[J].SIAM Journal of Applied Mathematics，2001，62(3):1019-1043.

[4]張紅英，彭啟琮，吳亞東.數字破損圖像的非線性各向異性擴散修補算法[J].計算機輔助設計與圖形學學報，2001，18(10):1541-1546.

［5］侯景儒，黃競先.地質統計學及其在礦產儲量計算中的應用[M].北京:地質出版社，1982.

[6]SONKA M，HLAVAC V，BOYLE R.圖像處理、分析與機器視覺[M].艾海舟，武勃，等譯.北京: 人民郵電出版社， 2003.

[7]OLIVEIRA M M，BOWEN B，MCKENNA R，et al.Fast digital image inpainting[C]//Proc of International Conference on Visualization， Imaging， and Image Processing.2001:261-266.