基于路网的GPS轨迹在线压缩方法

在传统的GPS轨迹压缩中,其压缩的结果与原始轨迹差别较大,在压缩过程中不同程度的忽略了轨迹点的速度信息、方向信息以及轨迹的形状,在本文中,在保证压缩率的前提下将保存速度、方向、轨迹形状等GPS轨迹特征信息,作为重点研究的问题.本文算法基于路网信息、OW(Opening Window,开放窗口)算法、关键点法以及停留点法之上提出了一种能够保存GPS轨迹时空特性的在线压缩算法.实验结果表明,该压缩算法较现有的压缩算法在保证压缩率的前提下,在保留轨迹时空特性的基础上有所改进.     

基于相对同步欧氏距离筛选的在线GPS轨迹数据压缩算法

为了减小给定压缩率下,压缩轨迹与原始轨迹之间的差异,提出一种基于相对同步欧氏距离筛选的在线GPS轨迹数据压缩算法。所提算法可以根据用户的压缩率要求设定轨迹压缩过程,将新到来的轨迹点保存到一个存储队列中,每次从队列中选择引起同步欧氏距离误差最小的轨迹点移除,以达到在给定压缩率下减小压缩前后轨迹间差异的目的。理论分析和实验结果表明,较现有以压缩率为压缩依据的主流在线GPS轨迹数据压缩算法而言,压缩率相同时,所提算法对应的平均同步欧氏距离误差明显减小,所需的压缩时间略有增加。     

路网感知的在线轨迹压缩方法

随着定位技术的高速发展,定位传感器被广泛地应用于智能手机、车载导航等各种移动设备中,用于采集移动对象位置数据并将数据上传至服务器.该技术的应用方便了位置跟踪、预测和分析,同时也带来了轨迹数据量大、数据冗余、传输和存储代价高等问题.轨迹压缩技术即是针对该问题而提出的,它通过保留关键轨迹点和去除冗余轨迹点信息,降低了轨迹数据的传输和存储开销.本文分析了近年来轨迹压缩领域的国内外研究进展,针对现有研究工作的不足,提出了一种路网感知的在线轨迹压缩方法,包括针对轨迹压缩的距离有界的隐马尔科夫地图匹配算法和误差有界的高效轨迹压缩算法等,并实现了该方法的原型系统（ROADER）.基于真实数据集的实验证明,该系统在压缩率、误差和执行时间等方面均显著优于同类算法.     

一种距离误差可控的DPTS-SP-Prac改进算法

移动对象的GPS轨迹常被应用于各种基于位置服务的应用当中,由于原始的轨迹包含的数据量较大,在使用这些数据前通常要进行轨迹压缩操作。相比于传统的基于位置保持的轨迹压缩算法,基于方向保持的DPTS-SP-Prac算法由于考虑到了轨迹的方向信息,因此该算法有着更广泛的应用范围。为了进一步提高DPTSSP-Prac算法的可用性,提出一种距离误差可控的DPTS-SP-Prac改进算法。该算法不仅能够捕捉轨迹的方向信息,还具有距离误差可控的优势,能够实现更加精确的轨迹压缩。真实轨迹数据集下的实验结果表明,改进的算法有效地降低了轨迹压缩的距离误差,提高了算法的可用性。     

基于运动状态改变的在线全球定位系统轨迹数据压缩

针对基于偏移量计算的轨迹数据压缩算法中对于关键点的评估不足以及基于在线轨迹数据压缩算法中累积误差和对偏移量考虑不足的问题,提出一种基于运动状态改变的在线全球定位系统(GPS)轨迹数据压缩算法——限定同步欧氏距离(SED)的阈值结合算法(SLTA)。该算法通过轨迹点的转向角度大小和速度变化大小来评估轨迹点信息量的大小;同时用SED限制点的偏移量,以达到较好的信息保留度。实验结果表明,SLTA的轨迹压缩率能够达到50%左右,与阈值结合算法(TA)相比,SLTA的平均SED误差(5 m以内)可以忽略不计;相对于基于偏移量计算的轨迹数据压缩算法,SLTA的平均角度误差最小(1.5°~2.3°),运行时间最稳定。SLTA能够稳定有效地进行在线GPS轨迹数据压缩。     

