Stroke構造、移位一體化的道路網示意化方法

付仲良，翁寶鳳，胡玉龍

武漢大學遙感信息工程學院,湖北 武漢 430079

?

Stroke構造、移位一體化的道路網示意化方法

付仲良，翁寶鳳，胡玉龍

武漢大學遙感信息工程學院,湖北 武漢 430079

針對當前常用示意性地圖生成方法中往往存在簡化程度不夠、未考慮長度信息以及時間效率低等問題，提出了stroke構造、移位一體化的道路網示意化方法。該方法在對道路網進行stroke劃分構造的同時，直接對其進行漸進式的移位示意化及拓撲檢查。同時本文還提出利用相似分形維數(shù)來定量比較并驗證不同示意化方法的有效性。試驗表明，本算法在考慮原始線形的基礎上，示意化過程簡單，時間效率較高，減少了拓撲沖突問題，保證了拓撲一致性及路網的均衡分布，具有較好的清晰度和認知度。

路網；示意化；stroke構造；移位；相似分形維數(shù)

示意性地圖(schematic map)始于19世紀初，是對網絡線性要素進行簡化，舍去與地圖主題無關的地圖要素，對地圖中的線性要素進行概略性表達的地圖。倫敦地鐵圖是示意性地圖的代表，它將地鐵線繪制成水平、垂直、對角線方向，并保留相對的拓撲信息，提供給用戶簡潔清晰的地圖信息[1]。之后，示意性地圖被廣泛地應用于各個領域，如道路交通網[2]、公交線路網、電力網[3]、河流網[4]等。

示意性地圖應用領域的不同，所關注的信息也會不同，因而在繪制道路網示意性地圖時與繪制地鐵圖將有所區(qū)別。對此，國內外學者對示意地圖進行了相關的研究。文獻[5—7]研究自動化生成示意性地鐵圖的方法，算法簡單方便，但未考慮原始線形，示意結果圖與原始圖有較大差別，并不適合道路網的自動示意化。文獻[8—9]在考慮原始線形的基礎上，基于道路網的路段進行示意化過程，以獨立網絡弧段作為基本單元。盡管示意圖接近原始道路網，但圖形容易產生鋸齒效應，簡化程度不夠。文獻[10]提出基于動態(tài)分段，以路徑為單位，顧忌路徑等級、長度等指標進行道路網示意化。然而對于某些道路網數(shù)據(jù)，并不存在路徑等級等屬性數(shù)據(jù)，無法進行動態(tài)分段；且在實際路網中，有些路徑過長，有些路徑過短，則造成結果的變形。文獻[11]以閉合多邊形(網眼)為基本單位，利用網眼的獨立性與鄰接性，提出了基于拓撲關系直接定位點線的多邊形生長算法。然而該算法僅考慮了節(jié)點之間的部分方位信息以及保證了拓撲不變形，而沒有參考圖形的長度信息，使得示意化后的結果圖在形狀上有明顯的變形。文獻[12]提出基于路劃(stroke)的自動化示意化方法，主要通過屬性一致性或幾何連通性組織網絡弧段從而構造stroke，以stroke為基本單元進行排序、形狀簡化、拓撲驗證，最終生成示意圖，算法考慮了線的原始形狀，但過于繁瑣復雜，多次迭代，時間耗費大。

本文對以上算法進行分析和對比，提出基于stroke構造、移位一體化的道路網示意化方法，并提出利用相似分形維數(shù)來定量評估示意化結果。算法在考慮原始線形的基礎上，使示意化過程更為簡單，時間效率更高，示意化過程中拓撲沖突減少，同時具有較高的清晰度和認知度。

1　基于道路網stroke的示意化

1.1道路網stroke模型

