基于稀疏表示的圖像分類字典學習*

何小衛, 張 莉

(浙江師范大學 數理與信息工程學院,浙江 金華 321004)

?

基于稀疏表示的圖像分類字典學習*

何小衛, 張 莉

(浙江師范大學 數理與信息工程學院,浙江 金華 321004)

針對K-SVD算法學習得到的字典結構性不強的問題，利用圖像的非局部自相似性，提出了基于稀疏表示的圖像分類字典學習方法(NLC-DL).該方法利用K-means對圖像塊進行聚類并對每個子類進行字典學習，增強字典的有效性.根據正交匹配追蹤算法(OMP)求得稀疏系數，迭代優化字典，最終利用優化后字典和稀疏系數矩陣重構圖像.實驗結果表明：生成的學習字典對訓練樣本的表達誤差更小，能夠有效地保持圖像的結構信息，重構后的圖像在峰值信噪比和視覺效果方面均優于傳統方法.

非局部；自相似性；稀疏表示；字典學習;K-均值

0 引 言

圖像的稀疏表示是通過引入過完備冗余字典，實現對信號的最優逼近.基于圖像稀疏表示的過完備信號稀疏表示理論最早是由Mallat等[1]提出的，使用Gabor字典并引入匹配追蹤算法，通過逐步逼近的方法對信號進行稀疏表示.近年來，基于過完備冗余字典的信號稀疏表示被廣泛應用于圖像處理的各個領域：利用形狀自適應字典塊對三維醫學圖像進行去噪處理[2]；通過抑制噪聲的稀疏編碼進行圖像恢復[3]；基于位置分類選擇合適加權分解人臉詞典并進行稀疏編碼用于人臉識別[4]；利用稀疏表示進行目標檢測實現背景分離進而實現目標跟蹤[5]；基于壓縮感知構造超完備稀疏字典進行稀疏降維[6]；強調任務驅動字典學習算法以提高高光譜分類的效果[7].

文獻[8]提出K-SVD字典學習算法，將觀測圖像作為訓練原子庫進行字典學習，能夠較好地保護圖像的細節信息.但在初始字典選擇不當的情況下，由于字典某些列可能不被更新，降低了字典原子的有效利用率，可能導致算法陷入局部最小值，并且算法在處理高維數據及運算復雜度上都有一定的局限性[9].為解決這些問題，近年來，有學者在K-SVD算法的基礎上進行了一些改進.在降低字典大小的問題上，Mazhar等[10]提出了增強K-SVD算法(EK-SVD)，在不影響逼近精度的前提下，從大量的字典原子中逐步修剪掉類似的原子，進而產生一個較小尺寸的優化字典，從一定程度上降低了K-SVD算法運算的復雜度；在對選擇合適大小的字典問題上，文獻[11]進行了探索并提出子聚類K-SVD算法，采用子聚類的方法保留最重要的原子，同時去除多余原子，通過引入錯誤驅動機制完成字典的更新；在提高字典原子參與圖像重構的使用率問題上，Ribhu等[12]提出了稀疏貝葉斯學習方法，在K-SVD算法最初的幾次迭代過程中，使用稀疏貝葉斯學習方法進行稀疏編碼完成信號從非稀疏表示逐步收斂到稀疏表示，從而解決了字典原子的利用不足問題.

上述基于K-SVD的圖像處理方法在字典大小、字典原子利用率和算法時間復雜度方面進行了改善，但這并沒有有效解決K-SVD算法對初始字典的隨機選取問題.文獻[3]指出,用K-SVD方法得到的稀疏編碼系數并不是隨機分布的，它們之間存在高度的相關性，提出了非局部中心化稀疏表示模型，并取得了非常好的圖像恢復效果.考慮到各圖像塊之間可能存在的幾何結構相似性[13]，對需要處理的圖像塊進行聚類，再對聚類后的圖像塊進行字典學習.一方面，使得各個子字典更有針對性，每類子字典只恢復與之相對應的圖像塊信息，增強了字典學習的有效性；另一方面，聚類使得并行計算成為可能，加快了圖像處理速度.在過完備稀疏表示問題的求解方面，貪婪追蹤算法在求解優化問題時不需要考慮整體最優性，總在當前的最好結果的條件下做選擇.主要算法有：匹配追蹤(MP)算法[1]、正交匹配追蹤(OMP)算法[14]等.OMP算法是對MP算法的一種改進，在分解的每一步對所選擇的全部原子進行正交化處理，使得在精度要求相同的情況下，OMP算法的收斂速度更快.

