趙東保 ，馮林林 ，鄧 悅 ，曹連海

（華北水利水電大學(xué)測(cè)繪與地理信息學(xué)院, 河南 鄭州 450046）

伴隨著基于位置的服務(wù)（location based service,LBS）[1]等現(xiàn)代技術(shù)的快速發(fā)展，產(chǎn)生了巨量用于刻畫移動(dòng)對(duì)象運(yùn)動(dòng)的時(shí)空軌跡數(shù)據(jù)，并被廣泛應(yīng)用于智能交通系統(tǒng)的分析決策.由于龐大的數(shù)據(jù)規(guī)模對(duì)于時(shí)空軌跡的存儲(chǔ)、管理和分析帶來了嚴(yán)峻挑戰(zhàn)，因此，時(shí)空軌跡的數(shù)據(jù)壓縮就成為了軌跡大數(shù)據(jù)研究領(lǐng)域的一個(gè)重要問題.

時(shí)空軌跡的數(shù)據(jù)壓縮方法[2]主要分為基于特征點(diǎn)提取的壓縮[3-6]、基于路網(wǎng)的壓縮[7-9]和基于語義的壓縮[10-11]等類別.基于特征點(diǎn)提取的壓縮方法是一類通用的軌跡壓縮方法，對(duì)數(shù)據(jù)的限制要求少.基于路網(wǎng)的壓縮方法壓縮率更低，但是被約束在道路網(wǎng)中，需要事先將軌跡數(shù)據(jù)進(jìn)行較為復(fù)雜耗時(shí)的地圖匹配.基于語義的壓縮多是將時(shí)空軌跡轉(zhuǎn)變?yōu)槲谋菊Z義信息，僅在某些場(chǎng)景中應(yīng)用.軌跡壓縮還可以分為離線壓縮和在線壓縮兩類，離線壓縮是指整個(gè)軌跡數(shù)據(jù)全部讀取完畢才進(jìn)行壓縮，一般都是利用軌跡數(shù)據(jù)的全局特征進(jìn)行靜態(tài)處理.例如：經(jīng)典的DP（douglas-peucker）算法[3]就是根據(jù)中間軌跡點(diǎn)到全局首末軌跡點(diǎn)連線的垂直偏差距離提取軌跡特征點(diǎn)；TD-TR （top-down time radio）壓縮算法[4]也是一種代表性離線壓縮算法，其思路與DP算法相似，但采用時(shí)間同步歐式距離（synchronous Euclidean distance，SED）閾值代替垂直偏差距離閾值來更好地顧及軌跡的時(shí)空特性.在線壓縮算法一般是基于軌跡數(shù)據(jù)的局部特征進(jìn)行動(dòng)態(tài)處理，以實(shí)現(xiàn)對(duì)軌跡數(shù)據(jù)的實(shí)時(shí)壓縮，方便網(wǎng)絡(luò)傳輸.代表性方法如滑動(dòng)窗口算法[5]、標(biāo)準(zhǔn)開放窗口（normal opening window，NOPW）算法等[4,6]，其基本思路都是從動(dòng)態(tài)改變的窗口中提取特征點(diǎn)，以實(shí)現(xiàn)在線壓縮.軌跡壓縮過程類似于曲線化簡(jiǎn)，因此制圖綜合領(lǐng)域的經(jīng)典算法[12]也具有重要參考價(jià)值，但制圖綜合關(guān)注的是地理要素空間特征的概括與抽象，而軌跡壓縮關(guān)注的是軌跡時(shí)空特征的采集、壓縮、存儲(chǔ)和傳輸?shù)?

盡管已經(jīng)存在了相當(dāng)數(shù)量的時(shí)空軌跡壓縮方法，然而采集軌跡數(shù)據(jù)的移動(dòng)設(shè)備（如智能手機(jī)等）都有存儲(chǔ)空間和用電量的限制，在智能手機(jī)等移動(dòng)設(shè)備上使用這些壓縮算法無疑會(huì)面臨較高耗電量和占用較大存儲(chǔ)空間的問題.由于智能手機(jī)設(shè)備不止具有GPS等定位傳感器，還具有其他各類傳感器，近些年來，一些學(xué)者利用手機(jī)傳感器在用戶活動(dòng)模式識(shí)別方面開展了較多的研究工作.例如，文獻(xiàn)[13-17]就系統(tǒng)討論了如何利用手機(jī)傳感器數(shù)據(jù)識(shí)別用戶的日常運(yùn)動(dòng)模式，如坐下、靜止、步行、跑步和上下樓梯等；文獻(xiàn)[18-20]則研究了基于手機(jī)傳感器數(shù)據(jù)識(shí)別用戶的出行模式，諸如騎行、公交車、出租車、火車、地鐵和輪渡等；文獻(xiàn)[21-23]則研究了利用手機(jī)傳感器識(shí)別車輛的運(yùn)動(dòng)模式，如急轉(zhuǎn)彎、急剎車、急變道等危險(xiǎn)駕駛行為.文獻(xiàn)[24]對(duì)上述有關(guān)研究進(jìn)行了總結(jié)歸納，對(duì)手機(jī)傳感器在用戶活動(dòng)模式識(shí)別領(lǐng)域上取得的進(jìn)展進(jìn)行了全面綜述.

