基于自適應(yīng)K-SVD字典的視頻幀稀疏重建算法

錢(qián) 陽(yáng)，李 雷，袁安安

(南京郵電大學(xué) 視覺(jué)認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

基于自適應(yīng)K-SVD字典的視頻幀稀疏重建算法

錢(qián) 陽(yáng)，李 雷，袁安安

(南京郵電大學(xué) 視覺(jué)認(rèn)知計(jì)算與應(yīng)用研究中心，江蘇 南京 210023)

壓縮感知理論的一個(gè)重要前提是找到信號(hào)的稀疏域，其直接影響著算法的重構(gòu)精度，研究快速高效的信號(hào)稀疏表示方法具有重大的現(xiàn)實(shí)意義。為了提高字典訓(xùn)練速度與性能，基于傳統(tǒng)的K-SVD算法，提出了一種自適應(yīng)K-SVD字典學(xué)習(xí)算法(AdaptiveK-SVD)。該算法交替執(zhí)行稀疏編碼階段和字典更新階段。在稀疏編碼階段，通過(guò)引入自適應(yīng)稀疏約束機(jī)制，以獲得更稀疏的表示系數(shù)，從而進(jìn)一步提高字典的更新效率；而在字典更新階段，則使用經(jīng)典K-SVD的字典更新方式來(lái)實(shí)現(xiàn)字典原子的逐列更新。將所提算法應(yīng)用于壓縮感知理論的信號(hào)稀疏表示中，實(shí)現(xiàn)視頻幀的稀疏重建。仿真對(duì)比實(shí)驗(yàn)結(jié)果表明，所提算法比經(jīng)典的K-SVD算法的字典訓(xùn)練速度更快，稀疏表示性能更優(yōu)，且能有效減少壓縮感知的重構(gòu)誤差。

K-SVD算法；自適應(yīng)K-SVD算法；字典學(xué)習(xí)；稀疏表示；壓縮感知

0 引 言

近年來(lái)，以信號(hào)的稀疏性先驗(yàn)求解圖像反問(wèn)題吸引著學(xué)者們的廣泛關(guān)注[1-2]，尤其是壓縮感知(Compressed Sensing,CS)領(lǐng)域[3]。CS理論主要包括三個(gè)階段：信號(hào)的稀疏表示、觀測(cè)矩陣的選取和信號(hào)重構(gòu)。其中尋找信號(hào)最佳的稀疏域，是壓縮感知理論應(yīng)用的前提和基礎(chǔ)，它決定了圖像反問(wèn)題的求解質(zhì)量。

傳統(tǒng)的稀疏表示思路是基于固定正交基的變換，如傅里葉變換、離散余弦變換、小波變換、Curvele變換等。這些正交基雖然構(gòu)造相對(duì)簡(jiǎn)單，計(jì)算復(fù)雜度低，但不能與圖像本身的復(fù)雜結(jié)構(gòu)最佳匹配，并不是最優(yōu)的稀疏變換基。隨著字典學(xué)習(xí)方法[4-6]的深入研究，人們開(kāi)始根據(jù)信號(hào)本身來(lái)學(xué)習(xí)過(guò)完備字典，對(duì)稀疏編碼研究的一個(gè)熱點(diǎn)是信號(hào)在冗余字典下的稀疏分解。諸多研究成果表明，通過(guò)學(xué)習(xí)獲得的字典原子數(shù)量更多,形態(tài)更豐富,具有更稀疏的表示，能更好地與信號(hào)或圖像本身的結(jié)構(gòu)匹配，為圖像帶來(lái)更大的壓縮空間，在圖像分類(lèi)[7]、圖像去噪[8-9]、圖像超分辨率[10]等方面性能更優(yōu)。

K-SVD(K-Singular Value Decomposition)[11]算法是目前一個(gè)比較受歡迎的字典學(xué)習(xí)算法，該算法交替執(zhí)行稀疏編碼階段和字典更新階段，并且在字典更新步驟中利用奇異值分解方式逐個(gè)更新字典原子，避免矩陣求逆計(jì)算的同時(shí)也提高了算法的收斂速度，在圖像處理中應(yīng)用極其廣泛[12-14]。然而，K-SVD算法存在字典訓(xùn)練時(shí)間長(zhǎng)、計(jì)算量大等不足。

針對(duì)這一問(wèn)題，為提高字典學(xué)習(xí)的收斂速度與性能，提出了一種新的快速字典學(xué)習(xí)算法-自適應(yīng)K-SVD算法(adaptiveK-SVD)。該算法在稀疏編碼階段，將稀疏上界與迭代更新的字典關(guān)聯(lián)，以獲得自適應(yīng)的稀疏約束；而在字典更新階段，使用經(jīng)典K-SVD的字典更新方式，通過(guò)稀疏編碼和字典更新兩步迭代學(xué)習(xí)得到字典。將訓(xùn)練的自適應(yīng)字典用于視頻幀的稀疏表示。實(shí)驗(yàn)結(jié)果表明，提出算法運(yùn)行速度快，具有更好的稀疏表示性能。

1 預(yù)備知識(shí)

1.1 壓縮感知理論基礎(chǔ)

在壓縮感知理論中，若被測(cè)信號(hào)x∈Rn×1在某正交基或緊框架Ψ=(ψ1,ψ2,…,ψn)T上是稀疏的或是可壓縮的，則可用一個(gè)與稀疏變換基不相關(guān)的m×n維(m?n)觀測(cè)矩陣Φ對(duì)稀疏變換向量Θ=ΨTx進(jìn)行線性觀測(cè)，得到觀測(cè)向量y∈Rm×1，而后利用優(yōu)化算法從低維觀測(cè)向量y中高概率地重構(gòu)出原始信號(hào)x[15]，其觀測(cè)模型如式(1)所示：

y=Φx=ΦΨΘ

(1)

信號(hào)的稀疏性是壓縮感知理論最基本的前提，它決定了CS非自適應(yīng)采樣過(guò)程的有效性。常見(jiàn)的稀疏基包括DCT基、小波基、FFT基等，這些基構(gòu)造簡(jiǎn)單，計(jì)算復(fù)雜度低，方便分析，然而不能處理圖像以及更高維數(shù)據(jù)的奇異性，并非最優(yōu)的稀疏基。近年來(lái)，基于過(guò)完備字典的信號(hào)稀疏分解方法發(fā)展迅猛，如何構(gòu)造出更高效的冗余字典已成為學(xué)者們研究的重點(diǎn)。

設(shè)計(jì)出一個(gè)平穩(wěn)的、與稀疏基Ψ不相關(guān)的測(cè)量矩陣Φ是CS理論應(yīng)用的關(guān)鍵，Candès和Tao指出，觀測(cè)矩陣Φ只有滿足了約束等距性(Restricted Isometry Property，RIP)條件，才能保證準(zhǔn)確地重構(gòu)出原始信號(hào)。常用的觀測(cè)陣有高斯隨機(jī)矩陣、哈達(dá)瑪矩陣、伯努利矩陣等。

(2)

其中，λ為正則化參數(shù)。

目前重構(gòu)算法主要集中于貪婪追蹤算法、凸優(yōu)化算法和組合算法等。

1.2 字典學(xué)習(xí)方法

基于過(guò)完備字典的稀疏表示是一種全新的信號(hào)表示理論。近年來(lái)，以設(shè)計(jì)簡(jiǎn)單、高效、通用性強(qiáng)的字典為目標(biāo)的字典學(xué)習(xí)方法吸引著學(xué)者們的廣泛關(guān)注，其中最受歡迎的是由Michal Aharon、Michael Elad提出的K-SVD字典學(xué)習(xí)算法。

該算法解決的是如式(3)所示的優(yōu)化問(wèn)題：

(3)

K-SVD算法的具體步驟如下：

算法1：K-SVD算法。

初始化：隨機(jī)初始化歸一化字典矩陣D(0)∈Rn×K

While停止迭代條件不滿足；

1)稀疏編碼階段。

