0 引言

基于位置服务(Location Based Service, LBS)的导航系统的广泛应用给人们的生活带来了极大的便利，尤其在移动端如手机、车载上的迅速普及使得导航服务成为日常出行中不可缺少的需求。

电子地图作为导航服务的基础，其完整性和正确性对导航系统有着直接的影响。而随着交通系统的发展，每年都有着成千上万条新增道路，如何准确及时地利用新增道路对电子地图的路网进行更新就成为了导航系统中尤为关键的问题。

通常情况下，电子地图中新增道路的数据信息主要依靠政府组织发动专门的机构进行测绘所得，这所带来的一个严重问题是测绘将花费大量的人力、物力且测绘周期较长，不能及时对电子地图的路网进行更新。为了解决该问题，很多具有实用性的新方法被开发出来。文献[1]基于遥感影像地图，以多尺度模板匹配为依据，通过LSB-Snake模型实现半自动化的新增道路提取；但是其准确率受限于影像地图中地物的识别与提取技术，且在识别过程中需要人为干预。文献[2]中通过高分辨率图像进行道路的提取，采用统计区域融合的方法进行图像分割，并利用基于轮廓划分的骨架修剪策略进行路网的提取，实现了道路提取的自动化控制；但是该方法无法处理图片中的被遮挡或覆盖的路段。文献[3]根据浮动车的大量历史数据结合空间网格的方法来进行新增道路的识别。文献[4]中参考浮动车的轨迹数据，通过与电子地图进行图层的图像配准并结合数据清洗的方法来发现新道路。

本文针对以图像识别为主的新道路发现算法的高时空复杂度，提出了一种结合历史轨迹匹配失效点的筛选识别算法，并利用新增道路对电子地图的路网进行更新，具有较低的时空复杂度和更高的灵活性。

1 异常轨迹方向判定

电子地图的构建基于MapInfo格式^[5-6]，拓扑路网中以路段为基本单位，单路段长度的选取以测绘为基准。单路段通常选取直线或近似直线的路段，并由道路方向、路段上离散点经纬度坐标等信息所组成。

在利用地图匹配算法^[7-9]将浮动车的GPS轨迹信息匹配到电子地图中时，有时会出现多辆车的行驶轨迹在电子地图的某特定区域内匹配失效的情形，即无法将行驶轨迹有效地匹配到电子地图中的具体路段上。本文中称一条匹配失败的轨迹为一个异常轨迹，它所包含的定位点为一个异常点组。

在地图匹配过程中，由匹配算法检测出的匹配失败的异常点组如表 1所示。其中时间戳属性标识GPS定位数据产生的时刻，以30s为采集周期。匹配结果为1表示定位点正确匹配到路网，匹配结果为0表示匹配失败。

为了确认这些异常点组所描述的轨迹是否为一条新路径，本文首先根据异常点组来确定轨迹所描述的路径的轮廓方向。

本文采取对所有异常点组中的定位点进行顺序遍历，取得所有定位点中的经度最大值LON_max、经度最小值LON_min、纬度最大值LAT_max、纬度最小值LAT_min。可得所有异常点的经向跨度ΔLON和纬向跨度ΔLAT计算公式如下：

$ \left\{ \begin{array}{l} \Delta LON = LO{N_{\max }} - LO{N_{\min }}\\ \Delta LAT = LA{T_{\max }} - LA{T_{\min }} \end{array} \right. $

(1)

其中：ΔLON≥ΔLAT则异常点组方向为主经向，ΔLON < ΔLAT则异常点组方向为主纬向。

根据上述所确定的异常点组的主方向，对各个异常点组内的定位点分别进行主方向排序。若方向为主经向，则对定位点进行排序时，先按照经度值进行排序，若两点的经度值相等，则再按照纬度值进行排序，反之亦然。

2 有效异常轨迹的筛选

异常轨迹的产生，有两种可能的情形：1)车辆端的GPS采集设备由于故障或“飘逸”而产生的定位失准；2)其所描述的路线是一条在实际环境中已存在的新路径，而在电子地图中尚未被更新。为了排除因故障或“飘逸”而产生的定位失准的情形，进而得到准确的新道路轨迹信息，必须对异常轨迹进行筛选，以剔除定位失准数据。

2.1 飘逸筛选

