李想+章登義

摘 要：針對從移動端采集到的移動對象原始軌跡序列的化簡，定義了一種回溯化簡框架，通過線性預測來控制化簡的時機，對當前時刻到回溯的歷史軌跡的起始時刻之間的原始軌跡進行離線化簡，化簡采用時態(tài)距離作為誤差度量方法.在回溯化簡框架下，首先利用每次離線化簡后新產(chǎn)生的化簡點構(gòu)建多個向量，通過向量計算出預測速度方向，旨在縮小預測方向與未來真實速度方向的差異；然后利用點集合存儲有向無環(huán)圖中必需訪問邊來降低最優(yōu)線化簡算法的時間復雜度.第1組實驗表明，相對于直接使用最近兩個位置點計算速度方向，抖動較為劇烈的原始軌跡在新的預測速度方向下的化簡率更高，說明預測速度方向比切線速度方向更接近移動對象的未來運動方向；第2組實驗表明，優(yōu)化后離線化簡算法的時間性能有所提高，說明減少邊的訪問量確實能夠降低算法的時間開銷.

關(guān)鍵詞：移動對象數(shù)據(jù)庫；軌跡；化簡；回溯；線性預測；時態(tài)距離

中圖分類號：TP301 文獻標志碼：A

Backtracking Based Method for On-line

Trajectory Simplification of Moving Objects

LI Xiang， ZHANG Dengyi

（School of Computer， Wuhan University， Wuhan 430072， China）

Abstract：For the simplification for the original trajectory sequence of the moving object collected from the mobile devices， this paper defined a kind of backtracking based simplification framework， which used the linear prediction and length of simplification queue to dominate the time of simplification， and simplified the original trajectory sequence between the present moment and starting time of a retrospective historical trajectory adopting the method of temporal distance as the error metric. In the backtracking based simplification framework， this paper first utilized the new reduced points to construct several vectors and predicted the velocity， which could narrow the gap between the prediction and actual velocity in the future. This paper then utilized the point sets to store the edges in the directed acyclic graph needed in the access to reduce time complexity of the algorithm. The first experiment shows that the reduction rate using the optimal velocity prediction is greater than that of the original velocity prediction with the high fluctuant trajectory data. It suggests that the predicted velocity is closer to the actual velocity in the future moving direction than that in the tangent direction. The second experiment shows that the time performances of the optimized simplification algorithm are improved. This study shows that the reduction of the visits of the edges can decrease the time overhead of the algorithm.

Key words：moving object database； trajectories； simplification； backtracking； linear prediction； temporal distance

如今GPS設備的普及使得基于位置的服務（Location Based Services，LBS）市場迅速增長，催生了大量的基于位置的應用.例如在車輛導航系統(tǒng)中，新的路線規(guī)劃服務需要根據(jù)環(huán)境、車輛運行狀態(tài)和道路交通規(guī)則[1]，綜合考慮多個行車成本（時間、距離、油耗等），通過收集和分析車輛的歷史軌跡得到駕駛員的行車偏好，然后為其定制個性化的行車路線[2]. 而“未來1小時路況預測系統(tǒng)”將高速公路通行狀況的歷史數(shù)據(jù)、實時數(shù)據(jù)與路網(wǎng)狀況結(jié)合，預測未來一小時內(nèi)高速公路的擁堵狀況.其次在商業(yè)動線設計中，通過分析大多數(shù)顧客在大型超市或者購物中心內(nèi)的行進軌跡，找到不同類型顧客的興趣點，對不同商品的擺放區(qū)域或不同商鋪的位置進行精心設計，讓顧客在商業(yè)體內(nèi)部停留時間更久，在購物過程中盡可能經(jīng)過更多有效區(qū)域，提升銷售額.上述應用都需要使用大量的車輛、人的時序軌跡數(shù)據(jù)，但是，目前在使用軌跡數(shù)據(jù)中存在著三大問題，第一，通過網(wǎng)絡傳輸大量的原始軌跡數(shù)據(jù)的代價十分高昂；第二，由于軌跡數(shù)據(jù)的低價值密度和存儲設備限制，數(shù)據(jù)庫無法保存全部軌跡數(shù)據(jù)[3]；第三，不斷增長的軌跡數(shù)據(jù)規(guī)模使得在其中發(fā)現(xiàn)有用的模式變得更加困難，因此對原始軌跡進行化簡和壓縮具有重要的研究價值和實際意義.

