一種基于樣例的快速圖像修復(fù)算法*

代仕梅,張紅英,曾 超

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

圖像修復(fù)是圖像復(fù)原研究中的一個(gè)重要內(nèi)容，它的主要思想是:對(duì)圖像中遺失或者損壞的區(qū)域，利用未損壞的圖像信息，按照一定的規(guī)則進(jìn)行填充，并且盡可能地使修復(fù)后的圖像接近或達(dá)到原來(lái)的視覺(jué)效果。隨著近幾年數(shù)字技術(shù)的發(fā)展以及數(shù)碼產(chǎn)品的普及，這一技術(shù)除了應(yīng)用于破損照片的修復(fù)，還被用于文本提取、目標(biāo)移除、超分辨率、圖像壓縮/傳輸以及視頻錯(cuò)誤隱藏等方面。

目前，圖像修復(fù)中占主流的修復(fù)模型有：偏微分方程的修復(fù)模型[1-2]、紋理合成[3]的修復(fù)模型。 前者計(jì)算量大、耗時(shí)長(zhǎng)、對(duì)紋理的還原能力有限，處理大區(qū)域圖像會(huì)有明顯的模糊現(xiàn)象，因此只適合于劃痕、污跡和文字等細(xì)窄的區(qū)域修復(fù)。相比之下，后者將待修復(fù)區(qū)域周?chē)膱D像作為樣本,從中提取特征并選取匹配的紋理，將其合成到待修復(fù)區(qū)域內(nèi)，適用于較大區(qū)域的修復(fù)。

現(xiàn)實(shí)中的圖像不是由簡(jiǎn)單結(jié)構(gòu)和單一紋理拼接而成的，而是同時(shí)包含復(fù)雜的結(jié)構(gòu)和多種紋理特征。參考文獻(xiàn)[4]將圖像分割為結(jié)構(gòu)和紋理兩部分，然后分別用偏微分方法和紋理合成技術(shù)進(jìn)行處理，最后將兩種處理結(jié)果進(jìn)行融合。但對(duì)實(shí)際圖像而言，該方法修復(fù)區(qū)域較小，速度較慢，對(duì)較大區(qū)域修復(fù)仍然有一定的模糊。Criminisi等人在2003年提出了一種不用分割圖像，同步處理紋理和結(jié)構(gòu)的基于樣例的圖像修復(fù)算法[5]。他們的算法取得了滿(mǎn)意的效果，但是耗費(fèi)的時(shí)間過(guò)長(zhǎng)，另外優(yōu)先權(quán)和相似度的計(jì)算還存在一定不足。本文改進(jìn)了參考文獻(xiàn)[5]的圖像修補(bǔ)算法。為了使優(yōu)先權(quán)計(jì)算更加準(zhǔn)確，本文采用梯度數(shù)據(jù)項(xiàng)和置信度共同決定填充順序；為加快修復(fù)速度，本文采用局部窗口搜索的策略；最后利用顏色和梯度共同決定相似性，使得修復(fù)后的圖像具有更好的視覺(jué)效果。大量實(shí)驗(yàn)結(jié)果表明，該算法提高了修復(fù)效率，同時(shí)產(chǎn)生了更滿(mǎn)意的視覺(jué)效果。

1 算法的基本步驟

對(duì)于待修復(fù)圖像，手工選定待修補(bǔ)區(qū)域Ω，也稱(chēng)為目標(biāo)區(qū)。如圖1所示，Φ代表目標(biāo)區(qū)域以外的部分(Φ=I-Ω)，提供修復(fù)過(guò)程中的樣本資源，又稱(chēng)為樣本區(qū)。Ψ為模板窗口，也稱(chēng)為最小的填充單元 (略微大于樣本區(qū)的最大紋理元)。

算法描述如下：

(1)手工選定待修復(fù)區(qū)域或待移除的目標(biāo)區(qū)域Ω;

(2)初始化需要修復(fù)圖像的邊界?Ω0;

(3)while(提取修復(fù)邊界 ?Ωn且 Ωn≠Φ)

①優(yōu)先權(quán)的計(jì)算：目標(biāo)塊 Ψp的大小初始化為 9×9，根據(jù)不同圖像調(diào)整它的尺寸,計(jì)算目標(biāo)塊Ψp的優(yōu)先權(quán)P(p)，?p∈?Ωn；

