面向地形匹配的多波束測深數(shù)據(jù)抽稀方法研究

訾桂峰，程秀麗，劉 毅，徐遵義

(1.濰坊市科學(xué)技術(shù)情報研究所，山東濰坊 261061;2.山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東濟(jì)南250101)

水下地形定位技術(shù)有可能解決水下潛航器長時間高精度導(dǎo)航定位問題，已成為新型導(dǎo)航系統(tǒng)發(fā)展的重要方向，其中基于多波束系統(tǒng)的地形輔助導(dǎo)航更成為研究和發(fā)展的重點(diǎn)［1-2］。由于多波束測深的高精度和高密度導(dǎo)致實(shí)時獲得的數(shù)據(jù)量巨大，必須對其進(jìn)行重采樣才能用于海底地形輔助導(dǎo)航，其中數(shù)據(jù)抽稀是實(shí)現(xiàn)重采樣算法的主要步驟之一［3-4］。

目前多波束測深數(shù)據(jù)抽稀算法主要有兩類:基于非散亂數(shù)據(jù)的數(shù)據(jù)抽稀算法和基于二維散亂數(shù)據(jù)的數(shù)據(jù)插值方法。前者代表性的算法主要有基于格網(wǎng)的數(shù)據(jù)抽稀和基于系統(tǒng)的抽?。?-6］，該類算法的主要特點(diǎn)是運(yùn)算速度快，主要用于多波束數(shù)據(jù)的快速顯示，多波束測深系統(tǒng)自帶軟件多采用此類算法，但因?qū)Χ嗖ㄊ鴾y深數(shù)據(jù)模型過分簡化而導(dǎo)致精度低，很多地形特征點(diǎn)無法保留;后者代表性的算法主要有基于鄰近距離及高差的抽稀算法和基于不規(guī)則三角網(wǎng)的抽稀算法［7-9］，該類算法能有效保留地形特征點(diǎn)，抽稀精度高，但運(yùn)算量巨大，無法實(shí)時執(zhí)行，多用于多波束測深數(shù)據(jù)的后期離線處理和地形可視化。面向地形匹配的多波束測深數(shù)據(jù)抽稀算法需要在運(yùn)算速度、采樣密度和精度之間達(dá)到一種最優(yōu)平衡，因此結(jié)合已有兩類抽稀算法的優(yōu)點(diǎn)，對多波束測深每ping數(shù)據(jù)采用角度-弦高聯(lián)合準(zhǔn)則法進(jìn)行抽稀處理，對多ping抽稀后的數(shù)據(jù)基于點(diǎn)云離散度再進(jìn)行簡化，從而實(shí)現(xiàn)用于地形匹配的多波束測深數(shù)據(jù)抽稀。

1 抽稀算法及實(shí)現(xiàn)

面向海底地形導(dǎo)航定位的多波束測深數(shù)據(jù)抽稀方法包括基于角度-弦高的每ping數(shù)據(jù)抽稀和基于點(diǎn)云離散度對多ping實(shí)測數(shù)據(jù)的抽稀處理。

1.1 角度-弦高聯(lián)合準(zhǔn)則抽稀法

在相鄰點(diǎn)水深差距較大時，即使夾角很小，弦高也可能很大;當(dāng)在相鄰點(diǎn)水深差距較小時，即弦高很小，角度也可能很大，如圖1所示。因此同時使用角度和弦高2種誤差限對水深數(shù)據(jù)進(jìn)行判別，凡是水深點(diǎn)同時小于2種誤差限的點(diǎn)舍去?；诮嵌?弦高聯(lián)合準(zhǔn)則的數(shù)據(jù)抽稀算法首先給定角度誤差限Δα和弦高誤差限Δd，然后對數(shù)據(jù)逐點(diǎn)進(jìn)行判斷，算法步驟［10］:

1)給定閾值Δα和Δd;

2)從起始點(diǎn)開始取相鄰的測深點(diǎn)P0，P1，P2;

