楊 彪，楊智應(yīng)

(上海海事大學(xué) 信息工程學(xué)院，上海 201306)

一種基于廣度優(yōu)先搜索的移動(dòng)對(duì)象軌跡簡(jiǎn)化算法

楊 彪，楊智應(yīng)

(上海海事大學(xué) 信息工程學(xué)院，上海201306)

移動(dòng)對(duì)象產(chǎn)生的軌跡數(shù)據(jù)在許多實(shí)際應(yīng)用中起著至關(guān)重要的作用。目前對(duì)移動(dòng)對(duì)象軌跡簡(jiǎn)化方法的研究或多或少依賴軌跡的幾何特性。這些方法沒(méi)有突出移動(dòng)對(duì)象的速度這一重要特征。文章介紹了基于速度的移動(dòng)對(duì)象軌跡簡(jiǎn)化新方法，提出了基于廣度優(yōu)先搜索算法的多項(xiàng)式時(shí)間算法及其優(yōu)化算法,通過(guò)大量實(shí)驗(yàn)證明所提出算法在權(quán)衡軌跡的簡(jiǎn)潔性和精確性上比DP算法、SP算法有較大優(yōu)勢(shì)。

移動(dòng)對(duì)象；離線軌跡簡(jiǎn)化；速度閾值

0 引言

隨著GPS嵌入式設(shè)備的激增(例如智能電話和出租車)，移動(dòng)對(duì)象軌跡數(shù)據(jù)變得無(wú)處不在。在過(guò)去十多年中，人們對(duì)移動(dòng)對(duì)象數(shù)據(jù)庫(kù)(MOD)已進(jìn)行了廣泛的研究[1]。移動(dòng)軌跡數(shù)據(jù)通常通過(guò)周期性地收集移動(dòng)物體的位置而獲得。

然而現(xiàn)在提出的軌跡簡(jiǎn)化算法要么去掉過(guò)多的軌跡特征點(diǎn)，使簡(jiǎn)化后的軌跡與原始軌跡偏差較大，精確度不高;要么保留了過(guò)多的軌跡點(diǎn)，使存儲(chǔ)成本上升，簡(jiǎn)潔度不夠。為了解決這個(gè)問(wèn)題，本文提出了v-bfs算法，在權(quán)衡軌跡的簡(jiǎn)潔性和精確性上有較大的優(yōu)勢(shì)。

1 相關(guān)工作

在最近的研究中，文獻(xiàn)[2]中提出了基于方向的軌跡簡(jiǎn)化算法，通過(guò)給定的角度閾值來(lái)簡(jiǎn)化軌跡，使求出的簡(jiǎn)化軌跡最大角度值不大于給定的角度閾值。在文獻(xiàn)[2]的基礎(chǔ)上，文獻(xiàn)[3]中提出了簡(jiǎn)化軌跡的數(shù)量在不大于給定值的情況下，使得簡(jiǎn)化軌跡與原始軌跡方向閾值最小的簡(jiǎn)化算法；文獻(xiàn)[4]提出了基于方向的實(shí)時(shí)簡(jiǎn)化算法。

另一類軌跡簡(jiǎn)化算法以垂線距離或同步歐氏距離為誤差度量指標(biāo)。文獻(xiàn)[5]中提出的DP算法以垂線距離作為誤差度量指標(biāo)來(lái)簡(jiǎn)化軌跡。Keogh等人基于垂線距離提出了實(shí)時(shí)壓縮算法。文獻(xiàn)[6]中對(duì)DP算法作了改進(jìn)，提出了以同步歐式距離為誤差度量指標(biāo)的軌跡簡(jiǎn)化算法。

此外，還有其他的軌跡簡(jiǎn)化算法，文獻(xiàn)[7]利用語(yǔ)義信息來(lái)替代軌跡數(shù)據(jù)，進(jìn)行軌跡簡(jiǎn)化。文獻(xiàn)[8]提出了基于速度的軌跡簡(jiǎn)化算法。本文的軌跡簡(jiǎn)化思想與文獻(xiàn)[8]有很大的不同，文獻(xiàn)[8]的軌跡簡(jiǎn)化核心度量指標(biāo)是關(guān)于軌跡段平均速度的比值，而本文軌跡核心度量指標(biāo)為軌跡段的最大速度差值。

2 移動(dòng)軌跡簡(jiǎn)化問(wèn)題描述及算法

2.1一些定義及記號(hào)

定義1(位置點(diǎn)或軌跡點(diǎn)):位置點(diǎn)用p表示,p是一個(gè)三元組，組內(nèi)對(duì)應(yīng)屬性分別代表該點(diǎn)的經(jīng)度、緯度、時(shí)間，p=(x,y,t)。

定義2(原始軌跡):原始軌跡T是一些有序位置點(diǎn)的集合。