固定字典D，使用任意一種追蹤算法來(lái)求解稀疏表示系數(shù)ai(i=1,2,…,N)。

(4)

2)字典更新階段。

固定稀疏系數(shù)矩陣A，對(duì)于k=1,2,…,K

(1)定義使用到原子dk的樣本的索引為：ωk={i|1≤i≤N,ai(k)≠0}；

更新字典：dk=u1,ak=Δ(1,1)·v1。

2 自適應(yīng)K-SVD算法

盡管K-SVD算法不需要矩陣求逆計(jì)算，且在字典更新階段聯(lián)合更新系數(shù)矩陣與字典原子，但存在字典訓(xùn)練時(shí)間長(zhǎng)、計(jì)算量大等缺陷。為此，對(duì)經(jīng)典的K-SVD算法進(jìn)行改進(jìn)，提出了自適應(yīng)K-SVD算法。該算法交替執(zhí)行稀疏編碼和字典更新這兩個(gè)階段。

2.1 稀疏編碼階段

不同于K-SVD算法的稀疏編碼方式，新算法利用字典的相干性將稀疏約束上限與迭代更新的字典關(guān)聯(lián)，以獲得自適應(yīng)的稀疏約束上限，從而反復(fù)減少重構(gòu)誤差。

定義Tj為每次迭代過(guò)程中的稀疏約束上界：

