熊 欣， 張新宇， 王金濤

(大連海事大學 航海動態(tài)仿真和控制交通行業(yè)重點實驗室, 遼寧 大連 116026)

基于道格拉斯改進的雷達回波數(shù)據(jù)簡化算法

熊 欣， 張新宇， 王金濤

(大連海事大學 航海動態(tài)仿真和控制交通行業(yè)重點實驗室, 遼寧 大連 116026)

為提高雷達模擬器生成物標回波的效率，提出一種基于道格拉斯改進的雷達回波數(shù)據(jù)簡化算法。首先，提取電子海圖岸線數(shù)據(jù)，分析人工岸線和自然岸線的特征；其次，對數(shù)據(jù)進行預處理，去除冗余點；隨后，通過提取岸線數(shù)據(jù)特征點，將岸線按特征點分段；最后，基于改進的道格拉斯算法，設置壓縮比自適應控制各分段的簡化閾值，實現(xiàn)各分段數(shù)據(jù)的簡化。經(jīng)實驗驗證，該方法能夠有效保持岸線地貌特征，并可達到簡化的效果。

船舶工程；雷達數(shù)據(jù)簡化；道格拉斯改進算法；自適應閾值；特征點提取；分段簡化

目前，雷達模擬器使用的模擬雷達數(shù)據(jù)一般由電子海圖數(shù)據(jù)直接生成，其回波仿真效率較低。若雷達模擬器直接根據(jù)該數(shù)據(jù)生成回波，當仿真大范圍回波時，需要多組雷達模擬數(shù)據(jù)，尤其是在雷達數(shù)據(jù)較為復雜時，將耗費計算機大量內(nèi)存，不能滿足實時生成回波的要求。因此，對于模擬器實時生成回波而言，簡化雷達回波數(shù)據(jù)具有重要的現(xiàn)實意義。

關于雷達回波數(shù)據(jù)簡化的研究目前還比較少。在地理綜合制圖方面，有關線要素簡化的研究[1-5]較多，具有一定的參考意義，其中D-P算法(道格拉斯算法)作為一種經(jīng)典的全局化簡方法被廣泛運用。該算法基于ATTNEAVE[6]的理論，曲線圖形的信息主要集中在曲線的特征點(大多集中于彎曲較大的地方[7])上，通過遞歸的方法篩選曲線上的點。D-P算法是最具代表性的空間圖形的綜合方法，不僅可以實現(xiàn)圖形特征的分解與組合，而且能夠保留圖形的方向、尺度、形狀等形態(tài)和拓撲特征?；贒-P算法的特性，劉歡等[8]提出一種基于D-P算法并結合“擴陸縮海”的思想，通過分維估值的方法實現(xiàn)岸線的自動綜合；陳惠榮等[9-10]提出以曲線骨架線作為化簡指標的綜合方法提取岸線的重要骨架，可同時優(yōu)化海岸線的自動綜合；毋河海[11]通過以雙側偏移量和等值偏移值為指標的曲線綜合方法，進一步提升了曲線簡化后的精度；XIE等[12]提出基于D-P算法，通過改進公差和曲率的范圍保持岸型;LI等[13]提出以角點檢測的方法改進D-P算法，實現(xiàn)簡化的快速逼近。

海圖中的人工岸線(碼頭、防波堤等)雖然地貌特征明顯、數(shù)據(jù)量少，但對船舶(尤其是進出港口作業(yè)的船舶)的航行安全意義重大，因此需精確保留原始形態(tài)特征，幾乎不用簡化。自然岸線地貌特征復雜、數(shù)據(jù)量大，由于船舶均遠離該岸線航行，對航行安全無較大影響，因此可大幅度簡化其數(shù)據(jù)。

由上可知，需將人工岸線和自然岸線分開處理。目前，對于雷達回波的簡化仍沒有成熟的算法。本文針對電子海圖岸線數(shù)據(jù)的特性，提出一種基于D-P改進的算法，以簡化雷達回波數(shù)據(jù)，進而提高模擬器生成岸線及物標回波的效率。

1 基于D-P改進的雷達回波數(shù)據(jù)簡化算法

1.1雷達回波數(shù)據(jù)特征分析

