遆 鵬,賈洪果,徐 柱,唐 建,肖亮亮

1.西南交通大學(xué)地球科學(xué)與環(huán)境工程學(xué)院,四川成都 610031;2.新疆維吾爾自治區(qū)建筑設(shè)計研究院,新疆烏魯木齊 830002

面向道路網(wǎng)絡(luò)地圖示意化的線形簡化方法

遆 鵬1,賈洪果1,徐 柱1,唐 建2,肖亮亮1

1.西南交通大學(xué)地球科學(xué)與環(huán)境工程學(xué)院,四川成都 610031;2.新疆維吾爾自治區(qū)建筑設(shè)計研究院,新疆烏魯木齊 830002

針對當(dāng)前示意網(wǎng)絡(luò)地圖線形狀簡化方法中存在需要人工干預(yù)或地圖認(rèn)知度低的問題,本文提出自動化程度高并能保證良好地圖認(rèn)知的線形狀簡化方法。該方法通過合理設(shè)定線形狀簡化中所需的閾值以避免人工干預(yù),提高了線形狀簡化過程的自動化程度,并通過在簡化過程中應(yīng)用平滑算法,以減少示意結(jié)果中線對象在方向上的轉(zhuǎn)折數(shù),從而提高了簡化度和清晰度。試驗表明該方法不僅可以生成清晰的示意結(jié)果,并且能夠保證良好的地圖認(rèn)知度。

道路網(wǎng)絡(luò)地圖;自動示意化;線形簡化

1 引 言

在示意性網(wǎng)絡(luò)地圖設(shè)計中,舍棄與地圖主題無關(guān)的地圖要素,忽略地圖要素位置精確度,對網(wǎng)絡(luò)線性要素的形狀進行簡化,由此能獲得更加清晰、簡單的網(wǎng)絡(luò)要素表達。倫敦地鐵圖(圖1)是示意性網(wǎng)絡(luò)地圖的典范,它的設(shè)計在簡化網(wǎng)絡(luò)形狀的同時保留了網(wǎng)絡(luò)的拓?fù)湫畔?提高了用戶的識圖效率,得到公眾的認(rèn)可。一些心理學(xué)研究表明[1-2],利用示意圖能夠更快、更準(zhǔn)確地獲取所需要的信息。文獻[3]認(rèn)為示意性地圖的抽象性與人類空間認(rèn)知所構(gòu)建的心像地圖抽象化特征一致,示意化表達便于識別和理解。目前示意圖已廣泛應(yīng)用于各領(lǐng)域,如表示公共交通網(wǎng)絡(luò)、煤氣管線以及電力網(wǎng)[4]。

一些研究通過對倫敦地鐵圖設(shè)計的分析[5-6],指出示意圖之所以能夠提供清晰表達的原因主要有兩個方面:以單根地鐵線作為基本單元,將簡化后線方向設(shè)計成45°或者90°方向;改變地圖密度分布將擁擠區(qū)域放大。第一個方面通過以單根地鐵線為示意基本單元保證了識圖效率并且提高清晰度;第二個方面改善了示意圖整體的清晰度。現(xiàn)實中的示意性網(wǎng)絡(luò)地圖的設(shè)計顧及了這兩個方面,然而當(dāng)前的網(wǎng)絡(luò)示意地圖制作主要由制圖員采用制圖軟件繪制的半自動化模式,這是一個耗時費力的過程,而且示意化效果主要依賴于制圖員的專業(yè)技能以及審美觀,自動生成示意性網(wǎng)絡(luò)地圖已經(jīng)被很多學(xué)者所關(guān)注。在當(dāng)前的自動示意化方法中,一些方法[7-11]已經(jīng)考慮通過最小化示意結(jié)果總長度或者通過可控的增大地圖上擁擠區(qū)域從而達到改善示意化結(jié)果圖清晰度。然而對于第一個方面,現(xiàn)有自動示意方法[7-16]的線形狀簡化過程需要人工干預(yù)而導(dǎo)致自動化程度較低,或者以自動化方式完全忽略線的原始形狀而降低了地圖認(rèn)知以及結(jié)果圖簡化度和清晰度。因此本文研究目的是提高示意性網(wǎng)絡(luò)地圖線形狀簡化方法的自動化程度,并保證其具有良好的地圖認(rèn)知和清晰度。

