当前, GPS定位系统在智能设备中被广泛应用, 例如:智能手机中的定位系统可以采集行人行驶的位置信息; 车辆可以通过车载定位系统采集车辆行驶过程中的位置信息.这些持续采集的GPS定位序列构成了行人或车辆的运动轨迹, 其中包含了丰富的语义信息, 可直接或间接地应用于个人行为分析^[1-3]、路径推荐^[4-6]以及城市道路的规划和设计等.随着轨迹数据重要性的增加, 定位设备采集轨迹点的频率也在提高.它们以秒级的速率采集位置信息, 这就导致每个移动设备产生更多的定位数据.例如:一个有数万辆车的租车公司, 每天产生数亿的轨迹点数据.这些原始定位数据通过移动设备传输到服务器并进行存储, 这不但占用了移动设备宝贵的网络带宽资源, 也浪费了存储空间.轨迹压缩技术^[7-18]即是针对该问题而提出的, 该技术通过去除轨迹中的冗余数据点, 以减少数据规模, 从而节省传输流量和存储空间.

现实生活中, 移动对象的运动通常受到道路结构的限制, 因此在轨迹压缩技术中发展出了基于路网的轨迹压缩技术^{[7, 8, 19]}.基于路网的轨迹压缩通常首先对轨迹进行地图匹配, 将原始轨迹表示为路网中的路径及路径上的匹配轨迹点, 然后分别对路径和轨迹点进行重编码和压缩.文献[7]通过稀释(dilution)-地图匹配(map-matching)-编码(coding)这3个步骤实现了基于路网的轨迹压缩和编码; PRESS系统^[8]采用先地图匹配后压缩的策略达到相似的效果.这些技术不仅减少了数据量, 还保留了移动对象所在的道路信息, 因此逐渐被学者所关注.然而, 从压缩效果和执行效率的角度看, 这些方法还存在一些明显的不足.

●首先, 虽然基于路网的轨迹压缩技术都采用了地图匹配技术, 但是现有的地图匹配技术都不是针对轨迹压缩而设计的, 因此直接使用这些地图匹配技术将导致不合理的匹配, 进而影响了压缩效果.比如车辆和行人的运动具有一定的随意性, 即, 人在行走或驾驶过程中可能会穿过一片草坪中的小径或者在远离道路的平地运动, 这种情况下, 若将这类轨迹匹配到道路上是不合理的.又比如, 移动对象在真实的道路上运动, 但是该道路尚未被收录到路网数据中, 导致轨迹点被匹配到其他道路上; 或者实际上相连的两条道路, 在地图中并未表现为连通的.图 1是不在地图道路上行驶的移动对象及其轨迹的真实案例.若不加针对性地处理, 这些情况都将使地图匹配过程中断或者匹配结果不合理, 进一步导致不良的压缩效果;

●其次, 现有的基于路网的轨迹压缩方法的压缩率不够好.比如PRESS系统, 其采用的匹配轨迹压缩算法是时序数据压缩中的BOPW方法^[20], 压缩率存在很大的提升空间;

●再次, 现有的基于路网的轨迹压缩方法都是离线的算法, 适合在后台执行.然而移动对象的轨迹通常在移动端产生, 若将原始轨迹上传至服务端再进行压缩, 则会在移动端产生大量的流量消耗和存储开销.因此, 在移动端对轨迹进行压缩是更好的方法.

针对以上问题, 本文提出了一种路网感知的在线轨迹压缩方法.首先, 本文在综合考虑移动轨迹的特点和地图质量的基础上, 针对轨迹压缩的需要, 设计了一种距离有界的地图匹配算法; 其次, 基于O’Rourke^[21]算法, 本文设计了更高效的匹配轨迹压缩算法; 再次, 本文设计和实现了ROADER(road-network aware and error-bounded trajectory compression)系统, 它通过滑动窗口机制和在线地图加载技术, 集成路网匹配、匹配轨迹压缩和未匹配轨迹压缩等算法, 实现了在移动端的轨迹压缩; 最后, 我们通过实验验证了ROADER系统的执行效果和效率.实验说明, 该系统在压缩率、误差和执行时间等方面均大幅优于同类算法或系统.

本文第1节介绍轨迹压缩领域的相关研究.第2节定义本文出现的相关概念, 同时介绍本文的工作基础.第3节提出一种距离有界的地图匹配算法.第4节提出基于路网的轨迹压缩算法.基于上述算法, 第5节设计并实现路网感知的在线轨迹压缩系统.第6节在真实数据集下, 通过实验验证本文系统.第7节总结全文, 并对后续研究进行初步探讨.

1 轨迹压缩相关研究

定位设备采集的轨迹通常由一系列轨迹点组成, 每个轨迹点至少包括相应的位置信息和时间信息.轨迹压缩技术去除轨迹中冗余的轨迹点, 保留轨迹中包含重要信息的点.为便于讨论, 本节将这些轨迹压缩技术分为3类:(1)线段简化算法, (2)基于路网的轨迹压缩算法, (3)其他轨迹压缩算法.

1.1 线段简化算法

线段简化的思想来自于计算几何, 其目的是用粗粒度的折线代替细粒度的折线, 且使后者到前者的最大距离小于用户给定的阈值.最优线段简化算法的时间复杂度为O(n²)^[22], 其中, n为输入的轨迹点数.最优算法的时间复杂度较高, 不适用于大规模数据的压缩.因此, 许多工作致力于时间复杂度相对较低的次优算法, 这些算法按其技术特点又可分为批处理算法、在线算法和单遍扫描算法.

1.1.1 批处理算法

批处理算法采用全局扫描的策略, 需要在压缩开始之前加载所有的数据点.批处理算法可以是自顶向下或是自底向上的.在自顶向下的算法中, 轨迹点序列被递归地划分为子序列, 直到满足一定的停止条件.Douglas-Peucker算法^[10]是经典的自顶向下的算法, 该算法将原始轨迹的起始点和终点连接起来, 然后计算每个点到这条连线的距离, 若某一轨迹点到连线的距离最大且超过设定的阈值, 则以该点作为分割点将轨迹分为两个子序列, 之后递归地进行上述过程, 直到轨迹无需划分.Douglas-Peucker算法的时间复杂度是O(n²).Meratnia提出的TD-TR^[9]算法是对Douglas-Peucker的改进, 主要变化是用同步距离(SED)^[23]代替了原算法采用的垂直距离(PED), 其他计算过程都类似.自底向上的算法是对自顶向下算法的补充, 典型的算法是Theo Pavlidis^[24], 该算法开始时用n/2个子轨迹段近似表示长度为n的原始轨迹, 之后, 该算法将误差最小的相邻子轨迹递归合并, 直到满足停止条件.批处理算法具有很高的时间复杂度和空间复杂度, 不适合于在线场景和资源有限的计算环境^[11].

1.1.2 在线压缩算法

在线算法使用了窗口机制, 只在窗口内进行全局扫描, 因此不需要获得整个轨迹信息就可以进行轨迹压缩.文献[25]提出了滑动窗口(sliding-window)算法和开放窗口(opening-window)两种在线算法.这类算法首先建立一个窗口, 然后对窗口内的轨迹进行压缩, 之后对后续的轨迹数据重复该过程.这两种算法的时间复杂度为O(n²).BQS^[12]和SQUISH-E^[13]进一步优化开放窗算法:BQS^[12]利用凸包优化技术, 从窗口的轨迹中挑选出最多8个特殊点, 以此加快算法执行速度; SQUISH-E^[13]算法是开放窗口和自底向上算法的结合, 该算法使用双向链表提高算法的效率.文献[26]提出将滑动窗口中偏移距离最大的轨迹点作为当前轨迹点能否被压缩的判据, 以此提高轨迹的压缩时间和压缩效率.在线算法仍具有较高的时间复杂度和空间复杂度.

1.1.3 单遍扫描算法

单遍扫描算法对每个轨迹点仅扫描和处理一次, 因而不需要窗口提前缓冲轨迹点.显然, 单遍扫描算法具有线性的时间复杂度和O(1)的空间复杂度.文献[14]中提出的算法将固定数目的连续数据点划分为区段, 保留每个区段中第n个点或一个随机点.虽然这个过程很快, 但该算法的误差没有上界.Reumann-Witkam^[15]建立了一个平行于前两个数据点连线的长方形条块, 并用一条线段表示该条块中的所有数据点.Reumann-Witkam执行速度很快, 但由于条块的方向受限于前两个数据点, 很难包含更多的点, 因而压缩率不佳.在20世纪70年代后期出现了扇区相交(sector intersection, 简称SI)算法^{[16, 17]}, 制图学科中的Sleeve算法^[18]也采用了与SI算法相同的思想, 它们都是单遍扫描算法.本文作者近期提出的OPERB算法^[11]也实现了误差有界的单遍扫描算法.需要指出的是:目前的这些单遍扫描算法^{[11, 16-18]}都只支持垂直距离, 不支持同步距离.

