基于殘差重構(gòu)的分布式視頻壓縮感知?

常侃，覃團(tuán)發(fā)，唐振華

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，南寧530004）

基于殘差重構(gòu)的分布式視頻壓縮感知?

常侃??，覃團(tuán)發(fā)，唐振華

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，南寧530004）

為了改進(jìn)分布式視頻壓縮感知方案的性能，提出了一種基于殘差重構(gòu)的分布式視頻壓縮感知方案。該方案在編碼端逐幀獨(dú)立進(jìn)行測(cè)量，在解碼端依靠視頻信號(hào)的時(shí)域相關(guān)性提升重構(gòu)信號(hào)質(zhì)量。首先，對(duì)關(guān)鍵幀獨(dú)立進(jìn)行重構(gòu)；其次，利用已重構(gòu)關(guān)鍵幀做運(yùn)動(dòng)估計(jì)/運(yùn)動(dòng)補(bǔ)償以生成非關(guān)鍵幀的邊信息；接下來，對(duì)邊信息采用與編碼端相同的測(cè)量矩陣進(jìn)行測(cè)量并計(jì)算測(cè)量殘差值；最后，采用全變分最小化重構(gòu)殘差信號(hào)值并將其與邊信息相加生成最終的重構(gòu)圖像。實(shí)驗(yàn)結(jié)果表明，在相同采樣率下，與已有的分布式視頻壓縮感知方案相比，提出的方案可獲得2.8 dB以上的峰值信噪比增益。

壓縮感知；分布式視頻壓縮感知；殘差重構(gòu)；全變分最小化；邊信息

1 引 言

分布式視頻編碼（Distributed Video Coding，DVC）［1］是一種特殊的視頻編碼框架。這類框架在編碼端對(duì)各幀進(jìn)行獨(dú)立編碼，在解碼端則對(duì)連續(xù)的視頻幀進(jìn)行聯(lián)合解碼以獲取更高質(zhì)量的解碼結(jié)果。與傳統(tǒng)混合視頻編碼框架不同，DVC把計(jì)算量較大的運(yùn)動(dòng)估計(jì)（Motion Estimation，ME）/運(yùn)動(dòng)補(bǔ)償（Mo-tion Compensation，MC）操作轉(zhuǎn)移到解碼端，具有“輕編碼、重解碼”的特點(diǎn)，特別適合于電力和計(jì)算能力有限的應(yīng)用場(chǎng)合，例如無線多媒體傳感器、無線視頻監(jiān)控、基于移動(dòng)設(shè)備的視頻會(huì)議等。

壓縮感知（Compressed Sening，CS）［2］是近年在信號(hào)處理領(lǐng)域得到廣泛重視的新興理論體系。該理論指出，若某個(gè)待采樣信號(hào)是稀疏的（或者在某個(gè)變換域是稀疏的），那么我們從其有限的（遠(yuǎn)低于原始信號(hào)維數(shù)）不相關(guān)測(cè)量值中準(zhǔn)確恢復(fù)出原始信號(hào)的可能性極高。該理論突破了奈奎斯特采樣定理的限制，使得信號(hào)獲取的復(fù)雜度大大降低。CS的測(cè)量過程運(yùn)算量較低，而重構(gòu)過程則需要迭代求解最優(yōu)化問題，復(fù)雜度相對(duì)較高。因此，CS理論結(jié)構(gòu)特別適合各類分布式應(yīng)用。

