陳建，蘇凱雄，楊秀芝，鄭明魁，林麗群

?

基于變分模型的塊壓縮感知重構算法

陳建，蘇凱雄，楊秀芝，鄭明魁，林麗群

（福州大學物理與信息工程學院，福建福州350116）

為了提高現(xiàn)有塊壓縮感知重構算法的性能，提出了基于全變分和混合變分模型的塊壓縮感知（簡稱BCS-TV和BCS-MV）算法。該方法以塊為單位進行圖像采樣，以自然圖像正則項的稀疏性為先驗條件，通過變型的增廣拉格朗日交替方向乘子法(ALM-ADMM)，在整幅圖像范圍內(nèi)逼近目標函數(shù)來重構原始圖像。與以前基于一致性塊采樣的壓縮感知工作對比，該算法的PSNR約提高1.5 dB，SSIM約提高0.05，運行速度較穩(wěn)定，特別適合具有固定傳輸時延的多媒體數(shù)據(jù)處理場合。

全變分；圖像重構；塊壓縮感知；交替方向乘子法

1 引言

壓縮感知（CS）理論[1~3]表明，只要信號在某個變換域具有稀疏性，就能利用一個與變換基不相干的觀測矩陣，將原始高維信號投影到一個低維空間上。利用這些少量的觀測值，即可實現(xiàn)信號的精確重構。但對于大尺寸的數(shù)據(jù)（如圖像、視頻），直接的壓縮采樣所需的存儲空間巨大，且復雜度很高。

為了降低圖像的采樣代價，文獻[4~10]研究了自然圖像的塊壓縮感知（BCS）。在測量方法上， Lu和Thong等[4,5]提出了基于塊對角結(jié)構的隨機矩陣和結(jié)構化隨機矩陣（SRM），但理論依據(jù)欠缺，且重構質(zhì)量有待于提高。此后，Thong和Armin等[8,9]分別探討了這2類矩陣的受限等距性質(zhì)(RIP)，為BCS測量方法提供了理論依據(jù)。另一方面，為了提高該測量方案的重構效率，F(xiàn)owler等[6,7]結(jié)合平滑投影算法和方向性小波變換，提出了基于塊壓縮感知的平滑投影蘭德韋伯重構（BCS-SPL, block compressed sensing and smoothed projected landweber reconstruction）算法，并將其應用到視頻壓縮和多視點編碼中。為了降低塊效應，BCS-SPL在每次迭代時都使用維納濾波器進行圖像平滑，但該步驟會模糊圖像的邊緣。為了保持圖像的邊緣像素，文獻[10]將圖像分解為高低頻2個分量分別處理，并添加了銳化空域濾波器和高斯平滑濾波器，雖然有效提高了重構質(zhì)量，但也增加了重構復雜度。

針對現(xiàn)有塊壓縮感知重構算法（BCS-SPL）的濾波步驟未考慮圖像自身特點，以及重構復雜度較高的問題，本文將具有良好邊緣特性和去噪性能的高效全變分模型引入到塊壓縮感知重構中，以求能夠在較低復雜度的條件下，高保真地重建自然圖像。為了提高該重構算法的通用性，進而將該模型推廣到可容納多種稀疏正則項的混合變分模型，以適用于更多類型的圖像。

2 相關理論

2.1 壓縮感知

根據(jù)CS理論[1~3]，在變換域具有稀疏性的信號（），可通過一組與變換基（）不相干的測量向量，投影得到測量值，即

其中，原始信號的尺寸為×1，為域的稀疏系數(shù)，是×l的測量值，是×的測量矩陣（<<）。常用的測量矩陣有高斯矩陣、貝努利矩陣等。

信號重構問題即求解式（1）中的。由于遠小于，故是一個病態(tài)方程求解問題?？梢酝ㄟ^式（2）先求出稀疏系數(shù)，即求解l最小范數(shù)下帶約束的優(yōu)化問題

最后由式（1）的約束條件=恢復出原始信號。目前主流的壓縮感知重構算法主要有凸優(yōu)化、迭代閾值以及貪婪法算法[11]。其中，凸優(yōu)化算法中的TV（全變分）[12,13]不僅能夠保持良好的邊緣特性，而且具有較好的去噪性能，因此備受關注。