道路網數(shù)據(jù)作為一種基礎地理數(shù)據(jù)，一般以節(jié)點-弧段的拓撲結構存儲于GIS中。然而這種以節(jié)點和弧段構成的道路網絡，不符合人們頭腦中現(xiàn)實路徑的認知整體性。文獻[12]提出根據(jù)感知分組“良好連續(xù)性”原則，將數(shù)條相對連續(xù)的路段連接成一個整體構建成一個“stroke”，考慮道路的自然形態(tài)單元，具有很好的連通性。構建stroke的方法分為基于幾何特征和基于語義特性兩種。前者考慮道路網在只有幾何特征的基礎上，根據(jù)幾何連通性組織構造stroke；后者利用屬性信息的一致性來構造stroke。而通常的做法是以幾何連通性為主，輔以名稱、類別等語義信息來進行判斷構造。由于實際道路網數(shù)據(jù)往往缺失語義信息或者語義信息不全，本文采用基于幾何特征的雙向探測方法來構建stroke，具體算法如下。

(1) 讀取道路網結構，得到節(jié)點集合P{p1,p2,…，pn}以及弧段集合E{e1,e2,…，em}。

(2) 順序讀取弧段集中的一弧段，作為起始弧段，判斷是否歸屬于某一stroke：若屬于，則繼續(xù)判斷下一弧段；若不屬于，則建立新stroke，執(zhí)行(3)。

(3) 利用起始弧段的首、尾節(jié)點進行雙向空間搜索，找出與其相鄰的弧段。判斷相鄰弧段是否都歸屬于某一stroke，若是，則回到(2)；若不是，則繼續(xù)判斷新弧段與起始弧段間的夾角是否大于某一閾值：若大于等于某一閾值，則與該弧段相連構成stroke；若小于某一閾值，則結束。該相鄰新弧段作為起始弧段，重復執(zhí)行(3)。

(4) 重復(2)—(3)，直至所有弧段集都遍歷完，所有stroke構建完成。

1.2基于stroke的示意化方法分析

道路網stroke模型近年來被學者應用于路網示意化[12]、路網綜合[13-14]中，顧及了路網語義、幾何及拓撲的特征，保持了路網的完整性和連通性。對于道路網基于stroke的示意化方法，文獻[12]給出了具體算法思路，如下：

(1) 通過屬性一致性或者幾何連通性構造stroke。

(2) stroke按照一定規(guī)則進行排序。

(3) 根據(jù)方向偏離或者方向變化來重新劃分子stroke。

(4) 對子stroke進行示意化。

(5) 最后檢查拓撲一致性，移位糾正。

然而，該算法過程復雜，多次迭代，耗時長，且在示意化過程中易出現(xiàn)以下問題：

(1) 一般stroke構造結合幾何和語義特征進行一致性判斷，完成stroke構造后，根據(jù)若干指標(重要度、連通度、中心度等)計算其重要性的權值，并以此排序[15]。然而，在實際應用中，道路網數(shù)據(jù)并不盡如人意，往往存在語義信息不全甚至沒有的問題。因而根據(jù)語義信息構造stroke存在許多實際問題。

(2) 在對stroke根據(jù)一定指標進行排序后，按照重要性由大至小來進行示意化，直至完成所有stroke的示意化。但是在這種重要性排序的前提下，難以維持拓撲一致性，可能導致示意圖局部集中，而忽略區(qū)域分布特征的問題，拓撲沖突問題明顯。如圖1(a)，在路a、b已示意化的前提下，對路c進行示意化時，使得a、b與c的相交點發(fā)生變化，從而引起拓撲沖突問題。

為解決以上問題，本文僅考慮道路網的幾何特征和拓撲關系來構造stroke，提出stroke構造、移位一體化的算法，使得示意化過程簡單，時間效率高，減少了拓撲沖突問題，保證拓撲一致性及路網的均衡分布。

2　基于stroke構造、移位一體化的示意化方法

本節(jié)將針對1.2節(jié)中所出現(xiàn)的問題進行討論。首先，針對上文所述語義信息問題，本文不考慮語義特征，主要采用基于幾何特征的雙向探測方法來構建stroke，算法見1.1節(jié)。其次，對于stroke排序后示意化而引起的拓撲不一致以及局部集中問題，本文提出基于stroke構造、移位一體化的示意化方法，在對道路網進行stroke劃分構造的同時，直接對其進行漸進式的移位示意化以及拓撲檢查。如圖1(b)，按1—7順序逐次構造stroke并同時進行投影移位，避免圖1(a)中的拓撲沖突。

2.1stroke構造

