基于結(jié)構(gòu)字典的圖像修復(fù)算法

劉春榮

(北京工業(yè)大學(xué)計算機學(xué)院，北京 100124)

0 引言

2003年，Elad等人最早提出了基于圖像簽名字典[1](Image-Signature-Dictionary，ISD)的稀疏冗余表示模型[2-3]。ISD字典又名結(jié)構(gòu)字典，與傳統(tǒng)的字典學(xué)習(xí)模型相比，這種新穎的字典結(jié)構(gòu)具有尺度靈活特性[4]、占用更少的內(nèi)存以及計算能力的需求更低等優(yōu)勢。

2011年，Julien Mairal等人在基于圖像簽名字典的基礎(chǔ)上又提出了基于縮略圖的稀疏表示模型[5]，結(jié)構(gòu)字典可以從縮略圖中獲得，該模型具有平移不變特性[6-7]、尺度靈活性、占用內(nèi)存少等優(yōu)點。目前，結(jié)構(gòu)字典已經(jīng)應(yīng)用在圖像處理和機器的很多領(lǐng)域，本文研究基于結(jié)構(gòu)字典的圖像修復(fù)算法。

圖像修復(fù)[8]是對圖像中破損區(qū)域進(jìn)行信息填充，從而減少圖像破損所帶來的信息損失。圖像修復(fù)的目的是采用最適合的方法將受損圖像修復(fù)到盡可能接近原始圖像的狀態(tài)。圖像修復(fù)的對象包括受污染的圖像、帶有文字的圖像、去除不想要的目標(biāo)等。

圖像修復(fù)技術(shù)主要包括3類:基于紋理的圖像修復(fù)技術(shù)[9-10]、基于偏微分方程(Partial Differential E-quation，PDE)[11-12]的圖像修復(fù)技術(shù)和基于稀疏表示的圖像修復(fù)技術(shù)[13]?；诩y理的圖像修復(fù)技術(shù)的主要方法以基于樣本的圖像修復(fù)技術(shù)為代表，該算法的核心思想是以未受損圖像為樣本，在其中尋找與丟失像素或丟失模塊最匹配的修復(fù)模型并對受損區(qū)域進(jìn)行填充，從而實現(xiàn)對圖像的修復(fù)?；谄⒎址匠痰膱D像修復(fù)技術(shù)的核心思想是利用待修復(fù)區(qū)域的邊緣信息從區(qū)域邊界向圖像內(nèi)部進(jìn)行各向異性擴(kuò)散，從而實現(xiàn)對圖像的修復(fù)。

基于紋理的圖像修復(fù)技術(shù)和基于偏微分方程的圖像修復(fù)技術(shù)存在的問題是需要依賴圖像的具體結(jié)構(gòu)來制定相應(yīng)的圖像修復(fù)算法，隨著稀疏表示理論的成熟，利用信號的稀疏性來對圖像進(jìn)行修復(fù)得到廣泛應(yīng)用。

基于稀疏表示的圖像修復(fù)方法的代表為Elad[13]等人提出的KSVD算法和局部MCA相結(jié)合的方法，可以實現(xiàn)對圖像的破損區(qū)域進(jìn)行修復(fù)，首先利用MCA將圖像分解成卡通和紋理部分，接著利用KSVD算法分別對卡通圖像和紋理圖像訓(xùn)練各自的字典，然后利用訓(xùn)練得到的字典對圖像進(jìn)行修復(fù)。該方法具有自適應(yīng)性并且修復(fù)效果好等優(yōu)點。

本文在基于稀疏表示的圖像修復(fù)技術(shù)的基礎(chǔ)上，提出基于結(jié)構(gòu)字典的圖像修復(fù)技術(shù)。

1 算法的提出

本文提出基于結(jié)構(gòu)字典的圖像修復(fù)算法，具體算法可以分為以下2個步驟:

1)首先從原始圖像中提取所有重疊塊并采用基于結(jié)構(gòu)字典圖像訓(xùn)練算法進(jìn)行字典訓(xùn)練。其中稀疏編碼階段采用LASSO算法，字典更新階段采用投影梯度下降算法。

2)字典訓(xùn)練完成后，針對去除丟失像素塊的圖像塊進(jìn)行稀疏編碼，采用基于誤差控制的OMP算法，最后通過把重構(gòu)的圖像塊加權(quán)平均后放在恢復(fù)圖像的對應(yīng)位置。

對于給定的信號X∈Rm×n，可以建立結(jié)構(gòu)字典學(xué)習(xí)算法:

