分塊篩選自適應壓縮感知重構算法

鄧 垚 李登峰

(武漢紡織大學數學與計算機學院 湖北 武漢 430200)

0 引 言

在傳統的香農定理條件下，信號的傳輸和存儲過程中為避免信號的失真，要求采樣率不得低于信號最高頻率的兩倍。然而，對于圖像和視頻這種類型數據的獲取，往往會產生大量的數據，尤其在圖像和視頻分辨率越來越高、對帶寬要求更大的今天，勢必造成傳輸和存儲的硬件成本升高。在此背景下，不依賴信號頻率、且在采樣的同時就能完成壓縮的壓縮感知[1-2]理論一經提出，就引起學術界和工業界的極大興趣和廣泛關注。

壓縮感知包括三個部分，即信號的稀疏表示、稀疏信號的壓縮觀測以及壓縮信號的恢復重構。其中重構算法是該理論能否實踐的關鍵環節。目前，重構算法主要分為三大類：貪婪迭代算法、凸優化重構算法和組合優化算法。其中組合優化類算法重構效果較好，但對采樣結構要求很嚴格，實際應用時受硬件約束較大。凸優化類算法需要的采樣值少，計算精度較高，但計算復雜度高、速度慢，難以滿足實際應用。貪婪迭代類算法的運行時間及采樣效率上都在上述兩類算法之間，因其結構簡單、運算量小，兼顧了運行效率和采樣效率，所以獲得了廣泛的研究和應用。

在實際應用中，由于隨機矩陣尤其是高斯隨機矩陣與任意正交字典都具有較強的不相關性，因此絕大部分算法都使用隨機矩陣作為測量矩陣，從而在信號恢復時，除了需要觀測信號y、字典矩陣Ψ外，還需要完整的觀測矩陣Φ。對于圖片和視頻等數據，這意味著每幅圖像、每一幀畫面都要提供一個完整大小的觀測矩陣。這樣無疑與壓縮感知的本意相違背，極大影響了其實際應用。除此之外，傳統的重構算法對整幅圖像按列處理，也使其程序執行效率低下。再者，大部分算法由于稀疏字典Ψ和觀測矩陣Φ都較大，評判壓縮重建條件的信息算子ACS的RIP、Spark常數和互相關系數等參考也很難獲得，所以不能據此調整所選矩陣。

相關研究人員采用了不同的方法，用于降低觀測矩陣和提高重構速度。例如：文獻[3]采用半張量積的方法，將觀測矩陣縮小至原來的1/256(甚至更低)；文獻[4-5]利用GPU并行化加速，大幅提高重構速度。

基于上述觀察，本文提出了一種分塊篩選自適應算法。該算法可以解決和改善如下問題：(1) 觀測矩陣過大占用較多資源；(2) 對于圖像信息重構速度較慢；(3) 不能自調整所選字典Ψ和觀測矩陣Φ組成的信息算子ACS使重構質量更好；(4) 以比引入重構算法更小的采樣率達到其相當的重構效果。

1 壓縮感知和重構算法

1.1 壓縮感知

考慮一個實值的有限長一維離散時間信號x[6]。實際應用中，信號x本身很少是稀疏的，但在某個正交基Ψ上的變換系數是稀疏的或者是可壓縮的。因此我們就能對信號x作線性變換：

x=Ψθ

(1)

式中：Ψ稱為字典矩陣或稀疏字典。

考慮另一個與Ψ不相關的觀測矩陣Φ，大小為M×N,M?N。對信號x進行觀測：

y=Φx

(2)

就可以得到M個線性觀測y∈RM。記信息算子Acs=ΦΨ，再由式(1)和式(2)可得：

y=Φx=ΦΨθ=Acsθ

(3)

式(3)也說明了壓縮感知的測量過程。壓縮感知方法的目的便是希望通過遠小于信號x數據量的觀測向量y來恢復信號的原始信息。由此可以看出，壓縮感知理論主要需解決的問題是在欠采樣情況下的信號重建[7]。

1.2 重構算法

信號在經過字典Ψ的稀疏化及觀測矩陣Φ的壓縮后得到觀測向量y，重構便是通過y恢復原始信息的過程。本文提出的算法不局限具體算法，任何采用隨機觀測矩陣的算法都能經由本算法運行。但為了實驗進行和具有可對比性，本文選用貪婪迭代類重構算法。

OMP算法[8-9]即正交匹配追蹤算法，它源于對匹配追蹤算法[10]的改進，是目前大部分貪婪迭代類算法的核心。其步驟如算法1所示。

算法1 OMP算法

輸入：M×N測量矩陣Φ,M維測量值＄y＄,信號x的稀疏度K

初始化：殘差r0=y,索引集Λ0=?,迭代次數t=1

第2步 更新索引集Λt=Λt-1∪{λt};