根據(jù)“良好連續(xù)性”的原則[16]，本文以方向變化一致的視為同一stroke，即相鄰兩條線段的偏斜角(圖2)是否超過某一閾值，若超過則分段；不超過，則視為同一stroke。本文主要采用8方位示意化方法(圖3)，即將stroke投影映射到水平、垂直、對角線方位上。通過計算其方位角α與{0°，45°，90°，135°，180°，225°，270°，315°}中任意角度αi比較，求最小值

(1)

滿足最小值時的αi即為該stroke的方向。由式(1)可知，當兩線段的偏斜角大于22.5°時，歸為不同方向。因而本文將22.5°視為stroke自動劃分閾值。

在示意化算法實現(xiàn)過程中，筆者發(fā)現(xiàn)若遇到道路交叉點這一特殊要素時，往往情況復雜，易引起道路拓撲變化，進而影響交叉點相連的數(shù)條線段。因而，本文對于交叉點，將其視為stroke構造劃分的重要依據(jù)。

2.2stroke移位投影、拓撲檢查

構造完成的stroke需進行移位處理。由式(1)求得的新方位角αi，根據(jù)式(2)采用投影的方式對其進行方位判斷后實現(xiàn)移位

(2)

以下以45°投影為例進行說明。如圖4，線段a的新方位角為45°，對其進行投影移位：首先，將a正方向旋轉45°至線段b；然后將線段b投影到水平位置，x不變，y為起始點y值，成為線段c；最后將線段c反旋轉45°至線段d。線段d即為線段a的新移位位置。

是否將某一stroke位移至新的位置，還需通過拓撲檢查，判斷新位置是否與原圖發(fā)生拓撲沖突，若發(fā)生拓撲沖突，需計算新的位置。本文涉及的拓撲檢查主要見參考文獻[17]，其詳細介紹了拓撲關系一致性檢查和新點位的計算。

圖1　拓撲問題Fig.1　Topological problem

圖2　偏斜角Fig.2　Deflection angle

圖3　8方位示意化Fig.3　8-direction schematic

圖4　45°投影位移圖Fig.4　45° projection and displacement map

2.3stroke構造、移位一體化算法

本文提出的基于stroke構造、移位一體化的道路網示意化方法，是在對道路網進行2.1節(jié)劃分構造的同時，直接漸進式地對stroke進行2.2節(jié)的移位投影和拓撲檢查，以保證算法的時間效率和拓撲一致性，同時減少因拓撲沖突引起的移位過程。具體算法如下：

(1) 從地圖的左下角的第1條開始標記，得到所有未處理線段segment集合S={S1,S2,…,Sm}，共m段，起始弧段SQ=S1。

(2) 判斷集合S是否為空，若為空，循環(huán)結束；若不為空，則判斷SQ是否為空，若為空，遍歷集合S，任取Si作為SQ。初始化stroke={SQ}，SQ移除集合S，且SQ=null。

(3) 判斷與當前stroke相鄰線段Sl是否屬于集合S，若屬于，則繼續(xù)(4)，若不屬于則跳至(6)。

(4) 判斷當前stroke與Sl的中間點是否為交叉點，若是，SQ=Sl，構造完成跳至(6)；若不是，繼續(xù)(5)。

(5) 判斷stroke與Sl的偏斜角是否超過閾值，若超過閾值，構造完成，SQ=Sl，跳至(6)；若不超過閾值，構造stroke={SQ,Sl}，Sl移除集合S，繼續(xù)(3)。

(6) 對當前stroke投影移位。

(7) 對當前stroke拓撲檢查：若拓撲一致，跳至(2)重新開始構造stroke；若拓撲沖突，重新計算新位置后重復執(zhí)行(7)。

上述方法，在集合S處理完成的同時，所有stroke示意化的過程也已完成，保證了示意結果道路目標的均勻性，緩解了以往等級劃分stroke而導致的局部集中問題。同時，整個過程時間效率上明顯優(yōu)于以往的方法，且拓撲也較易保持，有效地完成了道路網的示意化過程，也保證了道路網的連通性，示意結果的空間認知也有效地得到保證。

3　試驗及分析

3.1試驗數(shù)據(jù)與結果

