基于曲率和中值濾波的快速推移圖像修復方法

摘要：提出了一種結合中值濾波和基于曲率擴散的圖像修復方法。中值濾波修復方法對于灰度值變化比較平緩的圖像，修復效果從時間性能和視覺效果上均比較好，但對于灰度值變化比較劇烈的圖像，效果不能令人滿意。在結合了基于曲率擴散的修復方法之后，中值濾波的不足之處得到了改善。基于曲率擴散的修復方法考慮了圖像本身的幾何信息，在修復圖像的幾何特征上有較高的準確度。圖像修復順序由已知區域向未知區域擴散時經過各破損點的時間決定，用快速推移方法計算該時間。實驗表明，該算法能高效、穩定地處理破損區域的圖像信息。

關鍵詞： 圖像修補； 中值濾波； 擴散； 快速推移法

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

文章編號：1001－3695(2007)08－0186－03

0引言

圖像修復技術是當前圖像處理中的一個研究熱點，在文物保護、有目的性的圖像擦除等方面有著重要的應用價值。手工圖像修復始于人們修復一些古老的藝術作品。隨著年代的久遠，很多藝術作品不可避免地出現不同程度的損壞，人們通過對原作品的理解，試圖恢復出作品本來的面目，但實踐中很多人帶著個人感情色彩去修復，在修復歷程中曾出現了很多無法挽回的悲劇。數字圖像修復技術正是以實際應用為出發點應運而生的，以一定的模型為基礎，以自動修復破損區域為過程，以盡可能使圖像整體協調統一、滿足視覺效果為目的，實現數字圖像的修復。目前一些圖像處理軟件帶有圖像修復功能，但仍不可避免大量地手工操作，使得圖像修復耗時費力。

在圖像修補技術發展中，Bertalmio等人采用偏微分方程[1，2]的方法進行圖像修復，取得了較好的效果。用偏微分方程方法進行圖像修復時，用戶需指定需要修復的區域。該算法沿著等值線進行修復，用二維離散Laplacian算子估計光滑度的變分，利用光滑度的變分沿著等值線的投影來更新破損區域的值。該算法同時利用了各向異性的擴散，以保證邊緣處的邊界連續且避免邊緣的模糊，但計算時間較長。Chan 等人提出了整體變分方法(total variational，TV)[3]和基于曲率的擴散模型(curvaturedriven diffusion，CDD)[4]。整體變分方法采用各向異性的擴散原理建模，利用歐拉—拉格朗日方程的求解過程求解。CDD方法是整體變分方法的一種擴展，在擴散過程中考慮了圖像的幾何信息（曲率），修復結果更符合人的視覺效果，但其實現效率也不高。T. K. Shih 等人提出一種自適應的圖像修復方法[5]，采用一定的策略規則，根據已知的圖像信息，估計出待修復的圖像。在離修復點一定距離的窗口內，考察已知非噪聲點占該窗口內所有點的比例，是否達到規定可信度。若是，則用鄰近已知點的中值作為修復點值，否則擴大窗口尺寸。當窗口的大小超過一定尺寸時，停止窗口尺寸的增加，用全局中值做修復點值。該方法對于圖像灰度值變化較平穩且破損面積較小的圖像是一種較有效的修復方法，但是修復的效果有時會與人們對圖像的主觀理解效果不同。

本文提出的方法正是結合了以上兩種方法的利弊，揚長避短，使得修復效果更好。把待修復的區域按圖像灰度變化的均勻程度分為兩種：灰度值變化較平穩的物體內部區域或背景區域；灰度值變化劇烈的物體的邊緣區域。對于如何判斷某點是處于哪種類型的區域之中，本文采用了下面的方法：首先給定閾值，然后找出破損點鄰域內已知非噪聲點的極大值和極小值，用兩極值之差來判斷該點是屬于物體邊緣區域，還是屬于灰度變化較小的區域。由于預先把待修復的部分涂上了一定顏色值，會影響邊界處的梯度值計算，本文沒有通過梯度幅值來確定圖像破損點所屬的區域。對于均勻的破損區域采用中值濾波的方法，計算效率高，修復的結果也好；而對于處在物體邊緣區域的破損點則采用基于曲率擴散的方法來修復，通過迭代方式更新未處理的破損區域。

1理論介紹

1．1中值濾波修復法

如果要修復破損像素點，通常利用該點周圍已知點的信息，用線性的或非線性的外推法求出該點的值。中值濾波法是一種非線性方法，它是利用鄰近已知點的像素值去獲得破損像素點的值。設一待修復點為P(i， j)，以其為中心，尺寸為WS的窗口W內已知點的值為(u1，u2，…，un)，P點的值為

若當前窗口內的破損點較多時，筆者借鑒了自適應圖像修復方法的思想，增加窗口尺寸，確保在一定可信度范圍內恢復出破損點的值。但本文的窗口尺寸變化不會像自適應方法那樣范圍較大，當窗口尺寸停止增加時，不用全局的中值作為破損點的估計，而是保持原值。本文采用了特殊的修復順序，保證了在修復時窗口的尺度不需要太大的浮動，因為它盡量從可信度大的區域進行修復。這一點可以從快速推移算法中看出。這與手工修復相類似，首先從可信度較大的點開始修復，逐步向內推進。只有在達到足夠大的可信度時，才利用鄰近的像素值對破損點的值進行修復。因此要計算覆蓋破損像素點窗口內已知點的像素數目，并規定閾值。具體做法是：首先選擇小尺寸窗口，計算可信度，若超過閾值時，用式（1）得到待修復點的值；否則采用較大的窗口進行嘗試，若仍不滿足，則該點保持原值。本文所采用的窗口尺寸為3和5，對應的閾值分別是5、15，以保證有足夠多的已知像素信息來作為該點值的估計。