2.2 塊壓縮感知

為了減輕計算量和存儲器負擔，一些學者將基于塊的測量方案[4]引入壓縮感知中。塊壓縮感知將每幅圖像分為N個非重疊的塊（尺寸為×，為塊序號），并通過合適的矩陣（尺寸為M×2）進行測量，得到

將式（3）的塊壓縮感知應用于整幀圖像等效于按照式（1）進行壓縮感知，僅需滿足為塊對角矩陣，即

(4)

當稀疏基也具有類似的塊結(jié)構時，解碼端可以按塊重構，如BCS-SPL-DCT。由于基于塊的重構存在塊效應現(xiàn)象，基于式（2）的幀重構方法優(yōu)于塊重構，如基于DWT（離散小波變換），DDWT（離散雙樹小波變換）和CT（輪廓波變換）的BCS-SPL算法[6,7]。

2.3 高效全變分重構算法

TVAL3[12,13]是一種基于增廣拉格朗日交替方向乘子法（ALM-ADMM）的TV改進算法，不僅重構質(zhì)量好，而且收斂速度很快。TVAL3在TV模型基礎上引入變量，并增加一個約束項，表示圖像的離散梯度，其正則化模型可表示為

相應的增廣拉格朗日問題為

(6)

其中，λ和λ是拉格朗日乘子的2個分量，β和β是懲罰參數(shù)。重構過程采用交替方向算法分別求解和子問題，以及更新拉格朗日乘子，第+1次迭代為

(8)

(9)

此外，為了保證重構精度，由小到大更新懲罰參數(shù)，其中為比例系數(shù)。

(11)

2.4 混合變分不等式框架

TV模型實際上是受線性約束的可分離的凸優(yōu)化問題式（13）[14]的一個特例

He等[14~16]提出了針對該問題的混合變分不等式（MVI）統(tǒng)一框架，其標準形式為

求解式（14）的分裂算法詳見文獻[14~17]，而ALM-ADMM則是該算法在=2時的一個特例。文獻[14,17]證明了基于MVI統(tǒng)一框架的重構算法的最差收斂速率為。這為全變分模型能夠進一步推廣為混合變分模型，以及具有穩(wěn)定的重構速率提供了理論依據(jù)。

3 塊壓縮感知變分重構算法

為了在低復雜度和穩(wěn)定速率條件下高效地重構圖像，本文在塊壓縮感知的重構中引入全變分（TV）及混合變分（MV）模型，利用整幅圖像正則項的稀疏先驗知識，提出BCS-TV和BCS-MV的測量及重構方法。下面分別闡述其基本流程、重構模型、算法及性能分析。

3.1 基本流程

1) 分塊排列

先將圖像分為N個非重疊的塊（每塊尺寸為×），然后采用一個合適的掃描方式將每個圖像塊轉(zhuǎn)化為維的列矢量（=1,2,…,N）

= P

其中，= [1,…,]，P代表分塊排列操作符。

2) 按塊測量

通過測量矩陣（尺寸為M×）分別對每個圖像塊列矢量進行測量, 得到N列觀測值（=1,2,…,N）

=

N列組合成觀測值矩陣=[1,…,]，等效于對進行測量，即

=

3) 按幀重構

以整幅圖像梯度模的稀疏性為先驗知識，由和重構出圖像塊列矢量空間

= convex_rec (,)

4) 反掃描和整合

對恢復的每個圖像塊列矢量進行反掃描，并整合成完整的重構圖像

=?1

其中，?1代表分塊排列逆過程。

3.2 重構模型

當圖像相鄰點像素值差異較大時會產(chǎn)生較大的梯度值，由于大多數(shù)自然圖像具有分段光滑[2,7]的特性，因此其梯度模具有良好的稀疏性，結(jié)合測量操作和分塊排列的約束條件，可構造塊壓縮感知重構的正則化模型

其中，參數(shù)定義同前文所述，對應的增廣拉格朗日函數(shù)為

