地图匹配

概念：

• 地图匹配（Map-Matching）是将运营车辆的有序的GPS位置关联到电子地图的路网上，将GPS坐标下采样序列转换为数字路网坐标序列的过程；本质上是平面线段序列的模式匹配问题（ Alt等，2003）
• 地图匹配是一种将原始GPS位置映射到路网上的路段的过程，以创建对车辆所走路线的估算。

两个主要的地图匹配用例

• 乘车结束时，计算驾驶员行进的距离，以计算票价。——路线图匹配(EORMM)
• 实时 ，为ETA团队提供准确的位置并做出调度决策，并在rider应用程序上显示驾驶员的汽车。——实时地图匹配(RTMM)

不同点在于，实时地图匹配的要求比较高，必须低延时，因此相比之下，路线图匹配对等待时间的要求不那么严格，并且可以使用乘车的全部历史记录

参考：

• https://zhuanlan.zhihu.com/p/83039334

• Lyft的地图匹配算法论文翻译

  • 地图匹配算法的性能取决于道路网络数据的质量

  • 解决问题的一种好的方法是使用状态空间模型 。 状态空间模型是时间序列模型，其中系统具有“隐藏”状态，这些状态无法直接观察到，但会引起可见的观察。 在这里，我们的隐藏状态是我们要估算的汽车在道路网络上的实际位置。 我们仅观察到隐藏状态的修改版本：观察值(原始位置数据)。 我们假设系统的状态以仅取决于当前状态的方式演化(马尔可夫假设)，并进一步定义了从隐藏状态到隐藏状态的转移密度和从隐藏状态到观察的密度。

    常用的地图匹配状态空间模型是离散状态隐马尔可夫模型 (Newson＆Krumm [2]，DiDi的IJCAI-19教程[3]，Uber的Map Matching [4])。 在该系统中，我们通过查看路段上的最近点来生成候选对象，并使用维特比算法查找最可能的隐藏状态序列。

    • 对于不同的建模选择和输入数据而言，它相对不灵活
    • 它缩放严重(O(N²)，其中N是每个状态下可能的候选数)
    • 它不能很好地应对高频观测(请参阅Newson＆Krumm [2])。

• GPS定位与地图匹配方法研究

  • 地图匹配算法从原理上可以解释为两个独立的过程：（1）找到车辆当前行使的道路——确定候选路段（2）将当前GPS定位点投影到车辆行使的道路上——候选路段匹配规则
    • 圆心拓展半径找到最近的路段（唯一）——构建第一条边的算法

• [1]苏洁, 周东方, 岳春生. GPS车辆导航中的实时地图匹配算法[J]. 测绘学报, 2001, 30(3):5.

  • 另外，为了提高算法的鲁棒性，对于误差引起 的速度异常，我们利用推测航位法和线性插值来 进行 GPS数据补偿，以消除部分GPS接收外部 粗差

• [1]李清泉, 黄练. 基于GPS轨迹数据的地图匹配算法[J]. 测绘学报, 2010(2):6.

  • 针对传统导航系统的地图匹配方法的研究较多。其中点到线的匹配由于缺乏对整体轨迹趋势的考虑，在复杂的道路网环境下的匹配易导致误匹配。也有方法使用DR、差分GPS等辅助设备，采用滤波、模糊逻辑、证据理论等方法提高地图匹配的准确率。GPS浮动车轨迹数据提供了整体曲线的变化趋势，可以采用全局整体匹配的思想，保证轨迹的完整性和准确性14？。基于曲线相似度的算法一般 较为复杂，但匹配精度高，利于轨迹的直接恢复，适合进行数据的后处理
  • 与整个轨迹相对 应的路径必然是连通 的路段集 ，可以基于道路拓扑与连通性设计地图匹配算法
  • key：除了道路的几何连通性，实际行车还会受到交通规则的限制，本文基于道路网的行车限制信息提出了一种GPS浮动车轨迹数据的全局地图匹配算法，综合考虑备选路段的几何连通性与交通网络条件约束构建整体备选路径，然后使用改进的扫描线法判断全局轨迹曲线与备选路径的相似度，完成地图匹配 。
    • 一句话概括算法：通过行车限制将候选线段找出来后，选择曲线相似度最高的

