一種基于FPGA實(shí)現(xiàn)的優(yōu)化正交匹配追蹤算法設(shè)計(jì)*

蔣　沅，沈　培，代冀陽(yáng)，陳　震

(1.江西省圖像處理與模式識(shí)別重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063；2.南昌航空大學(xué) 信息工程學(xué)院，江西 南昌 330063；3.南昌航空大學(xué) 無(wú)損檢測(cè)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063)

一種基于FPGA實(shí)現(xiàn)的優(yōu)化正交匹配追蹤算法設(shè)計(jì)*

蔣沅1，2，沈培2，代冀陽(yáng)2，陳震3

(1.江西省圖像處理與模式識(shí)別重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063；2.南昌航空大學(xué) 信息工程學(xué)院，江西 南昌 330063；3.南昌航空大學(xué) 無(wú)損檢測(cè)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江西 南昌 330063)

針對(duì)壓縮感知重構(gòu)算法中正交匹配追蹤(OMP)算法在每次迭代中不能選取最優(yōu)原子問(wèn)題，對(duì)OMP算法進(jìn)行優(yōu)化設(shè)計(jì)，保證了每次迭代的當(dāng)前觀測(cè)信號(hào)余量最小，并提出了一種基于FPGA實(shí)現(xiàn)的優(yōu)化OMP算法硬件結(jié)構(gòu)設(shè)計(jì)。在矩陣分解部分采用了修正喬列斯基(Cholesky)分解方法，回避開(kāi)方運(yùn)算，以減少計(jì)算延時(shí)，易于FPGA實(shí)現(xiàn)。整個(gè)系統(tǒng)采用并行計(jì)算、資源復(fù)用技術(shù)，在提高運(yùn)算速度的同時(shí)減少資源利用。在 Quartus II開(kāi)發(fā)環(huán)境下對(duì)該設(shè)計(jì)進(jìn)行了RTL級(jí)描述，并在FPGA仿真平臺(tái)上進(jìn)行仿真驗(yàn)證。仿真結(jié)果驗(yàn)證了設(shè)計(jì)的正確性。

壓縮感知；正交匹配追蹤算法；修正喬列斯基分解；FPGA

0　引言

傳統(tǒng)信號(hào)獲取和處理過(guò)程主要采用奈奎斯特采樣定律實(shí)現(xiàn)，而奈奎斯特采樣定律要求采樣頻率不得低于模擬信號(hào)頻譜中最高頻率的兩倍，這使得高頻信號(hào)采集實(shí)現(xiàn)受到極大限制。隨著信息技術(shù)快速發(fā)展，信號(hào)帶寬急劇增加，工業(yè)進(jìn)入大數(shù)據(jù)時(shí)代，因此對(duì)信號(hào)處理能力和硬件設(shè)備要求也越來(lái)越高，給龐大數(shù)據(jù)處理帶來(lái)了挑戰(zhàn)[1]。

壓縮感知理論[2]具有數(shù)據(jù)采集與壓縮同時(shí)進(jìn)行處理的優(yōu)點(diǎn)，用較少的數(shù)據(jù)就可以準(zhǔn)確地恢復(fù)原始信號(hào)，從而使得受制于奈奎斯特采樣定理的采樣頻率能夠掙脫束縛，在較低的采樣頻率下也能夠?qū)崿F(xiàn)。壓縮感知理論包括三方面內(nèi)容：信號(hào)稀疏表示、測(cè)量矩陣的構(gòu)造、信號(hào)重構(gòu)算法設(shè)計(jì)。信號(hào)重構(gòu)算法設(shè)計(jì)是壓縮感知理論研究關(guān)鍵的優(yōu)化算法和基于貪婪迭代的匹配追蹤算法。以正交匹配追蹤算[4](Orthogonal Matching Pursuit，OMP)為代表的貪婪類及其改進(jìn)算法[5-6]相對(duì)于其他方法具有信號(hào)重建速度快、運(yùn)算量小等優(yōu)點(diǎn)。

