一种基于隐马尔可夫模型的地图匹配方法和系统与流程

本技术涉及地理信息处理，特别是涉及一种基于隐马尔可夫模型的地图匹配方法和系统。

背景技术：

1、路网匹配，也称为地图匹配或道路匹配，是一种地理信息系统技术，用于将gps记录的车辆或行人轨迹点精确对应到路网上的实际道路。路网匹配的目的是纠正gps定位的误差，因为原始的gps数据可能由于信号干扰、多径效应或设备精度限制而偏离实际道路，其在导航、交通管理等场景有着广泛的应用。路网匹配一般使用特定算法将每个轨迹点匹配到路网上最近的道路段或节点，如：最近邻匹配算法、隐马尔可夫模型（hmm）、粒子滤波算法、多相似度量指标算法等。

2、现有的基于隐马尔可夫模型的路网匹配方案，虽然取得了显著进展，但仍存在一些局限和不足。如hmm路网匹配算法在处理大规模路网或高频率采样的gps数据时，可能会遇到较高的计算复杂度，导致算法运行缓慢；现有的hmm路网匹配算法可能在特定数据集上表现良好，但泛化到不同的路网结构时，性能可能会下降。

3、目前针对相关技术中如何提高路网匹配精度的问题，尚未提出有效的解决方案。

技术实现思路

1、本技术实施例提供了一种基于隐马尔可夫模型的地图匹配方法和系统，以至少解决相关技术中如何提高路网匹配的效率和精度的问题。

2、第一方面，本技术实施例提供了一种基于隐马尔可夫模型的地图匹配方法，所述方法包括：

3、获取gps轨迹数据和道路网络数据；

4、基于所述gps轨迹数据和所述道路网络数据，计算gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数；

5、基于所述航向角折减系数、所述gps轨迹数据和所述道路网络数据，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率；

6、基于所述gps轨迹数据和所述道路网络数据，计算得到连续的两个gps轨迹点的候选路段之间的状态转移概率；

7、基于所述状态转移概率和所述单态生成概率，通过维特比算法计算得到gps轨迹与道路网络的匹配结果。

8、在其中一些实施例中，基于所述gps轨迹数据和所述道路网络数据，计算gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数包括：

9、基于所述道路网络数据，计算道路网络中每个路段的方向向量，得到路网路段方向向量；

10、基于所述gps轨迹数据，计算每个gps轨迹点的方向向量，得到gps轨迹点方向向量；

11、基于所述路网路段方向向量和所述gps轨迹点方向向量，计算得出gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数。

12、在其中一些实施例中，基于所述路网路段方向向量和所述gps轨迹点方向向量，计算得出gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数包括：

13、基于所述路网路段方向向量，确定gps轨迹点在道路网络中候选路段上的投影点的方向向量；

14、通过方向向量夹角计算公式，计算得出方向向量之间的夹角 θ，其中， u为gps轨迹点在道路网络中候选路段上的投影点的方向向量， v为gps轨迹点方向向量；

15、基于预设区间数量 n，对所述方向向量之间的夹角 θ进行划分，得到航向角折减系数 k(< θ* n/180>)，其中，< x>代表对 x取整， k(n)代表 k的第 n个元素。

16、在其中一些实施例中，基于所述航向角折减系数、所述gps轨迹数据和所述道路网络数据，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率包括：

17、基于所述gps轨迹数据和所述道路网络数据，计算出gps轨迹点到道路网路中候选路段的投影距离；

18、通过单态生成概率计算公式，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率，其中， 为gps轨迹点 gps i到候选路段 e j的投影距离， k(<* n/180>)为航向角折减系数， 为gps轨迹点 gps i的方向向量与候选路段 e j上投影点的方向向量之间的夹角， σ为观测误差的标准差。

19、在其中一些实施例中，基于所述状态转移概率和所述单态生成概率，通过维特比算法计算得到gps轨迹与道路网络的匹配结果包括：

20、基于状态转移概率和单态生成概率，通过维特比算法对于每个后续的gps轨迹点进行递推计算，以更新 f mat和 i mat，其中， f mat为用于存储最终状态生成概率的终态生成概率哈希表， i mat为用于记录达到最终状态生成概率的最优索引哈希表。

21、在其中一些实施例中，基于状态转移概率和单态生成概率，通过维特比算法对于每个后续的gps轨迹点进行递推计算，以更新 f mat和 i mat包括：

22、通过基于自然对数的计算公式：

23、递推计算出 t和 t index，其中， a mat为状态转移概率的集合， b mat为单态生成概率的集合， t为临时存储概率的数组， t index为概率最大值的索引；

24、基于递推计算出 t和 t index，通过更新公式更新 f mat，通过更新公式更新 i mat。

25、在其中一些实施例中，在获取gps轨迹数据和道路网络数据之后，所述方法包括：

26、基于所述道路网络数据，对道路网络的连通性进行修复，得到修复后的道路网络数据。

27、在其中一些实施例中，基于所述道路网络数据，对道路网络的连通性进行修复包括：

28、对于道路网络中的每个节点，基于所述道路网络数据，确定出与所述节点的距离小于第一距离阈值的边集合；

