趙庶旭，屈睿濤，劉昌榮

(蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070)

當(dāng)前各類數(shù)據(jù)都處于極其膨脹的狀態(tài)，衍生出眾多的數(shù)據(jù)分析方法，且大都有較為成熟的結(jié)果，而在這些成熟結(jié)果的背后，數(shù)據(jù)劃分作為一個重要步驟，為其做出了很大的貢獻(xiàn)。

很多情況下，車輛的軌跡數(shù)據(jù)都是通過車載GPS裝置采集獲得，導(dǎo)致這些數(shù)據(jù)的空間位置任意分布。因此，要想對這些數(shù)據(jù)進(jìn)行快速準(zhǔn)確的研究，就需要先對數(shù)據(jù)空間進(jìn)行劃分。面對交通軌跡數(shù)據(jù)劃分問題，出發(fā)點大都從其屬性方面進(jìn)行研究，即從加速度、時間、轉(zhuǎn)角、起始位置點、經(jīng)緯度等這些明顯特征點方面入手，并沒有考慮將特征點劃分與空間劃分相結(jié)合。因此，軌跡數(shù)據(jù)劃分效果還存在較大的優(yōu)化空間。

基于特征點的交通軌跡數(shù)據(jù)劃分方法現(xiàn)已有多種，最終可歸為兩大類：軌跡點劃分、軌跡段劃分。而對于交通軌跡數(shù)據(jù)基于空間的劃分方法包括以下幾個：按屏幕像素劃分、按均勻網(wǎng)格劃分、按行政區(qū)域劃分和按照數(shù)據(jù)本身的屬性進(jìn)行劃分[1]。文獻(xiàn)[2—6]主要描述了基于軌跡段的劃分。其中，文獻(xiàn)[2]按照最小描述邏輯對復(fù)雜的軌跡數(shù)據(jù)進(jìn)行劃分，將軌跡劃分為軌跡段的形式，但造成了軌跡局部特征丟失的現(xiàn)象。文獻(xiàn)[4]借鑒文獻(xiàn)[3]提出的拐點檢測算法對文獻(xiàn)[2]進(jìn)行了改進(jìn)，從轉(zhuǎn)角方面入手，對軌跡數(shù)據(jù)進(jìn)行了劃分，將整段軌跡劃分成更小片段來處理，同時也提高了軌跡聚類的精度，但未考慮軌跡數(shù)據(jù)的空間屬性。文獻(xiàn)[5—6]利用軌跡數(shù)據(jù)的位置與幾何特性對軌跡進(jìn)行了切分，考慮了軌跡數(shù)據(jù)分布的空間屬性，但特征點較為單一，劃分效果并不理想。文獻(xiàn)[7—13]主要描述了基于軌跡點的劃分。其中，文獻(xiàn)[7—10]提出了基于起始點到終點位置點的軌跡數(shù)據(jù)分析方法，對城市移動軌跡模式進(jìn)行了研究，用來揭示城市不同區(qū)域間的關(guān)系，考慮了區(qū)域和軌跡數(shù)據(jù)分布的聯(lián)系，提高了數(shù)據(jù)劃分的速度，但劃分點單一，遇到道路情況較為復(fù)雜時，劃分效果不明顯。文獻(xiàn)[11—13]將位置信息、時間信息、速度、加速度特征運用到軌跡數(shù)據(jù)劃分中，把這些特征歸為點來處理，形成簇，然后以可視化的形式展現(xiàn)出來。本文方法與其略有相似，但在特征點的尋找及點群的組建方面要優(yōu)于以上方法。

基于此，本文充分考慮了軌跡數(shù)據(jù)分布的空間任意性，結(jié)合軌跡數(shù)據(jù)的位置關(guān)系，提出基于軌跡數(shù)據(jù)特征點與空間劃分相結(jié)合的劃分方法。將某一時間段內(nèi)的軌跡數(shù)據(jù)與相應(yīng)的道路路網(wǎng)進(jìn)行匹配[14]，然后利用高效的α-Shapes去噪方法進(jìn)行軌跡數(shù)據(jù)去噪，得到多個車輛軌跡關(guān)鍵點。在基于點的劃分方面，除軌跡數(shù)據(jù)原因特征點外，再提取車輛行駛軌跡的其他特征點，與其組成點群。在空間劃分方面，將道路緩沖區(qū)視為軌跡數(shù)據(jù)分布的空間，采用Voronoi方法對軌跡數(shù)據(jù)進(jìn)行劃分。該方法提高了基于軌跡段劃分時因數(shù)據(jù)特征點單一，且未考慮軌跡數(shù)據(jù)的空間屬性而導(dǎo)致效果不明顯的缺陷，改善了空間劃分時，由于信息采樣不足而導(dǎo)致的信息不具代表性問題。將其應(yīng)用于交通擁堵、交通規(guī)劃、出行方式建議等方面，收到了良好的效果。

