魏泓丞，張立華，唐露露，董 箭，李改肖，袁 浩

海軍大連艦艇學(xué)院軍事海洋與測繪系，遼寧 大連 116018

航海圖線要素綜合作為海圖制圖綜合中的重要內(nèi)容，其自動綜合的研究始終受到人們的關(guān)注[1]。針對航海圖上線要素的自動綜合，國內(nèi)外眾多專家學(xué)者提出了不少算法[2-7]，這些算法多采用固定閾值或同一尺度對圖上要素進行綜合。然而，在經(jīng)典著作[1]、法律規(guī)范[8]及相關(guān)研究[9-11]的描述中，均強調(diào)在制圖綜合過程中需要依據(jù)圖上情形適當(dāng)調(diào)整綜合尺度，即在復(fù)雜區(qū)域，綜合尺度可適當(dāng)減小；在簡單區(qū)域，綜合尺度可適當(dāng)增大。由于這一描述較為模糊，且對于圖上線要素而言，其復(fù)雜程度常常難以界定，從而使得當(dāng)前的綜合尺度無法隨著圖上局部區(qū)域復(fù)雜程度的不同而變化，進而使得自動綜合的研究陷入瓶頸。

為了解決上述問題，眾多專家學(xué)者針對線要素的復(fù)雜程度定量化評估提出了不少模型算法[11-20]。文獻[11]依據(jù)邊的振動頻率及幅度，從凹口比例、凸殼周長相對增量及最小外包圓面積相對增量3個方面建立復(fù)雜性度量模型。文獻[12—16]基于分形理論，利用分形維數(shù)描述曲線的復(fù)雜程度。文獻[17—18]通過傅里葉變換將地理線要素從空間域轉(zhuǎn)化到頻率域進行分析，從頻率的角度分析并定義了線要素的復(fù)雜程度。文獻[19—20]主要基于幾何分析，通過線要素的幾何形狀、幾何拓撲、幾何分布來描述線要素的復(fù)雜程度。上述這些模型都是針對單一線或面狀要素，通過計算曲線自身特征(分維數(shù)、頻率、振動頻率)獲取曲線的復(fù)雜程度，取得了較好的試驗效果。然而，在實際航海圖上，曲線的復(fù)雜程度不僅需要顧及自身基本特性，還應(yīng)當(dāng)考慮曲線周圍的其他線要素，即使對于單一線要素而言，其不同部分的復(fù)雜程度也是不盡相同的。如圖1(a)所示，曲線部分A(圖1(a)紅色矩形所圍部分)與部分B(圖1(a)藍色矩形所圍部分)相比，顯然A要比B復(fù)雜得多。類似地，對于多條線要素而言，其圖上不同區(qū)域的復(fù)雜程度也是不盡相同，如圖1(b)中的區(qū)域C(圖1(b)紅色矩形所圍部分)與區(qū)域D(圖1(b)藍色矩形所圍部分)，顯然，區(qū)域C比區(qū)域D要復(fù)雜得多。若直接采用上述方法評估圖1所示曲線復(fù)雜程度，則只能得到各單一曲線的整體復(fù)雜程度，不能準確表示出圖上線要素在各區(qū)域的差異性，難以實現(xiàn)圖上線要素復(fù)雜程度的精細化度量。

圖1 不同分布線要素復(fù)雜程度對比Fig.1 Comparison of complexity between line elements with different distribution

考慮到當(dāng)前線要素復(fù)雜度的度量方法多基于單一線要素求取整體復(fù)雜程度，未顧及線要素在各區(qū)域的差異性，本文提出一種顧及局部差異的航海圖線要素復(fù)雜度度量方法。在分析線要素復(fù)雜區(qū)域與簡單區(qū)域特點的基礎(chǔ)上，通過構(gòu)建約束Delaunay三角網(wǎng)、計算線要素數(shù)據(jù)點復(fù)雜度及內(nèi)插等步驟，實現(xiàn)了圖上線要素復(fù)雜程度的精細化評估。

1 顧及局部差異的線要素復(fù)雜度模型

1.1 基本思想