(16)

最小化L(，，，)問題可以分解為如下4個子問題。

1)子問題

2)子問題

(18)

3)子問題

4)子問題

(20)

需要說明的是，式（16）和式（17）中的?為重構誤差，表示整幅圖像的離散梯度，根據(jù)自然圖像的梯度稀疏特性，的非零值個數(shù)很少。尋求同時滿足重構誤差最小和全局離散梯度最小的解，即是所求重構圖像。

3.3 重構算法

BCS-TV沿用TVAL3中分別采用一步最速下降法和類收縮法求解和子問題，僅增加計算量很小的和的轉(zhuǎn)換操作。

具體的重構算法如下。

算法1 Function BCS-TV

輸入值：,

輸出值：

迭代過程：

while（不滿足外循環(huán)截止條件）

while（不滿足內(nèi)循環(huán)截止條件）

第+1次迭代：

1)子問題

①計算L關于的次梯度g

②計算BB步長α

2)子問題：式（18）

3)子問題：

4)子問題：式（20）、式（21）

內(nèi)循環(huán)結(jié)束

更新懲罰參數(shù)：式（11）、式（12）

外循環(huán)結(jié)束

當然，這種BCS-TV算法很容易推廣到含多個正則目標的混合變分模型，只需將式（15）中的和擴展為多個分量。

比如增加一個表示小波域稀疏性的正則項，則式（15）擴展為

其中，D和D分別表示求梯度和小波變換，τ和τ分別表示這2個正則項的權重系數(shù)，對應的重構算法擴展為算法2。

算法2 Function BCS-MV

輸入值：,

輸出值：

迭代過程：

while（不滿足外循環(huán)截止條件）

while（不滿足內(nèi)循環(huán)截止條件）

第+1次迭代：

1)子問題

類似算法1的第①到④步

2)子問題：式（18）

3)子問題

4)子問題

5)子問題：式(20)、式(21)

內(nèi)循環(huán)結(jié)束

更新懲罰參數(shù)：式(11)、式（12）

外循環(huán)結(jié)束

實際上，BCS-MV是BCS-TV的分量擴展，BCS-TV則是BCS-MV的一個特例。

3.4 性能分析

本節(jié)以BCS-SPL-DCT、BCS-SPL-DWT、BCS- SPL-DDWT和BCS-SPL-CT[6,7]為參照，分析BCS-TV和BCS-MV的性能。由于上述算法均是采用一致性的分塊采樣，故采樣復雜度相同，均為，大大低于不分塊直接采樣方式的()。

6種算法的主要區(qū)別在于重構。在測量方式相同的情況下，圖像的變換系數(shù)越稀疏，重構質(zhì)量就越高。BCS-SPL每輪迭代過程都要進行一次像素域的維納濾波和變換域的閾值收縮，兼顧了圖像的分段平滑特征和變換域稀疏性。其中，BCS-SPL-DCT重構過程中針對圖像塊進行稀疏變換，因而重構圖像存在塊效應，需要濾波消除。而其他3種BCS-SPL重構過程中都是針對整幅圖像做稀疏變換，重構質(zhì)量優(yōu)于BCS-SPL-DCT，又由于圖像在DDWT和CT域的能量比DWT域更集中，即更稀疏，因而BCS-SPL-DDWT和BCS-SPL-CT的重構質(zhì)量更好。但是前4種算法的維納濾波環(huán)節(jié)沒有考慮圖像自身信息，統(tǒng)一采用一個3×3的濾波模板，可能會造成圖像的過渡平滑，從而影響圖像恢復質(zhì)量。BCS-TV每次迭代都交替地逼近關于誤差和梯度的增廣拉格朗日函數(shù)的最小值，而梯度最小化反映在重構圖像上自然就會具有分段平滑特征。此外，梯度變換系數(shù)近似圖像邊界，TV域的稀疏性與CT域相當，因而在梯度域具有良好的稀疏性。然而對于紋理圖像，TV域的稀疏性欠佳，DWT、CT和DDWT域稍好。BCS-MV則在BCS-TV基礎上添加了諸如小波約束的正則項，適用于具有光滑和紋理特征的圖像。

