廣義貝葉斯字典學習K-SVD稀疏表示算法

周飛飛，李 雷

(南京郵電大學 理學院，江蘇 南京 210023)

廣義貝葉斯字典學習K-SVD稀疏表示算法

周飛飛，李 雷

(南京郵電大學 理學院，江蘇 南京 210023)

稀疏字典學習是一種功能強大的視頻圖像稀疏表示方法，在稀疏信號處理領域引起了廣泛關注。K-SVD算法在稀疏表示技術上取得了巨大成功，但遇到了字典原子未充分利用的問題，而稀疏貝葉斯字典學習(Sparse Bayesian Dictionary Learning,SBDL)算法存在稀疏表示后信號原子不稀疏和不收斂的缺點。廣義貝葉斯字典學習(Generalized Bayesian Dictionary Learning,GBDL) K-SVD算法提供了一種新型稀疏表示系數更新模式，使得過完備字典稀疏學習算法逐步收斂的同時訓練向量足夠稀疏。仿真結果表明，對有損像素和壓縮傳感這兩種視頻圖像幀進行稀疏化，GBDL K-SVD算法表示的視頻圖像幀的重構效果與SBDL K-SVD算法相比有明顯的提高。

稀疏貝葉斯學習；視頻圖像稀疏表示；字典學習；K-SVD算法

0 引 言

近年來，信號的過完備字典[1]稀疏表示已成為重要的科研議題并引起了廣泛的研究和討論。信息時代下的信息獲取和處理方法已然成為一個是重要的議題。現實世界中，信息采樣技術已成為數字信息和溝通的重要橋梁，高維數據的稀疏表示是機器學習和計算機視覺領域[2]所關注的一個熱門話題。它的基本設想是自然圖像本身是稀疏信號，也就是說，當使用一組過完備基來線性表示輸入信號時,獲得的對應系數被認為是輸入信號在某一稀疏條件下的良好逼近。這些稀疏表示方法在壓縮傳感、圖像去噪、視頻稀疏編碼、特征提取等重要應用中取得了巨大的成功。過完備特性意味著它所擁有的原子個數大于原子的維度，一組基信號的過完備集合的目標是用字典原子的稀疏組合線性地表示輸入信號。過完備字典的最大優點是在有噪環境或退化信號條件下的魯棒性，更重要的是，它在字典中引入更多種形式導致了輸入信號的各種不同稀疏表示。

過去幾年中，要提出最好的稀疏表示方式是一個被廣泛研究的困難議題[3]。K-SVD算法[4]是一種迭代算法，優化迭代步驟分為兩步：樣本稀疏編碼，這是基于固定的字典原子；其次是更新字典原子，使該字典更好地適應數據。稀疏貝葉斯字典學習(Sparse Bayesian Dictionary Learning,SBDL)算法是基于稀疏表示信號的最大后驗(Maximum A Posteriori,MAP)，它可以加入K-SVD算法的第一步來改善過完備學習詞典的自適應性。文中提出一種廣義稀疏貝葉斯字典學習(Generalized Bayesian Dictionary Learning，GBDL)算法來擴展和修改SBDL算法的缺陷，證明了改進算法的可行性和有效性。

1 稀疏貝葉斯字典學習K-SVD算法綜述

1.1 K-SVD算法

(1)

其中：‖?‖2為矩陣的2-范數；T0為稀疏表示系數向量中的非零元素的最大個數。

首先是K-SVD稀疏編碼階段，要解決問題(1)，產生一個隨機標準化列的初始字典D0，通過固定字典不變而產生稀疏矩陣X。也就是找出每個訓練信號yi對應于當前字典D的稀疏表示xi。所選擇的稀疏編碼算法必須限制非零元素的最大數量的解決方案，因此通常使用OMP算法[6]來得到稀疏表示矩陣X。

(2)

(3)

1.2 SBDL算法

SBDL算法是以最大后驗概率為基礎的算法，被用于稀疏基恢復。稀疏貝葉斯模型是通過一種特定的先驗參數來優選稀疏系數組合的貝葉斯處理過程。基于高斯似然模型[7]的稀疏貝葉斯字典學習方式表示為：

(4)

目標是最大化方程(4)中的向量x和常量σ2的似然估計。為了避免模型中與訓練樣本數量相等的參數數量造成嚴重的匹配問題，添加一個滿足先驗概率分布的參數，得到的滿足零均值高斯分布的向量x的先驗分布為：

(5)

其中，α=(α0,α1,…,αK)是一個由K個超參數組成的向量。

假設噪聲參數σ2和超參數向量α滿足Gamma先驗概率分布，可以得到方程(6)中向量x的后驗概率：

(6)

(7)

2 廣義貝葉斯字典學習K-SVD算法(GBDL K-SVD)

(8)

相似地，對于σ2的更新規則可以被如方程(9)簡單地合成表示為：

(9)

(10)

因此明顯知道x所對應的α的稀疏概況和觀察到所有的x都是可行的，并且如果y是D的跨度且所有的α被初始化為非零值，這將永遠是可行的。

