周欽青，陳遵德

?

視覺傳感網(wǎng)中基于二次規(guī)劃的圖像壓縮感知

周欽青，陳遵德

(順德職業(yè)技術(shù)學(xué)院電子與信息工程系，廣東 佛山 528333)

為降低視覺傳感網(wǎng)絡(luò)中圖像壓縮感知算法的計算復(fù)雜度，提出一種基于二次規(guī)劃的網(wǎng)絡(luò)圖像恢復(fù)算法。該算法將壓縮感知重構(gòu)中的欠定線性方程組求解問題，轉(zhuǎn)化為有界約束二次規(guī)劃問題，在此基礎(chǔ)上結(jié)合阿米霍步長準則，設(shè)計一種壓縮感知圖像恢復(fù)算法，通過求解二次規(guī)劃問題對網(wǎng)絡(luò)圖像數(shù)據(jù)進行恢復(fù)。理論分析和仿真結(jié)果表明，與傳統(tǒng)圖像壓縮感知算法相比，該算法可減少約1/3的圖像數(shù)據(jù)恢復(fù)運算時間，且圖像重構(gòu)質(zhì)量提高3 dB~6 dB，有效提高了視覺傳感器網(wǎng)絡(luò)圖像恢復(fù)算法的實時性。

視覺傳感網(wǎng)；壓縮感知；圖像恢復(fù)；二次規(guī)劃；有界約束；實時性

1 概述

視覺傳感網(wǎng)(Visual Sensor Networks, VSN)是由一組具有計算、存儲和通信能力的視覺傳感器設(shè)備組成的分布式感知網(wǎng)絡(luò)，能夠?qū)崟r準確地從監(jiān)測環(huán)境中獲取含有特定事件信息的圖像[1]。然而，視覺傳感網(wǎng)將采集到的圖像信息通過無線傳輸方式發(fā)送給使用者需要消耗大量能量，而節(jié)點攜帶電源能量卻十分有限。因此，在保障監(jiān)測質(zhì)量的前提下降低網(wǎng)絡(luò)圖像數(shù)據(jù)傳輸能耗，延長節(jié)點壽命是視覺傳感網(wǎng)技術(shù)迫切需要解決的問題[2]。

視覺傳感網(wǎng)采集的圖像數(shù)據(jù)具有很大的冗余性和相關(guān)性，減少冗余信息在網(wǎng)絡(luò)中的傳輸是降低節(jié)點能耗的有效途徑。作為一種利用信號稀疏性或可壓縮性的全新信號采樣理論，壓縮感知(Compressed Sensing, CS)為實現(xiàn)這一目標(biāo)提供了契機[3-4]。與分布式信源編碼、圖像編碼等傳統(tǒng)的圖像數(shù)據(jù)壓縮算法相比，基于壓縮感知的圖像數(shù)據(jù)恢復(fù)僅需在節(jié)點進行簡單的測量運算，將復(fù)雜度較高的重構(gòu)運算移至觀測端，從而可進一步降低傳感器節(jié)點的能耗負擔(dān)。

然而，傳統(tǒng)的基于壓縮感知的圖像恢復(fù)算法通常具有較高的計算復(fù)雜度，而視覺傳感網(wǎng)對圖像重建算法的實時性提出了高要求，因此，現(xiàn)有的圖像壓縮感知算法難以滿足實時視覺傳感網(wǎng)圖像恢復(fù)要求。如在文獻[5]中通過傳統(tǒng)的線性規(guī)劃(Linear Programming, LP)算法求解1范數(shù)最小化問題對視頻數(shù)據(jù)進行重構(gòu)。線性規(guī)劃算法可得到較高的重構(gòu)精度，但算法復(fù)雜度極高。文獻[6-7]分別利用了匹配追蹤算法(Matching Pursuit, MP)及迭代收縮算法[8](Iterative Shrinkage Threshold, IST)，這2種算法可提高算法收斂速度，但重構(gòu)精度不高。文獻[9]的圖像重構(gòu)使用了壓縮采樣匹配追蹤算法[10](Compressive Sampling Matching Pursuit, CoSaMP)，該算法可達到與線性規(guī)劃類似的重構(gòu)精度，但對于視覺傳感網(wǎng)中的海量圖像數(shù)據(jù)而言，算法復(fù)雜度仍不能滿足圖像傳輸?shù)母邔崟r性要求。

