改進的粒子群優(yōu)化正交匹配追蹤重構(gòu)算法

王 麗，王 威，陳 博2(西安航空學(xué)院電子工程學(xué)院，西安70077)

2(咸陽師范學(xué)院物理與電子工程學(xué)院，陜西咸陽712000)

E-mail:wangli871016@163.com

1 引言

高光譜圖像的空間和譜間信息較為豐富，其應(yīng)用范圍較廣［1-3］.然而，高光譜圖像的數(shù)據(jù)量較大，給高光譜圖像帶來了挑戰(zhàn)，增加了傳輸和存儲系統(tǒng)的壓力.因此，在研究高光譜圖像時，尋找有效的壓縮技術(shù)對高光譜圖像的發(fā)展非常關(guān)鍵.

壓縮感知理論(Compressed Sensing，CS)［4，5］指出，若信號或圖像具有稀疏性或可壓縮性，可通過低于奈奎斯特速率進行采樣，利用較少的測量值仍能精確獲取重構(gòu)信號.高光譜圖像的空間和譜間均存在冗余，具備可壓縮性［6］.因此，利用壓縮感知理論可對高光譜圖像進行處理，基于冗余字典和正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)［7］可實現(xiàn)高光譜圖像的采樣和重構(gòu).因高光譜圖像的波段數(shù)眾多，當(dāng)利用OMP算法實現(xiàn)基于冗余字典的重構(gòu)時，其計算復(fù)雜度太高.

為提高OMP算法的計算效率，文獻［8］提出利用粒子群算法(Particle Swarm Optimization，PSO)［9］優(yōu)化 OMP 算法的匹配過程，實現(xiàn)高光譜圖像稀疏分解的最優(yōu)原子的搜索，但OMP算法的求逆過程仍然非常耗時.因此本文不僅用PSO優(yōu)化OMP的匹配過程，同時利用Hermitian求逆引理［10］優(yōu)化殘差更新過程，實現(xiàn)殘差的遞歸更新，應(yīng)用于高光譜圖像的壓縮感知重構(gòu)，提出改進的粒子群優(yōu)化 OMP重構(gòu)算法(fastPSO_OMP).該算法能夠快速實現(xiàn)高光譜圖像的重構(gòu)，計算復(fù)雜度低，且重構(gòu)精度與OMP算法相當(dāng).

2 基本理論

2.1 壓縮感知理論及OMP重構(gòu)算法

假設(shè)x是長度為N的離散時域信號，其可在某組基Ψ=［ψ1，ψ2，…，ψN］上表示為:

其中，S是投影系數(shù)Sd=?x，ψd?構(gòu)成的N*1維的列向量.

如果S中大部分系數(shù)為零或者排序后呈指數(shù)級衰減并趨近于零，則認為信號x是可壓縮的或在Ψ域上是稀疏的.用一個M*N維的觀測矩陣Φ(MN)對信號x進行測量，得到M維的觀測值y:

其中，Θ=ΦΨ是一個M*N維的矩陣.壓縮感知理論指出，在已知y和Θ的情況下，可利用重構(gòu)算法恢復(fù)出稀疏信號S，最后由公式(1)得到原始信號x.

傳統(tǒng)OMP算法的重構(gòu)過程如下:

1)初始化:殘差r0=y，最優(yōu)原子的索引集合Λ0=［］，迭代次數(shù)k=1;

2)遍歷矩陣Θ中的所有原子(列向量)，利用內(nèi)積選取最佳匹配原子的索引，其中，Θj是矩陣Θ的第j列;

3)利用 λk更新索引集合，

5)判斷是否達到最大迭代步數(shù)K，若不滿足則k=k+1，重復(fù)2)～4);若滿足則停止迭代.

重構(gòu)信號為:

其中，ΨΛK表示稀疏基Ψ中對應(yīng)于索引集合ΛK的列向量構(gòu)成的子矩陣.

由上述重構(gòu)過程可知，OMP的匹配過程在每次迭代時均需要遍歷所有原子以尋找最佳匹配原子.因冗余字典原子個數(shù)多，其匹配計算量大;同時其殘差更新中存在大型矩陣的求逆運算，非常耗時.針對以上耗時過程，本文分別利用粒子群算法和Hermitian求逆引理對其進行優(yōu)化.

