基于自適應采樣及平滑投影的分塊壓縮感知方法

石翠萍， 王立國， 那與晶， 黃柏鋒

(1.哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001；2.齊齊哈爾大學 通信與電子工程學院，黑龍江 齊齊哈爾 161006；3.中國電信股份有限公司河池分公司，廣西 河池 547000)

傳統的采樣定理要求采樣頻率至少是信號帶寬的2倍，才能完全恢復出原信號。隨著信號帶寬的日益增加，傳統的采樣定理對采樣速率要求越來越高。隨著壓縮感知(compressive sensing，CS)概念的提出，由于其允許采樣和壓縮同時進行，且對采樣速率要求很低，故壓縮感知迅速成為研究熱點[1-2]。壓縮感知是在遠小于奈奎斯特采樣率的條件下，通過隨機采樣來獲取離散信號。該理論指出一個可壓縮信號或在變換域為稀疏的信號，可通過一個與變換基無關的測量矩陣，將變換后的高維信號投影到低維空間，并采用優化算法從少量投影中完成高質量重構。近年來，基于壓縮感知的圖像采樣和重構引起了人們的廣泛關注[3-8]。在傳統方法中，圖像壓縮通常在變換域內進行，而壓縮感知可以直接作用在原始圖像上，并可通過任意CS重構技術來恢復圖像[9]。將壓縮感知算法應用到二維圖像上時，面臨的一個挑戰在于重建多維信號需要巨大的計算量。另外，當隨機采樣算子表示為一個稠密矩陣時，會帶來很大的存儲負擔。為了解決這些問題，有效的方法是將圖像劃分為若干塊，然后以塊為單位進行采樣[10]。文獻[11]提出了基于平滑投影重建的塊壓縮感知算法(block-based CS with smoothed projected Landweber reconstruction, BCS-SPL)。相比于對整幅圖像直接處理，能夠減小測量矩陣所需的存儲空間。同時，在采樣端對分塊信號采樣時直接進行壓縮，降低了采樣端的復雜度。這種塊處理方法能夠實現圖像快速重建，但這是以重建圖像質量變差為代價的。此外，分塊壓縮感知還容易出現塊效應現象。文獻[12]提出了一種基于非局部相似模型的壓縮感知恢復算法，將傳統的二維圖像塊的稀疏性擴展到相似圖像塊組在三維空間上的稀疏性，在提高圖像表示稀疏度的同時，提高了壓縮感知圖像恢復效率，使恢復圖像在紋理和結構保持方面有了較大的改善，提高了重建圖像質量。文獻[13]提出了一種基于秩極小化的壓縮感知圖像恢復方法，將相似圖像塊作為列向量構建一個二維相似塊矩陣，然后將壓縮感知測量作為約束條件，通過增廣拉格朗日方法將受限優化問題轉換為非受限優化問題，對二維相似塊矩陣進行恢復求解。文獻[14]提出了一種加權結構組稀疏表示的圖像壓縮感知重構方法，其采用非局部相似圖像塊結構組加權系數表示的L1范數作為規則化項，進行優化重構約束，能夠在更好地恢復圖像高頻信息的同時，減少圖像低頻成分的損失，從而改善圖像重構質量。文獻[15]在BCS-SPL的基礎上，提出了一種基于多假設預測的塊壓縮感知方法(multihypothesis predictions BCS-SPL, MH-BCS-SPL)，該方法先用初始BCS-SPL方法對圖像進行重建，然后在CS隨機投影域內對每個圖像塊進行多假設預測。相比于BCS-SPL方法，MH-BCS-SPL能較大程度改善重建圖像質量，但重建時間卻大大延長了。從重建圖像質量的角度，對整幅圖像采樣的結果，要優于局部采樣的結果。一個典型的例子是基于全變差(total-variation, TV)的壓縮感知方法，其能得到較高質量的重構圖像，但重構時間也特別長[16]。可見，重構圖像質量和重構時間，往往是矛盾的。為了實現2者間的相對平衡，文獻[17]提出了一種基于多尺度變量的塊壓縮感知方法(multiscale variant BCS-SPL, MS-BCS-SPL)，該方法是在離散小波變換(Discrete wavelet transform, DWT)域內進行的。其重構圖像的速度只比BCS-SPL略慢，但能獲得重構質量上較大的增益。然而，MS-BCS-SPL方法對小波域內各層子帶中的各子塊，均采用相同的采樣速率。由于小波子帶間信息量差別很大，這種采樣方式會限制重構質量的提升。針對該問題，本文在MS-BCS-SPL方法的基礎上，通過研究圖像上下文特征，同時考慮掃描順序對圖像重構性能的影響，提出了一種基于自適應采樣及平滑投影的分塊壓縮感知方法。