一种改进的邻接关系可查询压缩算法

目前多数数据压缩算法不能直接在压缩结果上进行数据查询,大数据的线性化压缩算法虽然可直接在压缩后的数据上进行邻接关系查询,但压缩率较低.针对该问题,对线性化压缩的实现原理进行研究,分析MPk线性化算法在不同社会网络样本下的压缩效率,发现线性化压缩结果中存在冗余信息,并针对该情况设计改进算法,删去原有数据结构中的冗余部分,进一步提高压缩率.实验结果证明,改进算法的时间复杂度与原算法相同,压缩率平均提升23％.     

基于偏移量计算的在线GPS轨迹数据压缩

针对现有基于偏移量计算的在线GPS轨迹数据压缩算法不能有效评估关键点的问题,提出基于偏移量计算的在线GPS轨迹数据压缩算法--关键点前继修正算法（KPFA）。该算法通过计算同步欧式距离（SED）累积偏移量来发现轨迹点中信息量较大的关键点,同时设置阈值对关键点之前和上一个关键点之后的轨迹点进行修正,更好地保留轨迹信息。实验结果表明,和按时间比例的开窗算法（OPW-TR）及启发式空间质量简化算法的改进算法（SQUISH-E）相比,压缩率相同时KPFA的平均SED误差最小,并且运行时间最快且维持在100 000 ms。KPFA算法对轨迹点的信息量评估准确度更高,运行时间更稳定。     

基于查找表的误差分散半调图像的混合压缩算法

结合现有逆半调技术,针对无损压缩所得压缩率较低,而现有二值图像有损压缩算法对误差分散图像的压缩效果并不理想等缺陷,设计了一种针对误差分散半调图像的混合压缩算法。该算法采用LUT逆半调对误差分散半调图像进行灰度化重建,再通过改进离散余弦变换(DCT)系数量化法,以提高压缩率。实验证明该算法能获得较好的压缩效果和较高的压缩率。     

基于划分的自适应轨迹拐点提取压缩算法

海量的轨迹数据为管理分析和数据挖掘工作带来了巨大的挑战, 轨迹压缩技术成为解决这一问题的一种有效方案. 针对目前多数轨迹压缩算法需要人为干预设定阈值的问题, 融合特征聚类与轨迹划分的思想提出了一种自适应的轨迹拐点提取压缩算法. 算法从轨迹的全局方向特征与局部方向特征出发考虑, 依次进行了轨迹粗划分、子轨迹合并以及轨迹细划分的工作. 实验结果显示, 随着轨迹规模的增大, 与其他算法相比, 该算法基本能够在保持更高压缩率的同时产生更低的方向误差. 提出的算法具有自适应和高精度拐点识别的优势, 在其他轨迹压缩场景之下仍有着较高的参考价值.     

一种加入时间维的船舶轨迹高效离线压缩算法研究

全球船舶轨迹大数据加工的一个重要步骤是对船舶轨迹进行压缩。以经典船舶轨迹离线压缩算法思路为基础,探讨了传统算法在压缩效果和压缩效率方面存在的问题。例如,经典Douglas-Peucker压缩算法没有考虑时间维,导致压缩后的数据对船舶的速度与航行状态信息的保留效果不佳。但是,动态Douglas-Peucker算法虽然考虑了时间维,却因此增加了计算量,导致压缩效率不高。在上述算法的基础上,将考虑时间维的轨迹压缩算法对应到向量空间中,利用向量的内积、外积的几何性质,对算法压缩效率和效果进行了改善,并提出了快速Douglas-Peucker算法。经过实验验证,该算法较经典算法效率提高了约30%以上,压缩效果比已有算法更优。     

基于分段的移动对象轨迹简化算法