第3步 利用最小二乘法求得信號的估計

第5步 判斷是否滿足t>K,若滿足則停止迭代，否則執行第1步。

2 分塊篩選自適應算法

本文提出的分塊篩選自適應算法，主要包括四個部分：圖像分塊、塊篩選、自適應觀測矩陣篩選和圖像重構。

2.1 圖像分塊

假設圖像尺寸是n×n。為方便計算，分塊的大小選取邊長為2b個像素的正方形，1≤b≤log2n,b∈Z。傳統的分塊會將塊拉直為一列處理，這樣需要大小為22b列的觀測矩陣。為了讓觀測矩陣更小，本文保持分塊的原始形狀。例如對于一幅512×512的圖像，按8×8每小塊進行分塊，則觀測矩陣只有原來大小的1/4 096。需要說明的是，所有分塊共用同一個觀測矩陣。

2.2 塊篩選

將圖像分塊后，緊接著便可以進行塊篩選的工作。將塊分為平滑塊和非平滑塊兩類，平滑塊所含信息較少，可以用M更小的觀測矩陣觀測得到尺寸更小的觀測值；相應地，非平滑塊采用M更大的觀測矩陣，以獲得更多的細節信息。具體的篩選方法如下：

對于某個分塊，可以得到其平均灰度μ：

(4)

式中：L為灰度劃分的級數，例如256級；gi為灰度的取值，p(gi)為該灰度值的概率，即該灰度值出現次數的占比。因此可以得到灰度方差σ2：

(5)

則平滑度定義為：

(6)

對于恒定亮度的分塊，S為0；對于灰度值有最大偏離的分塊，S為1。這里以經典的Lena圖(圖1)為例，展示分塊篩選后的效果。

圖1 Lena圖

Lena圖尺寸為256×256，分塊大小為8×8。如圖2所示，黑線上方為平滑塊，下方為非平滑塊。

圖2 分塊按平滑性篩選后的結果

2.3 自適應觀測矩陣篩選

由于觀測矩陣Φ較小，隨機性遠不如傳統的大尺寸觀測矩陣，因而重構結果隨機波動較大。圖3為觀測矩陣未經篩選時生成效果截然不同的兩幅圖像。

圖3 Φ未經篩選的隨機波動

因此，需要對觀測矩陣Φ進行篩選。其中傳統的信息算子ACS=ΦΨ由于尺寸較大，所以要計算RIP[11-12]并反過來檢驗觀測矩陣的性能是難以實現的。但當A尺寸縮小到很小，與分塊一樣大時，通過RIP進行檢驗便成為可能。RIP定義如下：

(7)

式中：δS稱為受限等距常數[13]。Cai等[14]在2010年給出了新的RIC界：δS<0.307。

為了使所選的分塊能盡量代表全部塊，采用隨機取值的方法。以分塊大小等于bn×bn為例，對于篩選出的平滑塊，隨機選擇bn個平滑塊，然后從這被選中的bn個平滑塊中，各隨機抽取一列組成bn×bn大小的隨機平滑塊，例如分塊大小8×8，兩種隨機塊如圖4所示，最后再進行RIP檢測，篩選出符合的觀測矩陣Φ。

圖4 兩種用于判斷的隨機塊

2.4 圖像重構

得到分好類的分塊矩陣和經過篩選后得到的兩個觀測矩陣后，便可以進行圖像重構。可以選擇任意重構算法。本文選擇貪婪迭代類重構算法中具有代表性的OMP算法、CoSaMP算法[15]、ROMP算法[16-17]、SAMP算法[18]作為引入算法，對每個塊分別重構后，再重組為一幅完整圖像。本文算法流程如算法2所示。

算法2 本文算法

觀測端輸入：N×N原始圖像X, 分塊邊長bn,bn×bn稀疏矩陣Ψ

圖像分塊：

分步1 若圖像不是bn的整數倍，分塊前對圖像進行邊緣填充；

分步2 將圖像按每塊大小bn×bn分為nb塊，并記錄塊位置(下標)bi；

分步3 按式(6)計算每塊的平滑度S。

塊篩選：對于平滑度S大于閾值θS的塊標記為1，小于閾值的標記為0；

自適應觀測矩陣篩選：

分步1 分別從標記為1和0的分塊，隨機抽取列制成兩種平滑判斷塊；

分步2 生成對應的大小為m1×bn和m0×bn的高斯隨機矩陣Φ1和Φ0，其中bn>m1>m0;

分步3 從第一列開始，對每列按式(7)進行判斷；

分步4 如果有一列不滿足，則返回第2步，直到全部列滿足，得到最終的Φ1和Φ0;

分步5 觀測：對標記為1和0的塊分別用Φ1和Φ0進行觀測，得到各塊的觀測ybi，其中bi為第i個分塊在原圖中的位置索引。