為驗證本文中所提出的示意化方法的高效性，試驗采用兩組真實道路網數(shù)據(jù)。數(shù)據(jù)1為某校園真實矢量道路網數(shù)據(jù)，見圖5；數(shù)據(jù)2為英國英格蘭東部Waveney地區(qū)的部分道路網數(shù)據(jù)，見圖9。本文利用這兩組數(shù)據(jù)，實現(xiàn)以獨立網絡弧段為基本單元的示意化試驗(試驗1)以及文獻[12]的stroke排序方法的試驗(試驗2)，對比stroke構造、移位一體化試驗(試驗3)來生成示意化結果。圖6—圖8為數(shù)據(jù)1的3組試驗結果，圖10—圖12為數(shù)據(jù)2的3組試驗結果。

圖5　原始圖(數(shù)據(jù)1)Fig.5　Original map (data 1)

圖6　試驗1圖(數(shù)據(jù)1)Fig.6　Experiment 1 map (data 1)

圖7　試驗2圖(數(shù)據(jù)1)Fig.7　Experiment 2 map (data 1)

圖8　試驗3圖(數(shù)據(jù)1)Fig.8　Experiment 3 map (data 1)

3.2定性分析

試驗結果從簡化度、空間認知度和時間效率3方面來進行定性評估。首先，分別對比圖5—圖8以及圖9—圖12，不難發(fā)現(xiàn)3個試驗都從不同程度上對原始道路網進行了一定程度的簡化示意化。其中試驗1相比試驗2、3的簡易程度較低，試驗2和3簡易度大體一致。而對比兩組數(shù)據(jù)的空間認知度，試驗1較復雜，試驗2、3更為清晰、明確。其次，在簡化程度和認知清晰度相近的情況下，主要對比分析試驗2和3的時間效率。本文采用VS2010開發(fā)系統(tǒng)，在Windows8，64位操作系統(tǒng)下對兩組數(shù)據(jù)進行試驗，兩個試驗對于數(shù)據(jù)1的運行時間分別約為135s、95s，數(shù)據(jù)2為289s、220s。試驗結果表明試驗3的時間效率明顯高于試驗2。

圖9　原始圖(數(shù)據(jù)2)Fig.9　Original map (data 2)

圖10　試驗1圖(數(shù)據(jù)2)Fig.10　Experiment 1 map (data 2)

圖11　試驗2圖(數(shù)據(jù)2)Fig.11　Experiment 2 map (data 2)

圖12　試驗3圖(數(shù)據(jù)2)Fig.12　Experiment 3 map (data 2)

3.3定量分析

以往研究都是從定性上進行分析評價，本文采用分形維數(shù)定量地對試驗效果進行評價。無論采用何種方式進行示意化，示意化后的結果空間形態(tài)上都具有相似性，因而滿足分形的要求。選取相似維數(shù)作為本文的研究指標，相似維數(shù)D反映原道路網與示意化道路網的相似程度。分維數(shù)越大，方格中有公路通過的網絡邊數(shù)越多，新網絡與原網絡的相似程度越高，網絡的覆蓋形態(tài)越好，曲線的分形維數(shù)可用式(3)表示[18-20]

L(r)=Cr1-D

(3)

由式(3)取對數(shù)，則演變?yōu)?/p>

lgNr=A-Dlgr

(4)

利用計盒法進行相似維數(shù)的計算，盒子取正方形。利用GIS矢量數(shù)據(jù)轉換柵格數(shù)據(jù)的過程來模擬用不同尺寸盒子去覆蓋曲線的方法，獲得不同尺寸r以及方格數(shù)Nr，利用最小二乘求線性回歸得到相似維數(shù)。試驗分別計算原始圖、試驗1、2、3結果圖的分形維數(shù)，得到數(shù)據(jù)1的結果值分別為1.011 1、1.014、1.020 5、1.016 9，數(shù)據(jù)2為1.016 1、1.015、1.018 3、1.014 1。求試驗1、2、3與原始圖的分形維數(shù)差，數(shù)據(jù)1分別為0.002 9、0.009 4、0.005 8，數(shù)據(jù)2為0.001 1、0.002 2、0.002。從分形維數(shù)差上發(fā)現(xiàn)：試驗1的分形維數(shù)差最??；試驗2、3相近，但試驗3小于試驗2。這表明試驗1相較于試驗2、3更接近于原始路網，示意化結果復雜；試驗2、3示意化程度相近，但試驗3與原圖的相似度更高些。兩組數(shù)據(jù)的具體分形維數(shù)的計算見表1和表2，分形維數(shù)的結果值見圖13和圖14。