1.2 基于路网的轨迹压缩

移动对象通常在路网上行驶, 因此其移动经常受路网的限制.基于路网的轨迹压缩^{[7, 8, 19]}保留移动对象在路网中的行驶路径, 更适用于基于位置的服务等应用.通常, 基于路网的轨迹压缩首先对轨迹进行地图匹配, 将原始轨迹表示为路网中的路径及匹配轨迹点, 然后分别对路径和匹配轨迹点进行重编码和压缩^{[27, 28]}.

文献[7]通过稀释(dilution)-地图匹配(map-matching)-编码(coding)这3个步骤实现了基于路网的轨迹压缩和编码:首先, 利用DP算法^[10]对移动端的原始轨迹数据进行压缩, 这一步称为稀释(dilution).压缩后的轨迹数据通过移动端传输到服务器端, 减少了移动端的带宽消耗; 第2步为地图匹配(map-matching), 将GPS轨迹点映射到路网上, 将原始轨迹用路径信息表示; 最后一步是对路径进行编码(conding), 文献提出了贪婪路径序列和最短路径序列两种路径编码方法.需要指出的是, 该算法的匹配和重编码都不适合在移动端完成.此外, 先压缩后匹配的做法, 也使得其匹配距离没有上界并且压缩效果较差.

PRESS系统^[8]采用先匹配后压缩的策略, 其压缩分为无损的路径信息重编码和有损的匹配轨迹点压缩.对于轨迹的路径部分, 压缩系统首先对整个路网进行预处理, 计算最短路径, 使得任意两点之间都可用最短路径表示; 同时, 由于不同的移动轨迹含有许多重复的轨迹(路径)片段, 因此将轨迹中出现频率高的路段或路径用轨迹模式表示, 进而减少数据规模.对路径上的轨迹点数据, 该系统进行了有损压缩.PRESS输出的压缩点的时间信息都是原始轨迹点的采样时间.PRESS系统对道路匹配距离没有限制, 因此匹配结果中匹配距离是无界的.此外, 其压缩率不够好, 且不支持在线压缩, 其压缩的效果和性能都有很大的提升空间.

COMPRESS系统^[19]是PRESS系统^[8]的后续发展, 主要变化是改变了匹配点的压缩算法.COMPRESS系统采用了基于计算几何的有损压缩方法, 在宽度为ε的管道内找到一条包含顶点数最少的折线.COMPRESS系统继承了PRESS的地图匹配方法, 因此其匹配结果中的匹配距离是无界的.此外, COMPRESS输出的压缩点的时间信息不是原始轨迹点的采样时间, 这点与本文方法以及PRESS系统都不同.

1.3 其他轨迹压缩

轨迹信息还可以表示为便于人们理解的信息, 例如兴趣点(POI)、标志建筑或者路口等.例如:文献[29]利用兴趣点形成的最小包围盒(MBB)表示压缩后的轨迹, 对压缩后的轨迹相似性进行度量, 并对轨迹进行聚类.这类工作与本文的相关性不高, 故不展开赘述.

2 基本概念及方法描述

本节先说明相关概念, 然后介绍基于HMM的地图匹配方法和匹配轨迹压缩的基础算法(O’Rourke算法).

2.1 术语定义

基于路网的轨迹压缩方法首先进行道路匹配, 将轨迹点序列匹配到路网中, 得到原始轨迹的匹配路径信息和映射在匹配路径上的匹配轨迹点序列.下面首先说明道路匹配的相关概念.

定义1(轨迹点).轨迹点p定义为p=(x, y, t), 其中, x, y, t分别表示轨迹点的经度、纬度及时间.

定义2(轨迹).轨迹$\dddot T = \{ {p_1}, ..., {p_n}\} $为按时间递增排序的轨迹点序列, 对于任意1≤i≤j≤n, 有p_i.t < p_j.t.

定义3 (路网).路网G=(V, E)是有向图, 其中, V是顶点v=(x, y)的集合, E是路段r=(v_s, v_e)的集合.

定义4 (路径).路径R={r₁, …, r_m}是连续的路段序列, 对于任意1≤i < m, 有r_i.v_e=r_i+1.v_s.

定义5 (匹配点).匹配点$\bar{\bar{p}}$是轨迹点p在路段r上的投影点, 定义为$\bar{\bar{p}}=(r, d, t)$, 其中, r为路段, d为匹配点$\bar{\bar{p}}$相对r.v_s的距离, t是轨迹点p的时间.

定义6(匹配距离).匹配距离是轨迹点p到路段r的距离, 表示为ped(p, r).匹配距离也是p到匹配点$\bar{\bar{p}}$的距离, 即, $ped(p, r)=|p\bar{\bar{p}}|.$

定义7(匹配轨迹).给定子轨迹$\dddot T = \{ {p_s}, ..., {p_k}\} (s \leqslant k)$, 其匹配轨迹是匹配点序列, 表示为$\bar{\bar{T}}=\{{{\bar{\bar{p}}}_{s}}, ..., {{\bar{\bar{p}}}_{k}}\}$.匹配轨迹也可以表示为$\bar{\bar{T}}=(R, \bar{\bar{S}})$, 其中, R为匹配轨迹的路径, $\bar{\bar{S}}=\{({{d}_{s}}, {{t}_{s}}), ..., ({{d}_{k}}, {{t}_{k}})\}$为路径R上的轨迹点序列.此处, d_i为${{\bar{\bar{p}}}_{i}}$相对路径R起始点的道路距离(s≤i≤k).

其次, 基于路网的轨迹压缩方法进一步对匹配轨迹进行压缩.压缩算法的核心是寻找穿越轨迹点序列的穿越直线, 其含义如下.

定义8(穿越直线).考虑(d, t)二维空间中的时序数据{(t_s, d_s), …, (t_k, d_k)}(s < k), 其中, t是时间, d是变量.若对于每个时刻t_i(s≤i≤k), 变量d都有一个取值范围[a_i, w_i], 则该时序序列可表示为三元组序列{(t_s, a_s, w_s), …, (t_k, a_k, w_k)}.一条穿越范围序列{(t_s, a_s, w_s), …, (t_k, a_k, w_k)}的直线称为穿越直线, 表示为L_sk.

2.2 基于HMM的地图匹配方法

目前的基于路网的轨迹压缩算法^{[7, 8]}都先将原始轨迹匹配到道路上, 并普遍采用了基于隐式马尔可夫模型(HMM)的地图匹配算法^[30-32].给定轨迹$\dddot T = \{ {p_s}, {p_{s + 1}}, ..., {p_k}\} $, 基于HMM的地图匹配算法将路段作为隐状态, 将轨迹点作为观测状态, 最终通过观测状态序列推测隐状态序列.对于每个轨迹点, HMM方法计算其发射概率和转移概率, 然后在路网G中找到一条联合概率最大的路径R.

HMM发射概率P(p|r)表示了在路段r上采集到移动对象轨迹点p的概率, 即轨迹点p匹配到路段r的概率.文献[25]证明发射概率相对于轨迹点p到路段r的匹配距离ped(p, r)服从正态分布.令σ_ped为距离ped的标准差, 轨迹点p在道路r上的发射概率可定义为

$ P(p|r) = \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} \ {\sigma _{ped}}}}{{\rm{e}}^{-0.5 \times {{\left( {\frac{{||ped||}}{{{\sigma _{ped}}}}} \right)}^2}}} $

(1)

相应地, 转移概率$P({{\bar{\bar{p}}}_{i}}.r, {{\bar{\bar{p}}}_{i+1}}.r)$表示移动对象从匹配路段${{\bar{\bar{p}}}_{i}}.r$移动到另一条匹配路段${{\bar{\bar{p}}}_{i+1}}.r$的概率.其中, 从${{\bar{\bar{p}}}_{i}}$沿道路至${{\bar{\bar{p}}}_{i+1}}$的距离又称为道路转移距离(如图 2所示).令${{\bar{\bar{p}}}_{i}}$和${{\bar{\bar{p}}}_{i+1}}$的道路转移距离与轨迹点p_i和p_i+1的欧氏距离之差为Δd, 文献[31]证明, Δd服从指数分布.由此, 移动对象从道路${{\bar{\bar{p}}}_{i}}.r$至道路${{\bar{\bar{p}}}_{i+1}}.r$的转移概率定义为

$ P({{\bar{\bar{p}}}_{i}}.r,{{\bar{\bar{p}}}_{i+1}}.r)=\frac{1}{\beta }\times {{\text{e}}^{-\frac{\Delta d}{\beta }}} $

(2)

其中, β是指数分布中的参数.