雖然在軌跡壓縮與基于手機(jī)傳感器的用戶活動(dòng)模式識(shí)別領(lǐng)域都取得了重要進(jìn)展，但是鮮有研究工作將二者相互結(jié)合，并根據(jù)雙方研究特點(diǎn)，綜合解決軌跡壓縮問題.為此，本文通過智能手機(jī)內(nèi)部多個(gè)低能耗傳感器（如線性加速度傳感器等）的相互配合作用來識(shí)別用戶的運(yùn)動(dòng)狀態(tài)變化，提出一種基于手機(jī)傳感器識(shí)別車輛運(yùn)動(dòng)模式的車輛軌跡數(shù)據(jù)壓縮算法，只有當(dāng)運(yùn)動(dòng)狀態(tài)發(fā)生改變時(shí)才采集該時(shí)刻下的軌跡特征點(diǎn)坐標(biāo)，以便更好地節(jié)省手機(jī)存儲(chǔ)空間，降低能耗和提高計(jì)算效率.

1 算法思路

軌跡壓縮的核心目標(biāo)是提取軌跡特征點(diǎn)，并去除冗余點(diǎn).已有壓縮算法都是先有原始軌跡，再?gòu)闹刑崛√卣鼽c(diǎn).但是，如果能夠根據(jù)車輛的運(yùn)動(dòng)行為模式在軌跡的采集過程中識(shí)別出軌跡特征點(diǎn)，就可以直接略過冗余點(diǎn)，即可實(shí)現(xiàn)軌跡壓縮.以圖1為例，藍(lán)色點(diǎn)、紅色點(diǎn)和黑色點(diǎn)分別代表著本次車輛出行的起止點(diǎn)（見①、⑩處）、變速點(diǎn)（見②、④、⑦、⑨處）和轉(zhuǎn)彎點(diǎn)（見③、⑤、⑥、⑧處）這些點(diǎn)顯然都是需要采集的軌跡特征點(diǎn)，而白色點(diǎn)則是無須采集的軌跡冗余點(diǎn).為此，可以借助智能手機(jī)的多個(gè)傳感器完成對(duì)車輛運(yùn)動(dòng)行為模式的識(shí)別.本文算法的核心思想就是通過監(jiān)測(cè)智能手機(jī)中低能耗的線性加速度傳感器和方向傳感器的數(shù)據(jù)變化來共同實(shí)時(shí)判斷車輛運(yùn)動(dòng)行為模式是否發(fā)生變化，運(yùn)動(dòng)行為模式包含直線行駛、左右轉(zhuǎn)彎、掉頭、啟動(dòng)、制動(dòng)、變速等，若車輛運(yùn)動(dòng)行為模式變化則使用GPS傳感器記錄當(dāng)前點(diǎn)坐標(biāo)，若車輛運(yùn)動(dòng)狀態(tài)處于平穩(wěn)不變時(shí)，則不采樣，從而減少定位請(qǐng)求，以此完成省內(nèi)存、低能耗的實(shí)時(shí)軌跡特征點(diǎn)采集工作，達(dá)到在線軌跡壓縮的目的.

圖1 軌跡特征點(diǎn)采集示意Fig.1 Collection of trajectory feature points

2 利用手機(jī)傳感器識(shí)別車輛運(yùn)動(dòng)行為模式及軌跡特征點(diǎn)采集

為了盡可能地降低能耗，本文只借助線性加速度傳感器和方向傳感器識(shí)別車輛的運(yùn)動(dòng)行為模式.線性加速度計(jì)輸出的是手機(jī)X、Y、Z三軸（如圖2所示）的加速度值，且除去了重力加速度在3個(gè)軸上的分量.方向傳感器的數(shù)據(jù)分別為方位角、俯仰角和翻滾角，其中方位角為手機(jī)繞Z軸旋轉(zhuǎn)時(shí)，Y軸正方向與地磁場(chǎng)北極方向的夾角；俯仰角為手機(jī)繞X軸旋轉(zhuǎn)時(shí)，Y軸正方向與水平方向的夾角；翻滾角為手機(jī)繞Y軸旋轉(zhuǎn)時(shí)，X軸正方向與水平方向的夾角.在傳感器數(shù)據(jù)采樣過程中需保持手機(jī)自身姿態(tài)固定不變，但對(duì)初始姿態(tài)不做限制，可以任意擺放.在獲取不同運(yùn)動(dòng)行為模式的傳感器數(shù)據(jù)后，通過對(duì)數(shù)據(jù)的分析來找到相應(yīng)運(yùn)動(dòng)模式下傳感器的數(shù)據(jù)變化規(guī)律，以此作為運(yùn)動(dòng)模式識(shí)別的判斷指標(biāo)，并采集相應(yīng)軌跡特征點(diǎn).

