李昂，馬強(qiáng)，岑翼剛，趙瑞珍，岑麗輝

(1.北京交通大學(xué) 信息科學(xué)研究所，北京100044;2.宜昌供電公司 電能計量中心，湖北 宜昌443000;3.中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南長沙410083)

隨著社會的進(jìn)步和通信技術(shù)的不斷發(fā)展，人與人之間的視頻傳輸變得越來越頻繁，這就對通信過程中的數(shù)據(jù)存儲和傳輸設(shè)備提出了更高的要求.傳統(tǒng)的奈奎斯特采樣定理指出，信號的采樣頻率必須大于或等于信號帶寬的2倍，才能準(zhǔn)確地恢復(fù)和重構(gòu)出原信號.顯然，對于視頻信號的傳輸，奈奎斯特采樣定理具有很大的局限性.

近年來，由 Donoho、Candes[1]及 Tao 等[2]提出了一種新的信息獲取理論稱作壓縮感知(compressed sensing或 compressive sampling，CS).這一理論的著眼點放在了信號的稀疏性，即信號在合適的稀疏基下可以變換到相應(yīng)的稀疏域，從而呈現(xiàn)出信號的稀疏性.另外，對于如何將信號在稀疏域進(jìn)行壓縮感知處理，很多算法被提出，例如利用峰值變換[3]、利用單層小波變換[4]等.

在處理監(jiān)控視頻信號時，還要充分考慮到視頻中幀與幀之間的相關(guān)性.對相鄰2幀做差，得到的差值圖像本身就具有一定的稀疏性.另外，在幀圖像重構(gòu)的過程中，可以通過參考幀圖像對當(dāng)前幀圖像進(jìn)行運動估計和運動補(bǔ)償，從而進(jìn)一步提高視頻重構(gòu)質(zhì)量.

1 壓縮感知理論

考慮一個可壓縮實值信號f(f∈RN×1)，信號長度為N，則該信號可以由一組正交基展開Ψ=ψ1ψ2… ψN[]，如式(1):

式(1)為正交變換的反變換，正變換為α=ΨHf.其中，ΨΨH=ΨHΨ=Ι，Ψ∈CN×N，Ι為單位陣，α 是信號f在Ψ下的稀疏表示.若式(1)中的α只有K個非零元素(N?K)，其余的元素為0或者接近于0，則認(rèn)為該信號是稀疏的.

信號可稀疏表示是壓縮感知的先驗條件.在已知信號是可壓縮的前提下，壓縮感知過程可分為如下2步[5]:

1)設(shè)計一個大小為M×N( M?N)的測量矩陣Φ對稀疏信號進(jìn)行觀測，得到M維的測量向量.

測量值y是一個M維向量，這樣使測量對象從N維降為M維.觀測過程是非自適應(yīng)的，即測量矩陣的選擇不依賴于信號f.測量矩陣的設(shè)計要求信號從f轉(zhuǎn)換為y的過程不會破壞原始信號的信息，否則，重構(gòu)是不可能的[6].由于信號f是可稀疏表示的，測量過程可以表示為

式中:Θ是一個M×N矩陣.若Φ滿足有限等距性質(zhì)(restricted isometry property，RIP)，即對于任意 K-稀疏信號f和常數(shù)δk∈(0，1)，矩陣Φ滿足:

則K個系數(shù)能夠從M個測量值中準(zhǔn)確地被重構(gòu).RIP性質(zhì)的等價條件是測量矩陣Φ和稀疏基Ψ不相關(guān).

2)由M維的測量向量重構(gòu)信號.

當(dāng)矩陣Φ滿足RIP準(zhǔn)則時，重構(gòu)K-稀疏系數(shù)α最直接的方法是通過在l0范數(shù)下求解式(2)的最優(yōu)化問題:

從而得到稀疏系數(shù)α的估計.由于式(3)求解時，方程個數(shù)遠(yuǎn)小于未知數(shù)的個數(shù)，即l0范數(shù)下的求解是NP-Hard問題.Donoho等[7]指出，當(dāng) Φ 和 Ψ 不相關(guān)時，求解一個更加簡單的l1范數(shù)優(yōu)化問題會產(chǎn)生相同的解.即l0極小化問題可轉(zhuǎn)化為l1范數(shù)下的最小化問題:

通過求解式(4)，可以得到稀疏域重建的結(jié)果.求解l1范數(shù)下極小化問題常用算法有3類:貪婪追蹤法、凸松弛法和組合算法，例如匹配追蹤法(matching pursuit，MP)[8]、正交匹配追蹤法(orthogonal matching pursuit，OMP)[9]、梯度投影法 (gradient projection，GP)[10]、鏈?zhǔn)阶粉櫡╗11]等.

