蔣　沅，沈　培，代冀陽，陳　震

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

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

蔣沅1，2，沈培2，代冀陽2，陳震3

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

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

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

0　引言

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

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

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

1　正交匹配追蹤算法

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

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

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

假設(shè)從過完備原子集{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||，記為，并且使得函數(shù)滿足下式(其中K＝1，2，…，n)：

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

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

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

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

步驟2：選擇當前觀測信號余量rn－1最匹配的原子索引 λn：λn＝argmaxl＝1，2，…，NCl。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖4　Modelsim功能仿真

5　結(jié)論

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

圖5　Modelsim仿真效果對比圖

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

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

[3]莫禹鈞，柏正堯，黃振，等.正交匹配追蹤算法的優(yōu)化設(shè)計與FPGA實現(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].電子設(shè)計工程，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

國家自然科學(xué)基金(61164015)；江西省自然科學(xué)基金(20142BAB211003)；江西省圖像處理與模式識別重點實驗室開放基金(TX201404003)

2015-06-05)

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

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

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

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