基于自適應分塊和聯合優化光滑l0范數的二維壓縮感知算法

張小貝 唐 辰 涂喜梅 陸曉剛 張 琦

①(上海大學通信與信息工程學院 上海 200444)

②(上海飛機設計研究院 上海 201210)

1 引言

壓縮感知(Compressed Sensing, CS)在21世紀初被Candes等人提出[1]，CS能在低于奈奎斯特采樣頻率下對信號采樣，從而減少圖像在傳輸過程中的數據量，解決資源浪費等問題[2,3]。壓縮感知的核心是信號的壓縮觀測和重構，如何充分利用圖像的稀疏性和精確重構成為關鍵[4]。

傳統的圖像壓縮感知通常將圖像轉換為1維信號，再采用經典的壓縮感知模型進行壓縮。由于圖像數據量大，造成測量矩陣變大，引起了空間的浪費和計算復雜度上升。2009年Mun等人[5]提出了均勻分塊的壓縮感知(Block Compressed Sensing,BCS)，雖然分塊減小了測量矩陣的大小，但均勻分塊引起的塊效應導致重構效果不佳。2017年何敬祿[6]提出基于自適應分塊的壓縮感知和平滑投影Landweber(Smooth Project Landweber, SPL)的重構算法，但由于自適應分塊算法復雜和SPL迭代周期多，導致計算時間較長。最直接重構的方式就是求解l0范數最優解，2008年Mohiman等人[7]提出了光滑l0范數(Smooth l0, SL0)重構算法，采用高斯函數逼近l0范數，將離散l0范數最小值問題轉化為函數最小化問題。基于SL0算法，2018年孫娜等人[8]提出了基于擬牛頓法的SL0算法，雖然提升了重構質量，但時間效率上依然存在不足。

為進一步提升壓縮和重構性能，本文提出一種基于自適應分塊和聯合優化SL0的2維壓縮感知算法(2-Dimension Compressed Sensing algorithm based on Adaptive Blocking and Joint optimization Smooth l0norm, 2D-ABCS-JOSL0)。在壓縮時以灰度熵為依據，采用四叉樹算法對圖像進行自適應分割和壓縮采樣率分配，然后使用改進的2維壓縮感知模型和混沌循環矩陣進行壓縮。在重構過程中，通過在目標函數中引入正則項和再加權函數，利用復合三角壓縮函數，結合擬牛頓法，采取動態收縮因子和動態迭代終止條件的方案，對SL0算法進行聯合優化，實現對圖像快速精確重構。

2 壓縮感知理論基礎

傳統的圖像壓縮感知過程如式(1)所示[1]。其中，Y ∈Rm×n(m ?n) 為觀測結果，Φ ∈Rm×n為測量矩陣，X ∈Rn×n為原始圖像，S ∈Rn×n為稀疏系數，Ψ ∈Rn×n為一組正交基將圖像進行稀疏表示。

重構原始信號可通過l0范數最小化求解，其數學模型如式(2)所示[9]

其中，X?∈Rn×n為重構圖像，SL0算法采用如式(3)的高斯族函數[7]對l0范數擬合。

式(3)中xi為稀疏系數，i為系數序號，σ為平滑因子，m為稀疏向量X的長度。當σ不斷縮小時，使得Fσ(X)逼近l0范數。最后利用最速下降法和梯度投影[10]，逐步迭代逼近最優解。

3 壓縮重構算法2D-ABCS-JOSL0

本文提出的2D-ABCS-JOSL0算法流程如圖1所示。在發送端，首先對圖像進行自適應分塊和壓縮采樣率分配，并利用新的2維壓縮感知模型和混沌循環矩陣進行壓縮，最后將像素值歸一化。在接收端，首先對圖像反歸一化，然后使用2維聯合優化的SL0(2-Dimension Joint Optimization Smooth l0norm, 2D-JOSL0)算法重構，最后進行塊組合輸出一張完整的重構圖像。

圖1 2D-ABCS-JOSL0算法流程圖

3.1 自適應分塊

