分塊子空間追蹤算法

莊燕濱王化程

摘要：壓縮傳感理論是一種充分利用信號稀疏性或者可壓縮性的全新信號采樣理論。該理論表明，通過采集少量的信號測量值就能夠?qū)崿F(xiàn)可稀疏信號的精確重構(gòu)。本文在研究現(xiàn)有經(jīng)典重構(gòu)算法的基礎(chǔ)上，提出結(jié)合圖像分塊思想和回溯思想的分塊子空間追蹤算法（Block Subspace Pursuit， B_SP）用于壓縮傳感信號的重構(gòu)。該算法以塊結(jié)構(gòu)獲取圖像，利用回溯過程實現(xiàn)支撐集的自適應(yīng)篩選，最終實現(xiàn)圖像信號的精確重構(gòu)。實驗結(jié)果表明，在相同測試條件下，該算法的重構(gòu)效果無論從主觀視覺上還是客觀數(shù)據(jù)上都有不同程度的提高。

關(guān)鍵詞：信號處理；壓縮傳感；稀疏表示；重構(gòu)算法；匹配追蹤

中圖分類號：TP301.6文獻標識碼：A

1引言

在傳統(tǒng)采樣中，為了避免信號失真，采樣頻率不得低于信號帶寬的2倍，這就是著名的香農(nóng)（Shannon）采樣定理。那么對于數(shù)字圖像、視頻數(shù)據(jù)的采樣，如果按照香農(nóng)定理采樣必定會產(chǎn)生大量數(shù)據(jù)，數(shù)據(jù)的存儲和傳輸將面臨巨大挑戰(zhàn)[1]。在2006年，由美國科學(xué)院院士D.Donoho和斯坦福大學(xué)的E.Candès提出的壓縮傳感（Compressive Sensing，CS）理論為解決這一問題帶來了曙光。其核心思想是將壓縮與采樣過程合二為一，首先以隨機投影方式采集稀疏信號的測量值，在采樣的同時完成了信號的壓縮，最終通過求解一個最優(yōu)化問題由測量值重構(gòu)出原始信號[2]。它突破了傳統(tǒng)香農(nóng)采樣定理的限制，在信號采樣的同時對數(shù)據(jù)進行適當?shù)膲嚎s，提高數(shù)據(jù)的使用效率，緩解了信號采樣、處理、傳輸和存儲過程中所面臨的越來越大的壓力，為信號獲取與傳輸帶來了革命性的進展。自從壓縮傳感理論提出以后就引起了信號領(lǐng)域相關(guān)研究人員廣泛地關(guān)注，其突出的優(yōu)點和廣闊的應(yīng)用前景使得它在信號處理領(lǐng)域展現(xiàn)出了旺盛的生命力。壓縮傳感理論為信號的采集提供了全新的視角，目前已被廣泛應(yīng)用于壓縮成像、模擬/信息轉(zhuǎn)換、信號采集、醫(yī)學(xué)圖像處理和壓縮雷達成像等眾多領(lǐng)域[3]。

信號重構(gòu)算法作為壓縮傳感理論的核心內(nèi)容，通過求解一個最優(yōu)化問題從低維數(shù)據(jù)中最大程度地恢復(fù)原始高維數(shù)據(jù)，這對于信號的精確重構(gòu)及采樣過程中的準確性驗證均具有重要意義[4]。本文將重構(gòu)算法中的分塊思想與回溯思想相結(jié)合，提出一種分塊子空間追蹤法（Block Subspace Pursuit， B_SP），實驗結(jié)果表明，該算法能夠顯著地提高圖像的重構(gòu)質(zhì)量、降低重構(gòu)時間，因而具有良好的應(yīng)用前景。2壓縮傳感與重構(gòu)算法

4實驗結(jié)果及分析

為了檢驗分塊子空間追蹤算法（B_SP）的正確性和有效性，使用MATLAB仿真軟件對本文算法進行各項測試。采用像素為256×256的cameraman圖像作為測試對象，并與OMP算法，SP算法，ROMP算法，CoSaMP算法進行對比。

實驗中，采用離散輪廓波變換對圖像進行稀疏化表示，能夠有效捕捉圖像的輪廓和邊緣信息，計算復(fù)雜度較低，在高維圖像重構(gòu)質(zhì)量上具有較大優(yōu)勢。測量矩陣選用分塊廣義輪換測量矩陣，編碼時不用對整個圖像進行測量，只需對每一塊進行線性測量后即可進行后續(xù)的處理，不僅提高了測量效率，且能使重構(gòu)圖像的均方差更小。

圖1給出了cameraman圖像在采樣率（M/N）為0.1，0.2，0.3，0.4，0.5時，得到B_SP算法的重構(gòu)結(jié)果。