此外, 每个轨迹点p都有多条候选匹配路段, 因此, 一条轨迹就存在多条候选匹配路径.对于子轨迹{p_s, …, p_i}及其某条候选匹配路径R_i, 对应了一条马尔可夫链, 且存在一个联合概率P({p_s, …, p_i}|R_i), 定义为

$ P(\{{{p}_{s}}, ..., {{p}_{i}}\}|{{R}_{i}})=\left\{ \begin{array}{*{35}{l}} P(\{{{p}_{s}}, ..., {{p}_{i-1}}\}|{{R}_{i-1}})\times P({{{\bar{\bar{p}}}}_{i-1}}.r, {{{\bar{\bar{p}}}}_{i}}.r)\times P({{p}_{i}}|{{{\bar{\bar{p}}}}_{i}}.r), \rm{ }i>s \\ P({{p}_{i}}|{{{\bar{\bar{p}}}}_{i}}.r), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ i=s \\ \end{array} \right. $

(3)

给定输入轨迹点序列$\dddot T = \{ {p_s}, {p_{s + 1}}, ..., {p_k}\} $, HMM地图匹配算法输出匹配轨迹$\bar{\bar{T}}=({{\bar{\bar{p}}}_{s}}, {{\bar{\bar{p}}}_{s+1}}, ..., {{\bar{\bar{p}}}_{k}})$.算法得到每个轨迹点的所有可能的匹配路段, 计算其概率, 并维持一个集合RSet保存当前所有可能的匹配路径R.当算法执行到轨迹点${{\bar{\bar{p}}}_{i}}$时, 选择P({p_s, …, p_i-1}|R_i-1)与$P({{\bar{\bar{p}}}_{i-1}}.r, {{\bar{\bar{p}}}_{i}}.r)$乘积最大的路径加入其中, 并更新联合概率P({p_s, …, p_i}|R_i)和当前路径集RSET.轨迹结束时, 算法选择联合概率P(p_k|R_k)最大的路径作为匹配路径.

例1:图 3为HMM地图匹配算法的示意图, 图中p₁~p₄为待匹配的轨迹点, r₁~r₅为路段.每个轨迹点对应的实心点是轨迹点的候选路段, 且每个实心点都有对应的发射概率, 即轨迹点与候选路段的匹配概率.每两个实心点之间有对应的转移概率, 以描述移动对象从一条路段移动到另一条路段的可能性.

(1轨迹点p₁的候选路段为{r₁, r₃, r₅}, 此时, 算法将p₁的所有候选路段作为候选路径;

(2) 当轨迹点p₂的候选路段{r₃, r₅}加入候选路径后, 此时, 候选路径为{(r₁, r₃), (r₃), (r₅)}, 且每条候选路径都可以计算其联合概率;

(3) 当最后一个轨迹点p₄的候选路段加入后, 候选路径更新为{(r₁, r₃, r₄), (r₃, r₄), (r₅, r₄)}, 算法最终选择其中联合概率最大的路径作为轨迹(p₁, p₂, p₃, p₄)的匹配路径.

2.3 O’Rourke算法

本文还采用了经典的O’Rourke^[21]算法, 用于判断是否存在一条直线同时穿过一组连续的取值范围.

如图 4所示, 考虑由(d, t)构成的二维空间, O’Rourke算法的目标是在(d, t)二维平面中找到一条穿越取值范围{(t_s, a_s, w_s), …, (t_k, a_k, w_k)}(s < k)的穿越直线L_sk.O’Rourke算法通过半平面相交的方法寻找穿越直线.首先, 对于第i个范围(t_i, a_i, w_i), 穿过它的直线必定满足a_i≤k×t_i+b≤w_i.通过变形进一步得到由变量k和b构成的方程组:

$ \left\{ \begin{array}{*{35}{l}} b\ge (-{{t}_{i}})\times k+{{a}_{i}} \\ b\le (-{{t}_{i}})\times k+{{w}_{i}} \\ \end{array} \right.. $

该方程组在k-b空间下表示两个边界平行的半平面相交区域(如图 5所示).

因此, 若存在穿过范围序列{(t_s, a_s, w_s), …, (t_k, a_k, w_k)}的直线, 则这些半平面在k-b空间下存在共同的相交区域, 且该区域为凸多边形; 否则, 这些半平面没有共同的相交区域.

给定范围序列{(t₁, a₁, w₁), …, (t_n, a_n, w_n)}, O’Rourke算法以(t₁, a₁, w₁)作为初始范围(t_s, a_s, w_s), 依次处理每个数据范围(t_i, a_i, w_i), 1≤i≤n, 计算k-b空间下的相交区域D, 若D不为空, 则继续下一个数据范围; 否则, 输出序列{(t_s, a_s, w_s), …, (t_i-1, a_i-1, w_i-1)}的穿越直线, 并且以(t_i-1, a_i-1, w_i-1)作为新的初始范围(t_s, a_s, w_s), 重复上述过程, 直到所有的数据范围都处理完成.O’Rourke算法的时间复杂度为O(n).

例2:给定范围序列{(t₁, a₁, w₁), …, (t₅, a₅, w₅)}, 图 4的L₁₃和L₃₅为该范围序列的穿越直线, 图 5为半平面交集求解过程.图 5中, 范围序列{(t₁, a₁, w₁), (t₂, a₂, w₂), (t₃, a₃, w₃)}的半平面在k-b空间下相交于D₁, 范围(t₄, a₄, w₄)在k-b空间下的半平面相交区域与D₁不重叠.因此, 算法输出{(t₁, a₁, w₁), (t₂, a₂, w₂), (t₃, a₃, w₃)}的穿越直线L₁₃.然后从(t₃, a₃, w₃)开始到序列结束, 范围序列{(t₃, a₃, w₃), (t₄, a₄, w₄), (t₅, a₅, w₅)}在k-b空间下相交于D₂.因此, 算法输出{(t₃, a₃, w₃), (t₄, a₄, w₄), (t₅, a₅, w₅)}的穿越直线L₃₅.注意:直线L₁₃和L₃₅在t₃时刻是不连续的.

3 距离有界的地图匹配方法

基于路网的轨迹压缩算法^{[7, 8, 19]}首先将原始轨迹匹配到路网上, 并且普遍采用了基于HMM的路网匹配算法^[30-32].但这些HMM地图匹配算法都不是针对轨迹压缩而设计的, 因而存在明显的缺陷.

(1) 没有考虑路网质量对匹配效果的影响, 进而影响了压缩率;

(2) 对于最大匹配距离和移动对象的运动方向没有限制, 导致了不合理的匹配, 同样影响了压缩的效果和性能.

针对上述问题, 本节首先分析了路网数据质量问题, 然后提出了一种距离有界的在线地图匹配方法, 通过限制最大匹配距离、将移动对象运动方向加入计算等方法, 提高了匹配的效果, 使其更适合于轨迹压缩.

3.1 路网质量的考虑

实际应用中, 由于地图数据不精确或地图更新不及时等原因, 通常会出现路网中相邻的道路不相连的情况.这种情况会影响到转移概率的计算, 从而导致匹配结果不准确.如图 6所示, 在实际中, 路段r₂和路段r₃是相连的, 即, 移动对象可以由路段r₂移动到路段r₃, 因此, 轨迹点p_i的匹配路段为r₂, 轨迹点p_i+1的匹配路段为r₃.然而, 由于路网数据质量问题导致路段r₂和路段r₃不相连, 使其不符合地理信息数据质量的逻辑一致性原则^{[33, 34]}(在著名的Openstreetmap中, 这种现象十分普遍.例如, 文献[34]对法国两个不同区域的Openstreetmap进行评估, 发现68%被测试区域的路网结构不符合逻辑一致性.本文对Openstreetmap北京地图进行统计, 由上述不连接造成的违背逻辑一致性的情况约占所有路段的34%), 造成不合理的转移概率和匹配结果.

对此, 本文统计了某专车的北京轨迹, 通过大量的轨迹来判断两个相近路段之间的连接性, 以此为基础完善路网信息.统计结果表明:在本文使用的路网数据OpenStreetMap中, 两条距离相近但不直接连接路段的平均距离为48m, 而其中的大部分实际上是存在通路的.

3.2 距离有界的路段选择

路网匹配时, 需要从路网中挑选候选路段.传统的HMM地图匹配方法考虑路网中的所有路段, 这会导致轨迹点到匹配路段的匹配距离没有上界.这样的匹配是极不合理的(如图 7所示).针对这种情况, 本文引入距离限制.给定距离阈值d和轨迹点p, 本文匹配方法只考虑与p的距离小于δ的路段.若轨迹点的匹配范围内不存在匹配路段, 此时我们可以认为地图中没有包含移动对象所在的路段数据, 或者移动对象在一块没有路段的平地上行驶.对于没有匹配路段的轨迹点, 本文采用保存原始轨迹点的策略.这种方法保证了原始轨迹点和匹配轨迹点的距离是有界的, 并且提高了匹配轨迹与原始轨迹的相似性.

图 8为由9个轨迹点组成的轨迹在路网上的示例图.圆圈半径表示距离阈值d, 轨迹点p₁, p₂, p₃, p₇, p₈, p₉在阈值范围内存在候选路段, 轨迹点p₁, p₂的候选路段为{r₁}, 轨迹点p₃的候选路段为{r₂, r₃}, 轨迹点p₇, p₈, p₉的候选路段为{r₅}.而轨迹点p₄, p₅, p₆在阈值范围内没有候选路段, 因此, 算法保留原始轨迹点{p₄, p₅, p₆}.

3.3 发射概率的计算

由于候选路段受到距离和行驶方向的影响, 本文在公式(1)的基础上, 将发射概率定义为

$ P = f(\alpha ) \times \frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} \ {\sigma _{ped}}}}{{\rm{e}}^{-0.5 \times {{\left( {\frac{{||ped||}}{{{\sigma _{ped}}}}} \right)}^2}}} $