區(qū)分圖1所示區(qū)域中各線要素復(fù)雜區(qū)域(區(qū)域A和區(qū)域C)與簡單區(qū)域(區(qū)域B與區(qū)域D)的關(guān)鍵點在于采用某種模型或方法對其進行定量化描述。而Delaunay三角網(wǎng)作為空間分析的重要工具，被大量應(yīng)用于空間鄰近關(guān)系探測、彎曲識別、沖突關(guān)系探測等[21-24]，并取得了較好的探測效果。因此，為探索關(guān)于線要素復(fù)雜度的評估模型，本文針對單一線要素及多條線要素分別構(gòu)建約束Delaunay三角網(wǎng)，如圖2所示。

圖2 不同線要素約束Delaunay三角網(wǎng)構(gòu)建Fig.2 The construction of constrained Delaunay triangulation with different line elements

由圖2可知，曲線L1及線要素L2、L3構(gòu)成區(qū)域與圖1中的線要素相類似，其左側(cè)區(qū)域(紅色矩形所示區(qū)域)明顯比右側(cè)區(qū)域(藍色矩形所示區(qū)域)復(fù)雜。在構(gòu)建約束三角網(wǎng)以后，分別從復(fù)雜區(qū)域(紅色矩形所示區(qū)域)以及簡單區(qū)域(藍色矩形所示區(qū)域)任取三角形T1、T3(圖2中藍色三角形所示)、T2、T4(圖2中綠色三角形所示)，不難看出，無論線要素數(shù)量多少，其復(fù)雜區(qū)域三角形T1、T3的邊長明顯要比簡單區(qū)域三角形T2、T4的邊長要短很多，且對于區(qū)域內(nèi)的其他三角形，也具有相同的特性?；诖?，不難得出結(jié)論：無論線要素數(shù)量多少，在構(gòu)建約束Delaunay三角網(wǎng)后，線要素越復(fù)雜，其三角形邊長越短；反之，線要素越簡單，則三角形邊長越長。

基于上述分析，線要素的復(fù)雜程度可采用Delaunay三角網(wǎng)中三角形邊長近似反映。為此，本文使用Delaunay三角網(wǎng)中三角形邊的長度變化對線要素復(fù)雜程度進行定量化描述，流程如圖3所示。

圖3 本文方法主要流程Fig.3 The main process of proposed method

1.2 約束Delaunay三角網(wǎng)構(gòu)建

在航海圖上，線要素分布常常復(fù)雜多樣，且曲線上數(shù)據(jù)點的疏密程度也分布各異?？紤]到本文主要嘗試使用三角形的邊反映曲線的距離變化，因此采用約束Delaunay三角網(wǎng)作為本文的基礎(chǔ)算法。所謂約束Delaunay三角網(wǎng)實際上是指在構(gòu)建三角網(wǎng)時，強行使曲線上的線段成為三角形的一條邊，避免三角形的邊與直線段相交，從而得到約束Delaunay三角網(wǎng)[25](圖4)。對圖4(a)的曲線要素構(gòu)建約束Delaunay三角網(wǎng)如圖4(b)所示，任取其中一個三角形T1(圖4(b)中藍色三角形所示)，邊BC為原始曲線L3上的線段，將這種三角形中為原始曲線線段的邊稱之為約束邊，同理將其中不為原始曲線線段的邊(如圖4(b)中的線段AB、AC)稱之為非約束邊[25]。

圖4 約束Delaunay三角網(wǎng)構(gòu)建Fig.4 The construction of constrained Delaunay triangulation

同時，考慮到曲線上數(shù)據(jù)點疏密分布不均，若直接構(gòu)建三角網(wǎng)會出現(xiàn)眾多狹長三角形進而影響計算結(jié)果，為此對曲線上數(shù)據(jù)點進行加密[24]，其加密后的約束三角網(wǎng)如圖4(c)所示。比對圖4(b)與圖4(c)不難看出，經(jīng)數(shù)據(jù)點加密后的約束三角網(wǎng)，三角形更為密集，更能反映曲線間距離變化。

