基于全局合作式投票的地图匹配方法、系统、介质及终端

技术领域

本发明涉及地图匹配技术领域，特别是涉及一种基于全局合作式投票的地图匹配方法、系统、介质及终端。

背景技术

随着科技在交通领域的飞速发展，GPS设备得到了越来越广泛的应用，越来越多装有GPS设备的车辆行驶在城市道路当中；GPS数据包含经度、维度、时间戳、车辆瞬时方向及瞬时速度信息等等，包含了丰富的车辆时空行驶特性，海量的GPS数据正在逐渐的成为智能交通系统以及相关服务的数据源，依靠海量的GPS数据可以来挖掘路网的时空动态特征，为交通拥塞分析、路径还原、行驶路径推荐等等提供相应的支持。

针对地图匹配问题，国内外有大量的学者都对此进行了研究，地图匹配问题主要分为高采样率下的地图匹配和低采样率下的地图匹配，如何对在复杂城市路网下的低采样率GPS数据进行地图匹配一直一个研究的难点；在低采样率条件下，GPS含有的噪声往往较大，复杂城市道路中，特别是在含有高架道路和辅路并行的道路中，实际的路径选择与驾驶者的经验有较强的关联，现有的地图匹配算法并不能准确的反映出驾驶者实际的行驶路径。

发明内容

鉴于以上所述现有技术的缺点，本发明的目的在于提供一种基于全局合作式投票的地图匹配方法、系统、介质及终端，用于解决在复杂路网环境下，现有地图匹配轨迹存在不稳定及准确率低的问题。

为实现上述目的及其他相关目的，本发明提供一种基于全局合作式投票的地图匹配方法，包括以下步骤：生成GPS点对应的候选点集合；所述候选点集合中包括至少一候选点；对所述候选点变迁进行多特征路径分析，获取所述候选点的合理变迁路径；对所述合理变迁路径进行修正，并基于全局合作式投票算法，获取全局最优匹配路径。

于本发明的一实施例中，生成GPS点对应的候选点集合包括以下步骤：获取待匹配的GPS轨迹数据；所述GPS轨迹数据包括至少一所述GPS点；对所述GPS轨迹数据进行预处理，获取预处理后的数据；获取空间路网数据；将所述预处理后的数据与所述空间路网数据进行整合，以将所述GPS点映射到道路上，计算出所述候选点集合。

于本发明的一实施例中，对所述GPS轨迹数据进行预处理包括：对所述GPS轨迹数据进行截断阈值聚类处理；其中，对所述GPS轨迹数据进行截断阈值聚类处理包括以下步骤：根据预设截断阈值和所述GPS轨迹数据，计算噪声集合；所述噪声集合中任意两个所述GPS点之间的欧式距离小于所述预设截断阈值；保留所述噪声集合中临近密度最大的点，将所述噪声集合中除所述临近密度最大的点以外的点视为噪声点，并进行去除。

于本发明的一实施例中，对所述候选点变迁进行多特征路径分析，获取所述候选点的合理变迁路径包括以下步骤：根据所述GPS点对应的所述候选点集合，计算任意两个连续候选点在路网中的最短路径，并将所述最短路径作为当前所述任意两个连续候选点的变迁路径；基于所述候选点，获取候选点变迁图；根据所述候选点变迁图中，每一对连续候选点变迁的时空数据，计算空间特征和时间特征；根据所述空间特征和所述时间特征，获取所述变迁路径的时空特征，以基于所述时空特征，产生两个连续GPS点的所有候选点变迁路径的时空特征分布图；计算所述时空特征分布图中相邻两个点的时空特征之间的差值；对所述差值利用箱线图异常点检测方法识别出分割点，以提取出时空特征函数最高的区域，获取所述合理变迁路径。

于本发明的一实施例中，根据所述空间特征和所述时间特征，获取所述变迁路径的时空特征包括以下步骤：对于所述空间特征，进行地理误差分析，定量描述所述候选点在空间层面的可能性，以获取空间相似度；对于所述时间特征，计算所述候选点变迁路径中，每条道路的限速值与所述GPS点之间平均速度的相似度，以获取时间相似度；对所述时间相似度和所述空间相似度做乘积运算，并将所述乘积运算的结果作为所述时空特征。

于本发明的一实施例中，对所述合理变迁路径进行修正包括以下步骤；将所述合理变迁路径按照不同的道路等级分割成不同的片段；确定所述合理变迁路径的修正因子，以基于所述修正因子对所述合理变迁路径进行修正；所述修正因子表示为：

