貪婪重構算法StOMP及其改進

陳艷良 戰(zhàn)蔭偉

貪婪重構算法StOMP及其改進

陳艷良 戰(zhàn)蔭偉

(廣東工業(yè)大學計算機學院 廣東 廣州 510006)

為了對新型的采樣定理：壓縮感知理論CS(Compressed Sensing)進行深入的研究并將其應用于圖像壓縮編碼，對壓縮感知中的貪婪重構算法進行綜述并分析該類算法的優(yōu)缺點。通過理論分析與仿真實驗，對比各算法的性能與效率。該類算法中StOMP需要人為地進行參數(shù)設置，而人為設置的參數(shù)值往往使算法的重建效果較差。針對該問題，利用粒子群優(yōu)化算法對StOMP中的參數(shù)進行配置，以此來提高StOMP的重建效果。實驗表明經過參數(shù)配置后的StOMP算法在重構效果上平均提高了2.62 dB，最大能提高13.63 dB。

壓縮感知 重構算法 匹配追蹤 粒子群算法

0 引 言

奈奎斯特采樣定理指出：為了避免信號失真，采樣頻率不得低于信號最高頻率的2倍[1]。 隨著社會信息化的不斷深入，人們對信息量的需求也在不斷上升，需要信號的帶寬也越來越寬。依照奈奎斯特采樣定理定然會導致海量的采樣數(shù)據，大大增加了存儲和傳輸?shù)拇鷥r，這無疑給信號處理的能力提出了更高的要求，也給相應的硬件設備帶來極大的挑戰(zhàn)。2006年提出的壓縮感知理論[2-4]是一個充分利用信號稀疏性或可壓縮性的全新信號采集、編解碼理論，它克服了傳統(tǒng)采樣定理的缺陷。該理論指出：對于稀疏或可壓縮的信號，能夠以遠低于奈奎斯特采樣率對其進行采樣，并通過重構算法來準確或近似地恢復該信號。壓縮感知在信號獲取的同時對數(shù)據進行適當壓縮。傳統(tǒng)的信號獲取和處理過程主要包括采樣、壓縮、傳輸和解壓四個部分，這種先對數(shù)據采樣后壓縮的處理方式，浪費了大量的傳感元、時間和存儲空間。而壓縮感知能夠將數(shù)據采集和壓縮合二為一，這一突出的優(yōu)點使其在信號處理領域中有廣闊的應用前景，如在圖像壓縮[5]、去噪[6]和視頻編碼[7]等應用中都取得了較好的效果。

壓縮感知理論主要包括三個部分：稀疏表示、觀測矩陣和重構算法。其中，重構算法作為壓縮感知的核心內容，它關系到能否快速、準確地恢復原始信號。目前，壓縮感知常用的重構算法主要包括兩類：一類是凸優(yōu)化算法，另一類是貪婪重構算法。凸優(yōu)化算法重構效果好，但其計算復雜度相當高。貪婪重構算法具有原理簡單、容易實現(xiàn)、運行速度快等優(yōu)點，雖然其重構質量略差于凸優(yōu)化算法，但由于該類算法在計算復雜度方面有很大的優(yōu)勢，所以在實際應用中使用廣泛。本文將對該類算法進行深入研究。

StOMP 算法[16]屬于貪婪重構算法，該算法需要人為地設置參數(shù)值，而經驗值往往不是最優(yōu)的參數(shù)配置。本文通過PSO算法對參數(shù)進行搜索，尋找最優(yōu)的參數(shù)配置。PSO是一種進化計算方法，同遺傳算法類似，是一種基于迭代的優(yōu)化算法。目前該算法已廣泛應用于函數(shù)優(yōu)化、神經網絡訓練和模糊系統(tǒng)控制優(yōu)化等領域。

1 壓縮感知理論

假設信號x∈RN和正交變換矩陣ψ∈RN×N，對信號進行變換有：

α=ψx

(1)

其中α∈RN。若K=‖α‖0且K?N，則認為信號x是稀疏的或可壓縮的，K稱為信號x的稀疏度。信號是否具有稀疏性是運用壓縮感知理論的前提條件。為了獲得α并使K盡可能小，通常要對x進行合適的變換。目前常用的變換有小波變換、傅立葉變換、余弦變換等。在已知信號是可壓縮的前提下，壓縮感知過程可分為以下兩步:

