基于正交匹配追踪的并行采样信号重构方法

王 琳，洪婉君，林文涛，张紫文，胡 忞，易朋兴

(华中科技大学机械科学与工程学院，湖北武汉 430074)

0 引言

随着科技水平与计算机技术的迅速提高，采样系统被广泛应用于众多领域中[1]，但低速的数据采样系统已经不足以满足实际应用中高速率、高精度、实时处理等需求，这也就意味着数据采样系统面临着很大的数据传输与存储压力。采样数据会通过无损压缩和有损压缩等压缩算法，在尽量不丢失信息的前提下，减少数据冗余以节约存储空间。因此，优化重构算法的研究对于高速并行采样系统起着至关重要的作用。在目前的研究中，数据重构算法主要分为以下三类：凸松弛算法、组合算法与贪婪追踪算法[2]，通过求解优化问题从少量测量值中高准确率地重构信号。

压缩感知(CS)[3-5]，作为一种最近兴起的信号处理方法,相较于传统的压缩编码更易于硬件实现。本文针对采样速率20 GSPS、采样精度12 bit、采样数据量级高达GHz的超高速并行采样系统，通过测量矩阵与采样信号进行矩阵相乘实现数据降维。在对高速数据流进行压缩的基础上，利用CS理论，对比几种常见的正交匹配追踪(orthogonal matching pursuit，OMP)算法的重构性能，提出一种经过优化改进后的重构算法，利用少量数据高精度地恢复原始信号，为后续信号的进一步处理提供有效的初始数据。

1 超高速并行采样系统信号感知与重构算法

1.1 超高速并行采样系统存储结构

本文基于ADC+FPGA的超高速采集系统架构对信号进行采集与存储处理。图1为以该架构为核心的数据采集与存储结构图。ADC对外部输入的模拟信号进行采样，由前端FPGA将采集数据进行压缩，放在DDR3缓存模块进行存储，然后经FMC传输接口传输至后端FPGA中，最终利用数据重构算法从压缩后的极少测量值中高准确率地重构信号。

图1 数据采集与存储结构图

1.2 压缩感知基本数学模型

对于长度有限、一维离散的实信号x而言，若它在某个变换基Ψ∈RN×N下是K-稀疏的。给出一个与该变换基不相关的测量矩阵Φ，则信号在该测量矩阵下作线性投影即可得到该信号的测量值y，其数学表达式如式(1)所示[6]。

y=Φx

(1)

