代仕梅，張紅英，曾 超

（西南科技大學(xué) 信息工程學(xué)院，四川 綿陽(yáng) 621010）

0 引言

數(shù)字圖像修復(fù)是對(duì)圖像中遺失或者損壞的部分，利用未被損壞的圖像信息，按照一定規(guī)則填補(bǔ)，使修復(fù)后的圖像接近或達(dá)到原來(lái)的視覺(jué)效果。圖像修復(fù)技術(shù)在文化藝術(shù)、視頻和多媒體[1-2]、機(jī)器視覺(jué)、生物醫(yī)學(xué)、航天和航空技術(shù)、通信工程等方面都有很高的應(yīng)用價(jià)值。

在小尺度缺損的數(shù)字圖像修復(fù)中，偏微分方程方法得到了廣泛的應(yīng)用。Bertalmio，Sapiro，Caselles和Bellester首先將偏微分方程（Partial Differential Equation，PDE）引入圖像修復(fù)鄰域[3]，他們利用待修補(bǔ)區(qū)域的邊緣信息，并采用傳播機(jī)制將有用的邊緣信息沿著等照度線(xiàn)方向自動(dòng)向內(nèi)擴(kuò)散修復(fù)圖像。隨后Tony Chan等人將全變分（Total Variation，TV）模型[4]推廣到圖像修補(bǔ)，其通過(guò)運(yùn)用拉格朗日（Lagrange）乘子法將有約束條件的極值問(wèn)題轉(zhuǎn)化為無(wú)約束條件的極值問(wèn)題。該模型在修復(fù)中可以保持尖銳的邊緣并且數(shù)值實(shí)現(xiàn)簡(jiǎn)單，但其主要缺點(diǎn)是不能滿(mǎn)足視覺(jué)理論中的連通原理。因此，Chan和Shen根據(jù)連通性原理對(duì)TV模型進(jìn)行改進(jìn)，提出新的擴(kuò)散模型——曲率驅(qū)動(dòng)擴(kuò)散（CDD）模型[5]。

盡管基于PDE的圖像修復(fù)方法能夠有條不紊地保持圖像邊緣，但是該類(lèi)方法需要大量復(fù)雜的迭代，實(shí)現(xiàn)困難。當(dāng)前，已有許多學(xué)者對(duì)簡(jiǎn)單快速的鄰域?yàn)V波圖像修復(fù)作了研究：Oliveria等人提出了一種快速圖像修復(fù)算法[6]，利用高斯卷積核對(duì)圖像進(jìn)行濾波；Shih等人提出一種自適應(yīng)窗口均值濾波圖像修復(fù)算法[7]，利用窗口中有效像素的平均值代替待修復(fù)點(diǎn)的像素值；秦川等人改進(jìn)了文獻(xiàn)[7]算法，提出一種自適應(yīng)偏心窗口平滑濾波圖像修復(fù)方法[8]，在窗口尺寸自適應(yīng)算法的基礎(chǔ)上增加了對(duì)窗口中心位置的自適應(yīng)調(diào)整。筆者在這些方法的基礎(chǔ)上，提出一種改進(jìn)的鄰域?yàn)V波圖像修復(fù)算法，對(duì)于給定的一幅破損圖像，通過(guò)計(jì)算窗口中待修復(fù)點(diǎn)與其鄰域中已知點(diǎn)的距離大小賦予相應(yīng)的權(quán)值，即離破損點(diǎn)越近的點(diǎn)，權(quán)值越大，離破損點(diǎn)越遠(yuǎn)的點(diǎn)，權(quán)值越??；然后僅利用該點(diǎn)鄰域的有效信息加權(quán)求和來(lái)估算。大量實(shí)驗(yàn)表明該算法可以有效地減少平滑處理中的模糊，而達(dá)到很好的視覺(jué)效果。

1 Oliveria算法

Oliveria等人的快速圖像修復(fù)算法的主要思想是：1）通過(guò)清空待修補(bǔ)區(qū)域Ω的顏色信息來(lái)對(duì)其進(jìn)行初始化；2）利用3×3高斯卷積核對(duì)待修復(fù)區(qū)域進(jìn)行反復(fù)卷積，將已知信息不斷向修補(bǔ)區(qū)域內(nèi)部進(jìn)行擴(kuò)散，達(dá)到修復(fù)目的。圖1顯示了快速圖像修復(fù)算法偽代碼以及2個(gè)擴(kuò)散核。

2 自適應(yīng)的圖像修復(fù)算法

