压缩感知重构算法研究

张永立　黄芳　范志勇

【摘 要】压缩感知是一种全新的信号采样重构方法，和传统的方法相比，它不再要求信号的采样率达到信号带宽的两倍以上，这样就克服了资源浪费，效率低下等缺陷，本文研究了压缩感知理论，并在此基础上研究了多种重构算法，并应用五种典型的压缩感知重构算法来重构二维彩色图片和二维灰度图片，客观的对比了两种算法的实验效果。

【关键词】压缩感知;重构算法

中图分类号： TN911.7 文献标识码： A 文章编号： 2095-2457（2019）10-0046-002

DOI：10.19694/j.cnki.issn2095-2457.2019.10.017

Research on Compression Perception Reconstruction Algorithm

ZHANG Yong-li HUANG Fang FAN Zhi-yong

（Jiaozuo Teachers College，Department of Mathematics， Institute of Applied Mathematics， Jiaozuo HeNan 454002，China）

【Abstract】Compressed sensing is a new method of signal sampling and reconstruction. Compared with the traditional method， it no longer requires the sampling rate of signal to be more than twice the bandwidth of signal， which overcomes the shortcomings of waste of resources and inefficiency. This paper studies the theory of compressed sensing， and on this basis， studies a variety of reconstruction algorithms， and applies five typical compressed sensing reconstruction algorithms to reconstruct. A two-dimensional color image and a two-dimensional gray image objectively compare the experimental results of the two algorithms.

【Key words】Compressed Sensing; Reconstruction Algorithms

0 引言

随着信息技术的发展，信息传输量越来越大，信息存储、传输和重构问题成为研究热点。传统Shannon-Nyquist采样理论要求采样率须达到信号带宽的两倍以上，资源使用率高.而在实际中，除了想高精度重构该信号外，也想降低存储和传输成本.为解决此问题，基于泛函分析、信号逼近和稀疏逼近的理论，统计学专家Donoho、华裔数学家陶哲轩、Romberg、Candes、Baraniuk等科学家提出了压缩感知理论[1-3]。

本文在压缩感知理论的基础上，总结多种重构算法，并采用五种典型压缩感知重构算法来重构一个二维彩色图片和一个二维灰度图片，在考虑时间效率和重构效果的双重前提下，比较各算法对不同类型图片的重构效果。

1 压缩感知重构算法

压缩感知重构算法大致可分为三类基本方法，第一类是贪婪算法，首先选取合适的原子，再逐步进行递增，进而逼近信号矢量，利用这种过程进行重构的方法统称作匹配追踪算法（MP）。MP算法中，具有代表性的有正交匹配追踪算法[4]（OMP），正则正交匹配追踪算法[5]（ROMP），压缩采样匹配追踪算法[6]（CoSaMP），稀疏自适应匹配追踪算法[7]（SAMP）。

另一类是凸松弛类算法，它将非凸问题转化为凸问题进行求解，即l0范数转化成l1范数并采用线性规划来求解，有代表性的包括同伦算法（HA），原始-对偶内点发（PDIPA），对偶增广拉格朗日乘数算法（DALM），原始增广拉格朗日乘数算法（PALM），迭代收缩阀算法（IST）等。

第三类是组合算法，该类算法一般要求信号的采样支持通过分组测试来实现原始信号的快速高精度重建。组合算法包括链式追踪算法、傅里叶采样算法等。

2 仿真实验

本节对二维彩色图片和二维灰度图片，采用BP、PALM、DALM、PAIPA以及Homotopy五种压缩感知重构算法对两类图片进行重构，使用的评价标准是峰值性噪比的大小，即：

其中MSE为均方误差。实验所采用的电脑配置是Intle酷睿i3 8100T（3.1GHz），内存为4GB，采用的软件为Matlab R2018a。

在不存在测量噪声的情况下，首先对原图像做了80次学习，然后使用以上五种算法分别对它进行重构，表1的第三列分别显示了五种算法所耗费的时间和PSNR，从表1中可以看出，在考慮时间效率和重构效果的双重因素下，PDIPA算法的效果更好。

下面进行有噪声的测量，目的是为了考察这五种典型算法的鲁棒性。首先对二维灰度图片的原图做80次学习，然后加入四种不同类型的噪声，分别是高斯白噪声（gaussian）、泊松噪声（poisson）、椒盐噪声（salt&pepper）和斑点噪声（speckle），然后应用BP、PALM、DALM、PAIPA以及Homotopy这五种算法对加入噪声的图片进行仿真实验。

表1的第四到七列分别显示出这五种算法在加入四种噪音后的重构结果和所耗时长，从表中的对比结果可以看出，在考虑重构效率和重构效果的双重前提下，Homotopy算法既考虑了时间因素，并且重构结果最好。

接下来得实验，我们采用一幅256*256的彩色图片。首先对彩色图像进行100次学习，选用小波基作为稀疏基去生成测量矩阵，用BP、PALM、DALM、PAIPA以及Homotopy这五种算法分别对其进行了仿真实验，使用PSNR来评价重建图像的质量。不存在噪声时，图2-3给出了五种算法的比较结果。表2的第三列分别列出了五种算法所耗费的时间和PSNR。从结果看出，同时考虑时间因素和重构效果，PDIPA算法的效果更好。

下面考虑了有噪声的测量，目的是为了考察这五种算法对彩色图像的鲁棒性。首先对原图做100次学习，并对其加入高斯白噪声（gaussian）、泊松噪声（poisson）、椒盐噪声（salt&pepper）和斑点噪聲（speckle），然后应用BP、PALM、DALM、PAIPA以及Homotopy五种算法对二维彩色图片进行仿真实验.以斑点噪声为例，在100次学习并存在斑点噪声时.这五种算法在四种噪声下的耗时时间和重构结果分别展示在表2的第四到七列.显然，在考虑重构效率和重构效果的双重前提下，PALM算法的效果较好。

3 结论

本文总结了一些压缩感知的经典重构算法以及相互关系，并将BP、PALM、DALM、PAIPA以及Homotopy五种算法应用到了二维灰度图像和二维彩色图像的重构仿真实验当中，实验结果显示，若同时考虑时间效率和重构效果的情况下，重构灰度图片时，Homotopy算法效果较好，对于彩色图像，PALM算法效果较好。

【参考文献】

[1]孙玉宝，肖亮，韦志辉，等.基于Gabor感知多成份字典的图像稀疏表示算法研究[J].自动化学报，2008，34（11）：1379-1387.

[2]李树涛，魏丹.压缩传感综述[J].自动化学报，2009，35（11）：1369-1377.

[3]杨海蓉，张成，丁大为，等.压缩传感理论与重构算法[J].电子学报，2011，39（1）：142-148.

[4]Muthukrishnan S.Data streams：Algorithms and applications[M].Now Publishers Inc，2005.

[5]Tropp J A，Gilbert A C.Signal recovery from random measu-

rements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory， 2007，53（12）：4655-4666.

[6]Needell D，Vershynin R.Greedy signal recovery and uncerta-

inty principles[C].Electronic Imaging 2008.International Society for Optics and Photonics，2008：68140J-68140J-12.

[7]Needell D，Tropp J A.CoSaMP：Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis，2009，26（3）：301-321.