一种声图直航段数据自动提取及镶嵌的方法∗

江泽林　张鹏飞　翟厚曦　刘维　刘纪元

（中国科学院声学研究所北京100190）

一种声图直航段数据自动提取及镶嵌的方法∗

江泽林†张鹏飞翟厚曦刘维刘纪元

（中国科学院声学研究所北京100190）

声图镶嵌是利用成像声纳获得声图进行测深、水下地形地貌测绘的重要应用方向。常见的成像声纳多要求声纳载体做直线运动，而实际应用中载体有大量转弯的情况。为此提出了一种声图直航段数据自动提取方法，该方法首先利用Douglas-Peucker算法对声纳航迹进行抽稀处理，之后利用相邻抽稀点之间的距离判断数据是否为直航段，最后将直航段图像提取出来。获得直航段数据后，利用地理信息对声图进行镶嵌处理。对千岛湖湖底地貌图像进行了处理，获得了较好的镶嵌结果。

声图镶嵌，直航段声图，Douglas-Peucker算法

1　引言

声纳是利用水下声波进行目标探测和定位的设备［1］，其中成像声纳是通过主动发射声波，利用反射声波的时延、强度、相位等特性，经过信号处理，获得水深或水底地形地貌的一类声纳。典型的条带式成像声纳有单波束侧扫声纳、多波束侧扫声纳、多波束测深声纳、测深侧扫声纳、合成孔径声纳等［2-4］。

成像声纳多要求载体做直线运动，这是因为一方面在转弯时声纳的姿态稳定性较差，另一方面许多成像声纳的成像算法要求声纳做直线运动。而在实际航行中，受到水域限制，并且为了多次、多视角地对目标进行成像，声纳的航迹通常仅在一定时间内保持直航，这样获得的声纳数据是由直航段数据和非直航段（如转弯）数据间隔相连组成的。而后期应用中通常只需要直航段数据，由于声纳图像数据量较大，使用人工提取直航段的方法对时间和人力资源消耗较大，为此亟需提出声纳数据直航段自动提取的方法。

在声纳图像的后期应用中，声图镶嵌是非常重要的一个方面［5］。通过声图镶嵌技术，将窄条带的声图镶嵌形成大范围水下声图，有助于水下地理信息系统的进一步构建；有利于目标定位；有利于湖海底资源勘探、水下工程实施等［6］。

在上述背景下，本文研究了基于Douglas-Peucker算法的声纳数据直航段自动提取方法以及基于地理信息的声图镶嵌方法。在直航段数据提取方法中，首先使用Douglas-Peucker算法对航迹线进行抽稀处理，相邻抽稀点之间的距离大于设定阈值的判断为直航段，之后利用帧号等辅助信息截取声图的直航段数据。在声图镶嵌中，基于声纳载体或拖曳平台的绝对地理位置信息（如GPS），利用载体或平台与声纳本身的相对位置关系，推算得到直航段图像关键点的绝对位置坐标，例如四个顶点的位置，最后利用这些坐标将声图镶嵌在地球模型上。利用成像声纳中典型的合成孔径声纳的实际图像数据进行实验，以验证提出方法的可行性。

2　直航段数据自动提取方法

2.1Douglas-Peucker算法基本原理

Douglas-Peucker算法是一种抽稀算法［7］。抽稀的含义是在数字化过程中，需要对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度上保持原有的形状。

Douglas-Peucker算法利用递归（迭代）的思想，以一段曲线的抽稀为例，其基本步骤如下：

（1）将曲线的首尾两点连成直线，判断曲线上各点到直线的距离；

（2）如果最大距离不大于阈值，则用首尾两点来代替曲线；

（3）如果最大距离大于阈值，则利用最大距离对应的曲线点将曲线分为两段，对每段曲线继续使用上述判断方法。

如图1所示，利用Douglas-Peucker算法将曲线AB进行抽稀后，得到了6个抽稀点，即可以用折线ADCEFB来取代曲线AB。

图1　Douglas-Peucker算法示意图Fig.1Simplifying a curve with the Douglas-Peucker algorithm

2.2数据直航段提取基本流程

在研究了Douglas-Peucker算法的基础上，针对成像声纳的工作特点，如图2提出声图数据直航段提取的基本处理流程如下：

（1）设定系统参数。系统的参数主要包括以下内容：

a.Douglas-Peucker算法中使用到的抽稀距离阈值Dth，即判断两点间曲线上到连接两点的直线距离最大的点与该阈值的关系，如果大于该阈值，则对该曲线进一步处理，否则视为该曲线可以近似为直线，由两端点来表示。

b.直航段距离阈值Dth_Azimuth，即判断相邻两个抽稀点之间的距离是否超过该阈值，如果超过，则认为该段为直航，否则认为是非直航。