2.2 粒子群優(yōu)化

粒子群算法的基本思想是通過群體中個體之間的協(xié)作和群體中信息的共享產(chǎn)生進化優(yōu)勢，從而達到尋找最優(yōu)解的目的.本文利用粒子代表冗余字典的原子，用位置、速度和適應(yīng)度值表示.假設(shè)搜索空間為L維，種群Z=(Z1，Z2，…，Zm)包含m個粒子，第i個粒子表示為向量 Zi=(zi1，zi2，…，ziL)，代表其在搜索空間中的位置.根據(jù)適應(yīng)度函數(shù)可計算出粒子Zi的適應(yīng)度值.第 i個粒子的速度為 Vi=(vi1，vi2，…，viL)，個體極值為 Pbesti=(Pi1，Pi2，…，PiL)，群體極值為 Gbest=(G1，G2，…，GL).粒子通過跟蹤個體極值Pbest和群體極值Gbest更新其速度和位置［9］，隨著迭代的進行，粒子不斷運動以找到群體的極值，即最優(yōu)原子，大大縮短運算時間.

2.3 Hermitian 求逆引理

隨著迭代次數(shù)的增加，索引集字典的維度越來越高，導(dǎo)致求逆運算－1的計算復(fù)雜度越來越高.因是正定Hermitian矩陣，本文利用Hermitian求逆引理實現(xiàn)矩陣的遞歸求逆，提高矩陣求逆速度.Hermitian求逆引理表示如下:

Hermitian矩陣的分塊形式為:

成立.即利用前次迭代的求逆結(jié)果線性表示當(dāng)次迭代的求逆結(jié)果，大大提高運行效率.

3 改進的粒子群優(yōu)化OMP重構(gòu)算法

3.1 Gabor字典

本文利用Gabor冗余字典作為高光譜圖像的稀疏基，Gabor字典的生成函數(shù)表示為［11］:冗余度很高，原子個數(shù)為52(N log2N+N－1).

3.2 改進的PSO_OMP重構(gòu)算法

由于OMP算法的匹配過程和殘差更新過程均非常耗時，本文提出一種改進的粒子群優(yōu)化OMP重構(gòu)算法(fastPSO_OMP)，利用粒子群算法的局部尋優(yōu)能力優(yōu)化OMP的匹配過程，快速找到最優(yōu)原子;并且利用Hermitian求逆引理加速OMP的殘差更新過程，實現(xiàn)殘差的遞歸更新，以降低算法的計算復(fù)雜度.下面分別介紹粒子群優(yōu)化和Hermitian求逆引理的實現(xiàn)過程.

3.2.1 粒子群優(yōu)化的實現(xiàn)過程

1)粒子位置和適應(yīng)度

粒子位置為(s，u，υ，ω)，是一個 4維向量，選擇 OMP 的匹配函數(shù)作為適應(yīng)度函數(shù):

2)粒子群的初始化

假定粒子群的群體規(guī)模為m，初始群體為Z0=(Z01，Z02，…)，第i個粒子的初始位置為

其中，n=0，1，…，N，N 為信號長度，γ =(s，u，υ，ω)是時頻參數(shù).時頻參數(shù)按以下方法離散化:γ =(aα1，α2aα1Δu，α3a－α1Δυ，α4Δω)，其中，a=2，，其取值分別是(s，u，υ，ω)取值范圍中的一個隨機數(shù).根據(jù)生成函數(shù)計算粒子所生成的原子，并計算適應(yīng)度.第i個粒子的最優(yōu)位置為Pbesti=Z0i，初始群體極值為1，2，…，m.同時設(shè)置每個粒子的初始速度.

3)最優(yōu)原子的確定

在迭代過程中，更新每個粒子的速度和位置，并評價其適應(yīng)度.若 fitness()＞Pbesti，則更新個體極值位置 Pbesti=，否則保持不變.若fitness()＞Gbest，則更新群體極值位置Gbest=Ziiter，否則保持不變.迭代得到的群體極值位置所對應(yīng)的原子即為最優(yōu)原子.