為了結(jié)合CS與DVC的優(yōu)點(diǎn)，已經(jīng)有一些學(xué)者將CS理論應(yīng)用于DVC框架，設(shè)計(jì)分布式視頻壓縮感知（Distributed Compressed Video Sensing，DCVS）框架。其中，Kang等人在解碼端采用GPSR（Gradient Projection for Sparse Reconstruction）方法對(duì)關(guān)鍵幀進(jìn)行獨(dú)立重構(gòu)，采用非關(guān)鍵幀與邊信息（Side Information，SI）間的相關(guān)性改進(jìn)非關(guān)鍵幀的GPSR重構(gòu)過程［3］。但是，Kang的方法沒能很好地利用時(shí)域相關(guān)性，因此信號(hào)的重構(gòu)質(zhì)量不高。Do等人采用已重構(gòu)關(guān)鍵幀中的空域相鄰塊對(duì)待重構(gòu)非關(guān)鍵幀中的塊進(jìn)行稀疏表示，以提高SI的準(zhǔn)確性［4］。在Do的方法中，SI的生成需要塊信號(hào)的測(cè)量值，而一般來說，幀級(jí)別測(cè)量比塊級(jí)別測(cè)量的性能更好；另外，SI的生成需要逐塊求解l1最小化問題，復(fù)雜度很高。文獻(xiàn)［4－5］都在重構(gòu)端對(duì)非關(guān)鍵幀進(jìn)行預(yù)測(cè)，并對(duì)預(yù)測(cè)值進(jìn)行測(cè)量，最后對(duì)測(cè)量殘差值進(jìn)行重構(gòu)。在預(yù)測(cè)準(zhǔn)確的前提下，殘差信號(hào)比原始信號(hào)在變換域下更為稀疏，因此殘差信號(hào)的重構(gòu)誤差在很大概率上要小于原始信號(hào)的重構(gòu)誤差。但是，文獻(xiàn)［5］首先對(duì)非關(guān)鍵幀進(jìn)行獨(dú)立重構(gòu)，其次以已重構(gòu)關(guān)鍵幀為參考進(jìn)行ME/MC，然后再次對(duì)非關(guān)鍵幀做殘差重構(gòu)。為了保證重構(gòu)質(zhì)量，上述過程還需迭代n次（一般取5次），可見解碼復(fù)雜度很高，并不實(shí)用。

為了提高DCVS方案的重構(gòu)信號(hào)質(zhì)量，本文提出了一種基于殘差重構(gòu)的DCVS方案。該方案利用相鄰關(guān)鍵幀迭代進(jìn)行1/4精度的ME/MC操作以保證SI的準(zhǔn)確性；對(duì)SI進(jìn)行測(cè)量，并對(duì)測(cè)量殘差值進(jìn)行全變分最小化（Total Variation Minimization，TVmin）重構(gòu)。與Kang的方案相比［3］，本文方案沒有過多增加解碼端負(fù)擔(dān)，卻較大幅度地提升了非關(guān)鍵幀的重構(gòu)質(zhì)量。

2 壓縮感知理論

CS理論［2］的出現(xiàn)，突破了香農(nóng)采樣定理的瓶頸，降低了對(duì)傳感器件分辨率的要求，使得超高分辨率信號(hào)獲取成為可能。具體地，假設(shè)x是n維原始數(shù)據(jù)，Φ是m×n維測(cè)量矩陣（m?n），y是m維測(cè)量數(shù)據(jù)。投影的過程可以采用公式描述如下：

若原始信號(hào)x足夠稀疏，則可以將信號(hào)重構(gòu)過程轉(zhuǎn)換為一個(gè)最小l0范數(shù)的最優(yōu)化問題：

若x本身不稀疏，但是在某種基Ψ下稀疏，則可以通過求解以下l0范數(shù)的最小化問題來重構(gòu)基Ψ下的原始信號(hào)：

其中，Θ＝ΦΨ，x＝Ψs。

在CS理論中，傳感器并不是直接獲取信號(hào)x本身，而是獲取其在測(cè)量基Φ上的投影值。對(duì)于測(cè)量矩陣Φ而言，希望其與稀疏矩陣Ψ不相干，這樣所需的測(cè)量數(shù)為

其中，k是x在Ψ下的非零值個(gè)數(shù)，c是常數(shù)。

比較普遍的方法是選取Φ為隨機(jī)矩陣，因?yàn)殡S機(jī)矩陣與任何稀疏基都能以極大的概率不相干。但是，采用此類矩陣需要較高的內(nèi)存開銷和計(jì)算量，所以并不實(shí)用。Gan等人提出了結(jié)構(gòu)化的隨機(jī)矩陣（Structurally random matrix，SRM）［6］，在該方法中，首先對(duì)輸入信號(hào)進(jìn)行隨機(jī)置亂，其次進(jìn)行簡(jiǎn)單、高效的變換（例如DCT或哈達(dá)瑪變換），最后做隨機(jī)下采樣操作。測(cè)量值的產(chǎn)生僅需要少量的計(jì)算和內(nèi)存開銷，并不需要存儲(chǔ)龐大的測(cè)量矩陣。鑒于該方法的良好性能，在本方案中編碼端采用SRM方法進(jìn)行測(cè)量。