2 示意網(wǎng)絡(luò)地圖線形狀簡化方法分析

作為示意網(wǎng)絡(luò)地圖最基本的設(shè)計原則之一,線形狀簡化是結(jié)果圖清晰度的關(guān)鍵,因此線形狀簡化方法至關(guān)重要。在現(xiàn)有的自動示意方法中可以分為兩類,本節(jié)將對這兩類方法進行分析。

第一類方法在線形狀簡化過程中并不考慮線的原始形狀。文獻[13]提出的自動化示意化方法,道路網(wǎng)絡(luò)地圖中節(jié)點位置不移動,通過二折或者三折的折線連接節(jié)點,其中折線上各段的方向歸為水平、豎直或者對角線45°斜方向,如圖2所示。通過二折或者三折的折線連接節(jié)點也許會降低示意化結(jié)果的簡化度和清晰度,尤其對于距離較近的節(jié)點。在一些自動化生成示意性地鐵圖的方法中[8-10],地鐵站點之間直接通過水平、豎直或者45°斜方向的線段相連接,此方法只用于地鐵圖的制作。對于這類未考慮線原始形狀的線形狀簡化方法,盡管有較高的簡便性,然而如果結(jié)果圖與原始形狀存在較大的差別,容易使用戶產(chǎn)生迷惑,不適用于其他類型的網(wǎng)絡(luò)型地圖,例如道路網(wǎng)。

圖2 生成示意化路徑[13]Fig.2 Generation of schematic paths[13]

在一些考慮線原始圖形的自動化示意化方法中[12,14-15],線形狀簡化通過Douglas-Peuker算法來實現(xiàn),該算法已經(jīng)廣泛應(yīng)用于制圖綜合中[17]。該算法的基本思路是通過直線連接曲線的首尾點,求曲線上所有點與該直線距離,找出最大距離并與給定閾值相比,如果大于給定閾值,則從該點將曲線分成兩部分,然后對這兩部分再重復(fù)該方法;如果小于給定閾值,則去除這條曲線上所有中間點。然而根據(jù)最大距離給出合理的閾值判斷曲線是否再分段,需要人工干預(yù)方式進行。此外,這些方法在示意化過程中都是以網(wǎng)絡(luò)弧段為基本單元,即在線簡化過程中分別考慮各個獨立弧段,這種思想并不符合人們在路徑認(rèn)知中的整體性,事實上通常用戶往往將有著相同路名或視覺連續(xù)性的幾個弧段看作一個整體來進行路線認(rèn)知[18],而以弧段為單元的示意化結(jié)果無法保證路徑在視覺上的連續(xù)性,以至于降低了地圖認(rèn)知的效率。為了使示意化結(jié)果具有更高的清晰度和認(rèn)知度,文獻[16]提出基于路劃(stroke)的自動化示意化方法,其主要思想為通過屬性一致性或幾何連通性組織網(wǎng)絡(luò)弧段從而構(gòu)造路劃,以路劃為基本單元進行形狀簡化并最終生成示意圖。圖3是根據(jù)幾何連通性[19]進行構(gòu)造路劃的例子,其中9條弧段構(gòu)造成4條路劃。在文獻[16]方法中,首先將曲線分段,然后將每段投影到水平、豎直以及對角線方向上。在曲線分段中主要是通過兩種方式進行,第一種是通過方向變化(direction change),即判斷曲線上每個點相連的兩條線段的偏斜角(deflection angle)是否超過閾值,如果超過將該點視為分段點,曲線分段數(shù)將取決于分段點的個數(shù)。然而該方法極易受到曲線上較小起伏的影響,降低了結(jié)果的簡化度和清晰度。第二種方法是通過方向偏離(direction distortion)(圖4),其思想類似于Douglas-Peuker算法,如果在與曲線首尾連線垂直距離最大的點上的方向偏離(任意一個)大于給定閾值,則在該點將曲線分成兩個次級路劃(sub-stroke),然后對這兩個次級路劃重復(fù)該方法,以迭代的方式進行直到?jīng)]有方向偏離大于給定閾值。