2 基于壓縮感知的監(jiān)控視頻恢復(fù)

監(jiān)控視頻的特點是背景基本不變，視頻圖像數(shù)據(jù)有著極大的相關(guān)性，也就是有大量的冗余信息.對于監(jiān)控視頻，背景不是重要信息，壓縮感知主要是針對監(jiān)控視頻中的運動物體進(jìn)行處理的.

對于YUV視頻數(shù)據(jù)來說，本文研究的是對其Y分量所構(gòu)成的部分進(jìn)行處理.首先，將視頻序列進(jìn)行分組，每組包含相同的幀數(shù).為了達(dá)到更好的恢復(fù)效果，在關(guān)鍵幀的選取上，選取一組幀圖像(奇數(shù)個)的中間幀作為關(guān)鍵幀.幀與幀之間差值的獲取比較簡單，即后一幀減去前一幀的結(jié)果作為差分的結(jié)果.對差值圖像運用壓縮感知技術(shù)進(jìn)行采樣，而關(guān)鍵幀不進(jìn)行壓縮感知處理，完全保留所有采樣點.另外也可先對幀圖像先感知，再做差分，此時則應(yīng)該對2幀圖像采用相同的測量矩陣，即應(yīng)有式(5)成立:

式中:f1和f2是相鄰的2幀.由式(5)可知，對2幀圖像的差值采樣等效于分別對2幀圖像先采樣再進(jìn)行差分[12].

由于監(jiān)控視頻中每一幀圖像的背景總是基本不變的，當(dāng)場景中的物體運動比較緩慢或者運動物體尺寸比較小時，幀與幀的差值在空域就具備稀疏的性質(zhì).但當(dāng)場景中物體運動比較迅速或者運動的物體尺寸比較大時，空域的稀疏性將急劇下降.因此，為了使差值都具有稀疏的性質(zhì)，本論文對差值進(jìn)行進(jìn)一步處理，即利用二維小波變換，將差值圖像投影到比較稀疏的域.

以視頻序列的第1組為例進(jìn)行說明，該組由5幀圖像組成，第3幀為關(guān)鍵幀.視頻的采樣過程如圖1所示.

圖1 視頻采樣過程Fig.1 The sampling process of surveillance video

獲得采樣值以后，接下來就根據(jù)采樣值重構(gòu)原來的視頻序列.首先，根據(jù)最小l1范數(shù)優(yōu)化方法重構(gòu)出差值圖像，本文采用正交匹配追蹤算.然后，用關(guān)鍵幀加上或減去差值圖像獲得與其相鄰的2幀圖像的重構(gòu)，之后，這2幀再做參考幀，和差值圖像做加法或減法得到下一幀或上一幀的重構(gòu)圖像.視頻的恢復(fù)過程如圖2所示.

圖2 視頻恢復(fù)過程Fig.2 The reconstruction of surveillance video

在恢復(fù)視頻序列的過程中，應(yīng)該充分利用視頻序列中幀與幀之間的相關(guān)性和連續(xù)性，把運動估計和運動補(bǔ)償技術(shù)添加到視頻序列的恢復(fù)過程中來.運動估計可以用來估計物體的位移，從而得到運動矢量.運動補(bǔ)償可以根據(jù)得到的運動矢量，對參考幀中由于運動而產(chǎn)生的位移進(jìn)行調(diào)整，從而得到盡可能接近于當(dāng)前幀的預(yù)測幀.

根據(jù)運動估計和運動補(bǔ)償?shù)奶攸c和作用，本文將其應(yīng)用到視頻序列中非關(guān)鍵幀的重構(gòu)過程中，采用的是全搜索算法.該算法分為2步:1)在搜索窗口內(nèi)，按從左至右、從上到下的順序逐個像素進(jìn)行搜索，分別計算各個像素的MAD值，直到遍歷搜索窗口內(nèi)所有的點.2)在所有記錄下來的MAD值中尋找到MAD值最小的點，即最小塊匹配誤差點，該點對應(yīng)的位置即為所求的運動矢量.這里，MAD是指平均絕對誤差，按照式(6)進(jìn)行計算:

式中:(i，j)是位移矢量，fk和fk－1分別為當(dāng)前幀和參考幀的灰度值，M×N為宏塊的大小.

