分塊篩選自適應(yīng)壓縮感知重構(gòu)算法

鄧 垚 李登峰

(武漢紡織大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院 湖北 武漢 430200)

0 引 言

在傳統(tǒng)的香農(nóng)定理?xiàng)l件下，信號(hào)的傳輸和存儲(chǔ)過程中為避免信號(hào)的失真，要求采樣率不得低于信號(hào)最高頻率的兩倍。然而，對(duì)于圖像和視頻這種類型數(shù)據(jù)的獲取，往往會(huì)產(chǎn)生大量的數(shù)據(jù)，尤其在圖像和視頻分辨率越來越高、對(duì)帶寬要求更大的今天，勢(shì)必造成傳輸和存儲(chǔ)的硬件成本升高。在此背景下，不依賴信號(hào)頻率、且在采樣的同時(shí)就能完成壓縮的壓縮感知[1-2]理論一經(jīng)提出，就引起學(xué)術(shù)界和工業(yè)界的極大興趣和廣泛關(guān)注。

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

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

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

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

1 壓縮感知和重構(gòu)算法

1.1 壓縮感知

考慮一個(gè)實(shí)值的有限長(zhǎng)一維離散時(shí)間信號(hào)x[6]。實(shí)際應(yīng)用中，信號(hào)x本身很少是稀疏的，但在某個(gè)正交基Ψ上的變換系數(shù)是稀疏的或者是可壓縮的。因此我們就能對(duì)信號(hào)x作線性變換：

x=Ψθ

(1)

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

考慮另一個(gè)與Ψ不相關(guān)的觀測(cè)矩陣Φ，大小為M×N,M?N。對(duì)信號(hào)x進(jìn)行觀測(cè)：

y=Φx

(2)

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

y=Φx=ΦΨθ=Acsθ

(3)

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

1.2 重構(gòu)算法

信號(hào)在經(jīng)過字典Ψ的稀疏化及觀測(cè)矩陣Φ的壓縮后得到觀測(cè)向量y，重構(gòu)便是通過y恢復(fù)原始信息的過程。本文提出的算法不局限具體算法，任何采用隨機(jī)觀測(cè)矩陣的算法都能經(jīng)由本算法運(yùn)行。但為了實(shí)驗(yàn)進(jìn)行和具有可對(duì)比性，本文選用貪婪迭代類重構(gòu)算法。

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

算法1 OMP算法

輸入：M×N測(cè)量矩陣Φ,M維測(cè)量值＄y＄,信號(hào)x的稀疏度K

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

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

第3步 利用最小二乘法求得信號(hào)的估計(jì)

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

2 分塊篩選自適應(yīng)算法

本文提出的分塊篩選自適應(yīng)算法，主要包括四個(gè)部分：圖像分塊、塊篩選、自適應(yīng)觀測(cè)矩陣篩選和圖像重構(gòu)。

2.1 圖像分塊

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

2.2 塊篩選

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

對(duì)于某個(gè)分塊，可以得到其平均灰度μ：

(4)

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

(5)

則平滑度定義為：

(6)

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

圖1 Lena圖

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

圖2 分塊按平滑性篩選后的結(jié)果

2.3 自適應(yīng)觀測(cè)矩陣篩選

由于觀測(cè)矩陣Φ較小，隨機(jī)性遠(yuǎn)不如傳統(tǒng)的大尺寸觀測(cè)矩陣，因而重構(gòu)結(jié)果隨機(jī)波動(dòng)較大。圖3為觀測(cè)矩陣未經(jīng)篩選時(shí)生成效果截然不同的兩幅圖像。

圖3 Φ未經(jīng)篩選的隨機(jī)波動(dòng)

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

(7)

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

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

圖4 兩種用于判斷的隨機(jī)塊

2.4 圖像重構(gòu)

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

算法2 本文算法

觀測(cè)端輸入：N×N原始圖像X, 分塊邊長(zhǎng)bn,bn×bn稀疏矩陣Ψ

圖像分塊：

分步1 若圖像不是bn的整數(shù)倍，分塊前對(duì)圖像進(jìn)行邊緣填充；

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

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

塊篩選：對(duì)于平滑度S大于閾值θS的塊標(biāo)記為1，小于閾值的標(biāo)記為0；

自適應(yīng)觀測(cè)矩陣篩選：

分步1 分別從標(biāo)記為1和0的分塊，隨機(jī)抽取列制成兩種平滑判斷塊；

分步2 生成對(duì)應(yīng)的大小為m1×bn和m0×bn的高斯隨機(jī)矩陣Φ1和Φ0，其中bn>m1>m0;

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

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

