AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

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

  • 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:495199

评论 2 条评论

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

TDengine 签约优力电,查询速度提升至毫秒级别

TDengine

tdengine 时序数据库

一张图搞清楚wait、sleep、join、yield四者区别,面试官直接被征服!

不在线第一只蜗牛

Java 程序员 面试

知识图谱中的数据服务是什么?

悦数图数据库

知识图谱

全栈开发与自动化测试高薪私教班,带你从0到1拿到高薪Offer

测试人

软件测试

站群云服务器租用攻略,让你的网站运行更稳定更快速

一只扑棱蛾子

站群服务器 站群云服务器租用 站群云服务器

【AAAI 2024】解锁深度表格学习(Deep Tabular Learning)的关键:算术特征交互

阿里云大数据AI技术

人工智能 机器学习 架构 算法

现网修改TiDB集群IP和端口

TiDB 社区干货传送门

6.x 实践

为什么Python语言那么受欢迎呢?

小魏写代码

2款办公必备的ai制作ppt软件,一键生成专业精致PPT!

彭宏豪95

PPT 在线白板 办公软件 AIGC AI生成PPT

新经济时代企业财务管理系统的新需求解读

智达方通

业财融合 财务管理 企业财务预算管理

知识图谱数据开发是做什么的

悦数图数据库

图数据库

2024Java笔试真题,java虚拟机面试题

阿里、莫言

Java java面试 金三银四 Java 面试题

利用阿里巴巴中国站1688商品详情API:电商开发者的必备指南

技术冰糖葫芦

API 接口 API 测试

TIDB DM功能使用实践

TiDB 社区干货传送门

6.x 实践

web快速开发框架,前端开发学习教程

阿里、莫言

前端 前端面试 前端知识

了解 x-www-form-urlencoded 及实践

Liam

程序员 前端 Web HTTP x-www-form-urlencoded

TiDB 7.5 LTS版本新增的Hint

TiDB 社区干货传送门

管理与运维 新版本/特性解读 7.x 实践

增长分析系列一:社交行业指标体系设计与运营策略探究

ClkLog

虾皮Shopee根据ID取商品详情API

Noah

Sora Opera:天图万境联合华为云共筑AI生成式视频音效新高度

华为云开发者联盟

人工智能 华为云 华为云开发者联盟 视频配音 AI生成式视频音效

华为吴辉:强健“伙伴+华为”体系,让数智世界一触即达

新消费日报

多模态 + 大模型会带来哪些 “化学反应”?

京东科技开发者

京东ES支持ZSTD压缩算法上线了:高性能,低成本

京东科技开发者

电商场景下 ES 搜索引擎的稳定性治理实践

字节跳动云原生计算

搜索引擎 云原生 云搜索

【必备】,95页初级前端模块笔记分享

阿里、莫言

前端 前端面试

北斗芯片产业的高质量发展之路

江湖老铁

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