基于多分类的车辆轨迹地图匹配算法的研究

王丽娟

摘要： 关键词： 中图分类号： 文献标志码： A文章编号： 2095-2163

Abstract： In the vehicle navigation system， the movement track of vehicle on the electronic map reflects the realtime measurement of the GPS devices. This thesis explores a kind of mapmatching method based on multiclassification algorithms， adopts SVM to preprocess the training data and designs an algorithm to select the best parameter of ELM. The experimental results show that the multiclassificationbased approach can achieve higher accuracy and faster matching speed.

0引言

在車辆导航系统中，电子地图上显示的车辆移动轨迹反映了通过GPS测量设备实时定位的结果。然而，显示在地图上的车辆轨迹可能与真实轨迹不一致，一些轨迹可能偏离了实际路网中的道路，很多定位点并不在道路上，导航效果不是很理想。因此，在进一步挖掘和分析地理信息之前，检测这些误差是很有必要的。

地图匹配是一种基于软件技术的定位修正方法，其基本思想是将车辆定位轨迹结合所在区域的道路网数据集，由此估计车辆在地图上的路段信息。本文的研究重点就是如何快速准确地完成地图匹配。

本研究中使用的数据集包括GPS采样数据集和北京市路网数据集，在预处理过程中使用了Arcgis软件划分路网和格式转换，此外，使用了Hadoop平台下的MapReduce计算框架提取车辆轨迹。研究中的另一关键部分是分类算法，包括支持向量机算法和极限学习机算法。

1数据分析及算法框架

1.1问题定义

在本论文中，根据数据集特征和算法设计分析的需要，对以下概念进行说明。

定义1路段一个路段r是在两个道路结点间的路径。一个路段通常包括了一些必要的其它属性，比如r.id表示路段r的id，r.oneway表示路段r是单向道还是双向道。

下面两条观察结果有助于设计本论文中的地图匹配算法。为了避免采样误差的影响，只考虑方向角在对应路段角度上下浮动15°的GPS点。具体内容如下。

1）观察1在单向道上，车辆只能在一个方向上行驶。在这种类型的道路上，GPS点的方向角围绕一个定角小范围变化，这个定角由道路形状和道路位置综合确定。

2）观察2在双向道上，车辆允许在两个方向上行驶。对某个道路结点，假设所在路段与正北方向夹角是α（0～180°），另一个夹角就是α+180°。因此，在双向道上的GPS点的方向角分别在α和α+180°周围小范围浮动。

问题定义给定路网数据集D，历史GPS点集合P，确定元素p所属的路段r.id，其中，p∈P，r∈D。概括地说，地图匹配过程是GPS点集合映射到路网数据集的过程，即P→D。

在本论文中，使用的历史GPS数据集是由12 000辆北京出租车在2012年11月收集到的数据 ，基本完整地记录了北京市出租车的移动情况，也大致能够覆盖北京市的所有道路。另外，一个数据集是北京市的路网数据集 ，北京市路网十分复杂密集。路网的基本要素为：点实体（节点）和线实体（路段）。

1.3研究框架

本论文提出的基于多分类的车辆轨迹地图匹配算法的研究框架如图1所示。

2基于多分类的车辆轨迹地图匹配

2.1基于网格划分的数据预处理

在多分类算法中，当训练的类别越多，需要的训练时间也会越长。因为研究的路网数据集中有433 391个路段，全部一起训练的话，需要的训练时间是相当长的。因此，拟定采用网格划分对数据进行预处理，每个网格内的操作能够并行处理。

2.1.1路网的划分

假设路网地图长为L，高为H。研究将整个地图划分为N×N个大小相同的网格，每一个网格长为l=L/N，高为h=H/N。又设路网地图左上角的坐标为p_0 （lat_0，lon_0），地图内任意一点的坐标为p（lat，lon），那么点p所属的网格ID由如下公式运算得出：ID=floor（N（lat_0-lat）/h）+floor（（lon-lon_0）/l）+1（2）这里，floor（）为向下取整函数。

确定网格划分方案后，继而使用ArcMap中提供的裁剪功能，用于创建一个新的特征文件，即感兴趣的区域（Area of interest，简称AOI）或研究区域，通常，输入的特征文件是一个比较大的文件，裁剪出来的文件是另一个特征文件的子集，包含了输入特征文件的地理特性。而设计过程可分述展开如下。

首先，创建裁剪形状图层。裁剪形状也必须是一个图层，在ArcCatlog目录下新建一个shapefile文件，创建好的文件保存在default.gdb目录下，然后用ArcMap打开，编辑成需要的形状，此处则编辑成对应位置的矩形框。

