基于壓縮感知理論的分塊壓縮感知算法

黃 超，吳亞娟

（西華師范大學，四川 南充 637009）

0 引言

在信息處理領域，傳統的信息采集方式一直遵循著奈奎斯特采樣定理，即采樣率必須大于被采樣信號頻率兩倍才能完整重建信號。但是在一些特殊環境下，無法做到全采樣時，奈奎斯特采樣定理反而成了阻礙采樣行為的壁壘。文獻［1］提出是否可以用低于奈奎斯特采樣定理規定的兩倍采樣率采樣信號并重建信號。文獻［2］正式提出壓縮感知理論并指出壓縮感知突破的關鍵在于采樣方式。當我們說“采樣頻率”的時候，是做等間距采樣，數字信號領域通常都是做等間距采樣，也服從奈奎斯特采樣定律。壓縮感知則不同，壓縮感知采用的是不等間距采樣，因此隨機的亞采樣給予了恢復信號的可能性。隨機采樣使得信號頻譜不是整齊的平移，而是一小段一小段地隨機遷移，頻率泄露均勻地分布在整個頻域，所以泄露值都比較小，從而有了恢復的可能。

基于壓縮感知理論，誕生了許多不同的壓縮感知算法，但大致可以歸結為壓縮感知體系的三個部分：非稀疏信號的稀疏表達Ψx、稀疏后信號的觀測y=ΦΨx、觀測值的重構。由于待觀測信號事先是未知的，所以稀疏基的選取和觀測矩陣的選取就直接決定了重構算法是否能夠完整重構信號。重構時傳入的信號分別是觀測值y，稀疏基Ψ，觀測矩陣Φ。而觀測矩陣和稀疏基一般結合使用稱為信息算子或者傳感矩陣ACS=ΦΨ。

目前大多數的壓縮感知算法針對觀測矩陣和重構算法的研究都是對一維信號進行的壓縮觀測和重構［3-5］，不適用于處理大規模二維數據。針對這個問題，文獻［6］提出了一種改進的壓縮感知算法以用于處理二維信號，在解決二維數據無法直接運用壓縮感知處理的問題上有明顯效果。本文提出一種分塊存儲按列恢復的算法，并加入傳感矩陣的不相干性判斷，相比于不分塊的壓縮感知和文獻［6］提出的簡單分塊壓縮感知，本文算法平均運行時間更短、圖像恢復精度更高、觀測矩陣占用空間更小。

1 壓縮感知及重構算法

1.1 稀疏性

壓縮感知也可以叫做感知壓縮，即直接感知壓縮后的信號。基本理論支撐來自TAO［7］及Candes［8］從數學上證明的RIP 原則：即如果信號是稀疏的，那么它可以由遠低于采樣定理要求的采樣點重建恢復。

考慮到自然界中的一些非稀疏信號，需要作稀疏變換，使信號近似滿足稀疏性。若一個信號x 為非自稀疏信號，只要信號x 在某一個變換域滿足近似稀疏性，就可以在這個變換域中把x 看做稀疏信號，即可壓縮信號。我們稱這種變換域為稀疏域，重建將在稀疏域進行。這樣，壓縮感知就可應用于自稀疏信號與非自稀疏信號。

設x 是信號，Ψ 是稀疏基，θ 是x 在Ψ 中的稀疏。x 的稀疏表示為：

Ψθ 稱為x 的稀疏表示，當x 是本身稀疏時，稀疏基Ψ 就可以是單位陣，即X 本身自稀疏。當X是非稀疏信號時，稀疏基可以是離散傅里葉變換陣、離散余弦變換陣DCT、離散小波變換陣DWT 等常用頻域轉換矩陣，也可以是基于冗余字典的擴展稀疏陣［9-10］，還可以是其他針對特定信號的確定性矩陣。

1.2 觀測矩陣及RIP性質

合適的觀測矩陣是重構質量的前提保障，選擇合理有效的觀測矩陣可以保證重構質量以及高概率重構信號。觀測矩陣一般分為三種類型，高斯/伯努利型隨機測量矩陣，傅里葉/小波測量矩陣及衍生矩陣，其他測量矩陣如局部哈達瑪矩陣、Toeplitz 循環矩陣等確定性矩陣。

設y 是觀測值，觀測陣為Φ，稀疏基為Ψ ，信號為X。則x 的觀測值為：

公式（1）對應亞采樣過程，它將高維型號x 投影到低維空間。y 是一維的測量值，也是亞采樣后的結果。

因此，壓縮感知問題就是在已知測量值y 和測量矩陣Φ 的基礎上，求解欠定方程組y=Φx 得到原信號x。一般的自然信號x 本身并不是稀疏的，需要在某種稀疏基上進行稀疏表示。令x=Ψs，Ψ 為稀疏基矩陣，s 為稀疏系數。