y=φx

(2)

(2) 利用重構算法，根據y∈RM重構原始信號x。

為了從y中恢復出信號x。將式(1)代入式(2)有：

y=φψ-1α

(3)

令Φ=φψ-1∈RM×N，Φ={φ1,φ2,…,φN}，則有：

y=Φα

(4)

由于Φ、y為已知，可以根據式(4)求解α，再根據式(1)即可恢復信號x。但由于式(4)是一個欠定方程，所以方程有無窮多解，故無法確定α。但是，如果信號x是稀疏的且Φ滿足有限等距性質RIP(Restricted Isometry Property)[8]，即對任意信號f和常數(shù)ε∈(0,1)，矩陣Φ滿足：

(5)

則可以通過求解以下問題來確定α：

min‖α‖0s.t.y=Φα

(6)

RIP的等價條件[9]是觀測矩陣和正交矩陣不相關。研究者已證明大多數(shù)隨機矩陣都滿足RIP[2,22]。壓縮感知中常用的觀測矩陣主要有高斯隨機矩陣、傅立葉隨機矩陣和哈達瑪矩陣等。

為了求解式(6)，許多有效的重構算法被相繼提出。目前，常用于壓縮感知的重構算法主要包括兩類，一類是凸優(yōu)化算法，另一類是貪婪重構算法。綜上可知壓縮感知的處理過程如圖1所示。

圖1 壓縮感知流程圖

凸優(yōu)化算法是將式(6)轉換為以下等價的凸優(yōu)化問題來進行求解：

min‖α‖1s.t.y=Φα

(7)

該類算法中常用的有：BP(Basis Pursuit)算法[10]、 內點法[11]、 梯度投影法[12]和同倫算法[13]等。該類算法的重構精度較高而且所需要的測量值較少，但是其計算復雜度相當高，比如BP算法的計算復雜度為O(N3)，所以只適合小規(guī)模問題的求解，在進行圖像處理時，常常不能滿足實時性要求。

貪婪重構算法對式(6)進行直接求解，其中具有代表性的算法有匹配追蹤(MP)算法[14]和正交匹配追蹤(OMP)算法[15]。后來出現(xiàn)了許多改進的匹配追蹤算法，其中包括分段正交匹配追蹤(StOMP)算法[16]、正則化正交匹配(ROMP)追蹤算法[18]和子空間追蹤(SP)算法[19]等。貪婪重構算法具有原理簡單、實現(xiàn)容易、運行快速等優(yōu)點。雖然其重構質量略差于凸優(yōu)化算法，但由于該類算法在計算復雜度方面有很大的優(yōu)勢，所以在實際應用中使用廣泛。

2 貪婪重構算法

2.1 算法分析

貪婪重構算法主要用于求解優(yōu)化問題：

min‖α‖0s.t.y=Φα

(8)

MP算法[14]是Mallat于1993年提出的，它是最早的一種貪婪重構算法。其基本思想是先從字典Φ中選擇與信號最匹配的原子φi0，i0滿足:

(9)

然后將y向φi0方向投影，則可分解為：

y=φi0+R1f

(10)

繼續(xù)對殘差R1f進行同樣的分解，令R0f=y，經過K步后有：

(11)

令:

(12)

αt=t=0,1,…,K-1

(13)

由于MP算法在每次迭代中只能保證新殘差與最后選擇的原子是正交的，而不能保證與之前選出的所有原子正交，使得每次迭代的結果可能是次優(yōu)的。這不僅減緩了算法收斂的速度、增加了計算復雜度，并且會影響重構精度。

StOMP算法[16]在OMP的基礎上提出了一種分段的策略，同時該算法在每次迭代中不止選擇一個原子，而是選擇若干個原子，選擇的規(guī)則是通過一個硬閾值τ來控制。而且StOMP算法的迭代次數(shù)n也是人為設置的。當τ設置過大，會影響算法的效率。當τ設置過小，則會增加選擇錯誤原子的概率，使得重構精度下降。因此，該算法中閾值設置是一個比較棘手的問題。該算法描述如下：

