基于非局部平均濾波和快速行進法圖像修補算法

收稿日期：2007-11-29；修回日期：2008-03-10

基金項目：國家“973”計劃資助項目（2006CB708305）；國家自然科學基金資助項目（10671066）

作者簡介：王坤成（1982-)，男，重慶人，碩士，主要研究方向為偏微分方程圖像處理 (kunchengking@gmail.com)；邢順來(1973-)，男，講師，博士研究生，主要研究方向為圖像處理；李志斌(1960-)，男，教授，博士，主要研究方向為數字圖像處理、符號計算*

(華東師范大學 計算機科學與技術系， 上海 200062)

摘 要：快速行進算法（FMM）與水平集法（level set）相結合進行曲線修補是一種高效的圖像修補算法，但是這種算法在修補較大區域時會產生模糊。最近，Buades 等人提出了基于非局部平均濾波（non-local means）的去噪算法。受其啟發，應用非局部平均濾波的思想進行圖像修補，提出了一種新的基于非局部平均濾波和快速行進算法的FMM-NL圖像修補算法。實驗結果表明，FMM-NL圖像修補算法針對具有較強紋理信息的圖像能有效解決FMM修補算法中的模糊問題。

關鍵詞：非局部平均濾波; 圖像修復; 圖像修補; 快速行進法; 水平集

中圖分類號：TP391.41

文獻標志碼：A

文章編號：1001-3695(2008)10-3042-03

Image inpainting based on non-local means algorithm and fast marching method

WANG Kun-cheng， XING Shun-lai， LI Zhi-bin

( Dept. of Computer Science Technology， East China Normal University， Shanghai 200062， China )

Abstract:Fast marching method (FMM) was an efficient inpainting algorithm for level set applications， but it would cause blur problem for big damaged portions of digital images. Recently， Buades presented a new image denoising method based on the non-local means (NL-means) algorithm. This paper presented a new image inpainting method (FMM-NL algorithm) which based on the non-local means algorithm and fast marching method. Experimental results illustrate that the FMM-NL inpainting method can well solve the blur problem for texture image.

Key words：non-local means; image restoration; image inpainting; fast marching method (FMM); level set

圖像修補是當前計算機圖形學、計算機視覺和圖像處理領域的研究熱點之一。它在藝術品的修補、網絡數據傳輸、計算機動畫、影視特技、虛擬現實等方面具有廣泛的應用前景。從數學的角度來看，圖像修補就是根據空白區域周圍的信息將圖像添入空白區域中，屬于圖像恢復的研究。在進行圖像修補時，通常先用掩碼(mask)確定需要修補的區域，然后根據修補區域周圍的信息用圖像修補算法自動恢復區域中的信息。

Bertalmio等人[1]提出了一種基于偏微分方程的BSCB 算法，利用待修補區域的邊緣信息，將待修補區域外的信息沿梯度的垂直方向擴散到修補區域內，取得了很好的效果。受到Bertalmio等人工作的啟發， Chan等人[2]提出了將全變分(total variational)模型用于圖像修補， 許威威等人[3]提出了改進的全變分模型。全變分算法是一種較好的異向擴散算法，該算法可以在保持邊緣的同時達到去噪的目的。Criminisi等人[4]提出了一種基于紋理生成的修補方法，在待修補區域的邊界通過塊匹配的方法選擇合適的紋理填充，對紋理修補有較好的效果，但對結構信息修補效果較差。針對TV模型的缺點， Chan等人[5]提出的基于曲率擴散的CDD修補模型能對較大破損區域進行修補，但是造成了一定程度的模糊。

雖然圖像修補基本思想十分簡單，但是上面提到的許多圖像修補算法都十分復雜，難以實現。2004年Telea等人[6]提出了一種基于快速行進算法（FMM）的圖像修補技術。由于其采用了FMM的水平集曲線進化算法，大大提高了圖像修補速度。但是基于快速行進算法的圖像修補技術針對較大修補區域時存在一些缺陷，只能對很狹小的區域有較好的修補效果，而較大的區域將產生模糊，如圖1、2所示。這是因為該方法修補過程中僅僅采用局部信息，當修補到內部區域時，必然會采用到周圍剛計算出來的新的像素點。而這些新的像素點是存在誤差的，從而導致誤差一層層向內傳遞，使誤差愈來愈大，最后出現模糊現象。

1 基于NL的去噪算法

11 傳統的濾波去噪算法

記去噪算子為Dh，那么濾波模型可寫成如下的一般形式：Dh(u)(x)=∫Ωw(x，y)u(y)dy（1）

