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

熊 欣， 張新宇， 王金濤

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

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

熊 欣， 張新宇， 王金濤

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

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

船舶工程；雷達(dá)數(shù)據(jù)簡化；道格拉斯改進(jìn)算法；自適應(yīng)閾值；特征點提??；分段簡化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3岸線分段

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

(a) 自然岸線特征

(b) 人工岸線特征

圖2 刪除冗余點

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

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

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

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

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

(a)

(b)

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

(1)

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

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

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

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

(a)

(b)

(c)

2 算法設(shè)計及實例分析

2.1D-P改進(jìn)算法

D-P改進(jìn)算法的流程見圖5。

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

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

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

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

2.2案例分析

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

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

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

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

圖5 算法流程

表1 簡化點及對應(yīng)的閾值

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

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

(a)

(b)

(c)

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

3 結(jié) 語

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

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

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

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

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

[5] 曲均浩，程久龍，崔先國.垂直剖面法自動提取山脊線和山谷線[J].測繪科學(xué),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].測繪科學(xué)技術(shù)學(xué)報，2010,27(3):225-228.

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

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

[11] 毋河海.基于多叉樹結(jié)構(gòu)的曲線綜合算法[J].武漢大學(xué)學(xué)報:信息科學(xué)版,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]. 武漢大學(xué)學(xué)報:信息科學(xué)版,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

國家自然科學(xué)基金(51309043);交通運輸部基礎(chǔ)應(yīng)用研究項目(2014329225020);中國博士后科學(xué)基金(2014M551095);遼寧自然科學(xué)基金(2014025005);中央高?；A(chǔ)研究基金(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