基于全搜索算法，運動估計和運動補(bǔ)償?shù)乃惴ㄔ斫榻B如下:先確定當(dāng)前幀中的待匹配塊，設(shè)其左上角的坐標(biāo)為(p，q)，然后在參考幀中對應(yīng)的搜索窗口內(nèi)找到與待匹配塊MAD值最小的塊，即預(yù)測塊，設(shè)其左上角坐標(biāo)為(u，v)，那么所求的運動矢量即為(u－p，v－q)，這就是運動估計的過程.在運動補(bǔ)償過程中，參考幀中的預(yù)測塊根據(jù)運動矢量平移到當(dāng)前幀中待匹配塊的位置.如此反復(fù)，當(dāng)參考幀中所有預(yù)測塊都按照相應(yīng)的運動矢量平移到了相應(yīng)的待匹配塊的位置時，就完成了對當(dāng)前幀的運動補(bǔ)償.

首先將關(guān)鍵幀作為參考幀，關(guān)鍵幀的前一幀的重構(gòu)圖像或后一幀的重構(gòu)圖像作為當(dāng)前幀，進(jìn)行運動估計得到運動矢量，再根據(jù)運動矢量進(jìn)行運動補(bǔ)償，得到前一幀或后一幀的優(yōu)化重構(gòu)圖像.再將得到的優(yōu)化圖像作為參考幀，其前一幀的重構(gòu)圖像或后一幀的重構(gòu)圖像作為當(dāng)前幀，重復(fù)前面的運動估計和運動補(bǔ)償?shù)倪^程，從而得到對應(yīng)幀的優(yōu)化重構(gòu)圖像.以此類推，完成整個視頻序列的每一組中的非關(guān)鍵幀的運動估計和運動補(bǔ)償，從而恢復(fù)出整個視頻序列.整個過程如圖3所示.

圖3 視頻序列的運動補(bǔ)償Fig.3 The motion compensation of surveillance video

對于一個實際的處理系統(tǒng)來講，上述內(nèi)容分別對應(yīng)編碼端和解碼端的處理過程.編碼端:1)將視頻序列進(jìn)行分組，每組包含相同的幀數(shù);2)在關(guān)鍵幀的選取上，選取一組幀圖像(奇數(shù)個)的中間幀作為關(guān)鍵幀;3)用傳統(tǒng)的方法對關(guān)鍵幀進(jìn)行熵編碼;4)每組后一幀減去前一幀獲得差值圖，并將差值圖進(jìn)行小波變換;5)在小波域?qū)Σ钪颠M(jìn)行壓縮感知，獲得差值的采樣值，并進(jìn)行熵編碼.解碼端:1)通過熵解碼獲得關(guān)鍵幀和差值的采樣值;2)將差值的采樣值利用OMP算法進(jìn)行重構(gòu)，并進(jìn)行小波反變換，獲得重構(gòu)的差值圖像;3)由關(guān)鍵幀和差值圖像獲得該組非關(guān)鍵幀的重構(gòu)圖像;4)通過運動估計和運動補(bǔ)償對該組非關(guān)鍵幀進(jìn)行優(yōu)化.

3 實驗仿真

實驗是建立在MATLAB運行環(huán)境下實現(xiàn)的.實驗中處理的視頻對象為監(jiān)控視頻hall(QCIF格式)，共有300幀圖像，每幀圖像的大小為144×176，播放時間為10 s.采取服從N(0，1)正態(tài)分布的隨機(jī)矩陣作為測量矩陣，用sym8小波函數(shù)對差值圖像進(jìn)行小波變換，分解層數(shù)為4層.將視頻序列分成60組，每組5幀，并且中間幀作為關(guān)鍵幀.

每幅差值圖像的采樣點數(shù)為44×176時，在未進(jìn)行運動估計和運動補(bǔ)償?shù)那闆r下，重構(gòu)序列的平均峰值信噪比為40.263 4 dB.重構(gòu)視頻序列如圖4所示.

當(dāng)對圖4的結(jié)果進(jìn)行運動估計和運動補(bǔ)償之后，重構(gòu)序列的平均峰值信噪比可以提高到42.178 4 dB.得到的重構(gòu)視頻序列，如圖5所示.

圖4 未進(jìn)行運動補(bǔ)償?shù)闹貥?gòu)視頻序列Fig.4 The reconstructed surveillance video without motion compensation

圖5 已進(jìn)行運動補(bǔ)償?shù)闹貥?gòu)視頻序列Fig.5 The reconstructed surveillance video with motion compensation

由圖4～5可以得出，在未進(jìn)行運動估計和運動補(bǔ)償?shù)那闆r下，視頻序列雖然可以重建出來，但背景和運動的人物還是存在比較明顯的模糊現(xiàn)象.經(jīng)過運動補(bǔ)償以后，這種模糊現(xiàn)象明顯降低，反映到數(shù)據(jù)上就是重構(gòu)視頻序列平均的峰值信噪比增加.也就是說，運動補(bǔ)償可以減少較小的采樣率給重構(gòu)視頻序列帶來的不利影響，可以實現(xiàn)對重構(gòu)視頻序列的優(yōu)化.

