基于總體最小二乘的Douglas-Peucker算法在多波束測深數(shù)據(jù)抽稀中的應(yīng)用

盧銀宏,岳東杰,宋飛鳳

(河海大學(xué) 地球科學(xué)與工程學(xué)院,江蘇南京 210098)

基于總體最小二乘的Douglas-Peucker算法在多波束測深數(shù)據(jù)抽稀中的應(yīng)用

盧銀宏,岳東杰,宋飛鳳

(河海大學(xué) 地球科學(xué)與工程學(xué)院,江蘇南京 210098)

Douglas-Peucker算法是多波束數(shù)據(jù)抽稀的主要算法之一,通過保留特征點來達到抽稀的目的,這導(dǎo)致了抽稀后的數(shù)據(jù)與原始數(shù)據(jù)精度的極度不一致,無法很好地反映水下地形的真實情況。基于總體最小二乘的Douglas-Peucker算法,在采用Douglas-Peucker算法確定特征點的基礎(chǔ)上,充分利用多波束測深原始數(shù)據(jù)的信息進行分段總體最小二乘擬合,從而達到更真實地反應(yīng)海底狀況的目的。通過對仿真海底地形模擬計算,結(jié)果表明:與Douglas-peucker算法相比,該算法能夠更加逼近原始數(shù)據(jù),提高抽稀精度。

Douglas-Peucker算法;多波束探測;總體最小二乘;抽稀

海洋測繪是一切海洋開發(fā)活動的基礎(chǔ),海底地形測量是海洋測繪基礎(chǔ)性任務(wù)之一。隨著科學(xué)技術(shù)的發(fā)展,多波束測深系統(tǒng)已經(jīng)成為了當(dāng)今世界進行海底測量先進技術(shù)手段的杰出代表。采用多波束測深系統(tǒng)具有全覆蓋、高精度,能夠準(zhǔn)確全面的反映水下地形起伏變化的情況的特點,但是產(chǎn)生的數(shù)據(jù)量極大,通常會產(chǎn)生TB級的數(shù)據(jù)量[1]。面對如此海量的數(shù)據(jù),快速有效的數(shù)據(jù)抽稀算法已成為了多波束測深數(shù)據(jù)處理中一項不可缺少的技術(shù)。對于多波束測深抽稀方法,一般采用Douglas-Peucker算法,但由于Douglas-Peucker算法僅利用垂向距離作為約束條件來決定曲線上點的取舍,并沒有采用任何優(yōu)化方法,抽稀得到的數(shù)據(jù)也無法最優(yōu)逼近原始數(shù)據(jù)。基于此,本文采用基于總體最小二乘的Douglas-Peucker算法充分利用原始數(shù)據(jù),從整體上逼近原始數(shù)據(jù),以便獲得更加逼真的海底地形圖。

1 Douglas-Peucker算法

Douglas-Peucker算法是通過保留關(guān)鍵點刪除次要點來達到抽稀的目的,其算法的基本思想是:首先選取曲線的兩個端點,然后計算曲線內(nèi)其余各點到連接兩端點的直線的距離。如果這些點到直線的垂直距離中最大值小于某一給定的閾值,則所有的這些點都被舍去;如果最大距離大于閾值,則此點保留,并以此將曲線分為兩段,重復(fù)以上過程直到?jīng)]有多余的點被舍去為止[2]。

2 基于總體最小二乘的Douglas-Peucker算法

由于Douglas-Peucker算法將保留點直接相連來表示原始曲線,這就導(dǎo)致了抽稀后的數(shù)據(jù)在保留點處沒有誤差,而在刪除點處存在明顯的誤差,數(shù)據(jù)的精度非常不一致。如圖1,當(dāng)采用Douglas-Peucker算法對實線所示的原始數(shù)據(jù)進行壓縮時,會得到虛線ABC。在保留點AB和BC之間,被刪除的點全部位于保留線的同一側(cè)。很顯然,用ABC代替原始數(shù)據(jù)會產(chǎn)生較大的誤差。如果略微放寬對A、B、C三點的精度要求,通過總體最小二乘算法采用虛線來代替會使逼近效果更好[3]。

圖1 總體最小二乘的Douglas-Peucker示意圖

設(shè)曲線由點序列A1、A2…An構(gòu)成,取曲線端點A1、A2,計算曲線上各點到直線A1A2的距離di(i=1,2,…n-2),選取其中的最大值dmax,將dmax與給定閾值ε比較。如果dmax＜ε,則對所有點用總體最小二乘進行擬合;如果dmax≥ε,則將所對應(yīng)的點Ak保留,并將曲線分為兩段,重復(fù)以上操作直到?jīng)]有剩余的點為止。

于是,直線方程可寫為:Y=XK。令=[X,Y],=[K-1]T,P=T,由總體最小二乘原理知,當(dāng)=η v時,目標(biāo)函數(shù) ξTLS=(TP)/(T)可以取得最小值,即各序列點到擬合直線的距離之和最小,其中v為二階矩陣P的最小特征值相應(yīng)的特征向量,常數(shù)η的選取應(yīng)使得的最后一個值為-1,其精度評定類似于最小二乘,為了方便計算,本文另定義函數(shù)進行計算[4-5]。

3 仿真實現(xiàn)與分析

采用平移、轉(zhuǎn)換MATLAB中PEAK函數(shù)的方法,構(gòu)建仿真海底(圖2),其仿真函數(shù)為:H=peaks〔(x-50),(y-50)〕-20。使用SeatBat 8101多波束測深系統(tǒng)沿x方向布設(shè)測線,即船的行駛方向,對仿真海底進行全覆蓋掃描,忽略各種測量效應(yīng)帶來的誤差,共獲得100個ping的掃描數(shù)據(jù),每個ping含有101個測深點。

圖2 海底地形模擬圖

為了比較兩種算法,選取了近似平坦海底(5號ping)(見圖3)、凹形海底(25號ping)(見圖4)、凸形海底(75號ping)(見圖5)的測深剖面來進行比較分析,其中,閾值設(shè)為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 結(jié) 語

在分析Douglas-Peucker算法的基礎(chǔ)上提出了基于總體最小二乘的Douglas-Peucker算法,經(jīng)試驗證明,基于總體最小二乘的Douglas-Peucker算法可以獲得更好的精度,從而整體上可以更加真實的反映海底的地形情況,更加符合多波束系統(tǒng)測深數(shù)據(jù)抽稀的地形完善性準(zhǔn)則。

[1]曹鴻博,張立華,朱穆華,等.海量多波束數(shù)據(jù)抽稀方法的比對分析[J].海洋測繪,2010,30(5):81-82.

[2]夏 偉,黃謨濤,劉雁春,等.Douglas-Peucker算法在多波束測深數(shù)據(jù)抽稀中的應(yīng)用[J].測繪科學(xué),2009,34(3):159-160.

[3]楊 云,孫 群,朱長青.曲線數(shù)據(jù)壓縮的總體最小二乘算法[J].西安電子科技大學(xué)學(xué)報(自然科學(xué)版),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].遼寧工程科技大學(xué)學(xué)報(自然科學(xué)版),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

國家自然科學(xué)基金資助項目“數(shù)碼影像高精度工程監(jiān)測關(guān)鍵技術(shù)及質(zhì)量控制方法”(51079053)

盧銀宏(1989—),男(漢族),江蘇靖江人,碩士研究生,研究方向為測量誤差理論與數(shù)據(jù)處理。