一種面向輪廓保持的軌跡數(shù)據(jù)壓縮算法

孟 慶 彬，　于 曉 強(qiáng)，　劉 　 柏，　邵 　 利

( 大連工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院, 遼寧 大連　116034 )

0　引　言

近年來(lái)，隨著具有定位功能的傳感器及智能移動(dòng)終端的興起，人們可以很方便地獲取到個(gè)人的移動(dòng)軌跡。通過(guò)對(duì)軌跡數(shù)據(jù)進(jìn)行分析可以為熱點(diǎn)區(qū)域發(fā)現(xiàn)、城市交通監(jiān)控、城市功能區(qū)識(shí)別、城市公共衛(wèi)生及城市旅游管理等提供支持[1]。但隨著用戶規(guī)模的增大，軌跡數(shù)據(jù)幾乎呈指數(shù)增長(zhǎng)。有資料表明，北京市有67 000輛出租車，如果這些出租車以2～3 s為周期向數(shù)據(jù)中心發(fā)送位置信息，這些出租車每天就能夠產(chǎn)生60 TB的軌跡數(shù)據(jù)[2]。這些軌跡數(shù)據(jù)中包含了很多有價(jià)值的信息，但海量的軌跡數(shù)據(jù)也給基于位置的服務(wù)(location based service，LBS)帶來(lái)了挑戰(zhàn)：海量的軌跡數(shù)據(jù)會(huì)占用大量的存儲(chǔ)空間；海量的軌跡數(shù)據(jù)會(huì)消耗大量的傳輸流量；當(dāng)在瀏覽器中渲染這些軌跡數(shù)據(jù)時(shí)，會(huì)給瀏覽器帶來(lái)沉重的負(fù)擔(dān)。在地圖上渲染1 000個(gè)定位點(diǎn)就需要1 s的時(shí)間[3]，當(dāng)軌跡數(shù)據(jù)的規(guī)模變大時(shí)，難以從軌跡數(shù)據(jù)中挖掘到有用的知識(shí)模式，減少數(shù)據(jù)的規(guī)模能夠使得模式挖掘變得相對(duì)容易[4]。

軌跡壓縮可以分為在線壓縮與離線壓縮。離線軌跡壓縮在進(jìn)行壓縮時(shí)，需要軌跡的全部數(shù)據(jù)。進(jìn)行離線軌跡壓縮時(shí)可以充分地利用軌跡的特征，實(shí)現(xiàn)精確的壓縮。在線軌跡壓縮可以在實(shí)時(shí)地接收軌跡定位點(diǎn)的過(guò)程中進(jìn)行軌跡壓縮，具有支持在線應(yīng)用的優(yōu)勢(shì)。一般來(lái)說(shuō)在線軌跡壓縮的壓縮精度要低于離線軌跡壓縮。

離線軌跡壓縮算法包括Douglas-Peucker算法[5]、TD-TR算法[6]、最優(yōu)化的軌跡壓縮算法[7-10]、近似最優(yōu)化的軌跡壓縮算法[11]、TS算法[12]、SQUISH-E(μ)算法[13]。在線軌跡壓縮算法包括Before-OPW-TR算法[6]、Normal-OPW-TR算法[6]、SQUISH-E(λ)算法[13-14]、SQUISH算法[15-17]。這些軌跡壓縮算法能夠高效地進(jìn)行軌跡壓縮，但壓縮過(guò)程中大多沒(méi)有對(duì)軌跡的輪廓進(jìn)行控制，因而在使用這些算法進(jìn)行軌跡壓縮時(shí)易造成軌跡輪廓的丟失。軌跡的輪廓對(duì)于描述軌跡的語(yǔ)義起著至關(guān)重要的作用。從一個(gè)完整輪廓的軌跡中能夠詳盡地了解到用戶去過(guò)的地點(diǎn)，在哪些區(qū)域或地點(diǎn)進(jìn)行過(guò)停留(停留區(qū)域用戶的運(yùn)動(dòng)方向變化較為頻繁，在停留點(diǎn)由于用戶的細(xì)微移動(dòng)和定位系統(tǒng)的誤差也會(huì)導(dǎo)致較大的方向變化)，進(jìn)而可以理解用戶的行為。不完整的輪廓會(huì)造成曾經(jīng)到達(dá)地點(diǎn)(例如：銀行)、停留點(diǎn)(例如：高速公路繳費(fèi)站、堵車地點(diǎn))的丟失，不能反映用戶在停留區(qū)域(例如：公園)的詳細(xì)的行走路線。沒(méi)有這些細(xì)節(jié)，就無(wú)法清楚地了解用戶的行為，就會(huì)造成軌跡語(yǔ)義的丟失。