那么，GBDLK-SVD算法關鍵步驟如下所述：

步驟2(初始化)：過完備字典矩陣D(0)∈Rn×K，先驗估計噪聲方差σ2，超參數向量α=(α0,α1,…,αK)，并設置J=0和S=0。

步驟3(主程序)：執行J=J+1，重復如下步驟直到滿足收斂或停止準則J≥Jmax：

1)執行S=S+1，重復如下步驟直到滿足停止準則S≥Smax：

(3)更新噪聲方差和超參數：

2)如果‖xi‖>T0，繼續用OMP算法來優化向量x，直到滿足‖xi‖≤T0。

3)更新字典，更新D(J-1)中k=1,2,…,K的每一列。

3 實驗仿真和分析

3.1 字典學習結果對比分析

文中仿真實驗使用由一組圖像幀組成的視頻序列作為樣本，從由51個Y幀組成的視頻信號中提取出大小為176×144的一組圖像幀[10]。為提高視頻圖像幀的稀疏度，采用重疊塊滑動窗口的塊算法來獲得分塊圖像。從圖像幀獲得多個8×8大小的重疊塊，并將每個依次重新排列成維數是64的向量，最后以這些向量為列構成64×23 153大小的矩陣。選擇過完備字典的大小為64×256，設定SBDL算法和GBDL算法的Smax=10,Jmax=10。經過視頻序列分解和分塊圖像處理后，分別用SBDLK-SVD算法和GBDLK-SVD算法對圖像幀進行稀疏編碼，獲得的基于圖像塊訓練字典的結果如圖1所示。

從圖1可以看到，通過仿真實驗，由SBDLK-SVD稀疏編碼訓練后的塊信號，雖然訓練信號的每一塊的特點大致能夠表現出來，但圖像幀的訓練特征不明顯。然而，通過GBDLK-SVD算法稀疏編碼后，被訓練的標準信號的特征紋理較前一種字典訓練后的特征更加突出，紋理更加清晰。因此，使用GBDLK-SVD過完備字典訓練圖像幀信號更具有前瞻性和有效性。

圖1 算法訓練結果

3.2 稀疏表示信號的重構性能對比分析

根據實際經驗，視頻經過媒介傳輸，在解碼器端解碼后會產生不同程度的失真。為了使仿真實驗符合實際情況，隨機地從視頻序列中選擇一個圖像幀。首先，從圖像幀中損失不同數量的像素，而后分別在SBDLK-SVD算法和GBDLK-SVD算法這兩種過完備稀疏字典學習算法的訓練下，重構出非損失像素的圖像幀。為直觀地比較不同學習字典的效果，對損失像素范圍在10%～90%的圖像幀進行重構，得到的對比結果如圖2所示。

圖2 過完備稀疏字典對不同程度有損

從圖2可以看到：若圖像幀有損像素比例是10%，經兩種不同稀疏字典稀疏表示后重構出的圖像幀的峰值信噪比(PSNR)可以上升到35dB左右。損失的像素占原像素的比率越低，過完備字典稀疏表示后的重構圖像的PSNR值都相對較高。但隨著損失像素的比例相對增加，獲得的PSNR值近似線性下降。通過GBDLK-SVD算法獲得的PSNR值總是高于SBDLK-SVD算法獲得的PSNR值。因此改進后的過完備字典學習算法比原始的稀疏表示性能強，這是由于改進算法稀疏編碼步驟中新更新模式考慮了EM算法最大化后驗概率。因此通過GBDLK-SVD算法獲得的信號稀疏表示來處理損失像素的圖像幀具有更好的性能。

壓縮感知[11-12]是近年來新興的技術并逐漸成熟，它主要包含信號的采樣稀疏、壓縮測量和重構三個主要步驟。采樣稀疏也就是常說的稀疏編碼，它在壓縮感知技術中起著舉足輕重的作用。在稀疏編碼步驟中，選擇一個合適的稀疏變換基或矩陣Ψ，或者選擇一種過完備字典稀疏學習來獲得信號的稀疏表示系數，再通過對稀疏系數的壓縮測量，獲得一個低維的向量。信號通過傳輸媒介后，在解碼器端獲得壓縮后的信號。為了獲得原始信號的逼近值并重構出圖像幀，通常情況下采用貪婪迭代算法重建圖像幀，如：正交匹配追蹤(OMP)[8]、分段正交匹配追蹤(StOMP)[13]和稀疏度自適應匹配追蹤(SAMP)[14]。

為了比較稀疏表示算法的性能，設置了從0.3到0.7范圍的不同采樣率，對比結果見圖3。其中，m表示圖像矩陣列向量的維數，采樣率表示獲得的信號數量占原始圖像幀數量的比率。

圖3 過完備稀疏字典對基于壓縮感知

從圖3可以看出，當采樣率較低時，經兩種算法稀疏表示后的重構圖像幀的PSNR值相對較低，但隨著采樣率增加，PSNR值也明顯提高。通過GBDLK-SVD算法獲得的PSNR總是高于SBDLK-SVD算法獲得的PSNR。