圖2 手機(jī)三軸坐標(biāo)系Fig.2 Three-axis coordinate system of mobile phone

2.1 基于變速模式識(shí)別采集軌跡特征點(diǎn)

變速模式識(shí)別主要識(shí)別車輛的啟動(dòng)制動(dòng)行為及車輛行駛過程中的急加減速行為，圖3為手機(jī)線性加速度計(jì)在車輛啟動(dòng)和制動(dòng)時(shí)各軸的數(shù)據(jù)變化情況.可以看出，車輛靜止、加速啟動(dòng)、正常行駛和制動(dòng)停車過程中，線性加速度值的變化趨勢(shì)區(qū)分明顯.在車輛靜止候車狀態(tài)時(shí)，三軸加速度圍繞速度0上下有規(guī)律波動(dòng)；當(dāng)車輛加速啟動(dòng)時(shí)，Y軸加速度數(shù)據(jù)從0向正值快速變大，后加速結(jié)束又趨于0附近；當(dāng)車輛正常勻速行駛時(shí)，三軸加速度圍繞0值上下波動(dòng)且幅度大于車輛靜止時(shí)；當(dāng)車輛制動(dòng)停車時(shí)，Y軸加速度數(shù)據(jù)從0值附近向負(fù)值快速變大，

圖3 車輛啟動(dòng)、制動(dòng)時(shí)線性加速度計(jì)數(shù)據(jù)變化趨勢(shì)Fig.3 Changes in linear accelerometer data during vehicle starting and breaking

變速特征點(diǎn)的識(shí)別方法：車輛的加減速行為反應(yīng)在加速度序列的增減趨勢(shì)變化上，那么加速度的時(shí)間數(shù)據(jù)序列就不是圍繞某一值上下波動(dòng)的平穩(wěn)狀態(tài)而是值不斷上升或下降的非平穩(wěn)狀態(tài)，本文采用M-K （manner-Kendall）非參數(shù)趨勢(shì)檢驗(yàn)法[25]來識(shí)別加速度時(shí)間序列的變化趨勢(shì)，該方法不需要樣本數(shù)據(jù)遵循一定分布且不受少數(shù)異常值影響，故在加速度序列的趨勢(shì)判斷上具有較高的準(zhǔn)確率.

設(shè)加速度時(shí)間序列含有n個(gè)數(shù)據(jù)，并記錄為{x1,x2,···,xn}，是獨(dú)立、隨機(jī)同變量分布樣本，對(duì)于所有的xi,xj，i,j≤n且i≠j，計(jì)算統(tǒng)計(jì)量為

式中： s g n(·) 為符號(hào)函數(shù)，

當(dāng)n≥10 時(shí)（本文n=40 ），統(tǒng)計(jì)量S近似服從正態(tài)分布，其均值為0，方差為

構(gòu)造標(biāo)準(zhǔn)正態(tài)分布統(tǒng)計(jì)量為

對(duì)U進(jìn)行雙邊檢驗(yàn)，在給定的置信水平 α 上，若|U|≥,則原假設(shè)是不可接受的，其中，為置信區(qū)間值.在 α 置信水平上，加速度時(shí)間序列存在明顯的上升或下降趨勢(shì).當(dāng)U＞0時(shí)，則為上升趨勢(shì)，為車輛的加速運(yùn)動(dòng)，反之則為車輛的減速運(yùn)動(dòng)；若U的絕對(duì)值分別大于或等于 1.28、1.64 和 2.32，表示該樣本通過置信度分別為 90%、95%以及99%的顯著性檢驗(yàn)水平，為確保對(duì)變速運(yùn)動(dòng)模式識(shí)別的敏感性，本文采用置信度為90%時(shí)的U值檢驗(yàn)，即 |U|≥1.28.由于該閾值是對(duì)加速度值相對(duì)變化趨勢(shì)的分析，為統(tǒng)計(jì)意義的參數(shù)，而非絕對(duì)量的加速度值，這有助于避免測(cè)量精度的影響，獨(dú)立于手機(jī)型號(hào).

2.2 基于轉(zhuǎn)向模式識(shí)別采集軌跡特征點(diǎn)