利用圖像的非局部自相似性，本文提出了基于稀疏表示的圖像分類字典學習方法(NLC-DL)：用K-means方法對圖像塊進行聚類，利用主成分分析(PCA)具有很好方向性的特性,對子類圖像塊進行子字典學習；對于每一子類圖像，利用OMP算法得出對應稀疏系數，迭代計算所得圖像與原始圖像之間的差距，優化字典直至達到優化條件；并通過實驗方法完成算法的相關參數設定和字典類數選擇，利用優化字典和稀疏系數實現圖像重構.

1 基于稀疏表示的圖像分類字典學習模型

1.1 基于稀疏分解理論的圖像表示

稀疏分解是將信號或圖像在過完備的字典下分解，尋找最匹配的原子重構信號或圖像.圖像的稀疏表示理論研究主要分為稀疏分解重建算法和字典的設計，而字典的設計將直接影響到圖像是否能有效地進行稀疏表示.稀疏編碼是對訓練字典進行線性組合，從而最大限度地逼近給定數據集[15].

或者

式(1)和式(2)中，范數‖5‖0表示向量非零元素的個數.由于l0的最小化是NP-hard問題，所以在a足夠稀疏的條件下，可用l1范數對其進行凸放松[17].模型(1)等價于

1.2 圖像分類字典學習模型

由于自然圖像在結構上存在自相似性[19]，即圖像上很多信息是相似的、冗余的，并且它們不是局部分布的，可以在整個圖像的任意位置，所以不同圖像塊之間也會存在結構上的相似性.圖像塊之間的相似性可以通過它們的灰度值的歐式距離來度量，歐式距離越小，結構越相似.將圖像塊利用K-means聚類后的原始圖像可表述為：Y=[y1,y2,…,yk]，其中yi={y(1),y(2),…,y(j)}表示聚類后每一類數據，再對每一子類數據塊進行稀疏編碼和字典學習，以實現圖像恢復的目的.在式(3)的基礎上引入分類的思想，模型可表述為

利用圖像非局部自相似性對圖像進行聚類，最終獲得的子類字典之間可能包含有相似的原子信息，比如圖像的邊緣、輪廓、紋理等特征信息，都有可能出現在不同子類字典的原子信息中.因此，通過計算不同子類字典之間的相似度，把相似度較高的子字典合成一個特征字典，再用特征字典對相關圖像塊進行重構以實現對圖像特征信息的保護，可以進一步提高本文方法對圖像恢復的效果.

2 算法實現

利用圖像的非局部自相似性，充分考慮圖像塊間的相互聯系，對圖像塊進行結構聚類，并對聚類后的圖像塊做類內字典學習，有效地捕捉了圖像的內部結構特征，增強了字典的有效性，加快了收斂速度，從而更好地實現圖像的重構.具體的類字典學習過程如下:

NLC-DL算法

輸入：訓練樣本Y

1)利用K-means對訓練樣本進行聚類Y=[y1,y2,…,yk],yi={y(1),y(2),…,y(j)}.

①隨機選取k個聚類質心點π1,π2,…,πk；

2)利用PCA方法對每一類樣本進行降維處理，得出初始特征類字典Dk.

③對原圖像進行降維處理，得到Dk=(Y-υ)Ak.

3)利用OMP算法計算第i類樣本的稀疏系數ai.

4)通過以下步驟進行J次迭代：對于字典D中的每一列l=1,2,…,m，

①計算殘差El=yi-Diai；

②利用SVD算法分解得El=UΛVT；

④矩陣V的第1列乘以Λ(1,1)后所得的結果更新系數ai.

5)如果不能達到停止迭代的標準，那么返回第4步.

6)更新第i類圖像塊xi=Diai.

輸出：第i類數據對應的子字典Di及恢復圖像X.

算法的重點在于構造子類字典，以獲得對圖像信號更加準確的稀疏表示.首先，對圖像塊信息利用K-means方法，即通過計算它們的灰度值之間的歐式距離進行聚類，并對子類圖像塊利用PCA方法進行降維處理作為初始子類字典，可有效地避免傳統K-SVD算法對初始字典隨機選取不當情況下可能陷入局部最小值的問題.然后，采用OMP算法根據每一子類對應的PCA字典進行圖像信號的稀疏分解，分解過程的每一步均將圖像信號投影到特征子字典所構成的空間上，獲取信號的各個已選原子上的投影分量和殘余分量，再循環對殘差分量進行分解.在每次迭代時，在字典中選擇與殘余信號最相關的原子,再將信號殘余正交投影到所選的原子上;然后重新計算稀疏系數并更新信號殘余，重復計算直到信號殘余小于設定的閾值；最后，利用類特征字典Di獲得相應稀疏系數重構圖像X.

3 實驗結果與分析

3.1 分類子字典