由于求解l0范數(shù)的最小化問題是NP難，目前已有很多替代解法，其中最著名的方法是基追蹤（Basic Pursuit，BP）算法，該方法將最小化l0范數(shù)問題轉(zhuǎn)化為求解最小化l1范數(shù)問題，即

求解BP問題的復(fù)雜度較高，當(dāng)信號(hào)的維度較高時(shí)（例如圖像與視頻信號(hào)），信號(hào)重構(gòu)過程所需時(shí)間過長(zhǎng)，使得CS的實(shí)用性降低。為提高信號(hào)的重構(gòu)速度，出現(xiàn)了基于梯度下降的方法（如GPSR［7］），并出現(xiàn)了許多貪婪算法，如正交匹配追蹤（Orthogonal Matching Pursuit，OMP）［8］等。

對(duì)于圖像/視頻信號(hào)而言，可以采用TVmin來取代l1最小化，從而更好地反映圖像/視頻信號(hào)的特征。TVmin由Candes等人引入CS中作為圖像/視頻信號(hào)的重構(gòu)方法［2］。經(jīng)典的求解TV最小化的方法是采用內(nèi)點(diǎn)法迭代求解log-barrier問題，但是需要較高的復(fù)雜度，并不實(shí)用。Li將TV最小化問題轉(zhuǎn)化為Augmented Lagrangian問題的形式，并將該問題拆成兩個(gè)子問題交替求解，大大簡(jiǎn)化了求解過程［9］，該方法被命名為TVAL3。本文采用TVAL3算法進(jìn)行信號(hào)重構(gòu)。

3 基于殘差重構(gòu)的DCVS方案

3.1 整體結(jié)構(gòu)

在編碼端，將視頻序列劃分為若干圖像組（Group of Pictures，GOP），每個(gè)GOP包含一個(gè)關(guān)鍵幀和若干非關(guān)鍵幀，對(duì)關(guān)鍵幀和非關(guān)鍵幀均獨(dú)立采用SRM［6］進(jìn)行CS測(cè)量，關(guān)鍵幀的采樣率需大于非關(guān)鍵幀的采樣率。

解碼端的重構(gòu)總體流程如圖1所示。首先重構(gòu)每個(gè)GOP中的關(guān)鍵幀——對(duì)關(guān)鍵幀的測(cè)量值獨(dú)立采用TVAL3算法［9］求解TVmin問題；其次，采用相鄰已重構(gòu)關(guān)鍵幀經(jīng)過1/4精度的迭代ME/MC操作生成非關(guān)鍵幀SI值；接下來，利用非關(guān)鍵幀的測(cè)量值及SI逐幀進(jìn)行殘差重構(gòu)。

圖1 解碼端圖像重構(gòu)總流程

非關(guān)鍵幀的殘差重構(gòu)過程如圖2所示，具體包括如下步驟：

步驟2：計(jì)算測(cè)量殘差值yr＝y(tǒng)－；

步驟3：對(duì)yr采用TVAL3算法［9］求解TVmin問題，得到重構(gòu)結(jié)果；

圖2 非關(guān)鍵幀殘差重構(gòu)流程

3.2 殘差重構(gòu)

殘差重構(gòu)是本文提出的DCVS結(jié)構(gòu)的核心，下面詳細(xì)對(duì)該方法的流程和性能進(jìn)行分析。

假設(shè)原始信號(hào)為x，采用測(cè)量矩陣Φ進(jìn)行測(cè)量，得到測(cè)量值y。在本文算法中，并不直接采用測(cè)量值y進(jìn)行重構(gòu)，而是采用殘差重構(gòu)的方法。具體地，假設(shè)在重構(gòu)端有待重構(gòu)信號(hào)的預(yù)測(cè)值，對(duì)預(yù)測(cè)值進(jìn)行測(cè)量，得到

