基于一種網(wǎng)絡結(jié)構(gòu)的塊稀疏字典學習

倪一寧　彭宏京

(南京工業(yè)大學電子與信息工程學院　江蘇 南京 211816)

?

基于一種網(wǎng)絡結(jié)構(gòu)的塊稀疏字典學習

倪一寧彭宏京

(南京工業(yè)大學電子與信息工程學院江蘇 南京 211816)

摘要以過完備字典為基礎(chǔ)，信號可以被描述為原子的稀疏線性組合。在以往的字典學習方法中，大都是以單個原子為單位進行字典學習。利用稀疏子空間聚類的方法將字典中具有相同稀疏表達形式的原子歸類為一組，形成具有塊結(jié)構(gòu)的字典，然后對訓練信號稀疏編碼，最后結(jié)合梯度下降的方法對字典進行更新。實驗結(jié)果表明，該方法在相同迭代次數(shù)下的優(yōu)化收斂速度較快，而且對信號的重構(gòu)誤差率優(yōu)于傳統(tǒng)方法。另外，所構(gòu)造一種對稱網(wǎng)絡結(jié)構(gòu)的字典學習流程框架，不同于一次性用全部訓練數(shù)據(jù)進行訓練的方法，該學習流程每處理一組信號，字典進行一次更新，實現(xiàn)了對字典的分步更新。

關(guān)鍵詞對稱網(wǎng)絡結(jié)構(gòu)塊稀疏梯度下降字典學習與信號稀疏表示

0引言

信號的表示是信號處理中的核心部分，大多數(shù)信號處理過程中依賴于信號的表示，例如圖像壓縮、去噪，信號的稀疏表現(xiàn)形式是常用的技術(shù)手段之一。將非正交基構(gòu)成的字典設(shè)計為過完備的，設(shè)字典的列數(shù)K，字典的原子的維數(shù)是n, k>>n,稱為過完備字典[1-4]。稀疏編碼形成的系數(shù)向量與字典原子相乘疊加形成重構(gòu)信號，所以信號的稀疏表示與重構(gòu)可以用下式表示：

(1)

可以看出信號是由原子線性組合而成的，{d(k)}k是組成字典的一個個原子。當大多數(shù)系數(shù)c(k)為0時，這種信號表示就是稀疏的表達形式，{d(k)}k組合而成的矩陣即為所謂的字典形式。

對于大多數(shù)字典而言，字典的設(shè)計多種多樣，這樣字典也能夠來表示寬泛的各種類型的信號。對于特定的信號和字典，為了用字典來精確表示和重構(gòu)信號，需要通過字典對大量該類型信號訓練[9]。字典學習過程中要將原始訓練信號轉(zhuǎn)化為與字典原子具有相同維數(shù)的列信號組合，同時在字典的設(shè)計方面，字典尺寸和結(jié)構(gòu)也是要考慮的要素[11,13]。

在字典設(shè)計中，選擇合適的字典學習算法是重要的。隨著利用字典學習的方法處理信號的優(yōu)越性日趨明顯，各種各樣的字典學習算法不斷被提出以適應多種輸入信號類型。字典學習算法的實質(zhì)是優(yōu)化目標式使得誤差在一定原則下最小。求解目標誤差式的最小二乘解其中一種方法是以直觀閉解的形式直接求得全局最優(yōu)解，其中典型的就是MOD[4]。另外通常以迭代的方法求局部最優(yōu)解來獲得最小誤差，梯度下降是常用的一種迭代方法。除此以外，K均值聚類奇異值分解算法(K-SVD), 迭代最小二乘字典學習算法(ILS-DLA)等都是字典學習算法的發(fā)展[1,4]。