• [1]陈滨, 王平, 施文灶,等. GPS轨迹数据的综合地图匹配算法研究[J]. 电子科技, 2014, 27(12):4.

  • 从实际的匹配效果来看，此匹配算法在交叉路口等路段较复杂的地方可有较高地匹配准确率，但该方法依赖于前后GPS定位点匹配准确度，若前一定位点匹配错误就会出现连锁反应，从而导致后面一系列点匹配错误；且历史轨迹推算匹配法计算量较大，匹配速度较慢，不利于高速实时定位。因此，需和其他地图匹配方法相结合使用才能取得较好的匹配效果。

• 智能交通系统中GPS地图匹配算法设计与实现_罗杰涛

  • 模糊逻辑： 效率高，实时性好，对绝大多数的路段状况都适用。不过在车俩拐弯处以及车速较慢的情况下匹配效果不尽如人意，且不同路段建模的系数凭靠经验值，没有相应的缺乏理论依据。——01、06、08论文

• 高级地图匹配算法：研究现状和趋势[2021]

  • 从实现技术或模型角度对近十年提出的算法进行分类，箭头标记算法间的继承关系。从图2可见，HMM模型是主流，其次是基于最大权重的模型.HMM-News-on、ST-Matching2 3IVMM3和HRIS8被引用对比最多，是具有开创性的工作。另外，从2019年开始，有研究采用深度学习技术来解决地图匹配问题。

    

Points:

• 另外，一个重要的实际问题是，即使车辆定位精度可以保证在10米以内，当电子地图缩放到较大的比例尺时，也会
  出现车辆偏离行使的道路而造成的视觉混乱现象.

• 由于城区内地物特征复杂，受密集的高大建筑物、隧道、立交桥、树木等地物的反射和遮蔽等影响，车栽GPS接收机接收到的卫星信号存在严重的多径效应，在某些区域内甚至会形成GPS定位育区，解决GPS盲区问题，一种方法是采用航位推算法（DR-Dead Reckoning），这种方法需要将DR设备装在车辆前端，一般在GPS接收机卫星信号受阻时一样可以得到正确的用户位置，但这种方法需要附加设备。另一种方法是在记忆正确GPS位置信息的基础上在一段时间内预测车辆位置，这种方法的优点是易于实现，缺点是精度不够（没有，作者使用卡尔曼滤波进行位置预测，预测结果如图所示。在规则行进时，预测效果较好，见图3、图4.但是当车辆转弯时，效果很差，见图5、图6

• 到折线的距离定义为点到折线上所有直线段的最短距离：点到线段的距离定义为如果点到直线段所在直线的投影在直线段上，则为垂线长度，否则为其到两个端点的最短距离。

• 定位误差： GPS误差、电子地图库误差、坐标投影变换投影

• 难点：

  • Y-junction问题——点到线的匹配方式，没有考虑全局匹配
  • 平行双线路

• MapMatching实现的思路

  • 离散点集匹配：相对简单，随机离散点没有形状和拓扑关系，用欧氏距离作吸附即可，典型应用如离散热力图。
  • 曲线拟合： 实际中更有应用价值的是曲线拟合匹配关系，比如轨迹和路网，GPS序列和导航路的相似性。

• MapMatching算法的分类：

  以使用到的信息来划分

  现有的算法可被分成四类：几何、拓扑、概率、高级。

  a）基于几何的算法考虑GPS点与道路的几何信息，如距离、角度等；

  b）基于拓扑的算法使用道路拓扑信息来控制；

  c）概率方法通过考虑GPS点的概率；

  d）高级的算法往往综合考虑使用全面信息，有卡尔曼滤波、模糊逻辑模型、隐式马尔可夫模型等等。

  2.2 以考虑采样点的范围来划分

  根据考虑采样点的范围，可分成局部/增量算法、全局算法。

  a）局部/增量算法是贪婪算法，每次确定一个匹配点，下个点从已经确定的匹配点开始。这些方法根据距离和方向相似性来找到局部最优点或边。（在线匹配）

  b）全局算法是要从路网中找到一条与采样轨迹最接近的匹配轨迹。为了测量采样轨迹和匹配轨迹的相似性，大多数算法使用“Frechet距离”或者是“弱Frechet距离”。还有时空匹配算法、投票算法等。（离线匹配）

  以采样点的频率来划分

  根据轨迹数据的采样频率，现有的地图匹配算法可分成：

  a）高频采样算法（所有局部算法、部分全局算法如Frechet距离判别法等）

  b）低频采样算法（ST-matching算法、IVVM算法）

  一般认为30s及其以上为低频采样，1s～10s为高频采样。

  https://www.cnblogs.com/LBSer/p/4612031.html#!comments

• 智能交通系统中GPS地图匹配算法设计与实现

  

算法评估的标准

• 实时性
• 可靠性(鲁棒性)
• 匹配的精度

