基于冗余字典學習的圖像修補算法

王鑫，朱行成，寧晨，王慧斌

1.河海大學計算機與信息學院，南京211100

2.南京師范大學物理科學與技術學院，南京210000

基于冗余字典學習的圖像修補算法

王鑫1，朱行成1，寧晨2，王慧斌1

1.河海大學計算機與信息學院，南京211100

2.南京師范大學物理科學與技術學院，南京210000

1 引言

數字圖像采集、傳輸、壓縮、存儲或編輯修改過程中，有時會造成圖像像素信息的丟失，影響圖像的視覺效果。如何對缺失部分進行修補，改善圖像的質量，直接影響到后續的應用。因此，設計有效的圖像修補算法以提高受損圖像的質量，具有非常重要的現實意義和應用價值[1]。

圖像修補技術是利用已知的信息推測并恢復丟失的信息，經過多年的研究發展，已經涌現出多種算法。這些算法歸納起來可以分為兩種類型：基于偏微分方程和變分算法理論的方法、基于樣本紋理合成技術的方法。其中，第一類方法的修補思路是從圖像中已知的區域擴展到未知區域，即圖像中缺失的部分。例如，Takeda等人[2]提出Steering核回歸（Kernel Regression，KR）模型，通過各向異性距離自適應調節權值，建立了非局部均值方法和核回歸模型之間的聯系，在圖像復原問題中取得了良好的應用效果。Chan和Shen[3]提出了一個基于全變分模型（Total Variation，TV）的圖像缺失信息修補方法，該算法在修補過程中會選擇最近的直線距離來連接斷裂的線性結構物體，因此無法滿足視覺連通性原則，修補效果不是很好。為此，Chan和Shen[4]隨后又提出了利用基于曲率擴散的非線性偏微分方程修補模型來解決這個問題?？紤]到圖像信號具有非局部自相似性，Peyré等人[5]在非局部圖上擴展全變分模型，進一步有效解決了圖像修補這一典型的逆問題。基于偏微分方程和變分算法理論的圖像修補方法在處理較小的缺失區域時，可以很好地恢復結構層信息，比如邊緣部分；但是在處理較大區域時效果不是很好，容易引入模糊和平滑效應。第二類基于樣本紋理合成技術的圖像修補方法，其思想是從待修補區域邊緣開始分割圖像小塊，從缺失圖像的已知部分尋找與待處理的圖像小塊最匹配的圖像塊，利用對應位置上的元素來進行圖像修補。例如，Efros和Leung[6]提出通過從缺失圖像的剩余區域中尋找最匹配的圖像塊來合成缺失區域的紋理層信息。但需要注意的是，自然圖像除了具有紋理層之外，還具有結構層信息，僅修補圖像的紋理層并不能取得很好的修補效果。為此，Criminisi等人[7]針對圖像修補問題在紋理合成的同時考慮了結構信息的傳播，利用合成紋理時的優先順序來保持結構信息的修補，提升了修補的性能。Chen等人[8]分別針對圖像缺失位置的結構信息和紋理信息進行圖像修補，其首先基于草圖模型重構缺失圖像的結構信息，然后利用基于圖像塊的紋理合成方法去合成圖像中缺失的區域?；跇颖炯y理合成技術的圖像修補方法可以處理大塊的缺失區域，更好地恢復待修補區域的紋理信息，但是該類修補算法具有貪婪性，在處理過程中可能會引入不相關的物體。