車輛的轉(zhuǎn)向模式識(shí)別主要是區(qū)分直線行駛和轉(zhuǎn)彎行駛，當(dāng)判斷處于轉(zhuǎn)彎行駛時(shí)則需要采集轉(zhuǎn)向點(diǎn)坐標(biāo)，當(dāng)判斷處于直線行駛則僅需要采集變速點(diǎn)即可.如圖4所示為車輛行駛過程中手機(jī)方向傳感器在發(fā)生不同轉(zhuǎn)向行為時(shí)各個(gè)軸的數(shù)據(jù)變化情況.可以看出：車輛在轉(zhuǎn)向時(shí)，俯仰角和翻滾角均保持平穩(wěn)未發(fā)生明顯趨勢(shì)變化，而方位角則發(fā)生了劇烈的上升和下降變化，在車輛右轉(zhuǎn)時(shí)，方位角逐漸增大，約為90°，反之左轉(zhuǎn)時(shí)則逐漸減小，也約為90°.

圖4 車輛轉(zhuǎn)向行駛時(shí)方向傳感器三軸數(shù)據(jù)變化Fig.4 Changes in three-axis data of direction sensor during vehicle turning

同時(shí)從圖4（a）和4（b）可以看出：當(dāng)車輛在幅度較大、距離較短的轉(zhuǎn)彎時(shí)用時(shí)較短，且方位角曲線斜率較大，相應(yīng)的車輛左轉(zhuǎn)或掉頭亦是如此；而車輛在幅度較小、但距離較長(zhǎng)的緩慢轉(zhuǎn)彎時(shí)用時(shí)較長(zhǎng)，且方位角曲線斜率較小.此外，由于方向傳感器中方位角的輸出范圍為 0～360°，會(huì)存在如圖4（c）、圖4（d）所示的方位角數(shù)據(jù)突變情況，多數(shù)情況下發(fā)生在車輛的轉(zhuǎn)向和掉頭行為中，有時(shí)也發(fā)生在車輛的直線行駛中（行駛方向正好為0或360°）.為此，在方向傳感器數(shù)據(jù)的處理部分也需要考慮該特殊情況.總體而言，方向傳感器的方位角數(shù)據(jù)所反映出的變化特征對(duì)轉(zhuǎn)向行為具有良好的識(shí)別性.

轉(zhuǎn)向特征點(diǎn)識(shí)別方法：本文將車輛轉(zhuǎn)向行為分為左右轉(zhuǎn)彎、掉頭等幅度較大的短距離轉(zhuǎn)彎和轉(zhuǎn)向幅度較小的長(zhǎng)距離轉(zhuǎn)彎.通常一個(gè)左右轉(zhuǎn)彎幅度大概在 80°～120°，當(dāng)轉(zhuǎn)向角度在 40°～60° 時(shí)，車輛大致位于道路的交叉點(diǎn)位置，故本文中當(dāng)累計(jì)轉(zhuǎn)向角累計(jì)到40° 時(shí)才采集一個(gè)轉(zhuǎn)向特征點(diǎn)，以避免冗余采集.但對(duì)于小幅度的長(zhǎng)距離轉(zhuǎn)彎，若等到累計(jì)到40° 再采樣特征點(diǎn)，此時(shí)車輛可能已經(jīng)行駛了較長(zhǎng)距離，故通過設(shè)置采樣時(shí)間間隔閾值T來控制在累計(jì)轉(zhuǎn)向角小于40° 的情況下的轉(zhuǎn)向特征點(diǎn)采樣.以圖5為例介紹本算法轉(zhuǎn)向特征點(diǎn)具體采樣過程.圖中：φ為方位角；t為采樣時(shí)刻.

根據(jù)方位角φ的變化幅度及曲線變化率，假設(shè)圖5中的AC、EF和HI段對(duì)應(yīng)軌跡的直線段，CE、FH段對(duì)應(yīng)軌跡的轉(zhuǎn)向段，且CE段為大幅度短距離轉(zhuǎn)彎，F(xiàn)H段為小幅度長(zhǎng)距離轉(zhuǎn)彎.定義錨點(diǎn)和浮動(dòng)點(diǎn)，錨點(diǎn)為特征點(diǎn)，浮動(dòng)點(diǎn)為當(dāng)前時(shí)刻的采樣點(diǎn).初始時(shí)設(shè)數(shù)據(jù)采樣序列第1點(diǎn)A為錨點(diǎn)(tmd，φmd)，序列 第 2點(diǎn)為浮動(dòng) 點(diǎn)(tfd，φfd)， 其中： φmd、 φfd分別為錨點(diǎn)、浮動(dòng)點(diǎn)的方位角；tmd、tfd分別為錨點(diǎn)、 浮動(dòng)點(diǎn)所對(duì)應(yīng)的采樣時(shí)刻.累計(jì)轉(zhuǎn)向角 θ 初值為 0.