3.2.2 Hermitian求逆引理的實現(xiàn)過程

fastPSO_OMP的每步迭代中，原子字典的更新表示為ΨΛk=［ΨΛk－1gγk］，其中，ΨΛk－1是第 k －1 次迭代后形成的原子字典，gγk是第 k 次迭代找到的最優(yōu)原子，則 ΘΛk=［ΘΛk－1與公式(4)對比可知:

將Hk－1和Hk代入公式(5)，得到殘差更新過程中矩陣求逆的遞歸表達式，見公式(11).通過遞歸方式實現(xiàn)傳統(tǒng)OMP算法的殘差更新過程，提高算法的執(zhí)行效率.

3.3 算法執(zhí)行過程

本文提出的改進的粒子群優(yōu)化OMP重構(gòu)算法的流程圖如圖1所示，圖中黑色粗實線框內(nèi)是利用粒子群算法尋找最優(yōu)原子的過程，黑色粗虛線框內(nèi)是利用Hermitian求逆引理進行殘差更新的過程.成的最優(yōu)原子gγk，根據(jù)公式(11)，利用第k－1步迭代所得到的(－1遞歸求解－1，并計算殘差 rk=y

圖1 改進的fastPSO_OMP重構(gòu)算法流程圖Fig.1 Framework of fastPSO_OMPreconstruction algorithm

5)判斷是否達到最大迭代次數(shù)K，若不滿足則k=k+1，重復(fù)2)～4);若滿足則停止迭代.

重構(gòu)信號表達式仍為公式(3)，其中，ΨΛK表示第K步迭代后形成的原子字典.

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

4.1 高光譜數(shù)據(jù)

利用OMP算法、PSO_OMP算法和fastPSO_OMP算法對四組高光譜圖像1數(shù)據(jù)來源:http://aviris.jpl.nasa.gov進行壓縮感知重構(gòu).前兩組數(shù)據(jù)是AVIRIS采集得到的場景Cuprite1和場景Cuprite2，數(shù)據(jù)集共有224個波段，去除異常波段和全零波段后，可用波段數(shù)為188，圖像大小裁剪至256×256.第三組數(shù)據(jù)是由AVIRIS采集的場景Indian Pines，數(shù)據(jù)集共220個波段，去除水汽吸收波段后，可用波段數(shù)為200，圖像大小裁剪至128×128.第四組數(shù)據(jù)是ROSIS采集的場景Pavia University，數(shù)據(jù)集包含115個波段，去除含噪波段后，可用波段數(shù)為103，圖像大小裁剪至256×256.為保證數(shù)據(jù)的統(tǒng)一性，對高光譜圖像進行處理時，對原始采集得到的圖像均重新進行量化，將每個波段圖像的量化位數(shù)設(shè)置為8位，即圖像像素值范圍是0～255.四組高光譜數(shù)據(jù)第50個波段的原始圖像如圖2所示.

4.2 結(jié)果與分析

因計算機內(nèi)存有限，實驗中利用高斯隨機矩陣對高光譜圖像進行分塊壓縮感知采樣，分塊大小為16，并利用OMP算法、PSO_OMP算法和fastPSO_OMP算法進行重構(gòu).三種重構(gòu)算法的迭代次數(shù)K=50，粒子群算法的迭代步數(shù)Tmax=5，種群大小m=10.

三種重構(gòu)算法重構(gòu)單個波段所需的匹配時間和更新時間見表1.從表中可以看出，僅用粒子群優(yōu)化OMP匹配過程的PSO_OMP算法，可以將匹配時間降低兩個數(shù)量級，但對更新時間的影響較小.本文進一步用Hermitian求逆引理對OMP的更新過程進行改進，提出的fastPSO_OMP算法能夠?qū)MP算法的更新時間降低一個數(shù)量級.加速原因在于:1)OMP需要遍歷Gabor字典中的每個原子，而PSO僅需搜索少量的空間參數(shù)點就能尋找到最優(yōu)原子;具體來說，在每次迭代時，OMP算法需遍歷119756個原子才能找到一個最優(yōu)原子，而PSO算法僅需搜索50個空間參數(shù)點(迭代次數(shù)*種群數(shù)量)就能找到一個最優(yōu)原子，計算量大大降低.2)引入Hermitian求逆引理，每次迭代過程中僅需少量矩陣計算，采用遞歸方式實現(xiàn)矩陣求逆，運算量大大降低，算法運行效率提高.

