基于過(guò)完備字典的視頻壓縮采集算法

段宏偉

(山西職業(yè)技術(shù)學(xué)院 數(shù)控系， 山西 太原 030006)

視頻圖像具有可壓縮性和稀疏性， 它們可以在特定的正交基或框架下稀疏表示. 然而， 傳統(tǒng)的成像系統(tǒng)是對(duì)視頻圖像的所有數(shù)據(jù)進(jìn)行采集， 然后再對(duì)其進(jìn)行壓縮. 在這個(gè)過(guò)程中， 視頻圖像的稀疏性被忽略， 浪費(fèi)了有限而寶貴的資源. 研究表明， 壓縮感知(Compressive Sensing, CS)[1]理論具有開(kāi)發(fā)視頻圖像方面的潛力， 該技術(shù)將視頻信號(hào)的采集和壓縮結(jié)合在一起， 并可直接獲取壓縮過(guò)的信號(hào). 與傳統(tǒng)的成像系統(tǒng)不同， 該技術(shù)致力于最小化信號(hào)冗余的采集， 從而提高了采樣效率.

壓縮感知已成功應(yīng)用于視頻采集中. 文獻(xiàn)[2]提出了將2D小波變換CS應(yīng)用到視頻中的每一幀， 并提出了逐幀壓縮采樣的方法， 視頻中的每一幀被視為獨(dú)立的圖像. 這種方法利用視頻幀的空域冗余， 提高了視頻的采樣效率， 然而， 其未涉及視頻的空域冗余. 為了解決這個(gè)問(wèn)題， 文獻(xiàn)[3]提出了幀間差異壓縮感知的方法， 對(duì)相鄰幀之間的差異而非原始幀進(jìn)行測(cè)量. 這種方法的缺點(diǎn)是， 所有的幀之間存在依賴性， 如果某一幀沒(méi)有得到很好的恢復(fù)， 重建誤差會(huì)擴(kuò)散到后面的視頻幀， 甚至整個(gè)視頻.

視頻壓縮感知的另一種方法為三維變換壓縮感知， 將整個(gè)視頻看作一個(gè)數(shù)據(jù)塊， 對(duì)整個(gè)視頻同時(shí)進(jìn)行處理[2]. 這種方法可以有效利用視頻中的空域和時(shí)域稀疏性. 為了獲得更高的稀疏性， 文獻(xiàn)[4]中提出了使用Li-MAT[5]作為稀疏基的視頻壓縮感知方法， 該算法利用視頻相鄰幀之間的運(yùn)動(dòng)補(bǔ)償， 獲得比其他常規(guī)的三維變換更高的稀疏度. 但是這種方法需要在多個(gè)尺度上計(jì)算相鄰幀的運(yùn)動(dòng)矢量， 計(jì)算復(fù)雜度大. 為了利用有限的測(cè)量值進(jìn)行自適應(yīng)采樣， 一種基于視頻塊的采樣框架在文獻(xiàn)[6-7]中被提出， 首先每一幀被劃分成不重疊的小塊， 然后根據(jù)小塊的時(shí)域變化對(duì)其進(jìn)行分類. 然而實(shí)施小塊分類和不同的采樣策略增加了算法的時(shí)間成本， 而且該算法對(duì)分類器的設(shè)計(jì)過(guò)于敏感.

由于視頻在不同稀疏基上的稀疏性并不相同， 本文設(shè)計(jì)了一個(gè)新的基于過(guò)完備字典的視頻壓縮感知系統(tǒng). 在這個(gè)框架下， 視頻同樣被分為時(shí)間-空間的小塊， 為每個(gè)小塊采集相同數(shù)量的測(cè)量值. 為了視頻的有效重構(gòu)， 系統(tǒng)使用K-SVD方法為視頻塊訓(xùn)練了一種嚴(yán)格稀疏的過(guò)完備字典， 這樣視頻塊的時(shí)間-空間稀疏性可以得到最大化的利用， 從而保證視頻的高質(zhì)量恢復(fù).

1 壓縮感知

假設(shè)x∈RN是一個(gè)可以在某個(gè)正交基或框架上稀疏表示的信號(hào)，x=Ψα，α∈RN只有K?N個(gè)非零項(xiàng)， 則x是一個(gè)在稀疏基Ψ上K稀疏的信號(hào). 壓縮感知允許對(duì)信號(hào)進(jìn)行非相干測(cè)量，y=Φx在隨機(jī)投影域?qū)π盘?hào)進(jìn)行采集. 根據(jù)壓縮感知理論， 為了從采樣值y重建原始信號(hào)x， 需要對(duì)下列問(wèn)題進(jìn)行求解，

min‖α‖1s.t. ‖s-Φx‖2≤ε,(1)

