基于A*OMP算法的壓縮感知聲納成像*

段培培，徐志京（上海海事大學信息工程學院，上海201306）

?

基于A*OMP算法的壓縮感知聲納成像*

段培培，徐志京
（上海海事大學信息工程學院，上海201306）

摘 要：傳統聲納成像系統所要采集的數據量巨大，給硬件設備以及數據的存儲和傳輸帶來很大的壓力。壓縮感知作為一種全新的采樣理論，可以從很少的采樣數據中以很大的概率重建原始信號。將壓縮感知用于聲納成像，減少數據采集傳輸量。考慮到水下環境的復雜性，提出了A*OMP作為聲納成像算法，該算法使用A*搜索方法尋找最優原子，得到全局最優路徑。實驗結果表明，相比于傳統OMP算法，所提算法有效地提高了聲納成像的質量。

關鍵詞：壓縮感知；聲納成像；A*算法；正交匹配追蹤

0　引言

聲納是利用聲波在水下特有的傳播特性，完成水下探測和定位的重要工具。由于聲納成像可以直觀反映出被測目標的信息，因而受到研究人員的青睞。但是，為了獲得高分辨率的聲納圖像，按照傳統Nyquist采樣定理往往會產生海量數據，給硬件設備及數據的存儲和傳輸帶來巨大的壓力。

壓縮感知（Compressive Sensing，CS）［1］作為一種全新的信號采集理論，通過挖掘信號的稀疏性，利用少量非相關的線性測量，結合重構算法，可以以少量的采集數據重構原始數據。對于聲納成像而言，在整個成像平面上，目標圖像通常只占很小的一部分，即目標強散射點數要遠小于實際采樣數，滿足CS理論中對信號稀疏性的要求［2］。

本文基于壓縮感知理論及成像分析，闡明了CS對于聲納成像的可適用性。結合聲納數據的格式特點，分析了成像的具體流程。考慮到水下環境的特殊性，提出使用A *OMP（A*正交匹配追蹤）算法代替傳統算法用于聲納圖像重構，并通過實驗證明了此算法對提高成像質量的有效性，最后總結了所提方法的合理性以及需要進一步研究的問題。

1　基于壓縮感知的聲納成像及分析

1.1壓縮感知原理

壓縮感知是由DONOHO D L等人提出的一種新穎信息獲取方法，打破了Nyquist采樣定理的限制。該理論表明：當信號具有稀疏性時，可以構造一個觀測矩陣將原始信號投影到低維空間，通過采集少量的投影值就可以完成信號的近似重構。

考慮一個長度為N的一維離散信號x，其稀疏度為K（K≤N），假設｛ψi｝是RN的一組基向量，信號x可表示成：

根據CS理論，可以通過構造一個M×N的測量矩陣Φ，對x進行M（K＜M≤N）次觀測，得到降維后的測量信號y：

式中，c＞0為一固定常數，μ（Φ，Ψ）表示Φ和Ψ之間的相關性。此時，可以利用最小l0范數將式（2）轉化為約束最優化問題：

由于最小l0范數的稀疏重構問題已被證明是NP難解的，因此常將l0范數松弛為l1范數。在實際應用中，噪聲往往難以避免，因此將上式轉化成一個允許一定誤差存在的形式：

式中ε為誤差量。對于此式可以通過l1范數最小法來求解，也有學者提出了效率較高的貪婪算法，如基追蹤算法（BP）、正交匹配追蹤算法（OMP）等。

1.2CS成像分析

在CS成像模型中［4］，假設發射信號是長度為N的向量，其中每個元素可以表示為

式中n =1，2，…，N。將稀疏目標建模在N×N的距離-多普勒平面上，兩個維度分別表示延遲和多普勒頻移。那么對于一個目標物體，就存在N2個不同的回波信號，每個信號經過周期性擴展和調整后都可以轉化成長度為N的向量。N2個回波信號累積形成N×N2矩陣A。定義相干性μ（A）為

