基于回溯的移動(dòng)對(duì)象時(shí)序軌跡在線化簡(jiǎn)方法*

李想，章登義

(武漢大學(xué) 計(jì)算機(jī)學(xué)院,湖北 武漢 430072)

基于回溯的移動(dòng)對(duì)象時(shí)序軌跡在線化簡(jiǎn)方法*

李想?，章登義

(武漢大學(xué) 計(jì)算機(jī)學(xué)院,湖北 武漢 430072)

針對(duì)從移動(dòng)端采集到的移動(dòng)對(duì)象原始軌跡序列的化簡(jiǎn)，定義了一種回溯化簡(jiǎn)框架，通過線性預(yù)測(cè)來控制化簡(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è)向量，通過向量計(jì)算出預(yù)測(cè)速度方向，旨在縮小預(yù)測(cè)方向與未來真實(shí)速度方向的差異；然后利用點(diǎn)集合存儲(chǔ)有向無環(huán)圖中必需訪問邊來降低最優(yōu)線化簡(jiǎn)算法的時(shí)間復(fù)雜度.第1組實(shí)驗(yàn)表明，相對(duì)于直接使用最近兩個(gè)位置點(diǎn)計(jì)算速度方向，抖動(dòng)較為劇烈的原始軌跡在新的預(yù)測(cè)速度方向下的化簡(jiǎn)率更高，說明預(yù)測(cè)速度方向比切線速度方向更接近移動(dòng)對(duì)象的未來運(yùn)動(dòng)方向;第2組實(shí)驗(yàn)表明，優(yōu)化后離線化簡(jiǎn)算法的時(shí)間性能有所提高，說明減少邊的訪問量確實(shí)能夠降低算法的時(shí)間開銷.

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

如今GPS設(shè)備的普及使得基于位置的服務(wù)(Location Based Services，LBS)市場(chǎng)迅速增長，催生了大量的基于位置的應(yīng)用.例如在車輛導(dǎo)航系統(tǒng)中，新的路線規(guī)劃服務(wù)需要根據(jù)環(huán)境、車輛運(yùn)行狀態(tài)和道路交通規(guī)則[1]，綜合考慮多個(gè)行車成本(時(shí)間、距離、油耗等)，通過收集和分析車輛的歷史軌跡得到駕駛員的行車偏好，然后為其定制個(gè)性化的行車路線[2]. 而“未來1小時(shí)路況預(yù)測(cè)系統(tǒng)”將高速公路通行狀況的歷史數(shù)據(jù)、實(shí)時(shí)數(shù)據(jù)與路網(wǎng)狀況結(jié)合，預(yù)測(cè)未來一小時(shí)內(nèi)高速公路的擁堵狀況.其次在商業(yè)動(dòng)線設(shè)計(jì)中，通過分析大多數(shù)顧客在大型超市或者購物中心內(nèi)的行進(jìn)軌跡，找到不同類型顧客的興趣點(diǎn)，對(duì)不同商品的擺放區(qū)域或不同商鋪的位置進(jìn)行精心設(shè)計(jì)，讓顧客在商業(yè)體內(nèi)部停留時(shí)間更久，在購物過程中盡可能經(jīng)過更多有效區(qū)域，提升銷售額.上述應(yīng)用都需要使用大量的車輛、人的時(shí)序軌跡數(shù)據(jù)，但是，目前在使用軌跡數(shù)據(jù)中存在著三大問題，第一，通過網(wǎng)絡(luò)傳輸大量的原始軌跡數(shù)據(jù)的代價(jià)十分高昂；第二，由于軌跡數(shù)據(jù)的低價(jià)值密度和存儲(chǔ)設(shè)備限制，數(shù)據(jù)庫無法保存全部軌跡數(shù)據(jù)[3]；第三，不斷增長的軌跡數(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è)折線近似過程，首先由獲取到的移動(dòng)對(duì)象的軌跡點(diǎn)之間的連線構(gòu)成時(shí)空折線來表達(dá)移動(dòng)對(duì)象的原始軌跡，然后找到一條新的軌跡使其包含的原始軌跡盡量少點(diǎn)且盡可能接近原始軌跡，這一類方法的壓縮率高，但是時(shí)間復(fù)雜度高，不適用于實(shí)時(shí)化簡(jiǎn).一些研究者提出基于推算定位的化簡(jiǎn)方法，這一類方法需要根據(jù)現(xiàn)有的軌跡對(duì)移動(dòng)對(duì)象未來的運(yùn)動(dòng)速度矢量進(jìn)行估計(jì)，實(shí)際是對(duì)原始軌跡進(jìn)行分段離線化簡(jiǎn)的過程，速度矢量估計(jì)的精確度直接影響到化簡(jiǎn)的質(zhì)量，離線化簡(jiǎn)的效率直接影響到化簡(jiǎn)的時(shí)效性.另一些研究者提出了基于區(qū)域過濾的方法，該算法不同于用一條折線來近似原始軌跡的方法，通過參考運(yùn)動(dòng)速度、方向和時(shí)間構(gòu)建安全區(qū)域來對(duì)原始軌跡點(diǎn)進(jìn)行過濾，安全區(qū)域的構(gòu)建代價(jià)高.

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

