摘 要

由于Internet和移动设备的急速普及，通过GPS系统收集到的轨迹数据越来越多。而大量数据的产生和其可用性导致了新的问题：轨迹数据如何存储，查询延时增长，数据冗余，如何高效的进行对比和分析。因此，我们就必须用到轨迹数据压缩技术来解决这些问题。

对于规模庞大的轨迹数据，轨迹数据压缩可以减小轨迹数据存储规模和方便轨迹数据分析，难点在于如何既提供较好的轨迹数据压缩率，又尽可能地减少压缩误差，提高压缩轨迹的可用性。

本设计在真实船舶AIS轨迹数据的基础上，实现了3种轨迹压缩算法， Douglas-Peucker算法、OpeningWindow算法和Sliding Window算法，并使用这些算法对轨迹数据进行了压缩，对比分析了相应算法的压缩率,平均误差等指标，显示了不同算法间的差别，并进行了可视化，对压缩轨迹数据后不同算法的结果进行了解析，更深入的分析轨迹数据与轨迹压缩算法之间的关系。本文所得结果对于轨迹数据压缩的算法选择和如何优化压缩算法有重要意义。

论文主要研究了不同算法进行轨迹压缩的各项指标对比，并分析对比得出了不同情形下不同算法的适用情况。

关键词： 轨迹压缩；Douglas-Peucker算法；OpeningWindow算法；SlidingWindow算法

Abstract

With the Internet and mobile devices being more and more popular, the trajectory data collected by the GPS system is getting more and more. And having a large amount of data and its availability leads to a new problem: how to storage and query trajectory data , how to compare and analyze. Then, we need to use the technology of trajectory compression to solve these problems.

For the large scale trajectory data, trajectory compression can reduce the data storage space and simplify trajectory data analysis. The difficulty is how to provide great compression rate, reduce compression error as far as possible,and improve the availability of trajectory compression.

This design based on real boat AIS trajectory data, to achieve 3 trajectory compression algorithms such as Douglas-Peucker algorithm and OpenWindow algorithm and SlidingWindow algorithm, and the trajectory data are compressed using these algorithms, it also compare and analysis the corresponding compression rate and average error,which shows the differences between different algorithms, and visualize the result. The results of this thesis have important meaning in how to select and optimize the compression algorithm.

This thesis mainly studies the index comparison of the different trajectory compression algorithms,then analysis and compare the applicability of different algorithms under different circumstances.

KeyWords:trajectory compression;Douglas-Peucker algorithm;OpeningWindow

algorithm;SlidingWindow algorithm

目 录

摘 要 3

目 录 5

第1章 绪论 6

1.1研究背景和目的 6

1.2国内外研究现状 7

1.3本文研究目标和内容组织 8

1.3.1研究目标 8

1.3.2内容组织 9

第2章 轨迹压缩 10

2.1轨迹压缩技术 10

2.2Douglas-Peucker算法 10

2.2OpeningWindow算法 12

2.3SlidingWindow算法 12

2.4算法评估标准 14

第3章 轨迹数据压缩系统的设计 15

3.1开发准备 15

3.1.1基本内容 15

3.1.2设计方案 15

3.2轨迹压缩系统概述 15

3.2.1需求分析 15

3.2.2输入要求 16

3.3系统总体设计 16

3.3.1系统流程图 16

3.4系统详细设计 17

3.4.1运行环境 17

3.4.2界面设计 17

3.4.3轨迹数据压缩系统的设计与实现 19

第4章 系统测试与算法评估 21

4.1实验结果 21

4.2总结 23

第5章 总结与展望 24

5.1总结 24

5.2展望 25

参考文献 26

致 谢 27

第1章 绪论

1.1研究背景和目的

如今，智能移动设备已经实现了全球性的普及，其实用性和便利性已经有了长足的进步，并且能实现的功能也在飞速增加中。其中，智能移动设备普遍携带的GPS全球定位系统因为它的易用性和廉价性，成为其通用的配件。GPS系统具有的特性是快速、省时、高效率；全天24小时；三维高精度；全球覆盖和可移动定位等，这些显而易见的便利使其飞速发展并融入了社会经济发展等各种领域。

同时基于位置服务和移动端的社交软件的大力发展，使得用户迅速方便地得到个人位置信息，而工作人员通过信息传输得到这些轨迹数据，进一步进行分析和反馈。据相关研究报告称，在智能手机等移动设备持有量快速增长的同时，75%的智能手机用户在用手机获取LBS的实时GPS信息，而25%的用户则在使用相关的社交服务应用，如QQ、FACEBOOK等等，调研机构Pyramid Research甚至预估基于位置服务的全球市场会从2010年的150亿元增长到未来的上千亿元[^[1]]。

用户不管是个人，车辆或是船舶飞机等，其位置信息都能通过GPS设备采集到，而这样的数据一般包括用户编号，经纬度和时间信息。通过对这样的用户的连续采样，就能得到根据时间排列的地图上点的序列，进一步形成轨迹。而服务端一般选择获得这样的数据序列再将其以轨迹的方式存储下来。