1 改進的多尺度塊及平滑投影的壓縮感知算法

對傳統塊壓縮感知算法，在對原始圖像信號進行采樣時，各圖像塊往往采用固定的采樣率。這種不考慮圖像內容的采樣方式，限制了壓縮感知算法性能的提升。本文提出了一種改進的多尺度塊及平滑投影壓縮感知算法。首先，通過分析圖像上下文特征，同時考慮掃描順序對圖像重構性能的影響，設計了一種面向分塊的自適應掃描和采樣方法。該方法充分利用了子帶中各塊對圖像重構的不同貢獻，基于塊內容進行子帶自適應采樣率計算。然后，采用基于迭代投影的壓縮感知重建算法進行圖像重構。實驗結果表明，本文方法能夠有效提升整體重構圖像質量，且重構速度更快。改進的多尺度塊及平滑投影的壓縮感知算法整體框架如圖1所示。

圖1 本文算法整體框架Fig.1 The overall flow chart of the proposed method

1.1 自適應采樣率的計算

分塊壓縮感知(block-based CS，BCS)先將目標圖像信號變換到小波域，然后分割成大小相同但不重疊的塊。每個圖像塊大小為B×B，采用相同的觀測矩陣ΦB分別對每個塊進行觀測。假設xi是第i塊的原始輸入圖像，則其輸出分塊可表示為：

yi=ΦBxi

(1)

式中:ΦB是矩陣為MB×B2的觀測矩陣，ΦB與圖像塊不相關。xi是具有B2個樣本的列矢量。在BCS中，整個測量矩陣Φ變為塊對角結構，可表示為：

(2)

對BCS來講，其塊采樣率為R=MB/B2。基于BCS的算法對圖像進行采樣時，只需存儲大小為MB×B2的觀測矩陣對每個圖像塊進行觀測即可，降低了計算成本和存儲要求。然而，這種方法對每個圖像塊采用相同的采樣率，這較大地限制了重構圖像的質量。事實上，由于各高頻子帶反映的圖像信息不同，且子帶間的信息量可能相差很多，不同的塊采樣順序和采樣率會導致重構圖像質量相差很多，故本文采用了一種基于自適應采樣順序和采樣率的方法。

設原始圖像為X，具體步驟如下：

1)用A表示變換矩陣，經L級小波變換后，變換圖像為：

Y=[(Y)(1)(Y)(2)… (Y)k)]

(3)

式中k表示小波子帶總數。

2)對每個子帶(Y)(i),(i=1,2，…,k)，其高頻子帶的能量為：

(4)

式中：c(m,n)表示子帶中(m,n)位置處的系數；P和Q分別表示子帶的行和列。

3)將高頻子帶按能量Ei降序的順序，確定子帶間的掃描順序。即：

(5)

式中permu表示子帶順序的重排。

4)設子帶(Y)(i)的能量為Ei，子帶的基礎采樣率為Ri，其內部被分割為N個塊，塊大小為B×B。對每一個塊Bl，其塊采樣率為：

(6)

式中：el是第l個塊的能量；rl表示計算出的該塊的采樣率。

可以使用最小線性均方誤差準則(MMSE)估計出較好的初始圖像，以此可以加速重構過程。在MMSE中，圖像塊的初始解計算公式為：

