段培培，徐志京

　　（上海海事大学 信息工程学院，上海 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：

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

　　式中Θ称为感知矩阵。CS理论要求测量矩阵Φ的建立应当使Θ=ΦΨ满足RIP(Restricted Isometry Property)条件［3］，并且测量次数M应满足：

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

　　式中，c>0为一固定常数，μ(Φ,Ψ)表示Φ和Ψ之间的相关性。此时，可以利用最小l0范数将式(2)转化为约束最优化问题:

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

　　由于最小l0范数的稀疏重构问题已被证明是NP难解的，因此常将l0范数松弛为l1范数。在实际应用中，噪声往往难以避免，因此将上式转化成一个允许一定误差存在的形式:

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

　　式中ε为误差量。对于此式可以通过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<12(1+1/μ(A))。通过给定观测向量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算法将在下节作详细介绍。

2A*OMP算法及分析

　　2.1A*算法

　　A*算法是一种典型的启发式搜索算法，将其与OMP算法想结合［7］，使用字典原子所代表的节点迭代构建搜索树。A*算法使用估计函数g(PK)评估每条路径的代价，但对于不同长度的路径来说，无法比较它们的大小。为此引入辅助函数d()，对于一个长度为l的路径Pl，定义辅助函数为:

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

　　式中，ZK－l为其余K－l个节点产生的序列。由此定义代价函数为

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

　　考虑一个完整路径PK和一个局部路径Pl(l<K)，结合式(8)和式(9)，如果F(PK)≤F(Pl)，可得

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

　　这表明路径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条路径的代价

　　Si={sli}：第i条路径上的原子sli的矩阵

　　ci={cli}：第i条路径上的原子sli对应的系数向量

　　初始化：

　　T←

　　for i←1 to I do%设置初始路径长度为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%对每条扩展路径进行修剪

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

　　T←T∪v

　　←Sbest_path∪v%候选路径

　　←argminy－α2 %正交投影

　　←F()%候选路径的代价

　　if(<F(S))&%树尺寸修剪

　　(≠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%选择最优路径

　　end while

　　return Sbest_path,cbest_path

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

　　由图3可以看出，随着降采样率的增加，两种算法的成像成功率都是先上升直至趋于1，但A*OMP上升趋势明显要高于OMP。对两种算法的运行时间和峰值信噪比进行记录，具体结果如表2所示。 

　　实验结果表明，在时间上，由于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. 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.

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