近年來，稀疏表示（Sparse Representation，SR）作為一種新興的圖像表示模型，能夠利用很少量的稀疏捕獲到圖像的主要信息和內在幾何結構，并且對噪聲與誤差更加魯棒，在圖像超分辨率重建、壓縮感知成像、圖像分割、圖像復原等問題中取得了良好的效果[9-11]。針對圖像修補問題，由于圖像在退化過程中丟失了信息，圖像修補逆問題通常具有病態特性。圖像的先驗模型在圖像修補問題中起著重要作用。利用基于圖像稀疏性的正則化模型可以對真實解空間進行正則化約束，從而將具有不適定性的圖像修補病態問題轉換為適定問題，獲得符合人眼視覺特性的穩定解。為此，本文在稀疏表示理論研究的基礎上，提出了基于不同冗余字典的圖像修補算法。該方法首先設計采用離散余弦變換（Discrete Cosine Transform，DCT）[12]或K-奇異值分解（K-Singular Value Decomposition，K-SVD）算法[13]獲得冗余DCT字典、KSVDG全局字典及KSVDA自適應字典等三種不同的字典；然后分別基于上述三種不同的冗余字典，稀疏表示待處理圖像；最終圖像中缺損的部分將通過冗余字典和稀疏系數有效地表示出來。實驗結果表明，提出的算法能夠得到良好的圖像修補結果。

2 圖像修補問題描述

圖像修補是圖像恢復研究中的一個重要方向，它的目的是根據圖像中殘留的信息，恢復圖像中缺失的部分，以達到更好的視覺效果，這個過程可以形象地用圖1表示。圖中，E表示圖像中殘缺的部分，即待修補的部分，Ec為圖像中已知的部分，修補問題即描述為如何通過Ec恢復出E。

圖1 圖像修補問題描述

上述圖像退化過程還可以表示為如下數學問題[14]：

其中，x表示原始的清晰圖像，y表示有部分內容缺失的待修補圖像，η是指圖像退化過程中可能引入的噪聲（一般認為是加性高斯噪聲）。H是圖像缺失問題中的退化算子，當H為只包含0和1兩種元素的掩碼時，其可以將圖像中部分位置的像素值置0，造成圖像內容缺失的效果。圖像修補的目的就是從缺失的圖像y中恢復出原始的清晰圖像x。

3 提出的算法

3.1 算法整體框架

信號的稀疏表示理論發展至今，在圖像處理領域眾多問題，如圖像壓縮、圖像去噪中得到了廣泛的應用，并為圖像復原問題的研究打開了新的方向。但是，目前如何將稀疏表示理論在圖像修補問題中得以有效地應用仍然是需要進一步研究的內容?；诖?，本文提出了基于不同冗余字典學習的圖像修補算法，其采用離散余弦變換或K-SVD方法學習了三種不同類型的冗余字典，即：DCT字典（記為DCT）、全局字典（記為KSVDG）及自適應字典（記為KSVDA）；然后分別基于這三種字典，對待修補圖像進行稀疏表示；最終原始圖像中缺損的部分就可以由這些冗余字典和計算得到的稀疏編碼系數表示出來。圖2給出了提出算法的整體結構圖。

3.2 算法具體步驟

提出算法的具體步驟如下：

（1）給定原始待修補圖像y∈?N，如圖3所示（這里給出了兩個退化圖像例子）。首先對其進行可重疊分塊處理，每一個圖像塊可以表示為其中表示從待處理圖像中選取圖像塊的矩陣算子。

圖2 提出算法的結構圖

圖3 原始待修補圖像示例

（2）當采用稀疏表示理論進行圖像修補時，假設冗余字典D已知，結合退化模型（1），則圖像修補問題可以表示為：

（3）訓練冗余字典D∈?B×K，其中K是字典中原子的個數，即字典的列數，K＞B，保證冗余。為了得到適用于圖像修補問題的冗余字典，分別采用離散余弦變換方法計算得到結構穩定的DCT字典、K-SVD方法訓練得到KSVDG全局字典和KSVDA自適應字典。其中，全局訓練字典是指從大量清晰的自然圖像塊中訓練得到的，而自適應字典是從待處理的圖像中獲得圖像塊，作為訓練樣本集獲得的冗余字典。