式中： ‖·‖1表示l1范數(shù)；ε為一個(gè)正常數(shù). 各國(guó)研究者已經(jīng)提過(guò)很多不同的算法來(lái)解決這個(gè)問(wèn)題， 如正交匹配追蹤(OMP)[8]， 分段正交匹配追蹤(StOMP)[9]和基追蹤(BP)[10]等. 此外， 對(duì)于圖像來(lái)講， 另一種還原方法是最小變分法. 設(shè)x為一個(gè)向量化后的圖像， 那么重構(gòu)問(wèn)題可以寫(xiě)為

(2)

其中，

‖x‖TV=

它可以看做圖像l1范數(shù)的梯度.

2 視頻壓縮感知和過(guò)完備字典學(xué)習(xí)

不同于傳統(tǒng)的視頻采集系統(tǒng)， 本系統(tǒng)將視頻采樣和壓縮結(jié)合在一起， 可以同時(shí)有效利用視頻在空間和時(shí)間上的稀疏性. 此外， 所設(shè)計(jì)的算法還將視頻場(chǎng)景內(nèi)容的多樣性和視頻不同部分之間的差異性應(yīng)用于過(guò)完備字典的自適應(yīng)學(xué)習(xí)中.

2.1 框架

如圖 1 所示， 視頻中的每一幀圖像被分為相同大小的n×n個(gè)不重疊的小塊， 然后使用矩陣Φi對(duì)各個(gè)小塊進(jìn)行測(cè)量.

圖 1 基于過(guò)完備字典的視頻壓縮感知結(jié)構(gòu)圖Fig.1 Block diagram of video compressive based on over-completed dictionary

式中：Φ為測(cè)量矩陣.

2.2 視頻塊的過(guò)完備字典學(xué)習(xí)算法

本節(jié)討論基于稀疏性約束的視頻塊過(guò)完備字典學(xué)習(xí)算法. 為了保證字典的通用性， 盡量使用具有復(fù)雜紋理和空域變化的視頻塊來(lái)對(duì)字典進(jìn)行初始化， 本文選擇了各種視頻， 如運(yùn)動(dòng)的汽車， 流水， 騎馬和其它不同的紋理變化. 在本文所設(shè)計(jì)的字典中， 任何視頻的時(shí)間-空間小塊都可以被表示為有限個(gè)字典元素的線性和.

圖 2 部分過(guò)完備稀疏字典Fig.2 Part of over-completed dictionary

在字典訓(xùn)練的初始階段， 每個(gè)視頻塊都選自具有相同幀率的不同視頻， 每個(gè)視頻塊被裁剪為大小8×8×8. 為了保證視頻字典的多樣性， 將每個(gè)視頻字典原子進(jìn)行8個(gè)方向的旋轉(zhuǎn)并進(jìn)行前向和后向的播放. 總共選擇了100 000個(gè)原子作為初始字典并使用K-SVD訓(xùn)練方法[11]對(duì)字典進(jìn)行訓(xùn)練， 圖 2 展示了部分字典. 對(duì)于一個(gè)視頻塊E， 它將可以被表示為

E=Dα,(4)

式中：D為訓(xùn)練好的字典. 式(1)中所示的重構(gòu)問(wèn)題將變?yōu)?/p>

(5)

3 實(shí)驗(yàn)結(jié)果

為了測(cè)試系統(tǒng)的適應(yīng)性， 實(shí)驗(yàn)在不同紋理復(fù)雜度和不同目標(biāo)運(yùn)動(dòng)的視頻上進(jìn)行. 為了方便， 所有實(shí)驗(yàn)中的視頻幀被裁剪為256×256， 它們被分割為8×8×8的時(shí)間-空間塊. 使用采樣比例來(lái)測(cè)量系統(tǒng)的有效性， 采樣比例為測(cè)量值數(shù)目和總像素?cái)?shù)目的比值. 實(shí)驗(yàn)對(duì)不同算法的視覺(jué)質(zhì)量和峰值信噪比進(jìn)行了比較， 每種算法都對(duì)相同的50個(gè)視頻進(jìn)行試驗(yàn)并計(jì)算出平均值. 對(duì)所有算法使用相同的采樣比例和壓縮感知重構(gòu)算法， 系統(tǒng)使用“l(fā)1-magic”[12]工具箱中的內(nèi)點(diǎn)法進(jìn)行重構(gòu).

3.1 視覺(jué)質(zhì)量比較

圖 3 所示為不同采樣比例下本文算法的重建結(jié)果. 很明顯， 本文所提方法在即使測(cè)量比例低至5%的情況下依然可以獲得令人滿意的結(jié)果. 在采樣比例逐漸提高的過(guò)程中， 重建結(jié)果獲得了質(zhì)量提升， 小塊之間的不兼容性逐漸減少， 到達(dá)25%采樣比例時(shí)幾乎所有的塊狀效應(yīng)都已經(jīng)消失. 幀內(nèi)部的紋理信息在低采樣率的情況下依然可以得到較好的恢復(fù).

圖 3 不同采樣比例下結(jié)果Fig.3 Visual comparison under different measurement ratio