式中：Φ为测量矩阵，Φ∈RM×N；x为原始信号，x∈RN；y为压缩后数据，y∈RM(K<

由于M<

(2)

式中‖x‖1为1范数形式。

1.3 改进正交匹配追踪算法设计

正交匹配追踪(OMP)类算法作为压缩感知工程应用的主流，常见的算法有OMP、ROMP、StOMP、CoSaMP/SP、SAMP。该类算法的思想均是在每次迭代中选择一个局部最优解来逐步逼近原始信号，区别在于原子选择策略与迭代终止条件(迭代次数)的不同。

由于StOMP算法的先验信息中不需要已知原始信号的稀疏度K，但控制重构精度的阈值ts设置比较困难。ts过大时，增加计算量，降低计算效率；ts过小时，原子正确选择几率下降，重构精度下降。故本文提出一种基于粒子群优化的分段正交匹配追踪算法的原子选择策略。利用粒子群算法全局寻优能力突出、参数少等优点[8]，结合SAMP算法自适应性与StOMP算法分阶段的思想，通过设定阈值实现原子预选；然后利用固定步长实现对预选原子复选，来降低预选过程中阈值ts设置不当的概率；最后选取合适粒子，通过迭代优化更新种群全局适应度函数值，最终得到最优重构参数。改进算法称为基于粒子群优化的预选分段正交匹配追踪(preselected stage-wise orthogonal matching pursuit with particle swarm optimization，PPStOMP)算法，具体算法描述如下：

(1)初始化：r0=y,l0=φ,A0=φ,s=1,c1=c2=2，PSO随机生成粒子数20个，速度和位置向量维数3；

(3)令Is=I0∪Js,As=As-1aj；若Is=Is-1，停止迭代进入第(8)步；

(7)如果rs≤η(η=10-6‖y‖2)，停止迭代进入第(8)步，如果s≥S,停止迭代进入第(8)步，否则转入第(2)步；

2 PPStOMP算法性能分析

2.1 PPStOMP算法参数仿真测试

在MATLAB R2017a下，测量矩阵使用高斯随机矩阵，稀疏基底使用离散小波变换基，其中小波基为Coiflet函数。实验原始信号选用Lena、Peppers、couple、boat与camera 5幅图像进行仿真测试，图像均为256×256的灰度图，适应度函数值选取为PPStOMP算法多次运行得到的平均峰值信噪比(peak signal to noise rate，PSNR)值作为评价标准，得到不同采样率M/N下各图像对应的最佳参数，如表1所示。

表1 不同采样率下PPStOMP算法最佳参数值

PSNR表达式如式(3)所示。

(3)

由表1可知，PPStOMP算法在不同采样率下对应的各最优参数值范围较大，但在相同采样率下，不同图像对应的各项参数都在最优值附近波动，因此基于测试数据做出的统计可给出PPStOMP算法各参数在不同采样率下的取值范围，如表2所示。

表2 PPStOMP算法推荐参数取值范围

2.2 PPStOMP算法一维信号重构仿真

为验证PPStOMP算法的正确性，进行一维高斯随机信号的仿真实验，使用不同稀疏度K下算法准确重构率、重构时间作为算法性能的评价指标，通过PPStOMP算法与OMP、StOMP、CoSaMP、SP、SAMP算法做对比实验。不同稀疏度水平下算法的重构性能如图2、图3所示，其中测量值M=128。实验中，PPStOMP算法各参数由上述的分析选择为ts=2.0，S=20，L=5；StOMP算法取默认值，阈值ts=2.5，迭代次数S=10；SAMP算法取步长L=5。

图2 成功重构概率与稀疏度K的关系曲线

图3 平均重构时间与稀疏度K的关系曲线

由图2可知，PPStOMP算法的重构概率在稀疏度较大时，明显优于OMP、StOMP、CoSaMP、SP算法，在一定程度上低于SAMP算法。

从图3可知，PPStOMP算法的重构时间在稀疏度较小时，与CoSaMP、SP、OMP算法接近，明显少于SAMP算法；但随着稀疏度的增大，PPStOMP的重构时间略多于StOMP算法，而CoSaMP、SP、SAMP算法的重构时间都急剧增加到PPStOMP算法的数倍。实验结果表明改进算法在稀疏度较大时明显提高了信号成功重构率，且运行时间较低，与StOMP算法相当。

为更直观地说明改进算法的正确性，采用正弦波叠加信号进行实验，信号表达式如式(4)所示。

x(n)=0.5sin(2πf1nts)+0.6sin(2πf2nts)+0.2sin(2πf3nts)

(4)

式中：n=1,2,…,N；f1=50 Hz；f2=100 Hz；f3=300 Hz。

采样频率fs=800 Hz，ts=1/fs，测量值M=64,信号长度N=256，测量矩阵Φ与稀疏基分别采用高斯随机矩阵与傅里叶矩阵，算法的仿真结果如图4所示，从图4可以看出改进算法可以很好地重构原始信号，并且重构均方误差小至10-14数量级。

图4 PPStOMP算法重构信号

2.3 PPStOMP算法图像信号重构仿真

为验证PPStOMP算法在图像重构方面的性能优劣，选取256×256的camera图像与其余几种OMP类算法及参数优化前的PStOMP进行重构对比仿真实验，选用PSNR以及重构时间作为算法对图像重构性能的评价标准。OMP、StOMP、SAMP与PPStOMP算法的参数设置与2.1节一致。

分别对各算法在采样率M/N为0.4、0.5、0.6、0.7时进行试验，每个实验重复运行50次，求其平均PSNR值以及平均重构时间。图像重构得平均PSNR值与采样率的关系如图5所示；图像重构所需的平均时间与采样率的关系如图6所示。同时，为进一步显示camera图各算法的重构性能对比，列出采样率M/N为0.7时，camera图使用OMP、StOMP、SAMP、PStOMP与PPStOMP算法的重构效果图，如图7所示。

图5 camera图采样率与各算法的PSNR关系图

图6 camera图采样率与各算法平均重构时间关系图

图7 采样率为0.7时各算法的camera重构图像

由图5可知，PPStOMP算法随采样率的提高，重构得到的PSNR值增幅最大，且PSNR值是所有算法中最大的，即图像重构效果提升最明显。由图6可知，PPStOMP算法是除了StOMP算法中用时最短的。与SAMP算法相比，PPStOMP算法的重构时间仅占它的10%左右。随着采样率的提高，PPStOMP算法的重构时间接近为水平线，算法的收敛速度较快。因此PPStOMP算法保留了StOMP算法效率高的优势。由图7可知，采样率为0.7时，各算法的重构图像已经与原始camera图像很接近了，但从每幅重构图像的放大局部图来看，PPStOMP算法的视觉效果要优于其他算法。

3 实验验证

3.1 实验设计

实验流程如图8所示。首先在FPGA中对输入的采样数据进行有符号数转换，并进行数据缓冲，然后将原始数据与读取的测量矩阵进行压缩测量得到测量值，最后将该测量值传输至上位机中，通过PPStOMP算法对压缩数据进行重构恢复。

图8 实验流程图

实验中FPGA选用Kintex-7系列的XC7K325T-2FFG900I芯片，使用信号发生器产生AD9238所需的模拟采样信号，型号为ADG6032X。整个设计的运行频率为200 MHz。实验数据来自ILA抓取得到的ADC采样数据与压缩数据，将数据导入MATLAB中，解压保存为可用excel打开的.csv格式。

3.2 实验结果与分析

在MATLAB中利用保存的压缩数据进行数据重构，与原始的ADC采样数据进行对比，其中重构算法为PPStOMP算法，测量矩阵为硬件设计中的数据存储器保存的稀疏二值矩阵，变换基为傅里叶变换矩阵。

为计算数据压缩重构后引入的失真度，实验使用信噪比(SNR)与均方误差(NMSE)来反映重构数据与原始采样数据之间的失真度。SNR和NMSE表达式如式(5)、式(6)所示。

(5)

(6)

同时为对比各算法的重构性能，除PPStOMP算法外，还采用OMP、StOMP、CoSaMP、SP、SAMP算法进行数据重构，各算法对压缩数据重构所得的NMSE与SNR如表3所示。从表3可知，本文设计的PPStOMP算法的重构误差最小，并且重构信噪比最高。

表3 各算法重构的NMSE与PSNR值

同时选取2组由示波器采集并保存得到的实际信号作算法重构分析，分别如图9与图10所示。该实际信号由频率与幅值都不相同的多个正弦波信号叠加组成，并且包含白噪声，因此应先对信号降噪处理以便与算法重构结果进行对比。

(a)实际信号1

(a)实际信号2

分别采用PPStOMP、SAMP与StOMP算法进行重构，PPStOMP算法的重构效果最好，曲线最为平滑，与降噪后的原始信号基本一致；SAMP算法的重构效果次之，StOMP算法效果最差。

该2组信号的算法重构SNR值如表4所示，从表4可知，本文设计的PPStOMP算法在OMP类算法中的重构SNR值是最高的，因此该算法的重构效果更优。

表4 实际信号的算法重构SNR值

4 结束语

本文基于超高速采集系统平台，针对压缩数据在上位机的重构问题，提出一种结合SAMP算法自适应性与StOMP算法分阶段的改进算法——基于PSO算法优化的预选分段正交匹配追踪(PPStOMP)算法。与SAMP算法相比，该改进算法的重构运行时间极大缩短；与StOMP算法相比，该改进算法在保留了原算法效率高的前提下明显提高了算法的重构成功率。通过与OMP类算法进行对比实验可知，该改进算法对原始采样信号或图像信号可以很好地重构，且算法信噪比高，均方误差小，运行时间短。