段培培，徐志京

　　（上海海事大學(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：

　　y=Φx=ΦΨα=Θα(2)

　　式中Θ稱為感知矩陣。CS理論要求測(cè)量矩陣Φ的建立應(yīng)當(dāng)使Θ=ΦΨ滿足RIP(Restricted Isometry Property)條件［3］，并且測(cè)量次數(shù)M應(yīng)滿足：

　　M≥cμ2(Φ,Ψ)KlogN≤N(3)

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

　　minα0s.t.y=Θα(4)

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

　　minα1s.t.y－Θα2≤ε(5)

　　式中ε為誤差量。對(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<12(1+1/μ(A))。通過(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ì)介紹。

2A*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ù)為:

　　d(Pl)≥g(Pl)－g(Pl∪ZK－l),d(PK)=0(8)

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

　　F(Pl)=g(Pl)－d(Pl)(9)

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

　　g(PK)≤g(Pl∪ZK－l),ZK－l(10)

　　這表明路徑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à)

　　Si={sli}：第i條路徑上的原子sli的矩陣

　　ci={cli}：第i條路徑上的原子sli對(duì)應(yīng)的系數(shù)向量

　　初始化：

　　T←

　　for i←1 to I do%設(shè)置初始路徑長(zhǎng)度為1

　　←argmax〈y,vn〉n,vn∈ΦT

　　T←T∪n

　　s1i←n,c1i←〈y,n〉

　　ri←y－c1is1i

　　Ci=F(Si),Li=1

　　end for

　　Ci=y2,Li=0,i=I+1,I+2,…,P

　　best_path←1

　　while Lbest_path≠K do

　　←best_path%替換搜索路徑

　　T←Sbest_path

　　for i←1 to B do%對(duì)每條擴(kuò)展路徑進(jìn)行修剪

　　←argmax〈rbest_path,vn〉n,vn∈ΦT

　　T←T∪v

　　←Sbest_path∪v%候選路徑

　　←argminy－α2 %正交投影

　　←F()%候選路徑的代價(jià)

　　if(<F(S))&%樹(shù)尺寸修剪

　　(≠Sj,j=1,2,…,P) then %等效路徑修剪

　　S←,c←,C←

　　L←Lbest_path+1

　　r←y－Sc

　　←argmaxCii∈1,2,…，P

　　end if

　　end for

　　best_path←argminCii∈1,2,…,P%選擇最優(yōu)路徑

　　end while

　　return Sbest_path,cbest_path

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所示。

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

　　實(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)

　?。?］ DONOHO D L. Compressed Sensing ［J］. IEEE Transactions on Information Theory, 2006, 52(4): 12891306.

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

　?。?］ 馬慶濤，唐加山．基于壓縮感知的測(cè)量矩陣研究 ［J］.微型機(jī)與應(yīng)用,2013,32(8):6467.

　?。?］ HERMAN M A, STROHMER T. Highresolution radar via compressed sensing ［J］. IEEE Transactions on Signal Processing, 2009, 57(6): 22752284.

　?。?］ YAN H, Peng Shibao, Zhu Zhaotong,et al. Wideband 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 Microsoft Excel (XLS) format conversion mode: CN, CN 102541903 A ［P］. 2012.

　?。?］ KARAHANOGLU N B. A* orthogonal matching pursuit: Best first search for compressed sensing signal recovery ［J］. Digital Signal Processing, 2012, 22(4): 555568.