一些研究引入壓縮和線化簡算法對移動對象的歷史軌跡進行化簡，實際是一個折線近似過程，首先由獲取到的移動對象的軌跡點之間的連線構(gòu)成時空折線來表達移動對象的原始軌跡，然后找到一條新的軌跡使其包含的原始軌跡盡量少點且盡可能接近原始軌跡，這一類方法的壓縮率高，但是時間復雜度高，不適用于實時化簡.一些研究者提出基于推算定位的化簡方法，這一類方法需要根據(jù)現(xiàn)有的軌跡對移動對象未來的運動速度矢量進行估計，實際是對原始軌跡進行分段離線化簡的過程，速度矢量估計的精確度直接影響到化簡的質(zhì)量，離線化簡的效率直接影響到化簡的時效性.另一些研究者提出了基于區(qū)域過濾的方法，該算法不同于用一條折線來近似原始軌跡的方法，通過參考運動速度、方向和時間構(gòu)建安全區(qū)域來對原始軌跡點進行過濾，安全區(qū)域的構(gòu)建代價高.

本文的研究基于推測定位通過回溯部分歷史軌跡點來預測移動對象在未來一段時間內(nèi)的運動趨勢，在實際位置點與預測位置點的距離超過化簡精度閾值時，對當前時刻到回溯的歷史軌跡的起始時刻之間的軌跡進行化簡.針對上述化簡過程，本文對兩個步驟進行了優(yōu)化，首先針對整體抖動較為劇烈的軌跡，改進速度矢量的預測方法，減少離線化簡的次數(shù)，提升軌跡的化簡率；然后對離線化簡算法的實現(xiàn)過程進行優(yōu)化，提升化簡的時間性能.

1 相關(guān)工作

在線化簡的含義是在通過移動設備不斷獲取移動對象的軌跡點時對移動端累積的軌跡進行化簡，旨在減少軌跡點從移動設備傳輸?shù)椒掌鬟^程中的通訊代價，同時降低存儲軌跡的代價.目前，已有的研究中，移動對象軌跡在線化簡方法是根據(jù)其是否需要累積部分歷史軌跡來對后續(xù)的軌跡點進行化簡，化簡方法可分為部分在線化簡和完全在線化簡.

1.1 部分在線化簡

部分在線化簡方法的核心思想在于不斷累積和拋棄原始軌跡點，將化簡轉(zhuǎn)化為對無數(shù)個軌跡段的離線化簡.第1類為基于推算定位[4]方法，該類方法是根據(jù)當前軌跡點和預測速度來估計下一個軌跡點，當下一個軌跡點的實際位置與估計位置的距離超過化簡誤差時，將該軌跡點放入化簡軌跡，具有代表性的有線性推測定位（Linear Dead Reckoning）、連接保持推測定位（Connection-Preserving Dead Reckoning）和GRTS （Generic Remote Trajectory Simplification） [5].后者在前兩者的基礎(chǔ)之上將軌跡分為穩(wěn)定部分、可變部分以及預測部分，通過預測部分推算預測軌跡點的位置，一旦預測軌跡點與實際軌跡點的距離大于化簡誤差，則對可變部分和預測部分的原始軌跡點進行離線化簡，采用的離線化簡方法主要是最優(yōu)線化簡方法Opt（optimal line simplification）[6]、段啟發(fā)式方法Sec（segment heuristic）[7]以及道格拉斯普客算法DP（Douglas-Peucker）[8].基于推測定位方法的關(guān)鍵在于預測速度矢量的精度，其采用的速度矢量預測方法是直接使用預測起始點和其之前一點的向量進行減法運算后除以兩點的時間間隔得到，即近似軌跡在預測起始點的切線方向.該方法對于較為平穩(wěn)的軌跡能夠保證在較長一段時間內(nèi)移動對象的預測位置與實際位置的距離不超過化簡精度閾值，但是對于抖動劇烈的軌跡，該方法得到的速度矢量與移動對象未來運動方向的差距較大，使得化簡過程中頻繁觸發(fā)離線化簡，化簡率降低.另一類是基于區(qū)域過濾方法，國內(nèi)的一些研究者利用最小邊界扇形[9-10]來近似簡化移動對象的原始軌跡，在角度和距離兩個層面上對簡化誤差進行控制，另一些研究者[11]通過引入速率和偏離閾值，構(gòu)造分別適應于局部和總體速度的安全區(qū)域，實現(xiàn)軌跡簡化.對于移動對象的運動速率和方向波動頻繁的情況，基于區(qū)域過濾的方法需要頻繁重新構(gòu)建安全區(qū)域，計算代價較高.