輸入:矩陣Φ,信號y,迭代次數(shù)n,閾值τ輸出:α初始化:殘差r0=y,支撐集I=?,α=0,t=1(1)根據閾值找出Φ中與rt-1匹配原子的索引。即:J=j>τ{}(j=1,2,…,N)(2)更新索引集:I=I∪J{}(3)更新解:α=Φ+Iy(4)更新殘差:rt=y-ΦIαI(5)若t=n則停止迭代,否則t=t+1,轉到(1)

ROMP算法[18]與OMP算法的不同之處在于每次迭代中選擇K個最匹配的原子，用下式表示：

(14)

但并沒有將這K個原子直接添加到支撐集中，而是利用正則化方法，對這些原子進行二次篩選，即先計算：

(15)

(16)

添加到支撐集中，舍棄其余原子。由上可知，正則化過程可以保證被舍棄原子的能量一定小于被選入原子的能量。從而提高重構精度，而且一次選入多個原子，重構速度也有所提高。

由式(14)可知ROMP算法的前提條件是已知信號的稀疏度，而這往往是難以做到的。對于自然信號其本身并不是稀疏的，需要經過變換才能變成稀疏信號，而且在不同的變換基下信號的稀疏度也是不盡相同的，這樣估計信號的稀疏度就存在一定的困難。若稀疏度估計過小，就會經過多次迭代依然不能滿足迭代停止條件；若稀疏度估計過大，則會大大影響重建效果。所以在不知道信號稀疏度的情況下，利用ROMP算法進行重構，誤差會較大，這也是制約ROMP算法在實際中應用的一個關鍵因素。

SP算法[19]是從子空間的角度出發(fā)，首先選擇一個含有K個原子的支撐集作為子空間，然后通過反復迭代更新子空間的原子，使其逐漸逼近真實支撐集。SP算法首次采用了回溯的思想，在每次迭代中對已經選入的原子同時進行檢測，剔除錯選的原子，選擇更加匹配的原子，以達到更高的重構精度。同ROMP算法一樣，SP算法也必須知道信號的稀疏度K。子空間的大小始終等于信號的稀疏度K，支撐集I中最多有2K個原子，所以每次迭代回溯時最多剔除K個原子。CoSaMP 算法與SP算法思想一致，唯一的區(qū)別在于：CoSaMP算法每次迭代時選擇2K個原子，而SP算法每次選擇K個，意味著CoSaMP算法[20]的運行效率要低于SP。

SAMP算法[21]是針對信號稀疏度問題提出來的，相對于ROMP算法和SP算法，其創(chuàng)新之處在于當信號的稀疏度未知時也可以精確地重構信號，從而在很大程度上擴大了該算法的使用范圍。SAMP 算法引入了分段的思想，其稀疏度自適應過程如下：首先設定一個固定的步長s，在第一個階段令K=s，在該稀疏度下進行迭代重建信號。若稀疏度是合適的，則迭代會一直進行下去直到滿足迭代停止條件。否則，說明稀疏度太小，需要增大，令稀疏度K=2s進入第二個階段繼續(xù)迭代。SAMP 算法在每一個階段中采用了回溯的方法來剔除錯選原子，從而使原子的選擇更加準確。

對初始步長的估計也是一個關鍵問題，步長估計準確與否直接關系到信號的重建效果。一般要求s

2.2 仿真實驗

上節(jié)對OMP[15]、ROMP[18]、SP[19]和SAMP[21]等算法的原理及步驟進行了詳細分析，為了說明貪婪重構算法的有效性并對比各算法的運行效率。本節(jié)將對這些算法進行仿真實驗。以MATLAB 2010b作為編程實驗平臺，用256×256的Lena、peppers、couple和camera作為測試圖像，以PSNR來衡量重建效果。n置為10，采樣率為M/N=0.5，利用重構算法對圖像進行恢復，表1記錄了各算法的運行時間，圖2顯示了重建的Lena圖像。

表1 運行時間比較(單位:秒)

圖2 重構算法性能比較