（2）提取数据的航迹位置信息和帧号等辅助信息

通常在声纳载体上安装有定位设备，声纳数据文件中除了回波数据或图像数据外，还附加有航迹位置信息，以方便后期应用中的使用。较典型的航迹位置信息是GPS信息。

（3）利用Douglas-Peucker算法对航迹点进行抽稀处理

传统Douglas-Peucker算法在实现时使用递归迭代实现，这种实现方法虽然可读性较好，但效率较低，对内存有较高要求，尤其当航迹线较长、转弯较多时，递归调用的层数太大。本文研究了利用堆栈实现Douglas-Peucker算法的方法，见本文第2.4节。

图2　声纳数据直航段提取基本步骤Fig.2Extracting flow of straight track sonar images

（4）判断相邻抽稀点的距离是否超过设定的直航段阈值，选择超过阈值的航迹点对

设抽稀点集Q包含M个航迹点，依次判断相邻抽稀点对Qi和Qi+1（i=1，2，···，M-1）之间的实际距离DQi，Qi+1，如果DQi，Qi+1和设定阈值之间满足式（1），则认为Qi和Qi+1之间的航迹为直航，其数据可以被抽取出来进行处理。

否则认为Qi和Qi+1之间的距离过小，数据量不足以进行直航处理，该段数据可以被忽略。直航段起始点和结束点构成直航段端点集T，满足式（2）。

（5）根据航迹点对的帧号等辅助信息，相应地从数据中提取直航段数据

根据直航段端点集T，获得端点对应的帧号等辅助信息，根据帧号等信息从数据中提取直航段数据。

2.3抽稀距离阈值和直航段距离阈值设置方法

对于声纳数据，上述算法中使用的抽稀距离阈值Dth和直航段距离阈值Dth_Azimuth的设置主要考虑声纳成像原理、位置信息的精度等。以合成孔径声纳为例进行说明。

首先查看直航段距离阈值Dth_Azimuth的设置。合成孔径声纳成像原理表明，完整获得一行图像需要声纳在方位向上的直航段长度达到一个合成孔径长度dsyn。

其中λ为声波波长，D为基阵孔径，Rmax为最大探测距离。

理论上设置Dth_Azimuth为dsyn即可，但在实际应用中，由于设置了抽稀距离阈值Dth，且当拖缆入水长度较长、拖体重量较重，对转弯半径要求较高时，转弯时较大的转弯半径会产生一些短距离的符合直航条件的数据，但由于其航距太短，图像数据的实际意义并不大，在实际应用中应当将其剔除。为此设置Dth_Azimuth可更大，即

ρ1为阈值包含的合成孔径数量的因子，一般可取5—10。

其次查看抽稀距离阈值Dth的设置。合成孔径声纳为相干成像，相邻帧数据的相关性对成像质量有较大的影响，在不进行运动补偿处理的前提下，相邻两帧数据的运动误差大于八分之一波长时，成像结果就会产生明显的模糊［8］。以最差情形查看，即在一段截取的直航段中，前二分之一行程的运动误差为正向累积，后二分之一行程的运动误差为反向累积。如图3所示，实际航迹为ACB，抽稀处理后以直线段AB替代。

其中到直线段AB最远的航迹点C的距离应为成像原理限制下的抽稀距离阈值Dth1，有下列关系

其中l为直航段长度，v为声纳运动速度，tprt为脉冲发射间隔，λ为声波波长。l进行进一步替换

其中dsyn为合成孔径长度，ρ2为可调系数，使抽稀距离阈值Dth与直航段距离阈值Dth_Azimuth联系起来。

图3　声纳包含运动误差的运动轨迹和抽稀处理示意图Fig.3 Sonar track with additional motion errors and its simplifying

此外抽稀距离阈值的设置还受到位置信息的精度影响，声纳位置信息的获取有几种方式。对于拖曳式声纳，即有两种方式，一种是利用水声定位系统（如超短基线定位系统）实时获取拖体相对于母船的位置，利用母船的位置计算拖体的绝对位置信息；另一种由于拖体空间较小或者考虑成本因素，仅在母船上安装导航定位设备（如GPS），利用航向、拖缆入水长度和拖体深度推算拖体相对母船的位置，再利用母船的位置计算拖体的绝对位置。相对来说，由于拖缆入水长度、水中形态的难以检测，以及受到水流影响，拖缆的指向与母船的航向并不总能保持一致的影响，利用拖缆长度推算拖体位置的精度较低。对于以水下无人航行器（UUV）为载体平台的成像声纳，由于应具有自主导航特性，UUV本身通常要配备高精度的惯性导航系统（Inertial navigation system，INS），用以实时计算UUV的位置信息。UUV惯导系统的一个特点是会产生累积误差，因此长时间累积后绝对位置偏差较大。

