基于MBR的GPS轨迹数据压缩算法

朱　猛，孙　剑

(信阳农林学院 信息工程学院，河南 信阳 464000)



基于MBR的GPS轨迹数据压缩算法

朱猛，孙剑

(信阳农林学院 信息工程学院，河南 信阳 464000)

摘要：移动对象产生的大量GPS轨迹数据，蕴含了丰富的时间和空间信息。为了减少GPS轨迹数据的存储空间，提高数据分析的效率，针对常用GPS轨迹数据压缩方法不适用于移动设备的问题，本文提出了一种基于MBR的GPS轨迹数据压缩算法，通过Geolife作为样本数据集对该算法进行了测试。实验结果表明该算法对全局GPS轨迹数据和局部GPS轨迹数据均有较高的压缩率和压缩精度，为移动设备的GPS轨迹数据提供了一种有效的压缩方法。

关键词：GPS轨迹数据；数据压缩；MBR

伴随着物联网的快速发展和移动设备的大量普及，GPS轨迹数据呈爆炸式增长趋势。通过数据挖掘可以从这些数据中获得大量有用信息，构建大数据，实现云计算。但是GPS轨迹数据的巨大数据量给信息挖掘造成很大的困难，轨迹数据压缩成为当前移动设备GPS轨迹数据挖掘的研究热点[1]。所谓数据压缩，就是在保持原GPS轨迹数据形成的路径信息走势的前提下，尽可能的删除无用的点或者信息量少的点。

GPS轨迹数据压缩算法主要分为两大类，全局的GPS轨迹数据压缩算法和局部的GPS轨迹数据压缩算法，常见的压缩算法在压缩速度和压缩精度上均不适用于移动设备。如均匀采样法，它按给定的时间间隔或者距离间隔来决定保留哪些点，算法虽然简单，但对时空相关性不敏感，具有很大的不稳定性；航位推算法是通过直接相邻的坐标点的各种特性来决定是否保留当前的点，时间复杂度是线性的，同时也会积累显著的误差；Douglas Peucker算法是Douglas和Peucker[2]提出的，在规定的误差阈值内压缩通过递归选择的两个点之间的线段，其精确性虽高，但同时它对计算机资源(CPU和内存)的消耗也相当高，这种算法的时间复杂度也很高。

针对常用GPS迹数据压缩方法不适用于移动设备的特点，本文提出了一种基于MBR的GPS轨迹数据压缩算法。

1最小边界矩形(MBR)

最小边界矩形(Minimum Bounding Rectangle, MBR)是指能将GPS轨迹上的一段路径上包括的点全部包含进去的最小矩形[3]。如图1，其中以四个点为一个单位绘制了三个最小边界矩形。

图1最小边界矩形的示例图2声音抽样数据

例如在一个声音抽样数据中画出了三个最小边界矩形，如图2。通过分析每个范围内的声音数据的信息可以推断出这样的假设：

(1)最小边界矩形的面积越大，越多的抽样数据点将被保存进来(图2中的MBR2)。

(2)位于最小边界矩形的边界上的抽样数据点包含更多的有用信息(图2中最小边界矩形上的点)。

根据对数据的观察，为了达到最少的数据失真，保留信息内容的总量要尽可能的保持不变。在时空数据中，对于研究的轨迹数据，轨迹数据的信息内容可以被每一组抽样数据所表现，位置坐标(x, y)可以看做和抽样数据中的信息内容是一样的，并且在最小边界矩形上的点包含更多的信息内容。下面研究以此为基础的GPS轨迹数据压缩算法。

2基于MBR的轨迹数据压缩方法

2.1MBR分割和合并原则

图3分割和合并原则示例

