HarmonyOS开发者限时福利来啦!最高10w+现金激励等你拿~ 了解详情
写点什么

漫话 | 地图数据处理之道路匹配篇

  • 2020-03-04
  • 本文字数:3064 字

    阅读完需:约 10 分钟

漫话 | 地图数据处理之道路匹配篇

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


本文属于「漫话地图」系列,我们将结合地图数据业务的特点,持续介绍地图行业一些有趣的知识点,希望能抛砖引玉,为大家带来一定的启思和裨益,欢迎长期关注。

道路匹配定义及应用场景

定义


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



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


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


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


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

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

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

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


应用



最常见的应用场景


道路匹配最直观的应用就是地图导航。手机自带 GPS 的定位精度在 10 米上下,单车道的宽度一般是 2-3 米。实际上,手机 GPS 定位不足以精确判断车辆行驶的实际道路。但大家会发现,通常情况下高德导航的道路定位都是很准确的,导航过程中地图会知道用户在某某道路而不是附近小区或者沟河中。


究其原因,用户导航过程中,系统一直在计算 GPS 位置和导航路线 &路网间的配准关系,从而进行一定程度的纠偏,这也是提高定位精度的重要手段。


大家也会经常发现同一手机第三方客户 API 定位效果比高德地图差了不少,刨除硬件因素,实际上这里有算法水平的差异。

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

离散点集匹配


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


曲线拟合


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


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



算法分类


曲线匹配方法分类


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


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


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


空间距离


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


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

  • 欧氏距离(Euclidean Distance)

  • 曼哈顿距离(Manhattan Distance)

  • 切比雪夫距离(Chebyshev Distance)

  • 汉明距离(Hamming distance)

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

  • 豪斯多夫距离(Hausdorff Distance)

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

评价曲线相似性-弗雷歇距离

什么是弗雷歇距离?


Fréchet distance(弗雷歇距离)是法国数学家 Maurice RenéFréchet 在 1906 年提出的一种路径空间相似形描述定义。


狗绳距离


弗雷歇距离通俗的讲就是狗绳距离,人和狗之间有一条狗绳约束。主人走路径 A,狗走路径 B,各自走完这两条路径过程中所需要的 最短狗绳长度就是弗雷歇距离


最大距离最小化


设定 t 是时间点,该时刻曲线 A 上的采样点为 A(t), 曲线 B 上采样点为 B(t)。如果使用欧氏距离,则容易定义 d (A(t),B(t)) 。在每次采样中 t 离散的遍历区间[0,1],得到该种采样下的最大距离。弗雷歇距离就是使该最大距离最小化的采样方式下的值。


K-WALK 和弗雷歇排列


给定一个有 n 点的路链 P=〈p1 , p2 , … , pn 〉,一个沿着 P 的 k 步分割成为 k 个不相交的非空子集,称为 K-WALK。


给定两个路链 A =〈a1 , …, am 〉, B =〈b1 , …, bn 〉,一个沿着 A 和 B 的组合步(Paired Work)是 A 的 k-walk {Ai}i =1 …k 和一个沿着 B 的 k-walk {B i}i =1 …k 组成(1 ≤i ≤k) 。


链 A 和 B 间的离散 Fréchet 距离(discrete Fréchet distance)就是一个沿着链 A 和 B 的组合步 W={(Ai ,Bi)}的最小花费,这个组合步称为链 A 和 B 的 Fréchet 排列(Fréchet alignment),也称为最佳组合步。弗雷歇距离实际上就是不断的遍历计算,尝试找出最佳组合步的过程。


利用平均弗雷歇距离评价曲线相似性


采用平均 Fréchet 距离代替离散 Fréchet 距离,因为前者是从顶点距离集合中选取的一个最大距离,易受到局部变形较大点的影响。


基于离散 Fréchet 距离识别曲线上点与点之间最短路径的方法,平均 Fréchet 距离通过计算离散要素点集之间的最短距离的平均值,来度量线要素间的相似性。



全局算法



两条曲线之间的匹配,研究的是 1:1 的关系,实际应用中 GPS 轨迹比较长的时候面临 M:N 全局择优的问题。


进行全局路线匹配时,需要考虑 M:N 的情况来确定整体路径,代表性的算法是使用弗雷歇距离来衡量待匹配序列和候选路段序列的匹配度,并作为路段的权重,由此构建网络图,通过计算最短路径得到最佳匹配结果。

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

除了弗雷歇距离外,再介绍一种高级算法,也是目前应用中准确度最高的一种算法(和最通用解决方案)—隐式马尔科夫模型 HMM。


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


核心特征


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

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

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

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

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

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