1.2 完全在線化簡

完全在線化簡與部分在線化簡的區(qū)別在于前者在化簡過程不回溯歷史軌跡點，只判斷新到來的軌跡點是否是化簡點.最常見的在線化簡方法為均勻采樣法（Uniform Sampling），即每間隔相同數(shù)量的原始軌跡點采樣一個點放入化簡軌跡，該方法簡便快速，但是化簡誤差大.另一類經(jīng)典的在線化簡方法為OPW-TR[7]，其核心思想是首先以原始軌跡的第一個點為起始點開始維護一個窗口，不斷將新的原始軌跡點放入窗口中，直到原始軌跡到起始點與窗口中某一點連線的同步歐氏距離超過閾值，此時將該點或該點之前的點放入化簡軌跡中，并且以該點或該點之前的點為起始點重新維護窗口，該方法每接收到一個新的軌跡點后需要進行多次距離計算，時間復雜度較高.為了更好地保留軌跡的位置、時間和速度信息，有研究者提出了一種在線化簡方法SQUISH[12-13]，使用優(yōu)先隊列過濾軌跡點實現(xiàn)化簡，對于優(yōu)先隊列中除起始點外的任意一點，其優(yōu)先級為該點到與該點相鄰的前后兩點之間連線的同步歐氏距離，一旦新進的點的到來導致優(yōu)先隊列溢出，則將優(yōu)先級最低的點從隊列中移除，并調(diào)整該點相鄰兩點的優(yōu)先級.該方法與推測定位和道格拉斯普克算法相比在壓縮率較小的情況下，化簡誤差較小，該化簡方法的優(yōu)先級計算方法不適用于高壓縮率的化簡.

2 回溯化簡

本文以連續(xù)獲取移動對象的傳感軌跡為背景，將軌跡化簡過程放置在客戶端，客戶端上的位置傳感器不斷感知新的位置，同時客戶端通過化簡框架對獲取到的軌跡數(shù)據(jù)進行回溯化簡，化簡產(chǎn)生的化簡點即時發(fā)送給移動對象數(shù)據(jù)庫（Moving Object Databases，MOD），保證MOD接收的化簡軌跡經(jīng)過插值后與原始軌跡的誤差小于給定的化簡閾值.化簡框架的符號說明如表1所示.

定理1 當回溯的歷史軌跡序列長度達到閾值而觸發(fā)離線化簡的次數(shù)忽略不計時，回溯化簡過程中根據(jù)歷史軌跡序列推算的預測速度方向越接近移動對象在未來的實際運動速度方向，則軌跡的化簡率越高.