根据MBR方法，首先要对轨迹数据进行分割和合并，分割较大的最小边界矩形，合并较小的最小边界矩形，以保证所有的最小边界矩形都有大体一致的面积。图3所示，开始以4个点(这个数值可以由用户自行设定)为一组画出了4个最小边界矩形，然后合并了MBR2和MBR3，因为它们的面积远远小于标准的MBR(标准MBR的面积是由用户自行设定的)，同时分割了MBR4，因为它的面积远远大于标准的MBR。标准MBR的大小可以根据实验或者特殊的需求而设定，它的值和构成MBR的点的数量直接影响GPS轨迹数据压缩的压缩率和压缩精度。[4]

本文采用一种利用周期性计算标准MBR大小的方法，取所有MBR大小的平均值作为标准MBR大小的方法，保证了整个压缩过程中具有一致的压缩精度。这种方法的优势在包含多种运动方式的GPS轨迹中表现的最为突出，因为不同速度等级的移动方式下的标准MBR大小是有显著差别的，而这种方法确定的标准MBR大小避免了不同移动方式下使用固定标准MBR大小产生的失真。[5-6]

2.2选点策略

通过分割和合并后的最小边界矩形，包含大体相同的信息量内容，然后将通过这样的策略来确定哪些点保留和哪些点删除，见表1。

(1)当MBR的面积大于标准MBR的面积的2倍时，分割当前MBR。

(2)当MBR的面积大于标准MBR的面积并且小于标准MBR的面积的2倍时，选择保留4个点，分别为x坐标最小的点，y坐标最小的点，x坐标最大的点和y坐标最大的点。

(3)当MBR的面积大于标准MBR的面积的一半并且小于标准MBR的面积时，选择保留2个点，分别为当前MBR内在时间线上排列的第一个点和最后一个点。

(4)当MBR的面积大于标准MBR的面积的四分之一并且小于标准MBR的面积的一半时，只选择保留时间线上中间的那个点。

(5)当MBR的面积小于标准MBR的面积的四分之一时，合并当前MBR。

表1　选点策略

3基于MBR的轨迹数据压缩方法描述

输入：St_MBR_Points_Num：最初划分MBR时一个MBR包含几个点。

St_MBR_Area：标准MBR的面积。

Traj：原路径。

输出：压缩后路径。

MBR_Algorithm(St_MBR_Points_Num, St_MBR_Area, Traj)

{

Num = St_MBR_Points_Num;

Foreach point in Traj

{

If Num = Buf.Count

{

rlt = SelectPoints(Buf);

If rlt = false then Num = Num * 2;//合并MBR

}

Else {Buf.Add(point);}

}

}

SelectPoints(Buf)