所以改進后的算法具有更強的重構性能，這很大程度上取決于它的稀疏表示系數在新型更新模式中使得學習算法逐漸收斂。

4 結束語

文中通過深入研究過完備稀疏字典學習的稀疏表示方法，提出了GBDLK-SVD算法。對稀疏編碼步驟做出改進，改進協方差矩陣的計算和稀疏向量的估計方式，進而改進了常量σ2和γ的更新模式，提高了重構精度，加快了收斂速度。此外，仿真實驗表明，在有損像素的圖像幀和基于壓縮傳感的圖像幀兩種情況下，視頻圖像幀通過GBDLK-SVD算法稀疏表示后的重構效率高于SBDLK-SVD稀疏字典學習算法。總而言之，改進的過完備字典學習始于非稀疏表示信號，并通過迭代過程逐步收斂到一個稀疏表示系數。實驗結果說明了提出算法的正確性并證實了其有效性。

[1]DelgadoKK,MurrayJF,RaoBD.Dictionarylearningalgorithmsforsparserepresentation[J].NeuralComputation,2003,15(2):349-396.

[2]MairalJ,BachF,PonceJ,etal.Onlinelearningformatrixfactorizationandsparsecoding[J].JournalofMachineLearningResearch,2010,11:19-60.

[3]SongXN,LiuL,YangXB,etal.AparameterizedfuzzyadaptiveK-SVDapproachforthemulti-classesstudyofpursuitalgorithms[J].Neurocomputing,2014,123:131-139.

[4]AharonM,EladM,BrucksteinA.K-SVD:analgorithmfordesigningovercompletedictionariesforsparserepresentation[J].IEEETransactionsonSignalProcessing,2006,54(11):4311-4322.

[5]TroppJA,WrightSJ.Computationalmethodsforsparsesolutionoflinearinverseproblems[J].ProceedingsoftheIEEE,2010,98(6):948-958.

[6]TroppJA,GilbertAG.Signalrecoveryfrompartialinformationviaorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666.

[7]BabacanSD,MolinaR,KatsaggelosAK.Bayesiancompressivesensingusinglaplacepriors[J].IEEETransactionsonImageProcessing,2010,19(1):53-63.

[8]ZhouFF,LiL.ModifiedsparseBayesiandictionarylearningK-SVDalgorithmforvideoimagesparserepresentation[J].JournalofComputationalInformationSystems,2015,11(12):4567-4580.

[9]WipfDP,RaoBD.SparseBayesianlearningforbasisselection[J].IEEETransactionsonSignalProcessing,2004,52(8):2153-2164.

[10]SunYP,XuM,TaoXM,etal.Onlinedictionarylearningbasedintra-framevideocoding[J].WirelessPersonalCommunications,2014,74:1281-1295.

[11]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(5):1289-1306.

[12]ZhouFF,LiL.ResearchonclippingthresholdSAMPalgorithmbasedonhighfrequencysub-bandwavelettransform[J].ComputerTechnologyandDevelopment,2014,24(5):83-86.

[13]DonohoDL,TsaigY,DroriI.Sparsesolutionofunderdeterminedsystemsoflinearequationsbystagewiseorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2012,58(2):1094-1121.

[14]ThongT,GanL,NguyenN,etal.Sparsityadaptivematchingpursuitalgorithmforpracticalcompressedsensing[C]//ProcofAsilomarconferenceonsignal,systemsandcomputers.PacificGrove,California:[s.n.],2008.

K-SVD Sparse Representation Algorithm of Generalized Bayesian Dictionary Learning

ZHOU Fei-fei，LI Lei

(College of Science，Nanjing University of Posts and Telecommunications，Nanjing 210023，China)

Sparse dictionary learning is a powerful sparse representation method for video image which has attracted much attention in exploiting sparsity in signal processing.The K-SVD algorithm has achieved success in sparse representation but suffers from the problem of underutilization of dictionary atoms.Sparse Bayesian Dictionary Learning (SBDL) algorithm exists the drawbacks of non-sparse representation and convergence of signal atoms.But Generalized Bayesian Dictionary Learning (GBDL) K-SVD algorithm offers a novel update mode of sparse represent coefficient to make the learning algorithm gradually convergent and give the training vectors a perfect opportunity to become extremely sparsity over the overcomplete dictionary.The simulation experiment of two cases where image frames with missing pixels and ones based on compressive sensing shows that the efficiency of sparsely represent by GBDL K-SVD algorithm is better than SBDL K-SVD algorithm.

sparse Bayesian learning;video image sparse representation;dictionary learning;K-SVD algorithm

2015-07-25

2015-11-05

時間：2016-05-05

國家自然科學基金資助項目(61071167,61373137)；江蘇省研究生科研創新計劃項目(KYZZ_0233)

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

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0817.050.html

TP301.6

A

1673-629X(2016)05-0071-05

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