道路匹配——稀疏数据轨迹点的匹配

 

道路匹配分析与设计

出租车轨迹 由轨迹点序列组成<x,y,t>附带额外信息 speed,angle（GPS正北为0°，顺时针夹角，极坐标角度方向相反）

 

如何匹配轨迹？

轨迹的匹配依赖于单点匹配，在单点匹配的基础上，涉及到两个点之间寻找合理轨迹（路径规划），错误GPS点剔除（模式分类），多点之间的相互验证（投票）。

单点匹配

单点匹配方式：

由目前已知参数，忽略X，Y方向影响是独立同分布，即假设X，Y影响因素相同，因此，<distance,speed,angle>构成判别分析的依据。先假设distance,speed,angle相互独立。

 

• 距离因素：

假设GPS精度为precession=50m，且GPS满足正态分布, 因此可以假设为µ=0,σ=precession/3（根据6-Σ准则，99.7%的点落在(-3σ,+3σ)中）。那么distance的得分=2*落在(distance,+∞)的概率=1-2*Probility[0,distanc).

 

• 速度因素：

speed 在单点匹配中，可以忽略。基本上= similarity(speed,实时道路速度)。在实际计算中，这里可能出现一个循环引用问题，因为实时路况本身就是通过计算车辆轨迹匹配的来得到的。在实际计算过程中，需要不是使用速度，而是通过离散化拥堵等级来计算，因此

speed项得分=similarity（拥堵等级，实时路况拥堵等级）=2*(拥堵等级*实时路况拥堵等级)/( 拥堵等级^2+拥堵等级^2)

 

• 角度因素：

      一个直观的方式通过计算车辆行驶角度与道路自身方向的余弦来计算(即可通过向量点积来计算)

但需要考虑速度对角度的影响（因此，这两个因数并不独立）

      角度得分= similarity（angle，道路方向）=[cos(angle),sin(angle)][cos(道路方向)，sin(道路方向)]

 

• 综合考虑

实际综合得分total = Σ ω(i)*Score(i)

Σω(i)=1.如果确定ω(i)应该通过机器学习的方式来确定。

      最后，使用是还应该加一个因数，先验概率，即某个道路车辆行驶的概率，可以通过现有数据按照前面方法匹配后，进行累计统计得到。

 

总结

现有问题：ω(i)是经验值，即没有通过一定反馈机制（如反向传播算法BP），没有带标注的测试样例数据是个大问题。

 

• 连续多个轨迹点的匹配

    这个时候的轨迹匹配，可以看出是一个马尔科夫过程，基本原理如下：假设连续3个点

A{A1,A2,A3},B(B1,B2,B3},C{C1,C2,C3}

我们要寻找一条最优路径（概率最大），其中Ai表示A可以匹配的道路。

显然，P(Ai)可以通过单点匹配计算得到。但是，不能因为P(A1)>P(A2)就选择A1，因为A1与Bi(i=1,2,3...）

因此，实际上还要计算path(Ai,Bi)的实际距离（通常用最短或者最快距离）。因此这时可以构造一个图，边的概率P(Edge(x,y))= Euclid(x,y)/path(x,y),即用球面最短距离/当前选择的两个点构建成的道路的距离，而

图中每个点的概率采用上述点匹配的概率，计算一条最优路径。

 

在实际计算过程中，每个点的候选集合为4（太多，计算复杂度高），最多计算连续5个点{ P-1,P0,p1,p2,p3}