4　結　論

本文提出了一種新的基于stroke構造、移位一體化的道路網示意化方法，同時還提出利用相似分形維數(shù)來定量比較驗證不同示意化方法的有效性。試驗結果表明，與之前的方法比較，本算法在考慮原始線形的基礎上，使示意化過程更為簡單，時間效率更高，減少了拓撲沖突問題，保證拓撲一致性及路網的均衡分布，同時又具有很高的空間認知度和清晰度。本文對于相似維數(shù)的計算應在一定的無標度區(qū)內，而無標度區(qū)的計算復雜，將是今后的研究重點。

表1　分形維數(shù)計算表(數(shù)據(jù)1)

表2　分形維數(shù)計算表(數(shù)據(jù)2)

圖13　分形維數(shù)圖(數(shù)據(jù)1)Fig.13　Fractal dimension chart (data 1)

圖14　分形維數(shù)圖(數(shù)據(jù)2)Fig.14　Fractal dimension chart (data 2)

[1]MORRISON A. Public Transport Maps in Western European Cities[J]. The Cartographic Journal, 1996, 33(2): 93-110.

[2]AVELAR S, HURNI L. On the Design of Schematic Transport Maps[J]. Cartographica, 2006, 41(3): 217-228.

[3]AVELAR S. Convergence Analysis and Quality Criteria for an Iterative Schematization of Networks[J]. GeoInformatica, 2007, 11(4): 497-513.

[4]STOTT J M, RODGERS P. Automatic Metro Map Design Techniques[C]∥Proceedings of the XXII International Cartographic Conference. Madrid: [s.n.], 2005.

[5]HONG S H, MERRICK D, DO NOSCIMENTO H A D. Automatic Visualisation of Metro Maps[J]. Journal of Visual Languages & Computing, 2006, 17(3): 203-224.

