基于压缩感知的OMP图像重构算法改进

马小薇

(西安电子科技大学 生命科学技术学院,陕西 西安 710071)

基于压缩感知的OMP图像重构算法改进

马小薇

(西安电子科技大学 生命科学技术学院,陕西 西安 710071)

阐述了压缩感知相关理论以及信号的重构算法,围绕其中的匹配追踪系列算法展开研究,同时在正交匹配追踪算法(OMP算法)的基础上引入了几种改进算法,并结合OMP算法本身耗时长、速度慢的问题,给出了一种OMP的改进方案,该方案将图像进行分块再处理,从而大幅降低了OMP算法迭代的矩阵规模。在相同条件下该算法的主客观重建效果均优于原来的算法。

压缩感知;重构算法;匹配追踪;图像重构

目前,压缩感知的研究多数集中在信号或图像的重构及相关问题上。提出了一种基于匹配追踪(Matching Pursuit,MP)的压缩感知信号检测算法,从压缩感知信号获取的采样值中直接提取特征量,但由于其在已选定原子集合上投影的非正交性使得每次迭代的结果都是次优的,因此为获得收敛需要经过多次迭代。OMP仍沿用了MP算法中的原予选择准则,但是通过递归地对已选择原子集合进行正交化以保证迭代的最优性,从而减少了达到收敛的迭代次数。但其正交化过程引入了新的计算开销,特别是对于图像信号,计算量仍然巨大。为更加快速准确的进行信号与图像的重构,对OMP算法进行了改进研究,提出了几种有效的改进算法。

1 匹配追踪算法

1.1 信号重构

在压缩感知理论中,由于观测数量M远小于信号长度N,因此必须求解欠定方程组Y=ACSX。表面上看,求解欠定方程组似乎是无望的,但由于信号X是稀疏或可压缩的,这个前提从根本上改变了问题,使得问题可解,而观测矩阵具有RIP性质也为从M个观测值中精确恢复信号提供了理论保证[1]。

为更清晰地描述压缩感知理论的信号重构问题,首先定义向量X={X1,…,Xn}的p—范数为

(1)

当p=0时得到0—范数,它实际上表示X中非零项的个数。于是,在信号X稀疏或可压缩的前提下,求解欠定方程组Y=ACSX的问题转化为最小0—范数问题

(2)

1.2MP算法

次迭代以后的残余信号。首先按照某种规则设定了一个向量ak0∈D,则可将b0分解成沿着 方向的分量和与它垂直分量的迭加

b0=〈b0,ak0〉ak0+b1

(3)

重复上述的分解过程,直到分解的项数达到预先设定值,或者余项的能量小于预先设定的值时才停止迭代。经过m次迭代,信号b被分解为

(4)

如果迭代在第m步停止计算,并且记录下来二元序列{ak;lk;k=0,1,…,m-1},就可以恢复出x的近似值,其逼近误差为bm[3]。

1.3OMP算法

OMP算法[4]的本质是:以贪婪迭代的方法选择传感矩阵的列,使在每次迭代中所选择的列与当前的冗余向量最大程度地相关,从测量向量中减去相关部分并反复迭代,直到迭代次数达到稀疏度K,强制迭代停止。

步骤2 更新索引集Λt=Λt-1∪{λt},记录找到的传感矩阵中的重建原子集合Φt=[Φt-1,φλt]。

步骤5 判断是否满足t>K,若满足,则停止迭代;若不满足,则执行步骤l。

OMP算法保证了每次迭代的最优性,减少了迭代次数。但是它在每次迭代中仅选取一个原子来更新原子集合,这样必然会付出巨大的重建时间代价。迭代次数与稀疏度K或采样个数M密切相关,随其增大,耗时也将大幅增加,因此后来出现了许多改进的匹配追踪算法,如ROMP、STOMP、CoSaMP等。但OMP作为最早的贪婪迭代算法之一,它的思想影响了其他算法,有着不容忽视的意义[5]。

2 OMP算法改进研究

2.1 OMP改进算法

算法改进主要从两个方向对其进行改进,OMP算法由于每次只选取一个原子,使得重建过程缓慢。随着迭代次数的增加,耗时也将大幅增加,可以考虑减小单次运算规模以提高速度,首先考虑将图像进行分块,这样在不大幅降低算法性能的前提下提高速度,其次在向量选取方法上进行改进。OMP算法是在字典中寻找与信号最匹配的向量,即与信号内积最大的向量。这种选取方法的缺陷就是前后选取的向量没有关联,要达到要求的重建效果,所需的迭代次数就很大。在向量选取方法上进行改进就是每一次迭代过程同时选择L向量来代替OMP算法中的一个向量,这样比OMP算法在同样次数下的重建效果有所改善[6]。

2.2 实现步骤

步骤1 对原始测试图像X进行分块,X像素大小为I=n×n,均匀分成互不覆盖的大小为A×A的子块,每个子块记为Xi,(i=1,…,s,s=I/A2)。选取的测试图像为256×256,分块为8×8,实验表明,当块大小<8时被测信号的长度过小不适于CS框架正确的处理,同时当块过大时计算也会过于复杂[7]。

步骤2 对每个子块Xi选取相同的观测矩阵ΦA,ΦA是MA×A2的正交独立同分布高斯矩阵,其中MA的大小为(MA×A2)/I,这样整幅图像的观测矩阵Φ便是基于ΦA的一个块对角矩阵。可以清楚地看到在该算法中无需存储M×N的观测矩阵Φ,而需大小为MA×A2的块观测矩阵ΦA,这样降低了存储空间,并能快速有效地实现。

