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

?

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

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

摘 要：傳統(tǒng)聲納成像系統(tǒng)所要采集的數(shù)據(jù)量巨大，給硬件設(shè)備以及數(shù)據(jù)的存儲(chǔ)和傳輸帶來(lái)很大的壓力。壓縮感知作為一種全新的采樣理論，可以從很少的采樣數(shù)據(jù)中以很大的概率重建原始信號(hào)。將壓縮感知用于聲納成像，減少數(shù)據(jù)采集傳輸量?？紤]到水下環(huán)境的復(fù)雜性，提出了A*OMP作為聲納成像算法，該算法使用A*搜索方法尋找最優(yōu)原子，得到全局最優(yōu)路徑。實(shí)驗(yàn)結(jié)果表明，相比于傳統(tǒng)OMP算法，所提算法有效地提高了聲納成像的質(zhì)量。

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

0　引言

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

壓縮感知（Compressive Sensing，CS）［1］作為一種全新的信號(hào)采集理論，通過(guò)挖掘信號(hào)的稀疏性，利用少量非相關(guān)的線性測(cè)量，結(jié)合重構(gòu)算法，可以以少量的采集數(shù)據(jù)重構(gòu)原始數(shù)據(jù)。對(duì)于聲納成像而言，在整個(gè)成像平面上，目標(biāo)圖像通常只占很小的一部分，即目標(biāo)強(qiáng)散射點(diǎn)數(shù)要遠(yuǎn)小于實(shí)際采樣數(shù)，滿足CS理論中對(duì)信號(hào)稀疏性的要求［2］。

本文基于壓縮感知理論及成像分析，闡明了CS對(duì)于聲納成像的可適用性。結(jié)合聲納數(shù)據(jù)的格式特點(diǎn)，分析了成像的具體流程。考慮到水下環(huán)境的特殊性，提出使用A *OMP（A*正交匹配追蹤）算法代替?zhèn)鹘y(tǒng)算法用于聲納圖像重構(gòu)，并通過(guò)實(shí)驗(yàn)證明了此算法對(duì)提高成像質(zhì)量的有效性，最后總結(jié)了所提方法的合理性以及需要進(jìn)一步研究的問(wèn)題。

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

1.1壓縮感知原理

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

考慮一個(gè)長(zhǎng)度為N的一維離散信號(hào)x，其稀疏度為K（K≤N），假設(shè)｛ψi｝是RN的一組基向量，信號(hào)x可表示成：

根據(jù)CS理論，可以通過(guò)構(gòu)造一個(gè)M×N的測(cè)量矩陣Φ，對(duì)x進(jìn)行M（K＜M≤N）次觀測(cè)，得到降維后的測(cè)量信號(hào)y：

式中，c＞0為一固定常數(shù)，μ（Φ，Ψ）表示Φ和Ψ之間的相關(guān)性。此時(shí)，可以利用最小l0范數(shù)將式（2）轉(zhuǎn)化為約束最優(yōu)化問(wèn)題：

由于最小l0范數(shù)的稀疏重構(gòu)問(wèn)題已被證明是NP難解的，因此常將l0范數(shù)松弛為l1范數(shù)。在實(shí)際應(yīng)用中，噪聲往往難以避免，因此將上式轉(zhuǎn)化成一個(gè)允許一定誤差存在的形式：

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

1.2CS成像分析

在CS成像模型中［4］，假設(shè)發(fā)射信號(hào)是長(zhǎng)度為N的向量，其中每個(gè)元素可以表示為

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

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

1.3CS聲納成像

本文采用StarFish 450F拖曳型側(cè)掃聲納對(duì)某水域進(jìn)行測(cè)量，并使用Scanline軟件將測(cè)量的數(shù)據(jù)導(dǎo)出格式為CSV（Comma Separated Values）的數(shù)值數(shù)據(jù)文件。該文件以純文本形式存儲(chǔ)數(shù)據(jù)，每條記錄被分隔符分隔為字段，且可以轉(zhuǎn)化為XLS的格式［6］。通過(guò)MATLAB編程實(shí)現(xiàn)對(duì)CSV數(shù)據(jù)的讀取，經(jīng)過(guò)CS稀疏重構(gòu)后，即可完成對(duì)聲納目標(biāo)的CS成像。

