一种基于FPGA实现的优化正交匹配追踪算法设计*

蒋　沅，沈　培，代冀阳，陈　震

(1.江西省图像处理与模式识别重点实验室，江西 南昌 330063；2.南昌航空大学 信息工程学院，江西 南昌 330063；3.南昌航空大学 无损检测技术教育部重点实验室，江西 南昌 330063)

一种基于FPGA实现的优化正交匹配追踪算法设计*

蒋沅1，2，沈培2，代冀阳2，陈震3

(1.江西省图像处理与模式识别重点实验室，江西 南昌 330063；2.南昌航空大学 信息工程学院，江西 南昌 330063；3.南昌航空大学 无损检测技术教育部重点实验室，江西 南昌 330063)

针对压缩感知重构算法中正交匹配追踪(OMP)算法在每次迭代中不能选取最优原子问题，对OMP算法进行优化设计，保证了每次迭代的当前观测信号余量最小，并提出了一种基于FPGA实现的优化OMP算法硬件结构设计。在矩阵分解部分采用了修正乔列斯基(Cholesky)分解方法，回避开方运算，以减少计算延时，易于FPGA实现。整个系统采用并行计算、资源复用技术，在提高运算速度的同时减少资源利用。在 Quartus II开发环境下对该设计进行了RTL级描述，并在FPGA仿真平台上进行仿真验证。仿真结果验证了设计的正确性。

压缩感知；正交匹配追踪算法；修正乔列斯基分解；FPGA

0　引言

传统信号获取和处理过程主要采用奈奎斯特采样定律实现，而奈奎斯特采样定律要求采样频率不得低于模拟信号频谱中最高频率的两倍，这使得高频信号采集实现受到极大限制。随着信息技术快速发展，信号带宽急剧增加，工业进入大数据时代，因此对信号处理能力和硬件设备要求也越来越高，给庞大数据处理带来了挑战[1]。

压缩感知理论[2]具有数据采集与压缩同时进行处理的优点，用较少的数据就可以准确地恢复原始信号，从而使得受制于奈奎斯特采样定理的采样频率能够挣脱束缚，在较低的采样频率下也能够实现。压缩感知理论包括三方面内容：信号稀疏表示、测量矩阵的构造、信号重构算法设计。信号重构算法设计是压缩感知理论研究关键的优化算法和基于贪婪迭代的匹配追踪算法。以正交匹配追踪算[4](Orthogonal Matching Pursuit，OMP)为代表的贪婪类及其改进算法[5-6]相对于其他方法具有信号重建速度快、运算量小等优点。

目前，压缩感知信号重构硬件设计还处于初步阶段，仍有许多问题值得探究，学者们在这方面做了一系列工作。文献[7]对压缩感知信号重构算法进行超大规模集成电路(Very Large Scale Integration，VLSI)设计。按照特定顺序对OMP算法硬件设计执行资源复用技术，提高了资源利用率，运行速率更快[8]。文献[9]阐述了基于FPGA的LU分解方法，能够在计算机平台上得到很好的加速性能，然而，在LU分解过程中存在大量矩阵乘除法运算，需要占用 FPGA大量硬件资源，导致运算延迟。本文在矩阵分解部分采用修正Cholesky分解方法，回避了开方运算，减少了乘法运算次数，使运算速度更快。

1　正交匹配追踪算法

在压缩感知采样过程中，原始信号x∈RN稀疏度为K(K＜＜N)，设计一个 M×N(M＜＜N)的随机测量矩阵 Φ，将随机测量矩阵中的列向量 fl(l＝1，2，…，n)称为原子。根据压缩感知理论，将稀疏信号在随机测量矩阵中进行投影，得到一个比原始信号长度小很多的M×l观测向量y∈RN。匹配追踪算法的核心思想是在第N次迭代中从随机测量矩阵Φ中选择与当前观测信号余量r(初始化为观测信号y)最匹配的原子。将选出的原子增加至候选子集Γ中形成新的候选子集。根据候选子集，计算新的估计信号和新的观测信号余量r，在下一次迭代中，继续选择与观测信号余量最匹配的原子形成新的候选子集，用以计算和r直至迭代结束。

2　优化正交匹配追踪算法设计

2.1优化正交匹配追踪算法原子选择准则

假设从过完备原子集{fi，i＝1，2，…，n}中选出的一个子集，定义，其中⊕表示空间的正交和，定义 Wn+1是 Vn+1和 Vn的正交补空间，记 PVn+1为 Vn+1上的正交投影算子，则，其中，则在 Wn+1上的正交投影记为 Φn+1。Φn+1可以等效为：

对式(1)中 Φn+1进行归一化，n+1＝Φn+1/||Φn+1||，记为，并且使得函数满足下式(其中K＝1，2，…，n)：

利用参考文献[6]结论，得出测量值 y在 Vn+1上的正交投影式：

