第一章 绪论
1.1 轨迹压缩的背景及意义
随着技术进步和社会经济的飞速发展，近年来定位技术如全球卫星定位系统(Global Positioning System, GPS)在生活中的应用已经非常普遍。由于 GPS 等定位技术的普及，移动互联网可以通过获得定位设备位置去提供服务和信息，因此基于位置的服务(Location Based Service, LBS)[1]得到了广泛应用。LBS 指的是通过定位技术得到节点的位置信息，再通过网络和服务器为用户节点提供和位置相关的增值服务，包括导航[2]、运动记录、热点查询及推荐[3],[4]等。例如，腾讯地图在提供导航路径规划时，会持续不断地跟踪并确定用户的位置；网约车软件为用户提供叫车服务时，会通过定位用户和司机智能手机的位置来促成他们之间的交易。目前，多个领域已经应用了 LBS 技术，包括交通物流、灾害救援、军事行动、信息搜索服务等。
通过 GPS 等定位技术可以轻易获得大量人类出行、车辆运动、动物迁徙、气象运动等轨迹数据[5]。通过数据挖掘的方式分析这些轨迹，进一步得到轨迹背后的隐藏信息，对于研究道路地形，以及利用节点移动特性进行服务推荐具有重要意义。在城市环境中，人或者车辆（节点）的位置变化代表节点在城市环境下的人与社会、人与地域和人与人之间的交互，通过对轨迹数据的研究和分析可以挖掘节点背后的行为特征。另外，车载 GPS 设备可以实时记载车辆轨迹和行驶状态信息，这些信息反映了城市中车辆移动和路况条件，分析和挖掘这些车辆轨迹信息，可以应用于车辆轨迹预测[6]、交通异常事件预测[7]、交通规律挖掘[8]、路线规划[9]及电动车充电桩推荐[10],[11],[12]等。特别地，交通规律的挖掘对于城市的交通规划有着很大的作用，比如文献[10]，利用电动出租车的历史轨迹数据挖掘出电动出租车的潜意识移动倾向以及电动出租车司机的驾驶习惯，来为空载状态的电动出租车推荐合适的充电桩，以此得到最经济的充电行驶路线规划。此外，携带有定位模块的便携智能手机目前已经广泛普及，人们在使用 APP 比如打车[13]、聊天、网上购物、订外卖的同时，用户记录往往伴随着定位信息同步上传至服务器。
......................
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 等人提出，这些算法保持一定大小的窗口，按照时间顺序依次向窗口添加轨迹点，从第三个进入窗口的轨迹点开始，每新添加轨迹时都计算窗口内部的轨迹误差，若小于阈值则继续移动窗口或者扩大窗口，并添加下一个轨迹点。如果大于阈值，则根据误差度量删除窗口内的轨迹点，这种实时传输和处理轨迹的压缩算法被称为在线压缩。相比而言，离线压缩算法虽然时间复杂度较高，但能够获取全局较优的压缩轨迹，而着重处理局部轨迹的在线压缩则误差更大。
..........................
第二章 轨迹压缩技术概述及算法介绍
2.1 轨迹数据的起源
轨迹数据通常情况下来自于人类活动（主动记录和被动记录）、动物运动、交通工具移动和自然现象流动四种方式。
（1）人类活动：人们的行动轨迹可以被主动或者被动设备所记录下来。在智能手机等携带定位设备的移动设备流行和推广的基础上，人类的活动轨迹被广泛而且高密度地采集起来，这些轨迹数据对于居民出行模式、社会活动分析等具有重要意义。
(a)主动记录：比如游客主动记录他们的旅游路线，在 Flickr 上发布一系列带有地理位置的照片构成时空轨迹，每张照片都有一个地点和时间戳一一对应。同样的，在基于地理位置的社交软件上签到后，这些签到信息也会被视作一串轨迹。
(b)被动记录：用户的智能手机会时时刻刻产生包含时间信息和手机蜂窝 ID 的轨迹点。此外，信用卡的交易信息不仅代表了持卡者的活动堆积，由于每条交易记录都包括了时间戳和付款商店，所以这些记录反映了在何时何地发生了交易行为。
（2）动物运动：生物学家收集野生动物如老虎和候鸟的轨迹信息，通过分析动物的活动轨迹，用来研究动物的迁徙行为或者生存状况。
（3）交通工具移动：日常生活中，出租车、公交车、飞机、火车、轮船等交通工具都配置了 GPS 定位设备。比如，出租车上装有 GPS 模块，可以按照一定的时间间隔发布车辆的位置信息，这些记录形成了大量轨迹数据，可以用来分析交通流量、交通异常以及未来交通轨迹。
（4）自然现象流动：飓风、龙卷风和洋流等自然现象的轨迹运动反映了环境与气候的变化，气象和海洋科学家采集这些轨迹，并通过研究分析来帮助人类预测并保护所处的生态环境。
.................................
2.2 轨迹的相关定义
轨迹表示运动对象随着时间变化，在空间中产生的运动路径。空间轨迹可以通过路径几何描述，也可以通过对象的位置顺序来进行描述。移动对象由携带的定位设备连续不断地生成位置信息，将这些位置信息按照时间顺序排列就得到了移动对象的运动轨迹。运动对象的轨迹应该是连续的，因为运动对象在欧式空间的运动是连续的。但是，在很多实际应用中，由于节点存储空间、通信能力和设备鲁棒性等限制，往往采用周期采样轨迹点的方式。另外，由于信号缺失或者传感器噪声，不能保证每个采集时间点都能收到 GPS 信号，采集到的轨迹点还存在轨迹点错误和轨迹点缺失的情况。所以，在处理轨迹数据前需要先进行预处理，对原始轨迹数据进行噪声过滤，即去除噪声和离群点。下面给出本文需要用到的相关定义：
定义 2.1 GPS 轨迹点：通常来说，GPS 轨迹 T 包含空间数据（如经度和纬度）和时间戳。这些带有时间戳的位置点构成一个有序的序列，每个位置点用一个三元组????????= (????????, ????????, ????????)表示，其中????????和????????分别表示在时间戳????????的经度和纬度。
定义 2.2 轨迹段：从原始轨迹中提取的若干 GPS 点的序列，记为????????[1, ????] = {????1, . . . , ????????}。
定义 2.3 压缩轨迹段：作为原始轨迹????????[1, ????] = {????1, . . . , ????????}压缩后的轨迹点，记为????????′[1, ????]={????????1,…,????????????}。压缩轨迹段属于原始轨迹 T 的一部分，并且所有轨迹点都是按照时间戳顺序排列的。
计算机论文怎么写
第三章 基于折返点的在线轨迹压缩算法 .................................16
3.1 误差定义 ...............................................16
3.1.1 速率误差 ................................16
3.1.2 基于方向保持的速度误差 ......................................17
第四章 轨迹压缩原型系统的设计与实现 ............................30
4.1 系统需求分析 ..........................................30
4.1.1 系统功能性需求 ..........................................30
4.1.2 系统非功能性需求 .......................32
第五章 总结与展望 .......................................45
5.1 全文总结 ........................................45
5.2 未来工作展望 ........................................45
第四章 轨迹压缩原型系统的设计与实现
4.1 系统需求分析
本节分别从系统的功能性需求和非功能性需求两个方面对行人轨迹压缩原型系统进行需求分析。原型系统的功能性需求是指各个用户对于行人轨迹压缩的业务需求以及系统使用的相关功能，非功能性需求包括在系统中安全性、可靠性和可扩展等相关需求。对于功能性需求，本节首先通过用例建模来描述原型系统需求，其次依照原型系统建模中所涉及对象映射为相应的业务和功能，通过类图的形式来表示原型系统的相关对象类的属性以及操作。
4.1.1 系统功能性需求
（1）需求描述
行人轨迹压缩系统是一个对行人轨迹进行压缩的工具，主要需要提供轨迹数据管理、轨迹压缩和地图显示服务。其中，数据管理负责将离线的原始数据进行格式转换，最后经过噪声处理并存入数据库；轨迹压缩需要将存入数据库的轨迹数据经过 VPTR 算法进行压缩处理，能够检测出轨迹中的折返点；地图显示是把压缩后的轨迹数据在地图中显示出来，方便进行前后效果的对比。还需要提供地图操作，包括对压缩结果显示的各种操作，如地图放大、缩小等。此外，对于压缩处理过后的数据，需要能够进行一些简单的数据分析以及本地化存储。 （2）用例建模
首先对行人轨迹压缩原型系统用例建模，经需求描述可以确定原型系统管理员和用户是行人轨迹压缩原型系统的两种参与者。原型系统管理员的任务是负责轨迹数据格式转换、轨迹数据预处理和轨迹数据存储等操作；用户执行用户界面的数据集导入、算法选择、算法阈值设置。系统的具体用例模型如图 4.1 所示。
计算机论文参考
第五章 总结与展望
5.1 全文总结
随着定位技术和配备定位设备的移动节点的发展与普及，面对海量增长的移动节点轨迹数据，亟需快速、高效的轨迹压缩技术。轨迹压缩技术可以在控制误差度量的前提下，有效删除原始轨迹数据中的冗余轨迹点，这样不仅可以缓解海量轨迹数据的存储压力，还能减少轨迹数据在传输过程的开销。轨迹压缩技术的两个主要设计目标包括：减少轨迹点数量和降低压缩前后的误差度量。然而这两个目标往往是互相矛盾的，一般轨迹点压缩越多则压缩后的误差越大，所以在轨迹压缩算法设计时需要对这两方面进行权衡，即在保证压缩率的前提下，尽可能降低压缩前后轨迹的误差度量。
本文提出了一种基于折返点检测的轨迹压缩算法，从轨迹语义和轨迹速度信息两个角度对轨迹进行压缩。本文通过对轨迹特征的分析，提出了折返点和基于折返点检测的轨迹压缩算法。折返点表示行人围绕兴趣点所形成的一系列徘徊折返的轨迹点，这部分轨迹点权重较低，可以被删除。此外，该算法还利用一种结合速率和方向信息的误差度量对折返点检测算法处理后的轨迹进行压缩。
本文最后实现了一个行人轨迹压缩原型系统。该原型系统可以实现行人轨迹的输入、压缩和输出，并在地图上进行直观地展示和操作。通过该原型系统，可以实现便捷、快速的轨迹压缩。
参考文献（略）