2. 四川省第二测绘地理信息工程院，四川 成都 100017
2. The Second Surverying, Mapping and Geoinformation Engineering Institute of Sichuan Province, Chengdu 100017, China
1 引 言
自发地理信息(volunteered geographic information，VGI)是由非专业志愿者参与创建及分享的地理信息新范式，近几年随着Web2.0、GPS、位置导航服务(LBS)等软硬件技术的发展，逐渐成为一种重要的地理信息源[1, 2]。该数据可为城市发展格局、社会经济结构、社会行为心理、环境监测等领域开展定量化研究提供丰富的数据资料，在公众地理信息服务、数据集成与知识发现、室内外导航领域已经涌现出大量的研究案例[3, 4]。网络环境下，VGI数据的多尺度可视化是当前面临的重要课题。一方面，这种由非专业人员采集上传的数据数量巨大，缺乏层次化组织与尺度信息；另一方面，VGI数据的互联网“基因” 提出了用户参与交互及在线实时响应的新需求，对传统的尺度变换技术提出新挑战。以VGI数据的重要内容城市设施兴趣点(points of interest,POI)为例(如餐馆、商店、银行等)，集成POI主题数据与道路、街区等背景参考数据的混搭式地图应用(map-based mashup)已经成为主流地理信息平台(如Google Map、OpenStreetMap)的重要服务内容，但是由于缺乏适宜的多尺度可视化策略，随着显示比例尺的变小符号图形间出现严重的拥挤、压盖等冲突现象(如图 1)，严重影响用户的认知过程。
 |