目前，壓縮感知信號(hào)重構(gòu)硬件設(shè)計(jì)還處于初步階段，仍有許多問(wèn)題值得探究，學(xué)者們?cè)谶@方面做了一系列工作。文獻(xiàn)[7]對(duì)壓縮感知信號(hào)重構(gòu)算法進(jìn)行超大規(guī)模集成電路(Very Large Scale Integration，VLSI)設(shè)計(jì)。按照特定順序?qū)MP算法硬件設(shè)計(jì)執(zhí)行資源復(fù)用技術(shù)，提高了資源利用率，運(yùn)行速率更快[8]。文獻(xiàn)[9]闡述了基于FPGA的LU分解方法，能夠在計(jì)算機(jī)平臺(tái)上得到很好的加速性能，然而，在LU分解過(guò)程中存在大量矩陣乘除法運(yùn)算，需要占用 FPGA大量硬件資源，導(dǎo)致運(yùn)算延遲。本文在矩陣分解部分采用修正Cholesky分解方法，回避了開(kāi)方運(yùn)算，減少了乘法運(yùn)算次數(shù)，使運(yùn)算速度更快。

1　正交匹配追蹤算法

在壓縮感知采樣過(guò)程中，原始信號(hào)x∈RN稀疏度為K(K＜＜N)，設(shè)計(jì)一個(gè) M×N(M＜＜N)的隨機(jī)測(cè)量矩陣 Φ，將隨機(jī)測(cè)量矩陣中的列向量 fl(l＝1，2，…，n)稱為原子。根據(jù)壓縮感知理論，將稀疏信號(hào)在隨機(jī)測(cè)量矩陣中進(jìn)行投影，得到一個(gè)比原始信號(hào)長(zhǎng)度小很多的M×l觀測(cè)向量y∈RN。匹配追蹤算法的核心思想是在第N次迭代中從隨機(jī)測(cè)量矩陣Φ中選擇與當(dāng)前觀測(cè)信號(hào)余量r(初始化為觀測(cè)信號(hào)y)最匹配的原子。將選出的原子增加至候選子集Γ中形成新的候選子集。根據(jù)候選子集，計(jì)算新的估計(jì)信號(hào)和新的觀測(cè)信號(hào)余量r，在下一次迭代中，繼續(xù)選擇與觀測(cè)信號(hào)余量最匹配的原子形成新的候選子集，用以計(jì)算和r直至迭代結(jié)束。

2　優(yōu)化正交匹配追蹤算法設(shè)計(jì)

2.1優(yōu)化正交匹配追蹤算法原子選擇準(zhǔn)則

假設(shè)從過(guò)完備原子集{fi，i＝1，2，…，n}中選出的一個(gè)子集，定義，其中⊕表示空間的正交和，定義 Wn+1是 Vn+1和 Vn的正交補(bǔ)空間，記 PVn+1為 Vn+1上的正交投影算子，則，其中，則在 Wn+1上的正交投影記為 Φn+1。Φn+1可以等效為：

對(duì)式(1)中 Φn+1進(jìn)行歸一化，n+1＝Φn+1/||Φn+1||，記為，并且使得函數(shù)滿足下式(其中K＝1，2，…，n)：

利用參考文獻(xiàn)[6]結(jié)論，得出測(cè)量值 y在 Vn+1上的正交投影式：

在式(3)基礎(chǔ)上得出 y在 Vn+1上的正交投影系數(shù)為（其中K＝1，2，…，n）：

2.2優(yōu)化正交匹配追蹤算法計(jì)算步驟

分析了優(yōu)化正交匹配追蹤算法原子選擇準(zhǔn)則后，優(yōu)化后的OMP算法的重構(gòu)算法計(jì)算步驟如下：

步驟2：選擇當(dāng)前觀測(cè)信號(hào)余量rn－1最匹配的原子索引 λn：λn＝argmaxl＝1，2，…，NCl。

步驟 3；更新候選子集 Γn＝Γn-1∪λn，記錄傳感矩陣中的重構(gòu)原子集合。

步驟 6：n＝n+1，如果 n＜k，則返回到步驟 2，直到得到最后的近似信號(hào)，否則停止迭代。