3)對于 P0，P1，P2，計(jì)算P0P1到P0P2的夾角 α 和d=|P0P1|sinα;

圖1 角度和弦高示意Fig.1 Angle＆chord height of polygonal line

4)若α＜Δα并且d＜Δd成立，則舍去測深點(diǎn)P1，取P2后的一點(diǎn)P3;若P3不存在，則表明該ping測深數(shù)據(jù)已處理完畢，轉(zhuǎn)第6)步;若P3存在，則置P1=P2，P2=P3，轉(zhuǎn)第3)步;

5)若α＜Δα并且d＜Δd不成立，則置P0=P1，P1=P2，取P2后的一點(diǎn)P3;若P3不存在，則表明該ping測深數(shù)據(jù)已處理完畢，轉(zhuǎn)第6)步;若P3存在，則置P2=P3，轉(zhuǎn)第3)步;

6)判斷是否所有ping均已取完，如果沒有則取下一ping數(shù)據(jù)，轉(zhuǎn)第2)步，否則算法結(jié)束。

多波束測深獲得的數(shù)據(jù)是按ping存儲的，每ping可接收數(shù)百個水深數(shù)據(jù)(如Simrad EM3002最多可接收508個水深數(shù)據(jù))，這些水深數(shù)據(jù)基本上位于同一條曲線上，對于每ping數(shù)據(jù)采用角度-弦高聯(lián)合準(zhǔn)則，利用給定的角度和弦高誤差來對每ping測深數(shù)據(jù)進(jìn)行抽稀處理。

1.2 基于點(diǎn)云離散度的抽稀方法

對于海底某一地形區(qū)域，水深高程差異的大小表現(xiàn)為地形起伏程度的高低。為了有效地描述水深差異與地形起伏的關(guān)系，采用離散度的概念進(jìn)行闡述。

離散度定義:對于大小為MXN的某塊地形區(qū)域，設(shè)Z［i，j］是水下地形某點(diǎn)的測深值，ˉZ為該區(qū)域所有點(diǎn)的水深平均值，則局部區(qū)域中該點(diǎn)的離散度可定義為［11］

式中:Di，j為點(diǎn)云的離散度，ε為一很小的正數(shù)，用于防止平坦區(qū)域水深值完全相同時公式分母為零的情形。

點(diǎn)的離散度反映了該點(diǎn)對區(qū)域地形起伏貢獻(xiàn)的程度。利用點(diǎn)云的離散度可探測點(diǎn)云對地形起伏的影響程度，在簡化過程中可提取那些對地形起伏貢獻(xiàn)較大的點(diǎn)予以保留，從而保持測區(qū)的地形起伏特征。基于點(diǎn)云離散度的抽稀算法步驟:

1)根據(jù)多波束回波數(shù)、海底地形圖水深和慣導(dǎo)指示位置確定條帶寬度，根據(jù)載體運(yùn)行速度和采樣間隔確定條帶長度，根據(jù)導(dǎo)航地形圖格網(wǎng)大小對實(shí)測數(shù)據(jù)進(jìn)行格網(wǎng)劃分;

2)根據(jù)海底地形圖水深精度和位置精度生成水深差閾值和地形點(diǎn)最小距離閾值;

3)對給定格網(wǎng)中的所有點(diǎn)按水深值進(jìn)行排序，若格網(wǎng)中點(diǎn)的水深最大值與最小值之差大于水深差閾值，則視最大、最小值點(diǎn)為地形特征候選點(diǎn)作保留標(biāo)志;

4)計(jì)算格網(wǎng)中其它點(diǎn)的離散度，離散度大于閾值的則作保留標(biāo)志;

5)確定當(dāng)前格網(wǎng)的索引號，搜索近鄰區(qū)域，對于鄰域中距離當(dāng)前格網(wǎng)候選特征點(diǎn)較近而且水深差小于閾值的作刪除標(biāo)志;

