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

（廣西大學計算機與電子信息學院，南寧530004）

基于殘差重構的分布式視頻壓縮感知?

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

（廣西大學計算機與電子信息學院，南寧530004）

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

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

1 引 言

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

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

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

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

2 壓縮感知理論

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

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

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

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

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

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

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

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

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

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

3 基于殘差重構的DCVS方案

3.1 整體結構

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

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

圖1 解碼端圖像重構總流程

非關鍵幀的殘差重構過程如圖2所示，具體包括如下步驟：

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

步驟3：對yr采用TVAL3算法［9］求解TVmin問題，得到重構結果；

圖2 非關鍵幀殘差重構流程

3.2 殘差重構

殘差重構是本文提出的DCVS結構的核心，下面詳細對該方法的流程和性能進行分析。

假設原始信號為x，采用測量矩陣Φ進行測量，得到測量值y。在本文算法中，并不直接采用測量值y進行重構，而是采用殘差重構的方法。具體地，假設在重構端有待重構信號的預測值，對預測值進行測量，得到

其次，求實際測量值與預測測量殘差值：

從公式（7）可知，yr實際上就是原始幀與預測值的殘差xr做隨機投影的結果。假設為從yr中恢復出來的殘差信號，則可以通過下式獲取原信號x的重構值：

根據(jù)上述流程，原始信號x的重構誤差為

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

3.3 邊信息生成

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

類似于DVC［1］，可以通過在關鍵幀之間進行ME，并對運動矢量調整后進行MC得到SI。在本文方案中，首先對關鍵幀進行6-tap FIR濾波器插值得到1/2像素精度圖像，繼而進行雙線性插值得到1/4像素精度圖像；之后在前后兩個關鍵幀之間雙向迭代進行1/4像素精度的ME/MC操作。圖3給出了GOP大小為4時的雙向迭代ME/MC結構。

圖3 雙向迭代ME/MC結構

4 實驗結果及討論

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

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

表1 非關鍵幀重構質量比較Table 1 Reconstruction quality comparison for non-key frames

圖4 “foreman”序列PSNR比較

圖5 “football”序列PSNR比較

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

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

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

5 結束語

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

［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年于北京郵電大學獲博士學位，現(xiàn)為廣西大學計算機與電子信息學院副教授，主要研究方向為壓縮感知、視頻編碼與傳輸；

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

覃團發(fā)（1966—），男，廣西賓陽人，1997年于南京大學獲博士學位，現(xiàn)為廣西大學計算機與電子信息學院副院長、教授、中國電子學會高級會員、中國通信學會高級會員，主要研究方向為無線多媒體通信、網絡編碼、視頻編碼和圖像檢索；

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年于華中科技大學獲博士學位，現(xiàn)為廣西大學計算機與電子信息學院副教授，主要研究方向為無線多媒體通信。

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

國家自然科學基金資助項目（61261023）；廣西自然科學基金資助項目（2011GXNSFD018024）；廣西教育廳科研項目資助（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）