1.3 曲線數(shù)據(jù)點復(fù)雜度計算

1.3.1 數(shù)據(jù)點復(fù)雜度定義

依據(jù)1.1節(jié)的相關(guān)描述，利用約束三角網(wǎng)可對線要素間距離變化進行探測，進而反映出曲線復(fù)雜程度的變化。然而，這一描述仍然是定性的描述，無法直接計算曲線復(fù)雜程度，因此，如何建立三角形邊長與曲線復(fù)雜程度之間的定量映射關(guān)系就成了亟須解決的問題。為此，本文嘗試采用曲線上數(shù)據(jù)點的復(fù)雜程度描述曲線在該數(shù)據(jù)點附近的復(fù)雜程度(圖5)，并將曲線上數(shù)據(jù)點復(fù)雜度定義為與該數(shù)據(jù)點相關(guān)非約束邊平均長度的倒數(shù)，其計算公式為

(1)

式中，di表示各非約束邊的長度；n表示非約束邊的數(shù)量值。

對圖5(a)所示線要素構(gòu)建約束Delaunay三角網(wǎng)如圖5(b)所示，任取其中一個數(shù)據(jù)點A，依據(jù)構(gòu)建的三角網(wǎng)可知，與點A相關(guān)的邊有AB、AC、AD、AE、AF、AG，其中邊AB與AD為原始曲線L2上的線段(即約束邊)，其他邊均為非約束邊。依據(jù)1.2節(jié)的相關(guān)描述可知，在約束Delaunay三角網(wǎng)構(gòu)建時，需對曲線上的數(shù)據(jù)點進行加密處理，因此，上述約束邊的長度常被人為給定，且約束邊的長度實質(zhì)上反映的是曲線上數(shù)據(jù)點的疏密變化，與本文需反映的線要素間的距離變化并無直接關(guān)聯(lián)，因此在計算數(shù)據(jù)點復(fù)雜度時應(yīng)當(dāng)予以剔除。即計算圖5(b)中點A處的復(fù)雜度時，應(yīng)當(dāng)剔除邊AB與AD，僅考慮邊AC、AE、AF、AG，并使用式(1)計算其復(fù)雜程度。

圖5 數(shù)據(jù)點復(fù)雜度定義Fig.5 The definition of data point complexity

1.3.2 異常邊剔除

在實際航海圖上，線要素分布繁雜多樣，其構(gòu)建形成的約束Delaunay三角網(wǎng)也種類繁多。在計算數(shù)據(jù)點復(fù)雜度時還存在一類情形，如圖6所示，對曲線L1與L2構(gòu)建約束三角網(wǎng)后，其中曲線L2上與數(shù)據(jù)點A相關(guān)的非約束邊有AB、AC、AD、AE、AF、AG，其中邊AF、AG長度明顯大于其他非約束邊，若不加處理直接計算點A復(fù)雜度，將導(dǎo)致點A復(fù)雜度偏小，進而使得計算結(jié)果無法正確反映實際復(fù)雜程度。因此，有必要對該類型非約束邊進行剔除。本文將這種長度明顯長于其他非約束邊，且明顯影響復(fù)雜度計算的非約束邊稱之為異常邊。

圖6 異常邊剔除Fig.6 The rejection of abnormal edges

基于上述分析，為保證復(fù)雜度值計算的合理性與準確性，本文采用拉依達準則(3σ準則)對異常邊進行識別并剔除。其具體過程如下：

(1) 依據(jù)構(gòu)建的三角網(wǎng)，獲取與數(shù)據(jù)點相關(guān)的所有非約束邊的長度值，記為d1、d2、…、dn。如圖6中與點A相關(guān)的非約束邊AB、AC、AD、AE、AF、AG的長度值，可分別記為d1、d2、…、d6。

(2) 依據(jù)步驟(1)中的長度值，按照式(2)計算標準差σ

(2)

(3) 針對步驟(1)中的全體非約束邊長度值，依據(jù)式(3)做如下判斷：若某條非約束邊的長度d滿足

(3)

則認為該非約束邊的長度是含有粗大誤差值的異常值(n的取值可為1、2、3)，該非約束邊為異常邊。