②選出具有最大優(yōu)先權(quán)的塊，作為待匹配塊；

③在I-Ω區(qū)域內(nèi)，使用局部窗口搜索目標(biāo)塊Ψp的最近似的匹配塊Ψq。

④將Ψq的信息復(fù)制到Ψp需要修復(fù)的相應(yīng)位置；

⑤更新置信度 C(p)=C(p′)e-kd2,?p∈(Ψp∩Ω);

⑥重復(fù)①～⑤的過(guò)程，直到邊界為空。

2 算法的實(shí)現(xiàn)細(xì)節(jié)

2.1 模板大小的自適應(yīng)選擇

在反復(fù)的實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)，用固定大小的模板窗口Ψ，修復(fù)誤差比較大。對(duì)于包含豐富的細(xì)節(jié)及邊緣的區(qū)域，應(yīng)該采用小的模板窗口，以獲取較多的細(xì)節(jié)信息，減少畸變；對(duì)于平滑的紋理區(qū)域，由于樣本塊和目標(biāo)塊的相似距離非零，修復(fù)采用直接復(fù)制樣本，應(yīng)該采用較大的窗口，減少修復(fù)后的圖像產(chǎn)生明顯的假象。因此模板窗口的大小應(yīng)當(dāng)根據(jù)圖像的局部特征自適應(yīng)地變化。本文采用梯度函數(shù)自適應(yīng)地改變模板窗口大小。模板尺寸size(p)的定義為：

2.2 塊的優(yōu)先權(quán)

基于樣例的圖像修復(fù)算法，為了兼顧結(jié)構(gòu)和紋理部分的修復(fù)效果，填充順序是這類(lèi)方法的關(guān)鍵。填充順序的優(yōu)先權(quán)函數(shù)大小要考慮兩方面的因素:一方面是模板窗口中已知信息量的多少,另一方面要考慮待修復(fù)區(qū)域周?chē)慕Y(jié)構(gòu)特征。因?yàn)橐阎畔⒍嗟拇畛鋲K的周?chē)梢岳玫男畔⒋?，結(jié)構(gòu)特征明顯的區(qū)域包含了豐富的結(jié)構(gòu)信息。Criminisi定義的優(yōu)先權(quán)函數(shù)為：P(p)=C(p)×D(p)。當(dāng)?shù)日斩染€與單位法向量垂直時(shí)，D(p)=0，這時(shí)即使C(p)很大，甚至整個(gè)塊中只有幾個(gè)未知像素，塊也得不到及時(shí)填充。這樣優(yōu)先權(quán)的計(jì)算就變得不可靠，導(dǎo)致錯(cuò)誤的填充順序，進(jìn)而影響修復(fù)的效果。為了解決這個(gè)問(wèn)題，本文直接引入梯度信息來(lái)計(jì)算塊的優(yōu)先權(quán)。P為修復(fù)邊界?Ω上的點(diǎn)，Ψp是以點(diǎn) P為中心的塊，點(diǎn) P的優(yōu)先權(quán)函數(shù)P(p)定義為:

式中,C(p)為置信度項(xiàng)，G(p)為梯度數(shù)據(jù)項(xiàng)，分別定義為:

2.3 匹配塊的搜索空間

Criminisi等人采用在整幅未破損的圖像中全局搜索，這樣能夠找到與目標(biāo)區(qū)域塊最相似的匹配塊。但是許多圖像的匹配塊就在目標(biāo)區(qū)域的附近，因此全局搜索提供了巨大的搜索空間，降低了算法的效率。為了減少搜索過(guò)程的時(shí)間消耗，一些學(xué)者提出了紋理主方向的搜索方法[6]（水平、垂直等）。這種紋理主方向的搜索方法對(duì)于方向性很強(qiáng)的圖像能達(dá)到很滿(mǎn)意的效果，但是對(duì)于其他的圖像修復(fù)效果達(dá)不到滿(mǎn)意效果。為了既要減少搜索空間，又要達(dá)到滿(mǎn)意的修復(fù)效果，采用局部窗口空間搜索匹配塊。在Criminisi的算法中，設(shè)置的填充塊大小為 PatchSize，然后在整幅圖像的未破損區(qū)域搜索匹配塊。局部窗口尺寸設(shè)置如下:

其中，PatchSize仍然為填充塊的尺寸大小，StepLength為步長(zhǎng)，搜索空間以當(dāng)前具有最大優(yōu)先權(quán)的點(diǎn)為中心，分別向上、下、左、右延伸WindowLength這樣長(zhǎng)一段距離。因此實(shí)際搜索空間localspace為:

這一局部窗口搜索空間與全局搜索相比,窗口尺寸從 N×M(N、M 分別為圖像的行和列)減少到 n×m(n、m分別為局部窗口的行和列)。這一改進(jìn)減少了搜索時(shí)間，提高了圖像修復(fù)的效率。但是，當(dāng)有稀疏的邊緣和復(fù)雜的樣例的圖像在修復(fù)中，簡(jiǎn)單地縮小窗口尺寸來(lái)尋找最佳匹配塊會(huì)失敗。

2.4 塊的匹配準(zhǔn)則

選出具有最大優(yōu)先權(quán)的塊作為待匹配塊，然后根據(jù)顏色和梯度差異共同來(lái)計(jì)算目標(biāo)塊Ψp和樣本塊Ψq之間的相似度。相似度函數(shù) d(Ψp,Ψq)的定義為:

式中，M是目標(biāo)塊上的已知像素點(diǎn)的數(shù)目，CL(p)為顏色差的平方的和，W(p)為梯度的差的平方的和，分別定義為:

其中，R、G、B分別代表像素的紅、綠、藍(lán)分量值，G代表圖像的梯度值。通過(guò)反復(fù)實(shí)驗(yàn)發(fā)現(xiàn)，在匹配塊的匹配過(guò)程中，同時(shí)考慮顏色和梯度差異的相似度的計(jì)算，獲得的最佳匹配塊更能夠滿(mǎn)足人們的視覺(jué)效果。

2.5 置信度的更新

完成一次填充過(guò)程后，置信度需要更新。文中置信度的更新定義為:

式中，k是一個(gè)可調(diào)參數(shù)，d是前面提到的相似度函數(shù)。顯然，由這個(gè)方程可知相似度函數(shù)值越大，像素點(diǎn)誤差越大，置信度值越低。

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

將本文所提的算法應(yīng)用于許多的自然圖像,采用對(duì)比圖像的視覺(jué)效果來(lái)判斷修復(fù)質(zhì)量的好壞，用程序的運(yùn)行時(shí)間來(lái)衡量算法的效率。所有的實(shí)驗(yàn)是在配置為2.1 GHz處理器、2 GB內(nèi)存的計(jì)算機(jī)上運(yùn)行的，仿真環(huán)境為Matlab 7.0。本文用文本移除、單一目標(biāo)物移除和多目標(biāo)物移除，來(lái)說(shuō)明本文算法的優(yōu)越性。

3.1 文本移除

圖2為文本移除實(shí)驗(yàn)。其中，(a)為原始圖像，(b)為Criminisi算法，(c)為本文算法。從原始圖像中可以看出，圖中的文字“JAPANESE ANIMATION”只在圖片的下端，其文字移走后的空白區(qū)域，修補(bǔ)只需要搜索不到圖片一半的空間就可以找到最佳匹配塊；而Criminisi采取全局搜索，大量的時(shí)間浪費(fèi)在不必要的搜索中。對(duì)比發(fā)現(xiàn)，Criminisi所用的修復(fù)時(shí)間遠(yuǎn)遠(yuǎn)大于本文算法，而其修復(fù)效果略好于本文算法。

3.2 單一目標(biāo)物的移除

圖3為單一目標(biāo)物的移除。其中，(a)為原始圖像，(b)為Criminisi算法，(c)為本文算法。從 Criminisi算法可以看出，臺(tái)階恢復(fù)出現(xiàn)了明顯的不相容的“垃圾塊”，而且臺(tái)階下面的綠地延伸到黑色區(qū)域中；而本文算法很好地恢復(fù)了臺(tái)階的線性結(jié)構(gòu)，黑色區(qū)域內(nèi)也沒(méi)有綠地的延伸塊，幾乎看不出人工痕跡。