其中，TMF(cp)表示合理变迁路径cp对应的修正因子；len(cp)表示合理变迁路径cp的长度；NRB(cp)表示对应合理变迁路径cp，分割片段的个数；

于本发明的一实施例中，将所述局部最优路径作为所述修正后的合理变迁路径；基于全局合作式投票算法，获取全局最优匹配路径包括以下步骤：对于预设匹配窗口和所述局部最优路径，定义静态矩阵；所述静态矩阵表示为：

其中，

基于权重的静态投票矩阵表示为：

其中，

本发明提供一种基于全局合作式投票的地图匹配系统，包括：生成模块、分析模块及获取模块；所述生成模块用于生成GPS点对应的候选点集合；所述候选点集合中包括至少一候选点；所述分析模块用于对所述候选点变迁进行多特征路径分析，获取所述候选点的合理变迁路径；所述获取模块用于对所述合理变迁路径进行修正，并基于全局合作式投票算法，获取全局最优匹配路径。

本发明提供一种存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现上述的基于全局合作式投票的地图匹配方法。

本发明提供一种终端，包括：处理器及存储器；所述存储器用于存储计算机程序；所述处理器用于执行所述存储器存储的计算机程序，以使所述终端执行上述的基于全局合作式投票的地图匹配方法。

如上所述，本发明所述的基于全局合作式投票的地图匹配方法、系统、介质及终端，具有以下有益效果：

(1)与现有技术相比，本发明提供了一种改进的基于合作式投票的地图匹配算法，解决了在高架道路与地面道路共存的复杂路况下，地图匹配轨迹的不稳定问题，提高了地图匹配的准确率。

(2)本发明通过对GPS轨迹当中的噪声以及候选点转移路径中不合理的情况进行剔除，保证地图匹配准确率的同时，减少了处理时间和系统的压力，使得改进后的地图匹配算法更加适用于低采样率条件下的城市复杂路网。

附图说明

图1显示为本发明的基于全局合作式投票的地图匹配方法于一实施例中的流程图。

图2显示为本发明的生成GPS点对应的候选点集合于一实施例中的流程图。

图3显示为本发明的对GPS轨迹数据进行截断阈值聚类处理于一实施例中的流程图。

图4显示为本发明的GPS轨迹数据未经截断阈值聚类处理前于一实施例中的效果显示图。

图5显示为本发明的GPS轨迹数据经截断阈值聚类处理后于一实施例中的效果显示图。

图6显示为本发明的对候选点变迁进行多特征路径分析，获取候选点的合理变迁路径于一实施例中的流程图。

图7显示为本发明的候选点变迁图于一实施例中的结构示意图。

图8显示为本发明的根据空间特征和时间特征，获取变迁路径的时空特征于一实施例中的流程图。

图9显示为本发明的时空特征分布图于一实施例中的结构示意图。

图10显示为本发明的基于箱线图分割点检测于一实施例中的结构示意图。

图11显示为本发明的对合理变迁路径进行修正，并基于全局合作式投票算法，获取全局最优匹配路径于一实施例中的流程图。

图12显示为本发明的基于权重矩阵投票算法于一实施例中的结构示意图。

图13显示为本发明的基于全局合作式投票的地图匹配系统于一实施例中的结构示意图。

图14显示为本发明的终端于一实施例中的结构示意图。

标号说明

131 生成模块

132 分析模块

133 获取模块

141 处理器

142 存储器

S1～S3 步骤

S12～S14 步骤

S121～S122 步骤

S21～S26 步骤

S241～S243 步骤

S31～S34 步骤

具体实施方式

以下通过特定的具体实施例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需说明的是，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。

需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，遂图示中仅显示与本发明中有关的组件而非按照实际实施时的组件数目、形状及尺寸绘制，其实际实施时各组件的型态、数量及比例可为一种随意的改变，且其组件布局型态也可能更为复杂。

本发明的基于全局合作式投票的地图匹配方法、系统、介质及终端，与现有技术相比，本发明提供了一种改进的基于合作式投票的地图匹配算法，解决了在高架道路与地面道路共存的复杂路况下，地图匹配轨迹的不稳定问题，提高了地图匹配的准确率；本发明通过对GPS轨迹当中的噪声以及候选点转移路径中不合理的情况进行剔除，保证地图匹配准确率的同时，减少了处理时间和系统的压力，使得改进后的地图匹配算法更加适用于低采样率条件下的城市复杂路网。