圖像通常存在平滑區和紋理區[11]，應針對不同類型的區域進行分塊和采樣率的分配，從而提升重構質量和減少測量矩陣大小[12]。灰度熵表現了圖像內容復雜程度的估計，熵越大，圖像內容越豐富[13]。本文提出的自適應分塊具體流程如圖2所示。基于四叉樹算法，首先將圖片進行4等分，計算每個圖像塊的灰度熵，若熵大于閾值Tc，則繼續4等分，直到塊大小不大于 8×8或者熵小于閾值時，停止分割。在得到圖像塊序列后，需對每個圖像塊分配合適的壓縮采樣率，具體分配如式(4)所示

圖2 圖像自適應分塊流程

其中，ri和hi為第i塊圖像塊的采樣率和熵，avg為熵平均值，CR為整體采樣率，c為最大和最小熵的差，b為圖像塊的數量。ri分別與hi，CR和c有關，熵越大，采樣率就越大，重構得就更精細[14]；圖像塊間差異越小，則c越小，或當CR越小時，采樣率就越平均，從而避免了采樣率過小而導致重構失真。

3.2 2維壓縮感知模型和聯合優化的SL0重構算法

本文提出的2維壓縮感知模型公式如式(5)所示，Y ∈Rm×m為觀測結果，Φ ∈Rm×n(m ?n)為測量矩陣，ΦT為Φ的轉置，X ∈Rn×n為原始圖像，W∈Rm×m為 噪聲，S ∈Rn×n為 稀疏系數，Ψ ∈Rn×n為一組正交基。

該模型在經典的CS模型基礎上，在圖像兩邊同時進行壓縮采樣，提升了模型的壓縮能力。同時，考慮到噪聲的影響，允許在重構過程中Y和ΦXΦT存在誤差，從而更有利于提高重構精度。2維聯合優化的SL0重構算法根據壓縮模型對重構目標函數進行了相應優化，借鑒了l2-SL0算法[15]和再加權函數[16]的思想，將有約束條件的最優化問題變換為無約束最優化問題，目標函數模型如式(6)所示

其中，xi為稀疏系數，ζ為參數，避免分母為0的情況。P的作用是把較大的權值賦予較小的稀疏分量，較小的權值賦予較大的稀疏分量，從而提升模型收斂速度。經實驗測試，當λ=5, ζ=31時重構效果最佳。

針對經典SL0算法采用的高斯函數逼近l0范數效果不佳的問題，本文提出了一種“陡峭性”更高的復合三角壓縮函數(Compound Trigonometric Compression function, CTC)如式(8)所示

其中，xi為稀疏系數，i為系數序號，σ為平滑因子。為驗證CTC函數近似l0范數的優越性，圖3給出了高斯函數、文獻[17]中近似雙曲正切函數、文獻[18]中復合三角函數和CTC函數在σ=0.1時的對比。

圖3 l0近似函數對比圖

由圖3可得，CTC函數“陡峭性”遠高于高斯函數，在理論上能夠提升模型收斂速度和重構性。經典的SL0算法采用最速下降法求解，雖然對初值要求低，計算量小，但收斂速度慢，易出現“鋸齒現象”[19]。擬牛頓法中的BFGS(Broyden Fletcher Goldfarb Shannon)方法[20]既提高了收斂速度又避免了牛頓法中需要求解2階梯度出現病態問題的可能，但BFGS對初值的選取較為嚴格，若不接近近似解則可能無法收斂。故本文結合二者方法，先使用最速下降法求出近似解，再將近似解作為BFGS的初值繼續求解。首先，計算式(6)中F(X)的最速下降梯度方向

其中，?Fσ(X)為CTC函數的1階導數

3.3 測量矩陣

