本发明公开了一种基于GPS时空轨迹的路网拓扑变化自动检测方法及系统，包括步骤：步骤1，基于GPS时空轨迹构建局部时空轨迹向量；步骤2，基于路网数据和GPS时空轨迹构建局部道路拓扑向量；步骤3，局部时空轨迹向量和局部道路拓扑向量的相似性度量；步骤4，提取变化轨迹点，并构建变化轨迹点局部范围的道路拓扑关系；步骤5，将变化轨迹点局部范围的道路拓扑关系和原始路网对比，获得路网拓扑变化。本发明可自动检测城市路网的拓扑和图形变化，在提高路网变化检测精度的同时，还可实现路网拓扑和路网图形的变化检测；另外，本发明还具有成本低廉和高效的优点。
1.基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是，包括步骤：步骤1，基于GPS时空轨迹构建局部时空轨迹向量：
以当前轨迹点的上一时刻轨迹点为起点、当前轨迹点为终点，构建第一向量；
以当前轨迹点为起点、当前轨迹点的下一时刻轨迹点为终点，构建第二向量；
将第一向量与第二向量的合向量平移至以当前轨迹点为起点，即当前轨迹点的局部时空轨迹向量；
步骤2，基于路网数据和GPS时空轨迹构建局部道路拓扑向量：获得当前轨迹点及其上一时刻轨迹点、下一时刻轨迹点的最小包围矩形，构建最小包围矩形的面状缓冲区；
将面状缓冲区中属于同一拓扑路段且连续的图形路段作为一条局部拓扑路段，其他图形路段本身分别作为局部拓扑路段，局部拓扑路段方向同其来源的拓扑路段；
从局部拓扑路段的起点指向终点的向量即当前轨迹点的局部道路拓扑向量；
步骤3，局部时空轨迹向量和局部道路拓扑向量的相似性度量：获得当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的综合相似性S，S＝λSDis+(1-λ)SAng，以综合相似性最大值为有效综合相似性；SDis、SAng分别表示局部时空轨迹向量和局部道路拓扑向量的距离相似性、方向相似性，λ、(1-λ)为权值，根据实验验证确定；
步骤4，提取变化轨迹点，并构建变化轨迹点局部范围的道路拓扑关系：根据当前轨迹点的有效综合相似性提取变化轨迹点；
获得包括变化轨迹点的轨迹拓扑边界点，轨迹拓扑边界点即(1)匹配到不同拓扑路段的相邻轨迹点，或(2)一个匹配到拓扑路段、另一个未匹配到拓扑路段的相邻轨迹点；
根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系；
步骤5，将变化轨迹点局部范围的道路拓扑关系和原始路网对比，获得路网拓扑变化。
2.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤2中，所述的面状缓冲区大小为城市街区平均宽度。
3.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤3中，当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的距离相似性其中：局部时空轨迹向量起点到面状缓冲区四个顶点距离的最大值即距离阈值DTH；
当局部时空轨迹向量起点到候选图形路段i的垂足在候选图形路段上时，Di为局部时空轨迹向量起点到候选图形路段i的距离；当局部时空轨迹向量起点到候选图形路段i的垂足不在候选图形路段上时，局部时空轨迹向量起点到候选图形路段i两端点的距离较小值即Di；
所述的候选图形路段即进行相似性度量的局部道路拓扑向量对应的图形路段。
4.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤3中，当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的方向相似性SAng为：SAng＝|cos(θi,j)|
其中，θi,j为局部时空轨迹向量与局部道路拓扑向量的夹角。
5.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤4中，所述的根据当前轨迹点的有效综合相似性提取变化轨迹点，具体为：比较当前轨迹点的有效综合相似性和相似性阈值的大小，若有效综合相似性小于相似性阈值，该当前轨迹点为变化轨迹点，相似性阈值根据实验验证确定。
6.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤4中，所述的获得包括变化轨迹点的轨迹拓扑边界点，具体为：将轨迹点匹配到拓扑路段，记录各轨迹点匹配的拓扑路段编号；
依次比较相邻轨迹点匹配的拓扑路段编号，若匹配的拓扑路段编号不同，或其中之一轨迹点匹配到拓扑路段而另一轨迹点未匹配到拓扑路段，则该相邻轨迹点为轨迹拓扑边界点；
7.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤4中，所述的根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系，包括：当包含变化轨迹点的轨迹拓扑边界点Ge1、Ge2均能匹配到拓扑路段，记录匹配到的拓扑路段编号RID1、RID2，若轨迹拓扑边界点Ge1记录的时间先于轨迹拓扑边界点Ge2记录的时间，构建变化轨迹点局部范围内的新道路拓扑关系RID1→RID2。
8.如权利要求1所述的基于GPS时空轨迹的路网拓扑变化自动检测方法，其特征是：步骤4中，所述的根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系，包括：当包含变化轨迹点的轨迹拓扑边界点Ge3、Ge4只有轨迹拓扑边界点Ge3匹配到拓扑路段，记录匹配到的拓扑路段编号RID3，轨迹拓扑边界点Ge4对应新增拓扑路段RID4；若轨迹拓扑边界点Ge3记录的时间先于轨迹拓扑边界点Ge4记录的时间，构建变化轨迹点局部范围内的新道路拓扑关系RID3→RID4。
9.一种基于GPS时空轨迹的道路变化自动检测方法，其特征是，包括：根据权利要求1所获得的路网拓扑变化获得对应的道路变化，具体为：拓扑点增加和拓扑点不变的拓扑路段增加对应的道路变化类型为道路新增；
道路属性设置Tag字段，但有轨迹点经过该道路时，Tag字段加1，当预设时段后Tag字段保持不变，这种情况对应的道路变化类型为道路删除；
图形路段没有变化前提下，拓扑连通关系增加和删除对应的道路变化类型为路网连通与转向变化。
10.一种基于GPS时空轨迹的路网拓扑变化自动检测系统，其特征是，包括：①局部时空轨迹向量构建模块，用来基于GPS时空轨迹构建局部时空轨迹向量，本模块进一步包括：第一向量构建子模块，用来以当前轨迹点的上一时刻轨迹点为起点、当前轨迹点为终点，构建第一向量；
第二向量构建子模块，用来以当前轨迹点为起点、当前轨迹点的下一时刻轨迹点为终点，构建第二向量；
局部时空轨迹向量构建子模块，用来将第一向量与第二向量的合向量平移至以当前轨迹点为起点，即当前轨迹点的局部时空轨迹向量；
②局部道路拓扑向量构建模块，用来基于路网数据和GPS时空轨迹构建局部道路拓扑向量，本模块进一步包括：面状缓冲区构建子模块，用来获得当前轨迹点及其上一时刻轨迹点、下一时刻轨迹点的最小包围矩形，构建最小包围矩形的面状缓冲区；
局部拓扑路段构建子模块，用来将面状缓冲区中属于同一拓扑路段且连续的图形路段作为一条局部拓扑路段，其他图形路段本身分别作为局部拓扑路段，局部拓扑路段方向同其来源的拓扑路段；
局部道路拓扑向量构建子模块，用来从局部拓扑路段的起点指向终点的向量即当前轨迹点的局部道路拓扑向量；
③相似性度量模块，用来局部时空轨迹向量和局部道路拓扑向量的相似性度量，具体为：获得当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的综合相似性S，S＝λSDis+(1-λ)SAng，以综合相似性最大值为有效综合相似性；SDis、SAng分别表示局部时空轨迹向量和局部道路拓扑向量的距离相似性、方向相似性，λ、(1-λ)为权值，根据实验验证确定；
④道路拓扑关系构建模块，用来提取变化轨迹点，并构建变化轨迹点局部范围的道路拓扑关系，本模块进一步包括：变化轨迹点提取子模块，用来根据当前轨迹点的有效综合相似性提取变化轨迹点；
轨迹拓扑边界点提取子模块，用啦获得包括变化轨迹点的轨迹拓扑边界点，轨迹拓扑边界点即(1)匹配到不同拓扑路段的相邻轨迹点，或(2)一个匹配到拓扑路段、另一个未匹配到拓扑路段的相邻轨迹点；
路拓扑关系构建子模块，用来根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系；
⑤路网拓扑变化检测模块，用来将变化轨迹点局部范围的道路拓扑关系和原始路网对比，获得路网拓扑变化。
基于GPS时空轨迹的路网拓扑变化自动检测方法及系统
技术领域
[0001] 本发明涉及一种基于GPS时空轨迹的路网拓扑变化自动检测方法及系统，属于地理信息系统与智能交通研究领域。
背景技术
[0002] 传统道路变化检测方法，根据所使用数据源的不同，主要分为三种：影像与影像比较的变化检测、影像与矢量比较的变化检测、矢量与矢量比较的变化检测三种，这三种方法都是通过前后两期地图数据对比检测到路网数据的变化，往往具有数据获取周期长、成本高，检测算法复杂、计算难度大、检测时间长、检测效果差等缺点。
[0003] 城市道路变化主要有城市道路的新建、改建、废弃等类型，道路新建就是增加道路，增加路网拓扑关系；道路废弃就是删除道路，减少路网拓扑关系；而道路改建是道路的拓宽或变窄，如果没有改变道路的拓扑关系，对于现有非车道级的道路变化检测来说，不需要进行道路数据更新。因此，道路变化检测的本质是路网拓扑变化检测，通过检测路网的拓扑变化实现路网变化检测。
[0004] 安装GPS的出租车每天行驶在城市大街小巷，GPS时空轨迹遍布城市任何道路和路段，是一种采集成本低、时效性强且蕴含丰富道路信息的数据源。目前国内一些学者提出利用出租车GPS时空轨迹进行道路变化检测，但由于城市GPS数据精度低、城市路网结构复杂，严重地影响了匹配效果和变化检测结果，最终的变化检测结果不理想。
发明内容
[0005] 针对现有技术存在的不足，本发明提供了一种成本低廉、高效、检测精度高的基于GPS时空轨迹的路网拓扑变化自动检测方法及系统。
[0006] 为了解决上述技术问题，本发明采用如下的技术方案：
[0007] 一、基于GPS时空轨迹的路网拓扑变化自动检测方法，包括步骤：
[0008] 步骤1，基于GPS时空轨迹构建局部时空轨迹向量：
[0009] 以当前轨迹点的上一时刻轨迹点为起点、当前轨迹点为终点，构建向量
[0010] 以当前轨迹点为起点、当前轨迹点的下一时刻轨迹点为终点，构建向量
[0011] 将 与 的合向量平移至以当前轨迹点为起点，即当前轨迹点的局部时空轨迹向量；
[0012] 步骤2，基于路网数据和GPS时空轨迹构建局部道路拓扑向量：
[0013] 获得当前轨迹点及其上一时刻轨迹点、下一时刻轨迹点的最小包围矩形，构建最小包围矩形的面状缓冲区；
[0014] 将面状缓冲区中属于同一拓扑路段且连续的图形路段作为一条局部拓扑路段，其他图形路段本身分别作为局部拓扑路段，局部拓扑路段方向同其来源的拓扑路段；
[0015] 从局部拓扑路段的起点指向终点的向量即当前轨迹点的局部道路拓扑向量；
[0016] 步骤3，局部时空轨迹向量和局部道路拓扑向量的相似性度量：
[0017] 获得当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的综合相似性S，S＝λ·SDis+(1-λ)·SAng，以综合相似性最大值为有效综合相似性；SDis、SAng分别表示局部时空轨迹向量和局部道路拓扑向量的距离相似性、方向相似性，λ、(1-λ)为权值，根据实验验证确定；
[0018] 步骤4，提取变化轨迹点，并构建变化轨迹点局部范围的道路拓扑关系：
[0019] 根据当前轨迹点的有效综合相似性提取变化轨迹点；
[0020] 获得包括变化轨迹点的轨迹拓扑边界点，轨迹拓扑边界点即(1)匹配到不同拓扑路段的相邻轨迹点，或(2)一个匹配到拓扑路段、另一个未匹配到拓扑路段的相邻轨迹点；
[0021] 根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系；
[0022] 步骤5，将变化轨迹点局部范围的道路拓扑关系和原始路网对比，获得路网拓扑变化。
[0023] 步骤2中，所述的面状缓冲区大小为城市街区平均宽度。
[0024] 步骤3中，当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的距离相似性其中：
[0025] 局部时空轨迹向量起点到面状缓冲区四个顶点距离的最大值即距离阈值DTH；
[0026] i表示候选图形路段编号，n表示候选图形路段数量；
[0027] 当局部时空轨迹向量起点到候选图形路段i的垂足在候选图形路段上时，Di为局部时空轨迹向量起点到候选图形路段i的距离；当局部时空轨迹向量起点到候选图形路段i的垂足不在候选图形路段上时，局部时空轨迹向量起点到候选图形路段i两端点的距离较小值即Di；
[0028] 所述的候选图形路段即进行相似性度量的局部道路拓扑向量对应的图形路段。
[0029] 步骤3中，当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的方向相似性SAng为：
[0030] SAng＝|cos(θi,j)|
[0031] 其中，θi,j为局部时空轨迹向量与局部道路拓扑向量的夹角。
[0032] 步骤4中，所述的根据当前轨迹点的有效综合相似性提取变化轨迹点，具体为：
[0033] 比较当前轨迹点的有效综合相似性和相似性阈值的大小，若有效综合相似性小于相似性阈值，该当前轨迹点为变化轨迹点，相似性阈值根据实验验证确定。
[0034] 步骤4中，所述的获得包括变化轨迹点的轨迹拓扑边界点，具体为：
[0035] 将轨迹点匹配到拓扑路段，记录各轨迹点匹配的拓扑路段编号；
[0036] 依次比较相邻轨迹点匹配的拓扑路段编号，若匹配的拓扑路段编号不同，或其中之一轨迹点匹配到拓扑路段而另一轨迹点未匹配到拓扑路段，则该相邻轨迹点为轨迹拓扑边界点；
[0037] 找出包含变化轨迹点的轨迹拓扑边界点。
[0038] 步骤4中，所述的根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系，包括：
[0039] 当包含变化轨迹点的轨迹拓扑边界点Ge1、Ge2均能匹配到拓扑路段，记录匹配到的拓扑路段编号RID1、RID2，若轨迹拓扑边界点Ge1记录的时间先于轨迹拓扑边界点Ge2记录的时间，构建变化轨迹点局部范围内的新道路拓扑关系RID1→RID2。
[0040] 步骤4中，所述的根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系，包括：
[0041] 当包含变化轨迹点的轨迹拓扑边界点Ge3、Ge4只有轨迹拓扑边界点Ge3匹配到拓扑路段，记录匹配到的拓扑路段编号RID3，轨迹拓扑边界点Ge4对应新增拓扑路段RID4；若轨迹拓扑边界点Ge3记录的时间先于轨迹拓扑边界点Ge4记录的时间，构建变化轨迹点局部范围内的新道路拓扑关系RID3→RID4。
[0042] 二、一种基于GPS时空轨迹的道路变化自动检测方法，包括：
[0043] 根据路网拓扑变化获得对应的道路变化，具体为：
[0044] 拓扑点增加和拓扑点不变的拓扑路段增加对应的道路变化类型为道路新增；
[0045] 道路属性设置Tag字段，但有轨迹点经过该道路时，Tag字段加1，当预设时段后Tag字段保持不变，这种情况对应的道路变化类型为道路删除；
[0046] 图形路段没有变化前提下，拓扑连通关系增加和删除对应的道路变化类型为路网连通与转向变化。
[0047] 三、一种基于GPS时空轨迹的路网拓扑变化自动检测系统，包括：
[0048] ①局部时空轨迹向量构建模块，用来基于GPS时空轨迹构建局部时空轨迹向量，本模块进一步包括：
[0049] 第一向量构建子模块，用来以当前轨迹点的上一时刻轨迹点为起点、当前轨迹点为终点，构建向量
[0050] 第二向量构建子模块，用来以当前轨迹点为起点、当前轨迹点的下一时刻轨迹点为终点，构建向量
[0051] 局部时空轨迹向量构建子模块，用来将 与 的合向量平移至以当前轨迹点为起点，即当前轨迹点的局部时空轨迹向量；
[0052] ②局部道路拓扑向量构建模块，用来基于路网数据和GPS时空轨迹构建局部道路拓扑向量，本模块进一步包括：
[0053] 面状缓冲区构建子模块，用来获得当前轨迹点及其上一时刻轨迹点、下一时刻轨迹点的最小包围矩形，构建最小包围矩形的面状缓冲区；
[0054] 局部拓扑路段构建子模块，用来将面状缓冲区中属于同一拓扑路段且连续的图形路段作为一条局部拓扑路段，其他图形路段本身分别作为局部拓扑路段，局部拓扑路段方向同其来源的拓扑路段；
[0055] 局部道路拓扑向量构建子模块，用来从局部拓扑路段的起点指向终点的向量即当前轨迹点的局部道路拓扑向量；
[0056] ③相似性度量模块，用来局部时空轨迹向量和局部道路拓扑向量的相似性度量，具体为：获得当前轨迹点的局部时空轨迹向量和局部道路拓扑向量的综合相似性S，S＝λ·SDis+(1-λ)·SAng，以综合相似性最大值为有效综合相似性；SDis、SAng分别表示局部时空轨迹向量和局部道路拓扑向量的距离相似性、方向相似性，λ、(1-λ)为权值，根据实验验证确定；
[0057] ④道路拓扑关系构建模块，用来提取变化轨迹点，并构建变化轨迹点局部范围的道路拓扑关系，本模块进一步包括：
[0058] 变化轨迹点提取子模块，用来根据当前轨迹点的有效综合相似性提取变化轨迹点；
[0059] 轨迹拓扑边界点提取子模块，用啦获得包括变化轨迹点的轨迹拓扑边界点，轨迹拓扑边界点即(1)匹配到不同拓扑路段的相邻轨迹点，或(2)一个匹配到拓扑路段、另一个未匹配到拓扑路段的相邻轨迹点；
[0060] 路拓扑关系构建子模块，用来根据包含变化轨迹点的轨迹拓扑边界点反映的路网拓扑连通关系，构建变化轨迹点局部范围的道路拓扑关系；
[0061] ⑤路网拓扑变化检测模块，用来将变化轨迹点局部范围的道路拓扑关系和原始路网对比，获得路网拓扑变化。
[0062] 本发明首先针对GPS时空轨迹构建局部时空轨迹向量，再根据局部时空轨迹向量和路网数据构建局部道路拓扑向量，并度量局部时空轨迹向量局部道路拓扑向量的相似性，设定阈值提取相似性小于阈值的轨迹点，即可能采集于变化道路的变化轨迹点。构建变化轨迹点局部范围内的道路拓扑，将变化轨迹点局部范围内的道路拓扑与原有道路拓扑对比，得到路网拓扑和图形变化。
[0063] 和现有技术相比，本发明具有如下优点和有益效果：
[0064] 本发明基于GPS时空轨迹体现的道路拓扑信息，在提高路网变化检测精度的同时，还可实现路网拓扑和路网图形的变化检测；另外，本发明还具有成本低廉和高效的优点。
附图说明
[0065] 图1是本发明的具体流程图；
[0066] 图2是基于GPS时空轨迹的局部时空轨迹向量的构建示意图；
[0067] 图3是局部道路拓扑向量的构建示意图；
[0068] 图4是局部时空轨迹向量起点到面状缓冲区边界的最远距离示意图；
[0069] 图5是局部时空轨迹向量与局部拓扑向量的方向相似性度量示意图；
[0070] 图6是轨迹拓扑边界点示意图，其中，图(a)为轨迹拓扑边界点示意图，图(b)～(d)分别为三种不同的轨迹拓扑边界点；
[0071] 图7是本发明实施化轨迹点提取示意图；
[0072] 图8是本发明实施例变化轨迹点拓扑构建结果。
具体实施方式
[0073] 本发明可利用车载GPS实现，本发明本质是：通过车载GPS时空轨迹所体现的道路拓扑关系与电子地图体现的道路拓扑关系进行对比得到路网拓扑变化，进而实现路网拓扑的变化检测。目前国内出租车GPS每天行驶在城市大街小巷，GPS时空轨迹遍布城市任何道路和路段，出租车GPS采集的GPS时空轨迹数据可以在短时间内遍布城市的任何道路和路段，通过分析GPS时空轨迹的拓扑性质，并与现有电子地图道路拓扑关系进行对比，可以完成路网拓扑变化检测。本发明还建立了拓扑检测结果与道路变化类型的对应关系，通过这种对应关系完成路网的变化检测。由于车载GPS数据成本低、获取周期短，利用基于GPS时空轨迹的路网拓扑自动变化检测可以实现路网的实时自动变化检测。
[0074] 本发明可采用计算机软件方式支持自动运行流程，以下结合实施例和附图详细说明本发明技术方案。
[0075] 参见图1，本发明实施例提供的技术方案包括如下步骤：
[0076] 步骤1，基于GPS时空轨迹构建局部时空轨迹向量。
[0077] 现有的基于GPS时空轨迹的局部时空轨迹向量构建方法，都是将当前轨迹点作为向量起点、当前轨迹点的下一时刻轨迹点作为向量终点而构建。这种方法构建的局部时空轨迹向量的准确性易受GPS单点定位精度影响。
[0078] 为了减少GPS单点定位精度带来的影响，本发明提出一种全新的基于GPS时空轨迹的局部时空轨迹向量构建方法，具体为：按照GPS时空轨迹点的时间顺序，以当前轨迹点的上一时刻轨迹点为起点，以当前轨迹点为终点，构建轨迹向量，记为 以当前轨迹点为起点，以当前轨迹点的下一时刻轨迹点为终点，构建轨迹向量，记为 将向量 与向量的合向量平移至以当前轨迹点为起点，即为构建的当前轨迹点的局部时空轨迹向量[0079] 见图2，Gi、Gi-1、Gi-2分别表示当前轨迹点的下一时刻轨迹点、当前轨迹点、当前轨迹点的上一时刻轨迹点， 即构建的当前轨迹点的局部时空轨迹向量。
[0080] 步骤2，基于路网数据和GPS时空轨迹构建局部道路拓扑向量。
[0081] 构建局部道路拓扑向量时，为得到与局部时空轨迹向量最为相似的道路向量，提高向量相似性度量的准确性，本发明首次提出局部道路拓扑向量的构建方法，具体包括：
[0082] 2.1构建面状缓冲区。
[0083] 构建当前轨迹点、当前轨迹点的上一时刻轨迹点、当前轨迹点的下一时刻轨迹点的最小包围矩形的面状缓冲区。即，将最小包围矩形的长和宽分别增加预设值，从而获得最小包围矩形的面状缓冲区，这里预设值即面状缓冲区大小。
[0084] 构建面状缓冲区时，为保证路网未变化情况下面状缓冲区内存在正确的局部道路拓扑向量，所以面状缓冲区大小不能过大；同时在路网发生变化情况下，可以通过面状缓冲区内未构建的局部道路拓扑向量来判断新增的路网，因此面缓冲区大小不能过小。面缓冲区大小通常设为城市街区的平均宽度
[0085] 2.2构建局部拓扑路段。
[0086] 根据面状缓冲区内的道路动态构建局部拓扑路段。针对面状缓冲区内所有图形路段构建局部拓扑路段，将属于同一拓扑路段且连续的图形路段作为一条局部拓扑路段，其他图形路段本身分别作为局部拓扑路段。例如，拓扑路段A由于连续的图形路段1、2、3、4、5组成，其中图形路段1、2和5落入面状缓冲区，那么，图形路段1和2构成一条局部拓扑路段；图像路段5构成另一条局部拓扑路段。
[0087] 局部拓扑路段即从原有拓扑路段中截取出的、与原有拓扑路段具有相同方向性的拓扑路段，局部拓扑路段的方向同其来源的拓扑路段，即局部拓扑路段起点为其来源的拓扑路段起点方向上的第一个图形路段点，局部拓扑路段终点为其来源的拓扑路段终点方向上的最后一个图形路段点。当面状缓冲区中不存在属于同一拓扑路段的连续图形路段时，则将面状缓冲区中各图形路段本身作为局部拓扑路段。
[0088] 上述图形路段指两个相邻道路图形点间的道路，是绘制路网的基本单元，图形路段仅用来表达路网形状，其没有方向。图形路段数据来源于绘制路网的mif格式文件。上述拓扑路段指两个相邻道路拓扑点间的道路，用来表达路网连通性，拓扑路段可能由一条或多条图形路段组成，具有方向性。拓扑路段数据来源于拓扑点，拓扑点即路网拓扑关系表中结点。
[0089] 2.3构建局部道路拓扑向量。
[0090] 以局部拓扑路段起点为起点、以局部拓扑路段终点为终点的向量即局部道路拓扑向量。由于电子地图中，双向通行的道路只用一条道路线来绘制，在这种情形下，虽然道路上的所有图形路段只有一条，但是拓扑路段实际有上行和下行两条。为避免这种情况，确定局部拓扑路段方向性应以原有拓扑路段方向为准。即，如果原有拓扑路段方向为双向而电子地图中只用一条道路线来表示，则局部道路拓扑具有两对起点和终点，此时构建的局部道路拓扑向量也应该为两个大小相同方向相反的向量。见图3， 即局部道路拓扑向量。
[0091] 步骤3，局部时空轨迹向量和局部道路拓扑向量的相似性度量。
[0092] 本发明通过计算局部时空轨迹向量与局部道路拓扑向量间的距离相似性与方向相似性，对距离相似性与方向相似性加权求和，得到空间位置和运动方向双重约束下的综合相似性。
[0093] 度量向量相似性过程中分别计算距离相似性SDis和方向相似性SAng，并将两相似性赋权相加得到空间位置和运动方向双重约束下的综合相似性。距离相似性SDis和方向相似性SAng均为度量向量相似性的已有技术。
[0094] 距离相似性SDis用来描述局部时空轨迹向量与局部道路拓扑向量的距离接近程度，可采用：
[0095]
[0096] 式(1)中，DTH为距离阈值；Di为与局部时空轨迹向量起点和候选图形路段i距离有关的参数，i＝1,2,...n，i表示候选图形路段编号，n表示候选图形路段数量。
[0097] 见图4，当前轨迹点Gi-1到面状缓冲区四个顶点距离的最大值即距离阈值DTH，当前轨迹点Gi-1即局部时空轨迹向量 起点。
[0098] 当局部时空轨迹向量起点到候选图形路段i的垂足在候选图形路段上时，Di为局部时空轨迹向量起点到候选图形路段i的距离。当局部时空轨迹向量起点到候选图形路段i的垂足不在候选图形路段上时，分别计算局部时空轨迹向量起点到候选图形路段i两端点的距离，较小值即Di。候选图形路段即进行相似性度量的局部道路拓扑向量对应的图形路段。局部道路拓扑向量由局部拓扑路段构建，组成局部拓扑路段的图形路段即局部道路拓扑向量对应的图形路段。
[0099] 本发明中，依次计算参数Di，i＝1,2,...n，选择所有参数Di中最小值计算当前轨迹点的局部时空轨迹向量与局部道路拓扑向量的距离相似性SDis，距离相似性SDis的取值为[0,1]。随着局部时空轨迹向量起点到候选图形路段的距离不断增大，距离相似性SDis逐渐变小。
[0100] 方向相似性SAng用来描述局部时空轨迹向量与局部道路拓扑向量的方向相似程度，可表示为：
[0101] SAng＝|cos(θi,j)| (2)
[0102] 式(2)中，θi,j表示局部时空轨迹向量与局部道路拓扑向量的夹角。
[0103] 图5显示了局部时空轨迹向量与局部道路拓扑向量的夹角示意图。方向相似性SAng的取值范围为[0,1]，当局部时空轨迹向量与局部道路拓扑向量间的夹角为0时，SAng为1；当局部时空轨迹向量与局部道路拓扑向量间的夹角为π时，SAng为0；随着局部时空轨迹向量与局部道路拓扑向量间的夹角不断增大，SAng逐渐减小。
[0104] 空间位置和运动方向双重约束下的综合相似性S为：S＝λSDis+(1-λ)SAng，其中，S为双重约束下的综合相似性，SDis和SAng分别为距离相似性和方向相似性，λ和(1-λ)分别为距离相似性与方向相似性的权值。
[0105] 对当前轨迹点进行相似性计算时，先分别计算局部时空轨迹向量与面状缓冲区内所有局部道路拓扑向量的综合相似性，选择最大值作为当前轨迹点的有效综合相似性。当面状缓冲区内没有图形路段落入时，则可判断当前轨迹点周围一定范围内没有道路，则该当前轨迹点必然采集于变化道路，此时将综合相似性大小记为“0”。
[0106] 步骤4，提取变化轨迹点，构建新路网拓扑关系。
[0107] 4.1提取变化轨迹点。
[0108] 根据当前轨迹点的有效综合相似性进行阈值判断，如果当前轨迹点的有效综合相似性S小于相似性阈值T，该当前轨迹点为变化轨迹点。
[0109] 经过多次实验验证，城市环境中，在不同的距离相似性权值下，当相似性阈值T在0.8-0.9范围内时，提取的候选变化轨迹点具有较高的正确率。经试验验证，当相似性阈值T选取为0.8-0.9，距离相似性权值选取为0.8-0.9，变化轨迹点提取正确率最高，最能体现实际道路变化情况。
[0110] 4.2轨迹拓扑边界点检测。
[0111] 轨迹拓扑边界点为本发明首次提出的概念，指某一段轨迹中反应拓扑连通关系的一对相邻轨迹点。例如，当一辆车路过十字路口时，前一时刻GPS轨迹点采集于经过交叉路口前的拓扑路段，后一时刻GPS轨迹点采集于经过交叉路口后的拓扑路段，根据轨迹的连续性可知这两个拓扑路段之间是拓扑连通的，而这两个相邻的轨迹点即为轨迹拓扑边界点。因此当两个相邻的轨迹点分别属于不同的拓扑路段时，这两个相邻轨迹点即为轨迹拓扑边界点，如图6(a)所示，轨迹中匹配到不同拓扑路段的相邻点即拓扑边界点。
[0112] 具体实施时，首先，对各轨迹点进行点到线的地图匹配，记录各轨迹点匹配的拓扑路段编号；若轨迹点不能匹配到拓扑路段，则将匹配的拓扑路段编号记为“NULL”。然后，依次对比相邻轨迹点所匹配的拓扑路段编号，若匹配到不同编号的拓扑路段，或其中一轨迹点匹配到某拓扑路段而另一轨迹点不能正确匹配，那么这两个相邻轨迹点即为轨迹拓扑边界点。
[0113] 轨迹拓扑边界点存在以下几种情形：①相邻轨迹点分别匹配到不同拓扑路段，并且两拓扑路段直接连通，见图6(b)；②相邻轨迹点分别匹配到不同拓扑路段，但两拓扑路段不直接连通，见图6(c)；③相邻轨迹点之一匹配到拓扑路段，而另一不能成功匹配，见图6(d)。
[0114] 4.3变化轨迹点局部范围内新道路拓扑构建。
[0115] 检测出变化轨迹点中的轨迹拓扑边界点，根据轨迹拓扑边界点所反映的路网拓扑连通关系可构建一定范围内新的道路拓扑关系。
[0116] 具体实施时，如果轨迹拓扑边界点对均能匹配到拓扑路段，首先，记录该对轨迹拓扑边界点Ge1、Ge2所匹配的拓扑路段编号RID1、RID2；接着，根据变化轨迹点所构建的局部时空轨迹向量的“起点-终点”方向，找到拓扑路段RID1的起点和终点分别记为PS1、PE1，找到拓扑路段RID2的起点和终点分别记为PS2、PE2。如果轨迹拓扑边界点Ge1记录的时间先于轨迹拓扑边界点Ge2记录的时间，那么局部范围内新的道路拓扑关系为RID1→RID2，该拓扑关系表示车辆可以从拓扑路段RID1行驶到拓扑路段RID2，即，一辆车行使到拓扑路段RID1的终点时，可以选择RID2作为其继续行驶的路段。而对于原始电子地图拓扑来说，拓扑表中缺少“起点为PS1终点为PE1”、“起点为PS2终点为PE2”、“起点为PE1终点为PS2”三条拓扑关系记录，导致构建的局部道路拓扑向量与轨迹向量方向相反，计算所得的综合相似性较小，而被当作变化点选取出来。所以在拓扑关系表中应该增加“起点为PS1终点为PE1”、“起点为PS2终点为PE2”、“起点为PE1终点为PS2”三条拓扑关系记录。如果轨迹拓扑边界点Ge2记录的时间先于轨迹拓扑边界点Ge1记录的时间，那么局部范围内新的道路拓扑关系为RID2→RID1，对应拓扑关系表中应该增加“起点为PE1终点为PS1”、“起点为PE2终点为PS2”、“起点为PS2终点为PE1”三条拓扑关系记录。
[0117] 如果一对轨迹拓扑边界点Ge3、Ge4中只有一个轨迹拓扑边界点Ge3能匹配到拓扑路段，那么局部范围内新道路拓扑构建分为以下几个步骤：首先，记录轨迹拓扑边界点Ge3所匹配的拓扑路段编号RID3。接着，找到拓扑路段RID3的起点和终点记为PS3、PE3，此时由于轨迹点Ge4不能匹配，所以可以确定存在新增的拓扑路段，将新增的拓扑路段记为RID4，其对应新增的起点和终点记为PS4、PE4，需要说明的是，这里的RID4为新添加的路段编号，PS4、PE4为新添加的起始点编号。
[0118] 如果轨迹拓扑边界点Ge3记录的时间先于轨迹拓扑边界点Ge4记录的时间，那么局部范围内新的道路拓扑关系为RID3→RID4，对应拓扑关系表中应该增加“起点为PS3终点为PE3”、“起点为PS4终点为PE4”、“起点为PE3终点为PS4”三条拓扑关系记录。如果轨迹拓扑边界点Ge4记录的时间先于轨迹拓扑边界点Ge3记录的时间，那么局部范围内新的道路拓扑关系为RID4→RID3，对应拓扑关系表中应该增加“起点为PE3终点为PS3”、“起点为PE4终点为PS4”、“起点为PS4终点为PE3”三条拓扑关系记录。
[0119] 步骤5，新旧拓扑对比检测路网拓扑与图形变化。
[0120] 根据轨迹拓扑边界点所匹配拓扑路段构建匹配路段新的拓扑关系，将新拓扑关系与原路网进行对比，获得路网拓扑变化。见图7，G4、G5、G6为提取出的轨迹变化点，由于G3匹配到Road1，G4无可匹配路段，则G3、G4为一对轨迹拓扑边界点。根据轨迹拓扑边界点的匹配结果构建变化轨迹点与拓扑路段间的拓扑关系，见图8，由于变化轨迹点G4、G5、G6没有匹配的拓扑路段，所以变化轨迹点应采集于新增路段Raod6，同时G3采集于路段Road1，G4采集于路段Road6，可知新增路段Road6与路段Road1拓扑连通，通过新旧拓扑对比得到一条新增的拓扑路段、一个新增拓扑点和新增的拓扑连通关系。
[0121] 路网拓扑关系变化类型有拓扑的增加、删除、修改，与其相对应的道路变化类型是道路新增、道路删除、道路修改、路网连通与转向变化4种。拓扑检测结果与道路变化类型的对应关系如下：
[0122] ①道路新增：主要表现为拓扑增加，包括拓扑点增加时拓扑路段的增加和拓扑点不变时拓扑路段增加两种情形；
[0123] ②道路的删除：道路属性中设置一个“Tag”字段，每当有轨迹点经过时给该字段+1，当一周后“Tag”字段仍未0，认为在一周内没有车辆经过该路段，则该路段为道路删除；
[0124] ③道路的修改：是指同一条拓扑路段只有部分修改的情形，包括局部路段删除和局部路段新增两个部分，在检测路段修改过程中分别检测出道路新增与道路删除通过新旧路网对比得到道路修改；
[0125] ④路网连通与转向变化：包括路段单双通行变化和转向连通性变化两种，此情形下图形路段没有变化，只有道路拓扑连通关系的增加和删除。
