段培培，徐志京（上海海事大学信息工程学院，上海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