朴素算法：

快速匹配算法的执行步骤如下：

1. 步1接收GPS定位数据；
2. 步2判断定位数据是否无效，若无效，则根据历史定位数据进行推测匹配，然后转（8）；
3. 步3判断车辆当前是否处于停止或低速滑行状态，若是，对其作相应处理，然后转（8）；
4. 步4由车辆当前位置点计算其对应的候选网格，进而获取其中的路段；
5. 步5对步4得到的路段进行连接性拓扑检查，将通过拓扑检查的路段作为匹配候选路段；
6. 步6判断匹配候选路段数目，若唯一，则直接将其作为匹配路段，并由定位点向其作投影，然后转（8）；否则，计算所有候选路段的匹配度度量值f，（i=1,2，…，N），从中选出最大值fm和次大值fm；
7. 步7判断最大值fm和次大值fm之差是否大于阈值fh，且最大值fm是否大于阈值fh，如果大于，则将路段m作为匹配路段，并由定位点向其作投影；否则，暂不对本次定位结果进行匹配，待后面对其进行延时匹配处理；
8. 步8结束本次匹配

from : 一种适于车辆导航系统的快速地图匹配算法——2003

Key:

• 出行数据：采用GPS定位，那么是否是WGS-84数据，但是GIS部门的路网数据坐标是什么坐标系下的

• 双线路：

• 当下，现在很多用于MapMatching的方法，大多来自于推理、预测的数学方法，如隐马尔可夫链、贝叶斯模型、神经网络模型等，但在数据结构上的创新比较少，GIS算法，更多要在计算机的基础上，结合比如时空观念、数据特征、拓扑关系等对于GIS相关的基础理论

软件

• mapinfo: 当今世界上流行的桌面地理信息系统
• graphhopper: 路径规划库
• arcgis
• openstreetmap——开源地图，简称为OSM

线要素的匹配，主要通过几何、拓扑或语义相似度来进行识别，其中通过空间距离来进行要素匹配的常用方式有：

• 闵可夫斯基距离(Minkowski Distance)
• 欧氏距离(Euclidean Distance)
• 曼哈顿距离(Manhattan Distance)
• 切比雪夫距离(Chebyshev Distance)
• 汉明距离(Hamming distance)
• 杰卡德相似系数(Jaccard similarity coefficient)
• 豪斯多夫距离(Hausdorff Distance)
• 弗雷歇距离(Fréchet距离)

from：高德地图：地图数据处理之道路匹配篇

隐马尔科夫HMM

HMM有三个典型(canonical)问题:

• 概率计算问题：已知模型参数，计算某一特定输出序列的概率.通常使用**Forward算法**解决；
• 预测问题或者解码（decoding）问题：已知模型参数，寻找最可能的能产生某一特定输出序列的隐含状态的序列。通常使用**Viterbi算法**解决；
• 学习问题：已知输出序列，寻找最可能的状态转移以及输出概率。通常使用**Baum-Welch算法**。

HMM的几个重要元素：

• π(startprob_): 隐藏状态初始向量

  $\pi=\left(\pi_{i}\right): \pi_{i}=P\left(q_{1}=i\right), 1 \leq i \leq N$

• A(transmat_): 状态转移概率矩阵:

  $A=\left[a_{i j}\right]_{N \times N} \text {, 其中 } a_{i j}=P\left(q_{t+1}=j \mid q_{t}=i\right), 1 \leq i, j \leq N$

• B(emissionprob_): 观测状态概率矩阵

  $B=\left[b_{j}(k)\right]_{N \times M} ， \text { 其中 } b_{j}(k)=P\left(o_{t}=o_{k} \mid q_{t}=j\right), 1 \leq j \leq N, 1 \leq k \leq M$

• HMM的状态变量数目：N

• HMM的观察变量数目：M

如果观测序列是一维的，则观测状态的概率密度函数是一维的普通高斯分布。如果观测序列是N维的，则隐藏状态对应的观测状态的概率密度函数是N维高斯分布。高斯分布的概率密度函数参数可以用μμ表示高斯分布的期望向量，Σ表示高斯分布的协方差矩阵。在GaussianHMM类中，“means”用来表示各个隐藏状态对应的高斯分布期望向量μ形成的矩阵，而“covars”用来表示各个隐藏状态对应的高斯分布协方差矩阵Σ形成的三维张量。

from :用hmmlearn学习隐马尔科夫模型HMM

MapMatching与Hmm