當(dāng)前轉(zhuǎn)向角為

式中：φmd,···,φfd表示從錨點(diǎn)到浮動(dòng)點(diǎn)的各數(shù)據(jù)點(diǎn)的方位角.

首先， 采用式（5）判斷車輛行駛狀態(tài)，當(dāng)θ1≤ 3°時(shí)，認(rèn)為車輛為直線行駛狀態(tài)（如AC段），此過程不采樣轉(zhuǎn)向點(diǎn)，若該直線部分存在變速點(diǎn)（假如點(diǎn)B），則采樣該坐標(biāo)并將錨點(diǎn)A移動(dòng)到當(dāng)前點(diǎn)B，后繼續(xù)采樣新時(shí)刻的方位角數(shù)據(jù)；當(dāng)θ1＞3°時(shí)，車輛視為轉(zhuǎn)向行駛（如CE段），采樣該轉(zhuǎn)向點(diǎn)坐標(biāo)并將錨點(diǎn)B移動(dòng)到點(diǎn)C，然后，采用式（6）計(jì)算累計(jì)轉(zhuǎn)向角，

當(dāng)|θ |≥ 40°，則采集相應(yīng)坐標(biāo)（如點(diǎn)D），并令θ=0，后將錨點(diǎn)C移動(dòng)到D點(diǎn)，同理，假設(shè)圖1中點(diǎn)E為下一個(gè) θ 到達(dá) 40° 的轉(zhuǎn)向特征點(diǎn).EF段判斷仍采用與AC段相同的方法，假設(shè)識(shí)別出轉(zhuǎn)向點(diǎn)F；在FH段，設(shè)：

當(dāng) |θ |＜ 40°，但 ΔT=T時(shí)，則采集該坐標(biāo)（如點(diǎn)G、H），閾值T保證了長(zhǎng)距離緩慢轉(zhuǎn)彎的軌跡精度.

3 本文軌跡實(shí)時(shí)在線壓縮算法步驟

本算法按照20 Hz采樣頻率，即采樣間隔為0.05 s對(duì)手機(jī)內(nèi)置方向傳感器和線性加速度計(jì)進(jìn)行數(shù)據(jù)采集和分析，以實(shí)時(shí)在線提取特征點(diǎn)，實(shí)現(xiàn)軌跡壓縮.

設(shè)P為傳感器的數(shù)據(jù)集，P={Pi}， 其中，Pi(t,φ,z)為 第i次采樣的數(shù)據(jù)點(diǎn)，其中，z為三軸合線性加速度.初始時(shí)，令錨點(diǎn)Pstart=P1，浮動(dòng)點(diǎn)Pcur=P2.設(shè)定T為5、10 s等，以初始時(shí)刻數(shù)據(jù)點(diǎn)的方位角為計(jì)算起點(diǎn)，累計(jì)轉(zhuǎn)向角則步驟如下：

步 驟 1當(dāng)φfd>φmax時(shí) ， 令φmax=φfd； 當(dāng)φfd＜φmin時(shí) ，令φmin=φfd； 否則φmax、φmin不變.

步驟2采用式（4）、（5）分別計(jì)算正態(tài)統(tǒng)計(jì)變量U和 θ1，并分為兩種情況.

情況 1當(dāng)θ1≤ 3° 時(shí)，視為直線行駛，后根據(jù)U值繼續(xù)判斷：

1）若 |U|＜1.28 時(shí)，車輛處于勻速直線行駛或靜止不動(dòng)狀態(tài)，則保持錨點(diǎn)Pstart不動(dòng)，并繼續(xù)采樣新的傳感器數(shù)據(jù)點(diǎn)Pcur，回到步驟1.

2）若 |U|≥ 1.28 時(shí)，車輛發(fā)生變速行為，當(dāng) ΔT≥T，則采樣當(dāng)前坐標(biāo)點(diǎn)，并移動(dòng)錨點(diǎn)Pstart到 當(dāng)前點(diǎn)Pcur，令 φmax=φfd，φmin=φfd，后繼續(xù)采樣新的傳感器數(shù)據(jù)點(diǎn)，重回步驟1.