圖1針對(duì)距離閾值算法，在10 m距離閾值的條件下，展示了一條步行軌跡及其壓縮后的表現(xiàn)形式。從圖1中虛線框所示的區(qū)域可以看出，SQUISH-E(μ)、DP、TD-TR、Before-OPW-TR和Normal-OPW-TR算法均會(huì)造成不同程度的輪廓丟失。

為了解決軌跡壓縮過(guò)程中輪廓丟失的問(wèn)題，提出了一種面向輪廓保持的軌跡數(shù)據(jù)壓縮算法。該算法使用歐氏距離閾值和角度閾值在開(kāi)放窗口的過(guò)程中對(duì)軌跡數(shù)據(jù)進(jìn)行壓縮。通過(guò)設(shè)置角度閾值，該算法能夠有效地捕捉到單個(gè)定位點(diǎn)的方向變化以及窗口內(nèi)所有定位點(diǎn)方向漸變的情況，從而實(shí)現(xiàn)了對(duì)軌跡輪廓的控制。

(a) 原始軌跡

(b) SQUISH-E(μ)算法

(c) DP算法

(d) TD-TR算法

(e) Before-OPW-TR算法

(f) Normal-OPW-TR算法

圖1一條步行軌跡及其在不同算法10 m閾值壓縮后的軌跡

Fig.1A walking trajectory and its 10 m threshold compression trajectories at different algorithms

1　軌跡壓縮相關(guān)定義

定義1軌跡

一條長(zhǎng)度為n的軌跡T是一系列以時(shí)間為順序的定位點(diǎn)的集合，即T={P1，P2，…，Pn-1，Pn}。T中每一個(gè)定位點(diǎn)Pi都由三元組(xi，yi，ti)組成，其中xi與yi代表移動(dòng)對(duì)象在ti時(shí)刻的位置坐標(biāo)。

定義2軌跡壓縮

給定軌跡T={P1，P2，…，Pn-1，Pn}，軌跡壓縮就是要尋找一系列以時(shí)間為順序的定位點(diǎn)的集合T′(T的子集)，即T′={Pc1，Pc2，…，Pcm-1，Pcm}，其中1=c1

定義3壓縮率

給定原始軌跡T={P1，P2，…，Pn-1，Pn}，壓縮后的軌跡T′={Pc1，Pc2，…，Pcm-1，Pcm}。壓縮率

CR=n/m，n≥m

(1)

定義4歐氏距離誤差

給定原始軌跡T及壓縮后的軌跡T′，T中的定位點(diǎn)Pi對(duì)應(yīng)于T′的歐氏距離誤差可表示為Pi與Pi的估計(jì)點(diǎn)P′i之間的距離。如果T′中包含Pi，則P′i=Pi。否則，P′i為Pi與直線predT′(Pi)succT′(Pi)的垂點(diǎn)，predT′(Pi) 與succT′(Pi)分別表示T′中離Pi最近的前驅(qū)和后繼。

圖2用軌跡T={P1，P2，P3，P4，P5，P6}及其壓縮后的軌跡T′={P1，P4，P6}闡述了歐氏距離誤差。如圖2所示，軌跡T中P1，P4，P6對(duì)應(yīng)于T′的歐氏距離誤差為零。P2的歐氏距離誤差為P2到直線P1P4的垂直距離。

圖2　歐式距離誤差

定義5方向誤差

給定原始軌跡T及壓縮后的軌跡T′，軌跡T中Pi點(diǎn)對(duì)應(yīng)于T′的方向誤差可表示為HeadingChange(h1，h2)，其中h1為Pi點(diǎn)的方向，h2為T′中的定位點(diǎn)PsPe構(gòu)成的射線方向。其中，Ps=predT′(Pi+1)，Pe=succT′(Pi)。方向變化函數(shù)HeadingChange及方向函數(shù)Heading定義為

Heading(Pi)=PiPi+1，Pi≠Pn

(2)

Heading(PsPe)=PsPe

(3)

HeadingChange(h1，h2)=

(4)

2　面向輪廓保持的軌跡壓縮算法

2.1　算法描述

給定原始軌跡T，歐氏距離閾值μ和角度閾值θ。在T中的第1個(gè)定位點(diǎn)P1及第3個(gè)定位點(diǎn)P3之間定義一個(gè)窗口，其中P1被稱之為錨點(diǎn)Pa，P3被稱之為浮動(dòng)點(diǎn)Pf。執(zhí)行如下步驟：

