基于GPS的地图匹配算法研究

黄奕峰

(兴天通讯技术有限公司，天津 301700)



基于GPS的地图匹配算法研究

黄奕峰

(兴天通讯技术有限公司，天津 301700)

针对传统导航系统的地图匹配算法缺乏整体性考虑的缺点，且GPS浮动车轨迹数据具有曲线整体趋势特性，文中结合城市中对行车的约束限制，提出了一种基于GPS浮动车轨迹数据的全局地图匹配算法，该算法综合考虑各种因素，从而达到较好地实现匹配效果的目的，如轨迹数据和网络路径进行曲线拟合时的相似性、实际行车路径与交通约束的连通性。对所提出的算法进行实验验证，从而促进了GPS浮动车轨迹数据的进一步分析应用。

GPS轨迹数据；浮动车；行车约束；地图匹配

GPS浮动车数据即为包含有速度数据和方向信息的一系列轨迹点，但由于GPS位置精度有限，当在进行数字地图分析处理时会产生轨迹点与道路有偏差的情况，则需要进行地图匹配以获得无偏差轨迹描述。虽然传统的地图匹配算法研究较多[1-2]，但大多缺乏整体性考虑而导致复杂环境下的误匹配，后又出现一些改进的匹配算法，如使用差分GPS辅助设备、滤波等提高匹配准确率[3-6]。GPS浮动车轨迹数据具有曲线整体趋势特性，利用全局思想保证轨迹的准确性[7]。目前轨迹数据的地图匹配方法大多基于全局匹配算法或复合匹配算法，全局匹配算法是基于曲线相似度，一般比较复杂，但匹配精度高[8]；复合匹配方法较为简单，但精度低[9]。在进行算法匹配时，由于轨迹代表的路径均是连通的路段，因此可根据道路拓扑与连通性设计地图匹配算法[10-12]。实际生活中交通规则会限制车辆的行驶，据此本文提出了一种基于GPS浮动车轨迹数据的全局地图匹配算法，该算法综合考虑各种因素，可达到较好地实现匹配效果的目的。

1 算法基本原理

本文算法的基本原理如图1所示，是以GPS浮动车数据采样精度构建缓冲区，并以此估计轨迹点所处位置，然后根据路段的连通性与交通约束来构建和更新未匹配路径，最后以曲线相似度准则得到与浮动车轨迹最接近的路径，从而实现地图匹配，其具体过程可描述如下。

图1 地图匹配算法的基本原理

(1)计算路段集Rc，其为当前可能行驶路段的集合；(2)计算Rc与每一个阶段最后一个路段的续段集交集Rinsect(i)；(3)根据交集Rinsect(i)更新总体路径集PPathset；(4)处理完所有GPS点之后，计算GPS轨迹路径与PPathset中路径的曲线相似度，并选择相似度最高的作为整体匹配路径。

2 行车约束的备选全局路径集的确定

本文由之前所构建的缓冲区得到当前可能路段的集合Rtpi，考虑实际情况中除了连通性之外的车辆行驶交通规则限制条件将会显著提高算法的精度。如图2所示，在交叉点处只能右转，所以r1的后续路段只有r4。

图2 道路的直接后续道路

Ti(topo)为路段对应的拓扑约束，Ti(ru)为车辆行驶的交通规则，若用NRG(Ri)代表Ri的后续路段集，则Ri的直接可行路段集为

NR(Ri)={Ri∈NRG(Ri)|Ti(topo)∩Ti(ru)}

GPS采样间隔变化会产生跨路段现象，为了解决此问题，文献[13]用Dijstra算法计算得到的最短路径作为最终匹配解，文献[14]则通过测量距离来获得最接近真实路段的路径。通过分析与总结，本文引入椭圆误差概念，如图3所示。两个采样点Pi、Pi+1在时间段内可能经过的路径集可通过式(1)进行计算

(1)

其中，Vpi为采样点Pi的速度；tpi为采样点Pi处的时间。

图3 两个采样点间的可行椭圆区域

3 基于曲线相似度的匹配路径选择

判断所有可行路径集中路径与GPS浮动车轨迹数据的相似性是以曲线的整体走势相似性进行的，本文选择的相似度计算方法为改进的扫描线曲线相似度计算法[15]，具体步骤如下：

(1)对所有可行路径按照轨迹延伸范围进行切割，如图4所示；

(2)将总体路径划分为n个部分，其中n为总体路径包含的路段数，然后扫描线法计算每部分的相似度。设X、Y方向的延伸范围为ExtendX、ExtendY，若ExtendX>ExtendY，则扫描线方向平行于Y轴，若ExtendX

(3)最后根据式(2)计算总体路径集中路径PPathset(i)的曲线相似度scoresim，从而得到匹配路径

(2)

图4 扫描线法边框的切割

4 算法验证

本文所使用的GPS浮动车数据采样间隔为10 s，重采样间隔为60 s，重采样是为了更有效的对实验进行分析。地图数据为武汉卓越科技提供的MapInfo格式的武汉道路数据。

4.1 时间效率分析

算法的基本步骤是首先构造总体路径集，然后采用改进的扫描线曲线相似度计算方法进行相似度计算，最终找到最匹配路径。总体路径集中数据量较小，本算法与点到线的匹配算法、基于弱Frechet距离全局匹配算法整体时间复杂度O(n)的比较，如表1所示。

表1 地图匹配算法的时间复杂度与全局性比较

表中，n表示采样点数;m表示路段数。

4.2 地图匹配的结果

用实验验证本文所提出的算法，在所得出的效果图中GPS浮动车轨迹点用黑点表示，匹配后的路径则为高亮粗线条表示。如图5所示，其为实验匹配效果图。

