許文杰，張相芬，嚴(yán) 實(shí)

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院，上海200234)

責(zé)任編輯:時(shí) 雯

圖像修復(fù)是近幾年新興的一個(gè)研究領(lǐng)域，它廣泛應(yīng)用于古文字畫、舊照片的修復(fù)以及字幕和一些圖片中人物的去除。圖像修復(fù)的原理即是根據(jù)破損圖像周圍的已知信息，通過特定的算法使圖像按規(guī)則從已知區(qū)域向破損區(qū)域傳播，從而修復(fù)破損區(qū)域，并使修復(fù)后的圖像達(dá)到或接近原圖的效果。一般人為的修復(fù)需要花費(fèi)大量的時(shí)間和勞力，且修復(fù)效果較差。圖像修復(fù)技術(shù)使人們從繁瑣的圖像修復(fù)工作中解脫出來，并減少人為失誤，提高準(zhǔn)確度和可信度。由于圖像修復(fù)在理論和實(shí)際中都有著重要的意義，因此近年來受到國(guó)內(nèi)外的廣泛關(guān)注。

目前的數(shù)字圖像修復(fù)算法主要分為兩類，即針對(duì)紋理圖像和非紋理[1](即結(jié)構(gòu))圖像進(jìn)行研究，研究方法也大致被分成以下兩類，對(duì)于非紋理結(jié)構(gòu)的圖像主要采用變偏微分方程模型[2]，它包括變分模型和偏微分方程模型兩種。由Bertalmio[3]等人提出一種分解圖像修復(fù)的算法，主要思想是首先找到待修復(fù)區(qū)域，利用邊緣信息，獲得等照線度的方向，從而沿邊緣輪廓向邊界內(nèi)擴(kuò)散。該方法雖然考慮到了擴(kuò)散信息和擴(kuò)散方向，但是不穩(wěn)定，對(duì)損壞圖像的修復(fù)效果也不是很好，只適合于劃痕、污跡和文字等細(xì)窄的區(qū)域修復(fù)。而對(duì)于具有紋理結(jié)構(gòu)的圖像，需要通過特征匹配來進(jìn)行紋理合成[4]。還原方法有以下兩種，一種是將圖像中的結(jié)構(gòu)部分和紋理部分區(qū)分開，獨(dú)立進(jìn)行修復(fù)，這就是在分解圖像基礎(chǔ)上的修復(fù)技術(shù);另一種是尋找目標(biāo)區(qū)域的合成技術(shù)，通過選取以一個(gè)像素點(diǎn)為中心的區(qū)域塊，在待修復(fù)區(qū)域周圍尋找和它相近的目標(biāo)區(qū)域塊進(jìn)行修復(fù)。該算法運(yùn)行時(shí)間長(zhǎng)，修復(fù)效果不佳?；跇永耐教幚砑y理和結(jié)構(gòu)區(qū)域[5]，不需要分割圖像的方法是Criminisi等人在2003年提出的，即將待修復(fù)區(qū)域周圍的圖像作為樣本，從中提取特征并選取匹配的紋理[6]，將其合成到待修復(fù)區(qū)域內(nèi)，這種算法適用于較大區(qū)域的修復(fù)，取得了較好的修復(fù)效果，但是耗費(fèi)時(shí)間過長(zhǎng)，另外由于在計(jì)算的過程中，置信度會(huì)很快變?yōu)?，使修復(fù)順序變的不可靠。同時(shí)，尋找匹配塊是在整個(gè)圖像中進(jìn)行的，會(huì)花費(fèi)很長(zhǎng)的時(shí)間，因此在優(yōu)先權(quán)和相似度的計(jì)算中還存在一定不足。

本文是在Criminisi算法的基礎(chǔ)上對(duì)圖像修復(fù)算法進(jìn)行的改進(jìn)。為了使優(yōu)先權(quán)計(jì)算更加準(zhǔn)確，本文采用梯度數(shù)據(jù)項(xiàng)、置信度和顏色共同決定填充順序;同時(shí)為了達(dá)到更好的修復(fù)細(xì)節(jié)和邊緣信息，將通過方差和梯度共同決定模板窗口的大小，最后通過改變搜索的順序和閾值來減少修復(fù)時(shí)間，其中最優(yōu)匹配塊[7]由顏色和梯度共同決定相似性，使得修復(fù)后的圖像具有更好的視覺效果。通過實(shí)驗(yàn)，證實(shí)可以產(chǎn)生較好的實(shí)驗(yàn)效果。

