石昊蘇(西北政法大學(xué) 商學(xué)院, 西安 710063)

改進(jìn)的正交匹配追蹤超聲圖像重構(gòu)算法

石昊蘇
(西北政法大學(xué) 商學(xué)院, 西安 710063)

針對正交匹配追蹤(OMP)算法中超聲圖像重構(gòu)時間較長、重構(gòu)質(zhì)量不佳的問題，通過結(jié)合SP算法的思想，采用共軛梯度算法替換OMP算法中的最小二乘法求取估計值進(jìn)行圖像重構(gòu)的仿真實驗，采用圖像的PSNR值以及重構(gòu)時間進(jìn)行質(zhì)量分析，實驗結(jié)果表明: 改進(jìn)算法能夠有效減少重構(gòu)時間，提高圖像的重構(gòu)質(zhì)量。

正交匹配追蹤； 圖像重構(gòu)； 圖像質(zhì)量； 共軛梯度算法

0 引言

壓縮感知，是給定一個可壓縮或稀疏的原始信號，通過某個特定的矩陣將其投影到一個低維空間上，再利用一定的重構(gòu)算法重構(gòu)出原始信號[1]，因此重構(gòu)算法是壓縮感知理論中最為重要的部分。包括：最小全變分法、匹配追蹤(Matching Pursuit)系列算法、最小L1范數(shù)法，以及閾值迭代算法[2]。匹配追蹤系列算法大致思路是通過迭代方式選出信號的最佳支撐，然后基于貪婪準(zhǔn)則選擇局部最優(yōu)解，再逐步逼近原始信號。最初的匹配追蹤算法針對低維度小尺度信號具有較快的運算速度，但是當(dāng)大尺度信號存在噪聲時，其重建結(jié)果不夠精確[3]，后來在其基礎(chǔ)上產(chǎn)生了正交匹配追蹤算法(Orthogonal Matching Pursuit)[4]，以及一些其他改進(jìn)的算法，如正則化正交匹配追蹤(Regularize Orthogonal Matching Pursuit，ROMP)、子空間追蹤算法(Subspace Pursuit，SP)、最優(yōu)正交匹配追蹤(Optimized Orthogonal Matching Pursuit，OOMP)算法等[5-7]。

為了減小重構(gòu)算法中使用最小二乘法求解估計值耗時、重構(gòu)質(zhì)量不佳的問題，本文結(jié)合SP算法的思路，使用共軛梯度法(Conjugate Gradient Method，CG)求解估計值，以期達(dá)到對正交匹配追蹤算法的改進(jìn)。

1 正交匹配追蹤OMP算法

正交匹配追蹤(Orthogonal matching pursuit，OMP)算法屬于一種改進(jìn)貪婪迭代算法，該算法在每次迭代過程中從過完備集中選出原子，然后以Gram-Schmidt正交化方法進(jìn)行正交[5]，將采樣值投影到由這些正交原子張成的空間上，得到信號在該正交原子集上的分量和余量，最后以相同的方法繼續(xù)分解余量，余量會隨著分解過程迅速減小。通過遞歸的方式使已選擇原子集合相互正交，以保證迭代的最優(yōu)化，從而使迭代次數(shù)減少。

算法實現(xiàn)過程：

1. 余量初始化r0=v，索引集合∧0=?，設(shè)置迭代次數(shù)t=1；

2. 搜索索引λt，求解優(yōu)化問題：

λt=argmaxj=1,…,d|[rt-1,φj]|

3. 添加索引集合、已經(jīng)存在原子矩陣，即：

∧t=∧t-1∪{λt}，Φt=[Φt-1φλt]

4. 求解最小二乘法問題：

5. 計算at和rt：

at=Φtxt，rt=v-at

6. 迭代t=t+1，當(dāng)t

2 共軛梯度方法