精度可用误差的概率密度来表征，此时精度为σpos的函数。即由位置信息的精度决定的抽稀距离阈值Dth2为在一些定位产品的介绍中，通常使用1倍标准差来表征位置精度。此时

在实际应用中，由于定位设备理论精度的获取比较困难，因此可直接利用定位设备产品的标称精度来参与抽稀距离阈值的计算。

综上所述，针对合成孔径声纳总的抽稀阈值为

2.4Douglas-Peucker算法的堆栈实现

传统Douglas-Peucker算法在实现时具有效率较低，对内存要求较高的特点，当航迹线较长、转弯较多时，这种特点对实现可行性要求更高。为此本文研究了利用堆栈实现的方法。与递归实现相比，可以提高效率、节省计算时间和消耗的空间。该方法主要步骤如下所述。

（1）初始化。初始化的内容包括：设定抽稀阈值Dth；开辟向量空间P，依次存储航迹点的位置信息；开辟两个堆栈A和B，用来存放关键航迹点的点序号。在A中压入元素1，B中压入元素N（设航迹点的数量为N），分别表示第一个航迹点P1和最后一个航迹点PN的序号，如图4（a）所示。

（2）从堆栈A中读取栈顶元素i，并获取航迹点Pi的位置信息；从堆栈B中读取栈顶元素j，并获取航迹点Pj的位置信息，如图4（b）所示。

（3）计算航迹向量P中Pi到Pj之间各点到直线PiPj的距离，并获取其中的最大值Dk，设对应距离最大值的航迹点为Pk。

（4）比较Dk与抽稀阈值Dth大小。如果Dk≥Dth，认为Pi和Pj之间的曲线段不能近似为直线，此时将航迹点Pk的点序号k压入堆栈B中，同时堆栈B的栈顶指针加1，如图3（c）所示；如果Dk＜Dth，认为Pi和Pj之间的曲线段可以近似为直线，将j从堆栈B中删除，并压入堆栈A中，同时堆栈A的栈顶指针加1，堆栈B的栈顶指针减1，如图4（d）所示。

（5）重复执行上述第（2）至第（4）步骤，直到堆栈B为空。

（6）依序根据堆栈A中的元素，找到相应的航迹点组成点集，就是最终的抽稀点集，设为航迹点向量Q，显然Q为P的子集。

图4　Douglas-Peucker算法的堆栈实现示意图Fig.4 Realization of Douglas-Peucker algorithm based on stack

3　利用地理信息的声图镶嵌方法

3.1声纳位置推算

对于AUV和船载声纳，在对定位精度要求不高的条件下，可认为载体的位置就是声纳的位置。

对于拖曳式声纳，当获得的位置信息是母船位置信息时，由于拖缆较长，不能将母船位置与声纳位置等同。此时需要根据拖缆长度、声纳深度、航向信息推算声纳位置，如图5所示。

图5　声纳拖曳示意图Fig.5 Geometry of sonar towed fish

设拖缆长度为l，声纳深度为d，母船航向角为θ（以正北为0°，取值范围为0°—360°），UTM坐标（Universal transverse mercator system，通用横墨卡托地理坐标系）下的母船位置为（x0，y0），则根据几何关系可以求■得拖体的位置为

3.2声图任意点位置计算

获得声纳位置信息后，可计算图像上各点的位置。设待求像素点的UTM位置为（x，y），相应时刻声纳的UTM坐标为（x1，y1），该点所在图像位置距离图像内侧边缘有N个像素点，距离成像分辨率为δr，距离向采样最小距离为xmin，如图6所示。

图6　目标位置与声纳位置关系示意图Fig.6 Geometry for the positions of target and sonar

则利用平面几何关系可得到待求像素点的位置为［6］

获得待求点的UTM坐标后，再将其转换至经纬度坐标系，即得到其位置信息。针对直航图像，可只计算关键点的经纬度坐标，即图像四个顶点的坐标。获得这些坐标后，可将图像镶嵌在地球模型中。

4　实际数据处理

合成孔径声纳是一种典型的成像声纳，本节对实际的合成孔径声纳图像应用上述方法。项目组在浙江省千岛湖进行了合成孔径声纳湖试试验，获得了丰富的数据，对某一航次的数据应用了本文提出的直航段自动提取及声图镶嵌方法。获得的航迹抽稀点与原始航迹的关系如图7所示，其中原航迹线上位置信息点的数据量为22072点，抽稀后仅为208点。从图中可以看出，在直航段抽稀点分布稀疏，在声纳平台转弯的地方抽稀点分布密集。判断相邻抽稀点的距离是否大于阈值，可以将直航段数据提取出来。