1 Criminisi算法

在一幅待修復(fù)圖像中，有很多點(diǎn)需要修復(fù)，到底應(yīng)該先修復(fù)哪個(gè)區(qū)域，對(duì)整幅圖的修復(fù)效果非常重要，這樣修復(fù)的順序就變得很重要，它會(huì)影響到整幅圖的修復(fù)質(zhì)量。因此，本文首先要確定修復(fù)塊的先后順序。Criminisi算法說明見圖1。

圖1 Crinimisi算法說明圖

優(yōu)先權(quán)公式定義為

式中:C(p)和D(p)分別為數(shù)據(jù)項(xiàng)和置信度項(xiàng)，其中

對(duì)于常用的灰度圖像，初始化時(shí)

當(dāng)找到需要修復(fù)的塊，即以點(diǎn)p為中心的修復(fù)塊后，就需要尋找最佳的匹配塊，公式為

式中:d表示兩個(gè)區(qū)域塊之間的差距，以SSD公式計(jì)算區(qū)域塊內(nèi)存在像素之間顏色的差距，找到合適的匹配塊，然后將待修復(fù)區(qū)域塊中的值用找到的目標(biāo)區(qū)域塊的值替換。

當(dāng)匹配塊對(duì)待修復(fù)區(qū)域進(jìn)行替換后，按照式(5)來更新數(shù)據(jù)項(xiàng)和置信度項(xiàng)，如此循環(huán)計(jì)算，直到待修復(fù)塊完全被修復(fù)。

2 算法改進(jìn)

2.1 優(yōu)先權(quán)算法

在Criminisi等人的算法中P (p)=C(p)D(p)，直接用已知像素與Ψp中像素量的比值作為置信項(xiàng)C(p)，經(jīng)過分析置信度會(huì)很快降到接近于0，這時(shí)即使C(p)很大，兩者相乘的結(jié)果也為0，優(yōu)先順序會(huì)被打亂，從而影響待修復(fù)區(qū)域的修復(fù)效果。針對(duì)此問題在計(jì)算優(yōu)先級(jí)時(shí)，將它們分別乘以x1和x2的次方。若取x1=1，則x2=0，則優(yōu)先級(jí)定義中沒有考慮結(jié)構(gòu)部分D(p)的強(qiáng)弱;若取x1=x2=1，則為Criminisi的方法，還通過G(P)使置信項(xiàng)的比重變大。在G(p)中，D(p)越大，表示Ψp內(nèi)有關(guān)結(jié)構(gòu)的信息就越多。R(p)代表了待修復(fù)塊附近的RGB顏色的變化大小，R(p)的值越大，表明Ψp內(nèi)RGB顏色變化越明顯。因?yàn)樵陔x待修復(fù)區(qū)域遠(yuǎn)的地方，置信度會(huì)越來越小，因此在一定程序上置信度項(xiàng)會(huì)阻礙線性結(jié)構(gòu)的優(yōu)先修補(bǔ)，所以在新的方法中加大了G(p)的權(quán)重。

目標(biāo)區(qū)域的優(yōu)先級(jí)的公式為

式中:x1和x2為正有理數(shù);R(p)中σ代表Ψ(p)內(nèi)的均方差;u表示Ψ(p)內(nèi)均值。

在計(jì)算等照度線時(shí)需要用到目標(biāo)區(qū)域的鄰近像素值，而目標(biāo)區(qū)域的值需要填充，是未知的，因此結(jié)果會(huì)有所偏差，為了避免這種情況，需要對(duì)待修復(fù)區(qū)域進(jìn)行膨脹處理[8]。這樣所有需要用到的像素值都是是已知的，從而可以增加結(jié)果的可靠性。

2.2 Ψp大小的確定