然后，用裁剪工具处理。打开ArcMap，在Geoprocessing功能选项里，选择clip裁剪选项。需要选择输入的特征文件、形状特征文件，此处分别为原始的北京市路网文件和先前创建编辑的特征文件。通过特征文件能够看到对应的道路网信息也被保存下来，该网格有583个路段，与原始的道路网相比，路段数量大大减少。同时，数据格式与原来完整的路网保持一致。将输出的特征文件利用ArcMap里的转换工具layer to kml，转换成KML（或KMZ）文件，用于在地球浏览器中显示地理数据。endprint

2.1.2纠正路网

直接打开所得的路网裁剪后的KMZ文件，用Google Earth显示。显然，矢量路网KMZ文件和卫星地图上的道路存在着偏移，一些主干道與卫星地图上的道路并不重合。

实验处理过程中要对GPS点进行标记，不过GPS点显示在ArcMap上偏移很大。此外，路网在ArcMap上虽然有道路信息，但不能准确地把GPS点所在的道路分辨出来。所以尝试将矢量路网地图和卫星地图叠加起来以供分析。

叠加之前，需要利用谷地软件进行纠偏，实验中对源点坐标和目标点坐标进行参数设置，通过该软件的坐标纠正功能生成最终的 KML 文件。

纠正以后基本能和卫星地图重合，把卫星地图和矢量电子地图叠加在一起，直接双击KML文件上的路段，能够获取到道路信息。

2.1.3出租车轨迹的提取

根据网格区域来获取每辆出租车的GPS采样轨迹，本文选择MapReduce计算框架来应用于历史GPS点数据的研究讨论中。分析过程内容如下。

首先，在Map函数中，只提取出租车状态为0或1的点记录（分别为空车和载客两种运营状态的记录），同时对每个数据项的类型进行字符检查和字符数目检查，以防出现乱码。

MapReduce框架将所有键相同的值归集在一起传递给对应的Reduce函数，此时，键是出租车标识符。在Reduce函数里，只保留落在网格区域内的点记录，将点记录按照时间依次延展排序。同时，计算当前记录时间和上一条记录时间的差值，只有当差值大于30 s才记录当前的点记录。此外，还需判断前后记录的坐标数据是否相同，若前后两点的记录是相同的，只保留一条该位置的记录。

最后，研究得到每一辆出租车在同一天、同一网格内的GPS点记录。为方便后续处理，输出以Excel文件格式组织，每一个Excel文件对应一辆出租车的轨迹记录。然后使用Excel to kml转换工具，将满足要求格式的点记录Excel文件转换成KML文件，用于在地球浏览器中显示地理数据。

2.2获取训练数据

2.2.1利用GPS数据集进行标注

本文已经得到了目标网格内纠正好的路网矢量地图和2012年11月中在目标网格内每一辆出租车的轨迹。研究将这些轨迹转换成能够在电子地图上直观显示的格式。为了方便标注，将路网矢量地图和网格内的轨迹叠加显示在卫星地图上。根据坐标、时间顺序和出租车的行驶方向，就能够为每一个GPS点标注其所在路段的ID。

将卫星地图、纠正后的矢量电子地图和车辆轨迹叠加在一起，再用上述方法标注每一个GPS点，得到的训练集数据A，可以有效避免由误差导致的匹配不精确。这样得到的带标签的GPS点记录准确度比较高。

2.2.2利用路网中的GPS数据进行标注

为了对路网做进一步分析，将目标网格的路网数据（gdb格式）转换成json格式的文件，由此发现每条路段本身含有大量的GPS点坐标数据，将这些点提取出来（本文用Python语言编写功能程序），再利用kml to excel工具转换成KML文件，并用Google Earth软件显示在地图上。结果显示：其中包含了大量的点，弯曲的路段上的点更加密集。

接下来，深入观察路段上的点，发现这些点正好落在每条道路上，因此，这些点是每一条道路的关键坐标点，而且标志确定了道路的形状和位置。基于这些关键点均来源于自带路段标签属性的路网，因此比较容易地就可获取其路段ID。

