錢 陽，李 雷，袁安安

(南京郵電大學 視覺認知計算與應用研究中心，江蘇 南京 210023)

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

錢 陽，李 雷，袁安安

(南京郵電大學 視覺認知計算與應用研究中心，江蘇 南京 210023)

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

K-SVD算法；自適應K-SVD算法；字典學習；稀疏表示；壓縮感知

0 引 言

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

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

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

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

1 預備知識

1.1 壓縮感知理論基礎

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

y=Φx=ΦΨΘ

(1)

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

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

(2)

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

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

1.2 字典學習方法

基于過完備字典的稀疏表示是一種全新的信號表示理論。近年來，以設計簡單、高效、通用性強的字典為目標的字典學習方法吸引著學者們的廣泛關(guān)注，其中最受歡迎的是由Michal Aharon、Michael Elad提出的K-SVD字典學習算法。

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

(3)

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

算法1：K-SVD算法。

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

While停止迭代條件不滿足；

1)稀疏編碼階段。

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

(4)

2)字典更新階段。

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

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

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

2 自適應K-SVD算法

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

2.1 稀疏編碼階段

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

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

(5)

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

(6)

當μ(D)值很大時，字典原子間相似程度很強，反之很弱。

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

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

(7)

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

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

(2)式(3)中的l0問題也可以等價為l1問題；

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

由定理1可見，所定義的Tj能夠保證稀疏信號精確恢復，是合理可行的。

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

(8)

該問題可以通過任意一種追蹤算法(如BP、OMP)進行求解。

2.2 字典更新階段

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

(9)

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

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

squ=fr(x,y)

(10)

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

(11)

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

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

初始化：隨機初始歸一化字典矩陣D(0)∈Rn×K，通過式(5)獲得初始化稀疏約束上限T0。

forj=1,2,…,P

1)稀疏編碼階段。

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

2)字典更新階段。

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

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

獲得更新后的字典Dj。

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

end

fort=1,2,…,WL/n

end

3 仿真實驗及分析

采用格式為CIF的標準視頻序列Foreman進行實驗仿真，隨機選取Foreman的第1、6、10、15、23幀作為測試樣本集，如圖1所示。

圖1 測試圖像集

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

3.1 稀疏基選擇的視覺效果

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

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

圖2 兩種字典學習算法訓練出的字典

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

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

為了評估各算法的重構(gòu)性能，除了選用PSNR作為評價標準外，近年來相關(guān)學者提出的FSIM[19]可以用來衡量重構(gòu)圖像的視覺效果。FSIM值越高，則重構(gòu)圖像的視覺效果越好。

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

從圖3(a)可以看出，所提Adaptive KSVD-CS算法的運行時間遠遠低于KSVD-CS算法，這是因為所提的自適應K-SVD字典學習方法在稀疏編碼階段自適應選擇稀疏度，加快了字典的訓練速度。

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

4 結(jié)束語

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

為提高字典學習的收斂速度與性能，提出了一種自適應K-SVD字典學習算法。該算法在稀疏編碼階段根據(jù)當前字典自適應地調(diào)整稀疏度，更新字典則使用經(jīng)典K-SVD的字典更新方式，稀疏編碼與字典更新兩步迭代學習得到字典，并將所學習到的字典用于視頻幀的稀疏表示。仿真對比實驗表明，所提算法提升了字典訓練速度，提高了重構(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] 練秋生,石保順,陳書貞.字典學習模型、算法及其應用研究進展[J].自動化學報,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] 錢 陽.李 雷.一種基于新型KPCA算法的視頻壓縮感知算法[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)絡出版時間：2017-04-28

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

錢 陽(1991-)，女，碩士生，研究方向為非線性分析及應用；李 雷，博士，教授，研究方向為智能信號處理與非線性科學及其在通信中的應用。

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