如图1所示，于一实施例中，本发明的基于全局合作式投票的地图匹配方法包括以下步骤：

步骤S1、生成GPS点对应的候选点集合。

需要说明的是，所述候选点集合中包括至少一候选点。

如图2所示，于一实施例中，生成GPS点对应的候选点集合包括以下步骤：

步骤S11、获取待匹配的GPS轨迹数据。

需要说明的是，所述GPS轨迹数据包括至少一所述GPS点。

进一步地，由于在低采样率的条件下原始的GPS轨迹数据存在噪声，收集到的GPS轨迹数据的空间位置坐标与实际的位置有偏差，因此，需要对原始的GPS轨迹数据进行地图匹配预处理，将收集到的GPS点匹配到相应的道路上。

步骤S12、对所述GPS轨迹数据进行预处理，获取预处理后的数据。

于一实施例中，对所述GPS轨迹数据进行预处理包括对所述GPS轨迹数据进行截断阈值聚类处理。

需要说明的是，由于在交通拥塞的情况下，GPS轨迹数据往往在空间上呈现聚集的状态，为了减轻聚集数据对地图匹配过程的影响，充分利用GPS轨迹数据的分布规律，提出了截断阈值的聚类算法，将该GPS轨迹数据进行过滤。

如图3所示，于一实施例中，对所述GPS轨迹数据进行截断阈值聚类处理包括以下步骤：

步骤S121、根据预设截断阈值和所述GPS轨迹数据，计算噪声集合。

需要说明的是，所述噪声集合中任意两个所述GPS点之间的欧式距离小于所述预设截断阈值。

需要说明的是，该预设截断阈值具体为何值不作为限制本发明的条件，所以，在此也不对其数值进行明确限定。

步骤S122、保留所述噪声集合中临近密度最大的点，将所述噪声集合中除所述临近密度最大的点以外的点视为噪声点，并进行去除。

具体地，将该噪声集合中的GPS数据看作是包含重复信息的数据，从该噪声集合中选择临近密度最大的点作为代表性的点，而除该临近密度最大的点以外的点视为噪声点，去除该噪声点。

如图4所示，显示为于一实际应用场景中的GPS轨迹数据(未经截断阈值聚类处理)；如图5所示，显示为经截断阈值聚类算法对图4中的GPS轨迹数据处理后的结果；由图4可知，经截断阈值聚类算法处理前的数据，在容易发生拥堵的路口附近GPS点往往积聚在一起。

步骤S13、获取空间路网数据。

步骤S14、将所述预处理后的数据与所述空间路网数据进行整合，以将所述GPS点映射到道路上，计算出所述候选点集合。

步骤S2、对所述候选点变迁进行多特征路径分析，获取所述候选点的合理变迁路径。

如图6所示，于一实施例中，结合所述候选点进行多特征路径分析，获取所述候选点的合理变迁路径包括以下步骤：

步骤S21、根据所述GPS点对应的所述候选点集合，计算任意两个连续候选点在路网中的最短路径，并将所述最短路径作为当前所述任意两个连续候选点的变迁路径。

步骤S22、基于所述候选点，获取候选点变迁图。

如图7所示，显示为一候选点变迁图于一实施例中的结构示意图。

步骤S23、根据所述候选点变迁图中，每一对连续候选点变迁的时空数据，计算空间特征和时间特征。

步骤S24、根据所述空间特征和所述时间特征，获取所述变迁路径的时空特征，以基于所述时空特征，产生两个连续GPS点的所有候选点变迁路径的时空特征分布图。

如图8所示，于一实施例中，根据所述空间特征和所述时间特征，获取所述变迁路径的时空特征包括以下步骤：

步骤S241、对于所述空间特征，进行地理误差分析，定量描述所述候选点在空间层面的可能性，以获取空间相似度。

具体地，对于空间特征的提取主要包含地理误差分析，从而定量描述候选点在空间层面的可能性。

需要说明的是，通常，GPS坐标点与候选点的距离的分布情况服从均值为0，方差为θ的高斯分布。

步骤S242、对于所述时间特征，计算所述候选点变迁路径中，每条道路的限速值与所述GPS点之间平均速度的相似度，以获取时间相似度。

步骤S243、对所述时间相似度和所述空间相似度做乘积运算，并将所述乘积运算的结果作为所述时空特征。

需要说明的是，经步骤S243获取变迁路径的时空特征之后，因为每两个连续GPS点对应的多对候选点之间的变迁路径当中存在很多不合理的情况，为了进一步缩小变迁路径的数量，提高处理速度与准确率，于本发明中，提出了统计特征分析算法。