然而，作为训练数据，这些点还少了方向角这个特征。本文根据连续点间的坐标关系设计出一种方法来计算方向角。给定一组连续的关键点，可以通过给出的坐标计算每一个点的方向角。注意，出租车行驶在单向道和双向道的方向角是不同的，因此要将路网中oneway这个属性的值利用起来。假设当前点位于单向道上，设其坐标为p_0 （lon_0，lat_0），当前点下一点的坐标为p_1 （lon_1，lat_1）。由平面几何知识可知，已知平面上两点的坐标，可以求出一个点相对于另一个点的经度增量和纬度增量，易求得变化率，该变化率即是正切值，相应地，求得反正切值即能求得方向角。假设p_0的方向角是α，反正切由下式可得：α=arctan（（lon_1-lon_0）/（lat_1-lat_0））（3）最后，通过象限处理得到当前点的方向角，这里角度变化范围是0～360°，顺时针方向增加，取整数。如果点在双向道上，同一个坐标对应两个点记录，差别在方向角上，二者的方向角是相反的关系，一个方向角为α，另一个方向角为α+180°。通过这种方式，就可将在一个网格区域内获取的数据作为训练数据集B。

2.3插值获取训练数据

将多辆出租车的轨迹显示到地图上，发现这些采样点主要分布在道路中心线两侧，部分点偏离较大。据此，本文提出以道路中心线为基准，允许一定范围内的坐标变化来模拟真实的采样情况。根据前面的研究，计算得到了每条路段中的关键点的记录，这些记录自带路段标签且补充了方向角属性，在这些记录的基础上进行模拟操作。操作过程可表述如下。

首先，采取等比例插值，插值是比较均匀、线性的。其次，采用两点之间随机插值。

经过多次实验，决定采取如下方案进行随机插值，插值点的坐标在区间长度为相邻两个点坐标的经纬度增量的区间内随机变化。插值结果比较接近真实的GPS点分布。 为此，研究顺次提出各点规律展示如下。

3结束语

本论文提出一种利用模式识别的方法来解决地图匹配问题。采用支持多分类算法的解决方案来预测GPS点的真实位置，从而将地图匹配问题转换成多分类问题，能够运用多分类算法获得有效设计解决；提出使用GPS采样数据集获取训练数据的方法；挖掘相关路网数据中路段信息，得到另外一种快速准确获取带标签点记录的方法，即利用路段本身关键点进行插值；进而设计了寻找最优ELM参数的算法，同时，对基本的ELM输入进行调整，使得匹配精度大幅提升。endprint

但是该方法还有待更详尽的实验和分析，未来发展还需要考虑影响匹配结果的潜在因素。

參考文献：

[1] 杜江平. 基于 GPS/GIS 车辆定位导航系统的研究[D]. 成都： 电子科技大学， 2009.

[2] QUDDUS M A， OCHIENG W Y， NOLAND R B. Current mapmatching algorithms for transport applications： State-of-the art and future research directions[J]. Transportation Research Part C： Emerging Technologies， 2007， 15（5）： 312-328.

[3] BERNSTEIN D， KORNHAUSER A L. An introduction to map matching for personal navigation assistants[J]. Geometric Distributions， 1998，122（7）：1082-1083.

[4] GREENFELD J. Matching GPS observations to locations on a digital map[C]// Proceedings of the 81th Annual Meeting of the Transportation Research Board. Washington DC， USA： [s.n.].2002：1-14.

[5] YAMG Dakai， CAI Baigen， YUAN Yifang. An improved mapmatching algorithm used in vehicle navigation system[C]//Intelligent Transportation Systems， 2003. Proceedings.2003 IEEE. Shanghai， China： IEEE， 2003， 2： 1246-1250.

[6] HUANG Guangbin， ZHU Qinyu， SIEW C K. Extreme learning machine： A new learning scheme of feedforward neural networks[C]// IEEE International Joint Conference on Neural Networks. Budapest， Hungary：IEEE， 2004， 2： 985-990.

[7] 梁冬萍，戴迎春，刘兵. 基于Geodatabase的城市绿化现状数据库建设[C]//第七届ArcGIS暨ERDAS中国用户大会. 北京：中国地理信息系统协会，中国遥感协会，2006：397-400.

[8] 李锐， 王斌. 文本处理中的 MapReduce 技术[J]. 中文信息学报， 2012， 26（4）： 9-20.

[9] 林关成， 李亚安. 一种支持向量机训练集选取算法改进[C]//2009年中国西部地区声学学术交流会论文集. 西双版纳：中国声学学会， 2009：83-86.

[10]李静. 支持向量机多分类算法研究[D]. 武汉：湖北大学，2008.

[11]王义发. 车辆定位导航系统中的地图匹配算法研究[D]. 武汉：武汉理工大学， 2007.endprint