其中字典 D∈Rm×p，D=[d1，…，dp]為 p 個字典原子的集合，稀疏表示系數(shù) A∈Rp×n，X=[x1，…，xn]為 n個訓(xùn)練信號的集合，xi，j指 X的第i行 j列的元素，X的F范數(shù)為n個稀疏表示系數(shù)的集合，另外定義向量x∈Rm上的lq范數(shù)為，xj指 x 的第 j個坐標(biāo)，q＞1。對于大小為的結(jié)構(gòu)字典，即向量形式 E∈RM，線性操作算子可以提取結(jié)構(gòu)字典中所有重疊的塊并把其重新排列成字典D的列，其中指字典D的原子個數(shù)。φ(E)可以看成從結(jié)構(gòu)字典E到傳統(tǒng)字典D的映射算子，引入lm(φ)可以實現(xiàn)φ(E)到D的快速投影，φ是可逆的，φ和φ*是一對逆操作。

對于式(1)的求解，根據(jù)結(jié)構(gòu)字典E到傳統(tǒng)字典D的映射，可以將其轉(zhuǎn)化為傳統(tǒng)字典的求解，即:

式(2)的求解包括字典更新和稀疏編碼2個階段。

2 算法的求解

2.1 結(jié)構(gòu)字典與傳統(tǒng)字典的映射

假定 Ri∈{0，1}m×M，可以從結(jié)構(gòu)字典 E 中提取第i圖像塊，R=[R1T，…，RpT]T，φ(E)=[R1E，…，RpE]表示摘要圖E到傳統(tǒng)字典D的映射算子，φ*(D)表示字典 D∈Rm×p到摘要圖 E∈RM的映射算子

因地制宜，宜林植樹，選擇當(dāng)?shù)剡m宜的樹種種植。從提高生態(tài)效應(yīng)、景觀效果、經(jīng)濟(jì)效益出發(fā)，成片造林力度明顯提高。造林建設(shè)以發(fā)展經(jīng)濟(jì)林、生態(tài)景觀林等林地為主。采用多樣化的以林養(yǎng)林方式，以發(fā)展苗木養(yǎng)林，經(jīng)濟(jì)果林養(yǎng)林，采取林苗結(jié)合、林禽結(jié)合、林果結(jié)合等方式提高林地產(chǎn)出和經(jīng)濟(jì)效益。

進(jìn)一步推導(dǎo)φ*(D)=(RTR)－1RTvec(D)，因此vec(φ(E))=RE，vec(lmφ)=lmR，vec(φ(φ*(D)))=R(RTR)－1RTvec(D)，根據(jù)上面的推導(dǎo)可以得到以下3個特性:

1)φ*是φ的逆變換:φ*?φ=Id;

2)φ*是φ?φ*在lmφ上的正交投影;

3)∏lmp=φ?φ*。

通過建立結(jié)構(gòu)字典E到傳統(tǒng)字典D的映射，可以將其轉(zhuǎn)化為傳統(tǒng)字典的求解。

2.2 稀疏編碼階段

固定字典D更新稀疏表示系數(shù)A。通過固定字典D，對于稀疏表示矩陣A的更新可以看成是解關(guān)于αi的n個獨立的優(yōu)化問題。對于每一個優(yōu)化問題又可以看成是解加權(quán)l(xiāng)1優(yōu)化問題。對矩陣A的列αi的更新，定義矩陣 Γ =diag[‖d1‖2，…，‖dp‖2]及D'=DΓ－1，如果 Γ 是非奇異的，則有，則有式(3)和式(4):

接下來證明式(3)和式(4)的等價轉(zhuǎn)換:

定義 D'=DΓ－1，α'=Γα，則有:

通過以上推導(dǎo)，可以將有約束的算法求解問題轉(zhuǎn)化為無約束的算法求解問題，從而可以采用常用的稀疏編碼算法求解?？梢允褂肔ASSO[14－15]算法進(jìn)行求解。

2.3 字典更新階段

對于字典的更新可以采用投影梯度下降算法[16]。通過固定稀疏表示系數(shù)A更新字典D，得到目標(biāo)函數(shù):

式(7)中A是固定的，αj是A的第j列。函數(shù)f關(guān)于D是可微的，因此可以很容易地計算得到梯度:

3 實驗結(jié)果與分析

實驗設(shè)置:如圖1所示，測試圖像為Lena圖像(128×128)和Peppers圖像(128×128)，選取步長ρ=0.28，塊的大小為10×10，結(jié)構(gòu)字典的尺寸為24×24，平衡參數(shù)λ=0.15，為了保證實驗的公平性，選擇KSVD算法的字典原子數(shù)為256，另外，稀疏度為3。種算法都能夠?qū)D像進(jìn)行同樣稀疏表示的情況下，結(jié)構(gòu)字典占用的內(nèi)存小，因此具有較低的空間復(fù)雜度。

圖1 測試圖像

圖2 KSVD算法對Peppers圖像修復(fù)結(jié)果

