JUST技术：基于HMM的实时地图匹配
随着城市规模的不断扩⼤和便民业务的发展，⾏车导航、共享汽车和物流派送等应⽤已经深⼊⼈们⽇常⽣活之中。这些应⽤都不可避免地需要使⽤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和时间段上限τ 三个窗⼝配置参数⽤于配置路⽹点集合数。
go2map地图北京三、实现思路
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的不⾜，正在实现⼀套集实时数据接⼊、实时地图匹配、实时地图展⽰等⾼可扩展的完整解决⽅案。
参考⽂献
[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.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。