文獻(xiàn)[7]提出一種自適應(yīng)的圖像修復(fù)算法，其主要思想是：1）初始化待修復(fù)點(diǎn)為中心的窗口尺寸（如3×3）；2）計(jì)算窗口中信息未丟失點(diǎn)所占窗口總像素的比例；3）如果計(jì)算出的比例大于等于已給閾值，用此窗口有效像素的平均值代替中心點(diǎn)的值；否則增大窗口尺寸，然后回到第2步；4）如果窗口達(dá)到最大尺寸，停止窗口尺寸增加，直接用最大窗口有效平均值代替中心點(diǎn)的值。

秦川等人對(duì)文獻(xiàn)[7]進(jìn)行改進(jìn)，提出一種自適應(yīng)偏心窗口平滑濾波圖像修復(fù)方法。他們通過(guò)判斷待修復(fù)點(diǎn)p的鄰域灰度起伏廣義標(biāo)準(zhǔn)差Vp與閾值的關(guān)系，定位p點(diǎn)的歸屬區(qū)域。如果p屬于平滑區(qū)域，用文獻(xiàn)[7]的方法；如果p屬于邊緣區(qū)域，遍歷包含p的窗口，并計(jì)算每個(gè)窗口的距離Td，然后搜索出最小距離。若最小距離Td小于預(yù)定的閾值，記下窗口尺寸，用最小距離的窗口均值來(lái)修復(fù)p；如Td大于閾值則增大窗口尺寸，并繼續(xù)上述步驟。遍歷所有損壞像素執(zhí)行上述操作步驟，完成整個(gè)修復(fù)過(guò)程。

3 改進(jìn)的鄰域?yàn)V波圖像修復(fù)

經(jīng)反復(fù)試驗(yàn)發(fā)現(xiàn)，Oliveria算法與目前常用的基于偏微分方程的方法和基于紋理合成的方法相比，更易于實(shí)現(xiàn)，并且時(shí)間加快了2～3個(gè)數(shù)量級(jí)。但該算法僅考慮破損區(qū)域邊緣一周的顏色值，使得其僅適用于破損區(qū)域?yàn)?～3個(gè)像素寬度的情形。

文獻(xiàn)[7]可以自適應(yīng)地改變窗口大小，破損區(qū)域外更多的信息可以利用，但是破損點(diǎn)的值也只是窗口內(nèi)已知信息的簡(jiǎn)單平均，也即是窗口中每一個(gè)已知信息點(diǎn)的重要性均等，這樣不能保持邊緣特性。秦川等人在文獻(xiàn)[7]的基礎(chǔ)上，加入方差的計(jì)算來(lái)判斷破損點(diǎn)的歸屬區(qū)域，然后對(duì)屬于邊緣區(qū)的點(diǎn)采用變動(dòng)中心的窗口修復(fù)。此方法在修復(fù)過(guò)程中，對(duì)破損的每一個(gè)點(diǎn)都要計(jì)算方差使得收斂減緩；在邊緣區(qū)域點(diǎn)的修復(fù)中要找到合適的偏心窗口，既要反復(fù)調(diào)整幾個(gè)靈敏的參數(shù)，還要花費(fèi)大量的時(shí)間去搜索滿(mǎn)足條件的偏心窗口，參數(shù)的調(diào)整使得算法很難達(dá)到最佳的視覺(jué)效果，偏心窗口的搜索增加了大量運(yùn)行時(shí)間。

通過(guò)分析發(fā)現(xiàn)，自適應(yīng)的窗口大小和加權(quán)平均的鄰域?yàn)V波圖像修復(fù)可以很好地改善以上不足，同時(shí)不增加算法復(fù)雜度。算法要點(diǎn)是以待修復(fù)點(diǎn)為中心選取一個(gè)滿(mǎn)足條件的窗口尺寸，計(jì)算待修復(fù)點(diǎn)與其鄰域中已知信息點(diǎn)之間的歐氏距離來(lái)改變已知點(diǎn)的相應(yīng)權(quán)值，然后用鄰域像素的加權(quán)平均來(lái)估算待修復(fù)點(diǎn)的值。算法的實(shí)現(xiàn)細(xì)節(jié)：

1）采用文獻(xiàn)[7]的方法自適應(yīng)地改變窗口尺寸。以待修復(fù)的點(diǎn)p為中心，取一個(gè)大小為N×N（N為奇數(shù)）的窗口，初始化為3×3，接著計(jì)算窗口內(nèi)完好像素所占的百分比ηg。

2）預(yù)先給定的閾值為P0，如果ηg≥P0，則p點(diǎn)的估計(jì)值I（p）等于其鄰域內(nèi)已知信息的加權(quán)平均值，即