對信號的稀疏編碼是字典學習過程中重要部分。稀疏編碼用于在信號的分解與重構(gòu)過程中產(chǎn)生稀疏的系數(shù)矩陣，通常有匹配追蹤法(MP)、正交匹配追蹤法(OMP)和FOCUSS等方法。MP算法是一種貪婪算法，每次都選擇與信號最匹配的字典原子，獲得的余量再選擇匹配原子，直接達到預先設(shè)定的稀疏度或者余量誤差閾值[7]。而OMP方法選擇匹配字典原子之前對字典原子做正交處理，所以在稀疏編碼過程中產(chǎn)生的余量不再選擇已匹配過的原子，從而使得編碼過程收斂速度更快[3,6,8,10]。

本文預先介紹MOD方法的字典學習，用MOD進行字典的更新優(yōu)化時，字典更新的表達式是對欠定逆問題直觀的最小二乘解。ILS-DLA是以MOD為主的字典學習方法[4]，由此發(fā)展而來的遞歸最小二乘法(RLS-DLA)與本文所用的梯度下降法相似能夠?qū)崿F(xiàn)分步的稀疏編碼[2，5]。

字典的優(yōu)化和信號的稀疏編碼通常是在單個字典原子的基礎(chǔ)上進行的，針對塊稀疏信號(指信號不為0的地方成塊出現(xiàn)的信號)，提出了塊稀疏的壓縮感知模型。所謂塊稀疏指兩方面，一方面指字典的塊結(jié)構(gòu)，能夠表達相同信號的字典原子，將以聚類的形式結(jié)合形成最小的字典原子單位，從而在字典中形成塊結(jié)構(gòu)。當最小的字典原子單位為1時就降化為普通的字典結(jié)構(gòu)；另一方面是塊稀疏的編碼，為了適應塊結(jié)構(gòu)字典的稀疏編碼，將OMP的編碼方法改善為BOMP(Block OMP)即塊正交匹配追蹤，BOMP在字典中選擇與信號最匹配的塊原子從而能夠?qū)崿F(xiàn)信號的塊稀疏編碼。信號按照潛在的子空間對字典進行塊結(jié)構(gòu)的分類。以往字典的塊結(jié)構(gòu)是固定的[3]，不會隨著信號的輸入重新調(diào)整字典的塊結(jié)構(gòu)。本文的字典塊結(jié)構(gòu)除了最大塊尺寸(指字典中最大的聚類原子個數(shù))是設(shè)定的，其余由輸入信號決定，這樣設(shè)計的字典塊結(jié)構(gòu)能夠更好地適應信號的表示。梯度下降的方法和塊稀疏結(jié)合，可以在實現(xiàn)分步稀疏編碼的同時提高字典更新的收斂速度[12]。

1字典學習算法概述

(2)

ILS-DLA使用最小二乘法解這個誤差表達式[1-4]，s為重構(gòu)需要的原子數(shù)，固定系數(shù)矩陣C,可以得出：

D=(XCT)(CCT)-1

利用上式對字典D更新，然后保持D固定，利用OMP重新計算C，反復這兩個步驟直到字典D收斂[4]。

ILS-DLA發(fā)展出的RLS-DLA可以歸納為一種連續(xù)的字典優(yōu)化方法,更適合大規(guī)模訓練信號，因為RLS-DLA可以實現(xiàn)在信號分步輸入的情況下對字典連續(xù)優(yōu)化更新[2]。在本文中使用的梯度下降法同樣具有這個特性。

無論是ILS-DLA還是RLS-DLA字典更新方法大致四步驟：

(1) 輸入信號的分解。

(2) 固定字典D對輸入信號稀疏編碼，形成系數(shù)矩陣C。

(3) 固定系數(shù)矩陣C優(yōu)化字典D。

(4) 重復步驟(2)-步驟(3)直到字典D優(yōu)化收斂。

2塊稀疏的描述與實現(xiàn)

2.1塊稀疏的概念

