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

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

責(zé)任編輯:時 雯

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

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

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

1 Criminisi算法

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

圖1 Crinimisi算法說明圖

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

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

對于常用的灰度圖像，初始化時

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

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

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

2 算法改進(jìn)

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

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

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

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

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

2.2 Ψp大小的確定

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結(jié)果及結(jié)論

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

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

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