(5)

其中，μ(D)∈[0,1]表示字典的相干性，其描述了過(guò)完備字典中原子間的最大相似程度，公式如下[16]：

(6)

當(dāng)μ(D)值很大時(shí)，字典原子間相似程度很強(qiáng)，反之很弱。

為了充分說(shuō)明Tj的合理性，引入如下定理[16-17]：

定理1：給定字典D∈Rn×K(K>n)，其相干性為μ(D)，假設(shè)x=Da有稀疏解a，其稀疏度S若滿足：

(7)

則可推導(dǎo)出以下結(jié)論：

(1)解a必定是最稀疏的；

(2)式(3)中的l0問(wèn)題也可以等價(jià)為l1問(wèn)題；

(3)任意一種追蹤算法(如OMP)都能從字典D中找出最佳的S項(xiàng)原子的線性組合。

由定理1可見(jiàn)，所定義的Tj能夠保證稀疏信號(hào)精確恢復(fù)，是合理可行的。

使用Tj代替式(4)中的T0，則稀疏編碼階段即為求解如下的優(yōu)化問(wèn)題：

(8)

該問(wèn)題可以通過(guò)任意一種追蹤算法(如BP、OMP)進(jìn)行求解。

2.2 字典更新階段

在該階段應(yīng)用經(jīng)典的K-SVD字典更新方式，根據(jù)稀疏表示系數(shù)A，對(duì)字典D中的原子進(jìn)行迭代更新，字典列的更新結(jié)合稀疏表示系數(shù)的一個(gè)更新，使字典和稀疏表示系數(shù)同步更新。此階段求解的是如下的優(yōu)化問(wèn)題：

(9)

經(jīng)典的K-SVD算法采用SVD來(lái)求解上述優(yōu)化問(wèn)題。

給定一組視頻序列，假設(shè)其由I幀W×L圖像組成，則這組視頻序列可表示為[18]：

squ=fr(x,y)

(10)

其中，1≤x≤L，1≤y≤W，1≤r≤I。

(11)

綜上，基于自適應(yīng)K-SVD字典學(xué)習(xí)算法的視頻幀稀疏重建算法的具體實(shí)現(xiàn)步驟如下：

算法2：AdaptiveK-SVD-CS算法。

初始化：隨機(jī)初始?xì)w一化字典矩陣D(0)∈Rn×K，通過(guò)式(5)獲得初始化稀疏約束上限T0。

forj=1,2,…,P

1)稀疏編碼階段。

固定當(dāng)前字典Dj-1和稀疏約束上限Tj-1，使用OMP算法求解式(8)，獲得對(duì)應(yīng)于訓(xùn)練樣本X的稀疏系數(shù)矩陣Aj。

2)字典更新階段。

固定稀疏系數(shù)矩陣Aj，對(duì)于k=1,2,…,K

更新字典原子：dk=u1,ak=Δ(1,1)·v1。

獲得更新后的字典Dj。

利用式(5)計(jì)算稀疏約束上限Tj。

end

fort=1,2,…,WL/n

end

3 仿真實(shí)驗(yàn)及分析

采用格式為CIF的標(biāo)準(zhǔn)視頻序列Foreman進(jìn)行實(shí)驗(yàn)仿真，隨機(jī)選取Foreman的第1、6、10、15、23幀作為測(cè)試樣本集，如圖1所示。

圖1 測(cè)試圖像集

實(shí)驗(yàn)中將大小為352×288的視頻幀分成不重疊的8×8圖像塊，利用高斯隨機(jī)矩陣對(duì)每個(gè)圖像塊進(jìn)行觀測(cè)，以獲得CS觀測(cè)值。設(shè)置所訓(xùn)練的字典原子數(shù)為256，最大迭代次數(shù)為30。實(shí)驗(yàn)平臺(tái)為Windows 7,Intel(R) Core(TM) i7-5600U CPU,2.6 GHz,8 GB，所有實(shí)驗(yàn)設(shè)計(jì)基于Matlab R2011a編程實(shí)現(xiàn)。

