基于OpenStreetMap的地图匹配算法研究
2017-09-05蒋宗礼李娟
蒋宗礼+李娟
摘 要：借助OpenStreetMap （以下简称OSM）开源组织，分析研究了OSM相关的数据结构和使用方法，构建了地图服务系统，为研究地图匹配算法提供了基础。通过研究地图匹配算法，实现了基于几何投影法的地图匹配研究项目，为进行更复杂的地图匹配算法研究提供了依据。
关键词：地图匹配算法；开源地图数据；地图数据服务系统；OpenStreetMap；地图匹配系统
DOIDOI：10.11907/rjdk.171147
中图分类号：TP312
文献标识码：A 文章编号：1672-7800（2017）007-0052-03
0 引言
随着计算机的普及以及地理信息科学的发展，地理信息系统（ Geographic Information System，GIS）得到了广泛应用，在电子导航、交通旅游、城市规划以及电力、通讯等管网、管线布局设计中发挥了重要作用[1]。
地图服务是国家安全资源[2]，传统的地图匹配算法[3]，由于没有地图数据资源，大都利用模型进行验证，实际应用效果不佳。OpenStreetMap不仅开放了地图数据资源，还提供了许多工具来构建完善的地图服务系统，对深入研究地图匹配算法提供了良好支撑。
1 地图基础服务构建
地理数据构建是地图服务的基础。然而，地理数据一般都加密不对外公开 [4]。迄今为止，数字地图市场被控制，开发人员只能通过付费购买有限的地图数据使用权[5]。互联网技术的发展提供了很多基于地图服务的开放平台，如Google地图、百度地图、高德地图、腾讯地图等，但是这些服务非常有限，用户通过服务接口只能得到有限的数据服务，这对基于地图服务的研究带来了很大的局限性。
OSM是一个网上地图协作计划，目标是创造一个能自由获取内容且能编辑的世界地图，是当今最精确和完善的矢量地图数据集[1]。OSM的数据开源，可以自由下载使用，人们可以通过OSM的規范来构建自己的地图电子数据库，构建自己的路网信息服务系统。
1.1 OSM数据结构
OSM提供了路网信息数据服务，是一种类似于XML结构的文档数据类型，包含3种空间数据类型节点，分别是node、way和relation，构成了整个地图画面[4]。图1是一张OSM描绘的北京工业大学附近的路网地图。从中可以比较清楚地看到路网信息的组织方式，以及每个节点、道路和建筑物等。成千上万的节点信息如果用一个way进行保存数据会很大，不方便计算，可将way拆分，用relation关联。关于node、way和relation这3种类型的节点，参考文献[1]中进行了详细描述。
与北京工业大学附近路网信息地图相对应的OSM文档实例元数据部分内容如下：
从OSM文件可以看到一个relation包含了很多的member，每个member可以是单独的节点，也可以是一条新的道路信息。一个个node、way和relation共同组成了路网信息。
1.2 OSM应用
OSM是一种类似XML格式的文件，可以解析OSM文件获取相应的数据信息。参考文献[1]采用正则表达式来实现此功能，做法是提取way中的数据信息， node和relation信息也必须解析利用。OSM不仅仅是数据服务的开源，还提供了许多可利用的开源工具帮助解析OSM，Osmapi就是其中一种。Osmapi是一种针对OSM结构的解析工具，能够解析并获取OSM文件中的数据信息，有着完善的功能服务。除此之外，OSM还提供了很多开源工具供开发者利用，具体参考http：//wiki.openstreetmap.org/wiki/Frameworks。关于Osmapi的资料比较少，这里只对其进行简单的事例说明：
可直接通过maven使用Osmapi。在pom文件中添加如下引用：
利用Osmapi解析OSM数据文件具体代码可参考OSM官方网址： http：//wiki.openstreetmap.org/wiki/Java_Access_Example，其中给出了Osmapi的使用方法。
2 地图匹配算法设计与实现
地图匹配是一种通过软件方法校正导航定位误差的技术。建立数据模型，将GPS位置信息转化为矢量地图的坐标位置信息，从而将地图和GPS坐标点相匹配，形成地图匹配功能。本文以最实用的几何投影法进行地图匹配实现。
2.1 候选路段选取法
获取GPS位置信息后，需要从整个路网拓扑信息中获得候选路段。路网拓扑信息的数据量非常庞大，获取候选路段信息需要与每个路段进行最短距离计算。为了快速实现路段匹配，采用geohash算法，为路网拓扑信息划分网格。当GPS位置确定后，可找出网格中的相关路段进行计算，避免了多余节点的计算量，原理见图2。
如图2所示，每个网格对应一个唯一编号（0000，0001…），根据路网的经纬度划分得到，这个编号称为geocode。每个网格中都有路网数据，每段路网数据记录在网格编号中。当得到GPS位置信息时，首先获取GPS网格编号，通过网格编号查询该网格中相关路段有哪些，然后在计算GPS位置与当前路段的最短路径时获取候选路段。
2.2 投影法匹配定位点
获取候选路段后，如果要找到P点所在的路段及其所处的位置，可根据投影法进行匹配点计算，见图3。
2.3 几何法地图匹配算法描述
地图匹配过程：准备候选集，计算候选路段，确定最终路段，运行几何匹配算法，确定匹配位置。
（1）读取OSM地图数据，构建路网拓扑信息RL。路段信息用Ri表示，i表示路段编号。Ri中保存本路段的所有坐标点信息。设置表示位FLAG用来表示当前行驶路段RT是否确认。
（2）利用geohash算法划分路网，给每个路段信息Ri添加geocode編号属性，表示该路段所在的geohash区域可以包含多个geocode。参照候选路段选取法进行geohash区域划分。
（3）获取当前的GPS位置坐标点P，读取标志位FLAG，判断路网信息是否确认。如果确认直接跳转步骤（5），否则继续步骤（4）。
（4）根据坐标点P计算出该坐标点的geocode，根据geocode找出相关的候选路段信息。利用最短距离法，计算当前P点到各个路段的最短距离信息，确认当前行驶路段RT，修改标志位FLAG。
（5）应用地图匹配算法计算P点到当前道路轨迹的匹配点。
（6）将匹配后的点输出，描绘到地图道路轨迹中。
3 实验
本文通过分析OSM的数据结构以及OSM的使用方法，利用Osmapi解析获取OSM中的路网信息数据，实现了简易的路网信息服务系统。通过分析地图匹配算法，借助OSM提供的地图数据服务实现了基于几何投影法的地图匹配算法。为了验证实现效果，采用一段GPS轨迹信息，如图4所示，该GPS位置信息坐标点为车辆行驶轨迹，表现出没有匹配到道路的误差样本，期望利用OSM实现的地图匹配系统来进行修正。图中红色带箭头的轨迹路径为未经过匹配的行驶轨迹。
从图5可以看出，地图匹配过程基本可以将车辆的行驶轨迹匹配到正确的道路上去。但是几何地图匹配算法存在一定的不精确性，实验过程中仍会存在误差。
4 结语
本文通过研究OSM的数据结构和使用方法，构建了地图服务系统，能够提供地图相关的应用和计算。实现了基于几何投影法的地图匹配系统，能够将车辆的行驶轨迹匹配到正确的道路中。但几何投影法的地图匹配过程还不是很精确，存在很多需要改进的地方。更加精确的地图匹配算法是今后努力的方向。
参考文献：
[1] 张英辉，张水平，张凤琴，等.基于OpenStreetMap 最短路径算法的分析与实现[J].计算机技术与发展，2013，23（11）：36-41.
[2] 张绛丽，张笑非，徐丹，等.基于OpenStreetMap 的智能交通路网数据的构建 [J].2014，14（1）：41-47.
[3] 陆文昌，张迎，陈龙，等.基于计算几何的地图匹配算法研究[J].机械设计与制造，2012 （1）：43-45.
[4] HASHEMI M，KARIMI H.A critical review of real-timemap matching algorithms：current issues and future directions[J].Computers，Environment and Urban Systems，2015（11）：153-165.
[5] QUDDUS M，WASHINGTON S.Shortest path and vehicletrajectory aided map—matching for low frequency GPSdata[J].Transportation Research Part C：Emerging Technologies，2015（6）：328-339.
[6] 赵东保，刘雪梅，郭黎.网格索引支持下的大规模浮动车实时地图匹配方法[J].计算机辅助设计与图形学学报，2014，26（9）：1550-1556.
[7] 肖维丽，岳春生，奚玲.基于高程的改进D.s证据理论地图匹配算法[J].计算机应用与软件，2015（3）：262-265.
[8] YANG J，MENG L.Feature selection in conditional random fields for map matching of GPS trajectories[J].Springer International Publishing，2015，23（4）：121-135.
[9] 李清泉，黄练.基于GPS轨迹数据的地图匹配算法[J].测绘学报，2010，39（2）：7-13.
[10] YIN H，WOLFSON O.A weight-based map matching method in moving objects databases[J].Proc Ssdbm Con 2004，16（5）：437-438.
[11] 曹凯，唐进军，刘汝成.基于Fr6chet距离准则的智能地图匹配算法[J].计算机工程与应用，2007，43（2）：223-226.
[12] 雷健.基于分布式架构的智能车辆管理系统设计与实现[D].杭州：浙江大学，2015.