模板窗口的大小會(huì)對(duì)圖像的修復(fù)結(jié)果有一定的影響。在高頻部分包含有很多的細(xì)節(jié)和邊緣，采用大的窗口模板，會(huì)丟失很多有用的信息。為了包含更多的細(xì)節(jié)和邊緣信息，應(yīng)當(dāng)選取小的窗口。同樣，在低頻部分因?yàn)閳D像的變化很小。如果采用小的窗口，會(huì)浪費(fèi)很多的時(shí)間。因此，Criminisi算法中選取的窗口模板大小相同是不合理的。

圖像大多會(huì)受到噪聲的影響，梯度對(duì)噪聲比較敏感，雖然會(huì)影響其準(zhǔn)確性，但是梯度可以間接反映圖像空間頻率的變化。同時(shí)方差對(duì)噪聲不敏感，還能體現(xiàn)圖像的局部差異性，因此本文利用方差和梯度函數(shù)共同來決定模板的大小。

本文算法先將待處理的圖片經(jīng)過歸一化處理后再計(jì)算待求點(diǎn)的方差值，然后與梯度函數(shù)進(jìn)行相加，采用梯度函數(shù)和方差來共同決定變?chǔ)穚窗口的大小。對(duì)于顏色變化比較大的區(qū)域采用小的修復(fù)塊，可以更好地保留其顏色信息，同時(shí)也更符合人眼的視覺效果，而對(duì)于顏色變化小的區(qū)域就采用大的修復(fù)塊，可以縮短修復(fù)的時(shí)間。這樣，待修復(fù)區(qū)域的大小就可以根據(jù)圖像紋理變化的方向性和顏色變化是否明顯來自動(dòng)調(diào)節(jié)大小。

本文選擇的窗口大小計(jì)算函數(shù)為

式中:size(p)表示模板的大小;var(p)表示點(diǎn)的方差值。

2.3 最佳目標(biāo)區(qū)域的選用

當(dāng)選取出優(yōu)先級(jí)最高的待修補(bǔ)區(qū)域后，就是要找到最合適的目標(biāo)塊對(duì)其進(jìn)行修補(bǔ)，本文根據(jù)顏色和梯度差異共同來計(jì)算目標(biāo)塊Ψp和樣本塊Ψq之間的距離為G(Ψp，Ψq)[9]，定義為

式中:d(Ψp，Ψq)為待修復(fù)塊與目標(biāo)區(qū)域的像素值差的平方;L(Ψp，Ψq)為梯度的差的平方和，公式為

在Criminisi算法中搜索最佳匹配塊的順序是從左到右、從上到下，依次搜索，這樣不僅需要的時(shí)間長(zhǎng)，而且效率很低。已知在一幅紋理圖像中，相鄰的像素間的變化很小，因此可以只選取待修復(fù)區(qū)域的周圍的點(diǎn)作為待匹配區(qū)域，在候選塊與待修復(fù)塊進(jìn)行SSD計(jì)算得出最優(yōu)匹配塊，可以節(jié)約時(shí)間。

文中采用搜索最近最優(yōu)匹配區(qū)域的搜索方法。根據(jù)前面計(jì)算優(yōu)先權(quán)得到的修復(fù)點(diǎn)p，確定待修復(fù)塊，然后根據(jù)p的棋盤距離為n(n=1，2，3，…)的各點(diǎn)作為q點(diǎn)，然后依次將以q點(diǎn)為中心的區(qū)域塊與待修復(fù)的區(qū)域Ψp做SSD計(jì)算。將計(jì)算得到的值依次與閾值進(jìn)行比較，當(dāng)計(jì)算值小于閾值時(shí)，將待選區(qū)域塊的值替換到待修復(fù)的區(qū)域;反之，如果計(jì)算值大于閾值時(shí)，將棋盤距離值加1，然后繼續(xù)按這個(gè)順序搜索，直到搜索到有計(jì)算值小于閾值，如果一直到搜索區(qū)域全部搜索完仍然沒有找到比閾值小的計(jì)算值，就在計(jì)算值中選取一個(gè)最小的計(jì)算值的待選區(qū)域去替換待修復(fù)區(qū)域。

