精华内容
下载资源
问答
  • JUST技术:基于HMM的实时地图匹配
    2021-01-04 21:47:00

    随着城市规模的不断扩大和便民业务的发展,行车导航、共享汽车和物流派送等应用已经深入人们日常生活之中。这些应用都不可避免地需要使用GPS、北斗等定位系统,进而产生了大量的轨迹数据。然而,普通民用GPS定位系统上传的位置数据会由于许多缘故发生与物体的实际地理位置不同的现象,产生了米级别的误差,一般在10米以内。此外,在数据传输、存储和耗电的条件限制下,导致轨迹点采样频率不宜过高。因此,以上因素导致采集到的移动对象位置与其实际所在道路之间有一定距离偏差。为了使接收到的位置数据可以真实反映移动对象的运行轨迹,需要进行轨迹的各种预处理工作,其中地图匹配是一项十分重要的工作。

     

    一、地图匹配

    地图匹配是将存在误差或漂移的GPS观测点匹配至路网上的算法,它常用于还原观测点的真实位置和移动物体的运动轨迹。如图1,地图匹配算法将采集到点1、2、3映射到路段上。地图匹配可分为离线和实时两种处理方式:离线方式接收过去一段时间观测到的批量轨迹数据,并计算输出全量轨迹的最优匹配结果。其优势在于准确度高。然而,它的处理过程十分耗时,因此,面对监测和追踪等需要实时返回计算结果的场景难免力有不逮;实时地图匹配则可以很好地弥补离线处理时延大的缺陷。目前,基于HMM的实时地图匹配算法[2]被广泛使用于很多业务场景中,如公交车实时位置播报、快递员配送位置跟踪。以危化品运输车辆的监管为例,危化品运输车若偏离原报备路线,通过实时的地图匹配可以在第一时间获取其异常行为及最新位置,实现了对危化品车辆行驶路线的实时监测。barefoot [1]是一个开源项目,它基于实时地图匹配算法提供了实时地图匹配服务。本文接下来主要从算法思想和实现思路两方面介绍开源项目barefoot中的实时地图匹配服务。

     

    图1 地图匹配示意图

    二、算法思想

    Barefoot 是一个开源的Java项目,它提供了离线/实时地图匹配及空间分析等服务,其中实时地图匹配的实现思路以Goh[2] 提出的算法作为参考。如图2所示,Barefoot提供的实时地图匹配演示图。

     

    图片

    图2 实时地图匹配演示图

    Goh[2]提出的算法基于隐马尔可夫模型(HMM),并采用可变滑动窗口进行回溯计算,实现了高精度低延时的实时地图匹配。

    其主要流程大体分成三步, 1)寻找候选路网点,2)计算发射和转移概率,3)获取计算结果。

     1)寻找候选路网点

    寻找候选路网点是指,针对每一个轨迹点z_t,找到距离z_t指定距离(默认为50m)的路段,计算每条路段上距离z_t最近的位置,即为候选路网点。候选路网点通常为轨迹点z_t在对应路段的垂直投影点或路段的端点。

    2)计算发射和转移概率

    获取到轨迹点z_t对应的候选路网点集合S_t后,以z_t到每一个候选路网点的距离和GPS定位误差为参数,计算候选路网点的发射概率P(z_t |s_t);再针对上一时刻的候选路网点集合S_(t-1)与本次集合S_t中的每一组候选点,以两个候选点之间最短路径的长度作为主要参数计算这两点之间的转移概率。

    3)获取计算结果

    概率计算完成后,通过在线Viterbi算法检验是否存在结果点,并返回到达该点的最优路径。

     

    图3 HMM算法

    在HMM基础之上,barefoot扩展了两种概率模型:过滤概率和序列概率。其中,过滤概率P(s_t |z_0…z_t)用以计算在已观测到轨迹点序列z_0…z_t的条件下,最可能符合真实情况的路网点s_t;序列概率P(s_0…s_t |z_0…z_t)则在已观测到轨迹点序列z_0…z_t的条件下,计算在路网上到达点s_t 最可能的路径。

    需要注意的是,在转移概率和序列概率的计算过程中,需要使用历史轨迹点对应的候选路网点集合作为参数。因此,barefoot采用了可变滑动窗口来保存历史状态。可变滑动窗口指的是窗口中可容纳的路网点集合数固定,而总路网点数量取决于每个路网点集中的点数,是可变的值。当接收到一个新轨迹点时,可变滑动窗口向前扩展一位,同时根据配置中的窗口上限参数来判断是否需要清除当前窗口中的历史路网点集。Barefoot 提供了状态更新TTL、路网点集合数量上限k和时间段上限τ 三个窗口配置参数用于配置路网点集合数。

    三、实现思路

    Barefoot通过启动tracker server接收轨迹点,并发布计算结果。tracker server根据配置文件中的参数初始化指定容积的线程池,并为每一个发送数据的客户端分配一个处理线程T。T会持续接收客户端发送的轨迹数据,并将计算结果发送回客户端。当客户端长时间没有向tracker server发送消息时,对应的连接将被中断。在以上流程中,耗时较长的计算部分由处理线程T决定是否进行异步计算。

    为实现以上计算步骤中的空间范围查询和最短路径规划,barefoot需要在内存中维护路网结构。它使用的方法是通过查询读取数据库中的路网表,并根据道路线的属性值构建路网有向图和带有道路线空间范围的四叉树索引来实现最短路径规划。在空间查询获取候选路网点时,使用索引获取空间范围内的道路线id,并在道路线上通过插值计算出与轨迹点距离最近的候选路网点的坐标。

     

    图4 候选点

    针对每个轨迹点,barefoot将其对应的候选路网点集合保存至时间窗内。时间窗使用优先队列(PriorityBlockingQueue)实现,在提供超时清理和新增入队功能的基础上,起到保证线程安全的作用。时间窗内的候选路网点集合通过链表相连,方便获取到每个路网点在上一状态中的关联点,以及本集合中最可能为真的目标路网点(如图4中加粗的点)。本次候选路网点集合更新的同时,历史点集合中既不是目标点又与后继路网点无关联的点将被移除。

    四、测试结果

    Barefoot 使用合理的索引和路网结构,在Goh[2] 的实时地图匹配算法的基础上扩展了概率模型,实现了针对轨迹点实时地图匹配的毫秒级响应。经测试,针对单个轨迹点的地图匹配,Barefoot的计算耗时在50~200ms之间(详见图5)。

     

    图5 计算时间

    针对当前民用GPS的普遍采样频率低的现实情况,它也可以做到地图匹配结果的实时返回。但是,barefoot的实现方式也使它具有一定的局限性。

    Barefoot 采用固定数量的socket连接方式提供服务。因此,当连接的客户端超出一定数量时,服务端的响应速度会受到影响;同时Barefoot没有开放Kafka、Storm等实时平台的接入方式,这使得其使用方式并不灵活。在地图匹配计算方面,由于受到轨迹数据信息量不足的限制,在计算转移概率时,对路径cost的计算不是以轨迹点速度为参数,而是采用固定参数进行模拟计算。导致在一些情况下可能会对计算结果产生影响。除此以外,目前barefoot只支持OSM路网数据,不支持更加灵活的路网模型,且每次启动都将路网数据导入JVM中,这种方式限制了其扩展性和迁移性。诸如此类问题,都是在实现或者应用时可以改进的方向。例如,可以通过redis等分布式缓存技术优化路网构建的方法,使其更加适用于分布式场景;还可以针对特定路网数据的信息量对概率计算公式进行改进,通过这些方式使其更适用于特定的业务场景。

    目前,JUST时空数据平台[3]吸收了Barefoot优秀的设计思路,针对Barefoot的不足,正在实现一套集实时数据接入、实时地图匹配、实时地图展示等高可扩展的完整解决方案。

    参考文献

    [1] https://github.com/bmwcarit/barefoot

    [2] C.Y. Goh, J. Dauwels, N. Mitrovic, M.T. Asif, A. Oran, and P. Jaillet. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In International IEEE Conference on Intelligent Transportation Systems, 2012.

    [3] https://just.urban-computing.cn/

     

    转载请注明:康瑞部落 » JUST技术:基于HMM的实时地图匹配

    更多相关内容
  • 一种基于嵌入式Linux系统的地图匹配技术.pdf
  • 针对基于无线定位的交通信息采集中地图匹配问题,提出一种新的地图匹配算法,算法提取连续多个位置点的瞬时位置、方向和相邻时刻的运动距离构成具有三个特征变量的子时间序列,并用DTW来进行车行轨迹与候选路段的...
  • 提出了在不协调覆盖决策系统下基于扩展分体思想的分辨矩阵以及相关基本知识,给出其相对应的属性约简算法及其解释分析,与其他基于分辨矩阵的算法进行比较,分析了该方法的优越性和实用价值。
  • 本文将从地图匹配定位技术的简介、原理、误差分析以及常用算法进行介绍。文中介绍了高精自动驾驶系统中的地图匹配技术,具体涉及技术原理、误差分析以及常用算法。

    目录

    引言

    1. 地图匹配定位技术简介

    2. 地图匹配定位技术原理

    3. 地图匹配定位误差分析

    4. 地图匹配常用算法

    5. 总结


    引言

    汽车定位是让自动驾驶汽车知道自身确切位置的技术,在自动驾驶系统中担负着相当重要的职责。汽车定位涉及多种传感器类型和相关技术,主要可分为卫星定位、惯性导航定位、地图匹配定位以及多传感器融合定位几大类。其中地图匹配定位技术利用道路物理信息与预制高精度地图,实现实时的自动驾驶定位。在卫星定位、惯性导航系统出现明显误差时,地图匹配定位技术可为自动驾驶系统提供实时定位修正信息,因此对自动驾驶系统至关重要。本文将从地图匹配定位技术的简介、原理、误差分析以及常用算法进行介绍。

    1. 地图匹配定位技术简介

    无论是卫星定位(GNSS)还是惯性导航定位(INS),自动驾驶定位系统的误差都不可避免,定位结果通常偏离实际位置。引入地图匹配可以有效消除系统随机误差,校正传感器参数,弥补在城市高楼区、林荫区、立交桥、隧道中长时间GNSS定位失效而INS误差急剧增大的定位真空期。

    地图匹配定位技术是指将自动驾驶汽车行驶轨迹的经纬度采样序列与高精度地图路网匹配的过程。地图匹配定位技术将汽车定位信息与高精度地图提供的道路位置信息进行比较,并采用适当算法确定汽车当前的行驶路段以及在路段中的准确位置,校正定位误差,并为自动驾驶路径规划提供可靠依据。

    如图1所示,由于各种原因导致自动驾驶汽车定位信息存在误差,尽管汽车行驶在中间车道上,但定位效果与实际情况存在偏差,利用地图匹配定位技术可将定位信息纠正回正确车道,提高定位精度。

     图1 地图匹配定位效果示意图

    2. 地图匹配定位技术原理

    地图匹配定位是在已知汽车位姿信息的条件下进行高精度地图局部搜索的过程。首先,利用汽车装载的GNSS和INS做出初始位置判断,确定高精度地图局部搜索范围。然后,将激光雷达实时数据与高精度地图数据变换到同一个坐标系内进行匹配,匹配成功后即可确认汽车定位信息,地图匹配定位流程如图2所示。

     图2 地图匹配定位流程

    高精度地图的预制是地图匹配的基础,需包含特征明显的结构化语义特征和具有统计意义的信息。高精度地图中常用于地图匹配的特征主要包含车道线、停止线、导流线、路灯、电线杆等特征明显的物体,同时还包括平均反射值、方差及平均高度值等具有统计意义的信息。

    当自动驾驶系统的GNSS和INS出现较大误差时,汽车会根据实时感知数据进行环境特征的检测,主要检测对象是地面上的车道线与杆状物,并从高精度地图对应位置范围内提取对应的元素。实际匹配过程中,系统将检测出的车道线、护栏等道路特征与高精度地图提供的道路特征进行对比,修正汽车的横向纵向定位,如图3、4所示。

     图3 修正横向位姿示意图

     图4 修正纵向位姿示意图

    图3中,GNSS将汽车定位在前进方向的左侧车道,自动驾驶汽车利用传感器检测到的车道线信息与高精度地图数据进行匹配后,确定汽车位于前进方向中间车道,与GNSS的定位结果存在差异,进而修正横向的位姿误差。图4中,纵向上修正主要提取传感器所检测到的广告牌、红绿灯、交通标志灯等道路元素与高精度地图进行匹配,可以修正汽车的纵向误差。

    3. 地图匹配定位误差分析

    地图匹配定位误差主要由局部搜索范围正确性问题引起,局部搜素范围正确性即道路选择的正确性,是地图匹配中极大的影响因素,在选择道路正确的情况下,才能继续之后的地图匹配过程。造成道路选择错误的原因主要包括路况引起的误差、传感器误差、高精度地图误差及算法误差等方面。

    3.1 路况引起的误差

    真实道路的情况复杂多变,无法保证汽车在各种复杂路况上都能够正确地提取特征,并实现正确定位。车速变换将会影响传感器采集数据的质量,车速越快,质量越低,甚至产生运动模糊、失真等情况。在没有INS的定位系统中,各种路况下造成的汽车轮胎漂移及路面颠簸等情况都可能使激光点云数据发生畸变、抖动和运动模糊等问题。与此同时,实际行驶情况中汽车有时会离开道路,这将导致道路匹配错误并引起误差。

    3.2 传感器误差

    进行地图匹配需要利用传感器的量测信息(如激光雷达、摄像头),这些数据存在误差将直接影响定位速度与成功率。

    3.3 高精度地图误差

    在实际使用中,一般默认高精度地图的精度比传感器获得的数据精度高,但实际上,高精度地图同样有可能存在较大误差。在地图数据本身存在误差时,即使在正确选择道路的情况下也会引入误差。

    3.4 算法误差

    在地图匹配过程中,不可避免地因算法存在的缺点导致发生错误匹配,发生错误匹配会对之后的地图匹配定位结果产生恶劣影响。

    4. 地图匹配常用算法

    任何一种地图匹配算法都涉及两个根本的问题:(1) 当前汽车在哪一条道路上;(2) 当前汽车在对应道路的哪一个位置。因此,地图匹配算法几乎都可以用如下表达进行形式化描述:

    式中,Xn表示n时刻汽车的原始状态信息,如定位数据、速度、行驶方向等;G表示道路网络,由道路路段集R和道路节点集N构成。根据不同的地图匹配特点,将地图匹配算法分为几何匹配算法、概率统计算法和其他高级算法。

    4.1 几何匹配算法

    几何匹配算法包括点到点、点到弧和弧到弧的地图匹配算法。

    (1) 点到点的地图匹配算法

    点到点的地图匹配算法的原理即搜索汽车定位点与高精度地图中位置点之间几何距离最近的点作为匹配结果。该算法匹配精度取决于位置点集的数量,随着位置点集数量的增大,匹配精度更高,但占用的硬件资源也更多。点到点的地图匹配算法得到的匹配结果很可能会与实际情况不符,如在一条笔直道路上,待匹配GNSS点都会错误地匹配到道路两端的的节点上,这样的到的匹配精度显然不符合实际使用要求。

    (2) 点到弧的地图匹配算法

    通过寻找与汽车定位点几何距离最近的路段作为匹配线段,将汽车定位点投影到该选段上作为匹配结果。对于曲线则做线性化处理后进行投影,该算法只利用了部分数据,当两条曲线距离较小或相同时极易造成误匹配,在路网密度大时匹配结果的精度就会锐减,此时的算法缺乏稳定性。

    (3) 弧到弧的地图匹配算法

    将连续的汽车定位点组成一条轨迹曲线,寻找与这条曲线最近的匹配弧线作为匹配线段。由于最近路段的寻找方法是基于匹配路段与定位点的最小距离,所以若某定位点与非正确匹配线段非常近,将导致严重误差/

    4.2 概率统计算法

    概率统计算法通过在汽车导航定位系统中获得的历史轨迹,建立置信区域来与高精度地图进行匹配。置信区域参考GNSS误差、汽车航迹、汽车速度及道路信息等进行选取,与高精度地图匹配后采取最近距离原则来确定匹配选段。

    一个完整的基于概率统计的地图匹配算法包括三个主要的处理过程,即确定误差区域、选取候选路段和计算匹配位置,基于概率统计算法地图匹配的一般过程如图5所示。

    图5 基于概率统计法地图匹配的一般过程

    误差区域是指可能包含汽车真实位置的区域范围,它应根据传感器定位结果和误差情况确定。在误差区域内的道路称为候选路段,地图匹配算法认为其中包含了汽车的真实位置。匹配路段的选取方法是从候选路段中挑选最有可能的汽车行驶路段,挑选原则依据具体的算法设计而不同,通常挑选参考量是高精度地图中的道路形状与汽车轨迹的相似程度。确定匹配路段后,计算汽车在该路段中最可能的位置,并用匹配结果修正原有的定位信息并输出。

    4.3 其他高级算法

    除了上述两种地图匹配算法外,还有非参数滤波算法和参数滤波算法等。非参数滤波算法包括了直方图滤波(Histogram Filter, HF)和粒子滤波(Particle Filter, PF)等。参数滤波算法包括卡尔曼滤波、扩展卡尔曼滤波(Extended Kalman Filter, EKF)、信息滤波(Information Filter, IF)、扩展信息滤波(Extended Information Filter, EIF)等。这些算法在固定场景下有很高的匹配准确率,但需要大量的数据进行参数的前期学习和总结,对系统的要求较高。

    5. 总结

    地图匹配是自动驾驶定位系统的关键技术,本文介绍了高精自动驾驶系统中的地图匹配技术,具体涉及技术原理、误差分析以及常用算法。在实际自动驾驶定位系统的设计中,要针对具体硬件条件和实际工况,有针对性地进行地图匹配技术的设计。

    展开全文
  • 然而,现有的地图匹配技术不能满足具有大量轨迹数据的应用的不断增长的需求,例如交通流分析和路线规划。为了解决这个问题,我们提出了一种有效的地图匹配算法,称为Passby。我们不会将每个GPS点都匹配,而是将精力...
  • 基于TDOA定位如何消除或减少沿道路方向上的误差 求帮忙求帮忙
  • 由于低频浮动车数据时间间隔较长,现有地图匹配方法难以满足低频浮动车数据地图匹配的要求.综合考虑浮动车数据轨迹点之间的整体特性,在局部和全局地图匹配算法的基础上,提出了一种基于改进AOE网络的低频浮动车数据...
  • 基于蜂窝移动通信网络中切换定位技术的特点,提出一种城市近郊快速路地图匹配算法。以完备的导航电子地图和可靠的切换位置数据库作为地图匹配的前提条件,该算法首先选择切换在候选路段的发生频率和相邻切换间可能行驶...
  • 地图匹配算法的有效性和可靠性对于智能交通系统而言是非常重要的,而目前存在的地图匹配算法在一些复杂环境下(如道路交叉口)仍然不能提供合理的输出。采用D-S证据理论融合当前车辆位置信息和方向信息可以有效地扩大待...
  • 地图匹配算法实践

    千次阅读 2018-04-16 09:05:12
    地图匹配(Map Matching)是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程,其本质上是平面线段序列的模式匹配问题( Alt等,2003)。 在实际应用中,GPS采样信号的质量会严重影响地图匹配结果:采样频率...

    1 背景

    如下图所示,1、2、3 这三个点是汽车的GPS定位结果,尽管汽车是在道路上,但定位结果与道路存在偏差。地图匹配(Map Matching)是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程,其本质上是平面线段序列的模式匹配问题( Alt等,2003)。

    clipboard.png

    在实际应用中,GPS采样信号的质量会严重影响地图匹配结果:采样频率的降低、定位误差的加大、信号的丢失,都会使匹配的不准确性增加。这些情况在实际应用中经常出现。如何在这些情况下仍能保持较高的路径匹配准确率是个值得研究的问题。

    2012年ACM SIGSPATIAL首次设立的竞赛,其内容就是地图匹配。三年前本人有幸和国防科大的杨岸然博士一同参加了该竞赛,收获良多。

    2 地图匹配算法综述

    2.1 以使用到的信息来划分

    现有的算法可被分成四类:几何、拓扑、概率、高级。
    a)基于几何的算法考虑GPS点与道路的几何信息,如距离、角度等;
    b)基于拓扑的算法使用道路拓扑信息来控制;
    c)概率方法通过考虑GPS点的概率;
    d)高级的算法往往综合考虑使用全面信息,有卡尔曼滤波、模糊逻辑模型、隐式马尔可夫模型等等。

    2.2 以考虑采样点的范围来划分

    根据考虑采样点的范围,可分成局部/增量算法、全局算法。
    a)局部/增量算法是贪婪算法,每次确定一个匹配点,下个点从已经确定的匹配点开始。这些方法根据距离和方向相似性来找到局部最优点或边。(在线匹配)
    b)全局算法是要从路网中找到一条与采样轨迹最接近的匹配轨迹。为了测量采样轨迹和匹配轨迹的相似性,大多数算法使用“Frechet距离”或者是“弱Frechet距离”。还有时空匹配算法、投票算法等。(离线匹配)

    clipboard.png

    2.3 以采样点的频率来划分

    根据轨迹数据的采样频率,现有的地图匹配算法可分成:
    a)高频采样算法(所有局部算法、部分全局算法如Frechet距离判别法等)
    b)低频采样算法(ST-matching算法、IVVM算法

    一般认为30s及其以上为低频采样,1s~10s为高频采样。

    3 我们的训练数据

    a)路网数据: Washington State U.S.A.(有128万条边 )
    b)GPS数据:采样频率为1~30s,

    clipboard.png

    4 采用的算法

    使用ST-Matching算法(Lou等,2009),该算法是一种全局算法,能综合几何信息( GPS点与道路的距离)、道路拓扑信息(最短路径)、道路属性信息(每条道路的限速),具有精度高,稳定性好等优点。

    4.1 准备候选集

    clipboard.png

    4.2 确定权重

    clipboard.png

    a)空间因素权重(Fs)

    clipboard.png

    b)时间因素权重(Ft)

    clipboard.png

    5 实验结果

    clipboard.png

    6 技术实现要点

    6.1 地图投影问题

    问题:原始道路网数据的坐标与轨迹点的坐标并不在一个坐标体系下,不能直接进行计算!

    解决方法:使用PRJ4地图投影库将两个数据投影到统一坐标下。

    6.2 大路网信息数据量的读取

    问题:该路网有128万条边,我们采用C++,如果读取每条边都进行new和delete操作,将执行128万次,效率极低!

    解决方法:使用内存池技术。

    6.3 最短路径算法的选择

    问题:候选集不同层次的候选点之间都要计算最短路径,使用最常用的Dijkstra最短路径算法效率极低!

    解决方法:使用启发式最短路径算法:A-star算法。

    6.4 索引

    问题:由于竞赛真实测试会使用很多不同的路网数据,所以建立索引没必要,但是计算某一GPS点的候选集时路网所有数据会参与计算,效率很低;

    解决方法:计算某一GPS点的候选集时,先进行切片过滤,比如以该GPS点为中心,生成200m的正方形框,然后在该框里建立新的道路网,这时计算候选集时只需要与该框内的道路网数据计算。

    展开全文
  • 针对地图数据存储部分采用基于区域划分的数据水平切分技术与GeoHash编码技术相结合的方式。方案实现了对大规模车辆的实时监控,解决了大规模数据下并发处理的问题。同时与传统方案比较,方案在达成相同性能条件下...
  • MATLAB实现地图匹配问题的算法。 (一种基于的优化建议) 论文摘要 随着各种位置获取技术的进步,每天可以收集无数的GPS轨迹。 但是,由于许多物理限制和某些法律规则,传感器捕获的原始坐标数据通常无法反映实际...
  • 大数据时代低频采样交通轨迹数据呈指数级增长,准确、高效地对复杂路网中产生的海量低频浮动车数据进行地图匹配对出租车载客热点和路线推荐具有重要意义。基于上述考虑,提出了一种基于曲线拟合的改进算法,对缺失的...
  • 基于粒子滤波技术,提出了融合地图...实验证明,所提出的基于粒子滤波的地图匹配技术有效解决了由于无线定位结果穿墙、错定至隔壁房间而造成的用户体验差等问题,同时对室内定位结果进行了修正,提高了室内定位精度。
  • 随着定位技术和位置服务应用的发展,地图匹配研究不断演进,从早期基于高采样率GPS(Global Position System)的实时匹配,到近期基于低采样率GPS轨迹的离线匹配、再到当前非GPS定位数据或高精度地图匹配
  • 地图匹配实践

    2020-12-12 09:48:09
    地图匹配(Map Matching)是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程,其本质上是平面线段序列的模式匹配问题(Alt等,2003)。在实际应用中,GPS采样信号的质量会严重影响地图匹配结果:采样频率的降低、...

    1 背景

    如下图所示,1、2、3这三个点是汽车的GPS定位结果,尽管汽车是在道路上,但定位结果与道路存在偏差。地图匹配(Map Matching)是指将行车轨迹的经纬度采样序列与数字地图路网匹配的过程,其本质上是平面线段序列的模式匹配问题( Alt等,2003)。

    在实际应用中,GPS采样信号的质量会严重影响地图匹配结果:采样频率的降低、定位误差的加大、信号的丢失,都会使匹配的不准确性增加。这些情况在实际应用中经常出现。如何在这些情况下仍能保持较高的路径匹配准确率是个值得研究的问题。

    2012年ACM SIGSPATIAL首次设立的竞赛,其内容就是地图匹配。三年前本人有幸和国防科大的杨岸然博士一同参加了该竞赛,收获良多。本博文也就是对参加竞赛的工作做一个简要的总结回顾,想要代码参考的朋友可以在下面留下邮箱,并注明用途。

    2  地图匹配算法综述

    2.1 以使用到的信息来划分

    现有的算法可被分成四类:几何、拓扑、概率、高级。

    a)基于几何的算法考虑GPS点与道路的几何信息,如距离、角度等;

    b)基于拓扑的算法使用道路拓扑信息来控制;

    c)概率方法通过考虑GPS点的概率;

    d)高级的算法往往综合考虑使用全面信息,有卡尔曼滤波、模糊逻辑模型、隐式马尔可夫模型等等。

    2.2 以考虑采样点的范围来划分

    根据考虑采样点的范围,可分成局部/增量算法、全局算法。

    a)局部/增量算法是贪婪算法,每次确定一个匹配点,下个点从已经确定的匹配点开始。这些方法根据距离和方向相似性来找到局部最优点或边。(在线匹配)

    b)全局算法是要从路网中找到一条与采样轨迹最接近的匹配轨迹。为了测量采样轨迹和匹配轨迹的相似性,大多数算法使用“Frechet距离”或者是“弱Frechet距离”。还有时空匹配算法、投票算法等。(离线匹配)

    2.3 以采样点的频率来划分

    根据轨迹数据的采样频率,现有的地图匹配算法可分成:

    a)高频采样算法(所有局部算法、部分全局算法如Frechet距离判别法等)

    b)低频采样算法(ST-matching算法、IVVM算法

    一般认为30s及其以上为低频采样,1s~10s为高频采样。

    3 我们的训练数据

    a)路网数据: Washington State U.S.A.(有128万条边 )

    b)GPS数据:采样频率为1~30s,

    4 采用的算法

    使用ST-Matching算法(Lou等,2009),该算法是一种全局算法,能综合几何信息( GPS点与道路的距离)、道路拓扑信息(最短路径)、道路属性信息(每条道路的限速),具有精度高,稳定性好等优点。

    4.1 准备候选集

    4.2 确定权重

    a)空间因素权重(Fs)

    b)时间因素权重(Ft)

    5 实验结果

    6 技术实现要点

    6.1 地图投影问题

    问题:原始道路网数据的坐标与轨迹点的坐标并不在一个坐标体系下,不能直接进行计算!

    解决方法:使用PRJ4地图投影库将两个数据投影到统一坐标下。

    6.2 大路网信息数据量的读取

    问题:该路网有128万条边,我们采用C++,如果读取每条边都进行new和delete操作,将执行128万次,效率极低!

    解决方法:使用内存池技术。

    6.3 最短路径算法的选择

    问题:候选集不同层次的候选点之间都要计算最短路径,使用最常用的Dijkstra最短路径算法效率极低!

    解决方法:使用启发式最短路径算法:A-star算法。

    6.4 索引

    问题:由于竞赛真实测试会使用很多不同的路网数据,所以建立索引没必要,但是计算某一GPS点的候选集时路网所有数据会参与计算,效率很低;

    解决方法:计算某一GPS点的候选集时,先进行切片过滤,比如以该GPS点为中心,生成200m的正方形框,然后在该框里建立新的道路网,这时计算候选集时只需要与该框内的道路网数据计算。

    展开全文
  • 车载GPS_DR组合导航及地图匹配修正技术研究.pdf
  • 应用海底地图匹配技术提高水下载体(AUV)定位精度。通过双三次B一样条曲面插值重建参考地图 (RDM),选取RDM中部分地图附加正态白噪声模拟当地水深地图(LDM)。将两块地图同时转化为8位256级灰度图像,应用图像相关法进行...
  • 基于GPS与地图匹配的铁路运输安全监控技术研究.pdf
  • 针对精度差、频率低的浮动车数据特点,给出了空间和拓扑约束下的最短路径浮动车数据地图匹配算法,基于不同采样频率的匹配结果证明算法准确度高。基于武汉市浮动车数据的匹配结果表明,算法具有高可靠性,可以用于...
  • 定位匹配 模板匹配 地图By Marie Douriez, James Murphy, Kerrick Staley 玛丽·杜里兹(Marie Douriez),詹姆斯·墨菲(James Murphy),凯里克·史塔利(Kerrick Staley) When you request a ride, Lyft tries to ...
  • 一种基于被支持度的决策自适应的全局地图匹配算法,刘聪聪,陈恒鑫,地图匹配技术是建设智慧城市潮流中不可或缺的。地图匹配的难度主要取决于路网的密度和GPS点的质量。然而,大多数现有的地图匹配算
  • 地图匹配能够将车辆定位信息与路网电子地图相结合,是车辆导航系统中重要的定位技术。为克服地图匹配过程中当前定位点信息不足的缺点,充分利用车辆定位的历史轨迹信息,引入了Fr6chet距离来定义两曲线间的距离,并且...
  • 针对目前城市交通中对浮动车数据匹配实时性差和匹配率不高的缺点,提出一种利用道路缓冲区的大规模GPS数据的地图匹配算法。在综合考虑GPS定位点精度以及道路宽度的基础上,构建道路缓冲区区域,通过分析道路缓冲区...
  • 由于浮动车数据采集中存在GPS数据周期过长、拓扑关联性较差、数据量大的特点,传统的车载端地图匹配算法难以直接应用,针对车辆无法初次匹配的情况,设计了一种可根据路网拓扑关联性进行判断的延时地图匹配算法....
  • 为了改善机动车导航地图匹配的精度,提出了一种新的基于递推轨迹与候选路径相关性分析的地图匹配方法.为了获得最佳匹配路径,分别计算递推轨迹曲线和候选路径曲线的切向量角,并沿曲线分段计算切向量角的一阶差分,...
  • 影像匹配技术是一门迅速发展的图像处理技术,在图像镶嵌,图像融合,军事侦察等领域有广泛应用。影像匹配就是将图像归一化到统一的坐标系统中去,将两幅图像或者图像与地图进行空间对准,进而将两幅图像拼接在一起,...
  • 基于浮动车的交通流分析要求地图匹配快速而准确地处理GPS数据,现有的地图匹配算法无法满足交通流分析的实时处理要求。本算法采用延时策略,利用历史数据和最新数据及低速识别提取的静止点来指导延时点匹配,同时...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 26,018
精华内容 10,407
关键字:

地图匹配技术