2. 新疆维吾尔自治区建筑设计研究院，新疆 乌鲁木齐 830002
2. Xinjiang Architectural Design Institute,Urumqi 830002,China
1 引 言
在示意性网络地图设计中，舍弃与地图主题无关的地图要素，忽略地图要素位置精确度，对网络线性要素的形状进行简化，由此能获得更加清晰、简单的网络要素表达。伦敦地铁图(图 1)是示意性网络地图的典范，它的设计在简化网络形状的同时保留了网络的拓扑信息，提高了用户的识图效率，得到公众的认可。一些心理学研究表明[1, 2]，利用示意图能够更快、更准确地获取所需要的信息。文献[3]认为示意性地图的抽象性与人类空间认知所构建的心像地图抽象化特征一致，示意化表达便于识别和理解。目前示意图已广泛应用于各领域，如表示公共交通网络、煤气管线以及电力网[4]。
一些研究通过对伦敦地铁图设计的分析[5, 6]，指出示意图之所以能够提供清晰表达的原因主要有两个方面：以单根地铁线作为基本单元，将简化后线方向设计成45°或者90°方向；改变地图密度分布将拥挤区域放大。第一个方面通过以单根地铁线为示意基本单元保证了识图效率并且提高清晰度；第二个方面改善了示意图整体的清晰度。现实中的示意性网络地图的设计顾及了这两个方面，然而当前的网络示意地图制作主要由制图员采用制图软件绘制的半自动化模式，这是一个耗时费力的过程,而且示意化效果主要依赖于制图员的专业技能以及审美观，自动生成示意性网络地图已经被很多学者所关注。在当前的自动示意化方法中，一些方法[7, 8, 9, 10, 11]已经考虑通过最小化示意结果总长度或者通过可控的增大地图上拥挤区域从而达到改善示意化结果图清晰度。然而对于第一个方面，现有自动示意方法[7, 8, 9, 10, 11, 12, 13, 14, 15, 16]的线形状简化过程需要人工干预而导致自动化程度较低，或者以自动化方式完全忽略线的原始形状而降低了地图认知以及结果图简化度和清晰度。因此本文研究目的是提高示意性网络地图线形状简化方法的自动化程度，并保证其具有良好的地图认知和清晰度。
|
| 图 1 伦敦地铁图 Fig. 1 London tube map |
作为示意网络地图最基本的设计原则之一，线形状简化是结果图清晰度的关键，因此线形状简化方法至关重要。在现有的自动示意方法中可以分为两类，本节将对这两类方法进行分析。
第一类方法在线形状简化过程中并不考虑线的原始形状。文献[13]提出的自动化示意化方法，道路网络地图中节点位置不移动，通过二折或者三折的折线连接节点，其中折线上各段的方向归为水平、竖直或者对角线45°斜方向，如图 2所示。通过二折或者三折的折线连接节点也许会降低示意化结果的简化度和清晰度，尤其对于距离较近的节点。在一些自动化生成示意性地铁图的方法中[8, 9, 10]，地铁站点之间直接通过水平、竖直或者45°斜方向的线段相连接，此方法只用于地铁图的制作。对于这类未考虑线原始形状的线形状简化方法，尽管有较高的简便性，然而如果结果图与原始形状存在较大的差别，容易使用户产生迷惑，不适用于其他类型的网络型地图，例如道路网。
在一些考虑线原始图形的自动化示意化方法中[12, 14, 15]，线形状简化通过Douglas-Peuker算法来实现，该算法已经广泛应用于制图综合中[17]。该算法的基本思路是通过直线连接曲线的首尾点，求曲线上所有点与该直线距离，找出最大距离并与给定阈值相比，如果大于给定阈值，则从该点将曲线分成两部分，然后对这两部分再重复该方法；如果小于给定阈值，则去除这条曲线上所有中间点。然而根据最大距离给出合理的阈值判断曲线是否再分段，需要人工干预方式进行。此外，这些方法在示意化过程中都是以网络弧段为基本单元，即在线简化过程中分别考虑各个独立弧段，这种思想并不符合人们在路径认知中的整体性，事实上通常用户往往将有着相同路名或视觉连续性的几个弧段看作一个整体来进行路线认知[18]，而以弧段为单元的示意化结果无法保证路径在视觉上的连续性，以至于降低了地图认知的效率。为了使示意化结果具有更高的清晰度和认知度，文献[16]提出基于路划(stroke)的自动化示意化方法，其主要思想为通过属性一致性或几何连通性组织网络弧段从而构造路划，以路划为基本单元进行形状简化并最终生成示意图。图 3是根据几何连通性[19]进行构造路划的例子,其中9条弧段构造成4条路划。在文献[16]方法中，首先将曲线分段，然后将每段投影到水平、竖直以及对角线方向上。在曲线分段中主要是通过两种方式进行，第一种是通过方向变化(direction change)，即判断曲线上每个点相连的两条线段的偏斜角(deflection angle)是否超过阈值，如果超过将该点视为分段点，曲线分段数将取决于分段点的个数。然而该方法极易受到曲线上较小起伏的影响，降低了结果的简化度和清晰度。第二种方法是通过方向偏离(direction distortion)(图 4)，其思想类似于Douglas-Peuker算法，如果在与曲线首尾连线垂直距离最大的点上的方向偏离(任意一个)大于给定阈值，则在该点将曲线分成两个次级路划(sub-stroke),然后对这两个次级路划重复该方法，以迭代的方式进行直到没有方向偏离大于给定阈值。
|
| 图 4 根据方向偏差进行路划分段 Fig. 4 Formation of sub-strokes by direction distortion |
上述顾及线原始图形的简化方法中[12, 14, 15, 16]，由于对确定曲线分段点的阈值设定并未进行深入讨论，因此在线形状简化过程中仍需人工干预或者经验来设定阈值以保证结果图的简化度,从而降低了简化过程的自动化程度。事实上阈值的大小对示意化图的认知度和清晰度有着至关重要的作用，过大的阈值无法保证视觉上曲线的自然转折从而降低了认知度，而过小的阈值将导致单条线示意化结果上存在过多的方向转折，从而降低了结果的简化度和清晰度，因此合理确定阈值对于自动生成示意网络地图是十分重要的。
3 线形简化方法本节将根据示意网络地图设计特点对合理设定线形状简化过程中所需的曲线分段阈值进行讨论，并提出相应的线形简化方法。对于Douglas-Peuker算法，根据最大距离很难给出合理的阈值来判断曲线是否需要分段，因此本文将通过曲线上相连线段的方向变化来探讨合理设定曲线分段阈值。对已实用的人工设计的示意性网络地图(例如伦敦地铁图)或现有的自动化示意化方法来说，角度简化有着统一的标准，即将简化后线的方向归为水平、竖直或者对角线方向总共8个方向(图 5)。而判断归属方向主要依据与这8个方向的夹角，例如曲线分段后，某一段方向为15°，相对于其他7个方向，与水平0°方向夹角最小，因此将该段方向归为0°。根据这个设计特点，对于简化后曲线上相连的两段，如果其偏斜角大于22.5°，这两段将被归于两个不同的方向(图 6)，也就是说22.5°是方向变化的临界值，本文提出将22.5°作为阈值用于曲线分段以提高线形状简化过程的自动化程度。根据这个给定的阈值，本文使用文献[16]方法中的基于方向偏离(direction distortion)程度的线形状简化方式，相对于基于方向变化(direction change)的简化方式来说，这种方式不易受到曲线上较小起伏的影响。
|
| 图 5 网络示意的角度简化8个方向 Fig. 5 Eight directions in network schematization |
|
| 图 6 对于偏斜角大于22.5°的示意化结果 Fig. 6 Schematized results for the deflection angle greater than 22.5° |
然而仅使用22.5°作为曲线分段的阈值仍然无法保证线形状的高简化度，原因在于如果一些曲线平滑度差，即存在较多较小的起伏(图 7(a))，以迭代方式进行曲线分段的过程中，如果将存在较多突出起伏的部分作为单独一段，通过方向偏离(direction distortion)程度作为依据判断是否再分段，那么相应的示意化结果在这个部分将存在较多的方向变化(图 7(b))。事实上这些起伏不仅不会提高地图认知，反而会降低示意化结果的简化度和清晰度，降低了认知效率，因此可以被认为是“噪声”。
|
| 图 7 在线形状简化过程中使用阈值为22.5°的示意结果 Fig. 7 Schematized result by the threshold of 22.5°for line shape simplification |
针对这个问题，本文将通过线的平滑去除这些“噪声”,事实上通过平滑方法去除“噪声”已经被广泛地使用在数字图像处理和自动化制图综合中。处理曲线平滑的方法有两类[20]，第一类是在空间域(space domain)中基于曲线上点的坐标进行平滑，常见方法有移动平均(moving averaging)，曲线拟合等；第二类是在频率域通过去除曲线的高频部分从而实现平滑，常见方法有傅里叶转换和小波转换。在这些方法中移动平均方法使用简便，不需要额外根据经验选择合适曲线拟合或者参数，尤其对于处理整个网络更为便利，因而本文使用该方法去除曲线“噪声”。移动平滑方法是由文献[21]提出并应用于三维数据，其基本思想是在根据曲线上某一个点的位置与该点相邻点的点位确定该点平滑后的位置，基本公式如下
式中，p′i和pi分别为曲线上第i个点平滑后和平滑前的位置；k表示平滑窗口的大小，如果k=1，意味着第i个点平滑后的位置仅考虑该点和该点前后相邻的两个点(pi－1和pi+1)的点位，在平滑过程中曲线首位点位置不变。
图 8(a)为图 7(a)平滑后的结果，图 8(b)为图 7(b)的示意结果。可以看出图 8(b)比图 7(b)在简化程度上有明显的提高。
|
| 图 8 线平滑后使用22.5°阈值的示意化结果 Fig. 8 Schematized result by the threshold of 22.5 ° after line smoothing |
为验证本文中提出的线形状简化方法的有效性，试验采用真实道路网(图 9)数据生成示意化结果。其中图 9(a)和(b)为两个形状较为典型的道路网络地图，即格网状和发散状，图 9(c)为形状较为复杂的路网。由于文献[16]提出的基于路划(stroke)的交通网络地图自动化示意化更加符合人们对地图的认知，因此本文采纳以路划(stroke)为基本单元的思想进行自动化示意化，使用本文提出的线形状简化方法并结合文献[16]方法中保持网络拓扑关系的算法开展试验。示意化结果见图 10(a)、(b)和(c)。同时为更好地说明该方法能够生成较高清晰度的示意化结果，本文还将由文献[13]提出的方法所生成的结果(图 10(d))与试验结果图 10(c)进行对比分析，原因在于本文所提方法与文献[13]提出方法中的线形状简化过程都无须人工干预确定阈值。由于文献[13]方法的局限性，图 10(d)右边结果图中有一些路径的无法生成示意化结果(见图中较粗线)。
|
| 图 9 道路网原始形状 Fig. 9 Original shape of road networks |
|
| 图 10 示意结果 Fig. 10 Schematized results |
试验评估主要通过比较示意结果的简化度和认知度两个方面展开。试验主要采取问卷方式，邀请40名不同教育背景的志愿者(22名男性和18名女性)通过视觉评估试验对清晰度和对照原形的地图识别能力两个方面进行评分，评分根据简洁程度和识别的难易程度划分5个等级，对应分数分别为1～5分，其中1分为非常不简洁和非常难辨认，5分为非常简洁和极易辨认。在问卷中图 9和图 10的原始路网和示意化结果图以高清打印版本提供给志愿者。最终试验结果对于图 10(a)、(b)和(c)3个结果图的简化度平均分分别为4.8、4.6和4.2，对于图 10(d)的简化度平均分为3.0。对于对照原形的地图认知度，图 10(a)、(b)和(c)3个结果图的平均分数为4.7、4.3和4.1，图 10(d)的认知平均分为4.2。试验结果表明本文所提出的方法生成的结果图由于简化度高，其清晰度明显高于使用文献[13]提出的自动化线形状简化方法生成的结果。在识别方面，4.8、4.3和4.1的分数说明该示意结果基本上不影响地图识别。在线形状简化运算效率方面，对于图 10(a)道路网络数据(141个点和100条弧段)生成时间0.4s，对于图 10(b)道路网络数据(222个点和60条弧段)生成时间0.3s，对于图 10(c)道路网络数据(430个点和110条弧段)生成时间0.8s，试验计算机的中央处理器为3.2GHz和内存为24GB，说明本文所提方法有较高的运算效率。
5 结 论本文提出了一种新的道路网络地图示意的线形状简化方法，其中包括提出将22.5°作为曲线分段的阈值，并结合曲线平滑算法改善示意化结果的简化度和清晰度。本文的线形状简化方法考虑了线原始形状从而保证较好的结果图认知度，相对于现有的此类示意性网络地图生成方法，该方法由于不需要依靠人工干预和经验设定曲线分段阈值，从而具有高自动化程度和易用性，并且有着较高的运算效率。今后研究工作重点是在该示意结果图上有效添加道路网地图的其他内容，例如地标、高架桥等，从而将示意道路网络地图推向实用，此外现有的方法在示意化结果评判方面，主要通过视觉心理等主观性较强的测试[10, 11, 16]进行，使得评判结果缺乏客观性，因此更加客观的评价体系与方法也将成为今后研究工作的要点。
| [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. (艾廷华. 适宜空间认知结果表达的地图形式[J]. 遥感学报, 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. (董卫华, 郭庆胜, 刘纪平, 等. 道路网示意性地图的渐进式综合研究[J]. 武汉大学学报:信息科学版, 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].测绘学报,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. |