(7)

式中ρ的取值為0.9～1。通過仿真得知，只有當ρ取值為0.95，分塊尺寸B取值為32時，圖像重建效果最佳。

1.2 平滑投影算法

原始的Landweber算法是一種簡單的線性恢復方法，該算法適用于簡單的一維信號重建，而對于圖像信號卻不是很適用。當圖像信號的亮度值趨近于0時，若采用Landweber算法進行迭代，則在恢復過程中可能會出現亮度值為負的情況[15]。另外，原始的Landweber算法收斂速度比較慢，這增加了重構時間，并且很難選擇到對應該算法的一個合適的松馳參數。

本文采用了一種基于迭代投影的CS重建算法，該算法將投影Landweber算法應用到CS中[12]。實現過程主要包含2步：先進行初始化x[0]=ΦTy，然后再進行n+1次迭代過程，從x[n]產生近似圖像x[n+1]。具體過程為：

傳統的BCS-SPL算法雖然改善了重構圖像的塊效應，但是在平滑塊效應和噪聲的同時，也把圖像信號中存在的一些邊緣和紋理平滑了，這使得圖像的邊緣和紋理信息變得模糊。本研究采用了一種基于迭代投影的CS重建算法，對每一圖像塊分別進行投影，改善了重構圖像信號中存在的邊緣模糊的問題。

本文優化的多尺度塊及平滑投影壓縮感知算法重構圖像的過程，主要根據各子塊及對應的采樣率rl，求出各層子塊中各塊的測量向量和測量矩陣，在進行平滑投影Landweber重建算法進行圖像重構的過程中，先通過測量向量和測量矩陣求出小波域圖像，然后進行逆變換，并采取維納濾波去除塊效應。在此期間，平滑投影和濾波操作持續交替的進行迭代，直到恢復圖像。

2 實驗結果分析

為了驗證本文算法的有效性，這里將本文算法與BCS-SPL、基于梯度投影的稀疏重建(gradient projection for sparse reconstruction, GPSR)[17]、TV、MH-BCS-SPL 4種算法進行比較。實驗選取了不同場景的6幅圖像作為測試圖像，包括人物、物體以及自然景象。圖像具有不同的復雜度，其中，Lena、pepper相對平滑，goldhill、Barbara、mandrill具有復雜的紋理，SanDiego是遙感圖像，其反映的是城市地貌，包含了大量的紋理細節。每幅圖像的大小均為512×512，測試圖像如圖2所示。

圖2 測試圖像集Fig.2 The test image set in this paper

實驗分塊大小均采用8×8。在采樣率為0.1～0.5時，對lena圖像分別采用上述5種算法進行重構，并對重構圖像的峰值信噪比(peak signal to noise ratio, PSNR)進行比較，結果如圖3所示。實驗根據基礎采樣率計算得到的各塊采樣率，保留到小數點后5位。由圖3可見，相比于其他4種方法，本文方法在圖像的重構質量上具有較大的優勢。對于其他5幅測試圖像，其重構圖像對應的PSNR結果，分別見表1～表5。

為了進一步驗證本文算法，在采樣率為0.3時，對這5種算法的平均重構時間進行了比較。實驗中計算機硬件配置為Intel i5-3317U處理器，1.7 GHz，4 G內存，Windows 7系統。編程語言為Matlab。實驗結果見表6。

由圖3以及表1～表6的結果可知，在0.1～0.5的采樣率下，本文提出的多尺度塊及平滑投影壓縮感知算法，總體上比其他5種算法得到的圖像重構質量更高。

圖3 采用5種方法對Lena圖像的重構結果比較Fig.3 The comparisons of reconstructed images obtained by five methods for Lena

表1 peppers圖像上各項算法PSNR結果對比Table 1 The PSNR comparison of different methods on pepper dB

表2 goldhill圖像上各項算法PSNR結果對比Table 2 The PSNR comparison of different methods on goldhill dB

表3 Barbara圖像上各項算法PSNR結果對比Table 3 The PSNR comparison of different methods on Barbara dB