為了驗證上述字典學習方法的有效性，使用一些經典的圖像作為實驗用例.以512×512像素的灰度圖像Lena為例，在加入σ=20的高斯噪聲之后，定義圖像塊大小為8×8像素，并按不同步長(step=1，2，4，6，8和10)，共生成424 204個圖像塊進行訓練，其中類數cls=15，迭代結束條件(即設定的誤差閾值)T=1.15σ，最大迭代次數num=10.按照本文算法得到的子類字典如圖1和圖2所示，圖3是相同圖像數據利用K-SVD算法得到的字典，視覺上看字典塊信息排列雜亂無章，字典的維數相對較高，列字典原子之間表現出一定的相似性，在一定程度上降低了字典的有效性，不利于對圖像結構特征進行保護，可能影響到圖像的恢復效果.圖1是圖像Lena利用本文算法生成的15類子字典.由圖1～3觀察比較可知，本文NLC-DL算法對圖像整體信息進行分類細化，由于不同類數據信息具有一定的差異性，最終獲得的n個分類字典與傳統算法獲得的一個字典相比，能夠更有效地捕捉圖像不同結構的細節紋理特征，如圖1中第4，5類字典及圖2中第1，2，14類字典雖然看起來極其相似，但是字典內部數據塊的紋理結構傾斜度又有一定的差別，能夠表現出圖像不同結構間的差異性.本文利用圖像非局部自相似性對圖像整體進行K-means聚類，用歐式距離衡量圖像塊間的相似性，由于每一類圖像塊數量不固定，使得類內圖像塊數量相對較少，且結構相對簡單的子類圖像構造的類內字典塊存在一些冗余信息，如圖1中第7，12，13，14類字典和圖2中第1，2，4，12類字典.

3.2 圖像去噪效果

自然圖像的多樣性使得同一算法可能會在不同圖像上表現出不同的性能，為了克服這一問題，筆者使用大量具有代表性的圖像進行測試.選取大小為512×512的Lena，Barbara，Cameraman，Boat，Peppers及Bridge圖像，并疊加不同標準差σ=10，20和30的高斯噪聲，利用DCT[20]，Global[16]，K-SVD[8]及本文NLC-DL算法分別進行測試，去噪結果如表1所示.

表1顯示所選圖像在不同噪聲水平下的PSNR值.通過對比可知，本文方法在圖像去噪方面優于DCT,Global算法0.27～2.69 dB，優于與本文框架結構類似的K-SVD算法0.11～0.76 dB.并且對于紋理豐富的Lena，Barbara及Boat圖像，通過不同方法的比較結果可見，對所選圖像施加的噪聲越大，本文算法的PSNR值增加得越多.說明本文利用結構聚類進行字典學習的方法更有利于保護圖像的紋理特征，在圖像恢復方面更為成功.

為了更加形象、直觀地表述本文算法在圖像恢復方面的效果，以細節紋理比較豐富的圖像Barbara為例，施加σ=20的高斯噪聲并運用不同方法進行圖像去噪，效果對比如圖4所示.從圖4中的具體細節放大信息來看，其他3種算法將圖像整體化處理使得圖像的明暗對比度減低，而本文算法在圖像對比度方面更接近原始圖像；對于一些細小紋理特征，其他算法都丟失了部分紋理信息，但本文方法恢復的紋理信息明顯比傳統算法更多、更清晰；在邊緣保護方面，其他算法均將邊緣平滑掉了，而本文方法基本上保持了邊緣的原有特征.由此說明,本文利用分類字典學習方法對圖像進行分類處理有助于保護圖像的紋理、邊緣等結構特征.

本文算法不論是從PSNR值還是細節結構特征方面，都優于其他3種方法.

4 結 論

本文利用非局部的思想對圖像進行結構聚類和字典學習，提出了基于稀疏表示的圖像分類字典學習方法.一方面，利用圖像的非局部自相似性對圖像塊進行結構聚類，有效地保持了圖像的結構信息；另一方面，對聚類后的圖像塊單獨進行字典學習，使得字典更有針對性，可以提高圖像的重構效果.實驗結果表明，本文算法與其他傳統算法相比，隨著圖像噪聲逐漸增大，無論是從平滑效果，還是對于邊緣、紋理等結構信息，本文算法所產生的學習字典結構性更強，能較好地表示訓練樣本，在峰值信噪比和視覺效果方面都優于傳統方法.

[1]Mallat S G,Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

[2]Thilagavathi M,Deepa P.An efficient dictionary learning algorithm for 3d medical image denoising based on sadct [C]//2013 International Conference on ICICES.Chennai:IEEE,2013:442-447.

[3]Dong Weisheng,Zhang Lei,Shi Guangming,et al.Nonlocally centralized sparse representation for image restoration[J].IEEE Transactions on Image Processing,2013,22(4):1620-1630.