于是最終方程就變成：y=ΦΨθ ，已知y、Φ、Ψ，求解θ。

當采集未知信號x 時，不可能事先對信號進行預稀疏化處理，所以稀疏基Ψ 一般在重建過程與觀測陣Φ 同時使用，令ACS=ΦΨ ，則ACS稱為信息算子或傳感矩陣。

Tao 等人證明［7］，觀測矩陣需滿足RIP 性質，即約束等距性。RIP性質如下：

對于任意和常數有：

然而，對于處理圖像的觀測矩陣來說，要去判斷其完整的RIP 性質滿足與否，是比較困難的，隨后，Baraniuk 證明，RIP 等價條件是觀測矩陣和稀疏基不相關。

相關性定義：

μ 越小，Φ 和Ψ 越不相關，等價于RIP 性質越滿足，則重構信號效果越好。

1.3 重構算法

在獲得線性觀測值之后，將觀測值y 和傳感矩陣ACS傳入重構算法中，以求得x 在Ψ 中的稀疏系數θ，則可以通過x-Ψθ 重構信號。目前重構算法多種多樣，大致可以分為三類：基于數學上求解l1范數［11］的凸優化類算法，比如BP 算法、內點法［12］，此類算法優點是重構精確度高，但是算法比較復雜難以硬件實現；基于MP 貪婪算法求解的衍生算法［6］，此類算法精確度不如凸優化類算法，但是優點是便于實現和求解概率較高；其他組算法，比如傅里葉采樣、鏈式追蹤等。

本文算法均采用OMP算法作為重構算法，采樣率為0.5進行實驗對比，保證重構算法為不變量，并使用不同尺寸的lena 圖像進行觀測和重構以研究算法在不同尺寸圖像觀測和重構時的性能。

算法步驟：

Step1 初始化x 為N=256 長度的信號，稀疏度K=30，x 的K 個位置隨機賦值1，其余位置為0，x 為一維離散稀疏信號

Step2 初始化觀測陣phi，初始化稀疏陣psi，初始化恢復向量x_r

Step3 觀測，y=phi*x

Step4 重構，此處用OMP 算法重構信號，求得θ，x_r=psi*θ

Step5 繪圖，計算殘差

測試不同大圖像對比結果如表1所示。

表1 隨機矩陣采樣率0.5，i7-10700k,32G,matlabR2017平臺

2 壓縮感知實現

2.1 一維信號

由圖1 可以看出，在K=30 時，當采樣率大于或者等于0.5以后，信號就能完整恢復。

由圖2可以看出，在采樣率P=0.5時，稀疏度K在大于或者等于30以后，開始出現信號恢復出錯的情況。

以上每個點數據都是測算10次后取的平均值，幾乎不存在偶然性，可以看出，對于一般一維稀疏信號，壓縮感知還是比較有效的，采樣率可以遠低于2倍采樣并且精確重構信號。

圖1 一維信號

圖2 不同采樣率下殘差

2.2 二維信號

如果用處理一維信號的壓縮感知來進行二維信號的處理時，會由于信號長度過大而導致觀測矩陣過大、恢復重構時間過長甚至不可處理一系列問題。處理二維信號的通常方法是將二維圖像矩陣變形成一維向量再進行觀測處理，這樣會導致數組爆炸，從而只能處理很小的圖像，或者對計算端的計算能力需求太大而不具實際意義。

不分塊的壓縮感知在處理不同大小圖像時的表現如下：用一般處理一維的方法處理二維圖像，處理時間近乎指數級增長，而且由于單次求解元素太多，導致精度難以得到保證，顯然不利于實際使用和實現。

2.3 分塊壓縮感知

分塊壓縮感知的提出是為了解決當圖像數據較大時，觀測矩陣占用內存太大和重建過程時間太長而提出的。運用分塊處理降低數據規模，把原始圖像分成若干大小相同的小塊，對每個小塊進行采樣和壓縮傳感，最后重構每個小塊至整個圖像，完成壓縮傳感重構。這種方法的優勢就是對每個小塊進行獨立測量，可以有效控制每次測量處理的數據規模，使用較小的觀測矩陣和傳感矩陣，保證算法運行時間不會隨圖像增大呈指數級增長，將算法運行時間控制在可接受范圍。

簡單分塊算法步驟：

Step1 輸入圖像X，將X 按bn*bn大小進行分塊，bn=8

Step2 對分塊循環執行觀測操作，觀測矩陣維數為bn*bn

Step3 對分塊循環執行

重構算法，將恢復的塊依次拼接到待恢復矩陣X_r

Step4 重構X_r，計算PSNR

測試不同大小圖像后對比結果如表2所示。

