浮动车快速道路匹配算法

耿小峰，王山东，季 军

(1.河海大学 地球科学与工程学院，江苏南京 210098；2.南通市海籍调查测量中心，江苏 南通226006)

0 引 言

浮动车也称GPS探测车，是近年来国际智能交通系统(ITS)中所采用的获取城市道路交通状态的重要途径和有效方式[1]。浮动车可以实时的采集车辆的瞬时速度、坐标以及瞬时方向角等信息，通过对车辆的运行信息进行分析，可以实时的对其监测并估计真实的道路交通状态。而快速地对大规模的浮动车进行道路匹配是依据浮动车对道路通行状况进行监测的关键算法之一[2]。

现有地图匹配算法包括基于模糊逻辑的地图匹配算法、基于D-S证据理论的地图匹配算法、基于权重的匹配算法、曲线拟合匹配法[3-6]等，它们往往只注重匹配精度、没有考虑匹配的效率以及浮动车的方向，尤其在实时性方面无法满足浮动车道路交通状态监测的要求。而基于投影的地图匹配算法[7-8]、基于道路缓冲区分析的匹配算法[9]逻辑简单、易于实现，满足浮动车大数据量匹配实时性的要求，但前者在弯道或交叉路口等道路密集的路况识别准确率降低、易造成识别混乱；后者的缺点是只能确定浮动车所在道路，无法确定浮动车在道路的具体位置。因此，本文在综合考虑匹配准确性和实时性的基础上，提出了浮动车快速道路匹配算法。

1 传统快速地图匹配算法

1.1 基于投影的地图匹配算法

算法思想:将浮动车GPS定位点垂直投影到与该定位点相关的路段上，计算垂直投影距离 di，及车辆行驶方向与道路间的夹角 θi，如图1所示，P点为待匹配的GPS定位点，L1和L2表示GPS点附近的道路中心线。选出 di和θi值小于给定阈值的所有道路，并根据式(1)计算各候选道路的距离度量值Di。

式中:Wd，Wθ分别是投影距离和方向夹角的权值。在所有候选道路中选择距离度量值最小的作为匹配道路，即认为车辆正在该道路上行驶，选取最小垂线段距离的交点作为匹配点。算法最后将车辆在匹配道路上的投影点作为车辆的当前位置。

图1 投影匹配原理图

1.2 基于道路缓冲区的匹配算法

首先依据路宽和GPS精度生成不同宽度的缓冲区，然后将浮动车数据与道路图层缓冲区相匹配。匹配时，首先确定浮动车数据定位点所处的缓冲区个数，当只有1个缓冲区区域时，可将浮动车数据定位点直接匹配到缓冲区区域对应的道路上；当缓冲区区域个数大于1时，则说明浮动车数据定位点在两个或两个以上缓冲区区域的叠加区域内，即浮动车定位点位于交叉口处，通过比较浮动车数据定位点的方向角与连接交叉口的道路的直线段的方向角之间差的绝对值，将浮动车数据匹配到绝对值最小的直线段所对应的道路上。

2 浮动车快速地图匹配算法

据前面的两种基本算法可知，基于投影的地图匹配算法因其逻辑简单使其匹配速度较快、实时性较好，但在十字路口等复杂路段的匹配准确度较差；基于道路缓冲区分析的匹配算法在十字路口等复杂路段的匹配准确度与投影的地图匹配算法相比有一定的改善，但该算法无法确定浮动车所在道路的详细位置，且在构建缓冲区时灵活性较差，不利于数据维护，因此很难应用于实际工程中。基于上述算法的缺点，本文在算法中融入了道路点元、点线相关度[10]的概念，使得算法在准确性、实时性方面满足工程的应用需求。

2.1 道路点元

矢量电子地图中任意线图元都是由一系列点元组成，每一点元的坐标(xi，yi)位置都是已知的。直线路段用线段表示，曲线路段之间用折线近似表示，如图2所示:一条曲线道路由组成它的多个点元连接而成。

图2 组成线的点元

2.2 点线相关度

设GPS定位点P的坐标为(x，y)，路段AB两端坐标分别为 A(x1，y1)，B(x2，y2)，则点 P和路段AB的点线相关度r计算公式如下:

图3 点线相关度r示意图

点P与路段AB的相对位置如图3所示，两条虚线分别为过A点和B点的垂直于x轴的直线，以这两条虚线为界，将线段AB所在的区域分为区域 Ⅰ、区域 Ⅱ和区域 Ⅲ，图中点P1、点P2、点P3分别表示点P与路段AB的三种相对位置。当点P位于区域Ⅰ时，由公式(2)计算出的r取值范围为:r＜0；当点 P位于区域 Ⅱ时，r范围为:0≤r≤1；当点P位于区域 Ⅲ时，r取值范围为:r＞1。

当r＜0时，取点P到路段AB的距离为线段PA的长度；当r＞1时，取点P到路段AB的距离为线段PB的长度；当r取其他值的时候，则直接根据点到直线的距离公式进行计算。当确定了GPS定位点到路段集合中各路段的距离后，选出距离值最小的路段，取其为当前行驶路段进行投影。投影时遵循车辆始终在路段上行驶的原则，根据r取值来确定投影点:当r＜0时，投影点为 A；当 r＞1时，投影点为B；当r取其他值时，投影点为P在路段AB上的垂足。

2.3 基于道路线图元地图匹配算法