经车载GPS采集设备而得到的车辆行驶轨迹的定位数据，可能由于采集设备未校准或故障等原因，而使轨迹信息产生大幅度飘逸，这类数据不能反映轨迹的真实信息，在进行筛选时应予以剔除。本文选取已排序的各个异常点组的中位点作为筛选依据。选取中位点是为了避免选取端点而可能引入的潜在误差，因为轨迹的端点可能会因为与路网中其他路段的交汇，而使匹配结果更加复杂化。

对主方向排序后的N组异常点，选取各组的中位点，计算任意两中位点间的欧氏距离D_ij，并统计每个中位点与其他组中位点间距离超过阈值θ的个数S_i。若S_i大于组数N的一半则将该失效点组剔除。对于任意两中位点G_i(lon_i, lat_i)和G_j(lon_j, lat_j)，有如下公式：

$ {D_{ij}} = \sqrt {{{\left( {lo{n_i} - lo{n_j}} \right)}^2} + {{\left( {la{t_i} - la{t_j}} \right)}^2}} $

(2)

$ {S_{ij}} = \left\{ {\begin{array}{*{20}{c}} {1,}&{{D_{ij}} \geqslant \theta } \\ {0,}&{{D_{ij}} < \theta } \end{array}} \right. $

(3)

$ {S_i} = \sum\limits_{j = 1}^n {{S_{ij}}} $

(4)

其中：S_i < N/2保留该失效点组，S_i≥N/2剔除该失效点组。

根据城市道路分级规范，城市主干道最大宽度约为50m，由于GPS定位数据在采集及传输过程中均有一定的误差，定位数据会在道路两侧呈现一定的摆动，本文中设定距离阈值θ取值对应实际距离100m。经纬度坐标与两点间的实际距离的转换，则采用文献[10]中的方法。

2.2 轨迹拟合

由匹配算法检测出的异常点组，所包含的是以30s为周期采集到的车辆位置的离散定位点，其只能反映车辆在某一具体时刻的位置，为了从一组定位点中得到车辆的更直观的轨迹信息，本文采用基于离散点的最小二乘法^[11]对异常点组中的离散定位点进行直线拟合。

若异常轨迹的方向为主纬向，对一个异常点组:

$ A\left[ M \right] = \left[ {\left( {lo{n_1},la{t_1}} \right),\left( {lo{n_2},la{t_2}} \right), \cdots ,\left( {lo{n_M},la{t_M}} \right)} \right] $

其由最小二乘法拟合所得的在直线方程为：lon=a*lat+b，则有：

$ a = \frac{1}{c}\sum\limits_{i = 1}^M {\left( {lat - \overline {lat} } \right)\left( {lon - \overline {lon} } \right)} $

(5)

$ b = \overline {lon} - a * \overline {lat} $

(6)

其中：$\overline {lon} = \frac{1}{M} * \sum\limits_{i = 1}^M {lo{n_i}} ,\overline {lat} = \frac{1}{M} * \sum\limits_{i = 1}^M {la{t_i}} ,c = {\sum\limits_{i = 1}^M {\left( {la{t_i} - \overline {lat} } \right)} ^2}$。

通过上述拟合方式得到的直线为通过异常点组所能得到的车辆轨迹线性化的最优解，由此得到的轨迹的位置及方向信息是角度筛选的关键。

2.3 角度筛选

对于异常点组，通过飘逸筛选可以剔除由于设备故障或未校准而产生的明显错误数据，但是，仍会有部分异常点组相对于全部异常点组所反映的新道路的真实轨迹具有相对较大的误差。为了尽可能减少由这些具有较大误差的异常点组所带来的误差，必须对飘逸筛选后的异常点组数据作进一步的筛选，去除较大误差的异常点组。

为此，本文采用角度筛选的方法来提炼异常点组。首先，将由飘逸筛选后所得的所有异常点组的数据进行融合并排序，并采用2.2节中的方法对其进行轨迹拟合，此时得到的轨迹称为综合轨迹：lon=a₀*lat+b₀。其次，对每单个异常点组进行轨迹拟合，称为单线轨迹：lon=a_i*lat+b_i。最后，分别计算每个单线轨迹与综合轨迹的间的最小夹角角度α，若该角度超过阈值δ，则认为相应单线轨迹的异常点组具有较大误差，在该角度筛选中应予以剔除。

$ \alpha \left\{ \begin{array}{l} \frac{{\rm{\pi }}}{2},\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{a_0} * {a_i} = - 1\\ \arctan \left( {\frac{{{a_i} - {a_0}}}{{1 + {a_0} * {a_i}}}} \right),\;\;\;{a_0} * {a_i} \ne - 1 \end{array} \right. $

(7)

若α < δ则保留异常点组，否则剔除异常点组，其中阈值δ设定为15°。

3 路网更新

对由匹配算法检测出的匹配失效的异常点组，通过飘逸筛选剔除失准数据，通过轨迹拟合后的角度筛选剔除较大误差数据，此时筛选所得的异常点组即为描述新道路的轨迹信息。将筛选所得的所有异常点组数据进行融合并排序，即得新道路的路段信息，可利用该新道路对电子地图的路网进行更新。

在对路网进行更新时，根据电子地图路网结构的特点，首先需要判断新道路在路网中的插入位置，即新道路路段的两个端点在路网中路段上的匹配位置。新道路的端点匹配结果有三种可能的情形分别如图 1所示。

图 1(a)所示，新道路的端点落在路网中的节点上，此时需要在路网的拓扑结构中将该新道路加入到节点处所有连接路段的邻接路段表中，并将节点处的所有连接路段加入到新道路的邻接路段表中。图 1(b)所示的情形，新道路的端点落在某一路段之内，根据电子地图的构建结构，应以该端点建立一个节点，并将该路段从端点处将该路段拆分成两个子路段，并同时更新自己的邻接路段表。由失效点组可知，新道路的两个端点至少有一端是可以匹配成功的，图 1(c)所示的情形，即新道路的某一端点未落入路网中的任一路段上及节点处，那么此时新道路的另一端点一定是匹配成功的，此时新道路是一条单通的路段，即该新道路仅有一端与路网中的其他路网相连通，另一端为一封闭的节点。此时仅需根据另一端点的匹配结果进行更新即可。

由此可得，本文实现的基于新道路发现的GIS地图更新算法的流程如图 2所示。

4 实验结果

为了验证本文提出的算法，在Linux操作系统下，在Qt环境中编码实现该算法，并在Qt Graphics View框架下使用MapInfo公司的MIF格式的电子地图进行显示。本文选取某市某局部地区的地图，利用该市某出租车公司的车辆轨迹的数据进行实验。由地图匹配算法所检测出的匹配失效点组如表 1所示。

通过Google地图对该区域进行地图抓取如图 3所示。

本文构建的该区域的电子地图的路网结构如图 4(a)所示，由此图可看出实际路网结构与电子地图的路网结构存在明显差异，若直接将表 2中各个失效点组的轨迹直接显示在该路网中则如图 4(b)所示。

对表 2所示的各失效点组，利用本文提出的算法进行处理后所得路网结构如图 5中所示。

由图 5可以看出，本文算法能够有效地进行轨迹信息的筛选过滤，并准确地将该路段插入到路网中。

为了进一步验证本文算法的正确率，在浮动车的历史轨迹覆盖的局部路网中，手动拆除原本已经存在并且被有效匹配过的多个路段，然后对浮动车的历史轨迹重新进行匹配，统计匹配过后被手动拆除的路段的重建率，结果如表 2。

由表 2可知，本文算法能够准确高效地判定新增路段并将其正确地插入路网中，表 2中的重建率之所以未能达到100%，分析原因是因为轨迹数据不够充分，在某些待重建路段上的轨迹未能完整覆盖该路段，若增加浮动车的历史轨迹数据，重建率可有效提高。

5 结语

为了解决电子地图的路网依靠人工测绘及更新的代价大、耗时长的问题，本文提出了一种基于浮动车轨迹匹配失效的新道路发现及电子地图路网更新算法。根据车辆的历史轨迹的匹配结果，对特定区域的匹配失效点组利用飘逸筛选排除定位失准产生的数据；采用基于直线的最小二乘法对失效点组进行轨迹拟合，通过各个失效点组间的夹角进一步剔除误差较大的失效点组；最后根据筛选所得定位点进行融合排序，根据路网结构准确高效地将新道路插入到路网中，实现地图的更新。在某城市局部区域的电子地图中，根据真实浮动车历史轨迹的实验可得，本文算法可有效解决基于新道路发现的电子地图更新问题，为靠人工实现的测绘和更新提供了一种新思路。