1 軌跡數(shù)據(jù)預(yù)處理

1.1 道路信息獲取

交通軌跡數(shù)據(jù)維度較高，但是采集的原始的基于GPS的數(shù)據(jù)在一般情況下缺乏道路信息，需要通過一定的處理方法，獲取到原始GPS數(shù)據(jù)中的道路信息。

對于得到的原始數(shù)據(jù)，首先要根據(jù)已有的經(jīng)緯度信息建立緩沖區(qū)，其次將原始數(shù)據(jù)與本文所建立的緩沖區(qū)進(jìn)行相交，得到所在道路的信息。如圖1所示，本文利用淄博市張店區(qū)的魯山大道、魯泰大道和309國道在16：00—17：00時間段內(nèi)的GPS數(shù)據(jù)，建立該路段的緩沖區(qū)后利用地圖匹配算法，把3條道路交匯處(由于交匯區(qū)域采集到的GPS數(shù)據(jù)較豐富，具有代表性)GPS點和路網(wǎng)數(shù)據(jù)匹配，從而得到圖1所示的GPS點在3條道路交匯處的分布結(jié)果，方便了后續(xù)工作的開展。

圖1 GPS點與道路緩沖區(qū)

1.2 數(shù)據(jù)去噪

由于從GPS裝置上獲取到的數(shù)據(jù)存在一定數(shù)量的噪聲，通過地圖匹配后，許多數(shù)據(jù)不一定會落到道路緩沖區(qū)內(nèi)，因此在進(jìn)行研究前要對這些數(shù)據(jù)進(jìn)行去噪，避免造成誤差。本文采用α-Shapes算法對軌跡數(shù)據(jù)進(jìn)行噪聲過濾[15-17]。

車輛在行駛過程中，時常出現(xiàn)變道、轉(zhuǎn)彎、超車等駕駛行為，同時，一些道路樞紐、立交橋、盤旋路及道路交叉口的路況大多為圓形，這些情況就造成車輛行駛路線多為彎曲路線，而α-Shapes算法去噪的原理主要是通過半徑圓的滾動來提取邊緣輪廓，能很好地適應(yīng)以上描述的車輛行駛路線。因此在交通軌跡數(shù)據(jù)分析中，將α-Shapes算法應(yīng)用在道路上的軌跡數(shù)據(jù)噪聲過濾問題上較為合適。

α-Shapes原理：一般情況下，設(shè)有一個離散的點集S，將一個半徑為α的圓在點集外滾動，α取合適的值時，這個圓所圍成的邊界線內(nèi)的數(shù)據(jù)即為去噪后的數(shù)據(jù)，邊界外數(shù)據(jù)為剔除的數(shù)據(jù)(噪聲數(shù)據(jù))。α-Shapes算法運算速度快，具有一定的自適應(yīng)性，通過α值的調(diào)節(jié)可實現(xiàn)一定的過濾功能，可以將數(shù)據(jù)噪聲和部分小目標(biāo)過濾掉。

在軌跡數(shù)據(jù)去噪中，對于邊界的確定，是由GPS點集S和α決定的。對于S，設(shè)其由n個GPS點組成，可以連接成n(n-1)/2條線，筆者在S中任意選取2個點P1、P2，繪制半徑為α的圓，圓心的確定根據(jù)測繪學(xué)中的求交法得到[18]。

令P1和P2的坐標(biāo)分別為(x1,y1)、(x2,y2)，求圓心(x,y)，如下

(1)

對于α的取值，需要通過多次試驗，最終確定一個合適的值。當(dāng)α足夠小時，每一個點就可以大致認(rèn)為是邊界；而α足夠大時，則是S的凸包。筆者對α的取值進(jìn)行了多次試驗，確定對于相對筆直路段，0.33 m較為符合，對于轉(zhuǎn)彎路段及道路交叉口，0.1 m較為理想，如圖2所示。