雷達回波數(shù)據(jù)具有如下特點：

1) 數(shù)據(jù)量大。海圖包含的目標豐富，如島礁、淺灘、人工建筑等。

2) 數(shù)據(jù)中存在誤差。數(shù)據(jù)采集中存在誤差，如可能出現(xiàn)重合點。

3) 數(shù)據(jù)特征差異大。人工岸線幾何精度低，地貌特征明顯；自然岸線幾何精度高，無明顯地貌特征。

4) 數(shù)據(jù)分布不規(guī)則。人工岸線數(shù)據(jù)較少,分布無規(guī)律;自然岸線數(shù)據(jù)量大,分布較為均勻。

海圖部分岸線特征見圖1。

1.2數(shù)據(jù)預處理

由于雷達回波具有數(shù)據(jù)量大、存在誤差、分布不規(guī)則等特點，需對其進行預處理。步驟為：

1) 統(tǒng)計岸線數(shù)據(jù)各點與之前后兩點構成的角度分布情況。

2) 刪除在設定容差范圍內(nèi)的數(shù)據(jù)，有效去除重合點及高密度的數(shù)據(jù)，進而初步簡化。

刪除點A容差范圍內(nèi)的重合點高密度點A1、A2，刪除B的重合點B1(見圖2)。

1.3岸線分段

基于自然岸線與人工岸線的特性，若按傳統(tǒng)D-P算法對整條岸線統(tǒng)一簡化處理，顯然無法全部適應岸線的特征，難免出現(xiàn)失真、自相交等情況。為保持岸線地貌特征，避免自相交等情況出現(xiàn)，提出基于骨架特征點,分段簡化數(shù)據(jù)。

(a) 自然岸線特征

(b) 人工岸線特征

圖2 刪除冗余點

岸線的地貌特征可由特征點保持，通過分析角度分布規(guī)律，選取合理角度范圍內(nèi)的點作為特征點對其分段。在海圖岸線中，特征點由明顯凹凸點、尖角點、碼頭等局部極值點構成。岸線分段如圖1所示,其中小圓點為原數(shù)據(jù)點，大菱形為特征點。

1.4數(shù)據(jù)簡化

傳統(tǒng)的D-P算法通過設定閾值對數(shù)據(jù)進行統(tǒng)一簡化，若數(shù)據(jù)特征差異較大，則不能合理簡化。分段點A,B將曲線分為Ⅰ,Ⅱ兩部分，且差異較大。若對岸線Ⅰ,Ⅱ設定統(tǒng)一閾值20，保留的點為A,A1,…,A4,B,B1,…,B9，簡化效果見圖3(a)。若對岸線Ⅰ設定閾值10，對岸線Ⅱ設定閾值20，保留的點為A,A1,…,A5,B,B1,…,B9，簡化效果見圖3(b)。簡化結果驗證，對岸線分段設定閾值的簡化效果優(yōu)于統(tǒng)一設定閾值的簡化效果。分段設定閾值簡化后的點生成的曲線與原始岸線具有更高的擬合度。

因此，在各分段岸線中，需分別設定閾值進行數(shù)據(jù)簡化處理。但對于數(shù)據(jù)量大的海圖，分段較多且特征不一，若通過人工設定各分段閾值，計算量大，算法復雜且不科學。

提出基于D-P的算法，通過設定壓縮比自適應尋找合理閾值，進而簡化各分段數(shù)據(jù)。具體步驟為：

(a)

(b)

1) 設定壓縮比，確定各分段岸線簡化后保留的數(shù)據(jù)點的數(shù)量。根據(jù)該算法，壓縮比與簡化點數(shù)存在關系式

(1)

例如,某段岸線中含28個數(shù)據(jù)點(不含兩端點)，設定壓縮比為0.3，則簡化后保留9個點(包括兩端點)。若某段岸線中含4個點，設定壓縮比為0.3，則簡化后保留2個點(包括兩端點)。

2) 計算初始閾值。初始閾值即遍歷曲線間各點到分段點連線的距離中的最大值。圖4(a)中,C到A,B連線的距離d1最大，以此作為初始閾值(d1)。通過D-P算法簡化,保留C點,則C為新的分段點。