證明 以圖1為例，假定Shistory的長度閾值為100，若s8.t時刻的另一個預測速度v′p比vp更接近移動對象的未來速度，使得|s8.p-（u′3.p+v′p × （s8.t-u′3.t））|<ε，則服務器將繼續(xù)接收新的位置點，假定直到s13.t時刻，|s13.p-（u′3.p+v'p×（s13.t-u′3.t））|>ε觸發(fā)了離線化簡，對軌跡段{s4，s5，…，s13}而言，離線化簡次數(shù)至少比原來減少了一次，擴展至整條軌跡，更接近實際速度方向的預測速度使得總體的離線化簡次數(shù)減少，化簡結(jié)果點數(shù)量減少，從而使得總體的化簡率提高.

證畢.

上述化簡過程中的距離度量方法定義如下：

定義2 時態(tài)距離. 在二維空間中，給定原始軌跡S上的任意子軌跡段{si，si+1，…，si+l}，其時態(tài)映射化簡軌跡段為ujuj+1（uj.t≤si.t

s′a.p=（sa.t-uj.t）uj+1.t-uj.t（uj+1.p-uj.p）+uj.p（1）

sa到化簡軌跡段ujuj+1的時態(tài)距離為sa到s′a的歐氏距離：

disttemporal（sa，ujuj+1）=distEuclidean（sa，s′a）=

sa.p-（sa.t-uj.t）uj+1.t-uj.t（uj+1.p-uj.p）-uj.p（2）

引理1 原始軌跡S上任意子軌跡段{si，si+1，…，si+l}在化簡軌跡U上的時態(tài)映射軌跡段為ujuj+1，如圖2所示原始軌跡點si，si+1，…，si+l在軌跡段ujuj+1上的時態(tài)插值點分別為uj，s′i，s′i+1，…，s′i+l，uj+1，由式（2）得到原始軌跡段{si，si+1，…，si+l}的化簡誤差之和為∑i+la=idistEuclidean（sa，s′a），根據(jù)定積分的幾何意義，當Δt趨近于零時，原始軌跡段{si，si+1，…，si+l}的化簡誤差之和近似為直線ujuj+1與曲線sisi+1…si+l∧圍成的幾何圖形的面積.

由引理1可知，對于任意一段原始軌跡，若其對應化簡軌跡的軌跡點越多，則該段原始軌跡的化簡誤差越小.

定義3 平均化簡誤差. 在二維空間中，原始軌跡序列為S：{s1，s2，…，sn}，化簡軌跡序列U={u1，u2，…，ul}{s1，s2，…，sn}且U是按照化簡精度閾值ε對S進行化簡得到的，根據(jù)定義1，對于S上任意一軌跡點s1的時態(tài)距離為distEuclidean（si，s′i），其中s′i為si在化簡軌跡段ujuj+1上的時態(tài)插值點，這個時態(tài)距離又稱作軌跡點si的化簡誤差，那么原始軌跡序列S的平均化簡誤差為：

1n∑ni=1distEuclidean（si，s′i）=1n∑ni=1si.p-s′i.p（3）

定義4 軌跡抖動系數(shù)J. 原始軌跡序列S：{s1，s2，…，sn}中任意連續(xù)三點si-1，si，si+1，組成的兩個向量si-1si和sisi+1的夾角余弦值為si的抖動系數(shù)，描述軌跡在si的抖動程度，則軌跡的抖動系數(shù)J為軌跡中所有連續(xù)三點組成的向量的夾角余弦值的平均值：

J=1n-2∑n-1i=2cos 〈si-1si，sisi+1〉 （4）

本文將軌跡抖動系數(shù)J=2/2作為軌跡抖動劇烈與否的分界線，抖動系數(shù)小于2/2的軌跡為抖動軌跡，即上述兩個向量的角度差為45°～180°，抖動系數(shù)大于2/2的軌跡為平穩(wěn)軌跡，即上述兩個向量的角度差為0～45°，抖動系數(shù)越小則抖動越劇烈.

3 優(yōu)化策略

本節(jié)將詳細描述針對回溯化簡框架下的在線化簡算法的兩個優(yōu)化策略.

3.1 速度預測模型的優(yōu)化