圖2 α-Shapes算法去噪對比

2 基于軌跡特征劃分的數(shù)據(jù)分析

2.1 軌跡特征點提取

軌跡的特征點包括起點和終點、明顯轉(zhuǎn)彎點和顯著停止點(運動停頓點)等。若軌跡是一條長直線段，則只需獲取其部分特征點。由于以上所述的特征點對于解決本文描述的問題還存在不足，因此，本文提出了較為全面的獲取軌跡特征點的方法，以更好地適應(yīng)軌跡數(shù)據(jù)分布的空間任意性問題。一些軌跡的明顯特征點如圖3所示。

圖3 軌跡明顯特征點

2.1.1 軌跡特征點描述

軌跡T=(xi,yi,ti)，1≤i≤n，n≥2，其中xi和yi為空間坐標(biāo)，ti為時間，則還需提取的軌跡特征如下。

(1) 最小轉(zhuǎn)角點：連續(xù)軌跡段的方向之間的最小角度，如圖4所示。

圖4 軌跡最小轉(zhuǎn)角

(2) 最短停留時間點：在大致相同的位置花費的最短停留時間，被視為重要的停留。

(3) 最短距離點：兩者連續(xù)的點，之間的距離連續(xù)低于其他連續(xù)點之間的距離，這兩個點被視為這條軌跡的最短距離點。

圖5 軌跡最短距離點

(4) 最大距離點：兩者連續(xù)的點，之間的距離連續(xù)大于其他連續(xù)點之間的距離，這兩個點被視為這條軌跡的最大距離點。

2.1.2 算法描述

編程采用Java語言，令C為軌跡特征點的集合，提取軌跡特征點的相關(guān)步驟算法描述如下：

step1 定義C={(x1，y1，t1)}；inti=1。

step2 intj=i+1。

step3 如果j>n，執(zhí)行第九步；

否則結(jié)束。

step4 計算兩點間的空間距離。

step5 判斷兩點間空間距離是否大于最大距離，則令C=C∪{(xj,yj,tj)}，并執(zhí)行第2步，否則結(jié)束。

step6 執(zhí)行k=j+1循環(huán)，并判斷兩點間的空間距離是否大于最小距離，是則執(zhí)行第2步；否則結(jié)束循環(huán)，進(jìn)行第9步。

step7 計算最短停留時間。

step8 計算最小轉(zhuǎn)角。

step9 添加所得點到C集合，令C=C∪{(xj,yj,tj)}。

step10 返回C。

通過該方法，可以得到軌跡特征點，將這些特征點與原有軌跡數(shù)據(jù)特征點相結(jié)合，為后續(xù)的軌跡數(shù)據(jù)空間劃分作輔助。

2.2 Voronoi劃分

2.2.1 軌跡點分類

對得到的軌跡特征點進(jìn)行一個簡單的分類，本文采取的方法是提取點群的質(zhì)心(平均點)，計算點之間的歐氏距離，距離近的點組成點群，質(zhì)心點作為Voronoi圖細(xì)分的生成元。Voronoi圖細(xì)分是指通過添加三角形的方式對一個網(wǎng)絡(luò)的三角形進(jìn)行細(xì)分，這些新添加的三角形可以偏移到一個新的位置。本文利用歐氏距離計算方法對軌跡點進(jìn)行分組

(2)

通過歐氏距離的計算，將距離相近的點分為一組，圖6所示為省級道路與鄉(xiāng)鎮(zhèn)道路上軌跡特征點的分布位置。

圖6 特征點分布

2.2.2 Voronoi劃分定義

Voronoi圖[19-22]是計算幾何領(lǐng)域中非常重要的一種結(jié)構(gòu)，由俄羅斯科學(xué)家M.G.Voronoi提出，針對平面內(nèi)n個離散的點，將平面分成多個區(qū)域，所得區(qū)域就是本文所要劃分軌跡數(shù)據(jù)最近點的集合。

設(shè)P={P1,P2,…,Pn}?R3為三維歐氏空間內(nèi)的n個點,d(P,Pi)為P和Pi間的歐氏距離，將由

