分塊子空間追蹤算法

莊燕濱王化程

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

關鍵詞：信號處理；壓縮傳感；稀疏表示；重構算法；匹配追蹤

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

1引言

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

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

4實驗結果及分析

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

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

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

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

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

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

6結論

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

參考文獻

[1]李樹濤，魏丹. 壓縮傳感綜述[J]. 自動化學報， 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]. 北京： 北京交通大學碩士論文， 2009，

[4]傅迎華. 可壓縮傳感重構算法與近似 QR 分解[J]. 計算機應用， 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]范曉維， 劉哲，劉燦. 分塊可壓縮傳感的圖像重構模型[J]. 計算機工程與應用， 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]李波， 謝杰鎮，王博亮. 基于壓縮傳感理論的數據重建[J]. 計算機技術與發展， 2009， 19（5）：23-25.

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