表2 隨機矩陣采樣率0.5，i7-10700k，32G，matlabR2017平臺

由表2 可以看出，分塊壓縮感知對算法速度的提升很大，并且可以處理超過256×256大小的圖像，算法運行時間也在可接受范圍內，但是重構質量并未得到提升。分塊壓縮感知最大的作用就是將二維圖像信息變得可處理，從數據來看，常規分辨率圖像都在可處理范圍，不會出現處理時間隨圖像增大而近乎指數級增長的情況。

3 算法

3.1 BSP-CS算法

對于上文提到的分塊壓縮感知，本文提出一種分塊存儲按列恢復的BSP-CS算法。與上文算法相比，分塊存儲可以模擬更真實的壓縮感知流程，按列恢復可以在二維觀測矩陣匹配圖像時使用更小的觀測矩陣，從而節約觀測和重構時間。

BSP-CS算法步驟：

Step1 輸入圖像X，

Step2 將X按bn*bn大小進行分塊，記錄每個分塊的位置信息bi

Step3 將分的塊依次通過觀測矩陣測量，將測量值存入yi

Step4 將測量值傳到重構端，依次讀取傳入的觀測值yi進行重構

Step5 將重構的圖像塊通過bi定位到圖像位置，更新恢復圖像X_r

Step6 重構X_r，計算PSNR

測試不同大小圖像后對比結果如表3所示。

表3 隨機矩陣采樣率0.5，i7-10700k，32G，matlabR2017平臺

由表3可以看出，本文算法運行時間極短，并且重構精度并未減少。相比于不分塊的方法，本文算法平均運行時間只有前者的1%，并且不會隨圖像增大而運算時間陡增。相比于簡單分塊的壓縮感知，本文算法平均運行時間只有前者的20%左右，提升明顯。

3.2 BSPI-CS算法

對于BSP-CS只提高了運算速度并未提升重構質量問題，結合壓縮感知原理，提出在觀測矩陣和稀疏陣的選擇時增加RIP 計算步驟，加入對傳感矩陣的不相干性判斷的BSPI-CS 算法以提高重構質量。由公式（3）可知，如果直接對觀測陣進行RIP判斷，通常比較困難。于是算法BSPI-CS 選擇第二種等效RIP 性質判斷方式，對觀測陣和稀疏陣進行不相關性判斷。由于觀測陣和稀疏陣都是預先設計好的，所以很容易判斷不相關性。

BSPI-CS步驟：

Step1 輸入圖像X，

Step2 將X按bn*bn大小進行分塊，記錄每個分塊的位置信息bi

Step3 根據公式（4）對設計的觀測陣和傳感陣進行不相關性判斷，直至得到滿足條件的傳感矩陣為止

Step3 將分的塊依次通過觀測矩陣測量，將測量值存入yi

Step4 將測量值傳到重構端，依次讀取傳入的觀測值yi進行重構

Step5 將重構的圖像塊通過bi定位到圖像位置，更新恢復圖像X_r

Step6 重構X_r，計算PSNR

測試不同大小圖像后對比結果如表4所示。

表4 隨機矩陣采樣率0.5，i7-10700k,32G,matlabR2017平臺

由表4 可以看出，因為加入了傳感陣不相干性判斷步驟，所以平均運行時間有所增加，在算法執行中對觀測陣和稀疏陣的選取決策時產生了額外時間，該時間不隨圖像大小而改變，只是圍繞一個固定值上下浮動。根據算法原理可以推測算法運行額外增加的時間是隨觀測矩陣的大小變化而變化的，當觀測矩陣不變時，額外增加的算法運行時間相差甚微。根據PSNR 值可以看出，由于加入了不相干性判斷，算法重構圖像的精度有了明顯提升，一般認為PSNR>30，則重構質量較好。

3.3 實驗數據對比

圖3 平均運行時間對比

圖3是固定采樣率為0.5，重構算法為OMP重構算法時，本文提到的各種算法的平均運算時間隨圖像增大的變化對比。可以看出，分塊算法BSP-CS在減少運行時間上效果與簡單分塊算法相比優勢明顯。

圖4 平均PSNR對比

圖4是固定采樣率為0.5，OMP重構算法時的平均PSNR 對比，可以看出BSPI-CS 算法在犧牲少量算法運行時長的情況下，穩定地提升了圖像重構的精度。

4 結語

在研究了壓縮感知算法后，本文提出了兩種算法，改進了觀測和重構運行時間，基于等效RIP性質的不相干性公式在重構算法開始前加入了傳感矩陣的不相干性判斷，提升了圖像重構精度。BSP-CS算法對縮短算法平均運行時間有明顯改進，BSPICS 算法則是犧牲一部分算法時間來提高圖像重構精度，兩種方法都對壓縮感知算法改進有一定的作用。