首先获取组成道路中心线图元的点元坐标、道路宽度，根据道路点元坐标、道路宽度以及定位点GPS的误差精度确定道路的矩形搜索范围，以及道路折线段的方向角；然后将GPS定位点与搜索范围进行匹配。在地图匹配时，首先判断浮动车GPS定位点所在搜索范围的个数，当个数为1时，将浮动车数据直接匹配到该搜索范围所在的道路上；当搜索个数大于1时，说明浮动车定位点在两条或者两条以上道路的搜索范围内，说明可能是交叉路口，也可能是相距很近的路段。若在交叉路口时，通过比较定位点的方向角与道路折线段方向角之间差的绝对值，将浮动车匹配到绝对值最小的道路上；若在相距很近的路段时，通过GPS定位点与道路折线间的相关度确定点到线的距离，将浮动车匹配到距离最小的道路上。主要算法步骤如下:

(1)获取组成每条道路中心线图元的点元坐标(xi，yi)，道路宽度 Ri，确定每条道路在坐标 x，y 方向上的最小 、最大值 xmin，xmax，ymin，ymax，以及道路折线段的方向角Ai；

(2)依据缓冲区思想确定道路的矩形搜索范围，因此:

式中:Ri为道路宽度，RΔ为GPS定位精度，本文采用的GPS定位精度为15 m；

(3)将定位GPS点坐标P(xp，yp)与搜索范围相比较，如式(4)所示:

记录符合上式条件的矩形搜索范围的个数n1以及相对应的路段编号；

(4)当n1=0时，表示无符合条件的路段，把未匹配的定位点作为异常点删除；

当n1=1时，表示唯一匹配路段，进入步骤6；

当n1＞1时，表示有多条符合条件的路段，进行步骤5；

(5)比较浮动车定位点方向角与符合条件路段的方向角之差的绝对值，与已给定的阈值相比较，当满足式(5)时，说明与路段方向相同，记为1；当满足式(6)时，说明与路段方向相反，记为0；记录符合满足式(5)或者式(6)条件的总个数n2；

式中:Ap为定位点方向角；AΔ为已知阈值，本文取30°；

(6)计算P点与符合条件路段的点线相关度ri，并根据相关度ri来确定定位点P到路段的距离di以及点在路段上的投影点P′；

(7)当n2=1时，表示已找到匹配路段，进入步骤8；

当n2＞1时，表示有多条符合条件的路段，进入步骤7；

(8)选取定位点到路段距离di最小的路段作为匹配道路；

(9)将投影点作为车辆的当前位置加以显示。

3 实验结果及分析

本文采用马鞍山市出租车GPS数据对算法进行验证。为了验证算法的有效性，在数据获取之前，已对数据进行筛选，将数据中速度小于0或大于150的速度值作为GPS接收机定位异常点处理。因此，本文中用于验证的浮动车单车GPS数据(如表1所示)可直接进行数据匹配。

表1 部分单车GPS数据

表2 单车数据匹配结果

匹配的结果见表2所示，GPS数据已匹配到相应的路段，表中的方向值1表示与路段方向相同，详见图4所示，行车方向与路段方向一致。

图4 单车匹配效果图

表3给出了不同数据定位点的匹配速度与匹配效率，时间为测试10次的时间所取的平均值。

表3 不同数据量的匹配率

可以看出，浮动车快速匹配算法随着GPS数据量的成倍增多，匹配时间基本成倍增长，匹配时间始终小于0.1 s，满足匹配实时性的需要；且匹配率基本都保持在92%左右，满足浮动车数据匹配准确性的要求。

表4为文中提到三种快速匹配算法用2 000条数据匹配10次的结果对照表。

表4 三种地图匹配算法对2000个点匹配的性能数据

从表4可以看出，三种匹配算法在匹配率方面非常相近，但浮动车快速匹配算法与缓冲区匹配法较投影匹配法在匹配时间上有着绝对的优势。考虑到缓冲区算法无法定位到详细位置、数据维护复杂的弊端，因此，浮动车快速匹配算法更符合实际工程应用中浮动车大数据量匹配实时性的要求。

实验中所记录的时间是程序去掉数据初始化后数据匹配的计算时间，时间因机器配置、路网情况而定。用于匹配的道路路段共有1 577段，点元数据为11 335个。

操作系统:Windows XP，CPU处理器:Intel(R)Pentium(R)Dual 1.79 GHz，内存:2GB。

4 结 语

文中提出的浮动车快速匹配算法在处理大规模GPS数据时，表现出良好的实用性，在保证高精度的同时，也满足实时性的要求，此算法已在马鞍山市公安交通地理信息系统中得到验证。鉴于城市发展的特点，立交桥的匹配是不可忽视的问题，也是一个难点，将是下一步研究的重点。

[1]王东柱，董继明，李亚檬，等.浮动车数据中零速度点数据地图匹配方法[J].交通信息与安全，2009，27(6):38-42.

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

[3]孙棣华，王春丽.基于模糊模式识别的车辆定位地图匹配算法[J].计算机工程与应用，2007，43(25):227-230.

[4]胡 林，谷正气，杨 易，等.基于权值D-S证据理论的车辆导航地图匹配[J].中国公路学报，2008，21(2):116-120.

[5]陈佳瑜，肖桂荣.基于权重的地图匹配算法[J].计算机工程与应用 ，2005，41(11):168-170.

[6]周 颖，程荫杭.基于曲线拟合的地图匹配算法[J].交通运输系统工程与信息，2004，4(2):68-70.

[7]陈 嘉，胡继华，张飞舟.面向车辆监控导航的地图匹配算法研究[J].北京大学学报，2009，45(2):299-305.

[8]王冬晖，许占文.一种基于类投影的地图匹配算法[J].沈阳工业大学学报，2003，25(5):433-436.

[9]赖云波，孙棣华，廖孝勇，等.基于道路缓冲区分析的地图匹配算法[J].计算机应用研究，2011，28(9):3312-3314.

[10]唐思静.车辆定位导航系统中地图匹配和路径规划算法研究[D].西安:西安电子科技大学，2009:30-32.