改進的正交匹配追蹤超聲圖像重構算法

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

改進的正交匹配追蹤超聲圖像重構算法

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

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

正交匹配追蹤； 圖像重構； 圖像質量； 共軛梯度算法

0 引言

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

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

1 正交匹配追蹤OMP算法

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

算法實現過程：

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

2. 搜索索引λt，求解優化問題：

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

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

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

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

5. 計算at和rt：

at=Φtxt，rt=v-at

6. 迭代t=t+1，當t

2 共軛梯度方法

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

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

x(k+1)=xk+αkdk

(1)

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

充分利用先進科學技術帶來的優勢進行噴灌或者滴灌都是不錯的選擇，這樣能夠在很大程度上改善干旱對于作物正常生長的影響，最大限度地減少作物受到干旱的侵擾程度。在干旱的區域，為了改善環境可以大力開展人工造林，減少水土流失，使得土壤有較好的水源涵養。對旱災經常發生的農田可以大力興修水利，促進水利基礎設施的建設，不僅能夠保障農作物生長的水分供給，還能大大降低干旱對農作物生長的影響。

(2)

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

(3)

3 正交匹配追蹤算法的改進

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

所以改進OMP算法中第四步為：

4 仿真實驗

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

圖1 原始圖像

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

圖2 OMP算法

與改進算法，如圖3所示。

圖3 改進算法

進行圖像重構，采用重構時間、PSNR值對圖像重構進行質量分析，如表1所示。

表1 OMP算法與改進算法重構質量對比

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

5 總結

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

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

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

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

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

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

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

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

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

[9] 張元園.共軛梯度法的改進[D]. 昆明：重慶西南大學, 2012.

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

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

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

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

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

[15] 趙巖,孟麗茹,王世剛,等.符合人眼視覺感知特性的改進PSNR評價方法[J].吉林大學學報(工學版),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)、陜西省自然科學基礎研究計劃(2013JM8035)、陜西省計算機教育學會教學改革項目(2016012)、西北政法大學教學改革項目(2016XJY201617)。

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

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