情況 2當(dāng)θ1＞3° 時(shí)，視為轉(zhuǎn)向行駛，則采樣該轉(zhuǎn)向點(diǎn)坐標(biāo)，并移動(dòng)錨點(diǎn)Pstart到 當(dāng)前點(diǎn)Pcur，且令φ=0， φmax=φfd，φmin= φfd；后采用式（6）計(jì)算 θ ，當(dāng)|θ|≥ 40°時(shí)采樣該點(diǎn)坐標(biāo)，若在 ΔT=T期間始終未出現(xiàn) |θ |≥ 40°的轉(zhuǎn)向點(diǎn)，則在該時(shí)間段結(jié)束時(shí)也采集當(dāng)前點(diǎn)坐標(biāo)，并以相同方式移動(dòng)錨點(diǎn)到浮動(dòng)點(diǎn)處，且令 φ =0 ， φmax=φfd，φmin= φfd；重回步驟1.

重復(fù)循環(huán)上述步驟直到數(shù)據(jù)采集完畢.

4 算法性能評(píng)價(jià)標(biāo)準(zhǔn)

軌跡壓縮算法的性能可從空間距離偏差、時(shí)空距離偏差、壓縮率、實(shí)時(shí)性、壓縮耗時(shí)等指標(biāo)進(jìn)行綜合評(píng)價(jià)，各指標(biāo)含義如下：

1）空間距離偏差.令P={P1,P2,···,Pn} 為按固定采樣間隔采集的原始軌跡，L={L1,L2,···,Lk} 為壓縮后保留的軌跡特征點(diǎn)，原始軌跡點(diǎn)的坐標(biāo)表示為(xPi,yPi)，i=1,2,···,n，壓縮后軌跡點(diǎn)的坐標(biāo)表示為(xLl,yLl)，l=1,2,···,k，將原始軌跡點(diǎn)垂直投影到相應(yīng)的化簡(jiǎn)線段上，如圖6（a）中，P3的垂直投影點(diǎn)為Q3，將原始軌跡中任意點(diǎn)Pi與其對(duì)應(yīng)點(diǎn)Qi的偏差距離記為Di，則該偏差距離之和的平均值即為空間距離平均偏差（average euclidean distance error，AEDE）.

圖6 壓縮精度指標(biāo)的計(jì)算Fig.6 Calculation of compression accuracy indexes

2）時(shí)空距離偏差.時(shí)空距離偏差不僅考慮了軌跡點(diǎn)的位置而且還加入了時(shí)間屬性，如圖6（b）所示，P3的對(duì)應(yīng)點(diǎn)仍是Q3，但該對(duì)應(yīng)點(diǎn)是對(duì)時(shí)間信息進(jìn)行線性插值得到的.在圖6（b）的原始軌跡中，根據(jù)從起始點(diǎn)到任意點(diǎn)Pi所經(jīng)歷的時(shí)間與總的時(shí)間之比，再在相應(yīng)的化簡(jiǎn)線段上進(jìn)行線性插值即可得到Pi的對(duì)應(yīng)點(diǎn)Qi，根據(jù)二者的偏差距離就可得到時(shí)空距離偏差，繼而得到時(shí)空距離平均偏差（average synchronized euclidean distance error, ASEDE）.

3）壓縮率R.壓縮后保留軌跡特征點(diǎn)數(shù)k與原始軌跡點(diǎn)總數(shù)n的比值，表示為

4）實(shí)時(shí)性.實(shí)時(shí)性是指采集獲取軌跡點(diǎn)后，需要多長(zhǎng)時(shí)間方能確定該點(diǎn)是否是特征點(diǎn).

5）壓縮耗時(shí).在規(guī)定的壓縮率下，完成對(duì)一條軌跡的壓縮所消耗的時(shí)間.

一般而言，很難有一種壓縮算法在所有性能指標(biāo)上全部占優(yōu)，需要結(jié)合應(yīng)用場(chǎng)景進(jìn)行選擇.當(dāng)看重壓縮精度指標(biāo)時(shí)，通常離線壓縮算法壓縮精度最好，當(dāng)看重實(shí)時(shí)性時(shí)，則可采用在線壓縮算法.

5 實(shí)驗(yàn)驗(yàn)證與分析

5.1 實(shí)驗(yàn)環(huán)境

本次實(shí)驗(yàn)采用4種不同型號(hào)的智能手機(jī)（MI 8、MI 8 Lite、HONOR 20 和 HUAWEI P20）分別采集4種路況下的軌跡數(shù)據(jù).手機(jī)均放置于車體內(nèi)部，且對(duì)初始姿態(tài)不做要求，但應(yīng)保證行駛過程中保持穩(wěn)定.首先對(duì)3種傳感器耗電情況進(jìn)行實(shí)際測(cè)試（以MI 8手機(jī)為例）.算法中線性加速度傳感器和方向傳感器的采樣間隔為 0.05 s，GPS 傳感器為 1.00 s，采用消耗電池的容量值（mA·h）代表傳感器的耗電量，實(shí)測(cè)結(jié)果如圖7（a）所示.線性加速度傳感器、方向傳感器和GPS定位傳感器每小時(shí)耗電約為1、2 mA·h和40 mA·h，GPS傳感器的耗電量遠(yuǎn)遠(yuǎn)高于其他兩種傳感器.圖7（b）是采用百度地圖API的定位功能實(shí)驗(yàn)測(cè)得的在不同采樣間隔下手機(jī)耗電量情況，隨著定位請(qǐng)求采樣間隔的增加，手機(jī)耗電量穩(wěn)步降低.可見合理增大采樣間隔，減少請(qǐng)求定位次數(shù)有助于一定程度上降低手機(jī)的能耗.