所給出的對空間的分割稱為以P={P1,P2,…,Pn}?R3為空間點集的Voronoi圖,V(Pi)(i=1,2,…,n)為Voronoi圖的晶胞，Pi(i=1,2,…,n)為Voronoi圖的母點(生成元)，如圖7所示。

圖7 Voronoi圖

2.2.3 Voronoi劃分

進(jìn)行Voronoi劃分之前，本文首先對特征點數(shù)據(jù)進(jìn)行處理，找到特征點群的質(zhì)心點，然后按照質(zhì)心點的位置進(jìn)行Voronoi劃分，其中圓點為母點，母點四周的多邊形為Voronoi劃分的區(qū)域，即為劃分后軌跡數(shù)據(jù)點的集合。

3 基于GPS數(shù)據(jù)的實例驗證

為進(jìn)一步說明本文方法，在共同依托項目的城市交通數(shù)據(jù)可視化平臺上進(jìn)行驗證[23]，將前文提出的算法與山東省淄博市的出租車GPS數(shù)據(jù)相結(jié)合，然后在與當(dāng)?shù)芈肪W(wǎng)數(shù)據(jù)匹配的基礎(chǔ)上，進(jìn)行實際GPS數(shù)據(jù)的實例驗證。筆者利用張店區(qū)的北京路、魯泰大道、南京路、公園北路、中潤大道的主要車輛行駛路段篩選出16：00—17：00點具有代表性的382條出租車運行軌跡，通過特征提取方法得到了6592個特征點數(shù)據(jù)進(jìn)行驗證。首先得到特征點質(zhì)心分布效果圖，如圖8所示。

圖8 實際特征質(zhì)心點

3.1 多特征軌跡數(shù)據(jù)劃分方法的優(yōu)勢

為說明多特征軌跡數(shù)據(jù)劃分方法的優(yōu)越性，筆者利用淄博市張店區(qū)(北京路、魯泰大道、南京路、公園北路、中潤大道)的主要車輛行駛路段篩選出16：00—17：00點的數(shù)據(jù)，利用其他方法進(jìn)行了試驗，并與本文提出的方法進(jìn)行了對比，結(jié)果見表1。

表1 劃分效果對比

注：空間分布適應(yīng)性是指劃分后的匹配數(shù)據(jù)與原始隨機(jī)分布數(shù)據(jù)之間的比例。

從表1中數(shù)據(jù)可以看出，本文方法在數(shù)據(jù)劃分點上面明顯多于其他方法，可以很好地適應(yīng)數(shù)據(jù)空間分布隨意性的特性。

3.2 實物驗證

為更好地說明多特征劃分方法在適應(yīng)空間分布隨意性上的優(yōu)勢，本文選擇表1中基于轉(zhuǎn)角的數(shù)據(jù)劃分方法進(jìn)行驗證，對青銀高速、淄博西樞紐立交、濱萊高速、原山大道、魯泰大道、中潤大道、世紀(jì)路，以及周圍車輛行駛較多的縣道、鄉(xiāng)鎮(zhèn)道路的16：00—17：00的軌跡數(shù)據(jù)進(jìn)行劃分，并利用共同依托項目的城市交通數(shù)據(jù)可視化平臺進(jìn)行驗證，如圖9所示。

圖9 多特征劃分下主要路段GPS數(shù)據(jù)劃分

從劃分效果圖可以看出，多特征劃分效果明顯優(yōu)于其他劃分的效果，該方法較好地克服了數(shù)據(jù)空間分布隨機(jī)性問題。

4 結(jié) 語

本文對軌跡數(shù)據(jù)按照其位置關(guān)系進(jìn)行車輛行駛特征點的提取，利用α-Shapes去噪算法，對提取到的特征點按照其分布的幾何相關(guān)性，進(jìn)行簡單分組并形成點群，且利用其空間分布的屬性，按照Voronoi多邊形進(jìn)行分割，克服了軌跡數(shù)據(jù)空間分布的任意性缺陷，提高了軌跡數(shù)據(jù)劃分的效率。最后利用山東省淄博市出租車軌跡數(shù)據(jù)，依托本課題項目城市交通數(shù)據(jù)可視化平臺進(jìn)行實例驗證，取得了良好的效果。后期將會在動態(tài)數(shù)據(jù)分析及可視化方面進(jìn)行深入研究。