利用K-SVD的方法訓練冗余字典的詳細訓練過程如下：首先，給定一組訓練圖像塊S=[]s1,s2,…,sJ，其中J代表訓練圖像塊的個數，字典學習和稀疏系數的聯合優化問題可以表示為：

圖4給出了不同冗余字典的示例圖。其中，圖4（a）是經過離散余弦變換得到DCT字典，圖4（b）是從一組大量的清晰自然圖像中訓練得到的KSVDG全局字典，其中圖中每一個小塊表示一個原子?？梢钥闯鯠CT字典和KSVDG全局字典在結構上有很大不同，KSVDG全局字典中的原子會包含有更多的圖像結構信息。圖4（c）是從被文字污染的圖3（a）中利用K-SVD方法學習得到的KSVDA自適應字典，圖4（d）是從被文字污染的圖3（b）中利用K-SVD方法學習得到的KSVDA自適應字典，比較這兩幅圖像可以看出，兩個KSVDA自適應字典結構上也存在不同，這說明自適應字典對待處理圖像具有適應性，即待處理圖像在其相應的自適應字典上會有更稀疏的表示，從而得到更好的處理結果。

圖4 不同冗余字典示例

（4）訓練得到冗余字典后，采用OMP算法計算每個圖像小塊yk在冗余字典D上的稀疏系數α?k，則恢復后的每一個圖像塊x?k可以表示為：

（5）依次重建所有的圖像塊，則恢復后的完整的圖像x就可以表示為：

通過式（5），即可將恢復后的圖像塊放置在原來的位置上，而對于圖像塊間相互重疊的部分取平均處理，這樣可以有效減少圖像塊在各重疊區域的誤差，獲得更好的修補結果。

本文提出的上述修補方法主要利用了自然圖像的稀疏性，該特性指明圖像信號可以由冗余字典中少量原子的線性組合準確表示出來，也就是說字典中的原子結構中包含有自然圖像恢復的關鍵信息，所以利用冗余字典中少量原子的線性組合稀疏的表示待處理圖像信號，則圖像中缺失的部分就可以由冗余字典和更新得到的稀疏系數表示出來，實現圖像修補。

4 實驗和分析

在本實驗中，選取的測試圖片大小為256×256，對待修補圖像進行重疊分塊處理，每一小塊的大小為8×8，獲取圖像塊時的步長為1，則共處理的圖像小塊數為62 001。

字典D大小設置為64×256，保證冗余，根據字典的不同，本文基于稀疏表示模型的圖像修補算法分為三種情況，分別是基于結構固定的DCT字典、訓練得到的全局字典和自適應字典。全局訓練字典由K-SVD算法訓練得到，迭代了180次，在每次的迭代中，采用OMP算法求解稀疏系數，系數的稀疏度設置為6。訓練了超過100 000幅8×8的圖像小塊，該圖像塊都是從清晰的自然圖像中獲得。而自適應字典則是從缺失的圖像中訓練得到，具有自適應性，采用K-SVD方法訓練，迭代10次獲得。下面將給出分別基于上述三種不同的冗余字典得到的圖像修補結果。

4.1 評價標準

在給出實驗結果和分析之前，首先選擇兩種典型的全參考圖像質量評價方法，即峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）[18]和特征相似性方法（Feature Similarity，FSIM）[19]，用于后續定量衡量修補后圖像的質量。這里，所謂全參考圖像質量評價方法，是指已知原始的清晰圖像，通過把處理后的圖像和原始的清晰圖像作比較來評價圖像質量，可見，這是一類切實有效的評價標準。

峰值信噪比的定義如下：

其中，MSE為圖像灰度值的均方誤差，M和N分別代表圖像的長和寬，和分別代表參考圖像（原始清晰圖像）和失真圖像在位置處的灰度值。n是圖像的深度，本文中測試的圖像深度均為8。峰值信噪比被用來評價信號失真率，通常來說，該值越大，則代表圖像失真越小。

