[發明專利]一種面向硬件實現的快速投影原子選擇正交匹配追蹤重構算法

在審

• 申請號: 202110451299.2
• 申請日: 2021-04-26
• 公開（公告）號: CN113300713A
• 公開（公告）日: 2021-08-24
• 發明（設計）人: 劉素娟;鄭麗麗
• 申請（專利權）人: 北京工業大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 劉萍

一種面向硬件實現的快速投影原子選擇正交匹配追蹤重構算法屬于圖像處理領域。該算法在投影原子選擇階段不再采用每次迭代選取單一索引識別策略，而是使用多個能量最大的原子的索引并行選擇的方法，極大的減少了算法迭代次數，降低了計算復雜度，大幅度提高計算效率；在算法關鍵步驟最小二乘問題解決階段，使用改進的基于修正的格雷姆施密特QR分解算法，免開平方根，簡化最小二乘問題的求解；使用矩陣增量分解的方式，基于相同的已分解矩陣的結構設計出了兩個不同的增量分解過程，提高了數據重用率，減少硬件資源，加快計算速度；在投影過程中使用了新穎的部分投影處理方式，減少了計算量。本發明Fast?POMP算法相比傳統算法更加適用于硬件實現。

技術領域

本發明涉及一種基于壓縮感知(Compressed Sensing，CS)理論的面向硬件實現的快速投影原子選擇正交匹配追蹤(Fast Projection-based Atom Selection inOrthogonal Matching Pursuit,Fast-POMP)重構算法。適用于數字信號處理、圖像處理等技術領域。

背景技術

壓縮感知(CS)理論為稀疏信號的亞奈奎斯特頻率采樣另辟蹊徑，壓縮感知理論通過滿足約束等距條件的測量矩陣將信號從高維空間映射到低維空間，從而實現采樣和壓縮的同步進行。所以壓縮感知理論在圖像處理、生物傳感、無線通訊和模式識別等領域有著廣泛的前景與運用。許多稀疏信號重構算法原型被提出，主要包括三大類：凸松弛算法，利用非凸優化技術的算法和貪婪算法。其中，貪婪算法是通過迭代的方式一步一步逼近原始信號，相對另外兩類算法而言，貪婪算法耗費資源少，更便于硬件實現。貪婪算法包括匹配追蹤算法(Matching Pursuit，MP)、正交匹配追蹤算法(Orthogonal Matching Pursuit，OMP)、子空間追蹤算法(Subspace Pursuit，SP)、壓縮采樣匹配追蹤算法(CompressiveSampling Matching Pursuit,CoSaMP)、分段正交匹配追蹤算法(Stagewise OrthogonalMatching Pursuit，StOMP)、基于投影的原子選擇正交匹配追蹤算法(Projection-basedAtom Selection in Orthogonal Matching Pursuit,POMP)等。

由于軟件恢復信號存在實時性差，自適應性差的缺點，所以重構算法最終要面向硬件實現。這就不僅要考慮算法的重構精度、重構速度，還要考慮重構算法的計算復雜度、硬件資源耗費等各種因素。MP算法減少了矩陣的正交性，信號重構精度低；SP和CoSaMP算法的恢復性能較好，但是硬件實現規模龐大，芯片面積增大造成高成本；StOMP算法雖然不需要信號稀疏度先驗，但是門限值的設置與測量矩陣有著密切的關系，當前研究只有門限值設置的經驗值，沒有理論值。OMP算法因其計算簡潔，計算速度快而被廣泛用作硬件實現的方法。但是當感知矩陣規模固定，稀疏度大幅度增大時，OMP算法的恢復性能無法滿足要求。POMP算法為了在信號稀疏度增高的情況下也能完美恢復信號，在OMP算法的基礎上加入了投影原子選擇操作。但是，代價是計算量龐大，計算復雜度上升，計算時間增加，計算效率降低。

本發明旨在提出一種基于壓縮感知理論的面向硬件實現快速投影原子選擇正交匹配追蹤重構算法，能夠極大地降低POMP算法的計算復雜度，減少計算時間，大幅度提高計算效率，更便于硬件實現。

發明內容