從五種不同采樣率下得到cameraman（256×256）圖像的重構(gòu)效果可以看出，當采樣率M/N=0.1時，僅僅能分清人物的基本輪廓，重構(gòu)后圖像模糊不堪。在低采樣率下，分塊重構(gòu)思想割裂了塊與塊之間的相關(guān)性，塊與塊之間的重構(gòu)圖像會出現(xiàn)明顯的“割裂”現(xiàn)象，嚴重影響了重構(gòu)效果。當采樣率不斷地提高M/N=0.2，0.3時，這種想象會逐步地得到改善。當采樣率提高到M/N=0.4，0.5時，塊與塊之間的“割裂”現(xiàn)象會明顯消除，從直觀視覺上來看，重構(gòu)質(zhì)量明顯提高。當采樣率M/N=0.5時，重構(gòu)算法OMP，SP，StOMP，CoSaMP，ROMP，B_SP算法對cameraman（256×256）圖像的重構(gòu)效果對比。

由圖2可以直觀看出，在采樣率同為M/N=0.5的情況下，B_SP算法的重構(gòu)質(zhì)量明顯優(yōu)于其他經(jīng)典的匹配追蹤系列算法，重構(gòu)后圖像的細節(jié)部分較為完整的呈現(xiàn)出來。從直觀的視覺感覺上來說，cameraman的頭部、遠處建筑等重構(gòu)效果都有很大程度的提高。

通過表1中七種算法在采樣率為50%時，得到運行時間、峰值性噪比（PSNR）、匹配度相關(guān)參數(shù)的對比。統(tǒng)一選取cameraman（256×256）作為處理對象，在運行時間上，最快的是ROMP算法，最慢的是CoSaMP算法，這是因為算法運行過程中引入回溯的思想，耗時較長；在峰值信噪比方面，顯然B_SP算法具有絕對優(yōu)勢，在處理對象的時候采用分塊的思想，不僅可以減少重構(gòu)算法運行過程中所需的存儲量同時重構(gòu)圖像塊更易實現(xiàn)；在匹配度方面，B_SP算法也是這幾種算法中的最高值，達到了0.9999。

6結(jié)論

本文在研究了各種壓縮傳感經(jīng)典重構(gòu)算法的基礎(chǔ)上，提出結(jié)合了分塊和自適應(yīng)篩選思想的B_SP算法，具有相對運行時間較短、重構(gòu)質(zhì)量高的特點。該算法以塊結(jié)構(gòu)獲取圖像，可以實現(xiàn)圖像實時傳輸和提高計算速度。然后再采用子空間追蹤算法對每一個圖像塊進行重構(gòu)，該算法是一種兩階段的回溯性貪婪算法，沿用了匹配追蹤算法一貫的原子選擇準則，首先選擇高度可靠的原子作為原始原子集，每次迭代的過程中選擇K（稀疏度）個原子加入原始原子集，但也會刪除同樣數(shù)量的原子，不斷更新原子集，數(shù)量始終保持為K個，當最后完成迭代時用K個原子進行稀疏逼近原始信號，實現(xiàn)對原子的最優(yōu)化選擇。實驗結(jié)果表明，在相同的測試條件下，該算法的重構(gòu)效果無論從主觀視覺上還是客觀數(shù)據(jù)上都得到了較為滿意的結(jié)果，具有一定的應(yīng)用前景。

參考文獻

[1]李樹濤，魏丹. 壓縮傳感綜述[J]. 自動化學(xué)報， 2009， 35（11）：1369-1377.

[2]MENG J， LI H，HAN Z. Sparse event detection in wireless sensor networks using compressive sensing[C]. Information Sciences and Systems， 2009. CISS 2009. 43rd Annual Conference on， IEEE， 2009：181-185.

[3]高睿. 基于壓縮傳感的匹配追蹤重建算法研究[D]. 北京： 北京交通大學(xué)碩士論文， 2009，

[4]傅迎華. 可壓縮傳感重構(gòu)算法與近似 QR 分解[J]. 計算機應(yīng)用， 2008， 28（9）：2300-2302.

[5]MALLAT S G，ZHANG Z. Matching pursuits with time-frequency dictionaries[J]. Signal Processing， IEEE Transactions on， 1993， 41（12）：3397-3415.

[6]RAUHUT H，SCHNASS K，VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. Information Theory， IEEE Transactions on， 2008， 54（5）：2210-2219.

[7]范曉維， 劉哲，劉燦. 分塊可壓縮傳感的圖像重構(gòu)模型[J]. 計算機工程與應(yīng)用， 2009， 45（29）：153-155.

[8]DUARTE M F，DAVENPORT M A，TAKHAR D，LASKA J N，SUN T， KELLY K F，Baraniuk R G. Singlepixel imaging via compressive sampling[J]. Signal Processing Magazine， IEEE， 2008， 25（2）：83-91.

[9]李波， 謝杰鎮(zhèn)，王博亮. 基于壓縮傳感理論的數(shù)據(jù)重建[J]. 計算機技術(shù)與發(fā)展， 2009， 19（5）：23-25.

[10]劉丹華， 石光明，周佳社. 一種冗余字典下的信號稀疏分解新方法 [J]. 西安電子科技大學(xué)學(xué)報， 2008， 35（2）：228-232.