维特比算法详见:


https://blog.csdn.net/xueyingxue001/article/details/52396494


开源实现 Graphhopper-mapmatching,Java 实现的地图匹配项目,作为开源导航引擎 graphhopper 的子项目提供,最新实现用的是隐式马尔科夫模型,GitHub 地址:


https://github.com/graphhopper/map-matching



解决三类问题


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


基于隐马尔科夫模型的路网匹配过程



衍生算法集合



其中 STM 算法,稳定健壮,实用性强,有成熟的研究和开源实现。


ACM SIGSPATIAL Cup


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

道路匹配在业务中的应用

道路匹配在自动化项目中的应用,包括交通轨迹拟合度计算和道路自动识别等。




更多场景,比如异源数据融合、轨迹数据挖掘、交通数据分析、城市规划等领域,道路匹配都有广泛的应用前景。


2020-03-04 14:494464

评论 2 条评论

发布
用户头像
您好,有深入研究过https://github.com/graphhopper/map-matching,匹配算法吗?测试了下,性能比较低,1000个轨迹点,匹配时长达7秒钟。
2020-03-10 16:23
回复
本人也在研究这个算法,可否交流下?本人QQ为2764418708
2020-09-22 16:08
回复
没有更多了
发现更多内容

聊聊Go里面的闭包

秦怀杂货店

Go 函数式编程 闭包

云原生安全系列2:提升镜像安全的10条建议

HummerCloud

云原生 镜像安全 云原生安全

2022我的前端面试总结

loveX001

JavaScript

阿里云无影研发负责人任晋奎:端云技术创新,打造全新用户体验

云布道师

云栖大会 无影云电脑

聊聊hashmap

急需上岸的小谢

11月月更

聊聊ThreadLocal

急需上岸的小谢

11月月更

极客时间运维进阶训练营第四周作业

chenmin

即时通讯技术文集(第6期):移动端弱网优化文章汇总 [共13篇]

JackJiang

网络编程 即时通讯IM

云图说|移动应用安全服务—App的体检中心,全面检测,安全上路!

华为云开发者联盟

华为云 移动应用安全 VSS

vivo霍金实验平台设计与实践-平台产品系列02

vivo互联网技术

A/B 测试 平台化 AB实验

一键开启云原生网络安全新视界

京东科技开发者

云原生 网络安全 软件架构 应用结构

6个tips缓解第三方访问风险

SEAL安全

安全 访问权限 第三方访问

Spring Boot 分离配置文件的 N 种方式

江南一点雨

Java spring springboot

Docker部署flink备忘

程序员欣宸

Docker flink 11月月更

一年前端面试打怪升级之路

loveX001

JavaScript

三次握手与四次挥的问题,怎么回答?

loveX001

JavaScript

从URL输入到页面展现到底发生什么?

loveX001

JavaScript

【web 开发基础】PHP 的函数工作原理 (28)

迷彩

函数 web开发基础 11月月更 结构化编程 函数的工作原理

CleanMyMac2023注册机mac系统清理工具

茶色酒

CleanMyMacX CleanMyMac X

支持向量机-支持向量机分类器原理

烧灯续昼2002

Python 机器学习 算法 sklearn 11月月更

NFTScan 正式推出「NFTScan as a Service」NaaS 服务

NFT Research

NFT 数据基础设施

iMazing2022免费试用版ios设备管理器

茶色酒

imazing imazing2023

主成分分析PCA与奇异值分解SVD-PCA对手写数据集的降维 & 用PCA做噪音过滤

烧灯续昼2002

Python 机器学习 算法 sklearn 11月月更

Java程序员在写 SQL 时常犯的错误

@下一站

学习 程序媛 Java core 11月月更

想搞懂持续交付理论和实践,你只差这三个问题

华为云开发者联盟

云计算 云原生 华为云 代码托管

100+款AI产品薅羊毛攻略(中)——1年节省大几百万

夏夜许游

AI 视觉智能 阿里云视觉智能开放平台 薅羊毛

其实你的下班时间,被 Excel 预定了

叶小鍵

100万行Spring源代码,鬼知道面试都会问啥

博文视点Broadview

Serverless Devs 重大更新,基于 Serverless 架构的 CI/CD 框架:Serverless-cd

Serverless Devs

云计算 Serverless Serverless Devs

部署代码质量检测服务 sonarqube,基于命令、shell 脚本和 pipline 实现代码质量检测

忙着长大#

jenkins

计算机网络:PPP协议与HDLC协议

timerring

计算机网络 11月月更

漫话 | 地图数据处理之道路匹配篇_文化 & 方法_高德技术_InfoQ精选文章