基于稀疏表示的圖像分類字典學(xué)習(xí)*

何小衛(wèi), 張 莉

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

?

基于稀疏表示的圖像分類字典學(xué)習(xí)*

何小衛(wèi), 張 莉

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

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

非局部；自相似性；稀疏表示；字典學(xué)習(xí);K-均值

0 引 言

圖像的稀疏表示是通過引入過完備冗余字典，實(shí)現(xiàn)對(duì)信號(hào)的最優(yōu)逼近.基于圖像稀疏表示的過完備信號(hào)稀疏表示理論最早是由Mallat等[1]提出的，使用Gabor字典并引入匹配追蹤算法，通過逐步逼近的方法對(duì)信號(hào)進(jìn)行稀疏表示.近年來，基于過完備冗余字典的信號(hào)稀疏表示被廣泛應(yīng)用于圖像處理的各個(gè)領(lǐng)域：利用形狀自適應(yīng)字典塊對(duì)三維醫(yī)學(xué)圖像進(jìn)行去噪處理[2]；通過抑制噪聲的稀疏編碼進(jìn)行圖像恢復(fù)[3]；基于位置分類選擇合適加權(quán)分解人臉詞典并進(jìn)行稀疏編碼用于人臉識(shí)別[4]；利用稀疏表示進(jìn)行目標(biāo)檢測實(shí)現(xiàn)背景分離進(jìn)而實(shí)現(xiàn)目標(biāo)跟蹤[5]；基于壓縮感知構(gòu)造超完備稀疏字典進(jìn)行稀疏降維[6]；強(qiáng)調(diào)任務(wù)驅(qū)動(dòng)字典學(xué)習(xí)算法以提高高光譜分類的效果[7].

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

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

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

1 基于稀疏表示的圖像分類字典學(xué)習(xí)模型

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

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

或者

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

1.2 圖像分類字典學(xué)習(xí)模型

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

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

2 算法實(shí)現(xiàn)

利用圖像的非局部自相似性，充分考慮圖像塊間的相互聯(lián)系，對(duì)圖像塊進(jìn)行結(jié)構(gòu)聚類，并對(duì)聚類后的圖像塊做類內(nèi)字典學(xué)習(xí)，有效地捕捉了圖像的內(nèi)部結(jié)構(gòu)特征，增強(qiáng)了字典的有效性，加快了收斂速度，從而更好地實(shí)現(xiàn)圖像的重構(gòu).具體的類字典學(xué)習(xí)過程如下:

NLC-DL算法

輸入：訓(xùn)練樣本Y

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

①隨機(jī)選取k個(gè)聚類質(zhì)心點(diǎn)π1,π2,…,πk；

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

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

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

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

①計(jì)算殘差El=yi-Diai；

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

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

5)如果不能達(dá)到停止迭代的標(biāo)準(zhǔn)，那么返回第4步.

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

輸出：第i類數(shù)據(jù)對(duì)應(yīng)的子字典Di及恢復(fù)圖像X.

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 分類子字典

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

3.2 圖像去噪效果

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

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

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

本文算法不論是從PSNR值還是細(xì)節(jié)結(jié)構(gòu)特征方面，都優(yōu)于其他3種方法.

4 結(jié) 論

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

[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.

(責(zé)任編輯 陶立方)

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

浙江省自然科學(xué)基金資助項(xiàng)目(LY14F010008)

何小衛(wèi)(1968-),男，浙江金華人，副教授.研究方向：稀疏和低秩；機(jī)器學(xué)習(xí).

TP391

：A

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