貪婪重構(gòu)算法StOMP及其改進(jìn)

陳艷良 戰(zhàn)蔭偉

貪婪重構(gòu)算法StOMP及其改進(jìn)

陳艷良 戰(zhàn)蔭偉

(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 廣東 廣州 510006)

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

壓縮感知 重構(gòu)算法 匹配追蹤 粒子群算法

0 引 言

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

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

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

1 壓縮感知理論

假設(shè)信號(hào)x∈RN和正交變換矩陣ψ∈RN×N，對(duì)信號(hào)進(jìn)行變換有：

α=ψx

(1)

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

y=φx

(2)

(2) 利用重構(gòu)算法，根據(jù)y∈RM重構(gòu)原始信號(hào)x。

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

y=φψ-1α

(3)

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

y=Φα

(4)

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

(5)

則可以通過(guò)求解以下問(wèn)題來(lái)確定α：

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

(6)

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

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

圖1 壓縮感知流程圖

凸優(yōu)化算法是將式(6)轉(zhuǎn)換為以下等價(jià)的凸優(yōu)化問(wèn)題來(lái)進(jìn)行求解：

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

(7)

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

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

2 貪婪重構(gòu)算法

2.1 算法分析

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

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

(8)

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

(9)

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

y=φi0+R1f

(10)

繼續(xù)對(duì)殘差R1f進(jìn)行同樣的分解，令R0f=y，經(jīng)過(guò)K步后有：

(11)

令:

(12)

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

(13)

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

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

輸入:矩陣Φ,信號(hào)y,迭代次數(shù)n,閾值τ輸出:α初始化:殘差r0=y,支撐集I=?,α=0,t=1(1)根據(jù)閾值找出Φ中與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,轉(zhuǎn)到(1)

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

(14)

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

(15)

(16)

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

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

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

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

對(duì)初始步長(zhǎng)的估計(jì)也是一個(gè)關(guān)鍵問(wèn)題，步長(zhǎng)估計(jì)準(zhǔn)確與否直接關(guān)系到信號(hào)的重建效果。一般要求s

2.2 仿真實(shí)驗(yàn)

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

表1 運(yùn)行時(shí)間比較(單位:秒)

圖2 重構(gòu)算法性能比較

由實(shí)驗(yàn)結(jié)果可知，貪婪重構(gòu)算法能有效地重建原始信號(hào)，其中SAMP 算法的重構(gòu)效果要優(yōu)于其他算法，但運(yùn)行時(shí)間最長(zhǎng)，主要是因?yàn)樗枰鸩奖平盘?hào)的真實(shí)稀疏度。StOMP算法不僅在每次迭代時(shí)選擇多個(gè)原子，而且迭代次數(shù)少，因而運(yùn)行時(shí)間最短。由于ROMP、SP 等算法需要信號(hào)的稀疏度作為先驗(yàn)知識(shí)，而圖像的稀疏度是難以預(yù)測(cè)的，所以重構(gòu)精度會(huì)受到影響，其中ROMP 算法所受影響較大，導(dǎo)致其重構(gòu)效果較差。ROMP、SP 等算法比OMP 快是因?yàn)檫@類算法在每次迭代時(shí)能有效地選擇多個(gè)原子，而OMP 只選擇一個(gè)原子。整體而言，SP 算法不僅重構(gòu)效果好，而且運(yùn)行效率高，是一個(gè)較好的重構(gòu)算法。

3 StOMP參數(shù)配置

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

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

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

(17)

xi=xi+vi

(18)

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

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

圖3 StOMP 算法性能比較

算法LenaPeppersCameraHouseGoldhillStOMP24.8223.4923.8122.5817.11DStOMP27.1026.0324.2927.2020.33

4 結(jié) 語(yǔ)

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

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

[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。廣東省教育廳高等院校學(xué)科建設(shè)專項(xiàng)資金項(xiàng)目(12ZK0362)。陳艷良，碩士生，主研領(lǐng)域：計(jì)算機(jī)視覺，圖像處理，人工智能。戰(zhàn)蔭偉，教授。

TP391

A

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