基于結構相似度的圖像修補算法

摘 要： 提出了一種基于Criminisi算法的改進的圖像修補算法。引入了圖像質量評價標準SSIM定義的結構相似度，結合結構相似度進行圖像修補過程中的模板匹配，從而減少了模板匹配時錯誤匹配的情況，提高了圖像修補的質量。仿真結果顯示，改進的算法對于圖像修補有不錯的效果，優于原有的Criminisi修補算法。

關鍵詞： 圖像修補； 結構相似度； Criminisi算法； 模板匹配

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2015）10-07-03

Abstract： A new inpainting algorithm based on the Criminisi algorithm is proposed in this paper. The new algorithm combines with the structural similarity， which comes from image quality evaluation criteria SSIM， to carry out the template matching in the image inpainting process. The algorithm can reduce the probability of error matching and improve the quality of image inpainting. The simulation results show that the improved algorithm has a good effect on the image inpainting， and is superior to the original Criminisi algorithm.

Key words： image inpainting； structural similarity； Criminisi algorithm； template matching

0 引言

圖像修補是對圖像缺失區域或者被破壞的地方進行修復，在手工修復圖像時，容易破壞圖像且需要大量的時間[1]。計算機的出現使得數字圖像修補技術得到大幅發展。圖像修補技術的原理是通過圖像中無損的區域來達到修復圖像缺損區域的目的。圖像修補在很多領域得到應用，比如文物保護[2]、影視特技制作[3]、圖像中文本或多余目標物的去除[4]，視頻通信中的錯誤隱匿[5]。由于圖像修復在實際中都有著重要的意義，因此受到國內外的廣泛關注，現在已成為計算機視覺和圖形學研究中的熱點之一。

從Bertalmio等[6]首次提出，到目前出現了大量圖像修補方法。圖像修補技術分為兩類。

第一類是基于擴散的修補技術，通過引入偏微分方程來傳播局部的結構，使圖像的信息從已知區域向缺損區域擴散[6]。在Bertalmio[6]所提算法中通過沿著等照度線的方向來修復圖像。Chen[7]提出使用全變差模型（TV）修補破損區域。Zhang[8]使用調和函數改進了全變差模型，提高了圖像修補質量。此類方法在修補小區域破損圖像時有很好的效果，比如劃痕，圖像中文字去除等。但對于紋理比較豐富或者大區域破損圖像時效果非常差。

另一類方法是基于樣本的紋理合成方法，算法的思想是從待修補區域邊界上選取一個優先權最高像素點，以該點為中心，選擇一個大小合適的紋理塊，然后在已知區域內尋找最相近的匹配塊來代替紋理塊。Criminisi[9]開創性的提出了基于紋理的修補算法。然而在Criminisi算法中，修補過程對結構、噪聲等一些因素比較敏感，在計算優先權時會產生錯誤的判斷，并且在尋找匹配塊的過程中容易發生錯誤匹配，影響最終的修補質量。Wu[10]提出通過偏微分方程（PDE）計算優先權。Xu[11]通過結構的稀疏表示來計算優先權。Meur[12]引入結構張量計算優先權。Yin[13]在Criminisi[9]的基礎上利用曲率來搜索匹配塊。這一類方法對于大尺度破損區域和紋理復雜的圖像有良好的修補效果。

本文在Criminisi算法的基礎上進行改進，屬于第二類算法。在算法中，通過使用顏色信息和結構相似度的結合來提高尋找最佳匹配塊的準確程度，改善圖像的修補質量。

1 Crimicisi算法

在圖1中，假設Φ是已知區域，Ω是待修補區域，那Ω是待修補區域的邊界，Ψp是以Ω上一點p點為中心選取的一個模板，稱為待修補塊，比如選取大小為9*9的方塊，Ψq是以q點為中心選取的一個模板，大小與Ψp相同且模板位于已知區域Φ內。Criminisi算法是一種基于樣本的圖像修補算法，綜合結構傳輸和紋理合成的優點，對于圖像修補有較好的效果。Criminisi算法實現過程如下：

⑴ 在圖像中選擇需要修補的區域Ω，然后確定其邊界_Ω；

⑵ 計算邊界_Ω上所有的待修補塊優先權，選擇優先權最大的待修補塊修補；

⑶ 在已知區域Φ內搜索一個與待修補區域大小相同的塊，稱為匹配塊；

⑷ 將匹配塊對應于待修補塊中待修補區域的像素復制到待修補塊中；

⑸ 重新確定待修補區域的邊界，重復上述修補過程，直到待修補區域修補完成。

算法中有兩個關鍵步驟：優先權的計算和搜索匹配塊。對于任一邊界點p∈Ω，定義待修補塊Ψp的優先權P（p）為

其中C（p）為置信項，D（p）為數據項，|Ψp|代表Ψp的面積，即像素的總數，C（q）=0當q∈Ω，C（q）=1當q∈Φ，是p點的等照度線，np是p點的法向量，是歸一化因子，在灰度圖像中取255。

2 改進的圖像修補算法

2.1 結構信息相似度

在Z.Wang等[14]提出的SSIM中，圖像分為3部分：亮度信息、對比度信息，結構信息。

2.2 結構信息相似度