需要說明的是，式(3)中的n值可取1、2、3，但經(jīng)筆者多次試驗，發(fā)現(xiàn)當(dāng)該值取2時，其識別效果最優(yōu)，可識別絕大部分的異常邊，因此本文建議將該值取為2。

1.4 航海圖線要素復(fù)雜場計算

通過1.3節(jié)的相關(guān)步驟，可計算出曲線上各數(shù)據(jù)點所在位置的復(fù)雜程度，然而，其結(jié)果為相對離散點的復(fù)雜度，仍無法反映整張航海圖線要素的復(fù)雜程度變化。因此，本文采用空間插值的方法對上述離散復(fù)雜度進行內(nèi)插，從而得到了連續(xù)的線要素復(fù)雜場，實現(xiàn)了航海圖線要素復(fù)雜度評估由離散線到面的躍升。

當(dāng)前空間插值算法相對較多，主要有泰森(Thiessen)多邊形法、反距離加權(quán)法、樣條函數(shù)法、克立格(Kriging)插值法、線性內(nèi)插法、雙線性多項式插值法、自然鄰點插值法、趨勢面法等[26-27]，經(jīng)過多次試驗，自然鄰點插值法[28-32]效果最優(yōu)，因此本文采用自然鄰點插值法對離散點復(fù)雜度進行內(nèi)插。復(fù)雜場求取主要步驟如下：

(1) 輸入航海圖線要素數(shù)據(jù)，構(gòu)建約束Delaunay三角網(wǎng)。

(2) 逐一遍歷線要素上的數(shù)據(jù)點，并依據(jù)1.3節(jié)所述方法計算各數(shù)據(jù)點復(fù)雜程度。

(3) 采用自然鄰點插值法對上述各數(shù)據(jù)點的復(fù)雜度進行內(nèi)插，即得到航海圖線要素復(fù)雜場，并輸出結(jié)果。

如圖7所示，對圖7(a)所示的線要素采用本文方法計算各點復(fù)雜度如圖7(b)所示，隨后采用自然鄰點插值法對其進行內(nèi)插，并根據(jù)復(fù)雜度的大小對試驗結(jié)果顯示成圖，如圖7(c)所示。

圖7 復(fù)雜場求取Fig.7 The calculation of complex field

2 試驗與分析

2.1 線要素復(fù)雜度有效性試驗

為對本文方法的有效性進行驗證，本文分別選取了3組單一線要素和多線要素作為試驗對象。運用本文復(fù)雜性度量方法，按照1.4節(jié)的步驟分別計算出線要素上各點的復(fù)雜度，經(jīng)過自然鄰點法內(nèi)插生成復(fù)雜場，利用C++及動態(tài)庫GDAL2.2.0編程實現(xiàn)，并使用ArcGIS對試驗結(jié)果進行顯示成圖。

2.1.1 單一線要素

為了驗證本文方法對線要素各區(qū)域復(fù)雜程度的識別效果，首先選取了3組不同形狀的單一線要素作為試驗對象，如圖8所示，其中圖8(a)、(c)、(e)為原始線要素，圖8(b)、(d)、(f)為本文方法生成的相對應(yīng)的復(fù)雜場。由圖8(a)、(c)、(e)可以看出每個區(qū)域的復(fù)雜程度是明顯不同的，同時各復(fù)雜區(qū)域的分布也是不同的，可較好地驗證本文方法的有效性。在圖8(b)、(d)、(f)中為了方便對各復(fù)雜區(qū)域進行區(qū)分，根據(jù)復(fù)雜度的數(shù)值采用熱力圖對計算結(jié)果進行顯示成圖。

圖8 單一線要素復(fù)雜場Fig.8 The complex field of single line element

在圖8(a)、(c)、(e)原始線要素中，線要素越曲折、震蕩越劇烈的區(qū)域，在圖8(b)、(d)、(f)對應(yīng)復(fù)雜場中表示的顏色就越鮮艷，其對應(yīng)復(fù)雜度的值也就越大；在圖8(a)、(c)、(e)原始線要素中，線要素越平緩、震蕩越輕微的區(qū)域，在圖8(b)、(d)、(f)對應(yīng)復(fù)雜場中表示的顏色就越藍，其對應(yīng)復(fù)雜度的值也就越小。