圖3 基于幾何連通性構(gòu)造路劃[19]Fig.3 Formation of strokes by good continuity principle[19]

圖4 根據(jù)方向偏差進行路劃分段Fig.4 Formation of sub-strokes by direction distortion

上述顧及線原始圖形的簡化方法中[12,14-16],由于對確定曲線分段點的閾值設(shè)定并未進行深入討論,因此在線形狀簡化過程中仍需人工干預(yù)或者經(jīng)驗來設(shè)定閾值以保證結(jié)果圖的簡化度,從而降低了簡化過程的自動化程度。事實上閾值的大小對示意化圖的認(rèn)知度和清晰度有著至關(guān)重要的作用,過大的閾值無法保證視覺上曲線的自然轉(zhuǎn)折從而降低了認(rèn)知度,而過小的閾值將導(dǎo)致單條線示意化結(jié)果上存在過多的方向轉(zhuǎn)折,從而降低了結(jié)果的簡化度和清晰度,因此合理確定閾值對于自動生成示意網(wǎng)絡(luò)地圖是十分重要的。

3 線形簡化方法

本節(jié)將根據(jù)示意網(wǎng)絡(luò)地圖設(shè)計特點對合理設(shè)定線形狀簡化過程中所需的曲線分段閾值進行討論,并提出相應(yīng)的線形簡化方法。對于Douglas-Peuker算法,根據(jù)最大距離很難給出合理的閾值來判斷曲線是否需要分段,因此本文將通過曲線上相連線段的方向變化來探討合理設(shè)定曲線分段閾值。對已實用的人工設(shè)計的示意性網(wǎng)絡(luò)地圖(例如倫敦地鐵圖)或現(xiàn)有的自動化示意化方法來說,角度簡化有著統(tǒng)一的標(biāo)準(zhǔn),即將簡化后線的方向歸為水平、豎直或者對角線方向總共8個方向(圖5)。而判斷歸屬方向主要依據(jù)與這8個方向的夾角,例如曲線分段后,某一段方向為15°,相對于其他7個方向,與水平0°方向夾角最小,因此將該段方向歸為0°。根據(jù)這個設(shè)計特點,對于簡化后曲線上相連的兩段,如果其偏斜角大于22.5°,這兩段將被歸于兩個不同的方向(圖6),也就是說22.5°是方向變化的臨界值,本文提出將22.5°作為閾值用于曲線分段以提高線形狀簡化過程的自動化程度。根據(jù)這個給定的閾值,本文使用文獻[16]方法中的基于方向偏離(direction distortion)程度的線形狀簡化方式,相對于基于方向變化(direction change)的簡化方式來說,這種方式不易受到曲線上較小起伏的影響。

圖5 網(wǎng)絡(luò)示意的角度簡化8個方向Fig.5 Eight directions in network schematization

圖6 對于偏斜角大于22.5°的示意化結(jié)果Fig.6 Schematized results for the deflection angle greater than 22.5°

然而僅使用22.5°作為曲線分段的閾值仍然無法保證線形狀的高簡化度,原因在于如果一些曲線平滑度差,即存在較多較小的起伏(圖7 (a)),以迭代方式進行曲線分段的過程中,如果將存在較多突出起伏的部分作為單獨一段,通過方向偏離(direction distortion)程度作為依據(jù)判斷是否再分段,那么相應(yīng)的示意化結(jié)果在這個部分將存在較多的方向變化(圖7(b))。事實上這些起伏不僅不會提高地圖認(rèn)知,反而會降低示意化結(jié)果的簡化度和清晰度,降低了認(rèn)知效率,因此可以被認(rèn)為是“噪聲”。