GPS的高采样率使轨迹的数据规模巨大，在实际应用中难以处理，需要依赖轨迹简化算法对原始数据进行压缩。针对此问题，提出了一种新的基于速度分段的轨迹简化算法，即STS算法，在保留速度特征的同时保留了给定轨迹的时空特征。STS算法将速度值分组成若干间隔，将轨迹分割成速度保留段，计算各轨迹段的SED阈值，通过在每个子轨迹段上应用TD-TR算法导出简化的轨迹。通过真实的数据集进行广泛实验，验证所提出的算法比ATS算法具有更好的性能。     

基于最小边界扇形的移动对象轨迹实时化简算法

为了对全球定位系统(GPS)设备采集到的移动对象原始轨迹数据进行简化,提高轨迹数据的使用效率,降低移动终端的通信代价和计算开销,提出了一种基于最小边界扇形(MBS)的移动对象轨迹实时化简算法。该算法不同于用一条折线来近似原始轨迹的方法,它利用扇形预测范围来估计、简化原始轨迹,在角度和距离两个层面上对简化误差进行控制。提出了新的误差度量方法--基于等极径的误差度量方法,并讨论了GPS定位误差对简化算法的影响。实验结果表明,所提算法的简化轨迹高效、稳定,所得到的简化轨迹与原始轨迹之间误差较小(不超过误差阈值的20%),对GPS定位误差有较好的容错能力。     

轮式机器人轨迹跟踪控制系统的设计

针对轮式机器人轨迹跟踪控制系统误差收敛速率低、精度和实时性差的问题,采用反演控制算法并结合李雅普诺夫稳定性分析方法对轮式机器人的轨迹跟踪系统进行了优化设计;建立了轮式机器人轨迹跟踪控制系统的运动学模型,并对该模型进行位置偏差分析;在反演控制算法中引入了分部虚拟控制量,并分析和设计了其他间接受控量,提高了算法运行的效率;采用李雅普诺夫收敛定理对系统的收敛性进行分析,根据分析的结果提出了算法更加简单的控制律;利用Matlab软件的Simulink库对设计的轨迹跟踪控制系统试验研究;结果表明,与基于李雅普诺夫直接法或者迭代学习算法设计的轮式机器人轨迹跟踪控制系统相比较,设计的控制系统具有跟踪精度高、收敛速度快、实时性好的优点。     

基于MapReduce的轨迹压缩并行化方法

带有全球定位系统（GPS）功能设备的增多,产生大量的时空轨迹数据,给数据的存储、传输和处理带来了沉重的负担。为了减轻这种负担,各种轨迹压缩方法也随之产生。提出了一种基于MapReduce的并行化轨迹压缩方法,针对并行化导致的分段点前后轨迹的相关性被破坏的问题,首先,采用两种分段点相互交错的划分方法划分轨迹;然后,将分段轨迹分配到多个节点上进行并行化压缩;最后,对压缩结果进行匹配合并。性能测试分析结果表明,所提出的并行化轨迹压缩方法能够大幅提高压缩效率,而且能完全消除因分段导致分段点前后相关性被破坏带来的误差。     

基于预测模型的轨迹数据压缩方法

针对目前路网环境下海量轨迹数据压缩效率低下的问题,提出了一种基于预测模型的轨迹数据压缩方法（CTPM）。通过将轨迹数据的时间信息和空间信息分别进行压缩,使得压缩后的轨迹数据在空间维度上无损,并且在时间维度上误差有界,以此提高压缩效率。在空间方面,首先利用部分匹配预测（PPM）算法通过轨迹已经行驶的部分路段对其下一时刻可能的位置进行预测;然后通过删除预测成功的路段来减少轨迹数据的存储代价。在时间方面,首先利用轨迹通行状况具有周期性的特点,构建了不同时间区间的通行速度统计模型,来预测移动对象进入下一路段所需要的时间;然后删除预测时间误差小于给定阈值的路段数据来进行压缩处理。实验结果显示,与已有的基于路网的并行轨迹压缩（PRESS）算法相比,CTPM的空间压缩比和时间压缩比平均分别提高了43%和1.5%,同时时间压缩误差减小了9.5%。实验结果表明所提算法在提高压缩比的同时有效地降低了压缩时间和压缩误差。