一种面向路网的多维度自适应轨迹压缩方法
本发明涉及轨迹数据处理与压缩,具体涉及一种面向路网的多维度自适应轨迹压缩方法,针对于路网匹配后的道路段标识序列、沿路距离序列和时间戳序列进行联合压缩。可应用于车辆gps轨迹、出租车轨迹等移动对象轨迹数据的高效存储与传输,在轨迹数据库压缩、交通流分析、路径规划等领域有较好的应用前景。
背景技术:
1、随着gps设备、移动车载终端的广泛应用,大规模车辆轨迹数据被持续采集。轨迹数据记录了移动对象在时间和空间上的连续变化,记录了车辆出行路径和道路使用规律。然而,轨迹数据的规模急剧增长,对数据存储和传输提出了严峻挑战,轨迹压缩技术成为解决该问题的关键手段。
2、现有轨迹压缩方法主要分为两类:面向自由空间的方法和面向路网约束的方法。
3、面向自由空间的方法(如douglas-peucker算法、td-tr 算法)直接在原始gps点上进行压缩,通过设定距离或角度阈值删除冗余点。这类方法计算简单、效率高,但忽略了轨迹所在的道路网络约束,压缩后的轨迹点可能偏离实际道路,难以直接用于路网相关的后续分析。
4、面向路网约束的方法先将gps轨迹匹配至道路网络,得到道路段标识序列,再对序列进行压缩。代表性方法包括基于方向编码的dor(direction-oriented representation)算法和基于时钟方向的clockwise算法。dor算法通过编码轨迹在道路段间的转向方向来实现压缩,在路网轨迹压缩中取得了较好的效果。然而,现有路网约束压缩方法存在以下不足:
5、(1)时间戳压缩采用有损插值预处理,破坏数据原始性。现有方法先通过插值将不规则采样轨迹转换为固定采样间隔,再仅保存起始时间和采样间隔。这种方法虽然能压缩规则时间序列,但只能恢复插值后的时间戳,无法恢复原始不规则时间戳,本质上是一种有损处理,破坏了轨迹数据的原始性。实际gps轨迹(如t-drive数据集)的采样间隔往往存在较大变化范围,固定间隔假设不成立,导致压缩质量不稳定。
6、(2)道路段编码未充分利用拓扑上下文和历史转移规律。dor方法主要利用当前道路段与前一个或前两个道路段的方向关系进行编码,本质上仍以局部方向编码为主,存在以下不足:1.未考虑道路段连续重复的游程压缩机会;2.未充分利用路网拓扑邻接关系来缩小候选集;3.未利用历史轨迹的转移统计规律来提高预测准确率。
7、(3)距离压缩未结合运动物理规律。将沿路距离序列作为普通浮点数直接交给elf压缩。elf是一种通用浮点无损压缩算法,主要利用浮点数二进制表示的尾数冗余,完全不知道车辆位于哪条道路、道路有多长、前后时间间隔是多少、车辆当前运动速度如何。因此elf没有利用轨迹数据的物理运动规律,压缩效率存在进一步提升空间。
技术实现思路
1、本发明的目的在于克服现有技术的不足,提供一种面向路网轨迹的多维度自适应无损压缩方法,旨在解决现有技术中时间戳压缩采用插值预处理导致无法恢复原始时间戳、道路段编码仅基于局部方向关系而未利用路网拓扑邻接与历史转移规律、以及距离压缩将沿路距离视为普通浮点数而未结合运动物理信息的问题,通过对时间、路段、距离三个维度的协同自适应压缩,实现高压缩率与高保真度的平衡。
2、为了实现上述目的,本发明采用的技术方案为:
3、一种面向路网的多维度自适应轨迹压缩方法,其特征在于,所述方法具体包括如下步骤:
4、s1、对原始轨迹数据进行预处理,包括数据读取与解析、空间范围过滤、轨迹完整性检查 、路网数据加载,完成路网匹配、输出轨迹数据,将其分解为道路段标识序列、沿路距离序列和时间戳序列;
5、s2、对时间戳序列进行多模式自适应时间压缩:计算相邻时间戳的差值,针对于不通过种类的时间间隔,使用游程编码、二阶delta-of-delta编码和差分原始增量rice编码,在轨迹数据块中自适应选择压缩代价最小的模式进行编码;
6、s3、对道路段标识序列进行基于路网拓扑预测的自适应空间压缩:首先基于路网邻接关系获取候选道路段集合,结合历史转移概率和方向连续性对候选道路段进行优先级排序,对实际下一道路段在候选集中的排名进行编码,对连续重复道路段进行游程编码;同时将基于方向的方向编码dor和原始路段id 存储作为备选策略,在轨迹数据快中选择压缩代价最小的策略进行编码;
7、s4、对沿路距离字段进行基于速度预测的自适应距离压缩:计算相邻轨迹点之间的沿路位移量,利用前两个轨迹点的位移和时间间隔预测当前位移并计算预测残差,对预测残差进行自适应量化,并对量化后的残差序列进行零残差游程编码;对比基于量化的elf压缩,选择压缩代价最小的方案进行编码;
8、s5、将步骤s2、s3、s4的压缩结果合并,输出压缩后的轨迹数据; 在步骤s1提取过程中:道路段标识字段由hmm和维比特算法完成地图匹配,将gps轨迹点映射至道路网络,沿路距离字段为每个轨迹点在其所在道路段上的投影距离,时间戳字段为每个轨迹点的采集时间,道路段标识序列为对应轨迹点匹配路段id。
9、在使用游程编码的基础上叠加多种差分编码自适应选择:步骤s2中所述固定间隔游程编码包括:检测相邻时间差是否恒定,若恒定则仅存储初始时间差值和轨迹点数量;delta-of-delta编码包括:对相邻时间差再次求差,对二阶差值进行zigzag编码后rice编码;原始增量rice编码包括:直接对相邻时间差值进行rice编码。
10、基于路网拓扑预测的自适应空间压缩如下:步骤s3中候选道路段集合的获取方法为:获取当前道路段的末端节点,从路网中获取该末端节点的所有邻接道路段作为候选集合,候选集合大小不超过预设上限值。历史转移概率的计算方法为:统计历史轨迹数据中从当前道路段转移到各候选道路段的频次,将频次除以当前道路段的总转移次数得到转移概率;方向连续性为当前道路段方向与候选道路段方向的夹角余弦值;将所述转移概率和方向连续性进行加权融合,得到候选道路段的优先级分数。
11、基于路网拓扑预测的自适应空间压缩如下:步骤s3中所述对实际下一道路段在候选集中的排名进行编码包括:若排名为第0位,则用1比特编码;若排名为第1位,则用2比特编码;若排名为第2位,则用3比特编码;若排名大于2,则用4比特标记后接rice编码的排名值;若实际下一道路段不在候选集中,则直接存储该道路段的原始id。基于方向连续性的方向编码为:计算轨迹在连续三个节点处的转向方向,将转向方向编码为q进制比特串,压缩代价为编码后的总比特数。
12、基于速度预测的自适应距离压缩的具体计算过程如下:步骤s4中所述沿路位移量的计算方法为:若相邻两个轨迹点在同一道路段上,则位移量等于两点沿路距离之差;若相邻两个轨迹点在不同道路段上,则位移量等于前一道路段剩余长度与当前道路段沿路距离之和。速度预测的具体方法为:根据前两个轨迹点的位移量和时间间隔计算前一时刻速度,将前一时刻速度乘以当前时间间隔与前一时刻时间间隔的比值,得到当前位移的预测值;预测残差为实际位移量减去预测位移量。零残差游程编码包括:遍历量化后的残差序列,统计连续零值的个数,用1比特标记零值游程,当游程长度大于1时用rice编码记录游程长度;对非零残差值用1比特标记后,进行zigzag编码再rice编码。elf压缩为:对沿路距离序列进行全局归一化量化,对量化后的序列计算差分值,对差分值进行基于ieee 754浮点数标准的无损压缩。
13、融合以上三大部分完成综合压缩:s5中所述合并输出包括:将步骤s2的压缩结果及所选模式标记、步骤s3的压缩结果及所选策略标记、步骤s4的压缩结果及所选方案标记,按轨迹顺序拼接形成完整的压缩数据流。
14、本发明的优点在于:本发明通过对时间戳序列设计三种编码模式自适应选择,解决了现有方法依赖插值预处理导致无法恢复原始不规则时间戳的问题,实现了时间戳的严格无损压缩,时间压缩率达到99.52%。
15、本发明通过对道路段序列设计游程分解与拓扑上下文预测编码,充分利用路网邻接关系和历史转移规律,在runtopology、dor和rawid三种策略中自适应选择最优,路段压缩率达到96.21%。
16、本发明通过对沿路距离序列设计速度预测残差编码,利用道路长度、时间间隔和运动速度物理信息,结合零残差游程编码和elf混合择优,距离压缩率达到95.98%,在86.3%的轨迹上优于elf方案。
17、本发明三个维度的压缩模块协同工作,在geolife真实轨迹数据集上达到97.13%的平均压缩率,显著优于dor算法(92.89%)、clockwise算法(91.94%)和zstd通用压缩算法(68.96%)。
18、本发明不采用任何有损预处理,所有编码均为严格无损,解码后可完全恢复原始轨迹数据,保证了数据的完整性和可追溯性。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com