图5 地图匹配的整体效果图

实验结果1 平行双线路。

传统的地图匹配算法在遇到平行双线路时易发生误匹配，而本文提出的算法在曲线相似性的基础上加入实际情况的交通约束，从而减少了误匹配情况的发生。如图6中有两条平行双线路A(自西向东)、B(自东向西)，浮动车轨迹点序列方向在图中用箭头所示，虽轨迹曲线形状更贴近道路B，但本算法中的行车约束使算法得到正确解A。

图6 平行双线路情况下的地图匹配结果

实验结果2 相邻轨迹点跨路段。

当车辆行驶速度过快或采样间隔较大时，则相邻点之间会出现中间路段，而本文提出的算法中运用椭圆误差与行车约束，得到两点间可能的路径集，从而结合整体路径集进行判断可提高匹配准确率。如图7中的GPS采样间隔分别为10 s、60 s，两种情况均实现了正确匹配。

图7 GPS采样间隔不同时的匹配结果

4.3 算法匹配效果统计

为了对算法匹配效果进行统计与分析，本文对采集到的32条轨迹数据进行匹配，并将结果匹配率进行统计，再与点到线的匹配算法、基于弱Frchet距离全局匹配算法的匹配率进行比较，比较结果如表2所示。

表2 地图匹配算法正确匹配率比较

5 结束语

针对传统导航系统的地图匹配算法缺乏整体性考虑的缺点，且GPS浮动车轨迹数据具有曲线整体趋势特性，因此本文结合城市中对行车的约束限制，提出一种基于GPS浮动车轨迹数据的全局地图匹配算法，该算法综合体现了道路拓扑算法与曲线匹配算法的优点，改进了点匹配算法中对各因素参数进行设定的缺点，并最终通过GPS浮动车与实际道路数据进行了实验，证明了该算法的有效性。

[1] Quddus M A.High integrity map matching algorithms for advanced transport telematics applications[D].London:University of London,2006.

[2] Quddus M A, Washington Y O,Robert B N．Current map-matching algorithms for transport applications：state-of-the art and future research directions[J].Transportation Research Part C,2007(15):312-328.

[3] Yang D,Cai B,Yuan Y.An improved map-matching algorithm used in vehicle navigation system[C].Shanghai:Intelligent Transportation Systems,2003.

[4] Li Z,Chen W.A new approach to map-matching and parameter correcting for vehicle navigation system in the area of shadow of GPS signal[C].Vienna:IEEE Intelligent Transportation Systems，2005.

[5] Najjar M E,Bonnifait P.A road—matching method for precise vehicle localization using kalman filtering and belief theory[J]．Autonomous Robots,2005,9(2):73-191.

[6] Obradovic D,Lenz H,Schupfner M.Fusion of mapand sensor data in a modern car navigation system[J]．Journal of VSLI Signal Processing,2006,45(1-2):112-122.

[7] Brakatsoulas S, Pfoser D, Salas R, et al. On map-matching vehicle tracking data[C].Norway:International Conference on Very Large Data Bases,2005.

[8] Yin H, Wolfson O. A weight-based map matching method in moving objects databases[C].Norway:International Conference on Scientific and Statistical Database Management, 2004.

[9] 章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息,2007,7(2):39-45.

[10] Blazquez C A, Vonderohe A P.Simple map-matching algorithm applied to intelligent winter maintenance vehicle data[J].Transportation Research Record,2005(1):68-76.

[11] Meng Y．Improved positioning of land vehicle in ITS using digital map and other accessory information[D]．Hong Kong：Hong Kong Polytechnic University,2006.

[11] Amer I,Badawy W,Jullien G.A high-performance hardware implementation of the H.264 simplified 8×8 transformation and quantization[C].PF,USA:Proceeding IEEE International Conference on Acoustics, Speech and Signal Processing,2005.

[12] Chao Y C,Tsai H H,Lin Y H,et al.A novel design for computation of all transforms in H.264/AVC decoders[C].Marco:Proceeding IEEE International Conference Multimedia and Expo,2007.

[13] Amer I,Badawy W,Jullien G,et al.A simplied 8×8 transformation and quantization real-time IP-block for MPEG-4 H.264/AVC applications: a new design flow approach[J].Journal of Circuits, System, Computer,2007(16):1011-1026.

[14] Park J S,Ogunfunmi T.A new hardware implementation of the H.264 8×8 transform and quantization[C].France:Proceeding of IEEE International Conference Acoustics, Speech and Signal Processing,2009.

[15] Jang F, Kao J N,Yang J S,et al. A 0.8μm 100 MHz 2-D DCT core processor[J].IEEE Transactions on Consumer Electron,1994(40):703-710.

Research on Map Matching Algorithm Based on GPS

HUANG Yifeng

(Xingtian Communication Technology Co. Ltd., Tianjin 301700, China)

The map matching algorithm based on traditional navigation system lacks overall consideration, and the GPS floating vehicle trajectory data has the characteristics of the overall curve trend. This paper proposes a global map matching algorithm based on the GPS floating vehicle trajectory data, combined with the drive constraints of the city. For better matching effect, the algorithm considers various factors, such as the curve similarity between trajectory data and network path, and the connectivity between the actual traffic path and traffic restriction. The proposed algorithm is verified by experiments.

GPS trajectory data; floating car; drive constraints; map matching

2016- 10- 24

黄奕峰(1973- )，女，本科。研究方向：通信工程，智能终端设备及软硬件管理平台。

10.16180/j.cnki.issn1007-7820.2017.06.015

TN967.1；P228.4

A

1007-7820(2017)06-054-04