基于MBR的GPS軌跡數(shù)據(jù)壓縮算法

朱　猛，孫　劍

(信陽農林學院 信息工程學院，河南 信陽 464000)

?

基于MBR的GPS軌跡數(shù)據(jù)壓縮算法

朱猛，孫劍

(信陽農林學院 信息工程學院，河南 信陽 464000)

摘要：移動對象產(chǎn)生的大量GPS軌跡數(shù)據(jù)，蘊含了豐富的時間和空間信息。為了減少GPS軌跡數(shù)據(jù)的存儲空間，提高數(shù)據(jù)分析的效率，針對常用GPS軌跡數(shù)據(jù)壓縮方法不適用于移動設備的問題，本文提出了一種基于MBR的GPS軌跡數(shù)據(jù)壓縮算法，通過Geolife作為樣本數(shù)據(jù)集對該算法進行了測試。實驗結果表明該算法對全局GPS軌跡數(shù)據(jù)和局部GPS軌跡數(shù)據(jù)均有較高的壓縮率和壓縮精度，為移動設備的GPS軌跡數(shù)據(jù)提供了一種有效的壓縮方法。

關鍵詞：GPS軌跡數(shù)據(jù)；數(shù)據(jù)壓縮；MBR

伴隨著物聯(lián)網(wǎng)的快速發(fā)展和移動設備的大量普及，GPS軌跡數(shù)據(jù)呈爆炸式增長趨勢。通過數(shù)據(jù)挖掘可以從這些數(shù)據(jù)中獲得大量有用信息，構建大數(shù)據(jù)，實現(xiàn)云計算。但是GPS軌跡數(shù)據(jù)的巨大數(shù)據(jù)量給信息挖掘造成很大的困難，軌跡數(shù)據(jù)壓縮成為當前移動設備GPS軌跡數(shù)據(jù)挖掘的研究熱點[1]。所謂數(shù)據(jù)壓縮，就是在保持原GPS軌跡數(shù)據(jù)形成的路徑信息走勢的前提下，盡可能的刪除無用的點或者信息量少的點。

GPS軌跡數(shù)據(jù)壓縮算法主要分為兩大類，全局的GPS軌跡數(shù)據(jù)壓縮算法和局部的GPS軌跡數(shù)據(jù)壓縮算法，常見的壓縮算法在壓縮速度和壓縮精度上均不適用于移動設備。如均勻采樣法，它按給定的時間間隔或者距離間隔來決定保留哪些點，算法雖然簡單，但對時空相關性不敏感，具有很大的不穩(wěn)定性；航位推算法是通過直接相鄰的坐標點的各種特性來決定是否保留當前的點，時間復雜度是線性的，同時也會積累顯著的誤差；Douglas Peucker算法是Douglas和Peucker[2]提出的，在規(guī)定的誤差閾值內壓縮通過遞歸選擇的兩個點之間的線段，其精確性雖高，但同時它對計算機資源(CPU和內存)的消耗也相當高，這種算法的時間復雜度也很高。

針對常用GPS跡數(shù)據(jù)壓縮方法不適用于移動設備的特點，本文提出了一種基于MBR的GPS軌跡數(shù)據(jù)壓縮算法。

1最小邊界矩形(MBR)

最小邊界矩形(Minimum Bounding Rectangle, MBR)是指能將GPS軌跡上的一段路徑上包括的點全部包含進去的最小矩形[3]。如圖1，其中以四個點為一個單位繪制了三個最小邊界矩形。

圖1最小邊界矩形的示例圖2聲音抽樣數(shù)據(jù)

例如在一個聲音抽樣數(shù)據(jù)中畫出了三個最小邊界矩形，如圖2。通過分析每個范圍內的聲音數(shù)據(jù)的信息可以推斷出這樣的假設：

(1)最小邊界矩形的面積越大，越多的抽樣數(shù)據(jù)點將被保存進來(圖2中的MBR2)。

(2)位于最小邊界矩形的邊界上的抽樣數(shù)據(jù)點包含更多的有用信息(圖2中最小邊界矩形上的點)。

根據(jù)對數(shù)據(jù)的觀察，為了達到最少的數(shù)據(jù)失真，保留信息內容的總量要盡可能的保持不變。在時空數(shù)據(jù)中，對于研究的軌跡數(shù)據(jù)，軌跡數(shù)據(jù)的信息內容可以被每一組抽樣數(shù)據(jù)所表現(xiàn)，位置坐標(x, y)可以看做和抽樣數(shù)據(jù)中的信息內容是一樣的，并且在最小邊界矩形上的點包含更多的信息內容。下面研究以此為基礎的GPS軌跡數(shù)據(jù)壓縮算法。

2基于MBR的軌跡數(shù)據(jù)壓縮方法

2.1MBR分割和合并原則

圖3分割和合并原則示例

根據(jù)MBR方法，首先要對軌跡數(shù)據(jù)進行分割和合并，分割較大的最小邊界矩形，合并較小的最小邊界矩形，以保證所有的最小邊界矩形都有大體一致的面積。圖3所示，開始以4個點(這個數(shù)值可以由用戶自行設定)為一組畫出了4個最小邊界矩形，然后合并了MBR2和MBR3，因為它們的面積遠遠小于標準的MBR(標準MBR的面積是由用戶自行設定的)，同時分割了MBR4，因為它的面積遠遠大于標準的MBR。標準MBR的大小可以根據(jù)實驗或者特殊的需求而設定，它的值和構成MBR的點的數(shù)量直接影響GPS軌跡數(shù)據(jù)壓縮的壓縮率和壓縮精度。[4]