| 图 1 Google Map上POI目标多比例尺表达 Fig. 1 Multi-scale visualization of POI in Google map |
随着社交网络、开放式自发地理信息平台的发展，类似POI数据的可视化问题成为泛在信息领域的研究热点。在计算机视觉领域，采用实时过滤、抽样等手段来缓解这种小尺寸空间与大数据表达间的矛盾[5, 6]。类似方法更多地关注于数据量的压缩，容易丢失数据内在尺度特征[7]。在GIS领域，相关学者将传统的尺度变换技术与网络环境相结合提出在线式综合(on-the-fly generalization)策略[8]，即在初级尺度数据基础上，通过实时综合输出符合显示比例尺的表达数据。具体方法如图 2所示，包括：①内容选取，减少目标表达数量；②结构化简，通过聚合、移位等操作解决表达冲突。如文献[9]依据POI符号尺寸及距离关系构建冲突树，将重叠目标组合表达为单个聚合符号，以注记或符号大小表达目标数量信息；文献[10]在同类型POI目标聚合的基础上，进一步通过移位操作解决符号表达冲突；文献[11]将POI点群组织为四叉树结构，利用其空间上的层次剖分特性构建适于多种综合操作的算法。从实现方式上看，上述研究侧重于设计适合移动客户端实时综合处理的方法模型，强调算法的低复杂度，难以兼顾多尺度表达的高质量；从实施效果上看，单一的选取或化简操作难以完全解决表达冲突问题，需要多种措施组合实施。
基于上述分析，本研究提出一种面向自发地理信息POI数据多尺度表达的在线综合策略，基本思路是：①服务器端对POI数据进行多层次结构化组织预处理，建立尺度索引和空间索引；②客户端按显示比例尺及范围检索选取POI目标，同时实施移位操作解决符号化后存在的局部冲突现 象。该方法将POI目标选取与冲突移位两种操作相集成，针对服务器/客户端机制特点进行优化配置，与已有方法相比在线响应更快、多尺度表达质量更高。下文首先结合已有理论方法对POI数据多尺度表达策略进行分析，提出本研究的技术路线，然后构建具体的模型算法，并结合实例分析讨论。 2 POI数据多尺度表达策略分析
在地学领域，尺度概念是指研究对象在空间维及时间维上的延展范围，具体到GIS领域则通常由比例尺替代，即小尺度对应大比例尺，大尺度对应小比例尺。从数据组织的角度看，数字技术环境下实现空间数据多尺度表达的方式包括两种[12]：①多级尺度显式存储，通过离线式综合预先获得同一区域多套比例尺版本数据，应用中直接调取尺度匹配的数据集；②在线综合动态生成，对初级尺度数据实时综合得到符合显示比例尺的数据。第一种方式是目前普遍采用的方法，较多地应用在由居民地、道路、水系等基础框架要素构成的背景参考数据。相比较，用户自发的POI数据本身来源多样、更新频繁，应用中通常作为前景主题数据而强调与用户间的交互，需要通过在线综合的方式实现多尺度表达。
与离线式综合相比，在线式综合强调过程实时性，可采用两种策略：一是在客户端直接实施综合处理，要求综合模型及算法简单高效，如目标选取、曲线Douglas-Peucker化简等；二是服务器端对数据进行多层次结构化组织预处理，如曲线结构BLG树[13]、多边形剖分结构GAP树[14]，在线表达时直接导出尺度对应层次的数据内容。前一种策略受限于算法低复杂度要求，尤其是移动客户端计算资源有限，导致综合质量难以保证；后一种策略可以利用服务器资源进行充分的数据分析与综合决策，应用中响应更快，但是难以兼顾客户端软硬件可视化环境，缺乏灵活性。两种方式各具优劣，实际应用中需依据具体需求配合使用。具体到POI数据，综合处理涉及目标选取、冲突移位等多种操作。在服务器端综合考虑语义分类、空间结构等上下文信息，评估POI目标间的重要性关系并构建层次化结构模型；在此基础上，客户端按显示比例尺导出对应层次POI目标，并结合屏幕尺寸、符号化样式等可视化环境实施冲突探测及移位处理。 3 服务器端POI数据多层次结构化组织 3.1 层次化模型构建
空间数据层次化描述是依据重要性关系进行目标有序化组织的过程，可通过记录数据综合的中间状态实现。如曲线结构BLG树建立在Douglas-Peucker算法化简曲线节点的基础上，多边形剖分结构GAP树记录的是多边形逐级合并的逆过程，河网层次化结构可以通过目标层次的选取和几何层次的化简构建得到[15]。对于POI数据，其层次化结构表现为个体POI目标在空间语义特征表达上的重要性差异，可基于POI点群 的结构化选取进行层次化组织。目前，针对点群目标的结构化选取提出了多种方法[16, 17, 18, 19, 20, 21]。其中，文献[17]提出的基于Voronoi 图动态重建多次抽样删除的方法，能够有效顾及点群的空间分布特征与语义信息，可操作性强，同时也符合层次化组织的需求。基于该思想，本研究提出一种多层线性复合结构的POI数据层次化模型，基本过程如下：
步骤1：对POI目标集合P0{o1，o2，…，on }按坐标点构建Voronoi图，初始化抽样提取次数t=1。
步骤2: 实施第t次抽样提取：
步骤2-1: 针对每个目标oi∈P0按式(1)计算重要性值pi。其中ρi=1/S，S为oi所在Voronoi多边形面积；vi代表oi语义重要性值，需要综合考虑POI目标的类型、等级信息及用户需求确定
步骤2-2: 按重要性值由小到大提取POI目标，并按次序组织为单层线性结构，同时动态更新P0及 Voronoi图模型。其中，每提取一个目标则暂时保留其周围一阶邻近的其他目标，如图 3所示。
 |
| 图 3 POI目标单次抽样提取过程示意图 Fig. 3 Resample extraction of POI in one time |
步骤3: 若保留POI数量比例大于设定阈值(如0.1)，重复步骤2实施t+1次抽样提取；否则将余下POI执行步骤2-1后，直接按重要性值由小到大组织为单层线性结构。
完成上述步骤后，将单层线性结构按抽样提取次序垂直连接组织(如图 4所示)，得到呈多层线性复合结构的POI层次化模型。从重要性关系分析，纵向从上到下不同单层结构POI重要性递增，横向由左到右单层结构内POI重要性递增，其中纵向差异大于横向差异。特定比例尺下确定目标表达数量后，即可基于该层次化模型按重要性排序派生出对应的POI目标。
 |