圖7 在線形狀簡化過程中使用閾值為22.5°的示意結(jié)果Fig.7 Schematized result by the threshold of 22.5° for line shape simplification

針對這個問題,本文將通過線的平滑去除這些“噪聲”,事實上通過平滑方法去除“噪聲”已經(jīng)被廣泛地使用在數(shù)字圖像處理和自動化制圖綜合中。處理曲線平滑的方法有兩類[20],第一類是在空間域(space domain)中基于曲線上點的坐標(biāo)進行平滑,常見方法有移動平均(moving averaging),曲線擬合等;第二類是在頻率域通過去除曲線的高頻部分從而實現(xiàn)平滑,常見方法有傅里葉轉(zhuǎn)換和小波轉(zhuǎn)換。在這些方法中移動平均方法使用簡便,不需要額外根據(jù)經(jīng)驗選擇合適曲線擬合或者參數(shù),尤其對于處理整個網(wǎng)絡(luò)更為便利,因而本文使用該方法去除曲線“噪聲”。移動平滑方法是由文獻[21]提出并應(yīng)用于三維數(shù)據(jù),其基本思想是在根據(jù)曲線上某一個點的位置與該點相鄰點的點位確定該點平滑后的位置,基本公式如下

式中,p′i和pi分別為曲線上第i個點平滑后和平滑前的位置;k表示平滑窗口的大小,如果k＝1,意味著第i個點平滑后的位置僅考慮該點和該點前后相鄰的兩個點(pi－1和pi＋1)的點位,在平滑過程中曲線首位點位置不變。

圖8(a)為圖7(a)平滑后的結(jié)果,圖8(b)為圖7(b)的示意結(jié)果?？梢钥闯鰣D8(b)比圖7(b)在簡化程度上有明顯的提高。

圖8 線平滑后使用22.5°閾值的示意化結(jié)果Fig.8 Schematized result by the threshold of 22.5° after line smoothing

4 試驗評估

為驗證本文中提出的線形狀簡化方法的有效性,試驗采用真實道路網(wǎng)(圖9)數(shù)據(jù)生成示意化結(jié)果。其中圖9(a)和(b)為兩個形狀較為典型的道路網(wǎng)絡(luò)地圖,即格網(wǎng)狀和發(fā)散狀,圖9(c)為形狀較為復(fù)雜的路網(wǎng)。由于文獻[16]提出的基于路劃(stroke)的交通網(wǎng)絡(luò)地圖自動化示意化更加符合人們對地圖的認(rèn)知,因此本文采納以路劃(stroke)為基本單元的思想進行自動化示意化,使用本文提出的線形狀簡化方法并結(jié)合文獻[16]方法中保持網(wǎng)絡(luò)拓?fù)潢P(guān)系的算法開展試驗。示意化結(jié)果見圖10(a)、(b)和(c)。同時為更好地說明該方法能夠生成較高清晰度的示意化結(jié)果,本文還將由文獻[13]提出的方法所生成的結(jié)果(圖10(d))與試驗結(jié)果圖10(c)進行對比分析,原因在于本文所提方法與文獻[13]提出方法中的線形狀簡化過程都無須人工干預(yù)確定閾值。由于文獻[13]方法的局限性,圖10(d)右邊結(jié)果圖中有一些路徑的無法生成示意化結(jié)果(見圖中較粗線)。

圖9 道路網(wǎng)原始形狀Fig.9 Original shape of road networks