本文采用一種利用周期性計算標準MBR大小的方法，取所有MBR大小的平均值作為標準MBR大小的方法，保證了整個壓縮過程中具有一致的壓縮精度。這種方法的優(yōu)勢在包含多種運動方式的GPS軌跡中表現(xiàn)的最為突出，因為不同速度等級的移動方式下的標準MBR大小是有顯著差別的，而這種方法確定的標準MBR大小避免了不同移動方式下使用固定標準MBR大小產(chǎn)生的失真。[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的軌跡數(shù)據(jù)壓縮方法描述

輸入：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軌跡數(shù)據(jù)在壓縮后直接存儲仍然會占用很多的存儲空間，對壓縮后的數(shù)據(jù)進行一些特定的編碼可以進一步提高GPS軌跡數(shù)據(jù)的壓縮率。

4實驗與結果分析

4.1測試數(shù)據(jù)集

為了測試本文提出的MBR的軌跡數(shù)據(jù)壓縮的效果，實驗采用Geolife為樣本數(shù)據(jù)集，其中主要記錄了182位志愿者的出行信息。根據(jù)本次實驗的特點，首先篩選出了含有具體交通模式(labels)的69組軌跡信息，它們的具體軌跡信息Trajectory都按照時間順序存儲在plt文件中，使用Office中的Access作為數(shù)據(jù)庫進行壓縮處理，對全局和局部的GPS軌跡數(shù)據(jù)壓縮壓縮效果、壓縮率和壓縮率進行對比。

4.2實驗結果

實驗一：使用數(shù)據(jù)為 GPS軌跡數(shù)據(jù)原文件r1.txt(22KB)

(1)全局的GPS軌跡數(shù)據(jù)壓縮：

參數(shù)設置：Max SED(m)為3。

壓縮效果如圖4。壓縮率：90.9%，r1_global.dat為2KB。簡化率：13.6% ，r1_global_Dec.txt為19KB。

(2)局部的GPS軌跡數(shù)據(jù)壓縮：

參數(shù)設置：stMbrArea為5000，stMbrPointsNum為4。

壓縮效果如圖5。壓縮率：95.5%，r1_local.dat為1KB。簡化率：72.7%，r1_local_Dec.txt為6KB。

圖4實驗一 全局的GPS軌跡數(shù)據(jù)壓縮效果圖圖5實驗一 局部的GPS軌跡數(shù)據(jù)壓縮效果圖

實驗二：實驗數(shù)據(jù)為GPS軌跡數(shù)據(jù)原文件r6.txt(150KB)

(1)全局的GPS軌跡數(shù)據(jù)壓縮：

參數(shù)設置：Max SED(m)為3。

壓縮效果如圖6。壓縮率：98.0%，r6_global.dat為3KB。簡化率：82.0%，r6_global_Dec.txt為27KB。

(2)局部的GPS軌跡數(shù)據(jù)壓縮：

參數(shù)設置：stMbrArea為5000，stMbrPointsNum為4。

圖6實驗二全局的GPS軌跡數(shù)據(jù)壓縮效果圖圖7實驗二局部的GPS軌跡數(shù)據(jù)壓縮效果圖

壓縮效果如圖7。壓縮率：98.7%，r6_local.dat為2KB。簡化率：88.0%，r6_local_Dec.txt為18KB。

從實驗結果可以看出，全局GPS軌跡數(shù)據(jù)壓縮算法的壓縮率略低于局部GPS軌跡數(shù)據(jù)壓縮算法壓縮率。全局GPS軌跡數(shù)據(jù)壓縮算法對軌跡的壓縮精度要高于局部GPS軌跡數(shù)據(jù)壓縮算法(見壓縮效果圖)。GPS軌跡數(shù)據(jù)壓縮算法可以對GPS軌跡數(shù)據(jù)文件進行有效的壓縮。

5結論

本文針對軌跡數(shù)據(jù)的數(shù)據(jù)量巨大給信息挖掘造成很大的困難，在數(shù)據(jù)挖掘之前，需對軌跡數(shù)據(jù)進行壓縮。在對現(xiàn)有的軌跡數(shù)據(jù)壓縮算法進行分析的前提下，提出基于MBR的軌跡數(shù)據(jù)壓縮方法，并給出了軌跡數(shù)據(jù)壓縮算法，并采用Geolife為樣本數(shù)據(jù)集進行壓縮實驗，實驗證明了本文算法的實際運行效果和有效性。

參考文獻：

[1]袁冠.移動對象軌跡數(shù)據(jù)挖掘方法研究[D].徐州：中國礦業(yè)大學 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]馮神柱.路網(wǎng)軌跡數(shù)據(jù)的壓縮存儲技術研究[D]. 杭州：杭州電子科技大學 2013.

[6]張達夫,張昕明.基于時空特性的GPS軌跡數(shù)據(jù)壓縮算法[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