從峰值信噪比的計算公式可以看出，峰值信噪比只是計算了圖像間灰度值的差異水平，并沒有考慮圖像塊間的結構相似性。為此，下面又采用了特征相似性方法來評價圖像恢復后的質量，該標準利用了梯度信息和相位一致性信息兩個特征，相位一致性用于體現局部結構信息重要性，而圖像梯度用于衡量圖像對比度，該標準從多角度來評價復原后的圖像，也更加客觀和準確。要計算特征相似度，首先要求解各像素點的相位一致性和梯度值。設和分別是原始圖像和復原后圖像中某像素點的相位一致性的值和梯度值。首先求得下面兩部分：

其中，T1和T2為常量。則原始圖像和復原后圖像的相似性記為：

其中，α和β為常數，通常設置為1。要說明的是，圖像上任意像素點的顯著性是不同的，如果原始圖像和復原后圖像上相同位置的像素點的相位一致性的值都比較大，則說明該位置更容易引起人們的興趣。所以這里采用來調節相似性SL()x在該評價標準中的重要性。最終，圖像的特征相似度定義為：

其中，Ω代表整幅圖像范圍。

上述給出的是求解灰度圖像的特征相似度值，但是在實際情況下，經常處理的是彩色圖像，所以下面給出彩色圖像的特征相似度性值（FSIM）的求解方法。在彩色圖像的特征相似性求解公式里，增加了彩色圖像的色度信息，首先將原始圖像從RGB空間轉換到YIQ空間，其中I和Q代表圖像的色度信息，Y則代表圖像的亮度信息，記和分別是原始圖像和復原后圖像的色度信息，則原圖和復原后圖像色度間的相似度可表示為：

其中，T3和T4是調節因子，為了計算簡單，這里設置兩者的值相等?？梢酝ㄟ^和得到圖像的色度信息SC()

x，如下所示：

這樣，彩色圖像FSIM的求解可以定義為：

其中，λ為公式中的調節因子，可以調節色度信息在彩色空間所占的比值。由于彩色圖像的FSIM加入了圖像的色度信息，所以該評價標準更為可靠，效果也更好。本節實驗中采用的就是求解彩色圖像的FSIM值。一般來說，該值越接近1，代表圖像的主觀質量越好。

4.2 結果和分析

為了證明提出的基于不同冗余字典的圖像修補算法的修補效果，這里將提出算法和現有的兩種代表性算法進行了比較。第一種比較算法是傳統的基于全變分模型的修補方法（記為TV算法）[3]，第二種比較算法是經典的基于核回歸（Kernel Regression，KR）的修補方法（記為KR算法）[2]。圖5～圖9分別給出了三種不同的算法在5幅被文字污染的景物圖像的去字效果。在每一幅圖中，（a）表示原始清晰圖像，（b）表示被文字污染的退化圖像，（c）是TV算法修補后的結果，（d）是KR算法修補后的結果，（e）～（g）是提出的基于不同冗余字典（即DCT、KSVDG、KSVDA）的稀疏表示算法修補后的結果，這些算法分別記為SR-DCT算法、SR-KSVDG算法和SR-KSVDA算法。

圖5 圖像修補效果對比示例一

圖6 圖像修補效果對比示例二

對比最終定性實驗結果可以看出，TV算法、KR算法，及本文設計的基于不同冗余字典的圖像修補算法都可以有效消除加在原始圖像上的英文或中文字符，對圖像整體進行修復。但是，本文的算法視覺效果更好。例如，比較圖6中（c）、（d）和（e）～（g）可以看出，（c）圖和（d）圖中湖邊的臺階處可以看到英文字符并沒有去除干凈，而經過本文提出的算法處理后得到的圖（e）～（g）看起來更接近原始圖像。

圖7 圖像修補效果對比示例三

圖8 圖像修補效果對比示例四

圖9 圖像修補效果對比示例五