3.3 多目標(biāo)物的移除

圖4為多目標(biāo)物的移除實(shí)驗(yàn)。其中，圖4(a)為原始圖像，圖 4(b)為 Criminisi算法，圖4(c)為本文算法。從圖4中可以看出，移走多棵樹(shù)以后，本文算法修復(fù)的海平面非常自然，而Criminisi算法修復(fù)的海平面有輕微的人工痕跡。

表1給出了這三組實(shí)驗(yàn)的運(yùn)行時(shí)間。從表1可以看出，運(yùn)行時(shí)間與圖像本身大小、破損區(qū)域大小以及破損區(qū)域周?chē)慕Y(jié)構(gòu)復(fù)雜度都有一定關(guān)系。本文方法與參考文獻(xiàn)[5]所用方法相比，根據(jù)圖像自身特征局部搜索運(yùn)行時(shí)間更短，然而得出的效果差不多或者更好，說(shuō)明了本方法的高效優(yōu)質(zhì)性。

表1 參考文獻(xiàn)[5]算法與本文算法運(yùn)行時(shí)間比

圖像修復(fù)在圖像處理和計(jì)算機(jī)圖形學(xué)領(lǐng)域中有許多重要應(yīng)用。本文提出了一種能夠滿(mǎn)足破損圖片修復(fù)、文本移除、目標(biāo)物體去除等多類(lèi)修復(fù)要求的快速算法。本算法改進(jìn)了基于樣例的修復(fù)算法，為了正確地傳播信息，有效地利用梯度值來(lái)計(jì)算目標(biāo)塊的填充順序和匹配塊的相似度。因此該算法更有能力對(duì)細(xì)小結(jié)構(gòu)和復(fù)雜的紋理優(yōu)先傳播。

文中提出的方法不需要人為干預(yù)分割紋理和結(jié)構(gòu)信息，算法根據(jù)圖像的局部特征計(jì)算出優(yōu)先權(quán)，接著根據(jù)優(yōu)先權(quán)的大小先后填充。在匹配塊的搜索空間，采用局部窗口搜索，大大縮短了修復(fù)時(shí)間。然而，該算法仍然存在著一定局限性：首先，局部窗口不能完全找到最匹配的塊，如果沒(méi)有局部特性的圖像或者有明顯跳變結(jié)構(gòu)的圖像修復(fù)都會(huì)失?。黄浯?，圖像的破損區(qū)域周?chē)仨氂写罅康臉颖緣K，以滿(mǎn)足待修復(fù)區(qū)域內(nèi)的結(jié)構(gòu)和紋理傳播。所以，在今后的工作中，應(yīng)該對(duì)該算法的局限性進(jìn)行逐步改進(jìn)，擴(kuò)大它的應(yīng)用范圍，使其能夠應(yīng)用到視頻和網(wǎng)格的修復(fù)工作當(dāng)中。

[1]BERTALMIO M,SAPIRO G,CASELLES V,et al.Image inpainting[A].In:Proceedings of International Conference on Computer Graphics and Interactive Techniques[C].New Orleans,Louisiana,USA,2000:417-424.

[2]CHAN T,SHEN J.Mathematical models for local nontexture inpainting[J].SlAM Journal of Applied Mathematics,2001,62(3):1019-1043.

[3]EFROS A A,FREEMAN W T.Image quilting for texture synthesis and transfer[A].Computer Graphics Proceedings,Annual Conference Series,ACM SIGGRAPH[C].Los Angeles,2001:341-347.

[4]BCAALMIO M,VESE L,SAPIRO G,et a1.Simultaneous texture and structure image inpainting[J].IEEE Transactions on Image Processing,2003,12(8):882-889.

[5]CRIMINISI A,PEREZ P,TOYAMA K.Object removal by exemplar-based inpainting[A].in:Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition[C].Monona Terrace Convention Center Madison,Wisconsin,USA,2003,2:18-20.

[6]魏琳,陳秀宏.基于紋理方向的圖像修復(fù)算法[J].計(jì)算機(jī)應(yīng)用,2008,9(28):2315-2317.