• 观察变量：从GPS设备中得到的位置信息（经度，纬度）
• 隐藏状态：拥有GPS设备的物体（车，人等）实际所在的位置路段。
• 观测概率：例如，现测的GPS点离旁边路段上的位置越近，那么这个真实点在这个路段上的概率越大状态。
• 状态转移概率：例如，前后两个真实的位置点的距离越近，那么状态转移的概率越大

在下面相关论文工作中会说明在这几篇论文中其实只用到了预测问题的Viterbi算法,下面也会另开一小节具体描述下Viterbi算法。

Map-Matching的两个变量：

• 从GPS设备中得到的位置信息（经度，纬度）：HMM中观察变量；
• 拥有GPS设备的物体（车，人等）实际所在的位置：HMM中的隐藏状态变量，实际地图是不知道GPS设备的准确位置的。

这样就把Map-Matching问题与HMM结合起来了。三个问题在Map-Matching中有用的是两个问题：（1）预测问题；（2）学习问题。

在论文中，定义的规则要满足人的直观上的感觉，即人的先验知识，主要有以下两种：

• 观测概率：观测的GPS点离旁边路段上的位置越近，那么这个真实点在这个路段上的概率越大。
• 状态转移概率：这里有两种解决思路：（1）前后两个真实的位置点的距离越近，那么状态转移的概率越大；或者（2）真实路段上的前后两个点的距离与GPS观测的前后两个点的距离越接近，状态转移概率越大。

from: 基于隐马尔科夫模型(HMM)的地图匹配(Map-Matching)算法

barefoot

• 观测概率: 测量位置与其真实位置之间的距离，用于对测量误差进行建模，测量误差用具有一些标准偏差σ的高斯分布来描述（默认为σ = 5 米）。
• 转移概率: 用各个位置测量之间的路由距离和视线距离的差异来量化的。转移概率呈负指数分布，速率参数λ（默认为λ = 0.1）是均值的倒数

==>

• 序列概率： 定义p(s 0 … s t |z 0 … z t )为最可能的序列到达匹配候选s t的概率，称为 s t 的序列概率， 可以通过递归确定

• 过滤概率：我们的 HMM 滤波器确定对象当前位置的估计值s̅ t，它是最可能匹配的候选对象$s_t ∈ S_t$ 给定测量值z0 ... zt，其定义为：s̅t = argmax(st ∈ St) p(st|z0 ... zt), p(st|z0 ... zt)称为$s_t$的过滤概率***，可以递归确定：

  p(st|z0...zt) = p(st|zt) · Σ(st-1 ∈ St-1) p(st|st-1) · p(st-1|z0 ... zt-1)。

from: https://github.com/bmwcarit/barefoot/wiki#stand-alone-servers

Coding

在之前的HMM系列中，我们对隐马尔科夫模型HMM的原理以及三个问题的求解方法做了总结。本文我们就从实践的角度用Python的hmmlearn库来学习HMM的使用。sklearn库中将HMM弃用了，新开了一个hmmlearn的新库，安装命令为：pip install hmmlearn，关于hmmlearn的更多资料在官方文档有介绍。

hmmlearn实现了三种HMM模型类，按照观测状态是连续状态还是离散状态，可以分为两类。

1. GaussianHMM 观测状态连续型且符合高斯分布
2. GMMHMM 观测状态连续型且符合混合高斯分布
3. MultinomialHMM 观测状态离散型

HMM主要解决的三个问题
假设隐藏状态序列和观测状态序列分别使用Z和X表示，则解决的3个问题可表示为:
1.解码问题：已知模型参数和X，估计最可能的Z；维特比算法
2.概率问题：已知模型参数和X，估计X出现的概率；向前-向后算法
3.学习问题：仅给出X和隐藏层个数，估计模型参数。 B-W算法，通常是经过一定数量的训练以后，得到模型，然后解决问题1和2。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#coding=utf-8
'''
Created on 2017-12-4

解码问题：本例为天气和行为的关系
'''
import numpy as np
import matplotlib.pyplot as plt
# hmmlearn可以在安装numpy以后，再使用pip install hmmlearn安装
from hmmlearn import hmm

states = ["Rainy", "Sunny"]##隐藏状态
n_states = len(states)##隐藏状态长度

observations = ["walk", "shop", "clean"]##可观察的状态
n_observations = len(observations)##可观察序列的长度

