倪一寧　彭宏京

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

?

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

倪一寧彭宏京

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

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

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

0引言

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

(1)

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

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

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

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

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

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

1字典學(xué)習(xí)算法概述

(2)

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

D=(XCT)(CCT)-1

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

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

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

(1) 輸入信號(hào)的分解。

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

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

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

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

2.1塊稀疏的概念

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

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

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

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

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

(3)

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

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

圖1　字典流程框架

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

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

表1　迭代不同階段字典去噪效果評(píng)估

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

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

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

(4)

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

所以對(duì)稱字典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中的對(duì)應(yīng)列合并同時(shí)將W中對(duì)應(yīng)行合并，合并塊尺寸不能超過s直至所有字典原子合并。

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

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

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

4實(shí)驗(yàn)結(jié)果及分析

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

4.1塊結(jié)構(gòu)算法實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

5結(jié)語

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

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

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

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

參考文獻(xiàn)

[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] 楊真真,楊震,孫林慧.信號(hào)壓縮重構(gòu)的正交匹配追蹤類算法綜述[J].信號(hào)處理,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。江蘇省自然科學(xué)基金項(xiàng)目(BK2011794)。倪一寧，碩士生，主研領(lǐng)域：數(shù)字圖像處理中的信號(hào)處理。彭宏京，副教授。

中圖分類號(hào)TP391

文獻(xiàn)標(biāo)識(shí)碼A

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