由于移動對象的運動具有慣性，而化簡軌跡序列的更新反映了移動對象的運動方向發(fā)生了顯著變化，因此我們通過MOD服務器接收到的化簡點（包括后來被替換掉的）對速度矢量進行預測.

情形I 當前離線化簡后新產(chǎn)生的化簡點數(shù)量大于等于2時，說明移動對象在最近的幾個化簡點所覆蓋的時間區(qū)域內(nèi)發(fā)生較為顯著的運動方向變化，此時通過MOD服務器最近接收到的4個化簡點ui-3，ui-2，ui-1，ui構(gòu)建如下3個向量：

v1=ui-2.p-ui-3.pui-2.t-ui-3.t，v2=ui-1.p-ui-2.pui-1.t-ui-2.t，

v3=ui.p-ui-1.pui.t-ui-1.t（5）

判斷第1個向量到第2個向量的變化方向是否與第2個向量到第3個向量的變化方向是否同時向下或向上，若為肯定，則如圖3（a）和（b）所示，此時軌跡呈現(xiàn)上揚趨勢或下降趨勢，預測速度的方向為：

vp=2v3-v2=2ui.p-ui-1.pui.t-ui-1.t-

ui-1.p-ui-2.pui-1.t-ui-2.t （6）

預測速度的大小為ui-1和ui之間的平均速率，若不是，則如圖3（c）和（d）所示，此時軌跡呈現(xiàn)波浪變化，預測速度的方向為：

vp=12（v2+v3）=12（ui-1.p-ui-2.pui-1.t-ui-2.t+

ui.p-ui-1.pui.t-ui-1.t）（7）

預測速度的大小為ui-1和ui之間的平均速率.

情形Ⅱ 當前離線化簡后新產(chǎn)生的化簡點數(shù)量小于2時，說明移動對象在歷史軌跡序列覆蓋的時間范圍內(nèi)運動方向的變化不顯著，此時通過MOD最近接收到的兩個化簡點ui-1和ui所覆蓋的時間區(qū)域[ui-1.t，ui.t]內(nèi)的原始軌跡序列的三等分點和ui-1，ui構(gòu)建與情形I類似的3個向量，然后采用與情形I相同的方式計算預測速度方向，預測速度的大小為ui-1和ui之間的平均速率.

3.2 離線化簡算法的優(yōu)化

本文針對推測定位中離線化簡通常采用的最優(yōu)化線化簡算法的實現(xiàn)過程進行優(yōu)化，原算法的化簡過程分為3步：第1步，根據(jù)回溯的歷史軌跡點構(gòu)建有向無環(huán)圖；第2步，求有向無環(huán)圖中起點s1到終點sm的最短路徑；第3步，返回最短路徑為化簡結(jié)果.

本文在兩個步驟中采用優(yōu)化措施降低算法的時間復雜度的同時降低空間復雜度，第一是針對最優(yōu)化線化簡算法在第1步中構(gòu)建有向無環(huán)圖時需要構(gòu)建所有可能存在的邊，從而導致時間復雜度高的特點，僅僅構(gòu)建廣度優(yōu)先搜索的過程中需要訪問到的邊，減少時態(tài)距離的計算量，且通過集合來代替鄰接表或鄰接矩陣存儲邊.具體做法是在廣度優(yōu)先搜索過程中將所有軌跡點進行分類，分類的原則是按照它們到起始點的距離進行判斷，距離為0的點是起始點s1本身，因此將s1單獨作為一個集合，然后訪問到s1距離為1的所有點，把它們放入一個集合.再訪問到這個集合中的每一個點距離為1且沒有被放入任何一個集合的點，將這些點放入到一個新的集合中，然后對新的集合進行上述相同的處理，直到終點sm放入某個集合中.第二是每當訪問到一個與當前集合Hc-1中的點之間存在邊的點，就直接判斷其與終點sm之間是否有邊，若存在邊，則最短路徑已經(jīng)得到，避免掃描一部分不相關(guān)的點.具體算法如下：