式中ai和aj為矩陣A的歸一化列，〈·，·〉表示內積。通過參考文獻［5］可知μ（A）的值很小，滿足CS理論中矩陣非相干的要求。同時，若稀疏目標數量k滿足k＜。通過給定觀測向量y和壓縮矩陣A，運用CS方法就能將稀疏向量x重構出來，即通過CS實現了稀疏目標的成像。

1.3CS聲納成像

本文采用StarFish 450F拖曳型側掃聲納對某水域進行測量，并使用Scanline軟件將測量的數據導出格式為CSV（Comma Separated Values）的數值數據文件。該文件以純文本形式存儲數據，每條記錄被分隔符分隔為字段，且可以轉化為XLS的格式［6］。通過MATLAB編程實現對CSV數據的讀取，經過CS稀疏重構后，即可完成對聲納目標的CS成像。

基于以上的分析，可將CS聲納成像步驟歸納為圖1所示。在重構算法上，本文提出多路徑搜索的A*OMP算法代替傳統OMP算法，提高水下成像的質量。A*OMP算法將在下節作詳細介紹。

圖1　基于CS的聲納成像步驟框圖

2　A*OMP算法及分析

2.1A*算法

A*算法是一種典型的啟發式搜索算法，將其與OMP算法想結合［7］，使用字典原子所代表的節點迭代構建搜索樹。A*算法使用估計函數g（PK）評估每條路徑的代價，但對于不同長度的路徑來說，無法比較它們的大小。為此引入輔助函數d（），對于一個長度為l的路徑Pl，定義輔助函數為：

式中，ZK-l為其余K-l個節點產生的序列。由此定義代價函數為

考慮一個完整路徑PK和一個局部路徑Pl（l＜K），結合式（8）和式（9），如果F（PK）≤F（Pl），可得

這表明路徑PK優于Pl的所有可能擴展路徑。因此，使用代價函數F（）選擇最優路徑是合理的。

2.2使用A*算法進行稀疏信號重構

A*OMP算法將A*與OMP相結合，把稀疏重構問題轉化為從動態更新的候選子集中選擇正確支撐K稀疏的信號x的問題。A*OMP算法的迭代過程主要有以下三個步驟：

（1）初始化搜索樹：由于僅有K≤N個字典原子是與y有關的，因此將初始子集限制為I（I≤K）個，每個子集包含一個原子，這些原子與y有最大的內積絕對值。

（2）擴展局部路徑：由于數量眾多的子集會產生大量搜索路徑，故采用3種修剪策略加以限制，分別為設置每條路徑的單次擴展數量B、設置搜索樹中最大路徑數量P以及對等效路徑的修剪。

（3）選擇最優路徑：理想情況下，輔助函數d（）應當與殘差衰變的路徑一致，但實際中這是很難實現的。為此參考文獻［7］中提出了3種代價模型，通過比較路徑代價函數的大小，就可以選擇出最優路徑。

A*OMP算法的流程如下：定義：

P：最大路徑個數

I：初始路徑個數

B：每次迭代中的節點擴展個數

Li：第i條路徑的長度

Ci：選擇第i條路徑的代價：第i條路徑上的原子的矩陣：第i條路徑上的原子對應的系數向量初始化：

3　實驗結果及分析

實驗采用1.3節中所述CSV數據段，聲納參數設置如下：頻率450 kHz，帶寬40 kHz，掃描幅度60 m，聲速1 470 m/s。取左舷數據進行處理，其中測量回波數及每個方位向的數據長度均為256，采樣點數設置為100。A* OMP算法參數設置為B =2，I=3，P=200，實驗所得結果如圖2所示。

從圖2可以看出，CS方法在降低采樣率的同時，也確保了成像的質量。相比傳統OMP算法，基于A*OMP的聲納成像方法保留了河底的絕大部分輪廓信息，成像質量更佳。為了更加直觀地表述兩種算法的成像質量，在不同降采樣率的基礎上，繪制成像成功率變化曲線如圖3所示。