(1)計(jì)算窗口內(nèi)每一個(gè)定位點(diǎn)Pi(除浮動(dòng)點(diǎn)Pf)到PaPf的歐氏距離及Pi與射線PaPf之間的方向變化。如果任意一個(gè)定位點(diǎn)的歐氏距離超過(guò)μ或方向變化超過(guò)θ，則在該窗口內(nèi)選擇具有最大歐氏距離誤差的定位點(diǎn)成為新的錨點(diǎn)，新錨點(diǎn)后的第2個(gè)點(diǎn)成為新的浮動(dòng)點(diǎn)。

(2)如果在該窗口內(nèi)μ與θ均沒(méi)有被超過(guò)，則進(jìn)一步判斷浮動(dòng)點(diǎn)的前一個(gè)點(diǎn)Pf-1是否為拐點(diǎn)，即判斷定位點(diǎn)Pf-2與定位點(diǎn)Pf-1之間的方向變化是否大于θ。如果Pf-1是拐點(diǎn)，則Pf-1成為新的錨點(diǎn)，Pf+1成為新的浮動(dòng)點(diǎn)。

如果在窗口PaPf之間沒(méi)有新錨點(diǎn)產(chǎn)生，則浮動(dòng)點(diǎn)Pf向下移動(dòng)一個(gè)點(diǎn)，在新窗口中重復(fù)執(zhí)行上述步驟。如果產(chǎn)生了新錨點(diǎn)和浮動(dòng)點(diǎn)，則將上述步驟應(yīng)用于新錨點(diǎn)與新浮動(dòng)點(diǎn)構(gòu)成的窗口。不斷地重復(fù)這個(gè)過(guò)程，直到整個(gè)軌跡T被壓縮為T′。

逐步開(kāi)放窗口的過(guò)程中檢查歐氏距離和角度變化，該算法可以確保所有方向變化大于θ的拐點(diǎn)被保留在T′中，同時(shí)可以確保窗口內(nèi)每一個(gè)定位點(diǎn)的歐氏距離誤差不超過(guò)μ，任意兩個(gè)定位點(diǎn)之間的方向變化不大于2θ。如圖3所示，通過(guò)設(shè)置10 m、60°的閾值對(duì)圖1(a)中所示的軌跡進(jìn)行了壓縮。結(jié)合圖1、圖3可以看出，相比于其他算法，本文算法能夠有效地保留軌跡的輪廓特征。

圖3　本文算法的壓縮軌跡

2.2　算法偽代碼

面向輪廓保持的軌跡壓縮算法如表1所示，算法首先選取P1和P3作為錨點(diǎn)和浮動(dòng)點(diǎn)(第2、3行)對(duì)窗口內(nèi)的定位點(diǎn)執(zhí)行步驟1和步驟2(第7行)，如果在窗口內(nèi)沒(méi)有新的錨點(diǎn)及浮動(dòng)點(diǎn)產(chǎn)生(即index=1)，則浮動(dòng)點(diǎn)向下移動(dòng)一個(gè)點(diǎn)(第13行)。如果有新的錨點(diǎn)產(chǎn)生，則Pindex和Pindex+2成為新的錨點(diǎn)及浮動(dòng)點(diǎn)(第10、11行)。當(dāng)整個(gè)軌跡T被壓縮完畢后，算法返回壓縮后的軌跡T′(第20行)。

表1　面向輪廓保持的軌跡壓縮算法Tab.1　Compression algorithm of contour maintaining oriented trajectory

doCheckInWindow算法如表2所示，doCheckInWindow算法首先計(jì)算射線PaPf的方向，然后計(jì)算窗口內(nèi)每個(gè)定位點(diǎn)Pi與PaPf的歐氏距離及方向變化(第5、7行)，如果θ或μ被超過(guò)，則返回窗口中具有最大歐氏距離誤差定位點(diǎn)的索引(第11行)。如果窗口中所有定位點(diǎn)的歐氏距離誤差及方向誤差均未超過(guò)給定閾值，則進(jìn)一步計(jì)算浮動(dòng)點(diǎn)的前一個(gè)點(diǎn)Pf-1的方向變化(第15行)，如果Pf-1為拐點(diǎn)，則返回Pf-1的索引(第17行)。如果窗口內(nèi)沒(méi)有新的錨點(diǎn)產(chǎn)生，算法返回-1(第19行)。

表2　doCheckInWindow算法Tab.2　doCheckInWindow algorithm

3　算法評(píng)估

