计算机论文哪里有？本文提出了一种基于折返点检测的轨迹压缩算法，从轨迹语义和轨迹速度信息两个角度对轨迹进行压缩。本文通过对轨迹特征的分析，提出了折返点和基于折返点检测的轨迹压缩算法。折返点表示行人围绕兴趣点所形成的一系列徘徊折返的轨迹点，这部分轨迹点权重较低，可以被删除。此外，该算法还利用一种结合速率和方向信息的误差度量对折返点检测算法处理后的轨迹进行压缩。
第一章 绪论
1.2 国内外研究现状
轨迹压缩技术最初来源于地图制图学中的地图概括问题和计算机图形学中的多线段简化问题。地图概括问题是利用较少的信息来表示复杂地图，多线段简化问题是把一整条的线段划分为成多条子线段，并按照一定的规则选取一部分子线段连线，从而代表原始完整线段[16]。
移动节点产生的轨迹数据量越来越大，受到移动节点的存储空间和能耗限制，使得它们没有足够的空间和能量来存储和传输这些轨迹数据。海量轨迹数据生成，也会对服务器带来很大的存储压力，轨迹压缩技术可以有效解决这些问题。轨迹压缩技术被定义为按照一定的规则减少原始轨迹数据的方法，它可以有效地降低了存储空间，提高了传输、存储和处理效率，而不丢失重要轨迹特征信息。
最常见的轨迹压缩算法是基于特征点的提取方法，这些算法采用多线段化简的方式抽取出具有关键特征的轨迹点，从而达到压缩轨迹的目的。最早的轨迹压缩方法是 Douglas Peucker(DP)算法[17]，DP 算法将最大的垂直欧氏距离误差距离限制在一个阈值内，利用递归方法保留大于阈值的特征点，将原轨迹划分成若干个近似轨迹段，但是 DP 算法仅仅考虑了轨迹的空间位置，而忽视了轨迹附带的时间属性。Meratina 等人在文献[18]中利用时间同步的空间距离(Time-Distance Ratio Metric)对轨迹进行压缩，这种度量方法同时考虑了空间属性和时间属性，比垂直欧氏距离考虑地更加全面，并由此提出了自顶向下的基于速度和时间比例的(Top-Down Time-Ratio, TD-TR)轨迹压缩算法。
上述算法属于离线压缩算法，离线压缩算法只能对完整收集的轨迹进行压缩，不仅耗存储内存而且需要大量处理时间。为了适应内存小或者实时性高的使用场景，滑动窗口(Sliding Window)和开放窗口(Open Window, OPW)算法在文献[19]中由 Keogh 等人提出，这些算法保持一定大小的窗口，按照时间顺序依次向窗口添加轨迹点，从第三个进入窗口的轨迹点开始，每新添加轨迹时都计算窗口内部的轨迹误差，若小于阈值则继续移动窗口或者扩大窗口，并添加下一个轨迹点。如果大于阈值，则根据误差度量删除窗口内的轨迹点，这种实时传输和处理轨迹的压缩算法被称为在线压缩。相比而言，离线压缩算法虽然时间复杂度较高，但能够获取全局较优的压缩轨迹，而着重处理局部轨迹的在线压缩则误差更大。
第三章 基于折返点的在线轨迹压缩算法
3.1 误差定义
随着携带 GPS 传感器的智能手机的广泛应用，在线轨迹压缩技术及相关应用也开始普及。现有的在线轨迹压缩算法往往主要关注位置误差，而忽略了速度误差。此外，传统的基于速度保持的轨迹压缩算法，仅仅考虑了速度信息中的速率，但忽视了速度向量中的方向信息，这些都影响了轨迹压缩结果。
在移动社会网络中，行人的轨迹还包含着丰富语义信息，通过挖掘轨迹数据背后的语义，可以对一些冗余的轨迹点进行有效删除。特别地，通过分析行人轨迹数据，我们注意到行人（节点）在移动过程中会出现节点移动方向变化剧烈或变化频繁的轨迹点，这些节点轨迹往往会存在折返行为，这些行为反映到现实生活中，可以是节点在购物区徘徊，或节点访问景区时的逗留。
本章提出一种可以实时处理轨迹数据的在线轨迹压缩算法 VPTR，该算法能同时保持速度向量的方向和速率信息。另外，VPTR 算法还考虑了节点运动存在随机性和不可控性的语义，通过分析节点产生折返行为的轨迹点（称为折返点），发现这些轨迹点中的冗余。在速度保持的基础上，VPTR 算法通过检测折返点并删除它们来提高压缩率。
第四章 轨迹压缩原型系统的设计与实现
4.1 系统需求分析
本节分别从系统的功能性需求和非功能性需求两个方面对行人轨迹压缩原型系统进行需求分析。原型系统的功能性需求是指各个用户对于行人轨迹压缩的业务需求以及系统使用的相关功能，非功能性需求包括在系统中安全性、可靠性和可扩展等相关需求。对于功能性需求，本节首先通过用例建模来描述原型系统需求，其次依照原型系统建模中所涉及对象映射为相应的业务和功能，通过类图的形式来表示原型系统的相关对象类的属性以及操作。
4.1.1 系统功能性需求
（1）需求描述
行人轨迹压缩系统是一个对行人轨迹进行压缩的工具，主要需要提供轨迹数据管理、轨迹压缩和地图显示服务。其中，数据管理负责将离线的原始数据进行格式转换，最后经过噪声处理并存入数据库；轨迹压缩需要将存入数据库的轨迹数据经过 VPTR 算法进行压缩处理，能够检测出轨迹中的折返点；地图显示是把压缩后的轨迹数据在地图中显示出来，方便进行前后效果的对比。还需要提供地图操作，包括对压缩结果显示的各种操作，如地图放大、缩小等。此外，对于压缩处理过后的数据，需要能够进行一些简单的数据分析以及本地化存储。
（2）用例建模
首先对行人轨迹压缩原型系统用例建模，经需求描述可以确定原型系统管理员和用户是行人轨迹压缩原型系统的两种参与者。原型系统管理员的任务是负责轨迹数据格式转换、轨迹数据预处理和轨迹数据存储等操作；用户执行用户界面的数据集导入、算法选择、算法阈值设置。系统的具体用例模型如图 4.1 所示。
4.2 系统总体设计
4.2.1 逻辑体系架构设计
根据章节 4.1 的系统需求分析，并且结合原型系统开发的层次结构，本文中行人轨迹压缩原型系统逻辑体系架构包括存储层、中间层、算法层和应用层四部分。存储层将是行人 GPS轨迹数据储存到数据库中；中间层包括算法层和业务逻辑层两个层次，其中算法层包含轨迹数据预处理、压缩算法选择，业务逻辑层主要实现系统中轨迹数据处理模块、轨迹压缩处理模块和地图显示模块的业务逻辑功能；应用层是客户端的操作界面。详细的原型系统逻辑体系架构如图 4.3 所示。
第五章 总结与展望
5.2 未来工作展望
本文在基于折返点的轨迹压缩方法方面取得了一定进展，根据本文的研究成果，未来可以从以下几个方面继续开展研究：
（1）在未来的实际生活应用场景中，轨迹数据量会迎来爆炸式的增长。从压缩算法的性能优化考虑，可以将现有的轨迹压缩系统数据库替换为 MongoDB 来进行高性能数据存储，并结合基于 Spark 的分布式技术，使系统升级为分布式在线轨迹压缩系统，从而大大提高压缩和存储的性能。
（2）从提高轨迹压缩准确度的角度来说，一是考虑更为复杂的轨迹特征，比如构造将角度特征、方向特征、速度特征、加速度特征等多种特征结合起来的复合指标，用来对轨迹数据压缩，使得压缩后的轨迹保留更多种类的特征信息；二是在轨迹折返点的检测中结合真实的路网信息，从而使更多的时空语义信息能够保留在压缩后的轨迹中；三是基于更多的不同类型节点所产生的数据集上验证并改进该轨迹压缩算法，以使得该算法能够适应不同的真实应用场景。
（3）结合神经网络与数据挖掘对轨迹数据进行研究。轨迹数据也是一种时序序列，可以利用轨迹数据进行概率模型学习。因此，将大量的历史轨迹数据集放入基于神经网络的训练模型内进行学习，最后可以得到对轨迹点预测的预测模型。模型预测得出每一轨迹点紧跟的下一位置，并将这一预测位置和原始的轨迹数据进行对比，若预测错误则将正确的轨迹位置进行保留，从而进行轨迹压缩。
参考文献（略）