29、对于所述边集合中的每条边，基于所述道路网络数据，计算所述节点到所述边的投影点，若所述投影点与所述边的端点的距离小于第二距离阈值，则执行所述节点与所述端点的直连修复，否则，执行所述节点与所述投影点的打断修复。

30、在其中一些实施例中，基于所述gps轨迹数据和所述道路网络数据，计算得到连续的两个gps轨迹点的候选路段之间的状态转移概率包括：

31、基于所述gps轨迹数据，计算得到连续的两个gps轨迹点之间的直线距离，

32、基于所述gps轨迹数据和所述道路网络数据，计算得到所述两个gps轨迹点在道路网络中各自候选路段上的投影点之间的路径距离；

33、基于所述直线距离和所述路径距离，计算得到所述候选路段的状态转移概率。

34、第二方面，本技术实施例提供了一种基于隐马尔可夫模型的地图匹配系统，所述系统用于执行上述第一方面任一项所述的方法，所述系统包括数据获取模块、单态生成概率计算模块、状态转移概率计算模块、地图匹配模块；

35、所述数据获取模块，用于获取gps轨迹数据和道路网络数据；

36、所述单态生成概率计算模块，用于根据所述gps轨迹数据和所述道路网络数据，计算gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数；基于所述航向角折减系数、所述gps轨迹数据和所述道路网络数据，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率；

37、所述状态转移概率计算模块，用于根据所述gps轨迹数据和所述道路网络数据，计算得到连续的两个gps轨迹点的候选路段之间的状态转移概率；

38、所述地图匹配模块，用于根据所述状态转移概率和所述单态生成概率，通过维特比算法计算得到gps轨迹与道路网络的匹配结果。

39、相比于相关技术，本技术实施例提供的一种基于隐马尔可夫模型的地图匹配方法和系统，该方法通过获取gps轨迹数据和道路网络数据；基于gps轨迹数据和道路网络数据，计算gps轨迹点的方向向量与gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数；基于航向角折减系数、gps轨迹数据和道路网络数据，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率；基于gps轨迹数据和道路网络数据，计算得到连续的两个gps轨迹点的候选路段之间的状态转移概率；基于状态转移概率和单态生成概率，通过维特比算法计算得到gps轨迹与道路网络的匹配结果，实现了对传统隐马尔可夫模型的改进，通过融合航向角信息和引入航向角折减系数来计算单态生成概率，能更加精细地考虑gps轨迹点与候选路段之间的方向一致性，从而提高了u型弯、双向道路等特殊情况的匹配精度，解决了如何提高路网匹配精度的问题。

技术特征：

1.一种基于隐马尔可夫模型的地图匹配方法，其特征在于，所述方法包括：

2.根据权利要求1所述的方法，其特征在于，基于所述gps轨迹数据和所述道路网络数据，计算gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数包括：

3.根据权利要求2所述的方法，其特征在于，基于所述路网路段方向向量和所述gps轨迹点方向向量，计算得出gps轨迹点的方向向量与所述gps轨迹点在道路网络中候选路段上的投影点的方向向量之间的航向角折减系数包括：

4.根据权利要求1所述的方法，其特征在于，基于所述航向角折减系数、所述gps轨迹数据和所述道路网络数据，计算得到gps轨迹点在道路网络中的候选路段的单态生成概率包括：

5.根据权利要求1所述的方法，其特征在于，基于所述状态转移概率和所述单态生成概率，通过维特比算法计算得到gps轨迹与道路网络的匹配结果包括：

6.根据权利要求5所述的方法，其特征在于，基于状态转移概率和单态生成概率，通过维特比算法对于每个后续的gps轨迹点进行递推计算，以更新fmat和imat包括：

7.根据权利要求1所述的方法，其特征在于，在获取gps轨迹数据和道路网络数据之后，所述方法包括：

8.根据权利要求7所述的方法，其特征在于，基于所述道路网络数据，对道路网络的连通性进行修复包括：

9.根据权利要求1所述的方法，其特征在于，基于所述gps轨迹数据和所述道路网络数据，计算得到连续的两个gps轨迹点的候选路段之间的状态转移概率包括：

10.一种基于隐马尔可夫模型的地图匹配系统，其特征在于，所述系统用于执行权利要求1至9任一项所述的方法，所述系统包括数据获取模块、单态生成概率计算模块、状态转移概率计算模块、地图匹配模块；

技术总结
本申请涉及一种基于隐马尔可夫模型的地图匹配方法和系统，其中，该方法包括：基于获取的GPS轨迹数据和道路网络数据，计算GPS轨迹点的方向向量与GPS轨迹点的投影点方向向量之间的航向角折减系数；基于航向角折减系数，计算出GPS轨迹点的单态生成概率；并计算出GPS轨迹点的状态转移概率；基于状态转移概率和单态生成概率，通过维特比算法计算得到GPS轨迹与道路网络的匹配结果。通过本申请，实现了对传统隐马尔可夫模型的改进，通过引入航向角折减系数来计算单态生成概率，能更加精细地考虑GPS轨迹点与候选路段之间的方向一致性，从而提高了U型弯、双向道路等特殊情况的匹配精度，解决了如何提高路网匹配精度的问题。

技术研发人员：唐铠,刘洋东,严宏宇
受保护的技术使用者：杭州浙诚数据科技有限公司
技术研发日：
技术公布日：2024/9/23