在傳統的低通濾波模型中，權函數w(x，y)只與空間分布有關，處理后的圖像中，每個像素的灰度值是在其小鄰域內的像素上作灰度加權運算得到，其表達式為LPF（u）(x)=∫ΩwD(x，y)u(y)dy（2）其中：wD(x，y)為衡量像素x和y在幾何上鄰近關系的權函數。在此基礎上，雙邊濾波模型增加了衡量該像素和其鄰域內像素的灰度值接近程度的權因子。其表達式如下：BF(u)(x)=∫ΩwD(x，y)wR(x，y)u(y)dy（3）其中：wR(x，y)為衡量像素之間灰度值的相近程度。

12 基于NL的去噪算法

最近Buades等人[7，8]對雙邊濾波算法作了進一步的推廣，提出了非局部平均濾波算法（non-local means algorithm）。該算法是對傳統局部去噪模型的一個革新。因為自然圖像中往往含有許多冗余信息，充分利用這些冗余信息為去噪服務，這是非局部平均濾波模型(以下簡稱NL模型)的主要思想。NL模型的主要特點是：該方法不是用圖像中單個像素的灰度值進行比較，而是對該像素周圍的整個灰度分布狀況進行比較，根據灰度分布的相似性來貢獻權值。

如圖3，雖然p、q1和q2具有相同的灰度值，顯然q1的鄰域灰度分布與p比較接近。那么q1對p的權值貢獻會比較大，而q2對p就幾乎沒有權值貢獻。

給定一個離散的噪聲圖像u={u(i)|i∈I}， u(i)表示像素i的灰度值。設處理后像素i的灰度值為NL[u](i)，計算公式如下:NL[u](i)=∑j∈Iw(i，j)u(j)(4)權值w(i，j)取決于灰度向量v(Ni)和v(Nj)。其中：v(Nk)代表以第k個像素為中心的四邊形鄰域。給出如下權值定義：w(i，j)=1/Z(i) exp(-‖v(Ni)-v(Nj)‖²2，α/h²)（5）其中：Z(i)=∑j∈Iexp(-‖v(Ni)-v(Nj)‖²2 ，α/h²)為權值歸一化參數；h為權值衰減控制參數。h值太小，去噪不充分，太大會造成圖像模糊。如果圖像包含的是方差為σ²的白噪聲，一般情況下h取值為10σ~１５σ。

2 基于NL的修補算法

如圖4所示，設當前待修補點為p，待修補區域為目標區域Ω。根據手工修補圖像的原則，常常采用相似點的灰度值來填補待修補點的灰度值。因此，雖然q1和q2兩點灰度值相同，但q1的鄰域灰度分布與p更接近。那么q1對p的權值貢獻會比較大，而q2對p的權值貢獻就幾乎為零。

根據上述修補原則，下面給出非局部平均濾波修補算法的具體實現步驟。

由于RGB圖像中的R，G，B三通道具有類似的結構分布信息，不妨考慮灰度圖像。 給定離散灰度圖像u={u(i)|i∈I}，u(i)表示像素i的灰度值，設當前待修補像素點為i，未修補區域為Ω，修補后像素i的灰度值為NL[u](i)，則計算公式為NL[u](i)=∑j∈I-Ωw(i，j)u(j)(6)權值w(i，j)取決于v(Ni)和v(Nj)。其中：v(Nk)代表以第k個像素為中心的四邊形鄰域。

由于圖像修補時未修補區域處的像素值是未知的，當計算權值w(i，j)時需要引入有效區域和有效區域率的概念。

設v(Nk)代表以第k個像素為中心的(2N+1)×（2N+1）鄰域，則v(Ni)和v(Nj)之間的有效區域率為兩個區域對應像素點的灰度值都已知的點的集合占(2N+1)×(2N+1)區域的比例，對應已知的點的集合稱為有效區域。

設pi∈v(Ni)和qi∈v(Nj)為兩個區域對應像素點，有效區域為Ωi，有效區域率為Ki，則Ki=count(Ωi)/(2N+1)²（7）

‖v(Ni)-v(Nj)‖²=∑Ωi‖u(pi)-u(qi)‖²（8）

另外，當有效區域率Ki太小時，會導致點j周圍有效信息太少，無法判斷是否為點i的相似點，此時應置權值w(i，j)=0，以免發生誤差。綜上，本文給出如下權值定義： w(i，j)=1/Z(i)exp(-‖v(Ni)-v(Nj)‖²/h²) Ki＞μK