試驗評估主要通過比較示意結(jié)果的簡化度和認(rèn)知度兩個方面展開。試驗主要采取問卷方式,邀請40名不同教育背景的志愿者(22名男性和18名女性)通過視覺評估試驗對清晰度和對照原形的地圖識別能力兩個方面進行評分,評分根據(jù)簡潔程度和識別的難易程度劃分5個等級,對應(yīng)分?jǐn)?shù)分別為1～5分,其中1分為非常不簡潔和非常難辨認(rèn),5分為非常簡潔和極易辨認(rèn)。在問卷中圖9和圖10的原始路網(wǎng)和示意化結(jié)果圖以高清打印版本提供給志愿者。最終試驗結(jié)果對于圖10(a)、(b)和(c)3個結(jié)果圖的簡化度平均分分別為4.8、4.6和4.2,對于圖10(d)的簡化度平均分為3.0。對于對照原形的地圖認(rèn)知度,圖10(a)、(b)和(c)3個結(jié)果圖的平均分?jǐn)?shù)為4.7、4.3和4.1,圖10(d)的認(rèn)知平均分為4.2。試驗結(jié)果表明本文所提出的方法生成的結(jié)果圖由于簡化度高,其清晰度明顯高于使用文獻[13]提出的自動化線形狀簡化方法生成的結(jié)果。在識別方面,4.8、4.3和4.1的分?jǐn)?shù)說明該示意結(jié)果基本上不影響地圖識別。在線形狀簡化運算效率方面,對于圖10(a)道路網(wǎng)絡(luò)數(shù)據(jù)(141個點和100條弧段)生成時間0.4 s,對于圖10(b)道路網(wǎng)絡(luò)數(shù)據(jù)(222個點和60條弧段)生成時間0.3 s,對于圖10(c)道路網(wǎng)絡(luò)數(shù)據(jù)(430個點和110條弧段)生成時間0.8 s,試驗計算機的中央處理器為3.2 GHz和內(nèi)存為24 GB,說明本文所提方法有較高的運算效率。

圖10 示意結(jié)果Fig.10 Schematized results

5 結(jié) 論

本文提出了一種新的道路網(wǎng)絡(luò)地圖示意的線形狀簡化方法,其中包括提出將22.5°作為曲線分段的閾值,并結(jié)合曲線平滑算法改善示意化結(jié)果的簡化度和清晰度。本文的線形狀簡化方法考慮了線原始形狀從而保證較好的結(jié)果圖認(rèn)知度,相對于現(xiàn)有的此類示意性網(wǎng)絡(luò)地圖生成方法,該方法由于不需要依靠人工干預(yù)和經(jīng)驗設(shè)定曲線分段閾值,從而具有高自動化程度和易用性,并且有著較高的運算效率。今后研究工作重點是在該示意結(jié)果圖上有效添加道路網(wǎng)地圖的其他內(nèi)容,例如地標(biāo)、高架橋等,從而將示意道路網(wǎng)絡(luò)地圖推向?qū)嵱?此外現(xiàn)有的方法在示意化結(jié)果評判方面,主要通過視覺心理等主觀性較強的測試[10-11,16]進行,使得評判結(jié)果缺乏客觀性,因此更加客觀的評價體系與方法也將成為今后研究工作的要點。

[1] AGRAWALA M,STOLTE C.Rendering Effective Route Maps:Improving Usability through Generalization[C]∥Proceedings of Association for Computing Machinery SIGGRAPH.[S.l.]:ACM,2001:241-250.

[2] TVERSKY B,LEE P U.Pictorial and Verbal Tools for Conveying Routes[C]∥Proceedings of the International Conference on Spatial Information Theory.London: COSIT,1999:51-64.

[3] AI Tinghua.Maps Adaptable to Represent Spatial Cognition [J].Journal of Remote Sensing,2008,12(2):347-354.(艾廷華.適宜空間認(rèn)知結(jié)果表達的地圖形式[J].遙感學(xué)報,2008,12(2):347-354.)

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

[5] GARLAND K.Mr Beck’s Underground Map[M].Harrow Weald:Capital Transport,1994.

[6] JENNY B.Geometric Distortion of Schematic Network Maps [J].Society of Cartographer Bulletin,2006,40:15-18.

[7] MERRICK D,GUDMUNDSSON J.Increasing the Readability of Graph Drawings with Centrality-based Scaling [C]∥Proceeding of Asia-Pacific Symposium Information Visualization.Tokyo:[s.n.],2006:67-76.

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

[9] 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.

[10] NOELLENBURG 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.

[11] TI P,LI Z L.Generation of Schematic Network Maps with Automated Detection and Enlargement of Congested Areas[J].International Journal of Geographical Information Science,2014,28(3):521-540.

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