在重構復雜度上，BCS-SPL每輪迭代需要進行一次維納濾波（fil），2次遞歸投影（pro)、2次變換（dct、dwt、ddwt和ct分別運行一次正變換和一次反變換，計算量相當）、若干次圖像分塊重排和逆過程（rank，正反排列重組計算量相當），以及針對不同變換系數(shù)的閾值收縮（shr)。前4種算法的主要計算量在于變換和閾值收縮部分，ddwt最復雜，dct最簡單，dwt和ct居中。而BCS-TV和BCS-MV則包含子問題的一步最速下降（osd)，子問題的塊排序變換（rank)，和子問題的類收縮（shr_like_w和shr_like_z），以及若干(lam)和(beta)分量的更新等步驟。上述步驟都有顯式求解，可以折合成有限個標量或矢量的乘法和加法。其主要運算量在p、及子問題，BCS-TV在這2步中包含多次采用矢量減法的梯度變換和反變換，計算復雜度比需采用矢量乘法的dct更低，BCS-MV由于需要多計算dwt的正反變換，故計算復雜度居中。

根據(jù)上述分析，表1和表2歸納了影響參考算法和本文算法的重構質(zhì)量和復雜度的要素。

表1 重構質(zhì)量要素對比

表2 重構復雜度對比

綜上所述，可知BCS-SPL-DCT、DWT、DDWT、CT的重構質(zhì)量級別分別是最差、中等、良好、良好，復雜度級別為較低、中等、高、中等。BCS-TV重構性能良好，復雜度最低；BCS-MV重構質(zhì)量最好，復雜度居中，合理分配BCS-MV各正則項的權值可以在重構質(zhì)量和速度間取得較好的平衡。此外，由于本文算法具有可計算的收斂性保證[14,17]，重構速度隨測量率變化波動不大。

4 實驗測試