1 相關(guān)工作

在線化簡(jiǎn)的含義是在通過移動(dòng)設(shè)備不斷獲取移動(dòng)對(duì)象的軌跡點(diǎn)時(shí)對(duì)移動(dòng)端累積的軌跡進(jìn)行化簡(jiǎn)，旨在減少軌跡點(diǎn)從移動(dòng)設(shè)備傳輸?shù)椒?wù)器過程中的通訊代價(jià)，同時(shí)降低存儲(chǔ)軌跡的代價(jià).目前，已有的研究中，移動(dòng)對(duì)象軌跡在線化簡(jiǎn)方法是根據(jù)其是否需要累積部分歷史軌跡來對(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ì)無數(shù)個(gè)軌跡段的離線化簡(jiǎn).第1類為基于推算定位[4]方法，該類方法是根據(jù)當(dāng)前軌跡點(diǎn)和預(yù)測(cè)速度來估計(jì)下一個(gè)軌跡點(diǎn)，當(dāng)下一個(gè)軌跡點(diǎn)的實(shí)際位置與估計(jì)位置的距離超過化簡(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è)部分，通過預(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)的軌跡能夠保證在較長一段時(shí)間內(nèi)移動(dòng)對(duì)象的預(yù)測(cè)位置與實(shí)際位置的距離不超過化簡(jiǎn)精度閾值，但是對(duì)于抖動(dòng)劇烈的軌跡，該方法得到的速度矢量與移動(dòng)對(duì)象未來運(yùn)動(dòng)方向的差距較大，使得化簡(jiǎn)過程中頻繁觸發(fā)離線化簡(jiǎn)，化簡(jiǎn)率降低.另一類是基于區(qū)域過濾方法，國內(nèi)的一些研究者利用最小邊界扇形[9-10]來近似簡(jiǎn)化移動(dòng)對(duì)象的原始軌跡，在角度和距離兩個(gè)層面上對(duì)簡(jiǎn)化誤差進(jìn)行控制，另一些研究者[11]通過引入速率和偏離閾值，構(gòu)造分別適應(yīng)于局部和總體速度的安全區(qū)域，實(shí)現(xiàn)軌跡簡(jiǎn)化.對(duì)于移動(dòng)對(duì)象的運(yùn)動(dòng)速率和方向波動(dòng)頻繁的情況，基于區(qū)域過濾的方法需要頻繁重新構(gòu)建安全區(qū)域，計(jì)算代價(jià)較高.

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

完全在線化簡(jiǎn)與部分在線化簡(jiǎn)的區(qū)別在于前者在化簡(jiǎn)過程不回溯歷史軌跡點(diǎn)，只判斷新到來的軌跡點(diǎn)是否是化簡(jiǎn)點(diǎ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)開始維護(hù)一個(gè)窗口，不斷將新的原始軌跡點(diǎn)放入窗口中，直到原始軌跡到起始點(diǎn)與窗口中某一點(diǎn)連線的同步歐氏距離超過閾值，此時(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ì)列過濾軌跡點(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)的到來導(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)過程放置在客戶端，客戶端上的位置傳感器不斷感知新的位置，同時(shí)客戶端通過化簡(jiǎn)框架對(duì)獲取到的軌跡數(shù)據(jù)進(jìn)行回溯化簡(jiǎn)，化簡(jiǎn)產(chǎn)生的化簡(jiǎn)點(diǎn)即時(shí)發(fā)送給移動(dòng)對(duì)象數(shù)據(jù)庫(Moving Object Databases，MOD)，保證MOD接收的化簡(jiǎn)軌跡經(jīng)過插值后與原始軌跡的誤差小于給定的化簡(jiǎn)閾值.化簡(jiǎn)框架的符號(hào)說明如表1所示.