图7　航迹抽稀处理实例Fig.7 Example of reducing the number of points on a real track

获得直航段数据后，根据声纳位置信息计算各直航段图像四个顶点的地理位置，最后将多幅声图镶嵌在地球模型中，结果如图8所示，其尺度约为1400 m×1400 m。千岛湖是1959年在新安江马铜官峡筑坝兴建水电站而形成的人工湖，淹没的淳安县城及其周边古村落历史悠久，因此千岛湖湖底地貌非常丰富。从图8可以看出，镶嵌结果中有两个明显的特点，一是其西北角有大量民居遗迹，二是东侧和西侧有两条河流遗迹。

图8　千岛湖地貌镶嵌实例Fig.8 Mosaicked result of the physiognomy images of the Qiandao Lake bed

根据声图镶嵌结果中的GPS位置信息，在筑坝建湖前的淳安县老地图上进行标定，获取镶嵌图像在老地图上的大致位置，如图9所示。标示区域中的一条河流分为两支，并且该区域位于淳安县城东南近郊，与镶嵌结果的两个特点相吻合。

图9　1959年前淳安县地图局部Fig.9 Part of the Chun'an county map before 1959

5　结论

本文提出了声纳数据直航段自动提取及利用地理信息的声图镶嵌方法。在声纳数据直航段自动提取阶段，利用Douglas-Peucker算法对航迹点进行抽稀处理，利用抽稀点之间的距离判断直航段并自动提取。在实现上，利用堆栈的方法改进了原理算法中的递归方法，提高了实现的效率。在声图镶嵌阶段，利用声图的地理信息进行镶嵌。对实际的千岛湖湖试数据进行了处理，获得了湖底地貌的镶嵌结果，验证了方法的有效性。

［1］BJØRNØ L.Developments in sonar and array technologies［C］.2011 IEEE Symposium on Underwater Technology and Workshop on Scientific Use of Submarine Cables and Related Technologies，Tokyo，Japan，2011：1-11.

［2］WILLIAM H K.Side scan sonar technology［C］.Oceans 2000MTS/IEEEConferenceProceedings，2000，2：1029-1033.

［3］LIU Xiaodong，ZHU Weiqing，FANG Changle，et al.Shallow water high resolution bathymetric side scan sonar［C］. Oceans 2007 Europe，2007：1-6.

［4］HAYES M P，GOUGH P T.Synthetic aperture sonar：a review of current status［J］.IEEE Journal of Oceanic Engineering，2009，34（3）：207-224.

［5］REED S，RUIZ I T，CAPUS C，et al.The fusion of large scale classified side-scan sonar image mosaics［J］. IEEE Transactions on Image Processing，2006，15（7）：2049-2060.

［6］江泽林.合成孔径声纳大范围成像关键技术研究［D］.北京：中国科学院声学研究所，2013.

［7］DOUGLAS D，PEUCKER T.Algorithms for the reduction of the number of points required to represent a digitized line or its caricature［J］.The Canadian Cartographer，1973，10（2）：112-122

［8］BONIFANT W.Interferometic synthetic aperture sonar processing［D］.Atlanta：Georgia Institute Of Technology，1999.

A straight track sonar images auto-extracting and mosaicking method

JIANG ZelinZHANG PengfeiZHAI HouxiLIU WeiLIU Jiyuan
（Institute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China）

Sonar image mosaicking is an essential application in the underwater oceanographic survey.Usually imaging sonars assume that the platform traverses a perfectly straight track.However this is the seldom case since the sonar platforms often swerve for planned or unplanned reasons.Thus a method automatically extracting the sonar image segments whose tracks are straight is proposed.For a sonar track consisting of all the sonar positioning points，the Douglas-Peucker algorithm is applied to get a much smaller subset of points that could define the sonar track approximately.Then if the distance between two adjacent points in the subset is longer than a threshold，the relevant image is extracted as a straight segment.Finally the straight segments are mosaicked on an earth model based on their geographic positions.For validation the method is applied to segment and mosaic the real sonar images in the Qiandao Lake trial.Results show the affectivity of the proposed method.

Sonar image mosaic，Straight track sonar images，Douglas-Peucker algorithm

TB566

A

1000-310X（2015）04-0333-06

10.11684/j.issn.1000-310X.2015.04.007

2014-08-13收稿；2014-12-29定稿

∗国家自然科学基金项目（11204343），中国科学院声学研究所青年人才领域前沿项目（Y454311211），哈尔滨工程大学水下机器人技术重点实验室基金项目（9140C27020112022601）

江泽林（1985-），男，山西黎城人，助理研究员，博士，研究方向：水声信号处理，水声图像处理。

E-mail：jzl@mail.ioa.ac.cn