圖2　基于CS的聲納成像結果

圖3　成像成功率的變化曲線

由圖3可以看出，隨著降采樣率的增加，兩種算法的成像成功率都是先上升直至趨于1，但A*OMP上升趨勢明顯要高于OMP。對兩種算法的運行時間和峰值信噪比進行記錄，具體結果如表2所示。

表2　A*OMP和OMP成像效果比較

實驗結果表明，在時間上，由于A*OMP算法執行的是多路徑搜索方式，因此要比OMP算法的運行時間長。然而從峰值信噪比的對比上可以看出，A*OMP算法有著比OMP算法更高的精度。隨著計算機性能的發展，時間上的差距將會被進一步縮小，A*OMP算法的優勢也會進一步凸顯。

4　結論

本文將壓縮感知技術用于聲納成像中，從理論上闡明了CS對于聲納成像的可適用性，并分析了具體的成像流程。在重構算法上，以A*OMP取代傳統的OMP算法，采用多路徑的迭代搜索方式尋找全局最優解。實驗結果表明所提算法與傳統OMP算法相比較，成像質量與精度有了很大的改善，但在運算效率與成像質量的平衡上面有待進一步研究，在提高運算效率的同時提高成像的精度。

參考文獻

［1］DONOHO D L.Compressed Sensing［J］.IEEE Transactions on Information Theory，2006，52（4）：1289-1306.

［2］賀西麗.壓縮感知在聲納成像中的應用研究［D］.哈爾濱：哈爾濱工業大學，2012.

［3］馬慶濤，唐加山.基于壓縮感知的測量矩陣研究［J］.微型機與應用，2013，32（8）：64-67.

［4］HERMAN M A，STROHMER T.High-resolution radar via compressed sensing［J］.IEEE Transactions on Signal Processing，2009，57（6）：2275-2284.

［5］YAN H，Peng Shibao，Zhu Zhaotong，et al.W ideband sonar imaging via compressed sensing［C］.OCEANS 2014-TAIPEI. IEEE，2014：1-4.

［6］Zhang Weifei，Yang Ye，Wang Guoqiang.Comma sepa-rated value（CSV）to M icrosoft Excel（XLS）format conversion mode：CN，CN 102541903 A［P］.2012.

［7］KARAHANOGLU N B.A* orthogonalmatching pursuit：Best first search for compressed sensing signal recovery［J］.Digital Signal Processing，2012，22（4）：555-568.

段培培（1992 -），男，碩士研究生，主要研究方向：智能信息處理與水下機器人。

徐志京（1972 -），男，博士，副教授，主要研究方向：水環境信號的采集處理、水下通信網、水聲圖像處理。

引用格式：段培培，徐志京.基于A*OMP算法的壓縮感知聲納成像［J］.微型機與應用，2016，35（10）：33-35，39.

Compressive sensing sonar imaging based on A*OMP algorithm

Duan Peipei，Xu Zhijing
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China）

Abstract：Traditional sonar imaging systems need to collectmassive amounts of data.It's bringingmuch pressure to the hardware equipment as well as the data storage and transmission.As a novel sampling theory，compressive sensing can reconstruct the original signal in large probability from the few samp ling data.This paper uses compressive sensing for sonar imaging to reduce the amount of data acquisition and transm ission.Considering the comp lexity of underwater environment，A* Orthogonal Matching Pursuit（A*OMP）algorithm is proposed as sonar imaging algorithm.This algorithm uses A*search to find the optimal atoms，and gets the global optimal path.The experimental results show that compared with the traditional OMP algorithm，the proposed method effectively improves the quality of the sonar imaging.

Key w ords：compressive sensing；sonar imaging；A*search；orthogonalmatching pursuit

作者簡介：

收稿日期：（2016-01-20）

*基金項目：國家自然科學基金（61404083）；上海海事大學校基金（20120108）

中圖分類號：TP391

文獻標識碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.012