{

Area = (Max_X(Buf) - Min_X(Buf)) * (Max_Y(Buf) - Min_Y(Buf));

If Area > St_MBR_Area * 2

{//分割MBR

SelectPoints(Buf/2);//前面一部分

SelectPoints(Buf/2);//后面一部分

}

Else if Area < St_MBR_Area/4

{

Return false;//需要合并

}Else SavePoints();//用选点策略存储点

GPS轨迹数据在压缩后直接存储仍然会占用很多的存储空间，对压缩后的数据进行一些特定的编码可以进一步提高GPS轨迹数据的压缩率。

4实验与结果分析

4.1测试数据集

为了测试本文提出的MBR的轨迹数据压缩的效果，实验采用Geolife为样本数据集，其中主要记录了182位志愿者的出行信息。根据本次实验的特点，首先筛选出了含有具体交通模式(labels)的69组轨迹信息，它们的具体轨迹信息Trajectory都按照时间顺序存储在plt文件中，使用Office中的Access作为数据库进行压缩处理，对全局和局部的GPS轨迹数据压缩压缩效果、压缩率和压缩率进行对比。

4.2实验结果

实验一：使用数据为 GPS轨迹数据原文件r1.txt(22KB)

(1)全局的GPS轨迹数据压缩：

参数设置：Max SED(m)为3。

压缩效果如图4。压缩率：90.9%，r1_global.dat为2KB。简化率：13.6% ，r1_global_Dec.txt为19KB。

(2)局部的GPS轨迹数据压缩：

参数设置：stMbrArea为5000，stMbrPointsNum为4。

压缩效果如图5。压缩率：95.5%，r1_local.dat为1KB。简化率：72.7%，r1_local_Dec.txt为6KB。

图4实验一 全局的GPS轨迹数据压缩效果图图5实验一 局部的GPS轨迹数据压缩效果图

实验二：实验数据为GPS轨迹数据原文件r6.txt(150KB)

(1)全局的GPS轨迹数据压缩：

参数设置：Max SED(m)为3。

压缩效果如图6。压缩率：98.0%，r6_global.dat为3KB。简化率：82.0%，r6_global_Dec.txt为27KB。

(2)局部的GPS轨迹数据压缩：

参数设置：stMbrArea为5000，stMbrPointsNum为4。

图6实验二全局的GPS轨迹数据压缩效果图图7实验二局部的GPS轨迹数据压缩效果图

压缩效果如图7。压缩率：98.7%，r6_local.dat为2KB。简化率：88.0%，r6_local_Dec.txt为18KB。

从实验结果可以看出，全局GPS轨迹数据压缩算法的压缩率略低于局部GPS轨迹数据压缩算法压缩率。全局GPS轨迹数据压缩算法对轨迹的压缩精度要高于局部GPS轨迹数据压缩算法(见压缩效果图)。GPS轨迹数据压缩算法可以对GPS轨迹数据文件进行有效的压缩。

5结论

本文针对轨迹数据的数据量巨大给信息挖掘造成很大的困难，在数据挖掘之前，需对轨迹数据进行压缩。在对现有的轨迹数据压缩算法进行分析的前提下，提出基于MBR的轨迹数据压缩方法，并给出了轨迹数据压缩算法，并采用Geolife为样本数据集进行压缩实验，实验证明了本文算法的实际运行效果和有效性。

参考文献：

[1]袁冠.移动对象轨迹数据挖掘方法研究[D].徐州：中国矿业大学 2012.

[2]Douglas, D.andT.Peucker. Algorithms for the reduction of the number of points required to represent adigitized line or itscaricature,[J]The Canadian Cartographer, 1973(10)：112-122.

[3]金龙.基于MBR的地图匹配算法研究[D]. 湘潭：湖南科技大学 2012.

[4]王欣然,杨智应.基于最小边界扇形的移动对象轨迹实时化简算法[J].计算机应用.2014(8) ：2409-2414.

[5]冯神柱.路网轨迹数据的压缩存储技术研究[D]. 杭州：杭州电子科技大学 2013.

[6]张达夫,张昕明.基于时空特性的GPS轨迹数据压缩算法[J].交通信息与安全.2013(3) ：6-9.

(编辑：严佩峰)

GPS Trajectory Data Compression Algorithm Based on MBR

ZHU Meng，SUN Jian

(College of Information Engineering, Xinyang College of Agriculture and Forestry, Xinyang 464000, China)

Abstract：GPS trajectory data is a kind of data with spatial and temporal characteristics. In order to reduce GPS trajectory data storage space and improve the efficiency of data analysis. In view of the common GPS trace data compression method is not applicable to mobile devices, a new trajectory data compression algorithm based on MBR is proposed. Tested with Geolife sample data，the experimental results show that the new algorithm has a good compression effect in reducing rate and accuracy in the whole or part trajectory data. In conclusion, we proved an effective way to GPS trajectory data compression.

Keywords：GPS trajectory data; data compression; minimum bounding rectangle

中图分类号：TP301

文献标识码：A

文章编号：2095-8978(2016)01-0117-04

作者简介：朱猛(1977—)，男，江苏沛县人，讲师，硕士，主要研究方向为智能信息处理.

基金项目：河南省教育厅高等学校重点科研项目(15A520095)

收稿日期：2015-11-24