一種基于廣度優(yōu)先搜索的移動對象軌跡簡化算法

楊 彪，楊智應

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

一種基于廣度優(yōu)先搜索的移動對象軌跡簡化算法

楊 彪，楊智應

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

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

移動對象；離線軌跡簡化；速度閾值

0 引言

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

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

1 相關工作

在最近的研究中，文獻[2]中提出了基于方向的軌跡簡化算法，通過給定的角度閾值來簡化軌跡，使求出的簡化軌跡最大角度值不大于給定的角度閾值。在文獻[2]的基礎上，文獻[3]中提出了簡化軌跡的數量在不大于給定值的情況下，使得簡化軌跡與原始軌跡方向閾值最小的簡化算法；文獻[4]提出了基于方向的實時簡化算法。

另一類軌跡簡化算法以垂線距離或同步歐氏距離為誤差度量指標。文獻[5]中提出的DP算法以垂線距離作為誤差度量指標來簡化軌跡。Keogh等人基于垂線距離提出了實時壓縮算法。文獻[6]中對DP算法作了改進，提出了以同步歐式距離為誤差度量指標的軌跡簡化算法。

此外，還有其他的軌跡簡化算法，文獻[7]利用語義信息來替代軌跡數據，進行軌跡簡化。文獻[8]提出了基于速度的軌跡簡化算法。本文的軌跡簡化思想與文獻[8]有很大的不同，文獻[8]的軌跡簡化核心度量指標是關于軌跡段平均速度的比值，而本文軌跡核心度量指標為軌跡段的最大速度差值。

2 移動軌跡簡化問題描述及算法

2.1一些定義及記號

定義1(位置點或軌跡點):位置點用p表示,p是一個三元組，組內對應屬性分別代表該點的經度、緯度、時間，p=(x,y,t)。

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

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

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

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

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

原始軌跡T中位置點的個數用|T|表示，則T中軌跡段的個數為|T|-1或n-1。簡化軌跡Tsim中位置點的個數用|Tsim|表示，則Tsim中軌跡段的個數為|Tsim|-1或m-1。

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

圖1 原始軌跡和簡化軌跡

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

2.2基于速度的軌跡簡化問題

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

本文采用了軌跡段的最大速度差值而不是平均速度差值，因為最大速度差值更能突顯出軌跡速度變化的劇烈程度。為了解決上述描述的問題，本文提出了以下多個算法來解決該問題：(1)基于廣度優(yōu)先搜索的簡化算法(v-bfs算法)；(2)v-bfs算法的優(yōu)化算法(v-bfs-imp算法)，并通過大量的實驗來說明v-bfs算法在權衡軌跡的簡潔性和精確性方面有較大優(yōu)勢。

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

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

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

(3)找到圖的簡化軌跡。根據第(2)步的路徑關系找到一條簡化軌跡。

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

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

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

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

根據引理2，可以證明相同的軌跡經過v-bfs算法和v-bfs-imp算法得到相同的簡化軌跡，只是v-bfs-imp算法時間復雜度降低了一個數量級,空間復雜度還是O(V+E)。

3 實驗比較

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

3.1度量指標

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

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

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

3.2不同軌跡數據對軌跡壓縮率的影響

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

圖2 不同速度閾值的簡化軌跡軌跡點與原始軌跡軌跡點的比值

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

3.3算法比較(v-bfsvsDPvsSP)

用本文提出的v-bfs算法來和DP算法、SP算法比較，用以上3個指標來度量算法在權衡軌跡簡潔度和精確度上的優(yōu)劣性。

采用DP算法[5]來作為比較對象，因為該離線算法是純粹的基于位置信息來簡化軌跡，同時也是非常著名的算法。采用SP算法[2]作為比較對象，因為該離線算法同樣是純粹地基于方向信息來簡化軌跡。算法的時間復雜度和空間復雜度比較如表1。

表1 算法時間復雜度與空間復雜度

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

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

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

圖3 L(H)值比較

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

圖4 L(D|H)值比較

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

圖5 MDL值比較

總的來說，v-bfs算法在簡潔度上比SP算法和DP算法差，在精確度上比SP算法和DP算法要好，在權衡簡潔性和精確性上比SP算法和DP算法也要好。

4 結論

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

[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ōu)先搜索的移動對象軌跡簡化算法J.微型機與應用，2017,36(21)：74-77.

2017-04-12)

楊彪(1992-),男,碩士,主要研究方向:移動對象數據庫。

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