式中：Ne是窗口中已知信息點(diǎn)的集合；W（p，q）為q點(diǎn)的權(quán)函數(shù)。權(quán)函數(shù)的計(jì)算是本算法的關(guān)鍵，它主要依賴(lài)于已知點(diǎn)與破損點(diǎn)之間的歐幾里德距離，并滿(mǎn)足條件0≤W（p，q）≤1和ΣW（p，q）=1。假設(shè)破損點(diǎn)p坐標(biāo)為（x0，y0），窗口中的某一已知點(diǎn)q坐標(biāo)為（x1，y1），p（x0，y0）與q（x1，y1）之間的歐幾里德距離為

則點(diǎn) q（x1，y1）的權(quán)值為

其中，z（p）是歸一化因子

函數(shù)C（q）初始化為：C（q）=0，q屬于破損點(diǎn)；C（q）=1，q屬于已知點(diǎn)。Ne是窗口中已知信息點(diǎn)的集合，dist（p，q）是前面計(jì)算的距離，|Ne|是窗口中已知像素點(diǎn)的總數(shù)目，h是指數(shù)函數(shù)的衰減因子，調(diào)節(jié)dist(p,q)/|Ne|對(duì)權(quán)函數(shù)的影響。從式（3）可知，這種權(quán)值計(jì)算方法使得權(quán)值在窗口中已知點(diǎn)處有正值，破損點(diǎn)為零，并且權(quán)值的大小隨著已知點(diǎn)與破損點(diǎn)p的距離增大而減小，也即是在與中心點(diǎn)正交的方向的點(diǎn)具有較大的權(quán)值，在于中心對(duì)角線(xiàn)上的點(diǎn)由于離中心有更大的距離，所以，它的重要性要比與中心直接相鄰的像素低，這樣的安排權(quán)值與直接平均值相比，減小了濾波處理中的模糊。

3）如果ηg＜P0，將窗口的上、下、左、右4個(gè)邊分別向外移動(dòng)1個(gè)像素，然后繼續(xù)執(zhí)行前面的步驟；如果窗口達(dá)到給定的最大值還不滿(mǎn)足條件，記下最大窗口尺寸，然后計(jì)算其對(duì)應(yīng)權(quán)值，用最大窗口的有效值加權(quán)平均代替破損像素值。

4 實(shí)驗(yàn)結(jié)果與分析

所有實(shí)驗(yàn)均在配置為2.1 GHz處理器、2 Gbyte內(nèi)存的計(jì)算機(jī)上，采用Matlab7.0實(shí)現(xiàn)了本文的算法。其中，實(shí)驗(yàn)中所有圖像均由互聯(lián)網(wǎng)獲得。為了與其他的圖像修復(fù)算法進(jìn)行比較，同時(shí)也實(shí)現(xiàn)了文獻(xiàn)[6-8]的算法。試驗(yàn)中，幾個(gè)自適應(yīng)的算法的初始窗口大小都設(shè)置為3×3，然后根據(jù)圖像破損區(qū)域自身的特點(diǎn)設(shè)置窗口的最大值。通過(guò)反復(fù)試驗(yàn)發(fā)現(xiàn)，這樣選著掩膜窗口大小的原因是Oliveira采用固定3×3大小的尺寸，破損點(diǎn)周?chē)梢岳玫囊阎畔⒕褪瞧茡p點(diǎn)8鄰域的信息，在這8個(gè)點(diǎn)中可能還有破損的信息，那么可以利用的信息量就很少；而后面3種自適應(yīng)的窗口可以利用更多的已知信息；但是不是窗口越大越好，隨著窗口的增大，采用濾波的方法會(huì)使得修復(fù)的圖像模糊。

圖2a是一幅帶有破損的圖像，圖2b～2e是采用不同方法對(duì)破損背景以及頭發(fā)的修復(fù)，通過(guò)對(duì)比頭發(fā)的局部放大圖像，得出以下結(jié)論：采用本文方法能夠恢復(fù)頭發(fā)的細(xì)節(jié)，而其他方法則在頭發(fā)與背景的交界地方把背景顏色引入頭發(fā)中，使得頭發(fā)的恢復(fù)很不自然，有人工痕跡現(xiàn)象。

圖2 破損圖像修復(fù)結(jié)果與局部放大比較

圖3a為一幅劃痕圖像，Oliveira方法在處理人物帽子上劃痕時(shí)，因劃痕較寬，可以利用有效消息較少，因此產(chǎn)生了較大的誤差（圖3b）；文獻(xiàn)[7]處理結(jié)果圖中，帽子的邊緣產(chǎn)生輕微的模糊（圖3c）；文獻(xiàn)[8]處理后，因均方誤差誤判斷破損點(diǎn)是屬于平滑區(qū)域還是邊沿區(qū)域，導(dǎo)致信息傳遞失誤（圖3d）；而本文修復(fù)圖中每一處劃痕處理的效果都很好，邊緣保持良好（圖3e）。