由實驗結果可知，貪婪重構算法能有效地重建原始信號，其中SAMP 算法的重構效果要優(yōu)于其他算法，但運行時間最長，主要是因為它需要逐步逼近信號的真實稀疏度。StOMP算法不僅在每次迭代時選擇多個原子，而且迭代次數(shù)少，因而運行時間最短。由于ROMP、SP 等算法需要信號的稀疏度作為先驗知識，而圖像的稀疏度是難以預測的，所以重構精度會受到影響，其中ROMP 算法所受影響較大，導致其重構效果較差。ROMP、SP 等算法比OMP 快是因為這類算法在每次迭代時能有效地選擇多個原子，而OMP 只選擇一個原子。整體而言，SP 算法不僅重構效果好，而且運行效率高，是一個較好的重構算法。

3 StOMP參數(shù)配置

StOMP 算法需要經驗性的設置閾值τ和迭代次數(shù)n，然而在不同的情況下，經驗設置往往不可靠。針對該問題，本文結合粒子群優(yōu)化算法對指定范圍的參數(shù)進行搜索，尋找最優(yōu)的參數(shù)配置。

粒子群優(yōu)化算法是美國電氣工程師Eberhart和社會心理學家Kenndy基于鳥群覓食行為所提出的優(yōu)化算法，簡稱粒子群算法PSO (Particle Swarm Optimization)[17]。該算法實現(xiàn)方便、收斂速度快、參數(shù)設置簡單，是一種高效的尋優(yōu)算法。在PSO中每個優(yōu)化問題的潛在解都可以想象成搜索空間中的一只鳥，稱之為“粒子”。所有的粒子都有一個被優(yōu)化函數(shù)決定的適應值，每個粒子還有一個速度決定其飛翔的方向和距離。粒子群體追隨當前的最優(yōu)粒子在解空間中搜索。PSO首先初始化一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己，第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值，另一個極值是整個種群目前找到的最優(yōu)解，這個極值為全局極值。粒子始終跟隨這兩個極值變更自己的位置和速度直到找到最優(yōu)解。設由m個粒子組成的群體在Q維空間進行搜索，每個粒子表示為：xi=(xi1,xi2,…,xiQ)，速度：vi=(vi1,vi2,…,viQ)，全局極值表示為：pg，個體極值表示為：pi(i=1,2,…,m)。則速度和位置的更新公式為：

vi=ωvi+c1ξ(pi-xi)+c2η(pg-xi)

(17)

xi=xi+vi

(18)

其中ω、c1、c2為算法中的參數(shù)，ξ、η為區(qū)間[0,1]的隨機數(shù)。該算法描述如下：

輸入:粒子數(shù)m和迭代次數(shù)K輸出:全局極值pg初始化:c1=c2=2,ω=1,t=0(1)隨機的初始化位置xi和速度vii=1,2,…,m()(2)計算適應值fi(i=1,2,…,m)(3)找出最大適應值對應下標,即^i=argmaxifi()(4)令個體極值pi=xi,全局極值pg=x^i(5)若t=K則停止迭代,否則t=t+1,轉入(6)(6)根據式(17)、式(18)更新vi,xi,轉入(2)

圖3 StOMP 算法性能比較

算法LenaPeppersCameraHouseGoldhillStOMP24.8223.4923.8122.5817.11DStOMP27.1026.0324.2927.2020.33

4 結 語

本文對壓縮感知中貪婪重構算法進行了深入的研究，并分析了各算法的優(yōu)缺點。SAMP能夠自適應地逼近信號真實的稀疏度，獲得很好的重構效果。但該算法運行時間較長，不適合處理大規(guī)模的重構問題。ROMP與SP算法在迭代中需要稀疏度的先驗知識，而自然信號的稀疏度往往是難以估計的，因而會影響該些算法的重構精度。總體而言，SP 算法兼顧了重建效果與運行效率，是一個較優(yōu)的重構算法。

粒子群算法是一種新的進化算法，它從隨機解出發(fā)，通過迭代尋找最優(yōu)解，根據適應度來評價解的優(yōu)劣。該算法實現(xiàn)容易、精度高、收斂快。本文通過粒子群優(yōu)化算法對StOMP中的參數(shù)進行配置，從而提高了StOMP算法的性能。并通過實驗對比說明了經過配置后，該算法的重構效果得到了較大改善。

[1] Nyquist H.Certain topics in telegraph transmission theory [J].Proceedings of the IEEE,1928,90(2):617-644.