表1 符號(hào)說明

我們對(duì)回溯化簡(jiǎn)有如下定義：

定義1 回溯化簡(jiǎn). 在當(dāng)前時(shí)刻tc，原始軌跡序列為S:{s1,s2,…,si}，MOD維護(hù)的化簡(jiǎn)軌跡序列U={u1,u2,…,uj}?{s1,s2,…,si}，保留一部分歷史軌跡序列Shistory:{si-l,…,si-1,si}，時(shí)刻tc+k×Δt(k∈N+)，位置服務(wù)器接收到新的位置點(diǎn)si+k，一旦si+k與線性預(yù)測(cè)位置點(diǎn)的距離大于ε或者Shistory的元素個(gè)數(shù)達(dá)到最大值，則對(duì)歷史軌跡序列Shistory:{si-l,…,si-1,si,si+1,…,si+k}則進(jìn)行離線化簡(jiǎn).化簡(jiǎn)結(jié)果為ΔU，然后刪除MOD維護(hù)的時(shí)間范圍在[si-l.t,si.t)內(nèi)的化簡(jiǎn)軌跡點(diǎn)后得到集合U′，新的化簡(jiǎn)軌跡序列為U=U′∪ΔU.

圖1 回溯化簡(jiǎn)示例

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

證畢.

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

(1)

(2)

圖2 原始軌跡映射到化簡(jiǎn)軌跡示意圖

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

(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)組成的向量的夾角余弦值的平均值：

(4)

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ā)生了顯著變化，因此我們通過MOD服務(wù)器接收到的化簡(jiǎn)點(diǎn)(包括后來被替換掉的)對(duì)速度矢量進(jìn)行預(yù)測(cè).

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

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

(6)

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

(7)

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

情形Ⅱ 當(dāng)前離線化簡(jiǎn)后新產(chǎn)生的化簡(jiǎn)點(diǎn)數(shù)量小于2時(shí)，說明移動(dòng)對(duì)象在歷史軌跡序列覆蓋的時(shí)間范圍內(nèi)運(yùn)動(dòng)方向的變化不顯著，此時(shí)通過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 速度向量方向變化情況示意圖

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

