孟 慶 彬，　于 曉 強，　劉 　 柏，　邵 　 利

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

0　引　言

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

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

離線軌跡壓縮算法包括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]。這些軌跡壓縮算法能夠高效地進行軌跡壓縮，但壓縮過程中大多沒有對軌跡的輪廓進行控制，因而在使用這些算法進行軌跡壓縮時易造成軌跡輪廓的丟失。軌跡的輪廓對于描述軌跡的語義起著至關(guān)重要的作用。從一個完整輪廓的軌跡中能夠詳盡地了解到用戶去過的地點，在哪些區(qū)域或地點進行過停留(停留區(qū)域用戶的運動方向變化較為頻繁，在停留點由于用戶的細微移動和定位系統(tǒng)的誤差也會導致較大的方向變化)，進而可以理解用戶的行為。不完整的輪廓會造成曾經(jīng)到達地點(例如：銀行)、停留點(例如：高速公路繳費站、堵車地點)的丟失，不能反映用戶在停留區(qū)域(例如：公園)的詳細的行走路線。沒有這些細節(jié)，就無法清楚地了解用戶的行為，就會造成軌跡語義的丟失。

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

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

(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軌跡

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

定義2軌跡壓縮

給定軌跡T={P1，P2，…，Pn-1，Pn}，軌跡壓縮就是要尋找一系列以時間為順序的定位點的集合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中的定位點Pi對應于T′的歐氏距離誤差可表示為Pi與Pi的估計點P′i之間的距離。如果T′中包含Pi，則P′i=Pi。否則，P′i為Pi與直線predT′(Pi)succT′(Pi)的垂點，predT′(Pi) 與succT′(Pi)分別表示T′中離Pi最近的前驅(qū)和后繼。

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

圖2　歐式距離誤差

定義5方向誤差

給定原始軌跡T及壓縮后的軌跡T′，軌跡T中Pi點對應于T′的方向誤差可表示為HeadingChange(h1，h2)，其中h1為Pi點的方向，h2為T′中的定位點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個定位點P1及第3個定位點P3之間定義一個窗口，其中P1被稱之為錨點Pa，P3被稱之為浮動點Pf。執(zhí)行如下步驟：

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

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

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

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

圖3　本文算法的壓縮軌跡

2.2　算法偽代碼

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

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

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

表2　doCheckInWindow算法Tab.2　doCheckInWindow algorithm

3　算法評估

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

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

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

(5)

(6)

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

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

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

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

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

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

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

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

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

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

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

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

圖8在相同壓縮率的條件下，就平均方向誤差進行了比較。從圖中可以看出，對于軌跡1及軌跡3，本文算法的平均方向誤差與DP算法的基本一致，誤差較小。對于軌跡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ù)壓縮算法，使用歐氏距離閾值和角度閾值，在逐步開放窗口的過程中進行軌跡壓縮。通過設置歐氏距離閾值和角度閾值，該算法有效地控制了軌跡的輪廓，確保算法不丟失拐點，解決了軌跡壓縮中輪廓丟失的問題。該算法可以在實時接收定位點的過程中進行軌跡壓縮，故具有支持在線應用的優(yōu)勢。真實數(shù)據(jù)集下的實驗結(jié)果表明，在相同歐氏距離閾值的情況下，本文提出的算法具有輪廓保持方面的優(yōu)勢。在相同壓縮率的情況下，也有著不錯的表現(xiàn)。

參考文獻:

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

[2] 袁晶.大規(guī)模軌跡數(shù)據(jù)的檢索、挖掘和應用[D].合肥:中國科學技術(shù)大學,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.