廣義貝葉斯字典學(xué)習(xí)K-SVD稀疏表示算法

周飛飛，李 雷

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

廣義貝葉斯字典學(xué)習(xí)K-SVD稀疏表示算法

周飛飛，李 雷

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

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

稀疏貝葉斯學(xué)習(xí)；視頻圖像稀疏表示；字典學(xué)習(xí)；K-SVD算法

0 引 言

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

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

1 稀疏貝葉斯字典學(xué)習(xí)K-SVD算法綜述

1.1 K-SVD算法

(1)

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

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

(2)

(3)

1.2 SBDL算法

SBDL算法是以最大后驗概率為基礎(chǔ)的算法，被用于稀疏基恢復(fù)。稀疏貝葉斯模型是通過一種特定的先驗參數(shù)來優(yōu)選稀疏系數(shù)組合的貝葉斯處理過程?；诟咚顾迫荒Ｐ蚚7]的稀疏貝葉斯字典學(xué)習(xí)方式表示為：

(4)

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

(5)

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

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

(6)

(7)

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

(8)

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

(9)

(10)

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

那么，GBDLK-SVD算法關(guān)鍵步驟如下所述：

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

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

1)執(zhí)行S=S+1，重復(fù)如下步驟直到滿足停止準(zhǔn)則S≥Smax：

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

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

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

3 實驗仿真和分析

3.1 字典學(xué)習(xí)結(jié)果對比分析

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

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

圖1 算法訓(xùn)練結(jié)果

3.2 稀疏表示信號的重構(gòu)性能對比分析

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

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

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

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

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

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

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

所以改進(jìn)后的算法具有更強的重構(gòu)性能，這很大程度上取決于它的稀疏表示系數(shù)在新型更新模式中使得學(xué)習(xí)算法逐漸收斂。

4 結(jié)束語

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

[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

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

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

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