實驗過程與分析:分別測試Peppers圖像在像素缺失率為20%的情況下采用KSVD算法[3]和本文提出的算法對圖像進(jìn)行修復(fù)，如圖2和圖3，通過對實驗結(jié)果進(jìn)行分析，2者都能比較理想地對圖像進(jìn)行修復(fù)。仔細(xì)觀察圖像的細(xì)節(jié)，基于結(jié)構(gòu)字典的圖像修復(fù)存在修復(fù)不徹底的現(xiàn)象，但是該算法計算簡單，先是對圖像樣本訓(xùn)練得到字典然后對缺失的圖像進(jìn)行修復(fù)，對圖像修復(fù)的效率較高?；贙SVD算法對字典原子的更新是逐列進(jìn)行更新，基于結(jié)構(gòu)字典的圖像修復(fù)算法是基于整個字典進(jìn)行更新，更新速度較快，且2

圖3 結(jié)構(gòu)字典算法對Peppers圖像修復(fù)結(jié)果

4 結(jié)束語

本文在基于冗余字典的稀疏表示方法的基礎(chǔ)上，結(jié)合結(jié)構(gòu)字典的思想，圍繞基于結(jié)構(gòu)字典的稀疏表示方法展開研究并將其成功應(yīng)用于圖像修復(fù)任務(wù)中。結(jié)構(gòu)字典克服了傳統(tǒng)的字典原子之間結(jié)構(gòu)不相關(guān)性問題，充分利用了原子之間的結(jié)構(gòu)特性，而且結(jié)構(gòu)字典具有平移不變性、尺度靈活性、占用內(nèi)存少的特點。最后通過實驗證明基于結(jié)構(gòu)字典的稀疏表示算法能夠訓(xùn)練字典更緊致地對圖像進(jìn)行表示，尤其在空間復(fù)雜度方面具有較大的優(yōu)勢。未來進(jìn)一步的工作將主要著眼于基于結(jié)構(gòu)字典的圖像分解技術(shù)在圖像修復(fù)問題上的研究。

[1] Aharon M，Elad M.Sparse and redundant modeling of image content using an image-signature-dictionary[J].SIAM Journal on Imaging Sciences，2008，1(3):228-247.

[2] Aharon M，Elad M，Bruckstein A.K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing，2006，54(11):4311-4322.

[3] Elad M.Sparse and Redundant Representations:From The-ory to Applications in Signal and Image Processing[M].Springer，2010.

[4] Mairal J，Sapiro G，Elad M.Learning multiscale sparse representations for image and video restoration[J].SIAM Journal on Multiscale Modeling and Simulation，2008，7(1):214-241.

[5] Benoit L，Mairal J，Bach F，et al.Sparse image representation with epitomes[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.2011:2913-2920.

[6] Mailhe B，Lesage S，Gribonval R，et al.Shift-invariant dictionary learning for sparse representations:Extending KSVD[C]//Proceedings of the 16th European Signal Processing Conference.2008.

[7] Thiagarajan J J，Ramamurthy K N，Spanias A.Shift-invariant sparse representation of images using learned dictionaries[C]//Proceedings of the 2008 IEEE Workshop on Machine Learning for Signal Processing.2008:145-150.

[8] Bertalmio M，Sapiro G，Caselles V，et al.Image inpainting[C]//Proceedings of the 27th Annual Conference on Computer Graphics and Interactive Techniques.2000:417-424.

[9] Criminisi A，Perez P，Toyama K.Region filling and object removal by exemplar-based image inpainting[J].IEEE Transactions on Image Processing，2004，13(9):1200-1212.

[10] Criminisi A，Perez P，Toyama K.Object removal by exemplar-based inpainting[C]//Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.2003，2:721-728.

[11] Tschumperle D，Deriche R.Vector-valued image regularization with PDEs:A common framework for different applications[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(4):506-517.

[12] Aubert G，Kornprobst P.Mathematical Problems in Image Processing:Partial Differential Equations and the Calculus of Variations[M].Springer，2006.

[13] Elad M，Starck J L，Querre P，et al.Simultaneous cartoon and texture image inpainting using morphological component analysis(MCA)[J].Applied and Computational Harmonic Analysis，2005，19(3):340-358.

[14] Efron B，Hastie T，Johnstone I，et al.Least angle regression[J].The Annals of Statistics，2004，32(2):407-499.

[15] Tibshirani R.Regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society，Series B(Methodological)，1996，58(1):267-288.

[16] Nesterov Y.Gradient Methods for Minimizing Composite Objective Function[DB/OL].http://www.optimizationonline.org/DB_HTML/2007/09/1784.html，2007-09-20.

[17] Bertsekas D P.Nonlinear Programming(2nd Edition)[M].Athena Scientific，1999.