其次，求實(shí)際測(cè)量值與預(yù)測(cè)測(cè)量殘差值：

從公式（7）可知，yr實(shí)際上就是原始幀與預(yù)測(cè)值的殘差xr做隨機(jī)投影的結(jié)果。假設(shè)為從yr中恢復(fù)出來的殘差信號(hào)，則可以通過下式獲取原信號(hào)x的重構(gòu)值：

根據(jù)上述流程，原始信號(hào)x的重構(gòu)誤差為

根據(jù)式（9）可知，在殘差重構(gòu)算法中，原始信號(hào)x的重構(gòu)誤差由預(yù)測(cè)殘差xr直接決定。另一方面，若與x足夠接近，則xr定會(huì)比原信號(hào)x更為稀疏。因此，采用CS重構(gòu)算法從yr中恢復(fù)xr會(huì)比從y中恢復(fù)x的誤差更小。由此可以推斷出，殘差重構(gòu)算法可以比直接重構(gòu)算法獲得更好的重構(gòu)質(zhì)量。

3.3 邊信息生成

為了保證SI準(zhǔn)確性，在Do的方法中［4］，需要逐塊求解l1最小化問題以獲取當(dāng)前預(yù)測(cè)塊的稀疏表示；而在Mun的方法中［5］，則需要先直接重構(gòu)非關(guān)鍵幀，接著多次迭代進(jìn)行“ME/MC-殘差重構(gòu)”操作。兩種SI生成方法的復(fù)雜度都過高，并不實(shí)用。

類似于DVC［1］，可以通過在關(guān)鍵幀之間進(jìn)行ME，并對(duì)運(yùn)動(dòng)矢量調(diào)整后進(jìn)行MC得到SI。在本文方案中，首先對(duì)關(guān)鍵幀進(jìn)行6-tap FIR濾波器插值得到1/2像素精度圖像，繼而進(jìn)行雙線性插值得到1/4像素精度圖像；之后在前后兩個(gè)關(guān)鍵幀之間雙向迭代進(jìn)行1/4像素精度的ME/MC操作。圖3給出了GOP大小為4時(shí)的雙向迭代ME/MC結(jié)構(gòu)。

圖3 雙向迭代ME/MC結(jié)構(gòu)

4 實(shí)驗(yàn)結(jié)果及討論

為了測(cè)試算法性能，在MATLAB平臺(tái)上仿真了本文方案，并與Kang的方法［3］進(jìn)行比較。GOP大小設(shè)定為4，關(guān)鍵幀的采樣率固定為0.7，對(duì)于非關(guān)鍵幀，分別采用0.1、0.2、0.3、0.4和0.5 5種采樣率。用于信號(hào)測(cè)量的SRM選用哈達(dá)瑪變換；用于信號(hào)重構(gòu)的TVAL3算法中的μ選為212，β選為26，外循環(huán)門限設(shè)為10－6，內(nèi)循環(huán)門限設(shè)為10－3，最大迭代次數(shù)設(shè)為150。采用的測(cè)試序列為CIF格式的“foreman”與“football”，幀率為30 frame/s?！癴oreman”序列含有較慢的運(yùn)動(dòng)，相對(duì)較平緩；相比之下，“football”序列細(xì)節(jié)信息豐富，包含快速運(yùn)動(dòng)。

表1列出了兩種方法在5個(gè)采樣率下的非關(guān)鍵幀重構(gòu)圖像的平均峰值信噪比（Peak Signal to Noise Ratio，PSNR），圖4和圖5則更直觀地顯示出了非關(guān)鍵幀重構(gòu)圖像PSNR值隨采樣率變化情況。

表1 非關(guān)鍵幀重構(gòu)質(zhì)量比較Table 1 Reconstruction quality comparison for non-key frames

圖4 “foreman”序列PSNR比較

圖5 “football”序列PSNR比較