下面用峰值信噪比PSNR和特征相似度FSIM兩個標準來定量評價修補后圖像的質量，結果如表1所示。每一組實驗中最高的峰值信噪比和特征相似度值均用粗體表示?？梢钥闯?，表中后三列的值都高于第二列和第三列的值，說明本章提出的基于不同冗余字典的修補算法比全變分修補算法或核回歸修補算法的效果要更好，修補后的圖像具有更高的峰值信噪比和特征相似度值，表明修補后的圖像失真更小，局部結構信息也更豐富，有更好的視覺效果。后三列是基于不同冗余字典的稀疏表示算法的修補結果，比較后三列的值可以看到，基于自適應字典的稀疏表示算法（SR-KSVDA）在多數實驗圖像上取得了較好的結果，這是因為KSVDA自適應字典是從待處理的圖像中訓練得到的，可以獲得更好的稀疏性，所以相對于DCT和KSVDG字典，會有更好的處理結果。

表1 不同算法修補后的圖像PSNR/FSIM結果

5 結束語

本文提出了基于不同冗余字典的圖像修補方法。該方法首先利用離散余弦變換獲得冗余DCT字典，或利用K-SVD方法訓練獲得KSVDG全局字典及KSVDA自適應字典；然后基于上述三種不同的冗余字典分別稀疏表示待處理圖像；最終圖像中缺損的部分就可以由冗余字典和更新得到的稀疏系數表示出來。實驗將提出的基于不同冗余字典的圖像修補方法與經典的基于全變分模型的圖像修補算法、基于核回歸的圖像修補算法進行了比較，結果證明了提出方法的有效性。

[1] 宋錦萍，鄭昌燕.高階模型的快速圖像修補[J].計算機工程與應用，2015，51（11）：154-157.

[2] Takeda H，Farsiu S，Milanfar P.Kernel regression for image processing and reconstruction[J].IEEE Transactions on Image Processing，2007，16（2）：349-366.

[3] Chan T，Shen J.Local inpainting models and TV inpainting[J].SIAM Journal on Applied Mathematics，2010，62（3）：1019-1043.

[4] Chan T，Shen J.Nontexture inpainting by curvature-driven diffusions[J].Journal of Visual Communication&Image Representation，2001，12（4）：436-449.

[5] Peyré G，Bougleux S，Cohen L.Non-local regularization of inverse problems[C]//Proceedings of European Conference on Computer Vision，Marseille，France，2008：57-68.

[6] Efros A A，Leung T K.Texture synthesis by non-parametric sampling[C]//Proceedings of IEEE International Conference on Computer Vision，Washington，DC，USA，1999：1033-1038.