0Ki≥μK（9）其中：Z(i)=∑j∈I-Ωexp(-‖v(Ni)-v(Nj)‖²/h²)為權值歸一化參數; h為權值衰減控制參數;μK取0.3左右。

3 基于FMM的修補算法

Telea[6] 提出了基于快速行進的修補算法，其修補一個像素的算法是基于加權平均數學模型的。

如圖5所示，給定一離散灰度圖像u={u(i)|i∈I}，u(i)表示像素i的灰度值，規定Bε(p)為待修補像素p周圍一個大小為ε的鄰域。Bε(p)中的像素q對p的貢獻uq(p)可用下式表示：uq(p)=u(q)+u(q)(p-q)（10）其中：u(q)表示q的梯度值。這樣，p的灰度值可用Bε(p)中所有已知像素對p的貢獻點加權平均求得，計算公式如下：FMM[u](p)=[∑q∈Bε(p)w(p，q)uq(q)]/[∑q∈Bε(p)w(p，q)]（11）其中：Bε(p)程序中采用p的8-鄰域，權值w(p，q)則使用下式求得：w(p，q)=dir(p，q)×dst(p，q)×lev(p，q)（12）其中：dir(p，q)=(p-q)/‖p-q‖×N(p)，dst(p，q)=d²0/‖p-q‖²，

lev(p，q)=T0/(1+|T(p)-T(q)|)。N(p)是p的梯度方向，在程序中d0、T0取1，T(m)是m點到達窄帶的時間（參見文獻[6]），‖p-q‖是p點與q點的距離值。dir(p，q)是p點法線方向上的像素q對p點的影響，距離越小對p點的貢獻越大；dst(p，q)表示q點和p點之間距離對修補p點的影響，距離越大影響越小；lev(p，q)考慮的是等值線方向上的像素q對修補p點的影響，距離越遠影響越小。

4 FMM-NL修補算法

Telea[6]提出的基于FMM的修補算法是基于局部信息的圖像修補技術，而前面提出的非局部平均濾波(NL-means)修補算法是基于全局信息的修補技術。基于FMM的修補算法能夠快速地根據鄰域信息修補像素，而忽略了全局信息，導致修補較大區域時出現模糊；而基于NL的修補算法僅僅考慮全局信息，導致局部光照等信息無法向修補區域內部傳遞。因此本文將上述兩種修補算法結合，提出了新的基于非局部平均濾波和快速步進法的圖像修補算法（簡稱FMM-NL修補算法），它不但能夠修補強紋理圖像較大損壞區域，而且針對弱紋理圖像的較小損壞區域也能夠得到較好的修補效果。

顯然，在基于FMM的修補算法中修補當前點時，需要加入判定條件。如果整個圖像中存在具有相似鄰域的點，優先采用基于NL的全局修補算法，否則采用基于FMM的局部修補算法。下面給出修補判定定理。

定理1 設當前待修補像素點為i，按式（9）計算出w(i，j)，j∈I-Ω，設最大權值為maxWi，則

基于NL的修補算法

maxWi＞μW

基于FMM的修補算法 maxWi≤μW

其中：μW為一接近1的常數。

在修補之前先對圖像進行預處理，對于圖像中的每一點設定三個值，即T、f和I。其中： T是該點到修補邊界的距離; I為該點的像素值; f為該點的標志，可以取為arrive、narrowband和faraway三個值。其意義如下:a)Arrive說明該點在修補邊界外部，是修補時利用的點，其T值和I值已知;b)Narrowband說明該點在修補區域的邊界上，屬于待修補的點，其T值和I值正待更新; c)Faraway說明該點在修補區域內部，其T值和I值未知。

在更新T值時，基于FMM的修補算法將問題變為求解一個表示曲線隨時間進化的Eikonal方程，其離散差分求解公式如下：max(D-xT， -D+xT，0)²+max(D-yT，-D+yT，0)²=1（13）其中：D-xTi，j=Ti，j-Ti-1，j，D+xTi，j=Ti+1，j-Ti，j，同理可得D-yTi，j，D+yTi，j。

FMM-NL算法進行圖像修補的基本思想，即修補工作一直在待修補區域的邊界上進行，通過控制修補區域邊界的向內收縮來達到修補整個區域的目的。修補過程如下：

a)初始化

(a)首先對要修補的圖像手工制作二值模板，要修補的區域在模板上對應位置為黑色(像素值為0) ，無須修補部分為白色(像素值為1)；