T=(p1,…,pi,…,pn)(i∈[1,n]),其中：pi=(xi,yi,ti)并且t1

定義3(原始軌跡的子軌跡):原始軌跡T的子軌跡用T[i,j]表示，也是一些有序位置點(diǎn)的集合，T[i,j]=(pi,pi+1,…,pj)(1≤i≤j≤n)。

定義4(簡(jiǎn)化軌跡)：簡(jiǎn)化軌跡Tsim是原始軌跡T去掉一些位置點(diǎn)的有序集合。

Tsim=(ps1,ps2,…,psm)(1≤s1

原始軌跡T中位置點(diǎn)的個(gè)數(shù)用|T|表示，則T中軌跡段的個(gè)數(shù)為|T|-1或n-1。簡(jiǎn)化軌跡Tsim中位置點(diǎn)的個(gè)數(shù)用|Tsim|表示，則Tsim中軌跡段的個(gè)數(shù)為|Tsim|-1或m-1。

如圖1所示，假定原始軌跡T=(p1,p2,…,p8)，簡(jiǎn)化后的軌跡Tsim=(p1,p4,p6,p8)，原始軌跡T的軌跡段用實(shí)心黑線表示，簡(jiǎn)化軌跡Tsim的軌跡段用實(shí)心虛線表示；此時(shí)|T|=8，|Tsim|=4。

圖1 原始軌跡和簡(jiǎn)化軌跡

定義9(簡(jiǎn)化軌跡Tsim的最大速度差值)：簡(jiǎn)化軌跡Tsim中，對(duì)任意位置點(diǎn)psk(k∈[1,m)),簡(jiǎn)化軌跡Tsim的最大速度差值用ε(Tsim)表示。

2.2基于速度的軌跡簡(jiǎn)化問(wèn)題

問(wèn)題描述：T是原始軌跡，Tsim是T的簡(jiǎn)化軌跡，εv是一個(gè)預(yù)先給定的速度閾值。如果T有多條簡(jiǎn)化軌跡滿足ε(Tsim)≤εv,如何找到一條簡(jiǎn)化軌跡Tsim，使簡(jiǎn)化軌跡Tsim的軌跡點(diǎn)最少？

本文采用了軌跡段的最大速度差值而不是平均速度差值，因?yàn)樽畲笏俣炔钪蹈芡伙@出軌跡速度變化的劇烈程度。為了解決上述描述的問(wèn)題，本文提出了以下多個(gè)算法來(lái)解決該問(wèn)題：(1)基于廣度優(yōu)先搜索的簡(jiǎn)化算法(v-bfs算法)；(2)v-bfs算法的優(yōu)化算法(v-bfs-imp算法)，并通過(guò)大量的實(shí)驗(yàn)來(lái)說(shuō)明v-bfs算法在權(quán)衡軌跡的簡(jiǎn)潔性和精確性方面有較大優(yōu)勢(shì)。

2.3基于廣度優(yōu)先算法的簡(jiǎn)化算法(v-bfs算法)

該算法運(yùn)用圖的廣度優(yōu)先搜索算法(BFS)來(lái)求解簡(jiǎn)化軌跡大小|Tsim|最小值問(wèn)題，稱該算法為v-bfs算法，構(gòu)造步驟如下:

(2)尋找最短路徑。在圖Gεv(V,E)中用廣度優(yōu)先搜索算法(BFS)尋找一條從p1到pn的最短路徑。

(3)找到圖的簡(jiǎn)化軌跡。根據(jù)第(2)步的路徑關(guān)系找到一條簡(jiǎn)化軌跡。

為了進(jìn)一步降低該算法的時(shí)間和空間復(fù)雜度，提出該算法的優(yōu)化算法。

2.4v-bfs算法的優(yōu)化算法(v-bfs-imp算法)

優(yōu)化算法的目的是為了降低算法的時(shí)間復(fù)雜度，在提出優(yōu)化算法之前先介紹幾個(gè)概念。

定義11(子軌跡的速度變化范圍)：在子軌跡T[i,j]中，fvr(T[i,j]|εv)為子軌跡中各個(gè)軌跡段的速度變化范圍的交集，子軌跡T[i,j]的速度變化范圍用fvr(T[i,j]|εv)表示。

根據(jù)引理2，可以證明相同的軌跡經(jīng)過(guò)v-bfs算法和v-bfs-imp算法得到相同的簡(jiǎn)化軌跡，只是v-bfs-imp算法時(shí)間復(fù)雜度降低了一個(gè)數(shù)量級(jí),空間復(fù)雜度還是O(V+E)。

3 實(shí)驗(yàn)比較