[4]Thavalengal S,Mandal S,Sao A K.Significance of dictionary for sparse coding based pose invariant face recognition[C]//2014 Tewentieth National Conference on Communications.Kanpur:IEEE,2014:1-5.

[5]Lu Weizhi,Bai Cong,Kpalma K,et al.Multi-object tracking using sparse representation[C]//2013 IEEE International Conference on ICASSP.Vancouver:IEEE,2013:2312-2316.

[6]Tang Yufang,Li Xueming,Liu Yang,et al.Sparse dimensionality reduction based on compressed sensing[C]//2014 IEEE WCNC.Istanbul:IEEE,2014:3373-3378.

[7]Sun X,Nasrabadi N M,Tran T D.Task-driven dictionary learning for Hyperspectral Image classification with structured sparsity constraints[C]//2015 IEEE Geoscience and Remote Sensing Society.Milan:IEEE,2015:1-15.

[8]Aharon M,Elad M,Bruckstein A.K-SVD:An algorithm for designing overcomplete dictionary for sparse representation[J].IEEE Transactions on Singal Processing,2006,54(11):4311-4322.

[9]Sahoo S K,Makur A.Enhancing image denoising by controlling noise incursion in learned dictionaries[J].IEEE Signal Processing Letters,2015,22(8):1123-1126.

[10]Mazhar R,Gader P D.EK-SVD:Optimized dictionary design for sparse representations[C]//19th ICPR.Valparaiso:IEEE,2008:1-4.

[11]Feng Jianzhou,Song Li,Yang XiaoKang,et al.Sub clusteringK-SVD:Size variable dictionary learning for sparse representations[C]//2009 16th IEEE ICIP.Cairo:IEEE,2009:7-10.

[12]Ribhu R,Ghosh D.Dictionary design for sparse signal representations usingK-SVD with sparse Bayesian learning[C]//2012 IEEE 11th ICSP.Beijing:IEEE,2012:21-25.

[13]Gu Shuhang,Zhang Lei,Zuo Wangmeng,et al.Weighted nuclear norm minimization with application to image denoising[C]//2014 IEEE CVPR.Columbus:IEEE,2014:2862-2869.

[14]Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthonormal matching pursuit:Recursive function approximation with applications to wavelet decomposition[C]//1993 Conference Record of The Twenty-Seventh Asilomar Conference on Signals,Systems and Computers.Pacific Grove:IEEE,1993:40-44.

[15]Tillmann A M.On the computational Intractability of exact and approximate dictionary learning[J].IEEE Signal Processing Letters,2015,22(1):45-49.

[16]Elad M.Sparse and pedundant representations:From theory to applications in signal and image processing[M].London:Springer,2010:227-244.

[17]Donoho D L,Huo X.Uncertainty principles and ideal atomic decomposition[J].IEEE Transactions on Information Theory,2001,47(7):2845-2862.

[18]Lin Y,Lee D.BayesianL1-norm sparse learning[C]//2006 IEEE ICASSP.Toulouse:IEEE,2006:605-608.

[19]Ram I,Elad M,Cohen I.Image denosing using NL-means via smooth patch ordering[C]//2013 IEEE ICASSP.Vancouver:IEEE,2013:1350-1354.

[20]Srivastava V K.A DCT based algorithm for blocking artifact reduction from DCT coded images[C]//2006 IEEE ICIT.Mumbai:IEEE,2006:2815-2820.

(責任編輯 陶立方)

Imageclassificationdictionarylearningbasedonsparserepresentation

HE Xiaowei, ZHANG Li

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,JinhuaZhejiang321004,China)

In order to deal with the weak structure of dictionary in theK-SVD algorithm, an nonlocal classification dictionary learning method (NLC-DL) based on sparse representation was proposed by taking advantage of image nonlocal self-similarity. The method clustered image patches with structural similarity by theK-means algorithm, then the dictionaries for each class were learned to reinforce the effectiveness. The sparse coefficients obtained by the Orthogonal Matching Pursuit algorithm (OMP) were used to optimize all the dictionaries alternately. Both the sparse coefficients and the optimized dictionaries were used for reconstructing the true image. Experimental results showed that the obtained dictionaries achieved a better effect with less error on representing the training sample and maintained the structural information effectively. Furthermore, the proposed method for reconstructing images performed better than the traditional ones in terms of PSNR and visual effect.

nonlocal; self-similarity; sparse representation; dictionary learning;K-means

10.16218/j.issn.1001-5051.2015.04.008

2015-04-07；

：2015-05-07

浙江省自然科學基金資助項目(LY14F010008)

何小衛(1968-),男，浙江金華人，副教授.研究方向：稀疏和低秩；機器學習.

TP391

：A

：1001-5051(2015)04-0402-08