2種情況下，重構(gòu)圖像與原來圖像的平均峰值信噪比(PSNR)隨采樣點數(shù)的變化情況如圖6所示.

圖6 平均峰值信噪比隨采樣點數(shù)的變化情況Fig.6 The change of the average PSNR along with the number of sampling

由圖6可以看出，隨著采樣點數(shù)的增加，2種情況的平均峰值信噪比都是逐漸增加的，但是經(jīng)過運動補(bǔ)償?shù)囊曨l序列的重構(gòu)質(zhì)量相對較高，且平均峰值信噪比受采樣點數(shù)影響較小，具有很好的魯棒性.

為了驗證在不同場景下本文算法的有效性，對背景變化的foreman(QCIF格式)的視頻序列進(jìn)行實驗，仿真結(jié)果如圖7所示.說明本文算法仍可獲得比較好的重構(gòu)效果，具有一定的普適性.

圖7 平均峰值信噪比隨采樣點數(shù)的變化情況Fig.7 The change of the average PSNR along with the number of sampling

4 結(jié)束語

在壓縮感知理論的基礎(chǔ)上，提出了一種基于幀間差值和運動補(bǔ)償?shù)囊曨l壓縮感知重構(gòu)的方法，該方法充分利用了幀與幀之間的連續(xù)性和相關(guān)性，并進(jìn)行了實驗，獲得了較好的實驗效果.在實驗仿真時，對視頻序列的分組比較固定，采樣點數(shù)比較統(tǒng)一，并且是對整幀圖像進(jìn)行處理.若是采用根據(jù)運動劇烈程度自適應(yīng)分組和自適應(yīng)采樣，并且將幀圖像分成子塊進(jìn)行處理，效果會進(jìn)一步得到優(yōu)化.

[1]DONOHO D.Compressed sensing[J].IEEE Transactions on Information Theory，2006，52(4):1289-1306.

[2]CANDES E.Compressive sampling[C]//Proceedings of the International Congress of Mathmaticians.Madrid，Spain，2006:1433-1452.

[3]岑翼剛，岑麗輝.基于峰值變換的信號系數(shù)表示及重建[J].電子與信息學(xué)報，2011，33(2):326-331.CEN Yigang，CEN Lihui.Sparse representation and reconstruction of signals based on the peak transform[J].Journal of Electronics and Information Technology，2011，33(2):326-331.

[4]岑翼剛，陳曉方，岑麗輝，等.基于單層小波變換的壓縮感知圖像處理[J].通信學(xué)報，2010，31(8A):52-55.CEN Yigang，CHEN Xiaofang，CEN Lihui，et al.Compressed sensing based on the single layer wavelet transform for image processing[J].Journal on Communications，2010，31(8A):52-55.

[5]石光明，劉丹華，高大化.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報，2009(5):1070-1078.SHI Guangming，LIU Danhua，GAO Dahua.Advances in theory and application of compressed sensing[J].Acta Electronica Sinica，2009(5):1070-1078.

[6]BARANIUK R.A lecture on compressive sensing[J].IEEE Signal Processing Magazine，2007，24(4):118-121.

[7]DONOHO D L，ELAD M，TEMLYAKOV V N.Stable recovery of sparse overcomplete representations in the presence of noise[J].IEEE Transactions on Information Theory，2006，52(1):6-18.

[8]TROPP J A.Greed is good:algorithmic results for sparse approximation[J].IEEE Transactions on Information Theory，2004，50(10):2231-2242.

[9]TROPP J A，GILBERT A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory，2007，53(12):4655-4666.

[10]FIGUEIREDO M A T，NOWAK R D，WRIGHT S J.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problem[J].Journal of Selected Topics in Signal Processing:Special Issue on Convex Optimization Methods for Signal Processing，2007，1(4):586-598.

[11]GILBERT A C，STRAUSS M J，TROPP J A，et al.Algorithmic linear dimension reduction in the l1norm for sparse vectors[C]//Proceedings of the 44th Annual Allerton Conference on Communication，Control and Computing.Monticello，USA，2006:1-27.

[12]翟沖.基于壓縮感知的視頻編碼技術(shù)研究[D].大連:大連理工大學(xué)，2010:18-20.Zhai Chong.The research of video coding based on compressive sensing[D].Dalian:Dalian University of Technology，2010:18-20.