為了分析與評(píng)估算法的性能，實(shí)驗(yàn)選取筆記本電腦作為硬件測(cè)試平臺(tái)，具體配置如下:處理器為英特爾Pentium(奔騰)P6200@2.13 GHz 雙核，內(nèi)存為6 GB;實(shí)驗(yàn)環(huán)境為 Windows 7 操作系統(tǒng)和 Eclipse開發(fā)系統(tǒng),Java語(yǔ)言實(shí)現(xiàn)。實(shí)驗(yàn)數(shù)據(jù)從項(xiàng)目INFATI得到[9]，INFATI 的位置數(shù)據(jù)由20個(gè)有效的GPS 數(shù)據(jù)集構(gòu)成。

3.1度量指標(biāo)

軌跡簡(jiǎn)化應(yīng)該具有以下兩個(gè)期望的性質(zhì)：簡(jiǎn)潔性和精確性。簡(jiǎn)潔性意味著簡(jiǎn)化后的軌跡數(shù)量盡可能少。精確性意味著簡(jiǎn)化軌跡應(yīng)該與原始軌跡差異盡可能小。然而既要高精度又要高簡(jiǎn)潔度是不可能，精確性與簡(jiǎn)潔性之間是相互矛盾的，只能在兩者之間找平衡點(diǎn)。文獻(xiàn)[10]用L(H)表示簡(jiǎn)化軌跡與原軌跡之間簡(jiǎn)潔度的偏差，用L(D|H)表示簡(jiǎn)化軌跡與原軌跡之間精確度的偏差。MDL表示簡(jiǎn)化軌跡與原始軌跡總偏差，根據(jù)文獻(xiàn)[10]中公式(1)、(3)、(6)、(7)，分別羅列出這三個(gè)變量的定義：

L(D|H)=L(D|H)_position+L(D|H)_direction

MDL=L(H)+L(D|H)

3.2不同軌跡數(shù)據(jù)對(duì)軌跡壓縮率的影響

選取4條不同的軌跡，每條軌跡選取300個(gè)連續(xù)的GPS軌跡點(diǎn)，采用相同的v-bfs算法進(jìn)行軌跡簡(jiǎn)化，當(dāng)速度閾值εv從0.5 m/s逐漸增大到4.5 m/s時(shí)，簡(jiǎn)化軌跡的軌跡點(diǎn)與原始軌跡的軌跡點(diǎn)的比值變化如圖2所示。

圖2 不同速度閾值的簡(jiǎn)化軌跡軌跡點(diǎn)與原始軌跡軌跡點(diǎn)的比值

從圖2中可以看出隨著εv逐漸增大，簡(jiǎn)化后的軌跡數(shù)逐漸減小;其中任意兩條軌跡，在相同的速度閾值下,軌跡簡(jiǎn)化率各不相同,簡(jiǎn)化率的差值也在不斷變化。

3.3算法比較(v-bfsvsDPvsSP)

用本文提出的v-bfs算法來(lái)和DP算法、SP算法比較，用以上3個(gè)指標(biāo)來(lái)度量算法在權(quán)衡軌跡簡(jiǎn)潔度和精確度上的優(yōu)劣性。

采用DP算法[5]來(lái)作為比較對(duì)象，因?yàn)樵撾x線算法是純粹的基于位置信息來(lái)簡(jiǎn)化軌跡，同時(shí)也是非常著名的算法。采用SP算法[2]作為比較對(duì)象，因?yàn)樵撾x線算法同樣是純粹地基于方向信息來(lái)簡(jiǎn)化軌跡。算法的時(shí)間復(fù)雜度和空間復(fù)雜度比較如表1。

表1 算法時(shí)間復(fù)雜度與空間復(fù)雜度

對(duì)每一個(gè)速度閾值εv，用算法v-bfs得到簡(jiǎn)化軌跡Tsim，根據(jù)文獻(xiàn)[2]中公式(2)求出簡(jiǎn)化軌跡Tsim與原始軌跡T的角度偏差，作為SP算法的輸入值。

用相同的簡(jiǎn)化軌跡Tsim求出每個(gè)軌跡段的軌跡點(diǎn)到軌跡兩端點(diǎn)的最大垂線距離，所有軌跡段垂線距離的最大值即為DP算法的輸入值。

在圖3中，v-bfs算法和DP算法的L(H)值隨著εv的增大而逐漸變小,當(dāng)εv等于6.0 m/s時(shí)，L(H)近似相等，然而SP算法L(H)值先變小然后保持不變;表明v-bfs算法在εv較小時(shí)能保證簡(jiǎn)化軌跡與原始估計(jì)的方向偏差；然而εv大于0.5 m/s時(shí)，簡(jiǎn)化軌跡與原始估計(jì)的方向偏差非常大。圖3表明v-bfs算法的簡(jiǎn)潔性均沒(méi)有DP算法和SP算法好。

圖3 L(H)值比較