2 抽稀算法精度評估方法

參考空間曲面形態(tài)參數(shù)和空間關(guān)系，采用抽稀前后空間曲面表面積的改變和抽稀前后DEM的誤差來定量表示以及等值線圖定性表示。

空間曲面表面積的計(jì)算采用構(gòu)成曲面的三角形格網(wǎng)表面積的和來計(jì)算，如圖2所示。空間三點(diǎn)P1，P2，P3構(gòu)成的三角形上的曲面面積［12］:

式中:h1，h2，h3為數(shù)據(jù)點(diǎn) P1，P2，P3上的數(shù)據(jù)值;a'，b'，c'為 ΔP1P2P3的邊長。

由于抽稀前后測深數(shù)據(jù)只是在數(shù)量上有所減少，數(shù)值本身并未改變，因此采用內(nèi)插點(diǎn)云的方式計(jì)算抽稀前后構(gòu)成的DEM誤差，對于內(nèi)插方法采用改進(jìn)的Shepard方法。首先均勻地從原始采樣數(shù)據(jù)中抽取N個點(diǎn)將其水深值作為真值，然后用抽稀后的結(jié)果點(diǎn)云內(nèi)插出這N個點(diǎn)的水深值并比對真值，最后統(tǒng)計(jì)抽稀前后的誤差指標(biāo)。誤差指標(biāo)采用最大絕對誤差MAE、中誤差RMSE和平均差ME來度量。

圖2 三角形格網(wǎng)曲面面積Fig.2 Surface area of triangulated network

3 數(shù)據(jù)抽稀實(shí)驗(yàn)與結(jié)果分析

為了評估提出的多波束測深數(shù)據(jù)抽稀算法的精度及其對實(shí)際地形的適用性，選用數(shù)學(xué)曲面和實(shí)際地形進(jìn)行了試驗(yàn)。

3.1 基于數(shù)學(xué)仿真曲面數(shù)據(jù)的實(shí)驗(yàn)分析

為了檢驗(yàn)數(shù)據(jù)抽稀算法對各種地形的適用性，選用橢圓拋物面(模擬谷底)、馬鞍面(模擬山脊及鞍部)、高斯曲面(模擬山峰的起伏)等能模擬代表性特征地形的可調(diào)節(jié)參數(shù)曲面來對抽稀算法進(jìn)行評估。

實(shí)驗(yàn)曲面的參數(shù)取值:a=3，b=10，c=1/3，m=n=1。

為了使數(shù)學(xué)仿真生成的曲面數(shù)據(jù)更加符合多波束實(shí)際，分別對位置數(shù)據(jù)增加格網(wǎng)間距1% 、水深數(shù)據(jù)增加水深值1% 的高斯誤差，曲面采用Delaunary三角形構(gòu)造，原始曲面加誤差后形成的條帶數(shù)據(jù)(以下簡稱仿真條帶數(shù)據(jù))及其經(jīng)抽稀后形成的曲面分別如圖3和圖4所示。仿真條帶數(shù)據(jù)抽稀前后數(shù)據(jù)點(diǎn)數(shù)、Delaunary三角形數(shù)量以及離散點(diǎn)抽稀率、抽稀前后Delaunary三角形面積變化率如表1所示(角度10°，弦高:每ping水深均值10%，離散度閾值:格網(wǎng)內(nèi)水深均值150%);三種仿真曲面DEM誤差如表2所示。

圖3 仿真條帶數(shù)據(jù)曲面Fig.3 3-D image of simulated swath data

表1 三種仿真曲面抽稀效果Tab.1 Thinned results of simulated surfaces data

圖4 仿真條帶數(shù)據(jù)抽稀后數(shù)據(jù)曲面Fig.4 3-D image of simulated swath thinned data

表2 三種仿真曲面DEM誤差Tab.2 DEM errors of simulated surfaces thinned data