start_probability = np.array([0.6, 0.4])##开始转移概率，即开始是Rainy和Sunny的概率
##隐藏间天气转移混淆矩阵，即Rainy和Sunny之间的转换关系，例如[0,0]表示今天Rainy，明天Rainy的概率
transition_probability = np.array([
  [0.7, 0.3],
  [0.4, 0.6]
])
##隐藏状态天气和可视行为混淆矩阵，例如[0,0]表示今天Rainy，walk行为的概率为0.1
emission_probability = np.array([
  [0.1, 0.4, 0.5],
  [0.6, 0.3, 0.1]
])

#构建了一个MultinomialHMM模型，这模型包括开始的转移概率，隐藏间天气转换混淆矩阵（transmat），隐藏状态天气和可视行为混淆矩阵emissionprob，对模型参数初始化
model = hmm.MultinomialHMM(n_components=n_states)
model.startprob_= start_probability
model.transmat_ = transition_probability
model.emissionprob_ = emission_probability

#给出一个可见序列
bob_Actions = np.array([[2, 0, 1, 1, 2, 0]]).T

# 解决问题1,解码问题,已知模型参数和X，估计最可能的Z； 维特比算法 
logprob, weathers = model.decode(bob_Actions, algorithm="viterbi")
print "Bob Actions:", ", ".join(map(lambda x: observations[x], bob_Actions))
print "weathers:", ", ".join(map(lambda x: states[x], weathers))



"""
解码问题： 盒子
"""
import numpy as np
from hmmlearn import hmm

states = ["box 1", "box 2", "box3"]
n_states = len(states)

observations = ["red", "white"]
n_observations = len(observations)

start_probability = np.array([0.2, 0.4, 0.4])

transition_probability = np.array([
  [0.5, 0.2, 0.3],
  [0.3, 0.5, 0.2],
  [0.2, 0.3, 0.5]
])

emission_probability = np.array([
  [0.5, 0.5],
  [0.4, 0.6],
  [0.7, 0.3]
])

model = hmm.MultinomialHMM(n_components=n_states)
model.startprob_=start_probability
model.transmat_=transition_probability
model.emissionprob_=emission_probability

seen = np.array([[0,1,0]]).T
logprob, box = model.decode(seen, algorithm="viterbi")
print("The ball picked:", ", ".join(map(lambda x: observations[x], seen)))
print("The hidden box", ", ".join(map(lambda x: states[x], box)))
('The ball picked:', 'red, white, red')
('The hidden box', 'box3, box3, box3')

限制

• 对于不同的建模选择和输入数据而言，它相对不灵活
• 它缩放严重(O(N²)，其中N是每个状态下可能的候选数)
• 它不能很好地应对高频观测(请参阅Newson＆Krumm [2])。

基于(无味)卡尔曼滤波器的新模型——https://blog.csdn.net/weixin_26713521/article/details/108134220

help Code:

• https://github.com/bmwcarit/barefoot
• https://github.com/oldrev/mapmatchingkit

网络文章

• 地图匹配实例-几何匹配——效果图
• 定位匹配 模板匹配 地图_什么是地图匹配？
• 出租车轨迹点地图匹配研究
• 地图匹配小结
• 基于隐马尔科夫模型(HMM)的地图匹配(Map-Matching)算法

工作安排

你的工作主要完成什么（概括说明就行），分为那几步，每一步完成什么（概括说明就行），每一步的工作量（预计完成这步工作需要多少个小时），每一步工作预计在什么时候完成（比如 3.5）

• 工作包含：地图匹配，将车辆的有序GPS位置数据关联到电子地图的路网上，将GPS坐标下采样序列转换为数字路网路径序列的过程。工作内容：解析过滤点并进行坐标转换->点过滤(点稀疏)->地图匹配算法->点映射

库：

• geometryEngine
• net.sf.geographiclib
• com.esri.core.geometry——QuadTree
• graphhopper——org.locationtech.jts.geom ==> Envelope --> findCandidateSnapsInBBox

简单版实现思路

1. 找到起始点O和终点D，以两点为半径画圆，把所有范围内的NormalEdge全部加入List（只要起始点or终止点有一个在范围内）
2. 确定第一条===> 找离第一个GPS点最近的边
3. likelyRoute.forEach从上一条的lowerNormalEdge中(保证拓扑可达连接)，从中选择得分最高（距离和方向）的边作为后续边 。 如果没有lowerNormalEdge（如果所有剩余的点都能映射到最后的这条边上，则认为是终点，此时不在意死路）， 平常如果是死路，则放弃这条序列路径。TODO：没有后续路径时是否要考虑增加可能边集？
4. 到达终点边结束
5. 从likelyRoute中选择得分最高的路径

用到的结构：

• likelyRoute: list[list], 存放多条可能