(4)

其中,

$ f(\alpha ) = \left\{ {\begin{array}{*{20}{l}} {0, \;\;\;\;\;\;\;\;\;|\alpha |-\theta > 0}\\ {1-\frac{{|\alpha |}}{\theta }, {\rm{ }}|\alpha |-\theta \le 0} \end{array}} \right.. $

ped为轨迹点到匹配道路的匹配距离, σ_ped为ped的标准差; θ为角度常数, 缺省值是π/4;α为轨迹点移动方向偏离路段方向的夹角(如图 9所示), 且-π < α < π.本文只选取夹角绝对值小于θ的路段作为轨迹点的候选路段.

3.4 路径匹配算法

在上述方法的基础上, 本文设计实现了在线地图匹配.在地图匹配过程中, 当输入的轨迹点无法匹配到路网, 从而导致匹配算法中断时, 算法选择联合概率最大的匹配路径作为轨迹的最佳匹配路径.若轨迹点在匹配距离阈值内没有候选路段, 则算法保存原始轨迹点.

算法1为本文地图匹配算法伪代码DistBoundedMapMatching, 算法输入为轨迹$\dddot T = \{ {p_1}, {p_2}, ..., {p_n}\} $, 输出为匹配子轨迹集$\overline{\overline{TSet}}$和没有匹配路段的未匹配子轨迹集TSet.

算法1.地图匹配算法.

输入:轨迹$\dddot T = \{ {p_1}, {p_2}, ..., {p_n}\} $及最大匹配距离d;

输出:匹配子轨迹集$\overline{\overline{TSet}}$和未匹配子轨迹集TSet.

1.    $\overline{\overline{TSet}}=\varnothing ;\overline{TSet}=\varnothing $; Rset=Ø;                    //RSet保存当前所有候选路径

2.    for i=1 to N do

3.      if candRoads(p_i)=Ø then                    //p_i没有候选道路

4.        if $\bar T = \emptyset $ then

5.          $\overline{\overline{TSet}}\leftarrow \bar{\bar{T}}$;

6.        $\bar T \leftarrow {p_i}$;

7.      if candRoads(p_i)≠Ø then

8.          if RSet=Ø then

9.            RSet←candRoads(p_i); $\overline {TSet} \leftarrow \bar T;$

10.          else for ${{\bar{\bar{p}}}_{i}}$ in candRoads(p_i)

11.            $\bar{\bar{T}}=RSet[\max (P(\{{{p}_{s}}, ..., {{p}_{i-1}}\}|{{R}_{i-1}})\times P({{\bar{\bar{p}}}_{i-1}}.r, {{\bar{\bar{p}}}_{i}}.r))];$

12.             $\bar{\bar{T}}\leftarrow {{\bar{\bar{p}}}_{i}}$; update P({p_s, …, p_i}|R_i) and RSet;       //更新$\overline{\overline{TSet}}$的联合概率及RSet

13.  return $\overline{\overline{TSet}}\And \overline{TSet}$;

算法步骤解释如下:

●第1行中, RSet保存当前所有的匹配路径;

●第2行遍历轨迹点;

●第3行中函数candRoads(p_i)求轨迹点p_i的候选路段;

●第3行~第5行表示若轨迹点p_i没有匹配路段, 且当前未匹配子轨迹T为空时, 则将当前匹配子轨迹$\overline{\overline{T}}$放入匹配子轨迹集$\overline{\overline{TSet}}$中;

●第6行为将没有匹配路段的轨迹点p_i插入当前未匹配子轨迹T;

●第7行, 若轨迹点p_i有匹配路段, 则继续往下执行;

●在第8行、第9行, 当p_i存在匹配路段时, 若RSet为空, 则p_i为当前轨迹段的起点, 将p_i的所有匹配路段作为当前的匹配路径集;

●若RSet不为空, 算法10行遍历p_i所有的候选路段, 并得到路段上的匹配轨迹点${{\bar{\bar{p}}}_{i}}$;

●第11行, 选择RSet中$P(\{{{p}_{s}}, ..., {{p}_{i-1}}\}|{{R}_{i-1}})\times P({{\bar{\bar{p}}}_{i-1}}.r, {{\bar{\bar{p}}}_{i}}.r)$值最大的路径作为当前匹配轨迹$\overline{\overline{T}}$的路径;

●第12行将p_i对应的匹配轨迹点${{\bar{\bar{p}}}_{i}}$插入$\overline{\overline{T}}$, 更新$\overline{\overline{T}}$对应路径的联合概率P({p_s, …, p_i}|R_i)及当前的Rset;

●第13行, 算法最终返回$\overline{\overline{TSet}}$和TSet.

记轨迹$\dddot T$的长度为n, 每个轨迹点平均拥有m条候选路段, 最长匹配子轨迹和最长未匹配子轨迹的长度分别为k和w.在算法执行前, 本文对路网进行划分网格预处理工作, 其目的是在计算每个轨迹点的候选路段时, 将轨迹点的坐标值转换为网格的索引ID, 并得到对应网格内的所有路段, 即, 获取每个轨迹点的候选路段时间的复杂度为O(1).当轨迹点的候选路段集为空时, 轨迹点加入未匹配子轨迹, 该操作的时间复杂度为O(1);当轨迹点的候选路段集不为空时, 遍历所有候选路段并将其加入当前匹配路径, 该过程的时间复杂度为O(m).因此, 匹配算法总体的时间复杂度为O(n×m).算法当前候选路径集RSet需要O(km²)空间; 函数candRoads(p_i)的空间复杂度为O(m); 当前匹配子轨迹和未匹配子轨迹的分别需要O(k)和O(w)空间, 故算法总的空间复杂度为O(km²).

4 误差有界的匹配轨迹压缩

本节在O’Rourke^[21]算法的基础上给出了匹配轨迹的一种误差有界的高效压缩方法, 该方法通过回溯的方式解决了直接采用O’Rourke算法压缩轨迹所导致的线段不连续的问题.

4.1 问题描述

匹配轨迹$\bar{\bar{T}}=\{{{\bar{\bar{p}}}_{s}}, ..., {{\bar{\bar{p}}}_{k}}\}$可以等价地表示为$\bar{\bar{T}}=(R, \bar{\bar{S}}), $其中, R为匹配轨迹的路径, $\bar{\bar{S}}=\{({{d}_{s}}, {{t}_{s}}), ..., ({{d}_{k}}, {{t}_{k}})\}$为路径R上的轨迹点序列, 并且d_i为${{\bar{\bar{p}}}_{i}}$相对路径R起点的道路距离.由此, R可以采用更紧凑的编码方式, 从而达到无损压缩的目的(关于R的编码见文献[7, 28], 不在本文的考虑范围).而$\bar{\bar{S}}$是时序数据^{[20, 35, 36]}, 可以被进一步压缩.本文在算法O’Rourke^[21]的基础上, 设计了一种误差有界的压缩算法.相比PRESS所采用的压缩算法^[8], O’Rourke算法可以用一条线段表示更多的轨迹点, 因而具有潜在的更好的压缩率.然而, 直接采用O’Rourke算法又将导致线段不连续的问题, 如图 4所示:穿越直线L₁₃与穿越直线L₃₅在t₃时刻与范围(t₃, a₃, w₃)相交于不同的两点, 导致在t₃时刻L₁₃与L₃₅不连续.这种情况一方面影响压缩效果, 另一方面, 这种不连续意味着需要保存更多的信息, 比如对于图 4的t₃时刻, 需要保存${{{p}'}_{3}}$和${{{p}''}_{3}}$两个点的信息, 这不利于提高压缩率.针对这个问题, 本文提出一种保证压缩结果连续的压缩方法.

4.2 算法原理

给定轨迹点序列$\bar{\bar{S}}=\{({{d}_{s}}, {{t}_{s}}), ..., ({{d}_{k}}, {{t}_{k}})\}$及误差阈值ε, $\bar{\bar{S}}$可以表示为范围序列{(t_s, d_s-ε, d_s+ε), …, (t_k, d_k-ε, d_k+ε)}.算法分两个步骤:首先, 采用O’Rourke算法计算每个最长的子范围序列以及该序列的穿越直线集; 其次, 逆向确定唯一的穿越直线序列.

(1) 计算每个最长子范围序列, 并得到每个最长子范围序列的穿越直线集.

算法以(t_s, d_s-ε, d_s+ε)作为初始范围, 计算过程如下.

a) 利用O’Rourke算法计算能同时被穿越直线穿过的最长子范围序列, {(t_i, d_i-ε, d_i+ε), …, (t_j, d_j-ε, d_j+ε)}(s≤i≤j≤k), 得到该范围序列内的穿越直线集L_ij, 表现为O’Rourke算法中k-d空间下的一个凸多边形.此时, (d_j, t_j)为子范围序列的端点, 称为断点;

b) 计算穿越直线集L_ij中斜率最大与最小的直线, 分别得到其在范围(t_j, d_j-ε, d_j+ε)内的交点(a_j, t_j)和(w_j, t_j).将(t_j, a_j, w_j)作为t_j时刻新的范围, 并将它作为后续计算的初始范围;

c) 重复上述过程a)和过程b), 直到处理完所有轨迹点.此时得到t_n时刻新的范围(t_n, a_n, w_n).