共軛梯度方法是從初始點出發(fā)，沿著某組共輒方向進(jìn)行迭代，求解無約束最優(yōu)化問題的方法。其迭代結(jié)構(gòu)簡單、存儲量小，具有良好的局部和全局收斂性，對于大規(guī)模無約束最優(yōu)化問題，數(shù)值表現(xiàn)遠(yuǎn)遠(yuǎn)優(yōu)于其它最優(yōu)化算法[8]。對于無約束最優(yōu)化問題Min(x),x(Rn，通常是通過迭代產(chǎn)生點列{xn}，或者{xn}的某一迭代點是它的極小點，或者{xn}的極限點是它的極小點。因此利用已知點x(0)的梯度及其共軛方向所構(gòu)成的一組方向進(jìn)行搜索，計算極小目標(biāo)值。

共軛梯度法的一般形式[9-10]為式(1)。

x(k+1)=xk+αkdk

(1)

其中x(0)是初始點，dk是k+1次迭代的搜索方向，ak為第k+1次迭代目標(biāo)函數(shù)f(x)沿搜索方向dk的搜索步長，gk表示目標(biāo)函數(shù)f(x)在xk處的梯度向量，Bk-1是標(biāo)量參數(shù)。

充分利用先進(jìn)科學(xué)技術(shù)帶來的優(yōu)勢進(jìn)行噴灌或者滴灌都是不錯的選擇，這樣能夠在很大程度上改善干旱對于作物正常生長的影響，最大限度地減少作物受到干旱的侵?jǐn)_程度。在干旱的區(qū)域，為了改善環(huán)境可以大力開展人工造林，減少水土流失，使得土壤有較好的水源涵養(yǎng)。對旱災(zāi)經(jīng)常發(fā)生的農(nóng)田可以大力興修水利，促進(jìn)水利基礎(chǔ)設(shè)施的建設(shè)，不僅能夠保障農(nóng)作物生長的水分供給，還能大大降低干旱對農(nóng)作物生長的影響。

(2)

因為d(k+1)與d(k)關(guān)于A共軛，可求出式(3)。

(3)

3 正交匹配追蹤算法的改進(jìn)

在上述正交匹配追蹤算法的第4步，使用最小二乘法對測量信號進(jìn)行計算估計值，但是由于最小二乘法作為從數(shù)據(jù)中解釋數(shù)據(jù)的經(jīng)典統(tǒng)計方法，它的準(zhǔn)則是使估計量殘差平方和最小[14]，即求解樣本觀測值與估計值殘差平方和的極值，這在非經(jīng)典線性問題求解上精度并不高，使得信號重構(gòu)過程中殘差更新的誤差逐漸積累，從而降低重構(gòu)質(zhì)量[15]。而共軛梯度方法迭代結(jié)構(gòu)簡單、存儲量小，具有良好的局部和全局收斂性，因此采用共軛梯度法替代最小二乘法求解估計值，最后完成圖像的重構(gòu)。

所以改進(jìn)OMP算法中第四步為：

4 仿真實驗

選取硬幣的超聲C-掃描圖像(圖像來源：www.pacndt.cn，由美國物理聲學(xué)公司ULTRAPAC對硬幣掃描產(chǎn)生像素為256*256的灰度圖像)，如圖1所示。

圖1 原始圖像

使用高斯測量矩陣進(jìn)行采樣，分別用OMP算法，如圖2所示。

圖2 OMP算法

與改進(jìn)算法，如圖3所示。

圖3 改進(jìn)算法

進(jìn)行圖像重構(gòu)，采用重構(gòu)時間、PSNR值對圖像重構(gòu)進(jìn)行質(zhì)量分析，如表1所示。

表1 OMP算法與改進(jìn)算法重構(gòu)質(zhì)量對比

改進(jìn)算法用共軛梯度法從整體上進(jìn)行信號估計，明顯減少算法收斂時間，取得較好的圖像重構(gòu)質(zhì)量。

5 總結(jié)