3) 適應尋找閾值。初始閾值按既定步長逐步減小，當其小于/等于遍歷曲線間各點到新的分段點連線的最大值時，以此為新的閾值進行D-P簡化。圖4(b)中，閾值d1按步長逐步減小，當其≤d2時，保留新的分段點D，其中d2分別為AC,CB間各點到AC,CB連線的最大距離。此時以d2為新的初始閾值,D為新的分段點。

4) 重復步驟3)，直到滿足步驟1)確定的簡化結果。圖4(c)中，C,D,…,I為依次簡化保留的點。

(a)

(b)

(c)

2 算法設計及實例分析

2.1D-P改進算法

D-P改進算法的流程見圖5。

1) 讀取電子海圖岸線數(shù)據(jù)。

2) 對數(shù)據(jù)進行預處理，去除冗余點。

3) 提取特征點將岸線分段。

4) 基于改進的D-P算法，設置壓縮比自適應控制各分段的簡化閾值，實現(xiàn)各分段的數(shù)據(jù)簡化。

2.2案例分析

以C1511381中大連港電子海圖數(shù)據(jù)為例，利用D-P改進的簡化算法對電子海圖的數(shù)據(jù)進行簡化，通過對比簡化前后的圖形說明該算法的可行性。具體步驟為：

1) 數(shù)據(jù)預處理。原大連港電子海圖數(shù)據(jù)為3 252個點，初步簡化后為3 077個點。

2) 特征點分段。大連港包含人工岸線、自然岸線,其中:人工岸線數(shù)據(jù)點與之前后點構成的角度大多分布在90°～110°;自然岸線數(shù)據(jù)仍占多數(shù)，其數(shù)據(jù)點與之前后構成的角度大多分布在130°～180°。通過統(tǒng)計各數(shù)據(jù)點角度分布情況，選擇合理的角度提取特征點,進而對岸線進行分段。

3) 數(shù)據(jù)簡化。以圖中部分岸線為例。岸線共有25個數(shù)據(jù)點，若設壓縮比為0.3，則應保留8個點。遍歷曲線間各點到分段點連線的距離中的最大值，C到AB的距離最大，保留C點及其閾值794。閾值按步長逐步減小并以C點為新的分段點，D到CB間距離為局部最大，保留D點及其閾值299。依次簡化,得到C,D,…,H點。簡化過程對應閾值及其保留的數(shù)據(jù)點見表1。簡化過程如圖4。

圖5 算法流程

表1 簡化點及對應的閾值

4) 簡化結果對比。大連港局部圖若分別設置壓縮比為0.3，0.4，0.5，相應的簡化效果見圖6(a),圖6(b),圖6(c)。通過簡化,可保留岸線特征，設定的壓縮比越大,越能更精確地保持岸線特征。

通過設置不同壓縮比,可計算出不同的長度誤差(即簡化前后的長度差與簡化前長度的比值)，利用相關文獻[14]方法證明,長度誤差越低則越能替代原岸線。分別設置壓縮比0.3，0.4，0.5,自適應尋找閾值進行D-P簡化，隨著壓縮比增大，簡化前后的岸線相似度也變高。其長度誤差分別為0.004 93，0.002 60，0.001 16。

(a)

(b)

(c)

經(jīng)實際系統(tǒng)運行驗證,利用簡化后的雷達模擬數(shù)據(jù)生成的雷達回波與利用原始數(shù)據(jù)生成的雷達回波擬合度很高,達到了仿真精度的要求。同時,簡化后的雷達模擬數(shù)據(jù)可大幅度提高雷達回波的顯示效率,滿足系統(tǒng)實時性的要求。

3 結 語

通過基于D-P改進的算法簡化電子海圖岸線數(shù)據(jù)，能夠有效保持原有岸線形態(tài)特征。對于碼頭、防波堤等人工岸線，可以保留原始形態(tài)；對于自然岸線，既可以保持岸型又可大量簡化數(shù)據(jù)。簡化后的岸線數(shù)據(jù)可以滿足雷達回波數(shù)據(jù)實時生成，設置不同壓縮比可以滿足對不同精度的需求。若以更加精確的條件進行岸線分段，可以進一步提高其簡化效果。因此,運用基于D-P改進的簡化算法簡化電子海圖數(shù)據(jù),對于提高航海模擬器實時顯示物標回波、保障航行安全而言具有重要意義。