分步5 觀測(cè)：對(duì)標(biāo)記為1和0的塊分別用Φ1和Φ0進(jìn)行觀測(cè)，得到各塊的觀測(cè)ybi，其中bi為第i個(gè)分塊在原圖中的位置索引。

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

重構(gòu)端輸入：為觀測(cè)端的輸出

輸入引入重構(gòu)算法，每塊分別進(jìn)行重構(gòu)，然后再按位置索引重組；

3 實(shí) 驗(yàn)

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

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

通過以上參數(shù)設(shè)置可以發(fā)現(xiàn)，觀測(cè)矩陣已經(jīng)大幅減小，采樣率也有所減小。

3.1 重構(gòu)速度比較

本部分實(shí)驗(yàn)比較重構(gòu)速度。實(shí)驗(yàn)引入算法為OMP算法、CoSaMP算法、ROMP算法和SAMP算法。運(yùn)行時(shí)間的計(jì)算范圍與本文所列的兩個(gè)算法流程圖對(duì)應(yīng)。每組算法實(shí)驗(yàn)次數(shù)各100次。實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 平均運(yùn)行時(shí)間比較

圖5橫坐標(biāo)表示不同算法作為引入算法和算法本身，縱坐標(biāo)對(duì)應(yīng)的平均重構(gòu)時(shí)間，單位為s?？梢钥闯觯谂cOMP算法、CoSaMP算法和SAMP算法的比較中，本文算法的重構(gòu)速度大幅快于引入的重構(gòu)算法。但與ROMP算法相比，本文算法略慢。通過分析，實(shí)際程序中最耗時(shí)的是矩陣的乘法運(yùn)算。已知矩陣乘法的運(yùn)行時(shí)間復(fù)雜度為O(nd), 其中n為方陣的邊長(zhǎng)。對(duì)于樸素的常規(guī)算法，d=3。1981年，Pan的算法[19]將d降至了2.494。經(jīng)過20多年的研究，2014年Gall將d降至了2.372 863 9[20]。容易計(jì)算分塊算法矩陣乘法部分的時(shí)間復(fù)雜度為：

(8)

式中：b為分塊的邊長(zhǎng)。

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

3.2 重構(gòu)質(zhì)量比較

對(duì)于重構(gòu)算法，提高運(yùn)行速度、降低采樣率這兩者與重構(gòu)質(zhì)量通常是不可兼得的。本文算法緩解該問題的方法主要是自適應(yīng)觀測(cè)矩陣這一步驟。該部分實(shí)驗(yàn)環(huán)境和狀態(tài)依然同上一小節(jié)。質(zhì)量的評(píng)估采用峰值信噪比PSNR。首先，以O(shè)MP作為引入算法為例，對(duì)比加入自適應(yīng)篩選觀測(cè)矩陣和未篩選的重構(gòu)質(zhì)量。實(shí)驗(yàn)進(jìn)行15次，結(jié)果如圖6所示。

圖6 重構(gòu)質(zhì)量波動(dòng)比較

由圖6可以發(fā)現(xiàn)，由于分塊后的觀測(cè)矩陣Φ尺寸較小，未經(jīng)自適應(yīng)觀測(cè)矩陣處理的算法因隨機(jī)性不足，難以保證Φ與每塊分塊的不相關(guān)性，因此呈現(xiàn)較大的波動(dòng)；而引入算法OMP由于擁有大得多的觀測(cè)矩陣，因而能以較大概率滿足RIP性質(zhì)，實(shí)驗(yàn)結(jié)果也反映了其穩(wěn)定性。而在經(jīng)過自適應(yīng)觀測(cè)矩陣處理后的分塊算法，其穩(wěn)定性較未經(jīng)處理的分塊算法大幅上升。同時(shí)，與引入算法比較可以發(fā)現(xiàn)，雖不如其穩(wěn)定，但重構(gòu)質(zhì)量都較其有所提升。

接下來，對(duì)比OMP、CoSaMP、ROMP和SAMP作為引入算法的實(shí)驗(yàn)。每組算法依然執(zhí)行100次，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 實(shí)驗(yàn)結(jié)果

可以發(fā)現(xiàn)，本文算法重構(gòu)質(zhì)量與引入算法相當(dāng)，其中OMP作為引入算法時(shí)，重構(gòu)質(zhì)量最佳，甚至超過了所有引入算法本身。

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

表1 資源占用對(duì)比

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

4 結(jié) 語(yǔ)

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