從表1和圖4、圖5中可以總結(jié)出，首先，在相同的采樣率下，本文方法比Kang的方法有較高的PSNR提升；隨著采樣率的升高，本文方法PSNR提升值逐漸增大。例如，對(duì)于“foreman”序列，在0.1的采樣率下，本文方法可以獲得2.87 dB的PSNR增益；當(dāng)采樣率提升到0.5時(shí)，該值提升到7.23 dB。其次，當(dāng)序列中含有快速運(yùn)動(dòng)和豐富細(xì)節(jié)信息時(shí)，本文方法的非關(guān)鍵幀重構(gòu)圖像質(zhì)量下降，主要原因有二：第一，豐富細(xì)節(jié)信息導(dǎo)致關(guān)鍵幀重構(gòu)質(zhì)量下降；第二，快速運(yùn)動(dòng)導(dǎo)致生成的SI準(zhǔn)確性降低。

圖6和圖7分別展示了“foreman”序列與“football”序列的SI與殘差值（取絕對(duì)值顯示）。由于“foreman”序列運(yùn)動(dòng)緩慢，因此SI較為準(zhǔn)確，圖6中的殘差值很小。在此情況下，采用TVAL3算法求解TVmin問題，整幀圖像的離散梯度值較稀疏，因此可斷定重構(gòu)效果較好，該分析結(jié)論也與表1的實(shí)驗(yàn)結(jié)果吻合。相比之下，“football”序列包含快速運(yùn)動(dòng)，生成的SI失真較大，圖7（b）中的殘差圖像梯度值不夠稀疏，因此求解TVmin問題的效果明顯差于“foreman”序列。

圖6 “foreman”序列第6幀SI與殘差值

5 結(jié)束語

本文將殘差重構(gòu)方式引入DCVS方案，并且綜合應(yīng)用了雙向迭代的SI生成方法，充分利用了視頻信號(hào)的時(shí)域相關(guān)性。依據(jù)實(shí)驗(yàn)結(jié)果可知，在SI準(zhǔn)確的前提下，殘差重構(gòu)方案可以較大幅度地提升重構(gòu)信號(hào)質(zhì)量，從而證明了殘差重構(gòu)方案的有效性。需要注意的是，本文方案未考慮測(cè)量值的量化和熵編碼問題。雖然量化和熵編碼可以有效降低輸出數(shù)據(jù)量，但是量化對(duì)非線性重構(gòu)結(jié)果的影響還需要進(jìn)一步地研究和分析。因此，下一步的工作重點(diǎn)是將量化和熵編碼合理、有效地引入到提出的DCVS方案中，以進(jìn)一步推進(jìn)DCVS方案的實(shí)用化。

［1］Guillemot C，Pereira F，Torres L，et al.Distributed monoview andmultiview video coding：basics，problems and recent advances［J］.IEEE Signal Processing Magazine，2007，24（5）：67－76.

［2］Candes E，Romberg J，Tao T.Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52（2）：489－509.

［3］KANG Li-wei，LU Chun-shien.Distributed compressive video sensing［C］//Proceedings of 2009 IEEE International Conference on Acoustics，Speech，and Signal Processing.Taipei，Taiwan：IEEE，2009：1169－1172.

［4］Do T，Chen Yi，Nguyen D，et al.Distributed compressed video sensing［C］//Proceedings of 2009 IEEE International Conference on Image Processing.Cario，Egypt：IEEE，2009：1393－1396.

［5］Mun S，F(xiàn)owler J.Residual reconstruction for block-based compressed sensing of video［C］//Proceedings of2011 Data Compression Conference.Snowbird，Utah，USA：IEEE，2011：183－192.

［6］Do T，Gan Lu，Nguyen N，etal.Fastand EfficientCompressive Sensing Using Structurally Random Matrices［J］.IEEETransactions on Signal Processing，2012，60（1）：139－154.

［7］Figueiredo M，Nowak R，Wrigh S.Gradient projection for sparse reconstruction：application to compressed sensing and other inverse problems［J］.IEEE Journal of Selected Topics in Signal Processing，2007，1（4）：586－597.

［8］Tropp J，Gilbert A.Signal recovery from random measurements via orthogonalmatching pursuit［J］.IEEE Transactions on Information Theory，2007，53（12）：4655－4666.