[7] Criminisi A，Pérez P，Toyama K.Object removal by exemplar-based inpainting[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition，Madison，Wisconsin，USA，2003：721-728.

[8] Chen Y，Luan Q，Li H，et al.Sketch-guided texture-based image inpainting[C]//Proceedings of IEEE International Conference on Image Processing，Atlanta，GA，USA，2006：1997-2000.

[9] Wang X，Shen S，Ning C，et al.Multi-class remote sensing object recognition based on discriminative sparse representation[J].Applied Optics，2016，55（6）：1381-1394.

[10] 費博雯，邵良杉，劉萬軍.基于子區域匹配的稀疏表示跟蹤算法[J].計算機工程與應用，2017，53（9）：201-207.

[11] Wang X，Shen S，Ning C，et al.A sparse representationbased method for infrared dim target detection under sea-sky background[J].Infrared Physics&Technology，2015，71：347-355.

[12] Liu Y，Yang Z，Yang L.Online signature verification based on DCT and sparse representation[J].IEEE Transactions on Cybernetics，2015，45（11）：2498-2511.

[13] Jiang Z，Zhe L，Davis L.Label consistent K-SVD：Learning a discriminative dictionary for recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35（11）：2651-2664.

[14] Zhang J，Zhao D，Gao W.Group-based sparse representation for image restoration[J].IEEE Transactions on Image Processing，2014，23（8）：3336-3351.

[15] Mairal J，Bach F，Ponce J.Task-driven dictionary learning[J].IEEETransactionsonPatternAnalysisand Machine Intelligence，2012，34（4）：791-804.

[16] Isaac Y，Barthélemy Q，Atif J，et al.Multi-dimensional sparse structured signal approximation using split bregmaniterations[C]//ProceedingsofIEEEInternational Conference on Acoustics，Speech and Signal Processing，Vancouver，BC，Canada，2013：3826-3830.

[17] Kowalski M.Thresholding RULES and iterative shrinkage/thresholding algorithm：A convergence study[C]//Proceedings of IEEE International Conference on Image Processing，Paris，France，2015：4151-4155.

[18] 蔣剛毅，黃大江，王旭，等.圖像質量評價方法研究進展[J].電子與信息學報，2010，32（1）：219-226.

[19] Zhang L，Zhang L，Mou X，et al.FSIM：A feature similarity index for image quality assessment[J].IEEE Transactions on Image Processing，2011，20（8）：2378-2386.

WANG Xin,ZHU Hangcheng,NING Chen,et al.Image inpainting based on redundant dictionary learning.Computer Engineering andApplications,2018,54（6）：198-204.

WANG Xin1,ZHU Hangcheng1,NING Chen2,WANG Huibin1

1.College of Computer and Information,Hohai University,Nanjing 211100,China
2.School of Physics and Technology,Nanjing Normal University,Nanjing 210000,China

Based on the sparse representation theory,this paper proposes an image inpainting framework by using different redundant dictionaries.First of all,it utilizes the Discrete Cosine Transform（DCT）or K-Singular Value Decomposition（K-SVD）to learn three different dictionaries,i.e.,the redundant DCT dictionary,K-SVD global（KSVDG）dictionary and K-SVD Adaptive（KSVDA）dictionary.Then,the image to be inpainted is sparsely represented by using these three different redundant dictionaries,respectively.At last,based on the redundant dictionaries and sparse coefficients,the missing part of the image can be well expressed.Experimental results show that the proposed algorithm achieves good visual effects.Further,compared with several existing classical image inpainting methods,it produces superior results in terms of some main image quality evaluation indexes such as peak signal-to-noise ratio and feature similarity.

image inpainting;redundant dictionary;sparse representation

在稀疏表示理論研究的基礎上，提出了基于不同冗余字典的圖像修補算法。首先設計采用離散余弦變換或K-SVD算法獲得冗余DCT字典、KSVDG全局字典及KSVDA自適應字典等三種不同的字典；然后分別基于上述三種不同的冗余字典，稀疏表示待處理圖像；最終圖像中缺損的部分將通過冗余字典和稀疏系數有效地表示出來。實驗結果表明，提出的算法修補后的圖像視覺效果好，并在峰值信噪比、特征相似度等主要圖像質量評價指標上優于現有幾種經典的圖像修補方法。

圖像修補；冗余字典；稀疏表示

2017-07-10

2017-10-23

1002-8331（2018）06-0198-07

A

TP394.1

10.3778/j.issn.1002-8331.1707-0161

國家自然科學基金（No.61603124，No.61374019）；中央高?；究蒲袠I務費專項資金（No.2015B19014）；江蘇省“333高層次人才培養工程”；江蘇省“六大人才高峰”高層次人才項目（No.XYDXX-007）。

王鑫（1981—），女，博士，副教授，研究領域為圖像處理，模式識別，計算機視覺，E-mail：wang_xin@hhu.edu.cn；朱行成（1990—），男，碩士研究生，研究領域為圖像處理和分析；寧晨（1978—），男，博士研究生，講師，研究領域為壓縮感知理論和應用；王慧斌（1967—），男，博士，教授，研究領域為圖像處理、視覺計算。