3.1 稀疏基選擇的視覺(jué)效果

為了驗(yàn)證改進(jìn)的字典學(xué)習(xí)算法具有更好的稀疏表示性能，分別采用K-SVD算法和所提AdaptiveK-SVD算法對(duì)視頻序列的第23幀進(jìn)行稀疏表示，從圖像本身學(xué)習(xí)過(guò)完備字典。實(shí)驗(yàn)中設(shè)置K-SVD算法的稀疏度為5，此處稀疏度為稀疏編碼階段稀疏表示系數(shù)中非零分量數(shù)目的最大值。通過(guò)兩種字典學(xué)習(xí)算法訓(xùn)練出的冗余字典如圖2所示。

從圖2可以看出，采用K-SVD算法訓(xùn)練出的字典已經(jīng)能較好地與圖像本身的結(jié)構(gòu)相匹配，而所提AdaptiveK-SVD算法訓(xùn)練出的字典形態(tài)更豐富，能與視頻幀本身的復(fù)雜結(jié)構(gòu)最佳匹配，稀疏性能更優(yōu)，具有更好的應(yīng)用前景。

圖2 兩種字典學(xué)習(xí)算法訓(xùn)練出的字典

3.2 在視頻幀重構(gòu)精度上的改進(jìn)

本節(jié)將會(huì)展示所提字典學(xué)習(xí)算法對(duì)壓縮感知重構(gòu)性能的影響。分別選用K-SVD冗余字典和自適應(yīng)K-SVD冗余字典作為CS的稀疏基，利用OMP算法對(duì)測(cè)試圖像集中的每一幅圖像進(jìn)行重構(gòu)。為了方便描述，分別記這兩種算法為KSVD-CS和Adaptive KSVD-CS。

為了評(píng)估各算法的重構(gòu)性能，除了選用PSNR作為評(píng)價(jià)標(biāo)準(zhǔn)外，近年來(lái)相關(guān)學(xué)者提出的FSIM[19]可以用來(lái)衡量重構(gòu)圖像的視覺(jué)效果。FSIM值越高，則重構(gòu)圖像的視覺(jué)效果越好。

圖3從直觀上給出了不同采樣率下兩種算法的運(yùn)行時(shí)間，PSNR和FSIM的對(duì)比情況。為了消除隨機(jī)性，運(yùn)行時(shí)間、PSNR、FSIM的數(shù)值均取五幅測(cè)試幀的平均值，且每一測(cè)試幀的TIME，PSNR與FSIM均取10次執(zhí)行結(jié)果的平均值。

從圖3(a)可以看出，所提Adaptive KSVD-CS算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)低于KSVD-CS算法，這是因?yàn)樗岬淖赃m應(yīng)K-SVD字典學(xué)習(xí)方法在稀疏編碼階段自適應(yīng)選擇稀疏度，加快了字典的訓(xùn)練速度。

從圖3(b)、(c)可以看出，當(dāng)采樣率較低時(shí)，兩種算法的重構(gòu)效果都不算很好，隨著采樣率的增加，兩種算法的重構(gòu)性能都在提升，且所提算法的重構(gòu)效果略勝一籌。

4 結(jié)束語(yǔ)

圖3 兩種算法重構(gòu)性能隨采樣率變化圖

為提高字典學(xué)習(xí)的收斂速度與性能，提出了一種自適應(yīng)K-SVD字典學(xué)習(xí)算法。該算法在稀疏編碼階段根據(jù)當(dāng)前字典自適應(yīng)地調(diào)整稀疏度，更新字典則使用經(jīng)典K-SVD的字典更新方式，稀疏編碼與字典更新兩步迭代學(xué)習(xí)得到字典，并將所學(xué)習(xí)到的字典用于視頻幀的稀疏表示。仿真對(duì)比實(shí)驗(yàn)表明，所提算法提升了字典訓(xùn)練速度，提高了重構(gòu)性能。

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(5):1289-1306.

[2] Candès E,Tao T.Near optional signal recovery from random projections:universal encoding strategies[J].IEEE Transactions on Information Theory,2006,52(12):5406-5425.

[3] Donoho D L,Tsaig Y.Extensions of compressed sensing[J]. Signal Processing,2006,86(3):533-548.

[4] 練秋生,石保順,陳書(shū)貞.字典學(xué)習(xí)模型、算法及其應(yīng)用研究進(jìn)展[J].自動(dòng)化學(xué)報(bào),2015,41(2):240-260.