算法1. Opt+算法.

輸入：回溯的歷史軌跡序列Shistory：{s1，s2，…，sm-1，sm}，化簡精度閾值ε

輸出：化簡結(jié)果u

1.H0={s1}； B={s2，…，sm-1，sm}； c=1；

2. WHILE （B≠

SymbolFC@） DO {

3. Hc←

SymbolFC@；

4. FOR EACH si in Hc-1 and EACH sj in B DO {//逆序訪問Hc-1和U中的元素

5. cond=TRUE；

6. FOR EACH sk in Shistory WHERE si.t

7. IF （disttemporal（sk，sisj）≤ε） THEN

8. cond=cond & TRUE；

9. ELSE

10. cond=cond &FALSE；

11. BREAK；

12. }

13. IF （cond） THEN //si到sj的邊存在

14. IF （sj==sm） THEN

15. RETURN； //已找到最短路徑

16. con=TRUE；

17. FOR EACH sq in Shistory WHERE sj.t

18. IF （disttemporal（sq，sjsm）≤ε） THEN

19. con=con & TRUE；

20. ELSE

21. con=con & FALSE；BREAK；

22. }

23.IF （con） THEN //sj到sm的邊存在

24. RETURN； //已找到最短路徑

25.B←B＼{sj}；

26.Hc←Hc∪{sj}；

27. }

28. c=c+1；

29. }

該算法維護若干集合，其中Hc（c=0，1，2，…）保存有向無環(huán)圖中起始點到其路徑已知的點，c表示從起始點到Hc中的點的路徑長度，而集合B用來保存有向無環(huán)圖中起始點到其路徑未知的點.因為s1作為最短路徑的起點，行1首先用軌跡序列Shistory中的第一個軌跡點s1初始化H0，B初始化為軌跡序列Shistory中的除第一點外的其他軌跡點，接著逆序訪問Hc-1和B中的軌跡點；行5-10通過計算Shistory中si到sj之間的每一個軌跡點sk到線段sisj的時態(tài)距離disttemporal（sk，sisj），并且判斷此距離是否小于等于化簡精度閾值ε；如行13，如果Shistory中si到sj之間所有的軌跡點的disttemporal（sk，sisj）小于化簡精度閾值ε，即有向無環(huán)圖中邊sisj存在，則在誤差范圍內(nèi)可以用線段sisj近似Shistory中si到sj的軌跡；在此基礎(chǔ)上行14判斷sj是否是Shistory最后一個軌跡點sm，若sj等于sm，則最短路徑已經(jīng)找到；最短路徑存入u中，算法結(jié)束，否則繼續(xù)執(zhí)行下一步；行16-24對于當前的軌跡點sj，判斷其與Shistory的終點sm是否存在邊，若存在則最短路徑已經(jīng)找到，算法結(jié)束，否則繼續(xù)執(zhí)行下一步，于是將sj從B中刪除，添加至Hc，繼續(xù)逆序訪問Hc-1和B中的軌跡點，直至Hc-1和B中的軌跡點都訪問完畢；行28將c自加1，重復4-27行的過程，直至集合B為空（行2）.

Opt算法的步驟1在構(gòu)建有向無環(huán)圖中，頂點個數(shù)為回溯的歷史軌跡點數(shù)量m，考慮圖中任意兩個頂點si和sj，若si.t

改進后的Opt+算法在采取了兩種優(yōu)化措施之后，避免了構(gòu)建一些不會訪問到的邊的計算和一些頂點的訪問，若化簡結(jié)果中僅有起始點s1和終止點sm，則此時能夠達到最好的時間復雜度O（m）.由于Opt+算法通過集合關(guān)系來表示在有向無環(huán)圖中頂點之間邊的關(guān)系且只需要保存每個頂點，因此其空間復雜度為O（m）.

4 實驗結(jié)果

