服务热线400-028-2850

新闻中心

News center

经达动态

更多 >
[2017-02-17]
浅谈UBI车险
[2016-12-23]
UBI的发展之旅
经达动态
地图数据处理之道路匹配
发布时间:2020-03-27阅读次数:236来源:上海经达信息科技股份有限公司

来源:高德技术


道路匹配是地图数据处理方面非常基础且重要的理论,特别是道路相关业务,一定避不开道路匹配的应用,这也是业务中普遍会碰到的痛点。


道路匹配定义


道路匹配是地图匹配理论的子集,通俗讲就是两幅地图AB,在没有唯一ID关联的情况下,如何确定地图A上的道路是B上一条道路的过程。如果做交通轨迹或者地图数据融合方面的研究,那么就一定会遇到地图匹配的问题。




地图匹配 Map Matching:不同条件下获取同一物景的地图之间的配准关系。

道路匹配是刨除了点和面状匹配之外的线状要素理论,道路的话就是路网,也是实际应用中研究最多、应用最广的一部分。

利用路网数据,采用适当算法,将目标定位映射到实际道路上的过程,具体来说道路匹配是:

l  地图匹配理论的首要子集

l  针对矢量拓扑道路数据的匹配模式

l  异源道路数据融合的关键

l  导航定位精度改善的重要手段


空间距离和评价曲线相似性的一般方法


离散点集匹配

路网匹配的两个方面应用:第一个是离散点集匹配,相对简单,随机离散点没有形状和拓扑关系,用欧氏距离作吸附即可,典型应用如离散热力图。


曲线拟合

实际中更有应用价值的是曲线拟合匹配关系,比如轨迹和路网,GPS序列和导航路的相似性。

曲线信息更多,这方面比离散点集有更多的评价要素,也有更高的复杂度。评价曲线相似性的一般要素有长度、形状、曲率、拓扑关系、方向比如正向逆向、距离、属性例如交通规则左转右转禁行等信息。




曲线匹配方法分类

基于几何信息的匹配算法考虑形状、角度等常规要素,属于早期的一些算法,实现最简单,准确度最低。基于拓扑信息的算法,准确度比几何方法大大提升,应用最广。基于概率预测的算法,实现比较困难,实际上应用不多。

目前有一些比较高级的算法理论,包括隐马模型等等,在实际应用中准确度是相对最高的。

实时算法主要用于在线导航,时间和空间复杂度低,离线算法用于数据处理的离线计算,算法复杂,追求最高准确度。


空间距离

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

l  闵可夫斯基距离(Minkowski Distance)

l  欧氏距离(Euclidean Distance)

l  曼哈顿距离(Manhattan Distance)

l  切比雪夫距离(Chebyshev Distance)

l  汉明距离(Hamming distance)

l  杰卡德相似系数(Jaccard similarity coefficient)

l  豪斯多夫距离(Hausdorff Distance)

l  弗雷歇距离(Fréchet距离)


最准确的匹配模型-隐式马尔科夫模型HMM


20世纪60年代,Leonard E. Baum和其它作者在一系列的统计学论文中描述了隐式马尔科夫模型。它最初的应用之一是语音识别,80年代成为信号处理的研究重点,现已成功用于故障诊断、行为识别、文字识别、自然语言处理以及生物信息等领域。


       核心特征

l  隐式马尔科夫模型五要素:2个状态集合和3个概率矩阵,Viterbi算法。

l  隐含状态S:马尔科夫模型中实际所隐含的状态,通常无法通过直接观测得到,这些状态之间满足马尔科夫性质。

l  可观测状态O:通过直接观测而得到的状态,在隐式马尔科夫模型中与隐含状态相关联。

l  状态转移概率矩阵A:描述隐式马尔科夫模型中各个状态之间的转移概率。

l  观测状态概率矩阵B:表示在t时刻隐含状态是Sj条件下,其可观测状态为Ok的概率。

l  初始状态概率矩阵π:表示隐含状态在初始时刻t=1的概率矩阵




路网匹配实际是一个解码问题,基于HMM的路网匹配算法是在一系列观察的前提下,寻找最有可能产生这个观察序列的隐含状态序列。一系列GPS位置点集合是可观测状态,寻找最有可能产生位置点集合的路网隐藏序列。

2012年ACM SIGSPATIAL Cup是由ACM主办的全球范围内关于地图匹配算法的科技竞赛,竞赛吸引了来自全球31支专业级的参赛队伍。所有算法当中匹配准确率最高的两个都是基于HMM的匹配算法。