由圖3和圖4以及表1和表2可知，提出的數(shù)據(jù)抽稀算法對三種典型地形均具有很好的抽稀效果，數(shù)據(jù)抽稀率均在85%以上，抽稀前后曲面表面積變化率均小于3%，其中橢圓拋物面點(diǎn)云數(shù)據(jù)抽稀率最低，高斯拋物面抽稀率最高。原因在于橢圓拋物面均勻變化，需要保留較多的點(diǎn)反應(yīng)原曲面，高斯曲面平面部分較多，而平面可以用較少的點(diǎn)來表示，但高斯曲面變化部分變化劇烈，導(dǎo)致抽稀前后曲面誤差較大，與表2高斯曲面DEM誤差最大相符合。馬鞍型曲面介于橢圓拋物面和高斯曲面之間，其數(shù)據(jù)抽稀率和DEM誤差也介于二者之間，但其抽稀后重構(gòu)曲面與原仿真曲面變化最大，原因在于馬鞍型曲面變化的不規(guī)則性。

3.2 基于實(shí)測數(shù)據(jù)的實(shí)驗(yàn)分析

為了驗(yàn)證文中提出的抽稀算法對實(shí)際地形的適用性，在此隨機(jī)選用2條多波束實(shí)測條帶數(shù)據(jù)的一部分進(jìn)行抽稀實(shí)驗(yàn)，抽稀結(jié)果如表3所示 (角度10°;弦高:每ping水深均值10%;離散度閾值:格網(wǎng)內(nèi)水深均值150%)，其中第2塊條帶數(shù)據(jù)抽稀前后三維效果如圖5所示。

表3 實(shí)測多波束地形數(shù)據(jù)抽稀結(jié)果Tab.3 Thinned results of surveyed terrain data

圖5 實(shí)測多波束數(shù)據(jù)抽稀效果Fig.5 Comparison between surveyed terrain data and thinned terrain data

由表3和圖5可知，提出的數(shù)據(jù)抽稀方法對多波束實(shí)測地形數(shù)據(jù)比仿真曲面數(shù)據(jù)有更好的抽稀效果，原因在于水下實(shí)際地形變化平穩(wěn)，劇烈變化的地形較少，可以用更少的點(diǎn)來表示原先的點(diǎn)云數(shù)據(jù)，減少數(shù)據(jù)存儲以及為后期測深數(shù)據(jù)的處理提高效率。

為了考察提出的多波束數(shù)據(jù)抽稀算法與已有多波束數(shù)據(jù)抽稀算法的在運(yùn)算速度、抽稀精度等方面的差異，對實(shí)測條帶數(shù)據(jù)1進(jìn)行了對比試驗(yàn)。試驗(yàn)環(huán)境:筆記本電腦 Dell Inspiron 1440(CPU T6600 2.2 GHz，RAM 4GB)，MS Windows Server 2003企業(yè)版，Matlab 2010a，傳統(tǒng)抽稀算法采用基于格網(wǎng)的數(shù)據(jù)抽稀算法(用格網(wǎng)均值代表格網(wǎng)值)和鄰近距離及高差［7］(鄰近距離采用格網(wǎng)外接圓，高差采用鄰近區(qū)域水深均值10%)，精度評價在前述評價方法的基礎(chǔ)上增加算法運(yùn)行時間，實(shí)驗(yàn)結(jié)果如表4所示。

表4 實(shí)測多波束地形數(shù)據(jù)1不同抽稀算法運(yùn)行結(jié)果Tab.4 Experiment results of different thinning algorithms of first surveyed terrain data

由表4可知，這里提出的多波束數(shù)據(jù)抽稀算法數(shù)據(jù)抽稀率和精度與基于鄰近距離及高差的數(shù)據(jù)抽稀算法接近，算法運(yùn)行時間與基于格網(wǎng)的數(shù)據(jù)抽稀算法接近，因此這里提出的該算法具有較高的精度以及實(shí)時性較好，能比較好地適用于面向地形匹配的數(shù)據(jù)重采樣應(yīng)用。