為了驗證優(yōu)化策略對軌跡化簡性能的提升，本文在回溯化簡框架下的在線化簡方法的基礎(chǔ)上用C++實現(xiàn)了上述優(yōu)化策略.實驗的硬件平臺為：Intel CoreTM i7-3630QM 2.4 GHz CPU， 16 G內(nèi)存和750 GB硬盤；軟件環(huán)境為Win7操作系統(tǒng)和VS2008編譯系統(tǒng).實驗數(shù)據(jù)通過OpenStreetMap（OpenStreetMap. http：//www.openstreetmap.org/）網(wǎng)站中的真實軌跡數(shù)據(jù)集提取獲得.在實驗中，化簡率定義為原始軌跡的點數(shù)量與化簡軌跡的點數(shù)量之比，化簡誤差定義為化簡軌跡經(jīng)由原始軌跡參考插值后的時態(tài)距離的平均值.

4.1 化簡率提升驗證實驗

實驗選取抖動系數(shù)分別為J=0.4，J=0.5，J=0.6，J=0.7和J=0.707等5類抖動程度依次減弱的軌跡，在化簡精度閾值為10～50 m變化過程中，分別使用切線速度和本文的優(yōu)化速度時的化簡率.

圖4（a）給出了不同化簡精度閾值下5類抖動軌跡的化簡率比較圖，可以看出在抖動系數(shù)較小，即軌跡抖動非常劇烈時，本文的優(yōu)化速度下在化簡精度為20～40 m時與切線速度下相比具有一定的優(yōu)勢，但是隨著抖動系數(shù)的增大，這種優(yōu)勢逐漸縮小至零.圖4（b）給出了不同化簡精度閾值下5類抖動軌跡的離線化簡次數(shù)情況，可以看出軌跡抖動系數(shù)較小時，本文的優(yōu)化速度下的離線化簡次數(shù)通常小于切線速度下的離線化簡次數(shù)，說明本文的優(yōu)化速度比切線速度更接近對象未來的速度.圖4（c）給出了與4（a）相應條件下的化簡誤差，可以看出在保證化簡誤差小于化簡精度閾值的前提下，本文的優(yōu)化速度下的化簡誤差與切線速度下相比十分接近.

4.2 化簡時間性能提升驗證實驗

實驗選取軌跡點數(shù)量為100萬的軌跡，在化簡精度閾值由10～100 m的變化過程中，比較回溯化簡框架下Opt+算法與Opt[6]算法的化簡時間性能，同時將DP[8]算法和Sec[7]算法作為參照.

圖5（a）給出了100萬軌跡下化簡精度閾值變化過程中化簡所消耗時間的情況.4種算法中，Opt算法的化簡時間隨著化簡精度閾值的變大而顯著增長，Opt+算法的化簡時間隨著化簡精度閾值的變大而略有減少，最終趨于平穩(wěn)，DP算法受化簡精度閾值變化的影響較小，Sec算法的化簡時間隨著化簡精度閾值的變大而略有增長.化簡精度閾值超過10 m時，Opt+算法的化簡時間性能優(yōu)于Opt算法.在化簡精度閾值為20～100 m時，Opt+算法所消耗的時間約為Opt算法的10%～70%，這是由于化簡精度閾值的增大導致化簡隊列平均長度變大，如圖5（b）所示，使得Opt算法中構(gòu)建有向無環(huán)圖所消耗的時間顯著增加，同時總體的化簡次數(shù)減少，如圖5（c）所示，使得變長段Opt+算法消耗的時間降低到一定范圍.

5 結(jié) 論