[5] Kreutzdelgado K,Murray J F,Rao B D,et al.Dictionary learning algorithms for sparse representation[J].Neural Computation,2003,15(2):349-396.

[6] Rubinstein R,Bruckstein A,Elad M.Dictionaries for sparse representation modeling[J].Proceedings of the IEEE,2010,98(6):1045-1057.

[7] Bahrampour S,Nasrabadi N,Ray A,et al.Multimodal task-driven dictionary learning for image classification[J].IEEE Transactions on Image Processing,2016,25(1):24-38.

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

[9] Protter M,Elad M.Image sequence denoising via sparse and redundant representations[J].IEEE Transactions on Image Processing,2009,18(1):27-35.

[10] Liu X,Zhai D,Zhao D,et al.Image super-resolution via hierarchical and collaborative sparse representation[C]//Data compression conference.[s.l.]:IEEE,2013:93-102.

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

[12] Ravishankar S,Bresler Y.MR image reconstruction from highly undersampled K-space data by dictionary learning[J].IEEE Transactions on Medical Imaging,2011,30(5):1028-1041.

[13] Bilgin A,Kim Y,Liu F,et al.Dictionary design for compressed sensing MRI[C]//ISMRM.[s.l.]:[s.n.],2010.

[14] Xu T T,Yang Z,Shao X.Adaptive compressed sensing of speech signal based on data-driven dictionary[C]//Conference on communications.[s.l.]:[s.n.],2009.

[15] 錢(qián) 陽(yáng).李 雷.一種基于新型KPCA算法的視頻壓縮感知算法[J].計(jì)算機(jī)技術(shù)與發(fā)展,2015,25(10):101-106.

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

[17] Donoho D L,Tsaig Y.Fast solution ofl1-norm minimization problems when the solution may be sparse[J].IEEE Transactions on Information Theory,2008,54(11):4789-4812.

[18] Liu Sheng,Gu Mingming.K-L transform in video compressed sensing[C]//Proceeding of the 32nd Chinese control conference.Xi’an,China:IEEE,2013:4528-4532.

[19] Zhang L,Zhang L,Mou X,et al.FSIM:a feature similarity index for image quality assessment[J].IEEE Transactions on Image Processing,2012,20(8):2378-2386.

An AdaptiveK-SVD Dictionary Learning Algorithm for Video Frame Sparse Reconstruction

QIAN Yang，LI Lei，YUAN An-an

(Center for Visual Cognitive Computation and Its Application,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

Finding sparsifying transforms is an important prerequisite of compressed sensing,which directly affects the reconstruction accuracy.It has practical significance to research the fast and efficient signal sparse representation method.Based on the traditionalK-SVD algorithm,an adaptiveK-SVD dictionary learning algorithm has been proposed to improve the speed and performance of dictionary training which is an iterative one that alternates between sparse coding and dictionary update steps.In the sparse coding stage,an adaptive sparsity constraint has been utilized to obtain sparser representation coefficient,which has further improved the efficiency of the dictionary update stage.And in the dictionary update stage,the dictionary atoms are updated column by column using the classicK-SVD dictionary update method.With the novel adaptive dictionaries as sparse representation for video frame compressed sensing,comparative experimental results demonstrate that the proposed adaptiveK-SVD dictionary learning algorithm achieves better performance than traditionalK-SVD algorithm in terms of running time.In addition,the new method has better signal sparse representation performance,and also can reduce the reconstruction error of compressed sensing.

K-SVD algorithm;adaptiveK-SVD algorithm;dictionary learning;sparse representation;compressed sensing

2016-05-29

2016-09-08 網(wǎng)絡(luò)出版時(shí)間：2017-04-28

國(guó)家自然科學(xué)基金資助項(xiàng)目(61070234，61071167，61373137，61501251)；江蘇省2015年度普通高校研究生科研創(chuàng)新計(jì)劃項(xiàng)目(KYZZ15_0235)；南京郵電大學(xué)引進(jìn)人才科研啟動(dòng)基金資助項(xiàng)目(NY214191)

錢(qián) 陽(yáng)(1991-)，女，碩士生，研究方向?yàn)榉蔷€性分析及應(yīng)用；李 雷，博士，教授，研究方向?yàn)橹悄苄盘?hào)處理與非線性科學(xué)及其在通信中的應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.016.html

TP301.6

A

1673-629X(2017)06-0036-05

10.3969/j.issn.1673-629X.2017.06.008