本文針對(duì)推測(cè)定位中離線化簡(jiǎn)通常采用的最優(yōu)化線化簡(jiǎn)算法的實(shí)現(xiàn)過程進(jìn)行優(yōu)化，原算法的化簡(jiǎn)過程分為3步：第1步，根據(jù)回溯的歷史軌跡點(diǎn)構(gòu)建有向無環(huán)圖;第2步，求有向無環(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)建有向無環(huán)圖時(shí)需要構(gòu)建所有可能存在的邊，從而導(dǎo)致時(shí)間復(fù)雜度高的特點(diǎn)，僅僅構(gòu)建廣度優(yōu)先搜索的過程中需要訪問到的邊，減少時(shí)態(tài)距離的計(jì)算量，且通過集合來代替鄰接表或鄰接矩陣存儲(chǔ)邊.具體做法是在廣度優(yōu)先搜索過程中將所有軌跡點(diǎn)進(jìn)行分類，分類的原則是按照它們到起始點(diǎn)的距離進(jìn)行判斷，距離為0的點(diǎn)是起始點(diǎn)s1本身，因此將s1單獨(dú)作為一個(gè)集合，然后訪問到s1距離為1的所有點(diǎn)，把它們放入一個(gè)集合.再訪問到這個(gè)集合中的每一個(gè)點(diǎn)距離為1且沒有被放入任何一個(gè)集合的點(diǎn)，將這些點(diǎn)放入到一個(gè)新的集合中，然后對(duì)新的集合進(jìn)行上述相同的處理，直到終點(diǎn)sm放入某個(gè)集合中.第二是每當(dāng)訪問到一個(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≠)DO{

3.Hc←;

4.FOREACHsiinHc-1andEACHsjinBDO{//逆序訪問Hc-1和U中的元素

5. cond=TRUE;

6.FOREACHskinShistoryWHEREsi.t

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.FOREACHsqinShistoryWHEREsj.t

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. }

改進(jìn)后的Opt+算法在采取了兩種優(yōu)化措施之后，避免了構(gòu)建一些不會(huì)訪問到的邊的計(jì)算和一些頂點(diǎn)的訪問，若化簡(jiǎn)結(jié)果中僅有起始點(diǎn)s1和終止點(diǎn)sm，則此時(shí)能夠達(dá)到最好的時(shí)間復(fù)雜度O(m).由于Opt+算法通過集合關(guān)系來表示在有向無環(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?CoreTMi7-3630QM2.4GHzCPU, 16G內(nèi)存和750GB硬盤；軟件環(huán)境為Win7操作系統(tǒng)和VS2008編譯系統(tǒng).實(shí)驗(yàn)數(shù)據(jù)通過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～50m變化過程中，分別使用切線速度和本文的優(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～40m時(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ù)，說明本文的優(yōu)化速度比切線速度更接近對(duì)象未來的速度.圖4(c)給出了與4(a)相應(yīng)條件下的化簡(jiǎn)誤差，可以看出在保證化簡(jiǎn)誤差小于化簡(jiǎn)精度閾值的前提下，本文的優(yōu)化速度下的化簡(jiǎn)誤差與切線速度下相比十分接近.

化簡(jiǎn)精度閾值/m

化簡(jiǎn)精度閾值/m

化簡(jiǎn)精度閾值/m

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

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

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

化簡(jiǎn)精度閾值/m

化簡(jiǎn)精度閾值/m

化簡(jiǎn)精度閾值/m

5 結(jié) 論

本文在基于推測(cè)定位的時(shí)序軌跡回溯化簡(jiǎn)框架下，分別對(duì)化簡(jiǎn)過程中的速度預(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)問題，而目前一部分移動(dòng)對(duì)象的軌跡數(shù)據(jù)都是在道路網(wǎng)絡(luò)下產(chǎn)生的，本研究沒有考慮路網(wǎng)約束對(duì)化簡(jiǎn)的影響；二是化簡(jiǎn)沒有將軌跡點(diǎn)的空間維度與時(shí)間維度相結(jié)合，仍然只是對(duì)空間維度進(jìn)行化簡(jiǎn)，而把時(shí)間維僅作為空間維的一個(gè)附加維度.因此未來的工作將重點(diǎn)考察道路網(wǎng)絡(luò)約束下的軌跡特征，著眼于基于道路網(wǎng)絡(luò)的移動(dòng)對(duì)象時(shí)序軌跡的時(shí)空化簡(jiǎn)方法研究.

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

WUYiwan,HUANGZhi.Dynamicvirtualobstaclebasedlocalpathplanningforintelligentvehicle[J].JournalofHunanUniversity:NaturalSciences, 2013, 40(1): 33-37.(InChinese)

[2]DAIJ,YANGB,GUOC,etal. 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,etal. Trajectory big data: data, applications and techniques[J]. Journal on Communications, 2015, 36(12):97-105.(In Chinese)

[4] BAIER P, DüRR 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,DüRR 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,etal. 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,etal. 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,etal. 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.

Backtracking Based Method for On-line Trajectory Simplification of Moving Objects

LI Xiang?, ZHANG Dengyi

(School of Computer, Wuhan University, Wuhan 430072, China)

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.

moving object database; trajectories; simplification; backtracking; linear prediction; temporal distance

1674-2974(2017)02-0149-08

10.16339/j.cnki.hdxbzkb.2017.02.021

2016-05-20

國家自然科學(xué)基金資助項(xiàng)目(60903035, 41001296),National Natural Science Foundation of China(60903035, 41001296);國家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)資助項(xiàng)目(2013AA12A301),National High Technology Research and Development Program of China (863 Program) (2013AA12A301)

李想(1987-)，男，湖北黃岡人，武漢大學(xué)博士研究生

?通訊聯(lián)系人，E-mail: lixiang1987@whu.edu.cn

TP301

A