基于手機傳感器的車輛軌跡實時在線壓縮方法

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

（華北水利水電大學測繪與地理信息學院, 河南 鄭州 450046）

伴隨著基于位置的服務（location based service,LBS）[1]等現代技術的快速發展，產生了巨量用于刻畫移動對象運動的時空軌跡數據，并被廣泛應用于智能交通系統的分析決策.由于龐大的數據規模對于時空軌跡的存儲、管理和分析帶來了嚴峻挑戰，因此，時空軌跡的數據壓縮就成為了軌跡大數據研究領域的一個重要問題.

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

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

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

1 算法思路

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

圖1 軌跡特征點采集示意Fig.1 Collection of trajectory feature points

2 利用手機傳感器識別車輛運動行為模式及軌跡特征點采集

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

圖2 手機三軸坐標系Fig.2 Three-axis coordinate system of mobile phone

2.1 基于變速模式識別采集軌跡特征點

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

圖3 車輛啟動、制動時線性加速度計數據變化趨勢Fig.3 Changes in linear accelerometer data during vehicle starting and breaking

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

設加速度時間序列含有n個數據，并記錄為{x1,x2,···,xn}，是獨立、隨機同變量分布樣本，對于所有的xi,xj，i,j≤n且i≠j，計算統計量為

式中： s g n(·) 為符號函數，

當n≥10 時（本文n=40 ），統計量S近似服從正態分布，其均值為0，方差為

構造標準正態分布統計量為

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

2.2 基于轉向模式識別采集軌跡特征點

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

圖4 車輛轉向行駛時方向傳感器三軸數據變化Fig.4 Changes in three-axis data of direction sensor during vehicle turning

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

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

根據方位角φ的變化幅度及曲線變化率，假設圖5中的AC、EF和HI段對應軌跡的直線段，CE、FH段對應軌跡的轉向段，且CE段為大幅度短距離轉彎，FH段為小幅度長距離轉彎.定義錨點和浮動點，錨點為特征點，浮動點為當前時刻的采樣點.初始時設數據采樣序列第1點A為錨點(tmd，φmd)，序列 第 2點為浮動 點(tfd，φfd)， 其中： φmd、 φfd分別為錨點、浮動點的方位角；tmd、tfd分別為錨點、 浮動點所對應的采樣時刻.累計轉向角 θ 初值為 0.

當前轉向角為

式中：φmd,···,φfd表示從錨點到浮動點的各數據點的方位角.

首先， 采用式（5）判斷車輛行駛狀態，當θ1≤ 3°時，認為車輛為直線行駛狀態（如AC段），此過程不采樣轉向點，若該直線部分存在變速點（假如點B），則采樣該坐標并將錨點A移動到當前點B，后繼續采樣新時刻的方位角數據；當θ1＞3°時，車輛視為轉向行駛（如CE段），采樣該轉向點坐標并將錨點B移動到點C，然后，采用式（6）計算累計轉向角，

當|θ |≥ 40°，則采集相應坐標（如點D），并令θ=0，后將錨點C移動到D點，同理，假設圖1中點E為下一個 θ 到達 40° 的轉向特征點.EF段判斷仍采用與AC段相同的方法，假設識別出轉向點F；在FH段，設：

當 |θ |＜ 40°，但 ΔT=T時，則采集該坐標（如點G、H），閾值T保證了長距離緩慢轉彎的軌跡精度.

3 本文軌跡實時在線壓縮算法步驟

本算法按照20 Hz采樣頻率，即采樣間隔為0.05 s對手機內置方向傳感器和線性加速度計進行數據采集和分析，以實時在線提取特征點，實現軌跡壓縮.

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

步 驟 1當φfd>φmax時 ， 令φmax=φfd； 當φfd＜φmin時 ，令φmin=φfd； 否則φmax、φmin不變.

步驟2采用式（4）、（5）分別計算正態統計變量U和 θ1，并分為兩種情況.

情況 1當θ1≤ 3° 時，視為直線行駛，后根據U值繼續判斷：

1）若 |U|＜1.28 時，車輛處于勻速直線行駛或靜止不動狀態，則保持錨點Pstart不動，并繼續采樣新的傳感器數據點Pcur，回到步驟1.

2）若 |U|≥ 1.28 時，車輛發生變速行為，當 ΔT≥T，則采樣當前坐標點，并移動錨點Pstart到 當前點Pcur，令 φmax=φfd，φmin=φfd，后繼續采樣新的傳感器數據點，重回步驟1.

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

重復循環上述步驟直到數據采集完畢.

4 算法性能評價標準

軌跡壓縮算法的性能可從空間距離偏差、時空距離偏差、壓縮率、實時性、壓縮耗時等指標進行綜合評價，各指標含義如下：

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

圖6 壓縮精度指標的計算Fig.6 Calculation of compression accuracy indexes

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

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

4）實時性.實時性是指采集獲取軌跡點后，需要多長時間方能確定該點是否是特征點.

5）壓縮耗時.在規定的壓縮率下，完成對一條軌跡的壓縮所消耗的時間.

一般而言，很難有一種壓縮算法在所有性能指標上全部占優，需要結合應用場景進行選擇.當看重壓縮精度指標時，通常離線壓縮算法壓縮精度最好，當看重實時性時，則可采用在線壓縮算法.

5 實驗驗證與分析

5.1 實驗環境

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

圖7 手機內置傳感器耗電情況Fig.7 Power consumption of built-in sensors in mobile phones

5.2 軌跡壓縮結果

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

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

5.3 結果分析與評價

本文算法是基于特征點識別的軌跡壓縮算法，將其與同類型代表性軌跡壓縮算法進行全面對比.

5.3.1 與固定間隔采樣的實驗對比

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

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

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

5.3.2 與代表性算法的實驗對比

將本文算法進一步和代表性在線壓縮NOPW算法及離線壓縮DP算法、TD-TR算法進行實驗對比，以路況最復雜的山區路段為例，結果如圖10所示.

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

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

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

圖10 本文算法與代表性算法的壓縮實驗對比Fig.10 Comparison of compression experiments between proposed algorithm and representative algorithms

最后是GPS請求定位次數少，上述各代表性軌跡壓縮算法需采集所有原始軌跡點方能完成軌跡壓縮，請求定位次數就是所有軌跡點個數.而本文算法只對軌跡的關鍵點才請求定位并進行坐標采集，GPS的請求定位次數僅僅只是保留下來的特征點數目.當需要對大規模浮動車（如出租車等）軌跡進行特征點采集并實時上傳到服務器時，本文算法由于實時性強，無延遲且請求次數最少，顯然有助于減弱對GPS傳感器的使用強度和減少數據的網絡傳輸量，有利于定位設備的節能.

6 結 論

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