表1 三種算法重構(gòu)單個波段所需的匹配時間和更新時間Table 1 Matching time and update time of three reconstruction algorithms for reconstructing one band

表2 三種算法的平均PSNR及加速比Table 2 Average PSNR and accelerating times of three reconstruction algorithms for reconstructing one band

利用重構(gòu)圖像的峰值信噪比(Peak Signal-to-Noise Ratio，PSNR)、運行時間(runtime)及重構(gòu)圖像的主觀視覺對算法性能進行評價.不同采樣率下，所有波段的平均PSNR及算法的加速比見表2.表中的平均PSNR是將每個波段的PSNR對所有波段進行平均得到的.表中的加速比是指將OMP算法的計算速度設(shè)為1，PSO_OMP算法和本文算法fastPSO_OMP的計算速度相對于OMP算法速度的倍數(shù).從表中可以看出，對于場景Cuprite1和場景Cuprite2來說，算法PSO_OMP和算法fastPSO_OMP的PSNR與OMP算法相當(dāng)，在采樣率為0.1和0.5時有提高的優(yōu)勢，其他采樣率下的差值能保證在1dB以內(nèi).對于場景Indian Pines和場景Pavia University來說，算法PSO_OMP和所提算法fastPSO_OMP的重構(gòu)性能在五個采樣率下均有不同程度的提高，特別是在采樣率為0.1時，提高值分別為1.76dB和1.31dB，算法性能得到保證.同時從表中可以看出，相較于算法PSO_OMP，本文算法fastPSO_OMP進一步地提高了執(zhí)行效率，加速比最高可達到18.8657.

重構(gòu)性能提高的原因在于:利用PSO算法搜索最優(yōu)原子時，粒子位置在整個參數(shù)空間中變化，能夠搜索得到最能表示圖像特征的原子，而OMP算法無法在事先構(gòu)造的冗余字典中找到與信號特征最相符的原子，因此利用粒子群算法能夠在一定程度上提高重構(gòu)圖像的質(zhì)量.執(zhí)行效率提高的原因在于:利用PSO搜索最優(yōu)原子時，僅需搜索50個參數(shù)空間點，其運行時間遠遠低于OMP算法的匹配過程;同時本文引入Hermitian求逆引理，采用遞歸方式解決了殘差更新的矩陣求逆問題，降低了OMP算法中大型矩陣的求逆時間.故本文算法能夠在較少時間內(nèi)完成高光譜圖像壓縮感知重構(gòu)，在保證 重構(gòu)精度的條件下，大大提高計算效率.個波段，采樣率為0.5.算法PSO_OMP和本文算法fastPSO_OMP均能夠得到重構(gòu)質(zhì)量優(yōu)于OMP算法的圖像.

圖2 4組高光譜數(shù)據(jù)的第50個波段的原始圖像Fig.2 50th band original images of four hyperspectral datasets

圖3 數(shù)據(jù)集Cuprite2的重構(gòu)圖像與原始圖像對比Fig.3 Comparison of reconstructed image of dataset Cuprite2 with its original image

利用OMP算法、PSO_OMP算法和fastPSO_OMP算法得到的重構(gòu)Cuprite2圖像如圖3所示，圖中為重構(gòu)圖像的第40

為提高OMP算法處理基于冗余字典的高光譜圖像壓縮感知重構(gòu)問題的計算效率，本文采用粒子群算法優(yōu)化OMP的匹配過程，并引入Hermitian求逆引理加速其殘差更新過程，提出改進的粒子群優(yōu)化OMP重構(gòu)算法(fastPSO_OMP).將所提算法應(yīng)用于高光譜圖像壓縮感知重構(gòu)，實驗結(jié)果表明，與OMP算法相比，本文算法能夠在保證重構(gòu)精度的條件下，大大提高計算效率.