圖 4 和圖 5 給出了在相同采樣比例下不同算法的重構(gòu)結(jié)果比較. 由于2.2節(jié)中所訓(xùn)練的字典可以使采集信號(hào)獲得更高的稀疏性， 在相同的采樣比例下， 本文算法可以獲得比其他現(xiàn)有算法更加優(yōu)秀的結(jié)果. 由圖4可見(jiàn)， 本文算法可以有效恢復(fù)出視頻的紋理和幀間的目標(biāo)運(yùn)動(dòng). 在采樣比例為5%時(shí)本文算法雖有塊狀效應(yīng)， 但基本輪廓和紋理信息可見(jiàn)， 其它算法很難辨別出恢復(fù)結(jié)果.

由圖5可見(jiàn)， 在采樣比例為25%時(shí)， 本文算法的結(jié)果基本為原圖， 而其它算法的輪廓較為模糊， 內(nèi)部紋理信息不如本文算法優(yōu)秀.

圖 4 采樣比例為5%時(shí)不同算法相同采樣比例下的結(jié)果Fig.4 Visual comparison for different methods when the measurement ratio is 5%

圖 5 采樣比例為25%時(shí)不同算法相同采樣比例下的結(jié)果Fig.5 Visual comparison for different methods when the measurement ratio is 25%

3.2 不同方法的峰值信噪比

本節(jié)比較了相同采樣比例下不同方法的峰值信噪比(PSNR). 使用了50個(gè)不同的視頻作為實(shí)驗(yàn)對(duì)象并求平均值. 如圖 6 所示， 本文算法達(dá)到了最好的PSNR， 尤其當(dāng)采樣率較低時(shí)， 由于采用稀疏基下的系數(shù)求解而后得到重構(gòu)視頻， 稀疏度的影響在此框架下非常重大.

三維視頻字典的效率和效果非常明顯， 遠(yuǎn)優(yōu)于其他常規(guī)的標(biāo)準(zhǔn)正交基或分析基. 使用相同的測(cè)量值， 本文算法可以獲得最少的誤差， 同時(shí)可以獲得最好的視覺(jué)質(zhì)量.

圖 6 不同算法相同采樣比例下的峰值信噪比比較Fig.6 PSNR of different methods under the same measurement ratio

4 結(jié) 論

本文提出了一種新的視頻壓縮感知系統(tǒng)， 該系統(tǒng)采用過(guò)完備字典作為稀疏基以獲得更高的稀疏度. 在此框架下， 視頻被分為不重疊的空間-時(shí)間小塊， 并對(duì)其進(jìn)行分別測(cè)量. 在重構(gòu)階段時(shí)間-空間小塊可以進(jìn)行聯(lián)合重構(gòu)， 實(shí)驗(yàn)表明重構(gòu)結(jié)果在高稀疏度的影響下更加優(yōu)化. 此外， 提出的視頻壓縮感知系統(tǒng)有效提高了視頻的采樣效率， 同時(shí)利用了視頻時(shí)間和空間上的冗余， 在采樣比例低至5%的情況下依然可以獲得了令人滿意的結(jié)果.

參考文獻(xiàn)：

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

[2] Wakin M, Laska J, Duarte M F, et al. Compressive imaging for video representation and coding[C]. Picture Coding Symp (PCS), Beijing, 2006: 716-731.

[3] Zheng J, Jacobs E L. Video compressive sensing using spatial domain sparsity[J]. Optical Engineering, 2010, 48(8): 1-10.

[4] Park J Y, Wakin M B. A multi-scale framework for compressive sensing of video[C]. Picture Coding Symp (PCS), Chicago, 2009: 1-4.

[5] Secker A, Taubman D. Lifting-based invertible motion adaptive transform framework for highly scalable video compression[J]. IEEE Transaction on Image Processing, 2003, 12(12): 1530-1542.

[6] Liu Z, Elezzabi A Y, Zhao H V, et al. Block-based adaptive compressed sensing for video[C]. IEEE International Conference on Image Processing (ICIP), HongKong, 2010: 133-142.

[7] Liu Z, Elezzabi A Y, Zhao H V, et al. Maximum frame rate video acquisition using adaptive compressed sensing[J]. IEEE Transaction on Circuits and Systems for Video Technology, 2011, 21(11): 1704-1718.

[8] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2008, 53(12): 4655-4666.

[9] Drori D D, Donoho D L, Tsaig Y， et al. Sparse solution of underdetermined linear equations by stage-wise orthogonal matching pursuit[C]. IEEE Transactions on Information Theory, 2012, 58: 1094-1121.

[10] Candes E, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[11] Aharon M, Elad M, Bruckstein A. K-SVD: an algorithm for designing over-complete dictionaries for sparse representation[J]. IEEE Transactions on Signal Processing, 2006, 54(11): 4311-4322.

[12] Candes E, Romberg J. l1-magic: recovery of sparse signals via convex programming[EB/OL]. http:∥users.ece.gatech.edu/ justin/l1magic, 2011-10-11.