在式(3)基础上得出 y在 Vn+1上的正交投影系数为（其中K＝1，2，…，n）：

2.2优化正交匹配追踪算法计算步骤

分析了优化正交匹配追踪算法原子选择准则后，优化后的OMP算法的重构算法计算步骤如下：

步骤2：选择当前观测信号余量rn－1最匹配的原子索引 λn：λn＝argmaxl＝1，2，…，NCl。

步骤 3；更新候选子集 Γn＝Γn-1∪λn，记录传感矩阵中的重构原子集合。

步骤 6：n＝n+1，如果 n＜k，则返回到步骤 2，直到得到最后的近似信号，否则停止迭代。

2.3优化正交匹配追踪算法硬件结构设计

优化OMP算法可以分为4个模块，第1个模块对应重构算法计算步骤 2，经过原子选择，利用式(1)～式(5)求出残差最匹配原子。

第2个模块对应重构算法计算步骤3，通过更新候选子集Γ，生成增广矩阵。

第3个模块对应重构算法计算步骤4，求解l0范数最小模型问题，解决最小二乘法问题，得到原始信号的估计值。求解增广矩阵逆的方法来得出原始估计值。然而，矩阵是非方形矩阵，对于求非方形矩阵一般是使用伪逆(Moore－Penrose)的方法求解，矩阵伪逆可以表示为：

矩阵分解有QR分解[10]、奇异值分解、LU分解、Cholesky分解[11]。QR分解和奇异值分解计算过程复杂，不易于FPGA的实现，LU分解在分解过程中会有大量的矩阵乘法和除法的计算操作，它一方面占用FPGA硬件资源，另一方面影响计算效率。虽然，在Cholesky分解计算中会产生开方操作的延时以及除法计算，但是复杂度相对于LU分解较少。针对 Cholesky分解在计算中产生开方操作的延时问题，利用 Cholesky分解，回避了开方运算带来的延时问题。具体修正Cholesky分解计算公式如下：

由式(8)～式(10)得出，矩阵G的逆如下：

第4个模块对应重构算法计算步骤5，计算残差r，为下次迭代做准备。

3　基于FPGA实现的优化OMP算法

硬件电路主要由四个模块组成，分为两大部分。具体电路图如图1所示。

图1　优化OMP算法硬件电路结构图

第一部分给定两个输入量，分别是测量矩阵Φ和观测矢量y，由输入的观测矢量y∈RN对残差r进行初始化。每个矩阵的列向量长为N，设计N个乘法器和N－1个加法器并行处理，它们可以在一个时钟周期内完成工作，测量矩阵Φ和残差r同时也在一个时钟内完成。观测矢量y用多个寄存器组进行存储，用多个RAM存储测量矩阵值Φ。利用式(1)～式(6)优化后的原子选择准则求出原子索引λn，通过步骤3更新候选子集得到重构矩阵。求解公式，得出矩阵 G。

第二部分对矩阵 G求逆过程，硬件电路由 Cholesky分解硬件电路、矩阵L求逆硬件电路和相乘运算硬件电路组成。利用修正的Cholesky分解矩阵G，分解矩阵G分别要求出下三角矩阵L和对角矩阵D。然后进行相乘，使得G＝L×D×LT，从而回避平方操作。其中矩阵L和矩阵D之间是相互依存的，其元素必须按照特定的顺序进行计算。最后对 G－1求解，G－1＝(L－1)T×D－1×L－1，可以先令O＝(L－1)T×D－1，对O进行计算，然后可方便计算G－1＝O×L－1。

4　仿真验证

通过一维信号对优化OMP算法和OMP算法进行重建实验比较。假设稀疏信号 x的长度N＝256，稀疏系数k＝6，OMP、优化OMP算法采用高斯随机测量矩阵 Φ∈RM×N，分别记录优化 OMP算法和OMP算法的重建成功率，将其结果绘制成图，如图2所示。

图2　高斯矩阵下成功率与测量次数之间的关系

在同样处理器工作下，通过二维图像信号实验验证优化OMP算法的有效性。实验中选取尺度为256像素× 256像素的经典实验图像 Lena，采用高斯随机矩阵作为测量矩阵。OMP算法与本文优化OMP算法进行重构实验对比，重构结果如图3所示。

图3　采样率M/N＝50%，lena图像在两种重构算法下的重构结果

当采样率M/N=50%，采用Lena图像测试时，优化OMP算法、OMP算法信噪比分别为34.53 dB、33.72 dB。因此，优化后的OMP算法比OMP算法重建精度要高。

通过FPGA仿真软件Modelsim对优化OMP算法硬件电路进行了仿真，如图4和图5所示。

图4　Modelsim功能仿真

5　结论

