基于總體最小二乘的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—),男(漢族),江蘇靖江人,碩士研究生,研究方向為測量誤差理論與數據處理。