圖7 手機(jī)內(nèi)置傳感器耗電情況Fig.7 Power consumption of built-in sensors in mobile phones

5.2 軌跡壓縮結(jié)果

根據(jù)不同路況屬性分成4種類型進(jìn)行算法測(cè)試：1）高速道路，道路平滑順直，路況好，車輛行駛速度快；2）山區(qū)道路，道路盤繞山體，蜿蜒曲折坡陡彎急；3）城郊道路，路況稍顯復(fù)雜，存在個(gè)別顛簸路段，行駛速度較快；4）市區(qū)道路，車輛時(shí)速較慢，各種交通信號(hào)燈和交通堵塞，走走停停.如圖8所示，圖中包含了 4 種路況下的原始軌跡以及在閾值T=60 s時(shí)本文壓縮算法提取的軌跡特征點(diǎn).

圖8 4種不同類型的實(shí)測(cè)軌跡路線圖及其壓縮結(jié)果Fig.8 Compression results of four different types of experimental vehicle trajectories

5.3 結(jié)果分析與評(píng)價(jià)

本文算法是基于特征點(diǎn)識(shí)別的軌跡壓縮算法，將其與同類型代表性軌跡壓縮算法進(jìn)行全面對(duì)比.

5.3.1 與固定間隔采樣的實(shí)驗(yàn)對(duì)比

采用本文算法對(duì)4種路況下的軌跡進(jìn)行壓縮，其時(shí)間間隔閾值T分別設(shè)置為 5、10、15、20 s.在保證相同壓縮率的情況下，與固定時(shí)間間隔采樣進(jìn)行AEDE和ASEDE的精度對(duì)比.為保證壓縮率一致，可根據(jù)圖9（a）中本文算法在不同路況下的壓縮率換算出固定時(shí)間間隔采樣所對(duì)應(yīng)的閾值.如在本文算法的T值分別為 5、10、15、20 s時(shí)，山區(qū)路段對(duì)應(yīng)的固定T值應(yīng)為 4、8、11、15 s，高速路段對(duì)應(yīng)的則為 6、10、15、20 s，其他路況可同理計(jì)算得出.

實(shí)驗(yàn)結(jié)果如圖9（b）～（e）所示，可以看出隨著時(shí)間間隔閾值的增大，不同路段的壓縮精度愈來愈差，而在這種趨勢(shì)下，本文算法的時(shí)空距離偏差和空間距離偏差始終小于固定間隔采樣的相應(yīng)值，且隨著采樣間隔的增大，這種優(yōu)勢(shì)有增大趨勢(shì).此外，從圖9（a）中可以看出在同樣的采樣時(shí)間間隔閾值下，本文算法對(duì)山區(qū)路段、城郊和市區(qū)路段、高速路段壓縮率由高到低，表明了本文算法對(duì)不同路況具有一定程度的適應(yīng)性.由于本文算法借助手機(jī)傳感器可以實(shí)時(shí)識(shí)別并采集軌跡中的關(guān)鍵轉(zhuǎn)向點(diǎn)和變速點(diǎn)，保證了軌跡的空間幾何形態(tài)和時(shí)間特征，因此在相同壓縮率下，本文算法在時(shí)間精度和空間精度都優(yōu)于固定間隔采樣.

圖9 本文算法與固定間隔采樣的壓縮精度對(duì)比Fig.9 Comparison of compression accuracy between proposed algorithm and fixed interval sampling

5.3.2 與代表性算法的實(shí)驗(yàn)對(duì)比

將本文算法進(jìn)一步和代表性在線壓縮NOPW算法及離線壓縮DP算法、TD-TR算法進(jìn)行實(shí)驗(yàn)對(duì)比，以路況最復(fù)雜的山區(qū)路段為例，結(jié)果如圖10所示.

從圖10（a）和圖10（b）中可以得出：本文算法的時(shí)空壓縮精度強(qiáng)于DP算法，但弱于TD-TR算法和NOPW算法，就平均而言，本算法的時(shí)空距離平均偏差比在線NOPW算法多約0.4 m；本文算法的空間壓縮精度弱于其他3種算法，在壓縮率最低時(shí)，其空間距離平均偏差比在線NOPW算法多約1.4 m，平均多出0.6 m.這表明本文算法在壓縮精度方面不如代表性算法，但相比手機(jī)GPS傳感器的定位誤差而言，總體差值也較小.