如图9所示，显示为时空特征分布图于一实施例中的结构示意图，该图描绘了某个连续GPS点的所有候选点变迁路径的时空特征分布情况，可以看出，不同候选点变迁路径的时空特征分布呈现出一种区域分段特点，即不同候选点变迁路径的时空特征函数值往往聚集在几个固定的值，而具有较高的时空特征的候选点变迁往往代表实际的情况，所以图9内圆圈中包含的候选点变迁就代表需要保留的转移情况，据此，可以执行下述步骤S25至步骤S26。

步骤S25、计算所述时空特征分布图中相邻两个点的时空特征之间的差值。

步骤S26、对所述差值利用箱线图异常点检测方法识别出分割点，以提取出时空特征函数最高的区域，获取所述合理变迁路径。

具体地，如图10所示，显示为基于箱线图分割点检测于一实施例中的结构示意图。

需要说明的是，在城市复杂路网当中，特别是高架道路与地面道路并行的路况下，传统的地图匹配算法容易出现在二者之间频繁切换以及长时间位于地面道路的不合理情况，这与实际的驾驶行为习惯不符；于本发明中，为了解决这个问题，从实际驾驶行为出发，提出了路径修正因子，来对待匹配的路径进行进一步的筛选；具体地，参见下述内容。

步骤S3、对所述合理变迁路径进行修正，并基于全局合作式投票算法，获取全局最优匹配路径。

如图11所示，于一实施例中，对所述合理变迁路径进行修正包括以下步骤；

步骤S31、将所述合理变迁路径按照不同的道路等级分割成不同的片段。