例3:图 10是在t-d空间和k-b空间下, 匹配轨迹$\bar{\bar{T}}=\{{{\bar{\bar{p}}}_{1}}, {{\bar{\bar{p}}}_{2}}, {{\bar{\bar{p}}}_{3}}, {{\bar{\bar{p}}}_{4}}, {{\bar{\bar{p}}}_{5}}\}$($\bar{\bar{T}}$还可表示为$\bar{\bar{T}}=(R, \bar{\bar{S}})$)在压缩误差ε下的压缩过程示意图.图 10(a1)中, $\{{{\bar{\bar{p}}}_{1}}, {{\bar{\bar{p}}}_{2}}, {{\bar{\bar{p}}}_{3}}\}$在取值范围内存在穿越直线, $\{{{\bar{\bar{p}}}_{1}}, {{\bar{\bar{p}}}_{2}}, {{\bar{\bar{p}}}_{3}}, {{\bar{\bar{p}}}_{4}}\}$在误差范围内不存在穿越直线.在$\{{{\bar{\bar{p}}}_{1}}, {{\bar{\bar{p}}}_{2}}, {{\bar{\bar{p}}}_{3}}\}$所有的穿越直线中, 斜率最大和最小的穿越直线与${{\bar{\bar{p}}}_{3}}$点处的误差范围(t₃, d₃-ε, d₃+ε)交于(a₃, t₃)和(w₃, t₃)两点.该过程在k-b空间下对应于图 10(b1), $\{{{\bar{\bar{p}}}_{1}}, {{\bar{\bar{p}}}_{2}}, {{\bar{\bar{p}}}_{3}}\}$对应的平行直线形成凸多边形D₁, ${{\bar{\bar{p}}}_{4}}$点对应的两条平行直线b=-t₄×k+d₄-ε和b=-t₄×k+d₄+ε与D₁不相交.因此, 算法保存当前的凸多边形D₁, 并由凸多边形D₁可得到${{\bar{\bar{p}}}_{3}}$点的新的取值范围(t₃, a₃, w₃).

图 10(a2)中, 从${{\bar{\bar{p}}}_{3}}$点以新的误差范围(t₃, a₃, w₃)作为t₃时刻的范围, 重新开始计算${{\bar{\bar{p}}}_{3}}$, ${{\bar{\bar{p}}}_{4}}$及其后面的点的误差范围内是否存在共同的穿越直线, 直到该轨迹在点${{\bar{\bar{p}}}_{5}}$结束时, $\{{{\bar{\bar{p}}}_{3}}, {{\bar{\bar{p}}}_{4}}, {{\bar{\bar{p}}}_{5}}\}$的穿越直线中, 斜率最大和最小的穿越直线在${{\bar{\bar{p}}}_{5}}$点处的误差范围(t₅, d₅-ε, d₅+ε)交于(a₅, t₅)和(w₅, t₅)两点, 此时, t₅时刻的范围更新为(t₅, a₅, w₅).该过程在k-b空间下对应于图 10(b2), $\{{{\bar{\bar{p}}}_{3}}, {{\bar{\bar{p}}}_{4}}, {{\bar{\bar{p}}}_{5}}\}$误差范围内的穿越直线形成凸多边形D₂, 沿D₂以斜率-t₅的2条直线与b轴相交于a₅和w₅.

(2) 逆向二次更新断点处的范围, 确定唯一的穿越直线序列.

令压缩后的匹配轨迹为${{\bar{\bar{S}}}^{\prime }}=\{({{{d}'}_{s}}, {{{t}'}_{s}}), ..., ({{{d}'}_{m}}, {{{t}'}_{m}})\}$, 计算过程如下:

a) 二次更新${{{t}'}_{m}}$时刻的范围$({t'_m}, {a'_m}, {w'_m}) = ({t'_m}, {a_m}, {w_m})$, 确定${{\bar{\bar{S}}}^{\prime }}$中最后一个压缩轨迹点:

$ ({{{d}'}_{m}}, {{{t}'}_{m}}), {{{d}'}_{m}}=({{{a}'}_{m}}+{{{w}'}_{m}})/2, {{{t}'}_{m}}={{t}_{k}}; $

b) 设${{{t}'}_{m-1}}={{t}_{f}}$, 且过$({{{a}'}_{m}}, {{{t}'}_{m}})$和$({{{w}'}_{m}}, {{{t}'}_{m}})$的穿越直线在t_f范围内交于$({{{a}'}_{f}}, {{t}_{f}})$和$({{{w}'}_{f}}, {{t}_{f}})$两点.二次更新${{{t}'}_{m-1}}$时刻的新范围为$({{{t}'}_{m-1}}, {{{a}'}_{f}}, {{{w}'}_{f}})$, 确定压缩轨迹点$({{{d}'}_{m-1}}, {{{t}'}_{m-1}})$, 其中,

${{{d}'}_{m-1}}=({{{a}'}_{f}}+{{{w}'}_{f}})/2, {{{t}'}_{m-1}}={{t}_{f}};$

c) 重复b)过程, 依次确定${{\bar{\bar{S}}}^{\prime }}$中后续的值, 直到确定${{\bar{\bar{S}}}^{\prime }}$的起点$({{{d}'}_{s}}, {{{t}'}_{s}}).$

例4:图 11为在图 10的基础上, 确定唯一穿越直线序列并得到压缩匹配轨迹${{\bar{\bar{S}}}^{\prime }}$的过程.

图 11(a1)中, 二次更新t₅时刻的范围$({t_5}, {a'_5}, {w'_5}) = ({t_5}, {a_5}, {w_5})$, 确定${{\bar{\bar{S}}}^{\prime }}$中最后一个轨迹点${{\bar{\bar{p}}}^{\prime }}_{5}=({{{d}'}_{5}}, {{t}_{5}})$, 其中, ${{{d}'}_{5}}=({{{a}'}_{5}}+{{{w}'}_{5}})/2$.过$({{{a}'}_{5}}, {{t}_{5}})$和$({{{w}'}_{5}}, {{t}_{5}})$的穿越直线在断点${{\bar{\bar{p}}}_{3}}$的范围内交于$({{{w}'}_{3}}, {{t}_{3}})$和$({{{a}'}_{3}}, {{t}_{3}})$两点.二次更新t₃时刻的新范围为$({{t}_{3}}, {{{a}'}_{3}}, {{{w}'}_{3}}), $确定压缩轨迹点${{\bar{\bar{p}}}^{\prime }}_{3}=({{{d}'}_{3}}, {{t}_{3}})$, 其中, ${{{d}'}_{3}}=({{{a}'}_{3}}+{{{w}'}_{3}})/2$.该过程在k-b空间下对应于图 11(b1), 沿D₂以斜率-t₅的2条直线与b轴相交于${{{a}'}_{5}}$和${{{w}'}_{5}}$; 沿D₂以斜率-t₃的2条直线与b轴相交于${{{a}'}_{3}}$和${{{w}'}_{3}}$.${{{d}'}_{5}}$和${{{d}'}_{3}}$分别取${{{a}'}_{5}}$和${{{w}'}_{5}}$的中点和${{{a}'}_{3}}$与${{{w}'}_{3}}$的中点.

在图 11(a2)中, 过$({{{w}'}_{3}}, {{t}_{3}})$和$({{{a}'}_{3}}, {{t}_{3}})$的穿越直线在断点${{\bar{\bar{p}}}_{1}}$的范围内交于$({{{a}'}_{1}}, {{t}_{1}})$和$({{{w}'}_{1}}, {{t}_{1}})$两点.二次更新t₁时刻的新范围为$({{t}_{1}}, {{{a}'}_{1}}, {{{w}'}_{1}}), $确定压缩轨迹点${{\bar{\bar{p}}}^{\prime }}_{1}=({{{d}'}_{1}}, {{t}_{1}})$, 其中, ${{{d}'}_{1}}=({{{a}'}_{1}}+{{{w}'}_{1}})/2$.该过程在k-b空间下对应于图 11(b2), 沿D₂以斜率-t₁的2条直线与b轴相交于${{{a}'}_{1}}$和${{{w}'}_{1}}$, ${{{d}'}_{1}}$取${{{a}'}_{1}}$与${{{w}'}_{1}}$的中点.

最终, 压缩后的匹配轨迹为${{\bar{\bar{T}}}^{\prime }}=\{R, {{\bar{\bar{S}}}^{\prime }}\}, $其中, ${{\bar{\bar{S}}}^{\prime }}=\{{{\bar{\bar{p}}}^{\prime }}_{1}, {{\bar{\bar{p}}}^{\prime }}_{3}, {{\bar{\bar{p}}}^{\prime }}_{5}\}.$

4.3 算法实现

算法2为匹配轨迹压缩算法RoadBasedCompression.算法的输入为匹配轨迹$\bar{\bar{T}}$及误差阈值ε, 输出为压缩后的匹配轨迹${{\bar{\bar{T}}}^{\prime }}.$

算法2.匹配轨迹压缩算法.

输入:匹配轨迹$\bar{\bar{T}}=\{{{\bar{\bar{p}}}_{s}}, ..., {{\bar{\bar{p}}}_{k}}\}$及误差阈值ε;

输出:压缩后的匹配轨迹${{\bar{\bar{T}}}^{\prime }}=\{{{\bar{\bar{p}}}^{\prime }}_{s}, ..., {{\bar{\bar{p}}}^{\prime }}_{m}\}.$

1.    polygonList=Ø; index=s; $\overline{\overline{S}}=\{({{d}_{s}}, {{t}_{s}}), ..., ({{d}_{k}}, {{t}_{k}})\}$            //index指向当前断点的位置

2.     for i=s to k do

3.      if intersection(polygon, ${{\bar{\bar{p}}}_{i}}$)=Ø||i=k then            //不存在穿越直线或者轨迹结束

4.        polygonList←polygon;              //将当前凸多边形加入polygonList

5.        (a_i-1, w_i-1)=updateRange(t_i-1);

6.         if i < n then index←(--i)             //更新index

7.       if intersection(polygon, ${{\bar{\bar{p}}}_{i}}$)≠Ø then            //存在穿越直线

8.        polygon(${{\bar{\bar{p}}}_{i}}$);             //更新加入${{\bar{\bar{p}}}_{i}}$后的凸多边形

9.     for j=polygonList.size to 1 do

10.        $({{{a}'}_{j}}, {{{w}'}_{j}})$=updateRange(polygonList[j]); ${{{d}'}_{j}}=({{{a}'}_{j}}+{{{w}'}_{j}})/2$;      //更新误差范围

11.        ${{\bar{\bar{S}}}^{\prime }}\leftarrow ({{{d}'}_{j}}, {{t}_{j}})$;

12. return${{\bar{\bar{T}}}^{\prime }}={{\bar{\bar{S}}}^{\prime }}$;

算法步骤解释如下:

●第1行中, polygonList为凸多边形的列表, 保存当前所有的凸多边形, index指向当前断点的位置, 初始时, 使其指向第1个轨迹点.$\bar{\bar{S}}$为$\bar{\bar{T}}$对应的匹配路径轨迹;

●第2行遍历轨迹点序列;

●第3行~第6行表示若第i个轨迹点与当前的凸多边形无交点, 即不存在穿越直线, 则将当前凸多边形加入polygonList中, 并更新断点时刻的范围;

●否则, 在第8行更新当前的凸多边形polygon;

●第9行倒序遍历凸多边形列表polygonList;

●第10行和第11行重新更新每个断点的凸多边形, 二次更新断点的范围$({{t}_{j}}, {{{a}'}_{j}}, {{{w}'}_{j}})$, 则得到压缩轨迹点$({{{d}'}_{j}}, {{t}_{j}}), $其中, ${{{d}'}_{j}}$取${{{a}'}_{j}}$和${{{w}'}_{j}}$的中值, 并将压缩轨迹点$({{{d}'}_{j}}, {{t}_{j}})$加入压缩轨迹${{\bar{\bar{S}}}^{\prime }}$中;

●第12行将${{\bar{\bar{S}}}^{\prime }}$构造为${{\bar{\bar{T}}}^{\prime }}$, 返回${{\bar{\bar{T}}}^{\prime }}$

记匹配轨迹$\bar{\bar{T}}$的长度为n, 压缩后匹配轨迹${{\bar{\bar{T}}}^{\prime }}$的长度为m, 算法第1步采用O’Rourke算法得到每个最长子范围序列的穿越直线集, 这个过程的时间复杂度为O(n); 第2步逆向确定唯一穿越直线序列的时间复杂度为O(m), 故匹配轨迹压缩算法的时间复杂度为O(n+m).在第1步中需要保存k-b空间下每个断点对应的凸多边形, 该算法的空间复杂度为O(m).

5 路网感知的轨迹压缩系统

基于上文提出的地图匹配算法和轨迹压缩算法, 本节设计并实现了路网感知的在线轨迹压缩系统.该系统可在移动端对轨迹进行在线压缩, 不仅减少了移动端上传轨迹的流量消耗, 也节省了服务端的存储空间.

5.1 系统结构与工作原理

路网感知的轨迹压缩系统的组成结构如图 12所示.该系统由地图加载(map loading)、地图匹配(map matching)、匹配轨迹压缩(road-based simplification)和未匹配轨迹压缩(piece-wise line simplification)这4个部分组成.

●地图加载:由于路网感知的轨迹压缩系统运行在客户端, 因此客户端需存在相应地图. ROADER系统允许客户端离线下载指定地图, 也可以在压缩的过程中在线下载移动轨迹区域的地图. ROADER对地图进行网格划分, 以每个网格作为地图加载的最小单位.离线下载地图时, 地图加载模块按照指定的区域范围, 将区域中所有网格内的地图加载到客户端.当客户端存储量较小时, 可以选择在线加载移动轨迹所在的区域, 若客户端没有轨迹所在区域的地图, 则将轨迹所在的网格以及周围的8个网格内的地图加载到客户端.在线加载地图按需下载部分地图数据, 节省了客户端的流量和存储量;

●地图匹配:该模块实现了距离有界的地图匹配.为使匹配结果更合理, 在匹配过程中, 轨迹点选择匹配距离阈值d内的路段作为匹配路段.若轨迹点在阈值δ内无候选路段, 则保留原始的轨迹点.地图匹配的输出是匹配轨迹和未匹配的轨迹;

●匹配轨迹压缩:该模块对地图匹配结果中的匹配轨迹进行压缩, 且保证压缩误差小于给定的阈值ε.匹配轨迹压缩算法在提高压缩率的同时, 也保证压缩结果折线是连续的;

●未匹配轨迹压缩:该模块利用基于同步距离的线段简化算法TD-TR^[9]对地图匹配结果中未匹配的轨迹进行压缩, 压缩阈值大小为$\sqrt{{{\delta }^{2}}+{{\varepsilon }^{2}}}$.线段简化算法实现原理简单、压缩率高.

5.2 算法实现

算法3 RoadAwareCompression是ROADER主算法.

算法3.路网感知的轨迹压缩算法.

输入:轨迹$\dddot T = \{ {p_0}, {p_1}, ..., {p_n}\} $, 窗口大小WSIZE, 最大匹配距离δ和最大匹配轨迹误差ε;

输出:压缩后的匹配子轨迹集${{\overline{\overline{TSet}}}^{\prime }}$及压缩后的未匹配子轨迹集${{\overline{TSet}}^{\prime }}.$

1.    While (having points in $\dddot T$) do

2.     T=LoadSubTraj($\dddot T$, WSIZE); G=LoadMap(T);        //加载轨迹至窗口及窗口内轨迹的地图

3.     (${\overline{\overline {TSet}} ^\prime }, {\overline {TSet} ^\prime }$)=DistBoundedMapMatching(T, G, δ);        //得到匹配轨迹$\overline{\overline {TSet}} $和未匹配轨迹TSet

4.      ${\overline{\overline {TSet}} ^\prime }$=RoadBasedCompression($\overline{\overline {TSet}} $, ε);          //对$\overline{\overline {TSet}} $执行基于路网的压缩

5.      ${\overline {TSet} ^\prime }$=LineSimplification(TSet, $\sqrt {{\delta ^2} + {\varepsilon ^2}} $);        //对TSet执行基于线段的压缩

6. output ${\overline{\overline {TSet}} ^\prime }$ and ${\overline {TSet} ^\prime }$       //输出数据

算法过程如下.

(1) 加载子轨迹至窗口(LoadSubTraj), 并读取窗口内轨迹的路段信息(LoadMap);

(2) 执行距离有界地图匹配(DistBoundedMapMatching), 匹配结果为匹配子轨迹集$\overline{\overline {TSet}} $和未匹配子轨迹集TSet;

(3) 对匹配结果中的每个子轨迹分别进行误差有界的轨迹压缩并输出压缩结果:对$\overline{\overline {TSet}} $中的每条匹配子轨迹$\overline{\overline {TSet}} $执行基于路网的轨迹压缩(RoadBasedCompression); 对TSet中的每条未匹配子轨迹T执行基于线段的轨迹压缩(LineSimplification);

(4) 算法重复以上过程, 直到所有的轨迹点都处理完成.

令轨迹$\dddot T$的长度为n, 每个轨迹点平均拥有m条候选路段, 轨迹$\dddot T$中匹配轨迹$\bar{\bar{T}}$所占比例为γ, 其中, 最长匹配子轨迹的长度为k, 则ROADER系统加载轨迹(LoadSubTraj)过程的时间复杂度为O(n); 地图加载(LoadMap)的时间复杂度为O(|G|), |G|为地图大小; 距离有界的地图匹配(DistBoundedMapMatching)时间复杂度为O(mn); 匹配轨迹基于路网的轨迹压缩过程的时间复杂度为O(γn); 未匹配轨迹基于线段的压缩算法TD-TR^[9]的时间复杂度为O((1-γ)²n²).故ROADER系统总时间复杂度为O((1-γ)²n²+mn+|G|).对于算法的空间复杂度, 算法的空间主要用于地图加载和地图匹配, 复杂度为O(|G|+km²).

例5:图 13是长度为10的轨迹$\dddot T = \{ {p_1}, ..., {p_{10}}\} $的压缩示例, 虚线表示路网中没被收录的小径, 路段r₁~r₄为路网中的路段.移动对象的轨迹是沿着路段r₁运动到图中虚线表示的小径, 再运动到路段r₃和路段r₄.

(1) ROADER首先加载轨迹$\dddot T = \{ {p_1}, ..., {p_{10}}\} $, 然后加载轨迹所在的区域的地图;

(2) ROADER对窗口内的轨迹进行地图匹配.给定最大匹配距离δ, 轨迹点选择最大匹配范围内的路段作为候选路段, 若在最大范围内, 轨迹点没有匹配路段, 匹配算法保留其原始轨迹点.图 13中的虚线圆代表最大匹配距离的范围, 这种情况下, 地图匹配的输出为匹配子轨迹序列$\overline{\overline{TSet}}=\{{{\bar{\bar{T}}}_{1}}, {{\bar{\bar{T}}}_{2}}\}$(其中, ${{\bar{\bar{T}}}_{1}}=\{{{\overline{\overline{p}}}_{1}}{{\overline{\overline{p}}}_{2}}\}, {{\bar{\bar{T}}}_{2}}=\{{{\overline{\overline{p}}}_{7}}, {{\overline{\overline{p}}}_{8}}, {{\overline{\overline{p}}}_{9}}, {{\overline{\overline{p}}}_{10}}\}$)以及未匹配子轨迹序列$\overline{TSet}=\{\bar{T}\}$(其中, $\bar{T}=\{{{\bar{p}}_{3}}, {{\bar{p}}_{4}}, {{\bar{p}}_{5}}, {{\bar{p}}_{6}}\}$).注意:匹配子轨迹${{\bar{\bar{T}}}_{1}}$和${{\bar{\bar{T}}}_{2}}$还可以表示为

${{\bar{\bar{T}}}_{1}}=\{\{{{r}_{1}}\}, \{({{d}_{1}}, {{t}_{1}}), ({{d}_{2}}, {{t}_{2}})\}\}, {{\bar{\bar{T}}}_{2}}=\{\{{{r}_{3}}, {{r}_{4}}\}, \{({{d}_{7}}, {{t}_{7}}), ({{d}_{8}}, {{t}_{8}}), ({{d}_{9}}, {{t}_{9}}), ({{d}_{10}}, {{t}_{10}})\}\};$

(3) 分别对匹配轨迹和未匹配轨迹进行轨迹压缩.由于${{\bar{\bar{T}}}_{1}}$中只包含2个点, 因此压缩后的轨迹仍保留起点和终点两个点, 故压缩后${{\bar{\bar{T}}}^{\prime }}_{1}=\{\{{{r}_{1}}\}, \{({{{d}'}_{1}}, {{t}_{1}}), ({{{d}'}_{2}}, {{t}_{2}})\}\}, {{{d}'}_{1}}$和${{{d}'}_{2}}$分别表示压缩后的轨迹点距离路径{r₁}起点的距离.${{\bar{\bar{T}}}_{2}}$被压缩为$({{{d}'}_{7}}, {{t}_{7}})$和$({{{d}'}_{10}}, {{t}_{10}})$两个点, 即${{\bar{\bar{T}}}^{\prime }}_{2}=\{\{{{r}_{3}}, {{r}_{4}}\}, \{({{{d}'}_{7}}, {{t}_{7}}), ({{{d}'}_{10}}, {{t}_{10}})\}\}, {{{d}'}_{7}}$和${{{d}'}_{10}}$分别表示对应压缩后的轨迹点距离路径{r₃, r₄}起点的距离.未匹配子轨迹T由基于同步距离的DP算法压缩为${\bar{T}}'=\{{{\bar{p}}_{3}}, {{\bar{p}}_{5}}, {{\bar{p}}_{6}}\};$

(4) 最终的输出结果为$\overline{\overline{TSet}}=\{{{\bar{\bar{T}}}^{\prime }}_{1}, {{\bar{\bar{T}}}^{\prime }}_{2}\}$及$\overline{TSet}=\{{{\overline{T}}^{\prime }}\}.$

6 实验 6.1 实验设置

本文使用了某专车的北京市数据集和Geolife数据集.其中, 从Geolife数据集中拆出了Geolife北京市数据子集和Geolife华盛顿州数据子集.

●专车北京市数据:选取某专车公司在北京市100多辆车2天的行驶轨迹, 共包含719 816个轨迹点.该数据集采集频率为:62.4%为6s;15%为5s;10.9%为7s;3.46%为8s;8.24%为其他.其中, 最小的频率为1s, 占0.0000347%;

● Geolife数据:Geolife北京市数据子集选取自Geolife数据集的500多条北京市的轨迹, 共876 198个轨迹点; Geolife华盛顿州数据子集选取自Geolife数据集的79条美国华盛顿地区的轨迹, 共包含245 168个轨迹点.Geolife数据集采样频率(按比例从高到低)为:74.23为5s;7.71%为2s;7.44%为1s;7.41%为3s;2.17%为4s;1.04%为其他; 其中最小的频率为1s, 占7.44%.

本文对比了两个路网感知的轨迹压缩系统, 即本文系统ROADER和PRESS系统^[8].PRESS的地图匹配部分没有公开算法和源代码, 只提供了“.exe”可执行文件, 故在实验中, ROADER系统和PRESS系统的执行时间实验部分运行在Windows系统下.除此之外, PRESS系统的压缩算法和ROADER系统的全部都运行在linux中.实验计算机的硬件配置为32 Intel(R) Xeon(R) CPU E5-2650 0@2.00GHz, 内存大小为256G.

6.2 实验结果

本文进行了5组实验, 前4组实验分别对比了ROADER和PRESS两个系统:(1)压缩率; (2)匹配距离; (3)压缩误差; (4)执行效率; 第5组实验分析了移动端路网加载的效果.

6.2.1 压缩率

轨迹的压缩率(compression ratio, 简称CR)是衡量轨迹压缩效果的重要指标, 本文将压缩率定义为

$CR = \frac{{{M_{T'}}}}{{{M_{\dddot T}}}} \times 100\%, $

其中, ${M_{T'}}$为压缩后轨迹的存储量, ${M_{\dddot T}}$为原始轨迹存储量.

●实验A.1:窗口大小对ROADER压缩率的影响

为验证滑动窗口大小WSIZE对ROADER压缩率CR的影响, 本文固定匹配距离阈值δ=50m, 压缩误差ε=50m, 将WSIZE从30增加至400.图 14为3个数据集的实验结果, 从中可以发现:

(1) 轨迹压缩率CR随窗口WSIZE的增大而降低.由于随着窗口的增大, 地图匹配会对匹配路径不断修正, 而匹配准确性的提高有利于基于路网的压缩, 因此压缩率会降低;

(2) 当窗口达到200之后, 窗口的增大对压缩效果的提升很不明显;

(3) WSIZE > 30时, 窗口大小对压缩率的影响并不大.专车北京市数据集的轨迹压缩率基本维持在31%~ 32%之间; Geolife北京市数据集的压缩率基本维持在41.5%~42.7%之间; Geolife华盛顿数据集的压缩率在34%~35%之间.

●实验A.2:ROADER与PRESS的压缩率对比

本组实验比较了ROADER系统和PRESS系统在不同数据集下的压缩率, 以及在压缩轨迹结果中路径信息、轨迹点信息等各部分所占的比例.我们分别从10m~200m变换了匹配距离阈值d和压缩误差阈值ε.实验结果如图 15~图 17所示.其中, 图 15(a)、图 16(a)和图 17(a)为这3个数据集的压缩率, 蓝色细网格表示ROADER的总压缩率, 绿色粗网格ROADER-MM表示ROADER中匹配轨迹(road-aware trajectories)的压缩率, 红色虚线代表PRESS的压缩率.在PRESS中, 由于它在地图匹配中没有距离上界, 因此其压缩率只受压缩误差阈值ε的影响, 为便于比较, 我们将PRESS的结果画在图中d=200m处.图 15~图 17的(b)图和(c)图分别为3个数据集下, ROADER和PRESS的压缩结果数据中路径信息、轨迹点信息等各部分所占的比例.此外, 在ROADER系统中, 压缩后的轨迹点又分为匹配轨迹点和未匹配轨迹点, 对此, 本文用$RR = \frac{{{M_R}}}{{{M_{T'}}}} \times 100\% $表示压缩结果中路径数据占存储量的百分比, 用$MR=\frac{{{M}_{{{\overline{\overline{S}}}^{\prime }}}}}{{{M}_{{{T}'}}}}\times 100%$表示匹配轨迹点所占存储量的百分比, 用$NMR = \frac{{{M_{\bar T'}}}}{{{M_{T'}}}} \times 100\% $表示未匹配轨迹点所占存储量的百分比.

图 15~图 17说明:

(1) 在PRESS中, 压缩率表现为随ε的增加而减小.在ROADER中, 压缩率同时受δ和ε大小的影响.在同一阈值δ下, 压缩率随ε的增加而变小, 出现该结果的原因主要是匹配轨迹$\bar{\bar{T}}$和未匹配轨迹T的压缩都受ε变化的影响.同一ε下, ROADER-MM的压缩率总体上表现为随着δ的增加先变小后变大, 在δ=20m~60m之间, 压缩率达到最佳, 且ε越大, 使压缩率达到最小的最佳δ也越大;

(2) ROADER的压缩率整体上优于PRESS.在专车北京市数据集、Geolife北京市数据集和Geolife华盛顿数据集下, ROADER的压缩率分别优于PRESS的压缩率5%~13%, 12%~35%和6%~26%;

(3) ROADER中, 固定匹配距离δ=50m, 变化压缩误差ε, 则其压缩结果数据中路径信息的比例(RR)相比PRESS的RR大7%~20%, 这从侧面说明ROADER对匹配轨迹点的压缩效果明显优于PRESS.而且, ROADER还可进一步通过路径编码提高压缩率;

(4) 在Geolife数据集下, 由于该数据集中包含许多不在路网上的行人轨迹, 所以在该数据集下, UMGPSR的值相对其他数据集较大.对于这部分轨迹, ROADER采用基于同步距离的DP压缩算法^[9], 因此从图 16(a)和图 17(a)中可以看出:在δ取值为10m~30m之间时, ROADER受DP压缩算法的影响较大.

6.2.2 匹配距离

匹配距离指轨迹点到匹配路段的垂直距离, 是衡量匹配正确性的主要指标之一.该组实验分别在匹配距离阈值δ和压缩阈值ε下, 对ROADER和PRESS的匹配距离ped进行分析.表 1为3个数据集下, PRESS的平均匹配距离meanPed和最大匹配距离maxPed, 以及在所有匹配结果中匹配路段的方向与轨迹点运动方向相反的比例.图 18为3个数据集下, ROADER的平均匹配距离meanPed和最大匹配距离maxPed.

实验结果说明:

(1) PRESS的匹配距离最大可能达到40km以上, 即没有边界;

(2) ROADER的meanPed和maxPed都显著小于PRESS, 且ROADER的匹配距离是有界的;

(3) ROADER中, meanPed随δ的增加而增大, 且不受压缩阈值ε的影响.专车北京市数据集下的meanPed低于Geolife数据集下的meanPed约10%左右.原因是Geolife数据集的行人轨迹多, 导致未匹配轨迹占比大, 从而meanPed也较大;

(4) ROADER中, maxPed随δ的增加而增大, 且不受压缩阈值ε的影响.

6.2.3 匹配轨迹的压缩误差

匹配轨迹的压缩误差是指轨迹点的匹配点相对压缩轨迹的对应点的距离, 是衡量轨迹压缩的重要指标之一.本组实验分别在匹配距离阈值δ和压缩阈值ε下, 对ROADER和PRESS的压缩误差red进行实验.图 19和图 20分别是ROADER和PRESS在3个数据集下的平均误差meanRed和最大误差maxRed.实验结果说明:

(1) ROADER压缩误差受ε和δ的共同影响;

(2) ROADER和PRESS的meanRed都随ε的增加而增大.ROADER的meanRed开始随δ的增加而缓慢增大, 当δ大于一定值后, meanRed的增加变得缓慢;

(3) ROADER最好的meanRed较PRESS的meanRed值大2%~9%;ROADER最差的meanRed较PRESS的meanRed值大2%~35%;

(4) ROADER和PRESS的最大压缩误差maxRed均接近于ε.

6.2.4 执行时间

为比较ROADER和PRESS的执行时间runningTime, 本组实验分别调节匹配距离阈值δ和压缩阈值ε, 实验结果如图 21所示.实验结果说明:

(1) ROADER的执行时间随着ε的增大而减小; 随δ的增大先增大后减小, 再增大.PRESS压缩算法的执行时间随ε的增大而减小;

(2) ROADER整体快于PRESS.实验中, 压缩阈值ε取不同值时, 在专车北京市数据集下, PRESS的执行时间约为150分钟, 而ROADER的执行时间快于PRESS近120分钟; 在Geolife北京数据集下, PRESS的执行时间约为70分钟, ROADER快于PRESS约50分钟; 在Geolife华盛顿数据集下, PRESS的执行时间约为20分钟, ROADER快于PRESS约14分钟.

6.2.5 ROADER地图加载的网络流量分析

为分析ROADER在线下载地图的客户端流量消耗情况, 本文在专车北京数据集和Geolife北京数据集下进行了在线地图下载实验.实验结果如图 22所示.其中, Original-Traj是原始轨迹的大小, 即客户端直接将原始轨迹上传至服务端所产生的流量; Origi-Map是离线下载整个地图时客户端产生的流量; Map是客户端在线下载地图时产生的流量; ROADER-Traj & map是ROADER在客户端在线执行时, 上传压缩轨迹和在线下载地图产生的流量之和.实验结果说明:

(1) 原始轨迹数据量较小时, 客户端的流量消耗主要来自地图下载产生的流量.随着原始轨迹数据量的增加, 下载地图消耗的流量趋于稳定;

(2) 专车数据和Geolife数据有明显的不同.专车轨迹覆盖区域比较广, 因此在线下载的地图数据量较快接近于地图总数据量; 而Geolife中的移动对象为行人, 其通常在有限的且较固定的范围内活动, 因此其客户端只需下载有限的地图就能满足其轨迹的匹配需求.

7 结论

本文提出一种路网感知的在线轨迹压缩系统, 包括适合于轨迹压缩的距离有界的隐马尔可夫地图匹配算法和误差有界的高效轨迹压缩算法等.给定匹配距离阈值和压缩误差阈值, 该系统可以保证最终的压缩结果与原始轨迹的距离在阈值之内, 从而保证了压缩轨迹和原始轨迹的相似性.该系统不仅适用于移动对象不在路网道路中行驶的轨迹压缩, 也适用于路网信息不完整情况下的压缩.基于真实数据集的实验证明, 该系统在压缩率、误差和执行时间方面均显著优于同类算法.

未来还将从以下几方面继续改进该系统:(1)在HMM地图匹配模型的计算中加入其他能够提高匹配准确率的因素, 例如速度等; (2)对匹配道路进行模式挖掘或对路径进行编码, 进一步提高道路存储的压缩率.