本文應(yīng)用壓縮感知理論嘗試改進(jìn)OMP算法，用共軛梯度法來替代最小二乘法，理論分析及仿真實驗表明改進(jìn)算法有效縮減重構(gòu)時間，保證了重構(gòu)的質(zhì)量。當(dāng)然后續(xù)還可以嘗試將系列具有充分下降性的共軛梯度算法運用于對正交匹配追蹤算法的改進(jìn)、優(yōu)化，以期得到更佳的效果，這有待于進(jìn)一步研究。

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

[2] 白凌云,梁志毅,徐志軍.基于壓縮感知信號重建的自適應(yīng)正交多匹配追蹤算法[J].計算機應(yīng)用研究，2011,28(11): 4060-4063.

[3] 李樹濤,魏丹.壓縮傳感綜述[J]. 自動化學(xué)報,2009,35(11):1369-1377.

[4] 張宗念,黃仁泰,閆敬文.壓縮感知信號盲稀疏度重構(gòu)算法[J].電子學(xué)報,2011,39(1):18-22．

[5] 劉亞新,趙瑞珍,胡紹海,等. 用于壓縮感知信號重建的正則化自適應(yīng)匹配追蹤算法[J]. 電子與信息學(xué)報, 2010, 32(11):2713-2717.

[6] 楊成,馮巍,馮輝,等. 一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J]. 電子學(xué)報, 2010, 38(8):1914-1917.

[7] 付麗華,李宏偉,張猛. 基于更貪心策略的快速正交核匹配追蹤算法[J]. 電子學(xué)報, 2013, 41(8):1580-1585.

[8] 董曉亮,何郁波,孔翔宇,等. 一類新的具有充分下降條件和強收斂性的共軛梯度法[J]. 數(shù)學(xué)雜志(英文),2017, 37(2)：231-238.

[9] 張元園.共軛梯度法的改進(jìn)[D]. 昆明：重慶西南大學(xué), 2012.

[10] 姚勝偉.幾類共軛梯度算法的研究[D]. 上海：華東理工大學(xué), 2014.

[11] 陳洪敏. Wolfe線搜索下具有全局收斂性的混合共軛梯度法[D]. 重慶：重慶師范大學(xué), 2016.

[12] 馬爍.一種帶強Wolfe線搜索的CD和LS混合共軛梯度算法[J]. 重慶工商大學(xué)學(xué)報(自然科學(xué)版), 2014, 31(8):62-65.

[13] 高蒙. 求解無約束最優(yōu)化問題算法比較[J]. 市場周刊:理論研究, 2014(5):155-156.

[14] 王曉東.基于MATLAB的數(shù)字電視圖像處理的矩陣表示及正交變換[J]. 電子世界, 2015(16):146-147.

[15] 趙巖,孟麗茹,王世剛,等.符合人眼視覺感知特性的改進(jìn)PSNR評價方法[J].吉林大學(xué)學(xué)報(工學(xué)版),2015,45(1):309-313.

AnImprovedOrthogonalMatchingPursuitAlgorithmforImageReconstruction

Shi Haosu
(School of Business, NorthWest University of Political Science and Law, Xi’an 710063)

For problems of longer time and poor quality of ultrasonic image reconstruction in the orthogonal matching pursuit (OMP) algorithm, with the idea of SP algorithm the conjugate gradient method is replaced by the least square method to calculate the estimated value and further get reconstruction image in simulation experiment. It uses PSNR value and reconstruction time to analyze the quality. The results show that the improved algorithm can effectively reduce the reconstruction time and improve the quality of image.

Orthogonal matching pursuit; Image reconstruction; Image quality; Conjugate gradient method

TP391

A

2017.05.05)

陜西省教育廳科研計劃項目(15JK1776)、陜西省自然科學(xué)基礎(chǔ)研究計劃(2013JM8035)、陜西省計算機教育學(xué)會教學(xué)改革項目(2016012)、西北政法大學(xué)教學(xué)改革項目(2016XJY201617)。

石昊蘇(1976-)，男，咸陽人，碩士，副教授，研究方向：物證圖像處理，信息管理.

1007-757X(2017)10-0019-03