2.3優(yōu)化正交匹配追蹤算法硬件結(jié)構(gòu)設(shè)計(jì)

優(yōu)化OMP算法可以分為4個(gè)模塊，第1個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟 2，經(jīng)過(guò)原子選擇，利用式(1)～式(5)求出殘差最匹配原子。

第2個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟3，通過(guò)更新候選子集Γ，生成增廣矩陣。

第3個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟4，求解l0范數(shù)最小模型問(wèn)題，解決最小二乘法問(wèn)題，得到原始信號(hào)的估計(jì)值。求解增廣矩陣逆的方法來(lái)得出原始估計(jì)值。然而，矩陣是非方形矩陣，對(duì)于求非方形矩陣一般是使用偽逆(Moore－Penrose)的方法求解，矩陣偽逆可以表示為：

矩陣分解有QR分解[10]、奇異值分解、LU分解、Cholesky分解[11]。QR分解和奇異值分解計(jì)算過(guò)程復(fù)雜，不易于FPGA的實(shí)現(xiàn)，LU分解在分解過(guò)程中會(huì)有大量的矩陣乘法和除法的計(jì)算操作，它一方面占用FPGA硬件資源，另一方面影響計(jì)算效率。雖然，在Cholesky分解計(jì)算中會(huì)產(chǎn)生開(kāi)方操作的延時(shí)以及除法計(jì)算，但是復(fù)雜度相對(duì)于LU分解較少。針對(duì) Cholesky分解在計(jì)算中產(chǎn)生開(kāi)方操作的延時(shí)問(wèn)題，利用 Cholesky分解，回避了開(kāi)方運(yùn)算帶來(lái)的延時(shí)問(wèn)題。具體修正Cholesky分解計(jì)算公式如下：

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

第4個(gè)模塊對(duì)應(yīng)重構(gòu)算法計(jì)算步驟5，計(jì)算殘差r，為下次迭代做準(zhǔn)備。

3　基于FPGA實(shí)現(xiàn)的優(yōu)化OMP算法

硬件電路主要由四個(gè)模塊組成，分為兩大部分。具體電路圖如圖1所示。

圖1　優(yōu)化OMP算法硬件電路結(jié)構(gòu)圖

第一部分給定兩個(gè)輸入量，分別是測(cè)量矩陣Φ和觀測(cè)矢量y，由輸入的觀測(cè)矢量y∈RN對(duì)殘差r進(jìn)行初始化。每個(gè)矩陣的列向量長(zhǎng)為N，設(shè)計(jì)N個(gè)乘法器和N－1個(gè)加法器并行處理，它們可以在一個(gè)時(shí)鐘周期內(nèi)完成工作，測(cè)量矩陣Φ和殘差r同時(shí)也在一個(gè)時(shí)鐘內(nèi)完成。觀測(cè)矢量y用多個(gè)寄存器組進(jìn)行存儲(chǔ)，用多個(gè)RAM存儲(chǔ)測(cè)量矩陣值Φ。利用式(1)～式(6)優(yōu)化后的原子選擇準(zhǔn)則求出原子索引λn，通過(guò)步驟3更新候選子集得到重構(gòu)矩陣。求解公式，得出矩陣 G。

第二部分對(duì)矩陣 G求逆過(guò)程，硬件電路由 Cholesky分解硬件電路、矩陣L求逆硬件電路和相乘運(yùn)算硬件電路組成。利用修正的Cholesky分解矩陣G，分解矩陣G分別要求出下三角矩陣L和對(duì)角矩陣D。然后進(jìn)行相乘，使得G＝L×D×LT，從而回避平方操作。其中矩陣L和矩陣D之間是相互依存的，其元素必須按照特定的順序進(jìn)行計(jì)算。最后對(duì) G－1求解，G－1＝(L－1)T×D－1×L－1，可以先令O＝(L－1)T×D－1，對(duì)O進(jìn)行計(jì)算，然后可方便計(jì)算G－1＝O×L－1。

4　仿真驗(yàn)證