[13] CABELLO S,DE BERG M,VAN DIJK S,et al.Schematization of Road Networks[C]∥Proceedings of the Seventeenth Annual Symposium on Computational Geometry.Massachusetts:[s.n.],2001:33-41.

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

[15] 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.(董衛(wèi)華,郭慶勝,劉紀(jì)平,等.道路網(wǎng)示意性地圖的漸進式綜合研究[J].武漢大學(xué)學(xué)報:信息科學(xué)版,2007,32(9):829-832.)

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

[17] HE Jin,FEI Lifan,HUANG Lina,et al.Study on the Method of Indirect Generalization for Contour Lines Based on the 3D Douglas-Peucker Algorithm[J].Acta Geodaetica et Cartographica Sinica,2013,42(3):467-473.(何津,費立凡,黃麗娜,等.三維Douglas-Peucker算法的等高線間接綜合方法研究[J].測繪學(xué)報,2013,42(3): 467-473.)

[18] KLIPPEL A.Conceptualizing Wayfinding and Route Direction Elements[D].Jacobs:Universitat Bremen,2003.

[19] THOMSON R C,RICHARDSON D E.The＇Good Continuity’Principle of Perceptual Organization Applied to the Generalization of Road Networks[C]∥Proceeding of the 19th International Cartographic Conference.Ottawa:[s.n.], 1999:1215-1225.

[20] LI Z L.Algorithm Foundation of Multi-scale Spatial Representation[M].London:CRC Press,2006.

[21] TOBLER W.Numeric Map Generalization[J].Cartographica, 1966,26(1):9-25.

(責(zé)任編輯:宋啟凡)

A Line-shape-simplification Method for Schematization of Road Network Map

Tl Peng1,JlA Hongguo1,XU Zhu1,TANG Jian2,XlAO Liangliang1
1.Faculty of Geosciences and Environmental Engineering,Southwest Jiaotong University,Chengdu 610031,China; 2.Xinjiang Architectural Design lnstitute,Urumqi 830002,China

The line shape simplification plays an important role in the production of schematic network maps.However,in current automated schematization methods,the simplification of line shapes either needs a threshold determined in manual manner so as to decrease the automated degree,or ignore the original line shape so as to reduce the map recognition.This study aims to tracke these problems and an automated method for the line shape simplification is proposed.ln this method,a threshold for the simplication of line shapes was given and the line smoothing was applied to network map in this simplification process in order to improve the simplification degree of the line shapes.The experimental results indicated that the new method is able to automatically generate schematic maps with great clarity and wellpreserved map recognition compared with their original shapes.

road network map;automated schematization;line shape simplification

Tl Peng(1977—),male,PhD,lecturer, majors in digital cartography and geospatial visualization.

JlA Hongguo

P283

A

1001-1595(2014)12-1280-05

國家863計劃(2013AA12A202);國家自然科學(xué)基金(41201475;41471383);教育部新世紀(jì)優(yōu)秀人才支持計劃(NCET-12-0942);高鐵運營安全空間信息技術(shù)教育部創(chuàng)新團隊(lRT13092);四川省地理國情監(jiān)測工程技術(shù)研究中心資助項目(GC201404)

2014-05-09

遆鵬(1977—),男,博士,講師,研究方向為數(shù)字地圖制圖與空間數(shù)據(jù)可視化。

E-mail:peng_ti＠hotmail.com

賈洪果

E-mail:lemon_gg＠hotmail.com

TI Peng,JIA Hongguo,XU Zhu,et al.A Line-shape-simplification Method for Schematization of Road Network Map[J].Acta Geodaetica et Cartographica Sinica,2014,43(12):1280-1284.(遆鵬,賈洪果,徐柱,等.面向道路網(wǎng)絡(luò)地圖示意化的線形簡化方法[J].測繪學(xué)報,2014,43(12):1280-1284.)

10.13485/j.cnki.11-2089.2014.0190

修回日期:2014-08-13