針對目前視覺傳感網(wǎng)圖像恢復(fù)算法存在的不足，本文提出一種基于二次規(guī)劃的網(wǎng)絡(luò)圖像數(shù)據(jù)恢復(fù)算法。與以往的算法不同，該算法將網(wǎng)絡(luò)圖像壓縮感知中的欠定線性方程組求解問題轉(zhuǎn)化為二次規(guī)劃問題，同時結(jié)合阿米霍步長準則[11]設(shè)計一種網(wǎng)絡(luò)數(shù)據(jù)恢復(fù)算法，通過求解二次規(guī)劃問題對網(wǎng)絡(luò)數(shù)據(jù)進行恢復(fù)。

2 問題描述

其中，向量表示的稀疏系數(shù)向量；表示向量的零范數(shù)，即向量中零元素的個數(shù)。

對圖像數(shù)據(jù)進行稀疏變換后，可對圖像數(shù)據(jù)進行測量，其過程可由下式表示：

而本文將式(4)求解轉(zhuǎn)化為二次規(guī)劃問題，通過求解二次規(guī)劃得到恢復(fù)圖像。

3 網(wǎng)絡(luò)圖像數(shù)據(jù)的二次規(guī)劃重構(gòu)

3.1 算法描述

其中：

式(9)可寫為二次規(guī)劃的標(biāo)準形式：

即：

在上述工作基礎(chǔ)上，完整的算法步驟可整理為：

步驟5判斷終止條件：

3.2 收斂性分析

結(jié)合式(16)可得：

綜合式(17)、式(18)及文獻[13]中定理2.4，即可得到算法的收斂性證明。

4 仿真實驗結(jié)果

圖2為在同一次重構(gòu)中不同重構(gòu)算法的重構(gòu)圖像與原始圖像對比。其中，IST算法、CoSaMP算法、本文算法計算時間分別為：1.61 s、1.66 s、1.07 s；PSNR值分別為24.44 dB、26.95 dB、28.37 dB。

圖2 重構(gòu)圖像與原始圖像對比

由重構(gòu)結(jié)果可以看出，本文算法可以達到較高的圖像恢復(fù)質(zhì)量，恢復(fù)的PSNR值略優(yōu)于以往的壓縮感知重構(gòu)算法。同時，實驗對算法計算時間的統(tǒng)計結(jié)果表明，對于同一分辨率的靜態(tài)圖像而言，本文算法計算時間相對經(jīng)典恢復(fù)算法減少約1/3。實驗在同一計算平臺上進行，計算時間與算法復(fù)雜度呈正比，因此，以上結(jié)果也表明，本文算法的計算復(fù)雜度小于以往算法。

圖3 網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)質(zhì)量對比

圖4 不同算法重構(gòu)時間對比

可以看出，本文算法計算時間小于IST算法及CoSaMP算法，并且隨圖像幀數(shù)的增加，算法優(yōu)越性表現(xiàn)得越來越明顯。圖5所示的PSNR對比進一步驗證了本文算法的有效性。

圖5 不同算法重構(gòu)質(zhì)量對比

5 結(jié)束語

針對視覺傳感網(wǎng)圖像數(shù)據(jù)量大與傳統(tǒng)壓縮感知重構(gòu)算法計算復(fù)雜度無法滿足圖像傳輸?shù)母邔崟r性問題，本文提出一種基于二次規(guī)劃的網(wǎng)絡(luò)圖像恢復(fù)算法，該方法將壓縮感知重構(gòu)中的欠定線性方程組求解轉(zhuǎn)換為二次規(guī)劃問題。實驗結(jié)果表明，相對于傳統(tǒng)分布式壓縮感知理論，本文算法可明顯降低圖像數(shù)據(jù)重構(gòu)算法的計算復(fù)雜度，同時保證重構(gòu)的準確度。對于網(wǎng)絡(luò)圖像數(shù)據(jù)而言，稀疏變換同樣會對壓縮感知重構(gòu)的實時性造成影響，下一步將對此進行研究，并提出面向網(wǎng)絡(luò)圖像數(shù)據(jù)實時重構(gòu)的稀疏變換方法。