| 图 4 呈多层线性复合结构的POI数据层次化模型 Fig. 4 Organization of POI in multi-layers structure |
为提高多尺度数据组织效率，在层次化模型基础上分别构建空间索引和尺度索引：空间索引可采用四叉树结构对POI目标分布空间进行逐层划分组织建立；尺度索引定义为POI目标资格显示比例尺的线性排序结构。多比例尺表达中，要素目标从“不显示”到“显示”的临界比例尺称为该目标的资格显示比例尺。综合选取中，通常采用开方根模型根据前后比例尺关系确定目标选取数量[22]。反之，每个目标也可以依据其重要性排序位置通过开方根模型反推得到对应的资格显示比例尺。实际应用中，没有必要以单个POI为单元设置资格显示比例尺，可以认为单层线性结构内的POI资格显示比例尺相同。假设POI数据原始比例尺分母为M0，单层线性结构按重要性排序分别为L1、L2、…、LK，对应POI数量为N1、N2、…、NK，则Lt包含POI的资格显示比例尺分母 M(Lt)可由下式求得
值得注意的是，与传统的纸质地图相比较，Web地图由于可视化环境(如符号颜色尺寸、屏幕分辨率、阅读方式等)的不同，适宜的载负量可能有所差异[23, 24]。最可靠的方式是通过计算客户端屏幕的载负量确定POI的选取数量，但是这种方法需要进行繁琐的统计分析工作，同时选取数量的自动化计算存在一定困难。因此，本文在传统开方根模型基础上增加调整系数，面向不同类型客户端配置定制多套资格显示比例尺计算方案。
基于上述层次化模型，POI数据的多尺度组织表现为检索过程P= query(R，M)，R为当前显示范围，M为显示比例尺分母，P为对应导出 的POI目标集。如图 5所示，首先根据R获得对应四叉树节点(1000，1001，1010，1011)下的目标集P′，然后比较P′中每个目标oi的资格显示比例尺分母Mj与M的大小关系，如果Mj<M，则oi∈P。
 |
| 图 5 基于层次化模型的POI目标检索示意图 Fig. 5 The process of POI retrieval based on hierarchical model |
客户端根据当前显示比例尺及表达范围获得POI目标后，符号化表达时局部区域仍可能出现符号图形的冲突现象，需要进一步实施移位处理。已有移位方法[25, 26]大多采用优化技术或迭代方式经过复杂的空间关系分析获得最优方案，但是应用到客户端难以满足实时处理的需求。因此，本研究采用一种线性的启发式移位方法。基本思想是：按重要性排序目标集P={o1，o2，…，om}，依次探测目标oi(1<i<m+1)与排序靠前的目标{o1，o2，…，oi-1 }是否存在冲突现象，若存在冲突则对oi实施移位操作，否则直接探测下一个目标。其中，两个POI目标是否表达冲突可以通过对应符号图形的最小外接矩形是否重叠进行判断。oi移位操作包括以下两个基本步骤：
(1) 建立移位候选位置集。每个与oi冲突的目标提供8个移位候选区域，初步得到oi移位的候选位置集E{e1，e2，…，em }。如图 6(a)所示，o4与o1冲突，o1周围8方向邻近区域作为o4移位的候选位置。进一步，剔除E中与{o1，o2，…，oi-1 }中任一目标冲突的候选位置，如图 6(b)中虚线表达区域为目标o4最终的移位候选位置集。
 |
