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

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

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

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

1 抽稀算法及實現

面向海底地形導航定位的多波束測深數據抽稀方法包括基于角度-弦高的每ping數據抽稀和基于點云離散度對多ping實測數據的抽稀處理。

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

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

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

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

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

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

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

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

6)判斷是否所有ping均已取完，如果沒有則取下一ping數據，轉第2)步，否則算法結束。

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

1.2 基于點云離散度的抽稀方法

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

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

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

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

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

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

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

4)計算格網中其它點的離散度，離散度大于閾值的則作保留標志;

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

2 抽稀算法精度評估方法

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

空間曲面表面積的計算采用構成曲面的三角形格網表面積的和來計算，如圖2所示?？臻g三點P1，P2，P3構成的三角形上的曲面面積［12］:

式中:h1，h2，h3為數據點 P1，P2，P3上的數據值;a'，b'，c'為 ΔP1P2P3的邊長。

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

圖2 三角形格網曲面面積Fig.2 Surface area of triangulated network

3 數據抽稀實驗與結果分析

為了評估提出的多波束測深數據抽稀算法的精度及其對實際地形的適用性，選用數學曲面和實際地形進行了試驗。

3.1 基于數學仿真曲面數據的實驗分析

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

實驗曲面的參數取值:a=3，b=10，c=1/3，m=n=1。

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

圖3 仿真條帶數據曲面Fig.3 3-D image of simulated swath data

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

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

3.2 基于實測數據的實驗分析

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

表3 實測多波束地形數據抽稀結果Tab.3 Thinned results of surveyed terrain data

圖5 實測多波束數據抽稀效果Fig.5 Comparison between surveyed terrain data and thinned terrain data

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

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

表4 實測多波束地形數據1不同抽稀算法運行結果Tab.4 Experiment results of different thinning algorithms of first surveyed terrain data

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

4 結語

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

這里將角度-弦高準則與點云離散度抽稀方法相結合用于多波束地形數據抽稀處理，通過仿真曲面和多波束實測地形數據實驗驗證，獲得以下結論:

1)角度-弦高準則與點云離散度抽稀方法相結合可以實現對多波束測深數據的實時抽稀，點云離散點抽稀率仿真曲面在85%以上，實測數據在90%以上;

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

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

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

［1］ 王杰華.國外各種導航定位技術最新進展［J］.中國航天，2010，8:30-34.

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

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

［4］ 馬 妍.基于多波束測量數據的海底地形可導航性分析［D］.哈爾濱:哈爾濱工程大學，2010.

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

［6］ 曹鴻博，張立華，朱穆華，等.海量多波束數據抽稀方法的比對分析［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］ 馬建林，金 菁，來向華.多波束測深海底數字地形模型的建立［J］.海洋測繪，2005，25(5):15-17.

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

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

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

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