塊稀疏的壓縮感知模型包括字典的塊結(jié)構(gòu)與塊稀疏編碼兩部分。字典的塊結(jié)構(gòu)是指能夠表示相同信號的原子聚類成為字典的一個原子單位，該原子單位里的原子個數(shù)將不再是一個。與塊結(jié)構(gòu)相對應的塊稀疏編碼法BOMP是對正交匹配追蹤法OMP的改善[3,6,8]，其本質(zhì)是選擇與訓練信號最匹配的字典原子塊。

2.2字典塊結(jié)構(gòu)和系數(shù)矩陣的初始化

對于給定的字典根據(jù)輸入信號設(shè)計字典的塊結(jié)構(gòu)，首先初始化字典結(jié)構(gòu)p和稀疏系數(shù)矩陣C，設(shè)字典D為N×K規(guī)模的矩陣，按照常規(guī)，字典D是由K個N維的向量組成的，每個向量是重構(gòu)稀疏信號的原子，為滿足冗余字典的要求，其中K>>N。初始化字典結(jié)構(gòu)p為p=[1,2,…,K],每個原子為一個最小單位塊等同于普通的字典結(jié)構(gòu)，所以對系數(shù)矩陣C初始化利用OMP計算就可以滿足。設(shè)稀疏度為k,表示每個重構(gòu)信號由k個非零原子構(gòu)成，字典的塊結(jié)構(gòu)尺寸設(shè)置為s，由于信號可視為k個塊原子組合而成的，所以在用OMP初始化系數(shù)C時，初始的稀疏度應該是k×s[3,6](系數(shù)矩陣中的每個列向量都有至多有k×s個非零元素)。

2.3更新塊結(jié)構(gòu)p與實例描述

更新塊結(jié)構(gòu)的時候應不再對系數(shù)矩陣C更新，為了在塊結(jié)構(gòu)p下得到最少的非零系數(shù)，可以描述為以下公式：

(3)

3基于網(wǎng)絡結(jié)構(gòu)的塊稀疏字典優(yōu)化方法

3.1字典優(yōu)化流程框架

圖1　字典流程框架

字典優(yōu)化流程可以概括為：首先對字典的塊結(jié)構(gòu)與系數(shù)矩陣初始化，然后基于字典D，對訓練信號X塊稀疏編碼產(chǎn)生系數(shù)矩陣C；最后利用C對W優(yōu)化更新。需要指出的是每次利用梯度下降對字典更新完成后，隨著新的訓練信號輸入會產(chǎn)生新的系數(shù)矩陣C，W的塊結(jié)構(gòu)也應及時優(yōu)化更新。

基于本文的字典學習框架的字典學習方法是輪換迭代的，即每學習完一輪，就會將W的轉(zhuǎn)置作為下一輪字典學習的初始字典D，學習一輪視為迭代1次，實驗一共迭代100次，分別記錄迭代第25次、50次、75次和100次的字典為D25、D50、D75和D100。分別用這四個字典對同一幅噪聲圖片去噪，記錄去噪后圖片的PSNR和MSE放入下面表1中對比。PSNR為峰值信噪比，MSE為均方根誤差。

表1　迭代不同階段字典去噪效果評估

從表1可以看出隨著迭代次數(shù)的增加，PSNR增加，MSE減小，對信號的重構(gòu)效果越來越好。同時也說明將W的轉(zhuǎn)置作為下一輪字典學習的初始字典D的方法是可行的。

另外需要注意的是由于此時字典的最小原子單位為塊，利用BOMP方法編碼產(chǎn)生C的最小單位也是塊的形式，例如，設(shè)塊結(jié)構(gòu)字典塊大小為s,字典中有k個塊原子，塊原子信號維度為n,那么字典大小為n×(K×s)，設(shè)輸入的一組訓練信號大小為n×s，可得C的大小為(K×s)×s,由于字典塊尺寸s不等于1，所以C的最小單位為塊，不是單行或單列的。

3.2梯度下降字典優(yōu)化方法的推導

(4)