表4 Mandrill圖像上各項算法PSNR結果對比Table 4 The PSNR comparison of different methods on Mandrill dB

表5 SanDiego圖像上各項算法PSNR結果對比Table 5 The PSNR comparison of different methods on SanDiego dB

表6 6種算法重構時間比較Table 6 Comparison of reconstruction time of six algorithms

相比于常見的BCS-SPL算法，采用本文算法得到的重構圖像，其PSNR值要提高1～3 dB，證明了本文算法的有效性。從計算復雜度上看，本文算法是在MS-BCS-SPL算法上的改進。相比于MS-BCS-SPL，本文算法增加了子帶間掃描順序的確定及子帶塊自適應采樣率的計算。設圖像大小為M×N，小波分解層數為J，則乘法計算次數為CM=MN(1-1/22J)，加法計算次數為CA=MN(1-1/22J)-3J-1，比較次數為CM=2J。其中，增加的乘法主要是平方運算。平方運算的實現并不復雜。由表5可見，從重構時間上看，本文算法所需時間比MS-BCS-SPL略長。但相比于其他4種算法，本文算法所需的重構時間還是短很多。

下面對一些紋理信息較多的圖像結果進行分析。以Barbara圖像為例，由表1～6可見，相對于BCS-SPL算法，本文算法無論是重構圖像的PSNR值，還是重構時間，均能得到更好的結果；相對于TV算法，本文算法的重構質量基本與TV算法重構質量持平，本文算法更明顯的優點在于算法的重構時間，對比TV算法，本文算法所需時間大大減少。在個別采樣率下，MH-BCS-SPL算法的圖像重構質量要優于本文算法，但MH-BCS-SPL算法的缺點在于時間過長，本文算法在重構時間上有較大優勢。對于細節和紋理較多的圖像，本文算法重構質量有時優勢不明顯。其原因在于：較少的平滑區域會導致信號更難稀疏，而一些計算復雜度較高的算法，如GPSR算法，其采用了凸優化，這使得該算法利用L1范數求解優化問題時，得到的局部最優解為全局最優解。這種重構性能的提升是以大幅犧牲圖像重構時間為代價的。盡管如此，在大多數情況下，本文方法的重構質量，依然優于GPSR算法。對于SanDiego圖像，其細節信息也較多，但采用本文方法，在多個采樣率下，均能得到最佳的性能，進一步證明了本文方法的有效性。與MS-BCS-SPL方法相比，本文算法采用了塊自適應采樣率計算，在給定基礎采樣率下，能夠根據各塊對重構的貢獻動態分配采樣率，故能得到更好的重構質量。這種優勢在低碼率的情況下更為明顯。這是由于低碼率下，對有限比特數的不同分配方法，對整幅圖像重構效果影響更大。

圖4給出了采樣率為0.1時，分別采用本文算法和其他5種算法，得到的重構圖像及殘差圖像的結果比較。可見，與其他算法相比，本文算法的殘差相對小一些，尤其是在方框內的區域。結合表6的結果可知，本文算法在重構時間上具有較大的優勢，不同于一般的以犧牲重構圖像質量為代價換取重構速度的算法，本文算法得到的總體重構質量依然較好，證明了本文算法的有效性。

圖4 不同算法的圖像重構圖像及殘差圖像比較Fig.4 Comparison of the reconstructed images and the error images with different methods

3 結論

1)本文提出的基于自適應采樣及平滑投影的分塊壓縮感知方法，通過對圖像內容的分析，同時考慮掃描順序對重構性能的影響，較好地解決了傳統壓縮感知方法由于固定碼率分配從而限制了稀疏表示性能的問題。

2)本文提出的方法重構速度很快，且能得到質量較好的重構圖像。

本文提出的算法僅是從稀疏效果的角度進行設計，并未考慮圖像的后續應用。在一些應用中，有時會對圖像稀疏提出特別要求，比如保留小目標。在特定應用背景下設計高效的壓縮感知算法，將作為下一步工作進行探索研究。