［9］LICheng-bo.An efficient algorithm for total variation regularization with applications to the single pixel camera and compressive sensing［D］.Houston：Rice University，2009.

常侃（1983—），男，廣西南寧人，2010年于北京郵電大學(xué)獲博士學(xué)位，現(xiàn)為廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院副教授，主要研究方向?yàn)閴嚎s感知、視頻編碼與傳輸；

CHANG Kan was born in Nanning，Guangxi Zhuang Autonomous Region，in 1983.He received the Ph.D.degree from Beijing University of Posts and Telecommunication in 2010，and is now an associate professor of School of Computer and Electronic Information，Guangxi University.His research interests include compressed sensing，video coding and transmission.

Email：pandack0619＠163.com

覃團(tuán)發(fā)（1966—），男，廣西賓陽人，1997年于南京大學(xué)獲博士學(xué)位，現(xiàn)為廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院副院長(zhǎng)、教授、中國電子學(xué)會(huì)高級(jí)會(huì)員、中國通信學(xué)會(huì)高級(jí)會(huì)員，主要研究方向?yàn)闊o線多媒體通信、網(wǎng)絡(luò)編碼、視頻編碼和圖像檢索；

QIN Tuan-fa was born in Binyang，Guangxi Zhuang Autonomous Region，in 1966.He received the Ph.D.degree from Nanjing University in 1997.He is now a professor and vice Dean of School of Computer and Electronic Information，GuangxiUniversity.He is also the seniormember of China Institute of Electronics and China Communications Institute.His research interests includewirelessmultimedia communications，network coding，video encoding and image retrieval.

Email：tfqin＠gxu.edu.cn

唐振華（1979—），男，廣西玉林人，2009年于華中科技大學(xué)獲博士學(xué)位，現(xiàn)為廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院副教授，主要研究方向?yàn)闊o線多媒體通信。

TANG Zhen-hua was born in Yulin，Guangxi Zhuang Autonomous Region，in 1979.He received the Ph.D.degree from Huazhong University of Science and Technology in 2009，and is now an associate professor of School of Computer and Electronic Information，Guangxi University.His research concerns wirelessmultimedia communications.

Email：tangedward＠126.com

Residual Reconstruction Based Distributed Compressed Video Sensing

CHANG Kan，QIN Tuan-fa，TANG Zhen-hua
（School of Computer and Electronic Information，GuangxiUniversity，Nanning 530004，China）

To improve the performance of Distributed Compressed Video Sensing（DCVS），a residual reconstruction based DCVS framework is proposed.The proposed framework samples each video frame independently at the encoder.However，it recovers frames at the decoder by exploiting inter frame correlation.Firstly，the key frame of a Group of Pictures（GOP）is independently reconstructed.Secondly，Side Information（SI）is generated by performing bi-directional Motion Estimation（ME）and Motion Compensation（MC）through the reconstructed key frames.Afterwards，the generated SI frame is sampled by the samematrix as the one at the encoder，and the measurement of SI is used to calculate the residual ofmeasurement.Finally，total variationminimization is applied to reconstruct the residual signal，and the output frame is formed by adding SI to the residual signal.Experimental results show that compared with the existing DCVSmethod，the proposed one can getmore than 2.8 dB Peak Signal to Noise Ratio（PSNR）increment at the same sampling rate.

compressed sensing（CS）；distributed compressed video sensing（DCVS）；residual reconstruction；total variationminimization；side information（SI）

TN919.8

A

1001－893X（2013）03－0274－05

10.3969/j.issn.1001－893x.2013.03.009

2012－08－31；

2012－11－09 Received date：2012－08－31；Revised date：2012－11－09

??通訊作者：pandack0619＠163.com Corresponding author：pandack0619＠163.com

國家自然科學(xué)基金資助項(xiàng)目（61261023）；廣西自然科學(xué)基金資助項(xiàng)目（2011GXNSFD018024）；廣西教育廳科研項(xiàng)目資助（201203YB001）

Foundation Item：The National Natural Science Foundation of China（No.61261023）；The Natural Science Foundation of Guangxi（2011GXNSFD018024）；The Foundation of Education Commission of Guangxi（201203YB001）