圖3 劃痕圖像修復(fù)結(jié)果與局部放大比較

圖4a是一幅帶有文本的圖像，圖4b～4e是采用不同的方法對(duì)文本移除圖像進(jìn)行修復(fù)的結(jié)果，其中第2行是單詞“me”所在區(qū)域的放大圖。從局部放大圖中可以輕易發(fā)現(xiàn)，前3種方法修復(fù)后的圖像都留有字母的印記，而本文方法幾乎沒(méi)有文本剔出的人工痕跡。

圖4 文本移除圖像修復(fù)結(jié)果與局部放大比較

下面采用客觀指標(biāo)，如歸一化均方誤差（NMSE），對(duì)修復(fù)質(zhì)量進(jìn)行客觀評(píng)價(jià)

式中：I0為用于評(píng)價(jià)修復(fù)結(jié)果的完好圖像；I為修復(fù)后的圖像；M和N為圖像I0和I的大小。該公式只能用于灰度圖像修復(fù)后質(zhì)量的評(píng)價(jià)，本文對(duì)彩色圖像的3個(gè)通道分別進(jìn)行誤差分析。由于未獲得圖2的原始未破損的圖像，本文只對(duì)圖3和圖4進(jìn)行客觀評(píng)價(jià)。其中，R，G，B 3個(gè)通道的NMSE誤差數(shù)據(jù)如表1所示，從表1每通道誤差知道本文的方法誤差最小，修復(fù)效果最好。

通過(guò)實(shí)驗(yàn)，從主觀視覺(jué)效果來(lái)看，本文方法能夠較好地連接圖像中的斷裂邊緣，恢復(fù)細(xì)小結(jié)構(gòu)；從客觀描述來(lái)看，本文方法對(duì)圖像缺損區(qū)域重建的歸一化均方誤差較小。

表1 修復(fù)后圖像R，G，B 3個(gè)通道的歸一化均方誤差

5 結(jié)論

筆者針對(duì)圖像上小區(qū)域的信息丟失或破損缺修復(fù)問(wèn)題，提出一種簡(jiǎn)單高效的處理算法。該算法既不像基于偏微分方程的方法反復(fù)地進(jìn)行復(fù)雜的數(shù)學(xué)迭代，也不像基于紋理合成的方法做大量的搜索匹配；只需在局部窗口內(nèi)簡(jiǎn)單計(jì)算破損點(diǎn)與已知信息點(diǎn)的歐歐幾里德距離，然后根據(jù)距離來(lái)調(diào)控已知點(diǎn)的相應(yīng)權(quán)值，因此運(yùn)算時(shí)間仍然保持了快速圖像修復(fù)的特點(diǎn)。從修復(fù)效果上看，該算法對(duì)文字、劃痕、破損的修復(fù)都有很好的效果。不足之處在于鄰域?yàn)V波會(huì)使突出的邊緣結(jié)構(gòu)平滑，產(chǎn)生輕微的模糊；對(duì)較大的破損區(qū)域中心部分的修復(fù)無(wú)能為力，這將在以后的工作中繼續(xù)研究完善。

[1]張利平，張紅英，吳斌.基于多種邊緣檢測(cè)的視頻劃痕檢測(cè)技術(shù)[J].電視技術(shù)，2010，34（1）：85-87.

[2]韓軍，閔有剛，宋海華，等.視頻圖像修復(fù)算法的研究[J].電視技術(shù)，2007，31（7）：72-74.

[3]BERTALMIO M，SAPIRO G，CASELLES V，et al.Image inpainting[C]//Proc.the ACM SIGGRAPH Conference on Computer Graphic 2000.[S.I]：ACM Press，2000：417-424.

[4]CHAN T F，SHEN J H.Mathematical models for local non-texture inpainting[J].SlAM J.Appl.Math.，2001，62（3）：1019-1043.

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

[6]OLIVEIRA M M，BOWEN B，MCKENNA R，et al.Fast digital image inpainting[C]//Proc.the International Conference on Visualization，Imaging and Image Processing（VIIP2001）.Marbella，Spain：[s.n.]，2001：261-266.

[7]SHIH T K.Adaptive digital image inpainting[C]//Proc.the 18th ntemational Conference on Advanced Information Networking and Applications.Fukuoka，Japan：[s.n.]，2004：71-76.

[8]秦川，黃素娟，王朔中.自適應(yīng)偏心窗口平滑濾波圖像修復(fù)[J].計(jì)算機(jī)工程，2008，34（5）：213-215.