改进的正交匹配追踪超声图像重构算法

石昊苏(西北政法大学 商学院, 西安 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