[6]STOTT J, RODGERS P, MARTINEZ-OVANDO J C, et al. Automatic Metro Map Layout Using Multicriteria Optimization[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(1): 101-114.

[7]NOLLENBURG M, WOLFF A. Drawing and Labeling High-quality Metro Maps by Mixed-integer Programming[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(5): 626-641.

[8]AVELAR S, MUELLER M. Generating Topologically Correct Schematic Maps[C]∥Proceedings of the 9th International Spatial Data Handling. Beijing: [s.n.], 2000: 28-35.

[9]WARE J M, TAYLOR G E, ANAND S, et al. Automated Production of Schematic Maps for Mobile Applications[J]. Transactions in GIS, 2006, 10(1): 25-42.

[10]董衛(wèi)華, 李志林, 郭慶勝. 基于動態(tài)分段的道路網示意性地圖模型綜合[J]. 武漢大學學報(信息科學版), 2010, 35(8): 892-895.

DONG Weihua, LI Zhilin, GUO Qingsheng. Automated Model Generalization of Schematic Network Maps Based on Dynamic Segmentation[J]. Geomatics and Information Science of Wuhan University, 2010, 35(8): 892-895.

[11]張藍, 李佳田, 徐珩, 等. 道路網絡示意圖的多邊形生長算法[J]. 測繪學報, 2015, 44(3): 346-352. DOI: 10.11947/j.AGCS.2015.20130724.ZHANG Lan, LI Jiatian, XU Heng, et al. Polygon Growing Algorithm for Network Schematic Maps[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(3): 346-352. DOI: 10.11947/j.AGCS.2015.20130724.

[12]LI Zhilin, DONG Weihua. A Stroke-based Method for Automated Generation of Schematic Network Maps[J]. International Journal of Geographical Information Science, 2010, 24(11): 1631-1647.

[13]楊敏, 艾廷華, 周啟. 顧及道路目標stroke特征保持的路網自動綜合方法[J]. 測繪學報, 2013, 42(4): 581-587, 594.

YANG Min, AI Tinghua, ZHOU Qi. A Method of Road Network Generalization Considering Stroke Properties of Road Object[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 581-587, 594.

[14]劉彩鳳. 基于路劃功能的城市道路主干網選取方法[D]. 成都: 西南交通大學, 2010. LIU Caifeng. Stroke Function-based Approach to Extracting Backbone of Urban Road Network[D]. Chengdu: Southwest Jiaotong University, 2010.

[15]徐柱, 劉彩鳳, 張紅, 等. 基于路劃網絡功能評價的道路選取方法[J]. 測繪學報, 2012, 41(5): 769-776. XU Zhu, LIU Caifeng, ZHANG Hong, et al. Road Selection Based on Evaluation of Stroke Network Functionality[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(5): 769-776.

[16]THOMSON R C, RICHARDSON D E. The Good Continuation Principle of Perceptual Organization Applied to the Generalization of Road Networks[C]∥Proceedings of the 19th International Cartographic Conference. Vancouver: [s.n.], 1999: 1215-1225.

[17]董衛(wèi)華, 郭慶勝, 劉紀平, 等. 道路網示意性地圖的漸進式綜合研究[J]. 武漢大學學報(信息科學版), 2007, 32(9): 829-832, 837. DONG Weihua, GUO Qingsheng, LIU Jiping, et al. Progressive Generalization Research of Schematic Road Network Maps[J]. Geomatics and Information Science of Wuhan University, 2007, 32(9): 829-832, 837.

[18]朱洪栓. 基于GIS的河南省公路交通網絡分形研究[D]. 開封: 河南大學, 2008.

ZHU Hongshuan. Study on Fractal Properties of Highway Network in Henan Province Based on GIS[D]. Kaifeng: Henan University, 2008.

[19]李雯靜, 毋河海. 地圖綜合中的地圖目標自相似性分形衰減研究[J]. 測繪科學, 2005, 30(3): 21-23.

LI Wenjing, WU Hehai. Fractal Attenuation Analysis of Cartographic Object on Cartography Generalization[J]. Science of Surveying and Mapping, 2005, 30(3): 21-23.

[20]陳杰. 矢量地圖信息定量度量方法研究[D]. 長沙: 中南大學, 2009.

CHEN Jie. The Methods of Quantitative Measurement of Geospatial Information in Vector Map[D]. Changsha: Central South University, 2009.

(責任編輯：張艷玲)

A Schematic Method Based on the Integration of Stroke Construction and Displacement for Road Network

FU Zhongliang,WENG Baofeng,HU Yulong

School of Remote Sensing and Information Engineering,Wuhan University,Wuhan 430079,China

In current map schematization methods, the degree of simplification is not enough, the length of information is not considered, and time efficiency is low. This study aims to track these problems and a schematic method based on the integration of stroke construction and displacement for road network is proposed.The method constructs strokes for road network, at the same time to make displacement and topology check. Simultaneously, this study uses similar fractal dimension to quantitatively compare and evaluate the effectiveness of different schematic methods. The experimental results indicated that the new method takes into account the original alignment and makes the process simply. The method has more effective in time and reduces topological confliction problem to maintain topological consistency and balance the road network. Finally, the schematic map has great clarity and well-preserved map recognition.

road network; schematization; stroke construction; displacement; similar fractal dimension

FU Zhongliang(1965—)，male, PhD, professor, PhD supervisor，majors in image processing, pattern recognition, GIS engineering.

WENG Baofeng

付仲良，翁寶鳳，胡玉龍.Stroke構造、移位一體化的道路網示意化方法[J].測繪學報，2016,45(9)：1115-1121.

10.11947/j.AGCS.2016.20160080.

FU Zhongliang, WENG Baofeng, HU Yulong.A Schematic Method Based on the Integration of Stroke Construction and Displacement for Road Network[J]. Acta Geodaetica et Cartographica Sinica,2016,45(9):1115-1121. DOI:10.11947/j.AGCS.2016.20160080.

P208

A

1001-1595(2016)09-1115-07

2016-03-01

付仲良(1965—)，男，博士，教授，博士生導師，研究方向為圖像處理、模式識別、GIS工程等。

E-mail： fuzhl@263.net

翁寶鳳

E-mail： raince_5617@qq.com

修回日期： 2016-06-17