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

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

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

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

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

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

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

1.1 基本思想

區(qū)分圖1所示區(qū)域中各線要素復雜區(qū)域(區(qū)域A和區(qū)域C)與簡單區(qū)域(區(qū)域B與區(qū)域D)的關(guān)鍵點在于采用某種模型或方法對其進行定量化描述。而Delaunay三角網(wǎng)作為空間分析的重要工具，被大量應用于空間鄰近關(guān)系探測、彎曲識別、沖突關(guān)系探測等[21-24]，并取得了較好的探測效果。因此，為探索關(guān)于線要素復雜度的評估模型，本文針對單一線要素及多條線要素分別構(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ū)域)復雜。在構(gòu)建約束三角網(wǎng)以后，分別從復雜區(qū)域(紅色矩形所示區(qū)域)以及簡單區(qū)域(藍色矩形所示區(qū)域)任取三角形T1、T3(圖2中藍色三角形所示)、T2、T4(圖2中綠色三角形所示)，不難看出，無論線要素數(shù)量多少，其復雜區(qū)域三角形T1、T3的邊長明顯要比簡單區(qū)域三角形T2、T4的邊長要短很多，且對于區(qū)域內(nèi)的其他三角形，也具有相同的特性?；诖?，不難得出結(jié)論：無論線要素數(shù)量多少，在構(gòu)建約束Delaunay三角網(wǎng)后，線要素越復雜，其三角形邊長越短；反之，線要素越簡單，則三角形邊長越長。

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

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

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

在航海圖上，線要素分布常常復雜多樣，且曲線上數(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ù)點復雜度計算

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

依據(jù)1.1節(jié)的相關(guān)描述，利用約束三角網(wǎng)可對線要素間距離變化進行探測，進而反映出曲線復雜程度的變化。然而，這一描述仍然是定性的描述，無法直接計算曲線復雜程度，因此，如何建立三角形邊長與曲線復雜程度之間的定量映射關(guān)系就成了亟須解決的問題。為此，本文嘗試采用曲線上數(shù)據(jù)點的復雜程度描述曲線在該數(shù)據(jù)點附近的復雜程度(圖5)，并將曲線上數(shù)據(jù)點復雜度定義為與該數(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ù)點復雜度時應當予以剔除。即計算圖5(b)中點A處的復雜度時，應當剔除邊AB與AD，僅考慮邊AC、AE、AF、AG，并使用式(1)計算其復雜程度。

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

1.3.2 異常邊剔除

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

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

基于上述分析，為保證復雜度值計算的合理性與準確性，本文采用拉依達準則(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)當該值取2時，其識別效果最優(yōu)，可識別絕大部分的異常邊，因此本文建議將該值取為2。

1.4 航海圖線要素復雜場計算

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

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

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

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

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

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

圖7 復雜場求取Fig.7 The calculation of complex field

2 試驗與分析

2.1 線要素復雜度有效性試驗

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

2.1.1 單一線要素

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

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

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

2.1.2 多條線要素

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.3 總體評估試驗

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

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

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

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

3 結(jié) 論

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