其中，XTX中不含Wij，所以：

所以對稱字典W的更新有以下關(guān)系式：

Wn=Wn-1-a×[-CX+CTCWn-1]ij

(5)

本文字典優(yōu)化方法具體步驟如下：

(1) 設(shè)置初始化字典結(jié)構(gòu)p=[1,2,…,K],字典塊最大尺寸為s,利用OMP將系數(shù)矩陣C求出，稀疏度為k×s。

(2) 根據(jù)第2節(jié)的描述的原則，尋找C中具有相同稀疏形式的列,將D中的對應列合并同時將W中對應行合并，合并塊尺寸不能超過s直至所有字典原子合并。

(3) 根據(jù)合并后的D，利用BOMP計算新的系數(shù)矩陣C。

(4) 根據(jù)訓練信號X和系數(shù)矩陣C，利用式(5)對W更新。

(5) 有信號輸入完成更新字典后，將W的轉(zhuǎn)置作為下一輪的初始字典D，重復步驟(1)-步驟(4)，直至字典收斂。需要指出首次輸入信號之后，由于字典形成了塊結(jié)構(gòu)，第(1)步改為根據(jù)上一次更新后的字典及其塊結(jié)構(gòu)，利用BOMP計算新的系數(shù)矩陣C。

4實驗結(jié)果及分析

在實驗部分，要測試和對比兩部分，分別是字典塊結(jié)構(gòu)算法中的系數(shù)稀疏度選擇、本文算法與ILS-DLA、K-SVD的對比實驗。

4.1塊結(jié)構(gòu)算法實驗

圖2　塊覆蓋成功率隨稀疏度的變化　圖3　誤差率隨稀疏度的變化

從圖2可以看出當k>5時，字典塊恢復率r明顯降低，而當k<5時字典塊恢復率r都較高。圖3可以看出隨著k的增長誤差率e也逐漸增長。所以在本文塊的稀疏度的選擇不能超過5。

4.2本文字典優(yōu)化方法與K-SVD、ILS-DLA重構(gòu)去噪對比實驗

設(shè)定D為64×1024的隨機矩陣并進行歸一化，字典塊結(jié)構(gòu)最大尺寸s=2,系數(shù)矩陣C時的稀疏度最大值設(shè)置為8(s×k=4)，梯度下降學習速率設(shè)置為0.05，調(diào)節(jié)速率為0.001。輸入訓練信號為圖像庫中隨機的選取的100幅圖片，測試圖片不在訓練圖片范圍之內(nèi)。對測試圖片加方差σ為20和30，均值為0的高斯白噪聲。如圖4-圖6所示。

圖4　圖像去噪結(jié)果比對

圖5　圖像去噪結(jié)果比對

圖6　圖像去噪結(jié)果比對

圖7　迭代過程中字典優(yōu)化誤差‖的變化

隨機選取100幅圖片作為輸入信號，觀測本文方法、ILS-DLA、K-SVD在迭代過程中的誤差變化如圖7所示。

由圖7可知在迭代過程中，本文方法中字典收斂速度比K-SVD、ILS-DLA更快。

5結(jié)語

本文方法能夠更加直觀地展現(xiàn)字典的訓練與重構(gòu)，以Frobenius范數(shù)衡量字典與初始字典的誤差，實驗證明本文的字典優(yōu)化收斂速度優(yōu)于K-SVD和ILS-DLA。

利用優(yōu)化后的字典處理噪聲圖片，實驗驗證了本文方法處理的圖片的PSNR均高于K-SVD和ILS-DLA。這也說明本文的字典優(yōu)化方法對信號的重構(gòu)效果優(yōu)于K-SVD和ILS-DLA。

對比用特定字典訓練特定類型信號的方法，本文方法更適合處理大量各種類型的訓練信號，優(yōu)化后的字典可以更精確的重構(gòu)表示各種類型的信號。