| 图 6 移位候选位置分析 Fig. 6 The candidate positions to displace |
(2) 最佳移位位置决策。采用约束条件下的移位距离最小原则进行最佳移位位置决策。约束条件包括：① 距离约束，d<=n·l，d表示oi移位前后坐标点的距离，l表示oi符号图形最小外接矩形长边的长度，n表示倍数关系；②方位约束，θ<φ，θ表示oi移位前后坐标点与任一相冲突的目标坐标点形成的夹角，φ为设置的阈值。对候选集E中符合上述约束条件的候选位置按照移位距离最小原则确定最佳移位位置。图 7展示了目标o4最佳移位位置决策过程，约束参数设置为n=5，φ=90°。
 |
| 图 7 最佳移位位置决策 Fig. 7 Determination of the best displacement position |
上述移位算法虽然不能确保获得总体最优解，但在大多数情况下都能得到较为合理的结果，同时算法执行的时间复杂度为O(n)，满足实时性需求。从可视化空间冲突解决上看，移位操作 属于微调性质，其实施效果首先取决于目标选取相关的层次化模型及选取数量取值是否合理。由于后者主要考虑整体上的空间分布特征、语义结构关系等，少数区域仍可能存在目标分布过于密集的情况，仅通过移位难以彻底解决符号冲突问题，需要结合目标聚合等其他操作，相关方法可参见文献[9]。 5 应用分析
为了验证上述方法，本研究基于B/S架构搭建一个面向POI数据可视化的混搭式Web GIS应用原型系统。试验数据来自于自发地理信息数据源OpenStreetMap(http://www.openstreetmap.org)，包括底图参考层的基础地理框架数据和前景主题POI数据。试验环境为：服务器CPU主频2.66 GHz、内存2 GB、Ubuntu 64位操作系统，使用PostGIS作为空间数据引擎，分别利用Mapnik和Mod_tile进行背景底图渲染和切片，背景底图数据涵盖16个比例尺级别；浏览器采用Google Chrome，利用 OpenLayers JavaScript库构建Web可视化客户端。
下面以银行ATM 机POI数据为例介绍相关的试验效果。图 8是深圳市银行ATM点的分布图，目标数量为1654个，空间分布上在西南侧形成显著的带状密集分布区域。考虑到背景底图数据的比例尺级别划分及采用的符号化形式，从第12级比例尺(1∶6万)开始显示POI目标。针对图 8中的矩形区域，在第12级比例尺下所有ATM目标的可视化表达效果如图 9(a)所示，存在大量的压盖拥挤现象。实施上文提出的在线综合策略后，在第12级(1∶6万)、13级(1∶3万)、14级(1∶1.5万)比例尺下的，表达效果分别如图 9(b)、(c)、(d)所示。图 10对比同一比例尺在线综合处理前后的POI目标的表达效果。从效果上看，可以发现目标间的空间冲突现象基本消失，随着比例尺变大目标表达逐渐详细，并且整体上保持了ATM点空间分布上的疏密特征，符合认知基本规律。响应时间上，12～14级比例尺可视化显示的平均耗时分别为160.3 ms、167.8 ms、179.6 ms，与单纯调度显示背景底图数据耗时(153.7 ms)基本一致，表明随着比例尺的缩放POI目标的多尺度表达满足在线实时需求。
 |
| 图 8 深圳市银行ATM点分布图 Fig. 8 The distribution of ATM objects in Shenzhen city |
 |
| 图 9 实施在线综合处理的ATM目标多比例尺表达 Fig. 9 Multi-scale visualization of ATM objects after applying the real-time generalization |
 |
| 图 10 在线综合处理前后ATM目标可视化对比图(比例尺1∶1.5万) Fig. 10 Visualization of ATM objects in different real-time generalization stages(1∶15 000) |
本研究针对VGI类型的城市设施POI数据多比例尺可视化问题，提出了服务器端多层次结构化组织与客户端冲突移位处理相结合的在线式综合策略。试验表明该方法满足实时性需求的同时，也能够顾及数据自身的空间分布特征及终端可视化环境特点，达到较好的多尺度表达效果。同时，服务器端构建的多层次结构化模型也可作为支持POI数据渐进式传输的支撑数据结构。下一步研究工作：①本研究目前侧重于同一类型体系内(如银行网点)POI目标的多尺度表达，如何处理多种类型混合的POI目标(如餐馆与停车场)还需要进一步探讨，例如不同类型POI目标间的语义重要值配置问题，可引入IT领域的个性化推荐技术对用户特点及历史信息进行追踪分析，从而实现语义重要性值得自适应调整和个性化的POI信息可视化效果;②不同比例尺段侧重不同层次POI信息的表达，如小比例尺段关注宏观分布范围和分布密度差异、中比例尺段侧重局部分布结构特征、大比例尺段需要表达目标具体位置及注记信息，需要将不同层次信息相结合，在大比例尺跨度可视化方面进行扩展。
| [1] | GOODCHILD M F. Citizens as Sensors: the World of Volunteered Geography[J]. GeoJournal, 2007, 69(4): 211-221. |
| [2] | LI Deren,SHAO Zhenfeng. New Era of GIS[J].Scientia Sinica Informationis,2009,39(6):579-587.(李德仁, 邵振峰. 论新地理信息时代[J]. 中国科学F辑, 2009, 39(6): 579-587.) |
| [3] | MUMMIDI L, KRUMM J. Discovering Points of Interest from Users' Map Annotations[EB/OL].[2010-01-28]. http://www.freepatentsonline.com/y2010/0023259.html. |
| [4] | GOETZ M.Using Crowdsourced Indoor Geodata for the Creation of a Three-dimensional Indoor Routing Web Application[J], Future Internet, 2012, 4: 575-591. |
| [5] | HUANG Haosheng, GEORG G. A Technical Survey on Decluttering of Icons in Online Map-Based Mashups[C]//Proceedings of Online Maps with APIs and WebServices.Berlin:Springer, 2012:157-175. |
| [6] | DAS S A, LEE H, GONZALEZ H, et al. Efficient Spatial Sampling of Large Geographical Tables[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.[S.l.]:ACM, 2012:193-204. |
| [7] | KORPI J, AHONEN-RAINIO P. Clutter Reduction Methods for Point Symbols in Map Mashups[J]. The Cartographic Journal, 2013, 50(3): 257-265. |
| [8] | WEIBEL R, BURGHARDT D. Generalization On-the-Fly[C]//Proceedings of Encyclopedia of GIS.New York: Springer, 2008:339-344. |
| [9] | BEREUTER P, WEIBEL R. Real-time Generalization of Point Data in Mobile and Web Mapping Using Quadtrees[J]. Cartography and Geographic Information Science, 2013, 40(4):1-11. |
| [10] | KOVANEN J, SARJAKOSKI L T. Sequential Displacement and Grouping of Point Symbols in a Mobile Context[J]. Journal of Location Based Services, 2013, 7(2):1-19. |
| [11] | STEFANO B, CHITTARO L. Decluttering of Icons Based on Aggregation in Mobile Maps[C]//Proceedings of Map-based Mobile Services. Berlin: Springer, 2008:13-32. |
| [12] | AI Tinghua, CHENG Jianguo. Key Issues of Multi-Scale Representation of Spatial Data[J]. Geomatics and Information Science of Wuhan University, 2005, 30(5): 377-382. (艾廷华, 成建国. 对空间数据多尺度表达有关问题的思考[J]. 武汉大学学报: 信息科学版, 2005, 30(5): 377-382.) |
| [13] | VAN OOSTEROM P.Reactive Data Structure for Geographic Information Systems[M].Oxford: Oxford University Press, 1994. |
| [14] | VAN OOSTEROM P. Variable-Scale Topological Data Structures Suitable for Progressive Data Transfer: The GAP-Face Tree and GAP-Edge Forest[J]. Cartography and Geographic Information Science, 2005, 32 (4): 331-346. |
| [15] | AI Bo, AI Tinghua, TANG Xinming. Progressive Transmission of River Network[J]. Geomatics and Information Science of Wuhan University, 2010,35(1): 51-54.(艾波, 艾廷华, 唐新明. 矢量河网数据的渐进式传输[J]. 武汉大学学报: 信息科学版, 2010,35(1): 51-54.) |
| [16] | WU Hehai. Principle of Convex Hull and Its Application in Generalization of Grouped Point Objects[J]. Engineering of Surveying and Mapping, 1997, 6(1):1-6.(毋河海. 凸壳原理在点群目标综合中的应用[J]. 测绘工程, 1997, 6(1):1-6.) |
| [17] | AI Tinghua, LIU Yaolin. A Method of Point Clouster Simplification with Spatial Distribution Properties Preserved[J]. Acta Geodaetica et Cartographica Sinica, 2002, 31(2): 175-181.(艾廷华, 刘耀林. 保持空间分布特征的群点化简方法[J]. 测绘学报, 2002, 31(2): 175-181.) |
| [18] | DENG Hongyan, WU Fang, QIAN Haizhong, et al. A Model of Point Cluster Selection Based on Genetic Algorithms[J]. Journal of Image and Graphics, 2003, 8(8):970-975.(邓红艳, 武芳, 钱海忠,等. 基于遗传算法的点群目标选取模型[J]. 中国图象图形学报, 2003, 8(8):970-975.) |
| [19] | CAI Yongxiang, GUO Qingsheng. Points Group Generalization Based on Konhonen[J]. Geomatics and Information Science of Wuhan University, 2007, 32(7):626-629. (蔡永香, 郭庆胜. 基于Kohonen网络的点群综合研究[J]. 武汉大学学报:信息科学版, 2007, 32(7):626-629.) |
| [20] | LI Wenjing, LIN Zhiyong, LONG Yi. Application of Rough Set Idea to Points Objects GIS Generalization[J]. Geomatics and Information Science of Wuhan University, 2008, 33(9): 896-899.(李雯静, 林志勇, 龙毅. 粗集分类思想在GIS点群综合中的应用[J]. 武汉大学学报: 信息科学版, 2008, 33(9): 896-899.) |
| [21] | YAN H, WEIBEL R. An Algorithm for Point Cluster Generalization Based on the Voronoi Diagram[J]. Computers and Geosciences, 2008, 34(8): 939-954. |
| [22] | TOPFER F, PLLEWIZER W. The Principles of Selection: a Means of Cartographic Generalization[J]. The Cartographic Journal, 1966, 3(1):10-16. |
| [23] | JIANG Nan, CAO Yani, SUN Qinghui, et al. Exploration of Two-peak Changing Law of Basic Electronic Map Load[J]. Acta Geodaetica et Cartographica Sinica, 2014, 43(3): 306-313.(江南, 曹亚妮, 孙庆辉, 等.双峰型基础电子地图载负量变化规律的探究[J]. 测绘学报, 2014, 43(3): 306-313.) |
| [24] | TAO Lianhui, CHEN Yanwu, XIAO Chengcai. Research on Multi-Scale Display and Map Loading of Navigation Electronic Map[J]. Geomatics World, 2012, 9(5): 46-50.(陶连会, 陈艳武, 肖成才. 导航电子地图多尺度显示与载负量的研究[J]. 地理信息世界, 2012, 9(5): 46-50.) |
| [25] | BADER M, BARRAULT M, WEIBEL R. Building Displacement Over a Ductile Truss[J]. International Journal of Geographical Information Science, 2005, 19(8-9): 915-936. |
| [26] | WU Fang, HOU Xuan, QIAN Haizhong, et al. A Model for Road Network Displacement in Automated Map Generalization[J].Acta Geodaetica et Cartographica Sinica, 2005, 34(3): 262-268.(武芳, 侯璇, 钱海忠, 等. 自动制图综合中的线目标位移模型[J]. 测绘学报, 2005, 34(3): 262-268.) |