本文通过优化原子选择准则，使得OMP重建本文算法能够在很短的时间内选择最优原子，缩短了信号重构时间，提高了算法重建速率。同时，本文优化设计了FPGA硬件结构，较好地平衡了占用资源和运算时间。本设计采用硬件描述语言Verilog HDL对优化OMP重建算法实现，运用Quartus软件进行算法综合，进行了RTL级描述，通过 Matlab和 Modelsim进行联合仿真，得到了较好的重建效果。结果表明，优化后的OMP算法能够以较少时间恢复原始信号。

图5　Modelsim仿真效果对比图

[1]任越美，张艳宁，李映.压缩感知及其图像处理应用研究进展与展望[J].自动化学报，2014，40(8)：1563-1575.

[2]DONOHO D.Compressed sensing[J].IEEE Trans.Info. Theory，2006，52(4)：1289-1306.

[3]莫禹钧，柏正尧，黄振，等.正交匹配追踪算法的优化设计与FPGA实现[J].电子技术应用，2014，50(10)：79-82.

[4]WANG J，KWON S，SHIM B.Generalized orthogonal matching pursuit[J].IEEE Trans.on Signal Processing，2012，60(12)：6202-6216.

[5]WU R，HUANG W，CHEN D R.The exact support recovery of sparse signals with noise via orthogonal matching pursuit[J]. IEEE Trans.on signal processing letters，2013，20(4)：403-406.

[6]李少东，裴文炯，杨军，等.贝叶斯模型下的 OMP重构算法及应用[J].系统工程与电子技术，2015，37(2)：246-252.

[7]SEPTINUS A，STEINBERG R.Compressive sampling hard ware reconstruction[C].Circuits and systems(ISCAS)，Proc.of 2010 IEEE Internatioal symposium on.IEEE，2010：316-3319.

[8]BLACHE P，RABAH H，AMIRA A.High level prototyping and FPGA implementation of the orthogonal matching pursuitalgorithm[C].Information Scien，Signal Processing and their Applications(ISSPA)，2012：1336-1340.

[9]WU G，DOU Y，PETERSON G D.Blocking LU decomposition for FPGAs[C].IEEE.Proceeding of FCCM′10.ChArlotte：IEEE，2010：109-112．

[10]STANISLAUS J.L.V.M，MOHSENIN T.High performance compressive sensing reconstruction hardware with QRD process[C].Circuits and Systems(ISCAS)，2012，IEEE. International Symposium on.IEEE，2012：29-32.

[11]魏婵，娟张春，水刘健.一种基于Cholesky分解的快速矩阵求逆方法设计[J].电子设计工程，2014，22(1)：159-164.

An orthogonal matching pursuit algorithm optimization design based on FPGA implementation

Jiang Yuan1，2，Shen Pei2，Dai Jiyang2，Chen Zhen3
(1.Jiangxi Province Key Laboratory of Image Processing and Pattern Recognition，Nanchang 330063，China；2.College of Information Engineering，Nanchang Hangkong University，Nanchang 330063，China；3.Key Laboratory of Nondestructive Testing of Ministry of Education，Nanchang Hangkong University，Nanchang 330063，China)

According to compression sensing reconstruction algorithm of orthogonal matching pursuit(OMP)algorithm the problem of each iteration can't select the optimal atomic,to optimize the OMP algorithm design,ensures that each iteration of the current allowance minimum observation signal,and proposes a kind of optimize the OMP algorithm based on FPGA to realize the hardware structure design.In the matrix decomposition part adopts modified Cholesky decomposition methods,avoid root operation,to reduce the calculation time delay,easy to FPGA implementation.The whole system adopts parallel computing,resource reuse technology,improve the computing speed and reduce resource utilization.In the Quartus II development environment for the design of the RTL description,on the FPGA simulation platform for simulation,the simulation results verify the validity of the design.

compressed sensing；orthogonal matching pursuit；modified Cholseky decomposition；FPGA

TN911.2

A

10.16157/j.issn.0258-7998.2015.10.020

国家自然科学基金(61164015)；江西省自然科学基金(20142BAB211003)；江西省图像处理与模式识别重点实验室开放基金(TX201404003)

2015-06-05)

蒋沅(1982-)，男，副教授，主要研究方向：非线性控制理论及应用、图像图形处理、飞行设计及应用。

沈培(1989-)，男，硕士研究生，主要研究方向：图像图形处理、嵌入式应用。

代冀阳(1966-)，男，教授，主要研究方向：智能控制技术及应用、嵌入式应用。

中文引用格式：蒋沅，沈培，代冀阳，等.一种基于 FPGA实现的优化正交匹配追踪算法设计[J].电子技术应用，2015，41 (10)：73-76，80.

英文引用格式：Jiang Yuan，Shen Pei，Dai Jiyang，et al.An orthogonal matching pursuit algorithm optimization design based on FPGA implementation[J].Application of Electronic Technique，2015，41(10)：73-76，80.