2.1.2 多條線要素

上述試驗驗證了本文方法針對單一線要素具有較好的識別效果。為了進一步檢驗本文方法的有效性及適用性，又另選取3組分布各異的多條線要素作為試驗對象。如圖9所示，圖9(a)、(c)、(e)為原始線要素，圖9(b)、(d)、(f)為本文方法生成的復(fù)雜場。從圖9(a)、(c)、(e)中可以看出，同一線要素上各區(qū)域的復(fù)雜程度是明顯不同的，同時線與線之間的緊密程度也是不同的，且分布各異，因此可較好地驗證復(fù)雜度評估模型的有效性。

圖9 多線要素復(fù)雜場Fig.9 The complex field of multiline elements

由圖9可知，在圖9(a)、(c)、(e)原始線要素中，線要素越曲折，線與線之間越緊密的區(qū)域，在圖9(b)、(d)、(f)對應(yīng)復(fù)雜場中表示的顏色越鮮艷，其對應(yīng)復(fù)雜度的值也就越大；在圖9(a)、(c)、(e)原始線要素中，線要素越平緩，線與線之間越稀疏的區(qū)域，在圖9(b)、(d)、(f)對應(yīng)復(fù)雜場中表示的顏色就越藍，其對應(yīng)復(fù)雜度的值也就越小。由試驗結(jié)果來看，線要素簡單稀疏的區(qū)域和復(fù)雜緊密的區(qū)域均被較好地識別區(qū)分出來，且對各區(qū)域的復(fù)雜程度進行了較好的度量。

綜合來看，對于上述單線要素以及多線要素，運用本文方法可較好地區(qū)分復(fù)雜與簡單區(qū)域，且能夠定量評估線要素在各區(qū)域的復(fù)雜度。

2.2 航海圖線要素復(fù)雜度統(tǒng)計分析試驗

為對本文復(fù)雜度模型的有效性及適用性進行整體性驗證，選取了兩組分布各異的航海圖作為試驗數(shù)據(jù)，利用ArcGIS對試驗結(jié)果進行顯示成圖，同時為了評估本文方法對線要素復(fù)雜程度的識別情況，采用問卷調(diào)查、統(tǒng)計分析的方法，對線要素復(fù)雜度場模型的識別效果進行評估分析。受調(diào)查者中，主要分為3類人群，普通人群(50人)、具有一定測繪專業(yè)基礎(chǔ)知識的人群(35人)、專家學(xué)者(10人)，由這95人對線要素復(fù)雜度模型的識別結(jié)果進行評判。

2.2.1 試驗區(qū)域1(C13640)

本次試驗海區(qū)數(shù)據(jù)選自由中國航海圖書出版社發(fā)行的普通航海圖C13640，圖10(a)為經(jīng)測試者劃分的復(fù)雜區(qū)域，圖10(b)為由線要素復(fù)雜度場模型劃分的復(fù)雜區(qū)域(采用熱力圖的方式表示復(fù)雜度不同的各區(qū)域)，并將關(guān)于復(fù)雜區(qū)域識別效果的問卷調(diào)查統(tǒng)計結(jié)果展示如圖11所示。

圖10 線要素復(fù)雜場Fig.10 The complex field of line elements

圖11 識別效果統(tǒng)計Fig.11 The statistical of recognition result

由圖10可以看出，由本文方法劃分的復(fù)雜區(qū)域與測試者劃分的復(fù)雜區(qū)域基本一致，其中5、6、7、9這4塊區(qū)域識別效果最好，能較好地區(qū)分出復(fù)雜程度不同的各線要素區(qū)域。同時由圖11問卷調(diào)查的統(tǒng)計結(jié)果可知，在普通人群中，超過九成以上的受訪者認為本文方法對復(fù)雜區(qū)域的識別效果較好，其中8人認為識別結(jié)果完全一致。在有測繪專業(yè)基礎(chǔ)的人群中，94%的受訪者認為本文方法對復(fù)雜區(qū)域的識別效果為基本一致及以上，其中10人認為識別結(jié)果完全一致。在對專家學(xué)者的識別度調(diào)查中，普遍認為場模型對復(fù)雜區(qū)域的識別劃分效果較好。

