一種基于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.