使用Scala語(yǔ)言，選用Geolife數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。Geolife 數(shù)據(jù)集由182個(gè)用戶，歷時(shí)5年(2007年4月—2012年8月)收集而來(lái)。其中73個(gè)用戶標(biāo)記了他們軌跡的交通模式，例如：開(kāi)車、乘公交、騎自行車和步行。Geolife 數(shù)據(jù)集包含了17 621條軌跡，總長(zhǎng)度1 292 951 km，累積時(shí)間50 176 h。這些軌跡數(shù)據(jù)來(lái)自不同的GPS 記錄器和智能手機(jī)，軌跡的采樣周期也不盡相同，其中91.5%的軌跡為密集采樣，即每隔1～5 s或每隔5～10 m記錄一個(gè)定位點(diǎn)。

在Geolife數(shù)據(jù)集中選取了3條不同交通模式的軌跡作為實(shí)驗(yàn)數(shù)據(jù)，軌跡1是一條混合交通模式的軌跡(步行、公交、火車)，包含了5 911個(gè)定位點(diǎn)，歷時(shí)229 min。軌跡2為高速公路上汽車行駛的軌跡，其中包含2 167個(gè)定位點(diǎn)，歷時(shí)37 min。軌跡3是一條步行軌跡，其中包含了2 121 個(gè)定位點(diǎn)，歷時(shí)94 min。

為了評(píng)估軌跡壓縮算法壓縮的精確程度，選取了平均歐氏距離誤差(average Euclidean distance error，AEDE)及平均方向誤差(average heading error，AHE)對(duì)算法進(jìn)行評(píng)估。給定原始軌跡T及壓縮后的軌跡T′，平均歐氏距離誤差及平均方向誤差的定義

(5)

(6)

3.1　相同距離閾值下各算法的比較

由于本文算法通過(guò)使用歐氏距離閾值及角度閾值對(duì)軌跡的輪廓進(jìn)行了控制，故該算法的壓縮效率受軌跡中定位點(diǎn)方向變化的影響很大。一般來(lái)說(shuō)，用戶的行走及移動(dòng)對(duì)象的停留均會(huì)造成較大的方向變化。如圖4所示，由于軌跡1與軌跡3均包含有步行段，故使用本文算法對(duì)軌跡1及軌跡3進(jìn)行壓縮時(shí)，壓縮率主要受角度閾值的影響。對(duì)于軌跡3，設(shè)置角度閾值與不設(shè)置角度閾值(角度閾值=180°)的壓縮率相差較大，因此可以看出軌跡3中定位點(diǎn)的方向變化較大、方向變化頻繁。因此在使用其他算法對(duì)軌跡3進(jìn)行壓縮時(shí)，極易造成軌跡輪廓的丟失。相比于軌跡1與軌跡3，軌跡2為高速公路上汽車的行駛軌跡，因只在服務(wù)區(qū)和高速公路收費(fèi)站處停留，其方向變化較小，壓縮率同時(shí)受距離閾值與角度閾值的影響。

由于軌跡1及軌跡3的方向變化較大，故設(shè)置一個(gè)相對(duì)寬松的角度閾值就能較好地保持其輪廓。而軌跡2由于其本身的方向變化就小，為了較好的保持其輪廓特征，則需要一個(gè)相對(duì)小的角度閾值。因此，在接下來(lái)相同距離閾值的比較中，針對(duì)3條軌跡，將算法的角度閾值分別設(shè)置為40°、10°及60°。圖5為相同距離閾值條件下各算法的平均歐氏距離誤差，從圖中可以看出本文算法在軌跡1及軌跡3上的誤差較小，而在軌跡2上的誤差相對(duì)較大。

(a) 軌跡1(混合交通模式)

(b) 軌跡2(高速公路上汽車的軌跡)

(c) 軌跡3(步行軌跡)

(a) 軌跡1(混合交通模式)s

(b) 軌跡2(高速公路上汽車的軌跡)s

(c) 軌跡3(步行軌跡)

平均方向誤差在一定程度上可以反映出軌跡輪廓的保持情況，圖6為相同距離閾值條件下，平均方向誤差的角度對(duì)軌跡輪廓的保持情況。從圖6中可看出，本文算法具有輪廓保持方面的優(yōu)勢(shì)。

3.2　相同壓縮率下各算法的比較

由于算法受軌跡方向變化的影響較大，故為了達(dá)到指定的壓縮率，需要將算法的角度閾值設(shè)置為鈍角或平角(即不對(duì)角度進(jìn)行控制)。在這種情況下，算法將失去其輪廓保持方面的優(yōu)勢(shì)。如圖7所示，在相同的壓縮率的條件下，在平均歐氏距離誤差方面，本文算法及DP算法表現(xiàn)最好。相比于DP算法，本文算法具有支持在線應(yīng)用的優(yōu)勢(shì)。