在Criminisi算法中搜索最佳匹配塊，是要根據待修補塊和匹配塊之間的顏色信息的差異大小衡量兩個塊的相近程度，本算法中在搜索時引入結構相似度，判斷兩個塊間的近似程度，d（Ψp，Φq）變為

算法的圖像修補過程如圖2所示。

2.3 細節實現

在算法仿真中，不同的處理方式會造成不一樣的結果。在改進的算法中，首先根據圖像需要確定一個二值圖，像素為1的表示待修補區域，像素為0表示已知區域，如圖4（c）所示。

確定優先權時，會遇到如圖3的情況，白色區域為待修補區域，假設A點的優先權最大，當選取9*9的方塊，方塊不完全在圖像內。此時將方塊移動，使得方塊位于圖像內。

計算兩個塊的結構相似度，是計算待修補塊中已知信息和匹配塊中對應于待修補塊已知區域的信息的結構相似程度。算法中，將待修補塊與對應的二值圖像塊相乘，使得待修補塊位于待修補區域的像素設置為0，將匹配快與待修補塊對應的二值圖像塊相乘，使匹配塊中對應于待修補塊中待修補區域的像素也設置為0，然后計算處理后的兩個塊之間的結構相似度。

3 實驗結果

通過MATLAB2010a進行算法仿真，實現過程中選取窗口大小為9*9，參數c為0.3。

圖4中是對bungee圖中目標物的移除，圖4（a）為原始圖像，圖4（b）中綠色的部分為需要移除的區域，圖4（c）是一個二值圖像，白色部分為原始圖像中需要移除目標物的區域。圖4（d）為bungee圖的修補結果，圖4（e）為Criminisi所提算法的仿真，圖4（f）為Wu所提算法的仿真，圖4（c）是本文改進的算法的仿真結果。由圖4可見，在圖4（a）和圖4（b）中用圓圈畫的部分都有很好的修補效果。

圖5是對baboon圖中的缺失區域進行修補，圖5（a）為原始圖像，圖5（b）中綠色的部分為圖像中缺失的部分，圖5（c）是一個二值圖像，白色部分為原始圖像中缺失的區域，圖5（d）為Criminisi所提算法的仿真，圖5（e）為Wu所提算法的仿真，圖5（f）是本文改進的算法的仿真結果。

4 算法優缺點分析

在算法中引進了結構相似度，通過參數的選擇，可以對不同圖像進行修復。從仿真結果來看，對結構或紋理復雜的破損圖像修補效果良好。但參數的選擇是由試驗得到的，對每幅圖像有一定的差別，因此，下一步的工作是對參數進行改進，做到自適應，提高算法的實用性。

參考文獻：

[1] 吳亞東，張紅英，吳斌.數字圖像修復技術[M].科學出版社，2010.

[2] W Huang， S Wang， X Yang and J Jia，Dunhuang murals inpainting based on image decomposition[J]. Journal of Shandong University （Engineering Sci-Ence），2010.40：24-27

[3] K. A. Patwardhan， G. Sapiro， and M. Bertalmio，Video inpainting of occluding and occluded objects[J].in Proc. IEEE Int. Conf，2005.2：69-72

[4] J. F.Wang， H. J. Hsu， and S. C. Liao，A novel framework for objectremoval from digital photogragh[J]. presented at the IEEE Conf. Image Processing，2005.

[5] Yongbing Zhang， Xinguang Xiang， Debin Zhao， Siwe Ma， Wen Gao.Packet Video Error Concealment With Auto Regressive Model[J].Circuits and Systems for Video Technology， IEEE Transactions on，2012.22（1）：12-27

[6] M. Bertalmio， G. Sapiro， C. Ballester， and V. Caselles，Imageinpainting[J]. in Proc. ACM SIGGRAPH，2000.7：417-424

[7] T. F. Chan and J. Shen，Mathematical models for local nontexture inpaintings[J]， SIAM J. Appl. Math，2001.62（3）：1019-1043

[8] H. Y. Zhang， B. Wu， Q. C. Peng， and Y. D.Wu，Digital imageinpainting based on p-harmonic energy minimization[J]. Chin. J. Electron，2007.3：525-530

[9] A. Criminisi， P. Pérez， and K. Toyama，Region filling and objectremoval by exemplar-based inpainting[J]. IEEE Trans. Image Process，2004.13（9）：1200-1212

[10] J. Wu and Q. Ruan，Object removal by cross isophotes exemplarbased image inpainting[J]. Proceeding of International Conference of Pattern Recognition，2006：810-813

[11] Z. Xu and J. Sun，Image inpainting by patch propagation usingpatch sparsity[J]. IEEE Trans. Image Process，2010.19（5）：1153-1165

[12] O. Le Meur， J. Gautier， and C. Guillemot，Examplar-based inpainting based on local geometry[J]. in Proc. IEEE Int. Conf. Image Processing （ICIP），2011.9：3401-3403

[13] Lixin Yin， Chen Chang，An effective exemplar-based image inpainting method[J]. 14th IEEE International Conference on Communication Technology （ICCT）， Chengdu， 2012.11：739-743

[14] Z. Wang， A. C. Bovik， and E. P. Sheikh， H. R. ans Simoncelli，Image quality assessment： From error measurement to structural similarity[J]. IEEE Trans. on Image Processing，2004.13（4）：600-612