通過(guò)一維信號(hào)對(duì)優(yōu)化OMP算法和OMP算法進(jìn)行重建實(shí)驗(yàn)比較。假設(shè)稀疏信號(hào) x的長(zhǎng)度N＝256，稀疏系數(shù)k＝6，OMP、優(yōu)化OMP算法采用高斯隨機(jī)測(cè)量矩陣 Φ∈RM×N，分別記錄優(yōu)化 OMP算法和OMP算法的重建成功率，將其結(jié)果繪制成圖，如圖2所示。

圖2　高斯矩陣下成功率與測(cè)量次數(shù)之間的關(guān)系

在同樣處理器工作下，通過(guò)二維圖像信號(hào)實(shí)驗(yàn)驗(yàn)證優(yōu)化OMP算法的有效性。實(shí)驗(yàn)中選取尺度為256像素× 256像素的經(jīng)典實(shí)驗(yàn)圖像 Lena，采用高斯隨機(jī)矩陣作為測(cè)量矩陣。OMP算法與本文優(yōu)化OMP算法進(jìn)行重構(gòu)實(shí)驗(yàn)對(duì)比，重構(gòu)結(jié)果如圖3所示。

圖3　采樣率M/N＝50%，lena圖像在兩種重構(gòu)算法下的重構(gòu)結(jié)果

當(dāng)采樣率M/N=50%，采用Lena圖像測(cè)試時(shí)，優(yōu)化OMP算法、OMP算法信噪比分別為34.53 dB、33.72 dB。因此，優(yōu)化后的OMP算法比OMP算法重建精度要高。

通過(guò)FPGA仿真軟件Modelsim對(duì)優(yōu)化OMP算法硬件電路進(jìn)行了仿真，如圖4和圖5所示。

圖4　Modelsim功能仿真

5　結(jié)論

本文通過(guò)優(yōu)化原子選擇準(zhǔn)則，使得OMP重建本文算法能夠在很短的時(shí)間內(nèi)選擇最優(yōu)原子，縮短了信號(hào)重構(gòu)時(shí)間，提高了算法重建速率。同時(shí)，本文優(yōu)化設(shè)計(jì)了FPGA硬件結(jié)構(gòu)，較好地平衡了占用資源和運(yùn)算時(shí)間。本設(shè)計(jì)采用硬件描述語(yǔ)言Verilog HDL對(duì)優(yōu)化OMP重建算法實(shí)現(xiàn)，運(yùn)用Quartus軟件進(jìn)行算法綜合，進(jìn)行了RTL級(jí)描述，通過(guò) Matlab和 Modelsim進(jìn)行聯(lián)合仿真，得到了較好的重建效果。結(jié)果表明，優(yōu)化后的OMP算法能夠以較少時(shí)間恢復(fù)原始信號(hào)。

圖5　Modelsim仿真效果對(duì)比圖

[1]任越美，張艷寧，李映.壓縮感知及其圖像處理應(yīng)用研究進(jìn)展與展望[J].自動(dòng)化學(xué)報(bào)，2014，40(8)：1563-1575.

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

[3]莫禹鈞，柏正堯，黃振，等.正交匹配追蹤算法的優(yōu)化設(shè)計(jì)與FPGA實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，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重構(gòu)算法及應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，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分解的快速矩陣求逆方法設(shè)計(jì)[J].電子設(shè)計(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

國(guó)家自然科學(xué)基金(61164015)；江西省自然科學(xué)基金(20142BAB211003)；江西省圖像處理與模式識(shí)別重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(TX201404003)

2015-06-05)

蔣沅(1982-)，男，副教授，主要研究方向：非線性控制理論及應(yīng)用、圖像圖形處理、飛行設(shè)計(jì)及應(yīng)用。

沈培(1989-)，男，碩士研究生，主要研究方向：圖像圖形處理、嵌入式應(yīng)用。

代冀陽(yáng)(1966-)，男，教授，主要研究方向：智能控制技術(shù)及應(yīng)用、嵌入式應(yīng)用。

中文引用格式：蔣沅，沈培，代冀陽(yáng)，等.一種基于 FPGA實(shí)現(xiàn)的優(yōu)化正交匹配追蹤算法設(shè)計(jì)[J].電子技術(shù)應(yīng)用，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.