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

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

關(guān)鍵詞： 圖像修補(bǔ)； 中值濾波； 擴(kuò)散； 快速推移法

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：A

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

0引言

圖像修復(fù)技術(shù)是當(dāng)前圖像處理中的一個(gè)研究熱點(diǎn)，在文物保護(hù)、有目的性的圖像擦除等方面有著重要的應(yīng)用價(jià)值。手工圖像修復(fù)始于人們修復(fù)一些古老的藝術(shù)作品。隨著年代的久遠(yuǎn)，很多藝術(shù)作品不可避免地出現(xiàn)不同程度的損壞，人們通過(guò)對(duì)原作品的理解，試圖恢復(fù)出作品本來(lái)的面目，但實(shí)踐中很多人帶著個(gè)人感情色彩去修復(fù)，在修復(fù)歷程中曾出現(xiàn)了很多無(wú)法挽回的悲劇。數(shù)字圖像修復(fù)技術(shù)正是以實(shí)際應(yīng)用為出發(fā)點(diǎn)應(yīng)運(yùn)而生的，以一定的模型為基礎(chǔ)，以自動(dòng)修復(fù)破損區(qū)域?yàn)檫^(guò)程，以盡可能使圖像整體協(xié)調(diào)統(tǒng)一、滿足視覺(jué)效果為目的，實(shí)現(xiàn)數(shù)字圖像的修復(fù)。目前一些圖像處理軟件帶有圖像修復(fù)功能，但仍不可避免大量地手工操作，使得圖像修復(fù)耗時(shí)費(fèi)力。

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

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

1理論介紹

1．1中值濾波修復(fù)法

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

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

1．2平均曲率擴(kuò)散（CDD）修復(fù)法

該模型是由Chan等人提出的。它結(jié)合了圖像本身的幾何信息（即曲率），建立一種基于偏微分方程的圖像修復(fù)模型，一般用于非紋理圖像的修復(fù)。值得指出的是TV圖像修復(fù)模型[3]，因?yàn)镃DD修復(fù)模型是在TV的方法上產(chǎn)生的，但TV模型在現(xiàn)實(shí)應(yīng)用中破壞了視覺(jué)的連續(xù)性原則，在恢復(fù)細(xì)小物體邊緣上仍具有局限性。在該模型中，擴(kuò)散的強(qiáng)度與圖像的對(duì)比度和等值線強(qiáng)度有關(guān)，而與曲率無(wú)關(guān)。圖1是用TV方法修復(fù)的一個(gè)例子。

中值修復(fù)后剩余的未知像素點(diǎn)將采用CDD方法修復(fù)。可以看到，用中值方法得到的像素值僅需一次計(jì)算即可得到，而由曲率擴(kuò)散計(jì)算的像素要通過(guò)多次迭代才得到。

1．3快速推移法FMM

除了偏微分方程逐步迭代的修復(fù)方法與圖像修復(fù)的順序無(wú)關(guān)之外，其他圖像修復(fù)方法大都與修復(fù)的順序相關(guān)。通常修復(fù)的順序是按圖像掃描的順序從上到下、從左到右進(jìn)行圖像修復(fù)。當(dāng)破損區(qū)域較大時(shí)，按這種修復(fù)順序得到的修復(fù)效果不好。因?yàn)閷?duì)于大面積連續(xù)的破損區(qū)域，若破損區(qū)域左邊或上邊的修復(fù)結(jié)果誤差較大，其向后傳播的誤差則大。為此，本文采用快速推移法（fast marching method，F(xiàn)MM）[7]。該方法可以一定程度地減少向后傳播的誤差。

通過(guò)式（6）得到邊緣經(jīng)過(guò)各點(diǎn)的時(shí)間T。具體實(shí)現(xiàn)見(jiàn)文獻(xiàn)[7]。根據(jù)邊緣經(jīng)過(guò)各個(gè)點(diǎn)的時(shí)間先后次序，來(lái)確定修復(fù)的順序。用圖3容易解釋快速推移法在本文中的應(yīng)用：空心點(diǎn)屬于未知區(qū)域，灰色區(qū)域?yàn)檫吔鐓^(qū)域，黑色點(diǎn)屬于已接受區(qū)域。現(xiàn)在由已知區(qū)域經(jīng)過(guò)邊界區(qū)域向未知區(qū)域擴(kuò)散，從邊界區(qū)域中選取出一網(wǎng)格點(diǎn)，邊緣經(jīng)過(guò)它的時(shí)間最小，并標(biāo)記此點(diǎn)為已接受點(diǎn)，更新它的四鄰域中的未接受點(diǎn)的時(shí)間信息，直到所有點(diǎn)均被接受為止。可見(jiàn)邊界區(qū)域是一個(gè)有限寬度邊界帶。每次只前進(jìn)一個(gè)單位F=1。詳細(xì)介紹見(jiàn)參考文獻(xiàn)[7]。

2算法實(shí)現(xiàn)

本實(shí)驗(yàn)圖片均用24位RGB彩色圖像，分三個(gè)通道分別處理。其步驟如下：

b)對(duì)a）中的T由小到大排列破損點(diǎn)，并保存對(duì)應(yīng)的像素坐標(biāo)信息于堆heap中。

c)重新設(shè)置已知區(qū)域的點(diǎn)為可用標(biāo)志(available)，破損區(qū)域的點(diǎn)置為不可用標(biāo)志(unavailable)。

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

3實(shí)驗(yàn)結(jié)果

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［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.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”