本文在基于推測定位的時序軌跡回溯化簡框架下，分別對化簡過程中的速度預測模型和離線化簡算法進行優(yōu)化.實驗結(jié)果表明，對于抖動劇烈的軌跡化簡，優(yōu)化后的速度下與原有切線速度下相比在化簡率上有一定的優(yōu)勢，而優(yōu)化后的離線化簡算法與原方法相比在時間性能上有較大的提升.當前的工作主要有兩點不足，一是仍然在歐氏空間中討論移動對象時序軌跡的化簡問題，而目前一部分移動對象的軌跡數(shù)據(jù)都是在道路網(wǎng)絡下產(chǎn)生的，本研究沒有考慮路網(wǎng)約束對化簡的影響；二是化簡沒有將軌跡點的空間維度與時間維度相結(jié)合，仍然只是對空間維度進行化簡，而把時間維僅作為空間維的一個附加維度.因此未來的工作將重點考察道路網(wǎng)絡約束下的軌跡特征，著眼于基于道路網(wǎng)絡的移動對象時序軌跡的時空化簡方法研究.

參考文獻

[1] 吳乙萬， 黃智. 基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J]. 湖南大學學報：自然科學版， 2013，40（1）：33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University： Natural Sciences， 2013， 40（1）： 33-37.（In Chinese）

[2] DAI J， YANG B， GUO C， et al. Personalized route recommendation using big trajectory data[C]// International Conference on Data Engineering. Seoul： IEEE Computer Society， 2015：543-554.

[3] 許佳捷， 鄭凱， 池明旻，等. 軌跡大數(shù)據(jù)：數(shù)據(jù)、應用與技術(shù)現(xiàn)狀[J]. 通信學報， 2015， 36（12）：97-105.

XU Jiajie， ZHENG Kai， CHI Mingmin， et al. Trajectory big data： data， applications and techniques[J]. Journal on Communications， 2015， 36（12）：97-105.（In Chinese）

[4] BAIER P， DRR F，ROTHERMEL K. Opportunistic position update protocols for mobile devices[C]// Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing. New York： ACM SIGMOD Record， 2013：787-796.

[5] LANGE R，DRR F，ROTHERMEL K. Efficient real-time trajectory tracking[J]. The International Journal on Very Large Data Bases， 2011， 20（5）：671-694.

[6] KATSIKOULI P， SARKAR R， GAO J. Persistence based online signal and trajectory simplification for mobile devices[C]// Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York： ACM SIGMOD Record， 2014：371-380.

[7] MERATNIA N，ROLF A. Spatio-temporal compression techniques for moving point objects[C]// Proceedings of the International Conference on Extending Database Technology. Greece： Berlin Springer， 2004： 765-782.

[8] DOUGLAS D H， PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica： The International Journal for Geographic Information and Geovisualization， 1973， 10（2）：112-122.

[9] 王欣然， 楊智應. 基于最小邊界扇形的移動對象軌跡實時化簡算法[J]. 計算機應用， 2014， 34（8）： 2409-2414.

WANG Xinran，YANG Zhiying. Real-time trajectory simplification algorithm of moving objects based on minimum bounding sector[J]. Journal of Computer Applications， 2014， 34（8）： 2409-2414.（In Chinese）

[10]王欣然， 楊智應. 基于PLAZA的移動對象 軌跡實時化簡方法[J]. 計算機應用研究， 2014， 31（5）： 1315-1319.

WANG Xinran，YANG Zhiying.Method of real-time trajectory simplification of moving object based on PLAZA[J]. Application Research of Computer， 2014， 31（5）：1315-1319.（In Chinese）

[11]李文海， 程志光， 文衛(wèi)東， 等. 基于自適應安全區(qū)域的軌跡實時化簡方法[J]. 計算機學報， 2014， 37（9）：1923-1935.

LI Wenhai， CHENG Zhiguang， WEN Weidong， et al. A safe-region based adaptive method for real-time trajectory simplification[J]. Chinese Journal of Computer， 2014， 37（9）：1923-1935.（In Chinese）

[12]MUCKELL J， HWANG J H， PATIL V， et al. SQUISH： an online approach for GPS trajectory compression[C]// Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications. Washington DC： ACM SIGMOD Record， 2011， 13：1-8.

[13]MUCKELL J， OLSEN P W， HWANG J H， et al. Compression of trajectory data： a comprehensive evaluation and new approach[J]. An International Journal on Advances of Computer Science for Geographic Information Systems， 2013， 18（3）：435-460.