1．2平均曲率擴散（CDD）修復法

該模型是由Chan等人提出的。它結合了圖像本身的幾何信息（即曲率），建立一種基于偏微分方程的圖像修復模型，一般用于非紋理圖像的修復。值得指出的是TV圖像修復模型[3]，因為CDD修復模型是在TV的方法上產生的，但TV模型在現實應用中破壞了視覺的連續性原則，在恢復細小物體邊緣上仍具有局限性。在該模型中，擴散的強度與圖像的對比度和等值線強度有關，而與曲率無關。圖1是用TV方法修復的一個例子。

中值修復后剩余的未知像素點將采用CDD方法修復。可以看到，用中值方法得到的像素值僅需一次計算即可得到，而由曲率擴散計算的像素要通過多次迭代才得到。

1．3快速推移法FMM

除了偏微分方程逐步迭代的修復方法與圖像修復的順序無關之外，其他圖像修復方法大都與修復的順序相關。通常修復的順序是按圖像掃描的順序從上到下、從左到右進行圖像修復。當破損區域較大時，按這種修復順序得到的修復效果不好。因為對于大面積連續的破損區域，若破損區域左邊或上邊的修復結果誤差較大，其向后傳播的誤差則大。為此，本文采用快速推移法（fast marching method，FMM）[7]。該方法可以一定程度地減少向后傳播的誤差。

通過式（6）得到邊緣經過各點的時間T。具體實現見文獻[7]。根據邊緣經過各個點的時間先后次序，來確定修復的順序。用圖3容易解釋快速推移法在本文中的應用：空心點屬于未知區域，灰色區域為邊界區域，黑色點屬于已接受區域。現在由已知區域經過邊界區域向未知區域擴散，從邊界區域中選取出一網格點，邊緣經過它的時間最小，并標記此點為已接受點，更新它的四鄰域中的未接受點的時間信息，直到所有點均被接受為止。可見邊界區域是一個有限寬度邊界帶。每次只前進一個單位F=1。詳細介紹見參考文獻[7]。

2算法實現

本實驗圖片均用24位RGB彩色圖像，分三個通道分別處理。其步驟如下：

b)對a）中的T由小到大排列破損點，并保存對應的像素坐標信息于堆heap中。

c)重新設置已知區域的點為可用標志(available)，破損區域的點置為不可用標志(unavailable)。

d)從堆heap中取出時間最小的一點P(i， j)，并從堆中刪除該點，用本文介紹的方法，判斷P點是否屬于較為平坦的區域。設覆蓋該點的窗口為Wsize，該窗口內已知點中最大像素值為Vmax，最小值為Vmin，用鄰域窗口內像素值的極大值、極小值之差Dif=｜Vmax-Vmin｜進行判斷：(a)若極值差Dif小于閾值，則說明該點處于較為平坦的區域，再判斷是否達到給定的可信度，若可信度滿足條件，則采用上述中值法更新該點值，并修改該點標志為可用；否則保持原狀態；(b)其余情況該點將不作任何改變，循環該步驟。

3實驗結果

4結束語

圖像修復包括紋理圖像修復和非紋理圖像修復，本方法適用于非紋理的圖像修復。在具體操作過程中，本文又對非紋理圖像待修復區域作了進一步的劃分，對于較平坦區域和灰度跳躍比較大區域分別采用不同的修復方法。對于平坦的區域通過簡單外推法效果較好，但對于灰度跳躍比較大區域，若用簡單外推法，則會導致圖像邊緣模糊，甚至丟失邊緣信息。圖像修復的關鍵在于建立圖像模型，圖像模型一旦確定，就可以根據該模型計算待修復區域的像素值。通過具體的實驗，充分驗證了本文方法效果顯著，即修復的視覺效果好，運行效率高。決定實驗效果有多個因素，一個因素是極值差的選擇問題，根據實驗效果一般選擇在30~50；另一個因素是極值窗口尺寸的選擇，本文分別用窗口尺寸3和5分別進行試驗，窗口尺寸大的運行時間較長，但準確度較高。從運行時間上看，時間的長短與破損點的總數有關。以后將進一步探索影響運行效率的內在因素，及其之間的關系，以進一步提高運行時間。

參考文獻：

［1］BERTALMIO M， SAPIRO G， CASELLES V， et al. Image inpainting[C]//The ACM SIGGRAPH Conference on Computer Graphics.New Orleans:ACM Press， 2000:417－424.

[2］BERTALMIO M， BERTOZZI A L， SAPIRO G. NavierStokes， FluidDynamics， and Image and Video Inpainting[C]//Proc of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Los Alamitos:IEEE Computer Society Press， 2001:355－362.

[3］CHAN T， SHEN J. Mathematical models for local deterministic inpaintings [R]. UCLA CAM Report. 11， 2000.

[4］CHAN T， SHEN J. Nontexture inpainting by curvaturedriven diffusions [R]. UCLA CAM Report. 35， 2000.

[5］SHIH T K， CHANG Rongchi， LU Liangchen， et al. Adaptive digital image inpainting[C]//Proc of the 18th International Conference on Advanced Information Networking and Applications.Washington，DC:IEEE Computer Society， 2004:71－76.

[6］MUMFORD D， SHAH J. Optional approximations by piecewise smooth functions and associated variational problems [J]. Communications on Pure and Applied Mathematics， 1989，42:577－685.

[7］ADLATEINSSON D， SETHIAN J A. A fast level set method for propa￣gation interfaces [J]. Jour Comp Phys， 1995，118:269－277.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”