4 結(jié)語

當(dāng)多波束測深數(shù)據(jù)用于水下地形輔助導(dǎo)航定位時，數(shù)據(jù)實(shí)時抽稀處理需考慮以下問題:1)多波束測深系統(tǒng)的波束數(shù)、水深和載體運(yùn)行速度，它們決定了多波束測深條帶的面積;2)算法對于任意地形區(qū)域都能得到較好的結(jié)果，并不具有特殊性;3)算法應(yīng)簡潔，執(zhí)行效率高，為此算法要特別關(guān)注海底地形特征點(diǎn)特征。

這里將角度-弦高準(zhǔn)則與點(diǎn)云離散度抽稀方法相結(jié)合用于多波束地形數(shù)據(jù)抽稀處理，通過仿真曲面和多波束實(shí)測地形數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證，獲得以下結(jié)論:

1)角度-弦高準(zhǔn)則與點(diǎn)云離散度抽稀方法相結(jié)合可以實(shí)現(xiàn)對多波束測深數(shù)據(jù)的實(shí)時抽稀，點(diǎn)云離散點(diǎn)抽稀率仿真曲面在85%以上，實(shí)測數(shù)據(jù)在90%以上;

2)角度-弦高準(zhǔn)則用于多波束每ping數(shù)據(jù)的抽稀，點(diǎn)云離散度用于多 ping組成的曲面數(shù)據(jù)的抽稀，算法充分利用了多波束水深測量的特點(diǎn)，算法實(shí)時性較好;

3)通過對每ping數(shù)據(jù)的抽稀和對多ping數(shù)據(jù)的聯(lián)合抽稀，這種抽稀方法能很好地保留測深數(shù)據(jù)的幾何特征，同時又可以獲得較高的抽稀率。

在數(shù)據(jù)抽稀過程中，角度、弦高以及點(diǎn)云離散度閾值均為經(jīng)驗(yàn)值，算法在普適性上還存在一定的問題，同時針對不同地形應(yīng)該采用不同的格網(wǎng)劃分和不同的閾值，這是今后進(jìn)一步要研究的主要內(nèi)容。

［1］ 王杰華.國外各種導(dǎo)航定位技術(shù)最新進(jìn)展［J］.中國航天，2010，8:30-34.

［2］ 李 臨.海底地形匹配輔助導(dǎo)航技術(shù)現(xiàn)狀及發(fā)展［J］.艦船電子工程，2008，28(2):17-19.

［3］ 于家城，陳家斌，賀 鵬，等.基于FFT的海底地形二維匹配技術(shù)［J］.系統(tǒng)仿真學(xué)報，2008，20(21):5795-5797.

［4］ 馬 妍.基于多波束測量數(shù)據(jù)的海底地形可導(dǎo)航性分析［D］.哈爾濱:哈爾濱工程大學(xué)，2010.

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

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

［7］ Pamela S.A data density reduction algorithm for Post-processed airborne lidar bathymetric survey data［D］.Florida:University of Florida，2000.

［8］ 馬建林，金 菁，來向華.多波束測深海底數(shù)字地形模型的建立［J］.海洋測繪，2005，25(5):15-17.

［9］ 賈俊濤，翟京生，孟嬋媛，等.基于海量多波束數(shù)據(jù)的海底地形模型的構(gòu)建與可視化［J］.測繪科學(xué)技術(shù)學(xué)報，2008，25(4):255-259.

［10］洪 軍，丁玉成，曹 亮，等.逆向工程中的測量數(shù)據(jù)精簡技術(shù)研究［J］.西安交通大學(xué)學(xué)報，2004，38(7):661-664.

［11］徐景中，萬幼川，張圣望.LIDAR地面點(diǎn)云的簡化方法研究［J］.測繪信息工程，2008，33(1):33-34.

［12］郭仁忠.空間分析［M］.第2版，北京:高等教育出版社，2004.