壓縮感知理論中指出，測量矩陣需要滿足有限等距原則[9]。由于混沌序列具有很強的隨機性，能夠極大概率地滿足有限等距性質。同時循環矩陣由于結構上的特殊性，能夠提高信號的恢復效果[21]，故本文采用Logistic混沌系統[22]和循環矩陣的特點，建立如式(13)所示測量矩陣。式(13a)為測量矩陣結構，式(13b)為Logistic混沌，m, n為測量矩陣的寬和長，ai ∈(0,1) 為混沌序列值，μ∈(0,4]為參數。通過對主對角線元素乘10，在合理范圍內擴大了每個待測信號對應位置在測量值上的分量，更有利于信號的重構。

3.4 歸一化函數

經過壓縮觀測后，觀測值會出現小數或超過[0,255]的范圍。本文使用式(14)所示的線性歸一化方法。其中，min和max分別為像素最小和最大值，xi為原始值，為歸一化后值，為向下取整。

4 仿真與分析

為驗證本文提出的2D-ABCS-JOSL0算法性能，選取了Set11和Set14圖像集的Peppers, Lena,Boat, Barbara, Goldhill, Mandrill, 6幅常用于壓縮感知大小為 256×256的灰度圖進行仿真，如圖4所示。仿真使用的硬件為搭載Intel(R) Core(TM)i5-11300H @ 3.10GHz CPU的計算機，仿真平臺為Python 3.6。

圖4 6幅測試圖像

本文采用峰值信噪比(Peak Signal to Noise Ratio, PSNR)和結構相似性指數(Structural SIMilarity Index, SSIM)作為性能指標來比較算法的重構性能，計算公式如式(15)、式(16)所示。其中，p，q為兩幅圖像，Xq和Xp為像素矩陣，m, n為矩陣長和寬，μp,μq分別為像素平均值，σp,σq為方差，σpq為協方差，c1, c2為參數，c1=Z1L, c2=Z2L,Z1=0.01, Z2=0.03，L=255。當PSNR越大，SSIM越接近于1時，表明圖像重構性能越好。

4.1 參數設置

一張灰度圖像素熵最大為8 bit。經多次仿真測試后得出結果，當熵值超過70%最大熵值時，圖像通常存在豐富的細節內容，故本文選取熵值Tc=5.6 bit作為閾值。如圖5所示，為圖像在經過四叉樹算法自適應分塊后的結果。可以觀察到較大的圖像塊內容較為平坦，較小的圖像塊存在豐富的紋理細節，可見本文提出的自適應分塊算法能根據圖像內容有效地進行自適應圖像塊劃分。

圖5 圖像自適應分塊后結果

在測量過程中，使用離散余弦變換(Discrete Cosine Transform, DCT)作為稀疏基。值得注意的是，為保證歸一化后的分布范圍，需要在DCT變換前對圖像所有像素點灰度值減去128。為保證序列存在較強的隨機性，Logistic混沌系統選取a0=0.5為初值，參數μ=3.99，并先迭代1 000次消除混沌系統的暫態效應。

4.2 單一優化方法性能對比

本文提出的2D-ABCS-JOSL0算法聯合了多種優化方法，為驗證每一種方法對性能的提升，令基于自適應分塊的SL0算法、基于2維聯合優化的SL0算法為方法1、方法2，均采用高斯矩陣進行測量，并對方法1、方法2和分別采用高斯矩陣及混沌循環矩陣的SL0算法與本文算法對比。圖6和圖7分別給出了6幅圖像在從10%～90%情況下的PSNR和SSIM曲線變化圖，可以明顯的觀察到，PSNR和SSIM曲線對比圖幾乎都呈現相同的趨勢，每一種單獨優化的算法，在性能指標上都有一定的提升。

圖6 圖像單一優化算法PSNR對比

從測量矩陣角度，使用高斯矩陣的性能低于混沌循環矩陣，尤其在壓縮采樣率較低的情況下，提升效果更明顯。這是因為本文采用的測量矩陣結構特殊，能夠在測量結果中保留大量的原信號分量。從SL0重構角度觀察，在低壓縮采樣率情況下，方法2體現了更大的優勢，這是因為方法2對壓縮和重構模型進行了優化，在保證重構效果的前提下，提高了壓縮率。而方法1在較高的采樣率情況下優勢更大，這是因為方法1充分利用了圖像塊的信息，使得塊大小和采樣率分配得更加均衡。本文算法結合了上述方法的優點，使得性能得到了極大的提升。相較于傳統的SL0算法，PSNR和SSIM分別平均提升了16.4 dB和71.69%。