(b)對于模板圖像，若I(x，y)=0，說明該點在要修補的區域內，令f(x，y)=faraway， T(x，y)=+∞;

(c)若I(x，y)=1，說明該點在要修補的區域外，令f(x，y)=alive， T(x，y)=0;

(d)若I(x，y)=0且點(x，y)的四鄰域中存在點(i，j)滿足I(i，j)=1， 這說明該點為修補區域邊界上的一點，令f(x，y)=narrowband， T(x，y)=0;

(e)將f值為narrowband的點放入一個名為band的棧中，它們按照T值從小到大順序排列。

b)修補

(a)從band中選擇具有最小T值的點，設為(imin，jmin)；

(b)對點(imin，jmin)根據定理1修補，并將其f值改為arrive，從band點集中刪除;

(c)將(imin，jmin)的鄰域點(imin-1，jmin)， (imin+1， jmin)， (imin， jmin-1)和(imin， jmin+1)中f值為faraway的點加入到band中;

(d)由Eikonal方程的差分形式（式（13））更新鄰域點的T值;

(e)轉(a);

(f)當band中無新的像素加入時，說明修補區域已經填充好，結束循環。

5 實驗結果與分析

為了檢驗本文算法的修補效果，采用VC++ 6.0 實現了本文算法，微機配置Pentium4 2.0 GHz CPU， 512 MB RAM 。

實驗時，首先給出一張分辨率為188×220的原始圖片(Float.bmp)，其mask圖像為圖6(a) ，加上mask圖像后損壞的圖像為(b)；然后，分別采用Telea提出的基于FMM的修補算法，以及本文提出的FMM-NL算法對(b)進行修補。基于FMM的修補算法修補結果如(c) 所示；FMM-NL修補算法修補結果如(d)所示。顯然，當修補區域較大時，基于FMM的修補算法產生了模糊，而基于FMM-NL的圖像修補算法則有較好的修補效果。

其次，給出一張分辨率為371×432的原始圖片Linc.bmp (圖7(a))，其加上mask圖像后的圖像為(b)。 基于FMM的修補算法修補結果如(c) 所示，FMM-NL圖像修補算法的修補結果如(d)所示。放大圖片可以發現，由于FMM-NL圖像修補算法利用了頭發的紋理信息，在頭發部分修補效果更好。

6 結束語

非局部概念的引進使得FMM-NL修補算法在修補效果上有了大幅度的提高。由于該算法能充分利用圖像的自相似冗余信息，尤其適用于強紋理圖像的修補。該算法和基于FMM的修補算法相比，其權值確定不是簡單地通過單個像素上灰度的比較，而是根據由該像素為中心的小鄰域上灰度分布的相似性來確定權值貢獻。如果在圖像其他地方有很相似的像素點，則確認此點為紋理點，優先采用基于NL的修補算法；否則才采取基于局部信息的FMM修補算法。這樣比先前的方法更穩定、更具可靠性。由于對每個像素都采取鄰域比較的方法，明顯增加了計算量，這也使得該方法的應用受到限制。數值實驗中還發現，由于一些圖像本身紋理分布不均或紋理信息不夠，使得該模型修補后，在圖像的平滑區域留有人工紋理。如何減少計算量和消除人工紋理等問題都是今后要研究的主要目標。

參考文獻：

[1]BERTALMIO M，SAPIRO G，CASELLES V， et al. Image inpainting[C]//Proc of SIGGRAPH. New York:[s.n.]， 2000:417-424.

[2]CHAN T F， SHEN J. Mathematical models for local non-texture inpaintings [J]. SIAM Journal on Applied Mathematics， 2002， 62(3): 1019-1043.

[3]許威威，張明敏，潘志庚.一種基于全變分的圖像修補算法[J].中國圖象圖形學報，2002，7(4):351-355.

[4]CRIMINISI A， PEREZ P， TOYAMA K. Objects removal by exemplar-based inpainting[C]//Proc of CVPR’03. 2003:721-728.

[5]CHAN T F， SHEN J. Non-texture inpainting by curvature-driven diffusion (CDD)[J]. Journal of Visual Communication and Image Representation， 2001，12(4):436-449.

[6]TELEA A. An image inpainting technique based on fast marching method[J]. Journal of Graphics Tools， 2004，9(1):25-36.

[7]BUADES A， COLL B， MOREL J. On image denoising methods[R]. Spain: CMLA， 2004:15.

[8]BUADES A， COLL B， MOREL J. A non-local algorithm for image denoising[C]//Proc of IEEE International Conference on Computer Vision and Pattern Recognition. 2005:60-65.