基于以上的分析，可將CS聲納成像步驟歸納為圖1所示。在重構(gòu)算法上，本文提出多路徑搜索的A*OMP算法代替?zhèn)鹘y(tǒng)OMP算法，提高水下成像的質(zhì)量。A*OMP算法將在下節(jié)作詳細(xì)介紹。

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

2　A*OMP算法及分析

2.1A*算法

A*算法是一種典型的啟發(fā)式搜索算法，將其與OMP算法想結(jié)合［7］，使用字典原子所代表的節(jié)點(diǎn)迭代構(gòu)建搜索樹(shù)。A*算法使用估計(jì)函數(shù)g（PK）評(píng)估每條路徑的代價(jià)，但對(duì)于不同長(zhǎng)度的路徑來(lái)說(shuō)，無(wú)法比較它們的大小。為此引入輔助函數(shù)d（），對(duì)于一個(gè)長(zhǎng)度為l的路徑Pl，定義輔助函數(shù)為：

式中，ZK-l為其余K-l個(gè)節(jié)點(diǎn)產(chǎn)生的序列。由此定義代價(jià)函數(shù)為

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

這表明路徑PK優(yōu)于Pl的所有可能擴(kuò)展路徑。因此，使用代價(jià)函數(shù)F（）選擇最優(yōu)路徑是合理的。

2.2使用A*算法進(jìn)行稀疏信號(hào)重構(gòu)

A*OMP算法將A*與OMP相結(jié)合，把稀疏重構(gòu)問(wèn)題轉(zhuǎn)化為從動(dòng)態(tài)更新的候選子集中選擇正確支撐K稀疏的信號(hào)x的問(wèn)題。A*OMP算法的迭代過(guò)程主要有以下三個(gè)步驟：

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

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

（3）選擇最優(yōu)路徑：理想情況下，輔助函數(shù)d（）應(yīng)當(dāng)與殘差衰變的路徑一致，但實(shí)際中這是很難實(shí)現(xiàn)的。為此參考文獻(xiàn)［7］中提出了3種代價(jià)模型，通過(guò)比較路徑代價(jià)函數(shù)的大小，就可以選擇出最優(yōu)路徑。

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

P：最大路徑個(gè)數(shù)

I：初始路徑個(gè)數(shù)

B：每次迭代中的節(jié)點(diǎn)擴(kuò)展個(gè)數(shù)

Li：第i條路徑的長(zhǎng)度

Ci：選擇第i條路徑的代價(jià)：第i條路徑上的原子的矩陣：第i條路徑上的原子對(duì)應(yīng)的系數(shù)向量初始化：

3　實(shí)驗(yàn)結(jié)果及分析

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

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

圖2　基于CS的聲納成像結(jié)果

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

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

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

實(shí)驗(yàn)結(jié)果表明，在時(shí)間上，由于A*OMP算法執(zhí)行的是多路徑搜索方式，因此要比OMP算法的運(yùn)行時(shí)間長(zhǎng)。然而從峰值信噪比的對(duì)比上可以看出，A*OMP算法有著比OMP算法更高的精度。隨著計(jì)算機(jī)性能的發(fā)展，時(shí)間上的差距將會(huì)被進(jìn)一步縮小，A*OMP算法的優(yōu)勢(shì)也會(huì)進(jìn)一步凸顯。

4　結(jié)論

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

參考文獻(xiàn)

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

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

［3］馬慶濤，唐加山.基于壓縮感知的測(cè)量矩陣研究［J］.微型機(jī)與應(yīng)用，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 -），男，碩士研究生，主要研究方向：智能信息處理與水下機(jī)器人。

徐志京（1972 -），男，博士，副教授，主要研究方向：水環(huán)境信號(hào)的采集處理、水下通信網(wǎng)、水聲圖像處理。

引用格式：段培培，徐志京.基于A*OMP算法的壓縮感知聲納成像［J］.微型機(jī)與應(yīng)用，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

作者簡(jiǎn)介：

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

*基金項(xiàng)目：國(guó)家自然科學(xué)基金（61404083）；上海海事大學(xué)?；穑?0120108）

中圖分類號(hào)：TP391

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.19358 /j.issn.1674-7720.2016.09.012