首先是壓縮耗時(shí)少，圖10（c）是各算法壓縮耗時(shí)對(duì)比，可以看出壓縮率在25%以下，本文算法的壓縮總耗時(shí)都最少，且隨著壓縮率減小而逐步降低，比DP算法減少約30%的計(jì)算耗時(shí).而NOPW算法的耗時(shí)卻隨著壓縮率的降低逐漸增大，相比其它算法其耗時(shí)明顯偏大，通常軌跡壓縮的壓縮率都是相當(dāng)?shù)偷?，這影響了其適用范圍和普適性.

其次是實(shí)時(shí)性強(qiáng)，本文算法相較于DP、TD-TR等離線壓縮算法可以實(shí)時(shí)在線地壓縮軌跡，根據(jù)加速度傳感器和方向傳感器的數(shù)據(jù)處理，可以在當(dāng)前秒就判定該軌跡點(diǎn)是否是特征點(diǎn).NOPW盡管是在線壓縮算法，但實(shí)時(shí)性有延遲.圖10（d）是針對(duì)每秒采樣一次的山區(qū)路段，NOPW算法在不同壓縮率下判斷得出讀入的軌跡點(diǎn)是否是特征點(diǎn)的平均延遲時(shí)間，可以看出其在5%壓縮率下，甚至要延遲十幾秒方能確定特征點(diǎn)，這在某些智能交通應(yīng)用場(chǎng)景是重要不足.

圖10 本文算法與代表性算法的壓縮實(shí)驗(yàn)對(duì)比Fig.10 Comparison of compression experiments between proposed algorithm and representative algorithms

最后是GPS請(qǐng)求定位次數(shù)少，上述各代表性軌跡壓縮算法需采集所有原始軌跡點(diǎn)方能完成軌跡壓縮，請(qǐng)求定位次數(shù)就是所有軌跡點(diǎn)個(gè)數(shù).而本文算法只對(duì)軌跡的關(guān)鍵點(diǎn)才請(qǐng)求定位并進(jìn)行坐標(biāo)采集，GPS的請(qǐng)求定位次數(shù)僅僅只是保留下來的特征點(diǎn)數(shù)目.當(dāng)需要對(duì)大規(guī)模浮動(dòng)車（如出租車等）軌跡進(jìn)行特征點(diǎn)采集并實(shí)時(shí)上傳到服務(wù)器時(shí)，本文算法由于實(shí)時(shí)性強(qiáng)，無延遲且請(qǐng)求次數(shù)最少，顯然有助于減弱對(duì)GPS傳感器的使用強(qiáng)度和減少數(shù)據(jù)的網(wǎng)絡(luò)傳輸量，有利于定位設(shè)備的節(jié)能.

6 結(jié) 論

本文通過監(jiān)測(cè)分析手機(jī)中低能耗的線性加速度傳感器和方向傳感器的數(shù)據(jù)變化，來識(shí)別車輛的運(yùn)動(dòng)行為模式，并據(jù)此請(qǐng)求采集行駛過程中的軌跡特征點(diǎn)，從而實(shí)現(xiàn)車輛軌跡的實(shí)時(shí)在線壓縮.將本文算法與代表性基于特征點(diǎn)提取的軌跡壓縮算法進(jìn)行實(shí)驗(yàn)對(duì)比，得出以下結(jié)論：本文算法在時(shí)空距離偏差上全面優(yōu)于固定時(shí)間間隔采樣法和DP算法，但弱于TD-DR算法和NOPW算法.盡管在壓縮精度上稍欠不足，但卻具有綜合優(yōu)勢(shì).首先，本文算法是在線壓縮算法，實(shí)時(shí)性強(qiáng)，無延遲，壓縮耗時(shí)少，對(duì)手機(jī)存儲(chǔ)空間的占用少；其次，本文算法僅在關(guān)鍵特征點(diǎn)處才請(qǐng)求定位，減少了數(shù)據(jù)的網(wǎng)絡(luò)傳輸量和對(duì)流量的消耗，減弱了對(duì)GPS傳感器的使用強(qiáng)度，有助于一定程度上降低手機(jī)能耗；最后，本文算法對(duì)不同路況具有一定程度的適應(yīng)性且算法所用的時(shí)間間隔閾值也便于普通用戶理解.總之，本文算法是一個(gè)兼顧了多項(xiàng)指標(biāo)的車輛軌跡實(shí)時(shí)在線壓縮算法，適用于面向大眾用戶的軌跡類場(chǎng)景應(yīng)用.