李想+章登義

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

關(guān)鍵詞：移動(dòng)對(duì)象數(shù)據(jù)庫(kù)；軌跡；化簡(jiǎn)；回溯；線性預(yù)測(cè)；時(shí)態(tài)距離

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

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

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

1 相關(guān)工作

在線化簡(jiǎn)的含義是在通過(guò)移動(dòng)設(shè)備不斷獲取移動(dòng)對(duì)象的軌跡點(diǎn)時(shí)對(duì)移動(dòng)端累積的軌跡進(jìn)行化簡(jiǎn)，旨在減少軌跡點(diǎn)從移動(dòng)設(shè)備傳輸?shù)椒?wù)器過(guò)程中的通訊代價(jià)，同時(shí)降低存儲(chǔ)軌跡的代價(jià).目前，已有的研究中，移動(dòng)對(duì)象軌跡在線化簡(jiǎn)方法是根據(jù)其是否需要累積部分歷史軌跡來(lái)對(duì)后續(xù)的軌跡點(diǎn)進(jìn)行化簡(jiǎn)，化簡(jiǎn)方法可分為部分在線化簡(jiǎn)和完全在線化簡(jiǎn).

1.1 部分在線化簡(jiǎn)

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

1.2 完全在線化簡(jiǎn)

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

2 回溯化簡(jiǎn)

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

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

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

證畢.

上述化簡(jiǎn)過(guò)程中的距離度量方法定義如下：

定義2 時(shí)態(tài)距離. 在二維空間中，給定原始軌跡S上的任意子軌跡段{si，si+1，…，si+l}，其時(shí)態(tài)映射化簡(jiǎn)軌跡段為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到化簡(jiǎn)軌跡段ujuj+1的時(shí)態(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}在化簡(jiǎn)軌跡U上的時(shí)態(tài)映射軌跡段為ujuj+1，如圖2所示原始軌跡點(diǎn)si，si+1，…，si+l在軌跡段ujuj+1上的時(shí)態(tài)插值點(diǎn)分別為uj，s′i，s′i+1，…，s′i+l，uj+1，由式（2）得到原始軌跡段{si，si+1，…，si+l}的化簡(jiǎn)誤差之和為∑i+la=idistEuclidean（sa，s′a），根據(jù)定積分的幾何意義，當(dāng)Δt趨近于零時(shí)，原始軌跡段{si，si+1，…，si+l}的化簡(jiǎn)誤差之和近似為直線ujuj+1與曲線sisi+1…si+l∧圍成的幾何圖形的面積.

由引理1可知，對(duì)于任意一段原始軌跡，若其對(duì)應(yīng)化簡(jiǎn)軌跡的軌跡點(diǎn)越多，則該段原始軌跡的化簡(jiǎn)誤差越小.

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

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

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

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

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

3 優(yōu)化策略

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

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

由于移動(dòng)對(duì)象的運(yùn)動(dòng)具有慣性，而化簡(jiǎn)軌跡序列的更新反映了移動(dòng)對(duì)象的運(yùn)動(dòng)方向發(fā)生了顯著變化，因此我們通過(guò)MOD服務(wù)器接收到的化簡(jiǎn)點(diǎn)（包括后來(lái)被替換掉的）對(duì)速度矢量進(jìn)行預(yù)測(cè).

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

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個(gè)向量到第2個(gè)向量的變化方向是否與第2個(gè)向量到第3個(gè)向量的變化方向是否同時(shí)向下或向上，若為肯定，則如圖3（a）和（b）所示，此時(shí)軌跡呈現(xiàn)上揚(yáng)趨勢(shì)或下降趨勢(shì)，預(yù)測(cè)速度的方向?yàn)椋?/p>

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

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

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

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）

預(yù)測(cè)速度的大小為ui-1和ui之間的平均速率.

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

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

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

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

算法1. Opt+算法.

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

輸出：化簡(jiǎn)結(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 {//逆序訪問(wèn)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. }

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

4.1 化簡(jiǎn)率提升驗(yàn)證實(shí)驗(yàn)

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

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

4.2 化簡(jiǎn)時(shí)間性能提升驗(yàn)證實(shí)驗(yàn)

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

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

5 結(jié) 論

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

參考文獻(xiàn)

[1] 吳乙萬(wàn)， 黃智. 基于動(dòng)態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J]. 湖南大學(xué)學(xué)報(bào)：自然科學(xué)版， 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ù)、應(yīng)用與技術(shù)現(xiàn)狀[J]. 通信學(xué)報(bào)， 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] 王欣然， 楊智應(yīng). 基于最小邊界扇形的移動(dòng)對(duì)象軌跡實(shí)時(shí)化簡(jiǎn)算法[J]. 計(jì)算機(jī)應(yīng)用， 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]王欣然， 楊智應(yīng). 基于PLAZA的移動(dòng)對(duì)象 軌跡實(shí)時(shí)化簡(jiǎn)方法[J]. 計(jì)算機(jī)應(yīng)用研究， 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)東， 等. 基于自適應(yīng)安全區(qū)域的軌跡實(shí)時(shí)化簡(jiǎn)方法[J]. 計(jì)算機(jī)學(xué)報(bào)， 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.