4.3 不同算法性能對比

本文選取了目前在2維壓縮、分塊壓縮、數學模型等方面優化的算法BCS-SPL[5]、基于圖像信息量差異和SPL的自適應塊壓縮感知方法(Adaptive Block Compressed Sensing based on the Difference of Image and SPL, ABCSDI-SPL)[6]、2維Landweber投影算法(2D Projected Landweber,2DPL)[23]、基于多尺度分塊壓縮感知和SPL的全變差算法(Total Variation based multiscale BCS and SPL, TV-MS-BCS-SPL)[24]進行對比。表1列出了6幅圖像分別在壓縮采樣率10%, 30%, 50%, 70%時的PSNR和SSIM結果。圖8和圖9展示了在30%壓縮采樣率下Lena和Barbara圖像各算法重構效果對比圖。本文提出的算法對于不同圖像性能都優于目前現有的算法，PSNR平均提高2.70 dB，最大提高6.70 dB, SSIM平均提升8.43%，最大提升27.03%，在30%采樣率情況下，視覺效果良好，無明顯的噪聲與偽影。BCS-SPL采用了固定大小的分塊和采樣率，導致明顯的塊效應，重構結果最差。ABCSDI-SPL和TV-MS-BCS-SPL通過自適應或多尺度的方法緩解了塊效應，但TV和SPL都融入了平滑算法，紋理細節存在一定的丟失。2DPL采用了2維壓縮感知的思想，在所有對比算法中提供了較好的重構質量，這是因為2維壓縮感知從數學模型上進行了修改，能在不減弱重構效果的同時提升壓縮效果，但由于2DPL沒有充分利用圖像塊間的內容，重構效果存在不足。本文提出的算法，既充分利用了圖像塊間的內容，采用了自適應分塊的方法；又優化了壓縮感知模型，通過2維壓縮感知提升壓縮效果；還對SL0算法進行優化，使得算法能實現高精度重構。從側面說明，2D-ABCS-JOSL0算法能在重構性能相同的情況下，提供更低的壓縮采樣率。

表1 不同圖像不同算法PSNR(dB)/SSIM(%))對比

圖8 30%壓縮采樣率下不同算法Lena圖像結果對比

4.4 計算時間對比

圖10給出了6幅圖像在不同壓縮采樣率下的平均計算時間，由圖可知本文算法計算時間平穩，穩定性優于其他優化算法，對于一張 256×256大小的圖片，平均計算時間減少了11.87 s。這是由于本文算法采用了計算量小的自適應分塊算法，減少了運算復雜度，同時在重構過程中通過聯合優化的方法加快了模型的收斂速度。但由于計算步驟的增多，相比經典的SL0算法平均增加了1.15 s，但重構質量大幅度提升，整體運算時間也僅需1.59 s，能在較短的時間內提供較高的重構質量，故本文算法依然有很強的實用性。

圖10 不同算法計算時間對比

5 結論

針對傳統圖像壓縮感知性能不佳和SL0重構算法精度低、計算時間長等問題，本文提出了2DABCS-JOSL0算法。在壓縮過程中采用四叉樹算法依據灰度熵對圖像進行快速自適應分塊和壓縮采樣率分配；同時在壓縮模型中增加壓縮維度，考慮噪聲影響，采用混沌循環矩陣進行壓縮，提高了模型的壓縮性能。在重構過程中，將正則項和再加權函數引入目標函數；基于SL0算法，采用“陡峭性”更高的CTC函數，結合擬牛頓法和動態迭代的方案進一步提高了模型收斂速度和減少了運算時間。仿真結果驗證了所提算法能實現對圖像的高效壓縮和精確重構，具有良好的實用性和穩定性。