步骤3 对块进行二维离散余弦变化并进行Zigzag扫描得到图像块的稀疏量化表示,对每块采用相同的观测矩阵ΦA对其进行采样,得到观测向量yi,对块的采样过程可以表示为

其中,T(Xi)是二维离散变换算子;γi是量化算子。

步骤4 在正交匹配追踪算法(OMP)的基础上进行向量选取方式的改进,根据公式

(5)

3 实验与结果分析

3.1 图像评价标准

(6)

式(6)中,f(x,y)代表图像函数;M和N分别表示图像的行数和列数。通常来讲,平均梯度越大,则表示重构后所得结果图像层数越多,图像越清晰。

(2)标准差δ。图像的标准差指标反映了图像中各像素点灰度相对于该图像平均灰度的离散情况,可以根据标准差指标的大小来衡量图像所含信息丰富程度,图像反差的大小也能通过标准差指标来体现,标准差计算公式如式(7)所示

(7)

(3)熵。熵值的大小反映了图像中所含的平均信息量的多少,关于图像评价指标熵的定义如下

(8)

式(8)中,H代表图像的熵;L表示图像中的灰度级数;ρi表示灰度值为i的像素数Ni在图像总像素数N中所占的比例。图像中所含的信息量越大,求得的熵值就越大,表示效果越好。

3.2 二维图像的重建仿真

源图像为256×256的Lena图,如图1所示,在选取观测值M=150的情况下,分别基于OMP算法和改进的OMP算法进行恢复重构,其重构结果如图2和图3所示,可见不同的重构算法会产生不同的重构效果。

图1 原始图像

图2 OMP算法重构图像

图3 OMP改进算法重构图像

为更加直观地对比在不同算法下的重构图像,在此给出了各重构图像的平均梯度,标准差,熵和PSNR值,通过所测数据可以直观地比较两幅图像的重构效果,如表1所示。

表1 两个重构图像的重构效果比较

通过仿真结果可以明显看出,改进后的重建效果比较好,图像较清晰,说明对图像进行分块处理后重构质量明显提高。从表1 中也可以看出,相比传统的OMP重构算法,本文算法在重构图像的平均梯度,标准差,熵上有显著提高,而且随着分块的处理,PSNR值也有相应提高,重建效果理想,但从实验中也可以得出随着分块 的处理,计算时间和计算复杂度会有所增加。而且在采样率过低时,重构图像会出现明显的块效应和人为噪声。

分块方案牺牲了少量的性能,但图像清晰度提高了很多。采取该算法时,性能和分块大小的选取是一个权衡问题。如何选用适合于所处理的图像信号的分块大小,是该算法效果优劣的关键。

4 结束语

压缩传感原理在图像重建领域的应用,可以有效简化采集系统的复杂度,降低系统的成本,加快图像的重建速度。虽然已经提出了很多的压缩传感图像重建系统和算法,但随着现代科技的发展,对图像重建速度和质量提出了更高的要求。因此需要充分发挥压缩传感的优势,使图像重建所需的观测值越少越好、图像稀疏表示时越稀疏越好、重建算法越简单越快越好。

[1] Candès E.Compressive sampling[C].Madrid,Spain:Proceedings of the International Congress of Mathematicians,2006,3:1433-1452.

[2] Candès E,Romberg J,Terence Tao.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):1289-1306.

[3] Donoho D L.Compressed sensing[J].IEEE Transactions on Informa2tion Theory,2006,52(4):72-82.

[4] Candès E J,Romberg J.Practical signal recovery from randomprojections[C].Proceedings of SPIE Computational ImagingⅢ:2006:76-86.

[5] Donoho D L,Tsaig Y.Extensions of compressed sensing[J].Signal Processing,2006,86(3):549-571.

[6] 刘丹华,石光明,周佳社.一种冗余字典下的信号稀疏分解新方法[J].西安电子科技大学学报:自然科学版,2008,35(2):228-232.

[7] Osher S,Mao Y,Dong B,at el.Fast linearized bregman iteration for compressive sensing and sparse denoising[R].Nology,Rice USA:Department of Computational and Applied Mathematices,Rice University,2008.

[8] 谢志鹏.迭代式正交匹配追踪及稀疏解[J].微电子学与计算机,2009,26(10):53-56.

[9] 石光明,刘丹华,高大化,等.压缩感知理论及其研究进展[J].电子学报,2009,37(5):1070-1081.

[10]方红,章权冰,韦穗.基于非常稀疏随机投影的图像重建方法[J].计算机工程与应用,2007,43(22):25-27.

[11]方红,章权冰,韦穗.基于亚高斯随机投影的图像重建方法[J].计算机研究与发展,2008,45(8):1402-1407.

Improvement of OMP Image Reconstruction Algorithm Based on Compressed Sensing

MA Xiaowei

(School of Life Science and Technology,Xidian University,Xi’an 710071,China)

Compressed sensing(CS) theories and the reconstruction algorithm of signals are discussed.Research is done on the matching pursuit algorithms.An improvement scheme for OMP algorithm is given.To increase the convergence speed of the OMP algorithm,the image to be processed is divided into some blocks.The new scheme could significantly improve the computation efficiency.With identical conditions,the algorithm is better than the traditional one in both objective and subjective reconstruction.

compressed sensing;reconstruction algorithm;matching pursuit;image reconstruction

2014- 09- 04

马小薇(1989—),女,硕士研究生。研究方向:软件技术。E-mail:maxw1989@163.com

10.16180/j.cnki.issn1007-7820.2015.04.014

TN911.73;TP391.41

A

1007-7820(2015)04-051-04