2.2.2 試驗區(qū)域2(C12351)

為了進一步評判線要素復(fù)雜度場模型對復(fù)雜區(qū)域的識別效果，本文選取了另一幅航海圖作為試驗數(shù)據(jù)，該圖選自中國航海圖書出版社發(fā)行的大比例尺港灣圖C12351，圖12(a)為經(jīng)測試者劃分的復(fù)雜區(qū)域，圖12(b)為由本文方法劃分的復(fù)雜區(qū)域，并將識別效果的問卷調(diào)查統(tǒng)計結(jié)果展示如圖13所示。

由圖12可以看出，相對上一組試驗本海區(qū)線要素要更為復(fù)雜，但由本文方法劃分的復(fù)雜區(qū)域與測試者劃分的復(fù)雜區(qū)域基本一致，其中1、2、3、4、5這5塊區(qū)域識別效果比較好。同時，由圖13可知，在普通人群中，94%的受訪者認為本文所提的線要素復(fù)雜度場模型對復(fù)雜區(qū)域的識別效果較好，其中35人認為基本一致，12人認為完全一致。在有測繪專業(yè)基礎(chǔ)的人群中，九成以上的受訪者也認為本文所提方法對復(fù)雜區(qū)域的識別劃分效果較好。在對專家學(xué)者的識別度調(diào)查中，8人認為基本一致，2人認為完全一致，均認為本文算法識別效果較好。

圖12 線要素復(fù)雜場Fig.12 The complex field of line elements

圖13 識別效果統(tǒng)計Fig.13 The statistic of recognition result

2.2.3 總體評估試驗

為了進一步說明本文所提方法對復(fù)雜區(qū)域的識別劃分能力，對受訪者做了一個關(guān)于兩幅圖總體識別效果的問卷調(diào)查，具體統(tǒng)計結(jié)果如圖14所示。

圖14 總體識別效果統(tǒng)計Fig14 The statistic of holistic recognition result

本文方法對于所選取的兩組分布各異的航海圖區(qū)域，總體識別效果良好。由圖14可知，在普通人群與有測繪專業(yè)基礎(chǔ)的人群中，超過九成的受訪者認為本文方法對復(fù)雜區(qū)域的總體識別效果表示認可，在對專家學(xué)者的識別度調(diào)查中，均認為線要素復(fù)雜度場模型對復(fù)雜區(qū)域的總體識別效果較好，統(tǒng)計結(jié)果都為基本一致。

綜上所述，從試驗結(jié)果及問卷調(diào)查的統(tǒng)計結(jié)果來看，本文方法取得了較好的識別效果，未出現(xiàn)明顯識別錯誤的區(qū)域，很好地符合了人們對線要素復(fù)雜程度的視覺感受，能較好地定量評估出不同線要素區(qū)域的復(fù)雜程度。

3 結(jié) 論

本文提出了一種顧及局部差異的航海圖線要素復(fù)雜度度量方法。該方法從線要素節(jié)點所構(gòu)三角網(wǎng)邊長與線要素復(fù)雜程度的關(guān)聯(lián)性出發(fā)，通過構(gòu)建約束Delaunay三角網(wǎng)、計算數(shù)據(jù)點復(fù)雜度以及內(nèi)插等步驟，最終得到了航海圖線要素復(fù)雜度場模型，經(jīng)理論推導(dǎo)及試驗比對分析，得出結(jié)論如下：本文方法顧及了線要素在圖上各區(qū)域的差異性，將線要素復(fù)雜度的計算，由對離散線的度量上升到對整個面的度量，能較好地定義航海圖線要素的復(fù)雜度，可精細化地定量評估航海圖線要素在各區(qū)域的復(fù)雜程度。