[1] Misra S, Reisslein M, Xue Guoliang. A Survey of Multimedia Streaming in Wireless Sensor Networks[J]. IEEE Comm- unications Surveys and Tutorials, 2008, 10(4): 18-39.

[2] 馬華東, 陶 丹. 多媒體傳感器網(wǎng)絡(luò)及其研究進展[J]. 軟件學(xué)報, 2006, 17(9): 2013-2028.

[3] Donoho D. Compressed Sensing[J]. IEEE Trans. on Inform- ation Theory, 2006, 52(4): 1289-1306.

[4] 焦李成, 楊淑媛, 劉 芳, 等. 壓縮感知回顧與展望[J]. 電子學(xué)報, 2011, 20(7): 1651-1662.

[5] Marcia R, Willet R. Compressive Coded Aperture Video Reconstruction[C]//Proc. of the 16th European Signal Processing Conference. Lausanne, Switzerland: European Association for Signal Processing, 2008: 3037-3041.

[6] Park J, Wakin M B. A Multiscale Framework for Compressive Sensing of Video[C]//Proc. of the 27th Conference on Picture Coding Symposium. Chicago, USA: [s. n.], 2009: 197-200.

[7] 練秋生, 肖 瑩. 基于小波樹結(jié)構(gòu)和迭代收縮的圖像壓縮感知算法研究[J]. 電子與信息學(xué)報, 2011, 33(4): 967-971.

[8] Daubechies I, Defrise M, DeMol C. An Iterative Thresholding Algorithm for Linear Inverse Problems with a Sparsity Constraint[J]. Communications on Pure and Applied Mathematics, 2004, 57(11): 1413-1457.

[9] Sankaranarayanan A C, Turaga P, Baraniuk R, et al. Com- pressive Acquisition of Dynamic Scenes[C]//Proc. of the 11th European Conference on Computer Vision. Crete, Greece: [s. n.], 2010: 456-465.

[10] Needell D, Tropp J. Cosamp: Iterative Signal Recovery from Incomplete and Inaccurate Samples[J]. Applied and Computational Harmonic Analysis, 2009, 26(3): 301-321.

[11]Bertsekas D. Nonlinear Programming[M]. Boston, USA: [s. n.], 1999.

[12] Gan L, Do T, Tran T D. Fast Compressive Imaging Using Scrambled Hadamard Ensemble[C]//Proc. of the 16th European Signal Processing Conference. Lausanne, Switzerland: European Association for Signal Processing, 2008: 11-20.

[13] Birgin E G, Martnez J M, Raydan M. Nonmonotone Spectral Projected Gradient Methods on Convex Sets[J]. SIAM Journal on Optimization, 2000, 10(4): 1196-1211.

編輯 索書志

Image Compressed Sensing Based on Quadratic Programming in Visual Sensor Networks

ZHOU Qin-qing, CHEN Zun-de

(Department of Electronic and Information Engineering, Shunde Polytechnic College, Foshan 528333, China)

For reducing the computational complexity of Compressed Sensing(CS) in Visual Sensor Networks(VSN), an image recovery algorithm based on quadratic programming is proposed. The under-determined linear equations in CS recovery are solved by bound-constrained quadratic programming, and an image recovery algorithm is designed based on the armijo rule. Theory analysis and experimental results show that the proposed algorithm can reduce 1/3 operation time of image recovery, and enhance the recovery quality by 3 dB~6 dB, thus significantly improve the real-time performance of image recovery in VSN.

Visual Sensor Networks(VSN); Compressed Sensing(CS); image recovery; quadratic programming; bound-constrained; real-time performance

1000-3428(2014)03-0258-04

A

TP391.41

廣東省信息技術(shù)教指委立項基金資助項目(XXJS-2013-35)；順德職業(yè)技術(shù)學(xué)院教改基金資助項目(2012-SZJGXM20)。

周欽青(1981－)，女，講師、碩士，主研方向：圖像處理與分析，信息安全；陳遵德，教授、博士。

2013-01-16

2013-04-02 E-mail：sd22329975@126.com

10.3969/j.issn.1000-3428.2014.03.054