本文方法執(zhí)行速度優(yōu)于ILS-DLA,但是比K-SVD慢，所以在執(zhí)行速度方面需要改善。另外最大塊尺寸s和學習速率η的設(shè)置對字典優(yōu)化速率和信號重構(gòu)的影響都是需要進一步探索的課題。

參考文獻

[1] Michal Aharon,Michael Elad,Alfred Bruckstein.K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Trans on Signal Processing,2006,54(11):4311-4322.

[2] Karl Skretting,Kjersti Engan.Recursive least squares dictionary learning algorithm[J].IEEE Trans on Signal Processing,2010,58(4):2121-2130.

[3] Kevin Rosenblum,Lihi Zelnik-Manor.Dictionary optimization for block-sparse representations signal Processing[J].IEEE Trans on Signal Processing,2012,60(5):2386-2395.

[5] Julien Mairal,Francis Bach,Jean Ponce,et al.Online dictionary learning for sparse coding,2009[C]//Proceedings of the 26th Annual International Conference on MachineLearning,ICML.2009:14-18.

[6] Yuli Fu,Haifeng Li,Qiheng Zhang,et al.Block-sparse recovery via redundant block OMP[J].IEEE Trans on Signal Processing,2014,97:162-171.

[7] 楊真真,楊震,孫林慧.信號壓縮重構(gòu)的正交匹配追蹤類算法綜述[J].信號處理,2013,29(4):486-496.

[8] Pati Y C,Rezzaiifar R,SKrishnaprsad P.Orthogonal matching pursuit:recursive function approximation with application to wavelet decomposition[C]//1993 ConferenceRecord of The 27thAsilomar Conference on Signal Process,1997,45(3):600-616.

[9] Elad M,Aharon M.Image denoising via sparse and redundant representations over learned dictionaries[J].IEEE Trans Image Process,2006,15(12):3736-3745.

[10] Julien Mairal,Francis Bach,Jean Ponce,et al.Online learning for matrix factorization and sparse coding[J].Journal of Machine Learning Research,2010,11(1):19-60.

[11] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Double sparsity learning sparse dictionaries[J].IEEE Trans on Signal Processing,2010,58(3):1553-1564.

[12] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Efficient implementation of the K-SVD algorithm using batch orthogonal matching pursuit[EB/OL].http://www.technion.ac.il/～ronrubin/software.html.

[13] Ron Rubinstein,Michael Zibulevsky,Michael Elad.Dictionaries for sparse representation modeling[J].IEEE Proceedings-Special Issue on Applications of Sparse Representation&Compressive Sensing,2010,98(6):972-982.

BLOCK SPARSE DICTIONARY LEARNING BASED ON A NETWORK STRUCTURE

Ni YiningPeng Hongjing

(SchoolofElectronicandInformationEngineering,NanjingUniversityofTechnology,Nanjing211816,Jiangsu,China)

AbstractBased on over-complete dictionary, the signal can be described as sparse linear combination of atoms. In previous dictionary learning methods, most of them are based on single atom unit. We made use of sparse subspace clustering method to range the atoms with same sparse expression form into one group and formed a dictionary with block structure, and then conducted the sparse coding on training signals, finally updated the dictionary in combination with gradient descent method. Experimental result showed that this method had faster optimised convergence rate in same iteration times, and was superior to traditional methods in signal reconstruction error rate. Besides, we constructed a dictionary learning process framework with symmetrical network structure, differing from the method which uses all training data one-off in training, in it the dictionary will update once along with each processing of a set of signals in this learning process, and it realises the stepwise update of the dictionary.

KeywordsSymmetrical network structureBlock sparseGradient descentDictionary learning and signal sparse representation

收稿日期：2015-01-12。江蘇省自然科學基金項目(BK2011794)。倪一寧，碩士生，主研領(lǐng)域：數(shù)字圖像處理中的信號處理。彭宏京，副教授。

中圖分類號TP391

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.05.065