基于总体最小二乘的Douglas-Peucker算法在多波束测深数据抽稀中的应用

卢银宏,岳东杰,宋飞凤

(河海大学 地球科学与工程学院,江苏南京 210098)

基于总体最小二乘的Douglas-Peucker算法在多波束测深数据抽稀中的应用

卢银宏,岳东杰,宋飞凤

(河海大学 地球科学与工程学院,江苏南京 210098)

Douglas-Peucker算法是多波束数据抽稀的主要算法之一,通过保留特征点来达到抽稀的目的,这导致了抽稀后的数据与原始数据精度的极度不一致,无法很好地反映水下地形的真实情况。基于总体最小二乘的Douglas-Peucker算法,在采用Douglas-Peucker算法确定特征点的基础上,充分利用多波束测深原始数据的信息进行分段总体最小二乘拟合,从而达到更真实地反应海底状况的目的。通过对仿真海底地形模拟计算,结果表明:与Douglas-peucker算法相比,该算法能够更加逼近原始数据,提高抽稀精度。

Douglas-Peucker算法;多波束探测;总体最小二乘;抽稀

海洋测绘是一切海洋开发活动的基础,海底地形测量是海洋测绘基础性任务之一。随着科学技术的发展,多波束测深系统已经成为了当今世界进行海底测量先进技术手段的杰出代表。采用多波束测深系统具有全覆盖、高精度,能够准确全面的反映水下地形起伏变化的情况的特点,但是产生的数据量极大,通常会产生TB级的数据量[1]。面对如此海量的数据,快速有效的数据抽稀算法已成为了多波束测深数据处理中一项不可缺少的技术。对于多波束测深抽稀方法,一般采用Douglas-Peucker算法,但由于Douglas-Peucker算法仅利用垂向距离作为约束条件来决定曲线上点的取舍,并没有采用任何优化方法,抽稀得到的数据也无法最优逼近原始数据。基于此,本文采用基于总体最小二乘的Douglas-Peucker算法充分利用原始数据,从整体上逼近原始数据,以便获得更加逼真的海底地形图。

1 Douglas-Peucker算法

Douglas-Peucker算法是通过保留关键点删除次要点来达到抽稀的目的,其算法的基本思想是:首先选取曲线的两个端点,然后计算曲线内其余各点到连接两端点的直线的距离。如果这些点到直线的垂直距离中最大值小于某一给定的阈值,则所有的这些点都被舍去;如果最大距离大于阈值,则此点保留,并以此将曲线分为两段,重复以上过程直到没有多余的点被舍去为止[2]。

2 基于总体最小二乘的Douglas-Peucker算法

由于Douglas-Peucker算法将保留点直接相连来表示原始曲线,这就导致了抽稀后的数据在保留点处没有误差,而在删除点处存在明显的误差,数据的精度非常不一致。如图1,当采用Douglas-Peucker算法对实线所示的原始数据进行压缩时,会得到虚线ABC。在保留点AB和BC之间,被删除的点全部位于保留线的同一侧。很显然,用ABC代替原始数据会产生较大的误差。如果略微放宽对A、B、C三点的精度要求,通过总体最小二乘算法采用虚线来代替会使逼近效果更好[3]。

图1 总体最小二乘的Douglas-Peucker示意图

设曲线由点序列A1、A2…An构成,取曲线端点A1、A2,计算曲线上各点到直线A1A2的距离di(i=1,2,…n-2),选取其中的最大值dmax,将dmax与给定阈值ε比较。如果dmax＜ε,则对所有点用总体最小二乘进行拟合;如果dmax≥ε,则将所对应的点Ak保留,并将曲线分为两段,重复以上操作直到没有剩余的点为止。

于是,直线方程可写为:Y=XK。令=[X,Y],=[K-1]T,P=T,由总体最小二乘原理知,当=η v时,目标函数 ξTLS=(TP)/(T)可以取得最小值,即各序列点到拟合直线的距离之和最小,其中v为二阶矩阵P的最小特征值相应的特征向量,常数η的选取应使得的最后一个值为-1,其精度评定类似于最小二乘,为了方便计算,本文另定义函数进行计算[4-5]。

3 仿真实现与分析

采用平移、转换MATLAB中PEAK函数的方法,构建仿真海底(图2),其仿真函数为:H=peaks〔(x-50),(y-50)〕-20。使用SeatBat 8101多波束测深系统沿x方向布设测线,即船的行驶方向,对仿真海底进行全覆盖扫描,忽略各种测量效应带来的误差,共获得100个ping的扫描数据,每个ping含有101个测深点。

图2 海底地形模拟图

为了比较两种算法,选取了近似平坦海底(5号ping)(见图3)、凹形海底(25号ping)(见图4)、凸形海底(75号ping)(见图5)的测深剖面来进行比较分析,其中,阈值设为0.28 m,TLS-DP为基于总体最小二乘的Douglas-Peucker算法,DP为Douglas-Peucker算法。

图3 5号ping的抽稀比较

图4 25号ping的抽稀比较

图5 75号ping的抽稀比较

表1 DP与TLS-DP算法精度比较

由表 1可知,基于总体最小二乘的Douglas-Peucker算法具有更高的精度,可以获得更加真实的海底状况。

4 结 语

在分析Douglas-Peucker算法的基础上提出了基于总体最小二乘的Douglas-Peucker算法,经试验证明,基于总体最小二乘的Douglas-Peucker算法可以获得更好的精度,从而整体上可以更加真实的反映海底的地形情况,更加符合多波束系统测深数据抽稀的地形完善性准则。

[1]曹鸿博,张立华,朱穆华,等.海量多波束数据抽稀方法的比对分析[J].海洋测绘,2010,30(5):81-82.

[2]夏 伟,黄谟涛,刘雁春,等.Douglas-Peucker算法在多波束测深数据抽稀中的应用[J].测绘科学,2009,34(3):159-160.

[3]杨 云,孙 群,朱长青.曲线数据压缩的总体最小二乘算法[J].西安电子科技大学学报(自然科学版),2008,35(5):946-949.

[4]Shen Yunzhong,Li Bofeng,Chen Yi.An iterative solutionof weighted total least-squaresadjustment[J].Journal of Geodesy,2010,85(4):229-238.

[5]丁克良,沈云中,欧吉坤.整体最小二乘法拟合[J].辽宁工程科技大学学报(自然科学版),2010,29(1):44-47.

Application of Douglas-Peucker Algorithm Based on Total Least Square in Data Thinning of Multibeam Sounding

LU Yin-hong,YUE Dong-jie,SONG Fei-feng
(College of Earth Science and Engineering,Hohai University,Nanjing,Jiangsu210098,China)

Douglas-Peucker algorithm is one of the main algorithms about the data thinning of multibeam sounding,through keeping important points and deleting other points,the data thinning ismade,which would lead the precision of the thinning data to be extremely inconsistent with that of the original data,and could not reflect the real situation of the seabed very well.Through using the Douglas-Peucker algorithm based on the total least square,the original data of multibeam sounding could be fully used for fitting,so as to reflect the real situation of the seabed more truly.The simulation experimentation shows that comparedwith the Douglas-Peucker algorithm,the Douglas-Peucker algorithm based on the total least square could be closer to the original data and improve the precision of thinning.

Douglas-Peucker algorithm;multibeam sounding;total least square;thinning

P2

A

1672—1144(2012)02—0004—02

2011-12-06

2012-01-09

国家自然科学基金资助项目“数码影像高精度工程监测关键技术及质量控制方法”(51079053)

卢银宏(1989—),男(汉族),江苏靖江人,硕士研究生,研究方向为测量误差理论与数据处理。