如圖2所示，設(shè)p為待修復(fù)塊的邊緣上的點(diǎn)，從圖中可以看出與p棋盤距離為1的像素分別為q11，q12，…，q18，首先會(huì)對(duì)棋盤距離為1的值進(jìn)行搜索，如果沒有找到小于閾值的計(jì)算值，則對(duì)距離為2的像素q21，q22，q23，…，q216進(jìn)行搜索，一直重復(fù)下去，直到找到需要的區(qū)域塊。這樣得到的修復(fù)結(jié)果與其鄰域的相關(guān)性較大，也更加符合視覺上的效果。

圖2 區(qū)域塊中像素值的表示

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

實(shí)驗(yàn)結(jié)果見圖3～圖6。圖4中黑色部分為需要修復(fù)的部分，從圖中5和6可以看出，改進(jìn)的算法中由于可以調(diào)節(jié)窗口模板的大小，修復(fù)的速度會(huì)有所提高，同時(shí)修復(fù)效果較好。

圖3 原圖

圖4 需要修復(fù)的圖

圖5 Criminisi算法修復(fù)的圖

圖6本文算法修復(fù)的圖

圖7 為待修復(fù)的圖片，其中黑色為要修復(fù)的區(qū)域;圖8為用Criminisi算法修復(fù)的圖片。圖9為待修復(fù)區(qū)域進(jìn)行膨脹化處理后用Criminisi修復(fù)的圖;圖10為通過改進(jìn)后的算法修復(fù)的圖片。圖9中水中的圖的修復(fù)效果好些，圖10中不僅水中沒有多余的草，岸上的修復(fù)效果感覺也更貼近視覺效果。

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

實(shí)驗(yàn)結(jié)果顯示，經(jīng)過改進(jìn)后的方法具有更好的修復(fù)效果。首先，Criminisi算法的修復(fù)順序是根據(jù)同線性結(jié)構(gòu)的信息來決定的，對(duì)于一幅破損的圖像，這種順序有時(shí)并不是合理的，本文加入顏色信息，優(yōu)化了算法，實(shí)驗(yàn)結(jié)果表明對(duì)于紋理顏色的變化能進(jìn)行更好的修復(fù)，根據(jù)方差值與梯度來決定修復(fù)塊的大小，從圖4和圖5就可看出明顯的不同，修復(fù)效果更好，也更靈活。最后通過設(shè)定閾值來減少搜素的范圍和時(shí)間，不過當(dāng)閾值過小時(shí)修復(fù)效果會(huì)比較差，但可以節(jié)約時(shí)間。本文的缺點(diǎn)是算法過于復(fù)雜，特別是參數(shù)設(shè)置過多，對(duì)于部分圖片，不能快速選擇合適的參數(shù)。

[1]IDDO D，DANIEL C，HEZY Y，et al.Fragment based image completion[C]//Proc.ACM SIGGRAPH 2003.New York，USA:ACM Press，2003:303-312.

[2]SUN J，LU Y，JIA J，et al.Image completion with structure.propagation[C]//Proc.ACM SIGGRAPH 2005.Los Angels.USA:ACM Press，2005:961-969.

[3]BERTALMIO M，SAPIRO G，CASELLES V，et a1.Image inapaint inapainting[C]//Proc.the 27th Annum Conference on Computer Graphics and Interactive Techniques.New Or Ieans，USA:ACM Press，2000:417-424.

[4]BERTALMIO M，VESE L，SAPIRO G，et al.Simultaneous structure and texture image inpainting[J].IEEE Trans.Image Processing，2003，12(8):882-889.

[5]PENG H，HOU W，GONG N.Anim proved exemp larbased inpaint ingmethod for object removal[J].Journal of Computer-Aided Design& Computer Graphics，2006，18(9):1345-1349.

[6]張顯全，高志卉.一種塊匹配的圖像修復(fù)算法[J].光電子激光，2012(4):805-811.

[7]CRIMINISI A，PEREZ P，TOYAMA K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Trans.Image Processing，2004，13(9):1200-1212.

[8]王黎明.基于樣本塊的圖像修補(bǔ)方法研究[D].北京:首都師范大學(xué)，2008.

[9]代仕梅，張紅英，曾超.一種基于樣例的快速圖像修復(fù)算法[J].微型機(jī)與應(yīng)用，2010(8):34-36.