圖8在相同壓縮率的條件下，就平均方向誤差進(jìn)行了比較。從圖中可以看出，對(duì)于軌跡1及軌跡3，本文算法的平均方向誤差與DP算法的基本一致，誤差較小。對(duì)于軌跡2，本文算法的平均方向誤差表現(xiàn)居中。

(a) 軌跡1(混合交通模式)

(b) 軌跡2(高速公路上汽車的軌跡)

(c) 軌跡3(步行軌跡)

(a) 軌跡1(混合交通模式)

(b) 軌跡2(高速公路上汽車的軌跡)

(c) 軌跡3(步行軌跡)

(a) 軌跡1(混合交通模式)

(b) 軌跡2(高速公路上汽車的軌跡)

(c) 軌跡3(步行軌跡)

4　結(jié)　論

提出了一種面向輪廓保持的軌跡數(shù)據(jù)壓縮算法，使用歐氏距離閾值和角度閾值，在逐步開(kāi)放窗口的過(guò)程中進(jìn)行軌跡壓縮。通過(guò)設(shè)置歐氏距離閾值和角度閾值，該算法有效地控制了軌跡的輪廓，確保算法不丟失拐點(diǎn)，解決了軌跡壓縮中輪廓丟失的問(wèn)題。該算法可以在實(shí)時(shí)接收定位點(diǎn)的過(guò)程中進(jìn)行軌跡壓縮，故具有支持在線應(yīng)用的優(yōu)勢(shì)。真實(shí)數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果表明，在相同歐氏距離閾值的情況下，本文提出的算法具有輪廓保持方面的優(yōu)勢(shì)。在相同壓縮率的情況下，也有著不錯(cuò)的表現(xiàn)。

參考文獻(xiàn):

[1] 李婷,裴韜,袁燁城.人類活動(dòng)軌跡的分類、模式和應(yīng)用研究綜述[J].地理科學(xué)進(jìn)展,2014,33(7):938-948.

[2] 袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應(yīng)用[D].合肥:中國(guó)科學(xué)技術(shù)大學(xué),2012.

[3] CHEN M J, XU M T, FRANTI P. A fast O(N) multiresolution polygonal approximation algorithm for GPS trajectory simplification[J]. IEEE Transactions on Image Processing, 2012, 21(5): 2770-2785.

[4] GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//ACM, 13th International Conference on Knowledge Discovery and Data Mining. San Jose: ACM, 2007: 330-339.

[5] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a line or its caricature[J]. International Journal for Geographic Information and Geovisualization, 1973, 10(2): 112-122.

[6] MERATNIA N, BY R A. Spatiotemporal compression techniques for moving point objects[C]//Springer, 9th International Conference on Extending Database Technology. Crete: Springer, 2004: 765-782.

[7] BELLMAN R. On the approximation of curves by line segments using dynamic programming[J]. Communications of the Association for Computing Machinery, 1961, 4(6): 284-286.

[8] PEREZ J C, VIDAL E. Optimum polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 1994, 15(8): 743-750.

[9] SALOTTI M. Improvement of perez and vidal algorithm for the decomposition of digitized curves into line segments[C]//IEEE, 15th Conference on Pattern Recognition. Barcelona: IEEE, 2000: 2878-2882.

[10] SALOTTI M. An efficient algorithm for the optimal polygonal approximation of digitized curves[J]. Pattern Recognition Letters, 2001, 22(2): 215-221.

[12] CHEN Y K, JIANG K, ZHENG Y, et al. Trajectory simplification method for location-based social networking services[C]//ACM, 2009 International Workshop on Location Based Social Networks. Seattle: ACM, 2009: 33-40.

[13] MUCKELL J, OLSEN P W, HWANG J H, et al. Compression of trajectory data: a comprehensive evaluation and new approach[J]. GeoInformatica, 2014, 18(3): 435-460.

[14] MUCKELL J, HWANG J, PATIL V, et al. SQUISH: an online approach for GPS trajectory compression[C]//ACM, 2nd International Conference on Computing for Geospatial Research and Applications. Washington: ACM, 2011:13.

[15] ZHENG Y, ZHANG L, XIE X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]//ACM, International Conference on World Wild Web. Madrid: ACM, 2009: 791-800.

[16] ZHENG Y, LI Q, CHEN Y K, et al. Understanding mobility based on GPS data[C]//Proceedings of the 10th International Conference on Ubiquitous Computing. Seoul: ACM, 2008: 312-321.

[17] ZHENG Y, XIE X, MA W Y. GeoLife: a collaborative social networking service among user, location and trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2010, 33(2): 32-40.