[2] Candes E,Romberg J,Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information [J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[3] Candes E,Wakin M.An introduction to compressive sampling [J].IEEE Signal Processing Magazine,2008,25(2):21-30.

[4] Donoho D.Compressed sensing [J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[5] Zhu S,Zhang B,GABBOUJ M.Adaptive reweighted compressed sensing for image compression [C]//IEEE International Symposium on Circuit and Systems,2014:1-4.

[6] Hosseini S H,Shayesteh M G.Compressed sensing for denoising in adaptive system identification[C]//20th Iranian Conference on Electrical Engineering,2012:1238-1242.

[7] Fan N F,Zhu X,Liu Y,et al.Scalable Distributed Video Coding Using Compressed Sensing in Wavelet Domain[C]//IEEE 78th Vehicular Technology Conference,2013:1-5.

[8] Candes E,Tao T.Decoding by linear programming [J].IEEE Transactions on Information Theory,2005,51(12):4203-4215.

[9] Baraniuk R G.Compressive sensing [J].IEEE Signal Processing Magazine,2007,24(4):118-121.

[10] Chen S,Donoho D,Saunders M A.Atomic decomposition by basis pursuit [J].SIAM journal on scientific computing,2006,20(1):33-61.

[11] Kimon F,Jacek G,Pavel Z.Matrix-free Interior Point Method for Compressed Sensing Problems [J].Mathematical programming computation,2014,6(1):1-31.

[12] Harmany Z,Thompson D,Willett R,et al.Gradient projection for linearly constrained convex optimization in sparse signal recovery[C]//17th IEEE International Conference on Image Processing.2010:3361-3364.

[13] Donoho D,Tsaig Y.Fast Solution of l1-norm minimization problems when the solution may be sparse [J].IEEE Transactions on Information Theory,2008,54(11):4789-4812.

[14] Mallat S G,Zhang Z.Matching pursuits with time-frequency dictionaries [J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

[15] Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal matching pursuit:Recursive function approximation with applications to wavelet decomposition[C]//Conference Record of the Twenty Seventh Asilomar Conference on Signals,Systems and Computers.1993,1:40-44.

[16] Donoho D,Tsaig Y,Drori I,et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit [J].IEEE Transactions on Information Theory,2012,58(2):1094-1121.

[17] Kennedy J,Eberhart R C.Particle swarm optimization[C]//Proc.IEEE International Conference on Neural Networks,1995,4:1942-1948.

[18] Needell D,Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit [J].Foundations of computational mathematics,2009,9(3):317-334.

[19] Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction [J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[20] Needell D,Tropp J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples [J].Applied and Computational Harmonic Analysis,2009,26(3):301-321.

[21] Do T,Lu G,Nguyen N,et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//42nd Asilomar Conference on Signals,Systems and Computers.2008:581-587.

[22] Baraniuk R,Davenport M,Devore R,et al.A Simple Proof of the Restricted Isometry Property for Random Matrices [J].Constructive Approximation,2008,28(3):253-263.

GREEDY RECONSTRUCTION ALGORITHM StOMP AND ITS IMPROVEMENT

Chen Yanliang Zhan Yinwei

(SchoolofComputer,GuangdongUniversityofTechnology,Guangzhou510006,Guangdong,China)

In order to carry out in-depth research on novel sampling theorem:the compressed sensing (CS),and to apply it to image compression coding,we give an overview on the greedy reconstruction algorithms in CS and analyse the advantages and disadvantages of each algorithm.According to theoretical analysis and simulation experiments,we give a comparison on performances and efficiencies of each algorithm.Among them,the StOMP algorithm shall set parameter values artificially,which usually lowers down the reconstruction effect of the algorithm.To solve this problem,we use PSO algorithm to configure the parameters of StOMP so as to improve the reconstruction quality of the algorithm.Experiment illustrates that the StOMP algorithm with parameters configured can increase the reconstruction effect by 2.62 dB in average and the maximum improvement reaches 13.63 dB.

Compressed sensing Reconstruction algorithm Matching pursuit Particle swarm optimisation (PSO)

2014-12-06。廣東省教育廳高等院校學科建設專項資金項目(12ZK0362)。陳艷良，碩士生，主研領域：計算機視覺，圖像處理，人工智能。戰(zhàn)蔭偉，教授。

TP391

A

10.3969/j.issn.1000-386x.2016.04.060