[1] 劉鵬程，羅靜，艾廷華，等.基于線要素綜合的形狀相似性評價模型[J].武漢大學學報:信息科學版，2012,37(1)：114-117.

[2] 朱鯤鵬，武芳.線要素化簡算法的傳遞誤差模型[J].武漢大學學報:信息科學版,2007,32(10):932-935.

[3] 陳波，朱鯤鵬，薛本新.線狀要素化簡算法的分析與評估[J].測繪科學技術學報,2007,24(2):121-124.

[4] 王玉海，朱長青，游雄，等.基于B樣條小波的等高線數(shù)據(jù)簡化[J].測繪科學,2003,28(2):23-25.

[5] 曲均浩，程久龍，崔先國.垂直剖面法自動提取山脊線和山谷線[J].測繪科學,2007,32(5):30-32.

[6] ATTNEAVE F. Some Informational Aspects of Visual Perception[J]. Psychological Review, 1954, 61: 183-193.

[7] KELLEY P S. Information and Generalization in Cartographic Communication[D]. Seattle: University of Washington, 1977.

[8] 劉歡，謝三德，王芳.海岸線自動綜合方法綜述[J].測繪科學技術學報，2010,27(3):225-228.

[9] 陳惠榮，彭認燦，鄭義東,等.以彎曲骨架線為化簡指標的海岸線綜合方法[J].武漢大學學報:信息科學版,2011,36(12):1 418-1 422.

[10] 陳惠榮，鄭義東，關海波,等.基于骨架線的Douglas-Peucker算法改進[J].海洋測繪，2011,31(5):18-20.

[11] 毋河海.基于多叉樹結構的曲線綜合算法[J].武漢大學學報:信息科學版,2004,29(6):479-483.

[12] XIE Zhong,WANG Huimin,WU Liang. The Improved Douglas-Peucker Algorithm Based on the Contour Character[C]. The 19th International Conference on Geoinformatics, 2011.

[13] LI Lelin,JIANG Wanshou. An Improved Douglas-Peucker Algorithm for Fast Curve Approximation[C]. 3rd International Congress on Image and Signal Processing, 2010.

[14] 武芳，朱鯤鵬.線要素化簡幾何精度評估[J]. 武漢大學學報:信息科學版,2008,33(6):599-603.

SimplifyingRadarEchoSimulationwithImprovedDouglas-PeuckerAlgorithm

XIONGXin,ZHANGXinyu，WANGJintao

(Marine Dynamic Simulation and Control Laboratory, Dalian Maritime University, Dalian 116026, China)

An improved Douglas-Peucker algorithm is proposed to reduce the amount of work to paint the radar echo of shorelines on simulator screens. The shoreline data are extracted from electronic charts. The data are preprocessed to distinguish artificial from natural shorelines according to their characteristics and to remove redundant points. The processed shoreline is segmented according to the feature points. The shoreline data are finally processed according to set compression ratio by an Douglas-Peucker algorithm with segment adaptive threshold control to form an compressed shoreline data set. Experimental results show that the proposed method can effectively reduce the volume of data while keeping the shape of shorelines satisfactorily.

ship engineering; radar data compression; improved Douglas-Peucker algorithm; adaptive threshold; feature point extraction; sectional approximation

2014-05-18

國家自然科學基金(51309043);交通運輸部基礎應用研究項目(2014329225020);中國博士后科學基金(2014M551095);遼寧自然科學基金(2014025005);中央高?；A研究基金(3132014202)

熊 欣(1988—)，四川遂寧人，男，碩士生，研究方向為交通信息工程及控制。E-mail:dmu_2012xx@163.com

張新宇(1978—)，吉林長春人，男，博士生，研究方向為交通信息工程、航海動態(tài)仿真、電子海圖系統(tǒng)等。

E-mail:zhang.xinyu@soho.com

1000-4653(2014)03-0001-04

TN957.51

A