觀測端輸出：X的分塊觀測集合{ybi|1≤i≤nb},觀測矩陣Φ1和Φ0, 相應的信息算子Acs1和Acs0

重構端輸入：為觀測端的輸出

輸入引入重構算法，每塊分別進行重構，然后再按位置索引重組；

3 實 驗

通過本文算法，希望解決如下問題：(1) 隨機觀測矩陣占用過多資源；(2) 圖像重構速度較慢；(3) 降低采樣率以繼續降低資源占用；(4) 保證重構的質量。

實驗硬件為Intel(R) Core(TM) i7-9700K處理器，軟件平臺為MATLAB 2018b。實驗材料選擇經典的Lena圖，圖片尺寸256×256。參數設置如下：分塊邊長bn=8, 平滑度閾值θS=0.002, 受限等距常數δS=0.307, 稀疏矩陣Φ。選為傅里葉矩陣，采樣率平滑部分為0.3、非平滑部分為0.5，對照算法采樣率為0.5。

通過以上參數設置可以發現，觀測矩陣已經大幅減小，采樣率也有所減小。

3.1 重構速度比較

本部分實驗比較重構速度。實驗引入算法為OMP算法、CoSaMP算法、ROMP算法和SAMP算法。運行時間的計算范圍與本文所列的兩個算法流程圖對應。每組算法實驗次數各100次。實驗結果如圖5所示。

圖5 平均運行時間比較

圖5橫坐標表示不同算法作為引入算法和算法本身，縱坐標對應的平均重構時間，單位為s。可以看出，在與OMP算法、CoSaMP算法和SAMP算法的比較中，本文算法的重構速度大幅快于引入的重構算法。但與ROMP算法相比，本文算法略慢。通過分析，實際程序中最耗時的是矩陣的乘法運算。已知矩陣乘法的運行時間復雜度為O(nd), 其中n為方陣的邊長。對于樸素的常規算法，d=3。1981年，Pan的算法[19]將d降至了2.494。經過20多年的研究，2014年Gall將d降至了2.372 863 9[20]。容易計算分塊算法矩陣乘法部分的時間復雜度為：

(8)

式中：b為分塊的邊長。

當以本實驗的圖像尺寸和分塊大小為例，d取最新的2.372 863 9時，在矩陣乘法部分，分塊速度是未分塊速度的3.641倍。再加上本文算法更低的采樣率，速度會進一步提高。

3.2 重構質量比較

對于重構算法，提高運行速度、降低采樣率這兩者與重構質量通常是不可兼得的。本文算法緩解該問題的方法主要是自適應觀測矩陣這一步驟。該部分實驗環境和狀態依然同上一小節。質量的評估采用峰值信噪比PSNR。首先，以OMP作為引入算法為例，對比加入自適應篩選觀測矩陣和未篩選的重構質量。實驗進行15次，結果如圖6所示。

圖6 重構質量波動比較

由圖6可以發現，由于分塊后的觀測矩陣Φ尺寸較小，未經自適應觀測矩陣處理的算法因隨機性不足，難以保證Φ與每塊分塊的不相關性，因此呈現較大的波動；而引入算法OMP由于擁有大得多的觀測矩陣，因而能以較大概率滿足RIP性質，實驗結果也反映了其穩定性。而在經過自適應觀測矩陣處理后的分塊算法，其穩定性較未經處理的分塊算法大幅上升。同時，與引入算法比較可以發現，雖不如其穩定，但重構質量都較其有所提升。

接下來，對比OMP、CoSaMP、ROMP和SAMP作為引入算法的實驗。每組算法依然執行100次，實驗結果如圖7所示。

圖7 實驗結果

可以發現，本文算法重構質量與引入算法相當，其中OMP作為引入算法時，重構質量最佳，甚至超過了所有引入算法本身。

表1為本文算法與引入算法資源占用的對比。

表1 資源占用對比

可以看出，同引入算法相比，本文算法占用資源有顯著降低。

4 結 語

本文針對壓縮感知在處理圖像信息時采用的隨機觀測矩陣過大問題，提出了分塊篩選自適應算法。此外，不同于其他分塊算法，本文算法根據圖像信息，加入了分塊平滑判斷，在降低采樣率上更進一步；另外，加入了觀測矩陣的自適應篩選，使重構質量和穩定性獲得提升。實驗結果表明，本文算法能在較小的觀測矩陣、更少的采樣率下，以更快的速度獲得與其他重構算法相當重構質量。與典型的OMP、CoSaMP和SAMP相比，速度得到極大提高；采用OMP作為引入算法的本文算法，重構質量與OMP、CoSaMP、ROMP和SAMP相比，均有所提高。相比其他算法，本文算法實際應用價值更高。