基于顏色信息和閾值的圖像修復算法

許文杰，張相芬，嚴 實

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

責任編輯:時 雯

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

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

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

1 Criminisi算法

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

圖1 Crinimisi算法說明圖

優先權公式定義為

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

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

當找到需要修復的塊，即以點p為中心的修復塊后，就需要尋找最佳的匹配塊，公式為

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

當匹配塊對待修復區域進行替換后，按照式(5)來更新數據項和置信度項，如此循環計算，直到待修復塊完全被修復。

2 算法改進

2.1 優先權算法

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

目標區域的優先級的公式為

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

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

2.2 Ψp大小的確定

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

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

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

本文選擇的窗口大小計算函數為

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

2.3 最佳目標區域的選用

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

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

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

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

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

圖2 區域塊中像素值的表示

3 實驗結果及結論

實驗結果見圖3～圖6。圖4中黑色部分為需要修復的部分，從圖中5和6可以看出，改進的算法中由于可以調節窗口模板的大小，修復的速度會有所提高，同時修復效果較好。

圖3 原圖

圖4 需要修復的圖

圖5 Criminisi算法修復的圖

圖6本文算法修復的圖

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

4 實驗結果分析

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

[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]張顯全，高志卉.一種塊匹配的圖像修復算法[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].北京:首都師范大學，2008.

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