诸如，对于合理变迁路径cp＝{r

步骤S32、确定所述合理变迁路径的修正因子，以基于所述修正因子对所述合理变迁路径进行修正。

具体地，所述修正因子表示为：

其中，TMF(cp)表示合理变迁路径cp对应的修正因子；len(cp)表示合理变迁路径cp的长度；NRB(cp)表示对应合理变迁路径cp，分割片段的个数；

于一实施例中，将所述局部最优路径作为所述修正后的合理变迁路径。

需要说明的是，在传统的交互式投票算法当中，在给定的窗口范围内，枚举每一个候选点作为强制通过的点，利用上述方法得到局部最优路径之后，遍历该路径，将每个候选点变迁的票数加一，最终将具有最大累计票数的路径作为全局最优匹配路径；这种方法不仅在时间上开销比较大，而且并没有充分的利用全局的上下文信息，对于不同的地图匹配窗口来说，每个候选点变迁具有的上下文信息是不同的，靠近窗口尾部的候选点转移路径由于涵盖之前的地图匹配信息，所以，在该候选点变迁上记录的投票值具有更高价值，而对于靠近匹配窗口头部的候选点变迁涵盖更少的前文地图匹配信息，所以在该候选点变迁上记录的投票具有较小的价值。

于本发明中，根据上述问题提出了如下的改进方法：

如图11所示，于一实施例中，基于全局合作式投票算法，获取全局最优匹配路径包括以下步骤：

步骤S33、对于预设匹配窗口和所述局部最优路径，定义静态矩阵。

所述静态矩阵表示为：

其中，

基于权重的静态投票矩阵表示为：

步骤S34、利用回溯算法对经过权重处理的投票矩阵进行计算，获取所述全局最优匹配路径。

需要说明的是，对于GPS轨迹当中的末端来说，由于缺少后续的上下文信息，该GPS点在路网当中的映射点可以单独的利用空间信息进行判断。

如图12所示，展示了一个窗口大小为4，匹配窗口为T[0]、T[1]、T[2]、T[3]的基于权重矩阵投票算法的实际情况，最终，路径①表示具有最大累计投票值的全局最优匹配路径。

需要说明的是，本发明所述的基于全局合作式投票的地图匹配方法的保护范围不限于本实施例列举的步骤执行顺序，凡是根据本发明的原理所做的现有技术的步骤增减、步骤替换所实现的方案都包括在本发明的保护范围内。

如图13所示，于一实施例中，本发明的基于全局合作式投票的地图匹配系统包括生成模块131、分析模块132及获取模块133。

所述生成模块131用于生成GPS点对应的候选点集合。

需要说明的是，所述候选点集合中包括至少一候选点。

所述分析模块132用于对所述候选点变迁进行多特征路径分析，获取所述候选点的合理变迁路径。

所述获取模块133用于对所述合理变迁路径进行修正，并基于全局合作式投票算法，获取全局最优匹配路径。

需要说明的是，所述生成模块131、所述分析模块132及所述获取模块133的结构及原理与上述基于全局合作式投票的地图匹配方法中的步骤一一对应，故在此不再赘述。

需要说明的是，应理解以上系统的各个模块的划分仅仅是一种逻辑功能的划分，实际实现时可以全部或部分集成到一个物理实体上，也可以物理上分开。且这些模块可以全部以软件通过处理元件调用的形式实现；也可以全部以硬件的形式实现；还可以部分模块通过处理元件调用软件的形式实现，部分模块通过硬件的形式实现。例如，x模块可以为单独设立的处理元件，也可以集成在上述系统的某一个芯片中实现，此外，也可以以程序代码的形式存储于上述系统的存储器中，由上述系统的某一个处理元件调用并执行以上x模块的功能。其它模块的实现与之类似。此外这些模块全部或部分可以集成在一起，也可以独立实现。这里所述的处理元件可以是一种集成电路，具有信号的处理能力。在实现过程中，上述方法的各步骤或以上各个模块可以通过处理器元件中的硬件的集成逻辑电路或者软件形式的指令完成。

例如，以上这些模块可以是被配置成实施以上方法的一个或多个集成电路，例如：一个或多个特定集成电路(Application Specific Integrated Circuit，简称ASIC)，或，一个或多个数字信号处理器(Digital Signal Processor，简称DSP)，或，一个或者多个现场可编程门阵列(Field Programmable Gate Array，简称FPGA)等。再如，当以上某个模块通过处理元件调度程序代码的形式实现时，该处理元件可以是通用处理器，例如中央处理器(Central Processing Unit，简称CPU)或其它可以调用程序代码的处理器。再如，这些模块可以集成在一起，以片上系统(System-On-a-Chip，简称SOC)的形式实现。

本发明的存储介质上存储有计算机程序，该计算机程序被处理器执行时实现上述的基于全局合作式投票的地图匹配方法。所述存储介质包括：ROM、RAM、磁碟、U盘、存储卡或者光盘等各种可以存储程序代码的介质。

如图14所示，本发明的终端包括处理器141及存储器142。

所述存储器142用于存储计算机程序；具体来说，所述存储器142包括：ROM、RAM、磁碟、U盘、存储卡或者光盘等各种可以存储程序代码的介质。

所述处理器141与所述存储器142相连，用于执行所述存储器142存储的计算机程序，以使所述终端执行上述的基于全局合作式投票的地图匹配方法。

具体来说，所述处理器141可以是通用处理器，包括中央处理器(CentralProcessing Unit，简称CPU)、网络处理器(Network Processor，简称NP)等；还可以是数字信号处理器(Digital Signal Processor，简称DSP)、专用集成电路(ApplicationSpecific Integrated Circuit，简称ASIC)、现场可编程门阵列(Field ProgrammableGate Array，简称FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。

需要说明的是，本发明的基于全局合作式投票的地图匹配系统可以实现本发明的基于全局合作式投票的地图匹配方法，但本发明的基于全局合作式投票的地图匹配方法的实现装置包括但不限于本实施例列举的基于全局合作式投票的地图匹配系统的结构，凡是根据本发明的原理所做的现有技术的结构变形和替换，都包括在本发明的保护范围内。

综上所述，本发明的基于全局合作式投票的地图匹配方法、系统、介质及终端，与现有技术相比，本发明提供了一种改进的基于合作式投票的地图匹配算法，解决了在高架道路与地面道路共存的复杂路况下，地图匹配轨迹的不稳定问题，提高了地图匹配的准确率；本发明通过对GPS轨迹当中的噪声以及候选点转移路径中不合理的情况进行剔除，保证地图匹配准确率的同时，减少了处理时间和系统的压力，使得改进后的地图匹配算法更加适用于低采样率条件下的城市复杂路网；所以，本发明有效克服了现有技术中的种种缺点而具高度产业利用价值。

上述实施例仅例示性说明本发明的原理及其功效，而非用于限制本发明。任何熟悉此技术的人士皆可在不违背本发明的精神及范畴下，对上述实施例进行修饰或改变。因此，举凡所属技术领域中具有通常知识者在未脱离本发明所揭示的精神与技术思想下所完成的一切等效修饰或改变，仍应由本发明的权利要求所涵盖。