QCon北京「鸿蒙专场」火热来袭!即刻报名,与创新同行~ 了解详情
写点什么

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

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

评论 2 条评论

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

机器学习实践:基于支持向量机算法对鸢尾花进行分类

华为云开发者联盟

人工智能 模型 华为云

华为云招募工业智能领域合作伙伴,强力扶持+商业变现

华为云开发者联盟

云计算 华为云 工业数据智能

[译]关于 Python 中的数字你可能不知道的 3 件事

宇宙之一粟

Python 6月月更

如何给研发团队分钱?

菜根老谭

研发体系 绩效管理 激励体系

如何低成本快速搭建企业知识库?

小炮

DAP事实表加工汇总功能应用说明

agileai

数据分析 数据集成 数仓建设 基础事实表 汇总事实表

万字攻略,详解腾讯面试(T1-T9)核心技术点,面试题整理

C++后台开发

后台开发 面试题 Linux服务器开发 C++后台开发 腾讯面试

年中大促 | 集成无忧,超值套餐 6 折起

融云 RongCloud

数字经济加速落地,能为中小企业带来什么?

脑极体

C语言字符串与内存库函数的介绍与模拟实现

未见花闻

6月月更

企业级软件开发新模式:低代码

力软低代码开发平台

如何做好研发效能度量及指标选取

思码逸研发效能

研发效能

学习 | 写论文看这一篇就够了~

写程序的小王叔叔

学习笔记 论文阅读 论文写作 6月月更

博睿数据出席阿里云可观测技术峰会,数字体验管理驱动可持续发展

博睿数据

可观测性 智能运维 博睿数据 数字体验管理

短视频源码开发,优质的短视频源码需要做好哪几点?

开源直播系统源码

软件开发 短视频源码

web技术分享| 【高德地图】实现自定义的轨迹回放

anyRTC开发者

前端 Web 音视频 地图 轨迹回放

预约直播|机器学习PAI:AI加速计划

阿里云大数据AI技术

AI 模型开发训练

5分钟快速上线Web应用和API(Vercel)

Liam

前端 前端开发 开发 Postman API

支持在 Kubernetes 运行,添加多种连接器,SeaTunnel 2.1.2 版本正式发布!

Apache SeaTunnel

Apache 大数据 开源 workflow

数据科学家是不是特有前途的职业?

袁袁袁袁满

网页制作存在的一些难点

源字节1号

再读凤凰架构-分布式架构更清晰

AiDaddy

分布式 凤凰架构

一张图解码 OpenCloudOS 社区开放日

腾源会

一文简述:钓鱼攻击知多少

穿过生命散发芬芳

6月月更 钓鱼攻击

详解openGauss多线程架构启动过程

华为云开发者联盟

数据库 后端

关河因果将机器学习融合逻辑规则,突破黑盒壁垒

6979阿强

数据分析 大数据分析 关河因果 关河智图 因果分析

活动预约|阿里云如何搭建云服务 SRE 与可观测体系

阿里巴巴云原生

阿里云 云原生 可观测 峰会

物联网开源开发平台 Shifu 开放内测!第一版技术文档发布

亚马逊云科技 (Amazon Web Services)

物联网 Tech 专栏

51万奖池邀你参战!第二届阿里云ECS CloudBuild开发者大赛来袭

阿里云弹性计算

阿里云 分布式缓存 开发者大赛 加密计算 大数据加速

Fegin的解析

卢卡多多

OpenFegin 6月月更

如何在物联网低代码平台中使用数据字典功能?

AIRIOT

物联网 低代码平台

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