為驗證本文算法的性能，采用Matlab軟件對4種BCS-SPL（-DCT、-DWT、-DDWT、-CT）和本文算法（BCS-TV、BCS-MV）進行仿真測試，以重構前后圖像的峰值信噪比（PSNR）和結(jié)構相似度(SSIM）反映重構質(zhì)量，以重構時間反映計算復雜度。測試素材取自6幅尺寸為256×256的經(jīng)典灰度圖像lenna、goldhill、barbara、mandrill、peppers和bridge，圖像塊的尺寸設為32×32（即==32），按列掃描。已知高斯矩陣與任意稀疏基線性無關[3,11]，故以之為測量算子。為了公平起見，小波和雙樹小波變換均采用4層，輪廓波按參考程序默認配置。實驗平臺是配置為Intel(R) Core i5-2520M CPU, 主頻2.50 GHz，內(nèi)存3.05 GB的聯(lián)想筆記本。

6種塊壓縮感知重構算法的、和重構時間曲線如圖1~圖3所示。

上述各圖展示了幾種塊壓縮感知重構算法在不同采樣率下重構質(zhì)量和時間代價的對比情況?？梢钥闯?，BCS-SPL-DCT的重構性能最差，BCS-SPL-DWT優(yōu)于-DCT，但僅對barbara做很高采樣時才能取得最好的。當測量率較小時，BCS-SPL-DDWT重構獲得的占一定優(yōu)勢，但是重構時間偏長。隨著采樣率的增大，BCS-SPL-CT的重構速度優(yōu)勢進一步體現(xiàn)，當僅有bridge獲得高于-DDWT的。而BCS-TV重構算法總能取得較好的性能，隨著采樣率升高，增長最快。尤其對于分段平滑的lenna、goldhill、peppers和bridge，BCS-TV在各種采樣率情況下都能取得很高的和。BCS-MV重構的和最高，即使對于紋理豐富的barbara和mandrill也能優(yōu)于其他算法。本文算法與上述BCS-SPL相比，約提高1.5 dB，約提高0.05 dB。此外，前4種BCS-SPL算法的重構時間都隨著采樣率的變化產(chǎn)生較大的波動，而BCS-TV和BC-MV的重構時間相對穩(wěn)定，BCS-TV的運行速度最快，這對于實時處理和重構時間預計具有一定優(yōu)勢。

圖4至圖9展示了當測量率為50%時，不同測試圖像采用BCS-SPL-DDWT、BCS-SPL-CT、BCS-TV、BCS-MV 4種算法重構圖像的主觀質(zhì)量對比。

從6組重構效果對比圖可以看出，BCS-SPL-DDWT和BCS-SPL-CT算法重構的層次感和對比度較好，但噪聲顆粒稍大，舒適度不及本文算法。BCS-TV算法重構的圖像比較柔和，噪聲小，主觀上感覺清晰度和舒適度稍好。BCS-MV重構的清晰度、層次感和舒適度均是最佳。

(a)原始圖像256×256 mandrill，采樣率50% (b)BCS-SPL-DDWT PSNR:21.9 dB, SSIM:0.70 (c)BCS-SPL-CT PSNR:21.9 dB, SSIM:0.71 (d)BCS-TV PSNR:21.9 dB, SSIM:0.75 (e)BCS-MV PSNR:22.2 dB, SSIM:0.76

(a)原始圖像256×256 bridge，采樣率50% (b)BCS-SPL-DDWT PSNR:27.1 dB, SSIM:0.81 (c)BCS-SPL-CT PSNR:27.5 dB, SSIM:0.83 (d)BCS-TV PSNR:28.7 dB, SSIM:0.87 (e)BCS-MV PSNR:28.7 dB, SSIM:0.87

5 結(jié)束語

為了在低復雜度條件下提高現(xiàn)有塊壓縮感知重構算法的性能，本文提出了基于變分模型的塊壓縮感知算法BCS-TV和BCS-MV。編碼端首先將圖像分解成若干不重疊塊，接著按列掃描，然后分塊測量得到若干測量值列矢量。解碼端首先將接收到的測量值列矢量整合成矩陣，以圖像正則項的稀疏性為先驗知識，以最小化增廣拉格朗日函數(shù)為目標，采用變型的交替方向乘子法依次求解子問題，重構出圖像塊的列矢量空間，最后經(jīng)過反掃描并組合成圖像。其創(chuàng)新點在于：以少量的運算代價將全變分模型應用到塊壓縮感知重構框架中，并將其擴展為可容納多個正則項的具有通用性的混合變分模型。對照現(xiàn)有塊壓縮感知重構算法，仿真結(jié)果表明，BCS-TV能取得較好的SSIM和最快的重構速度，BCS-MV的SSIM和PSNR均達最佳，而且它們還具有重構時間隨測量率變化波動不大的優(yōu)點，特別適合具有穩(wěn)定傳輸時延的圖像和視頻等多媒體數(shù)據(jù)的處理場合。鑒于BCS-MV算法具有靈活的可擴展性，下一步計劃將其用于視頻壓縮感知中，有望提高現(xiàn)有基于塊的視頻壓縮感知的總體性能。

[1] 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.

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

[3] ELDAR Y C, KUTYNIOK G. Compressed Sensing: Theory and Applications[M]. USA:Cambridge University Press, 2012.

[4] LU G. Block compressed sensing of natural images[C]//The 15th International Conference on Digital Signal Processing. Cardiff, c2007: 403-406.

[5] THONG T D, TRAC D T, LU G. Fast compressive sampling with structurally random matrices[C]//The 2008 IEEE International Conference on Acoustics, Speech and Signal Processing(ICASSP). Las Vegas, USA, c2008: 3369-3372.

[6] MUN S, FOWLER J. E. Block compressed sensing of images using directional transforms[C]//Data Compression Conference(DCC). Snowbird, Utah, c2010: 547.

[7] FOWLER J E, MUN S, TRAMEL E W. Block-based compressed sensing of images and video[J]. Foundations and Trends in Signal Processing, 2012(4): 297-416 .

[8] THONG T D, LU G, NAM H N, et al. Fast and efficient compressive sensing using structurally random matrices[J]. IEEE Transactions on Signal Processing, 2012, 60(1): 139-154.

[9] ARMIN E, HAN L Y, CHRISTOPHER J R, et al. The restricted isometry property for random block diagonal matrices[J]. Applied and Computational Harmonic Analysis, 2015, 38(1): 1-31.

[10] VAN T C, DINH K Q, JEON B. Edge-preserving block compressive sensing with projected landweber[C]//The 20th International Conference on Systems, Signals and Image Processing (IWSSIP). Bucharest, Romania, c2013: 71-74.

[11] FOUCART S, RAUHUT H. A Mathematical Introduction To Compressive Sensing[M]. Springer New York Press, USA.2013.

[12] LI C B. An Effcient Algorithm For Total Variation Regularization With Applications To The Single Pixel Camera And Compressive Sensing[D].Rice University, 2009.

[13] LI C B. Compressive Sensing For 3d Data Processing Tasks: Applications, Models And Algorithms[D]. Rice University, 2011.

[14] HE B S, TAO M, YUAN X M. A splitting method for separable convex programming[J]. IMA Journal of Numerical Analysis, 2014, (1): 1-33.

[15] HE B S, LIAO L Z, WANG X. Proximal-like contraction methods for monotone variational inequalities in a unified framework I: Effective quadruplet and primary methods[J]. Computation Optimization Application, 2012, (51): 649- 679.

[16] HE B S, LIAO L Z, WANG X. Proximal-like contraction methods for monotone variational inequalities in a unified framework II: General methods and numerical experiments[J]. Computation Optimization Application, 2012, (51): 681-708.

[17] GU G Y, HE B S, YUAN X M. Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach[J]. Computation Optimization Application, 2014, (59): 135- 161.

Reconstruction algorithm for block compressed sensing based on variation model

CHEN Jian, SU Kai-xiong, YANG Xiu-zhi, ZHENG Ming-kui, LIN Li-qun

(College of Physics and Information Engineering, Fuzhou University, Fuzhou 350116, China)

The algorithms for block compressed sensing based on total variation and mixed variation (abbreviated as BCS-TV and BCS-MV) models were proposed to improve the performance of current reconstruction algorithms for the block-based compressed sensing. In the measuring phase, an image was sampled block-by-block. In the recovering period, it took the sparse regularization of the natural image as a priori knowledge, and approached the target function within the whole image through the modified augmented Lagrange method and alternating direction method of multipliers (ALM-ADMM). The method proposed achieves average PSNR gain of 1.5 dB and SSIM gain of 0.05 at a more stable running speed, over the previous uniformly block-based compressed sensing. It is particularly suitable for the applications of the multimedia data processing with fixed transmission delay.

total variation, image reconstruction, block compressed sensing, alternating direction method of multipliers

TN911.73

A

10.11959/j.issn.1000-436x.2016011

2014-12-23；

2015-05-11

蘇凱雄，skx@fzu.edu.cn

國家自然科學基金資助項目(No.61471124，No.61571129)；福建省自然科學基金資助項目(No.2013J01234，No.2014J01234，No.2015J01251)；福建省科技重大專項基金資助項目(No.2014HZ0003-3)；福建省教育廳基金資助項目(No.JA14065)

The National Natural Science Foundation of China(No.61471124, No.61571129), The Natural Science Foundation of Fujian Province(No.2013J01234, No.2014J01234, No.2015J01251), The Major Technology Project of Fujian Province(No.2014HZ0003-3), The Education Department Project of Fujian Province(No.JA14065)

陳建（1981-），女，福建福州人，福州大學講師，主要研究方向為視頻編解碼、壓縮感知。

蘇凱雄（1959-），男，福建羅源人，福州大學教授、博士生導師，主要研究方向為多媒體通信、數(shù)字電視廣播。

楊秀芝（1963-），女，山西靈石人，福州大學教授、碩士生導師，主要研究方向為圖像處理、數(shù)字電視技術。

鄭明魁（1976-），男，福建閩侯人，福州大學副教授，主要研究方向為多媒體視頻編碼。

林麗群（1980-），女，福建莆田人，福州大學講師、博士生，主要研究方向為圖像處理。