在圖4中,三種算法的L(D|H)的值均隨著εv的增大先增大后保持不變，且L(D|H)在保持不變前，v-bfs算法的軌跡一直處于另外兩條軌跡的下方，說(shuō)明v-bfs算法比DP算法和SP算法保留了更多原始軌跡的信息。表明經(jīng)過(guò)v-bfs算法簡(jiǎn)化后的軌跡比SP算法和DP算法的精確度更高。

圖4 L(D|H)值比較

在圖5中，當(dāng)速度閾值εv小于1.5 m/s時(shí)，v-bfs算法在權(quán)衡簡(jiǎn)潔度和精確度上都要比DP算法和SP算法好;速度閾值εv大于1.5 m/s時(shí),經(jīng)過(guò)三種算法后的簡(jiǎn)化軌跡與原始軌跡的總偏差大體上相差不大，并且隨著εv的逐漸增大，這三種算法效果一樣。

圖5 MDL值比較

總的來(lái)說(shuō)，v-bfs算法在簡(jiǎn)潔度上比SP算法和DP算法差，在精確度上比SP算法和DP算法要好，在權(quán)衡簡(jiǎn)潔性和精確性上比SP算法和DP算法也要好。

4 結(jié)論

本文提出了基于速度的軌跡簡(jiǎn)化新思路，并且提出了基于廣度優(yōu)先搜索的軌跡簡(jiǎn)化算法及其優(yōu)化算法，通過(guò)實(shí)驗(yàn)比較得出，v-bfs算法在權(quán)衡簡(jiǎn)潔性和精確性上比SP算法和DP算法有較大優(yōu)勢(shì)。將來(lái)為了進(jìn)一步縮短軌跡壓縮時(shí)間，將考慮如何實(shí)現(xiàn)基于速度的軌跡壓縮實(shí)時(shí)簡(jiǎn)化算法。

[1] PATEL D，SHENG C，HSU W,et al.Incorporating duration information for trajectory classification[C].IEEE International Conference on Data Engineering.IEEE，2012:1132-1143.

[2] CHENG L,WONG C W,JAGADISH H V.Direction-preserving trajectory simplification[J].Proceedings of the Vldb Endowment，2013，6(10):949-960.

[3] CHENG L，WONG C W，JAGADISH H V.Trajectory simplification: on minimizing the directionbased error[J].Proceedings of the Vldb Endowment，2014，8(1):49-60.

[4] DENG Z，HAN W，WANG L，et al.An efficient online direction-preserving compression approach for trajectory streaming data[J].Future Generation Computer Systems，2017，68:150-162.

[5] 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 & Geovisualization，1973，10(2):112-122.

[6] MERATNIA N，BY R A D.Spatiotemporal compression techniques for moving point objects[C].Advances in Database Technology-EDBT 2004,International Conference on Extending Database Technology,Heraklion,Crete，Greece，2004:765-782.

[7] RICHTER K F，SCHMID F，LAUBE P.Semantic trajectory compression: representing urban movement in a nutshell[J].Journal of Spatial Information Science，2012，4(4):3-30.

[8] YING J C，SU J H.On velocity-preserving trajectory simplification[C].Intelligent Information and Database Systems，2016: 241-250.

[9] JENSEN C S，LAHRMANN H，PAKALNIS S，et al.The infati data[J].Computer Science，2004，29(3):449-473.

[10] LEE J G，HAN J，WHANG K Y.Trajectory clustering: a partition-and-group framework[C].ACM SIGMOD International Conference on Management of Data.ACM，2007:593-604.

A moving object trajectory simplification algorithm based on breadth-priority search

Yang Biao，Yang Zhiying

(School of Information Engineering，Shanghai Maritime University，Shanghai 201306，China)

The trajectory data generated by the moving object plays a vital role in many practical applications.At present，the study of the moving object trajectory simplification method is more or less dependent on the geometric characteristics of the trajectory.These methods do not highlight the important feature of the moving speed of the object.In this paper，we introduced a new method to simplify the trajectory of moving objects based on speed，and proposed a polynomial time algorithm based on breadth-first search algorithm and its optimization algorithm.Through a large number of experiments，we proved that the proposed algorithm has a great advantage over the DP algorithm and the SP algorithm in the simplicity and accuracy of the trade-off trajectory.

moving object; offline trajectory simplification; speed threshold

TP301

A

10.19358/j.issn.1674-7720.2017.21.022

楊彪，楊智應(yīng).一種基于廣度優(yōu)先搜索的移動(dòng)對(duì)象軌跡簡(jiǎn)化算法J.微型機(jī)與應(yīng)用，2017,36(21)：74-77.

2017-04-12)

楊彪(1992-),男,碩士,主要研究方向:移動(dòng)對(duì)象數(shù)據(jù)庫(kù)。

楊智應(yīng)(1964-),男,博士,教授,主要研究方向:算法與復(fù)雜性、移動(dòng)計(jì)算、分布式計(jì)算與軟件工程。