論文推薦|唐爐亮：一種眾源車載GPS軌跡大數據自適應濾選方法

《測繪學報》

構建與學術的橋樑 拉近與權威的距離

閱讀以下鏈接

贏中圖集團旅遊精品！

1

11, 李清泉1,2

1. 武漢大學測繪遙感信息工程國家重點實驗室, 湖北 武漢 430079;

2. 深圳大學 土木工程學院 空間信息智能感知與服務深圳市重點實驗室, 廣東 深圳 518060

收稿日期：2016-03-30； 修回日期：2016-10-27

基金項目：國家自然科學基金（41671442；41571430；41271442）

第一作者簡介： 唐爐亮(1973-),男,博士,教授,研究方向為GIS-T、時空GIS、軌跡大數據挖掘等。

摘要：基於同步高低精度GPS軌跡數據的空間特徵和GPS誤差分佈原理，提出了一種眾源GPS車載軌跡大數據自適應分割-濾選模型。該模型首先通過角度、距離約束將完整的車載GPS軌跡數據進行分割，以軌跡分割段作為基本濾選單元；然後通過對比軌跡分割段內GPS軌跡向量與其參考基線間的相似度，按照相似度與GPS定位精度之間的量化關係指導濾選。試驗結果表明，該方法可以實現車載軌跡大數據按信息提取精度需求的濾選。

關鍵詞： 眾源軌跡數據 軌跡分割 相似度模型 數據濾選 大數據

An Adaptive Filtering Method Based on Crowdsourced Big Trace Data

TANG Luliang1

1

11, LI Qingquan1,2

Abstract: Vehicles' GPS traces collected by crowds have being as a new kind of big data and are widely applied to mine urban geographic information with low-cost, quick-update and rich-informative. However, the growing volume of vehicles' GPS traces has caused difficulties in data processing and their low quality adds uncertainty when information mining. Thus, it is a hot topic to extract high-quality GPS data from the crowdsourced traces based on the expected accuracy. In this paper, we propose an efficient partition-and-filter model to filter trajectories with expected accuracy according to the spatial feature of high-precision GPS data and the error rule of GPS data. First, the proposed partition-and-filter model to partition a trajectory into sub-trajectories based on the constrained distance and angle, which are chosen as the basic unit for the next processing step. Secondly, the proposed method collects high-quality GPS data from each sub-trajectory according to the similarity between GPS tracking points and the reference baselines constructed using random sample consensus algorithm. Experimental results demonstrate that the proposed method can effectively pick up high quality GPS data from crowdsourced trace data sets with the expected accuracy.

Key words: crowdsourced trace trajectories partition similarity model data filtering big data

隨著GPS裝置的不斷普及和無線通信、網路技術的飛速發展，人們不僅成為城市地理信息的感知者，同樣也成為城市地理數據的採集者。這些由非專業地理數據採集人員提供的眾源車載軌跡大數據逐漸成為數據挖掘的重要數據源。面對不同的研究需求，對原始軌跡數據集的數據質量要求也有所不同。例如：對於城市群體、個人行為模式挖掘[

-

]，人們一般採用來自手機終端的軌跡數據，其定位精度大約在100 m左右；對於道路級城市交通動態、靜態信息提取[

-

]，一般採用來自城市計程車系統的車載GPS軌跡，其定位精度大約在15 m左右。對於車道級城市交通動態、靜態信息挖掘[

-

]，則需要原始軌跡數據的定位精度在3~5 m左右。然而，眾源車載軌跡大數據因採集源、採集環境等因素導致數據整體質量參差不齊，儘管數據量豐富但有價值數據比例較低。未經濾選的原始數據，不僅加劇了信息提取結果的不確定性，同時海量數據也為數據操作和分析帶來困難。因此，如何從眾源軌跡數據中自適應地濾選出符合精度需求的有效數據是研究的重點。目前，國內外有關眾源車載軌跡大數據自適應濾選的相關研究仍然處於起步階段。現有研究依然停留於對明顯的GPS噪音或異常值剔除。例如：基於濾波方法剔除GPS軌跡數據中的明顯噪音數據[

-

]和利用空間聚類方法去除GPS軌跡數據內大量的漂移點[

-

,

-

]。濾波方法一般根據前一個軌跡點的位置、航向、速度等運動特徵計算獲取下一個軌跡點的空間位置預測值，並與其真實測量值進行對比，實現對異常數據的判別；空間聚類方法則主要利用密度聚類方法剔除軌跡數據中的漂移點。採用濾波方法修正GPS軌跡數據中的明顯噪音點存在以下局限性：①依賴於數據採樣頻率；②只能修正明顯噪音。

採用空間聚類方法優化軌跡數據的基本原理有兩條：①低密度點等同於異常值，也等同於質量差的軌跡點;②高精度軌跡點一般會聚類於每一條車道中心線。第1種方式雖然不用考慮數據採樣間隔，但是無法對夾雜在高密度點中的低質數據進行去除。第2種方式同樣不需要考慮數據採樣頻率，然而卻需要先驗知識支持且演算法複雜。這些方法從應用角度分析，一定程度上改善了原始數據的質量問題，但是仍然沒有深入到軌跡數據自適應濾選。

本文提出一種眾源車載軌跡大數據自適應濾選方法。利用觀測信息和動力學模型信息的自適應平衡濾波已有充分研究[

-

,

]，本文側重通過分析高精度GPS軌跡數據的空間特徵和GPS誤差分佈，構建一種分割-濾選模型。該模型首先通過角度、距離約束將完整的浮動車軌跡數據進行分割，將軌跡分割段作為基本濾選單元；然後採用RANSAC[

]演算法(隨機抽樣一致)構建每一個軌跡分割段的參考基線，並將其作為位置參考，計算GPS軌跡向量與其參考基線間的相似度，按照相似度閾值進行濾選。試驗結果表明，該方法可以實現眾源軌跡大數據按精度需求濾選，降低數據冗餘度，為未來不同精度需求的信息提取提供可靠的數據源。

1 眾源車載GPS軌跡數據質量分析

眾源車載GPS軌跡數據一般由居民或者團體自發採集，數據量大、來源廣，其數據質量因GPS接收器性能、採集環境、採集行為而參差不齊。目前，按照GPS軌跡數據的定位精度可以將其粗略分為高精度GPS軌跡數據(如：定位精度分米級)和低精度GPS軌跡數據(定位精度米級，如10 m)。例如，由城市計程車採集的GPS軌跡數據一般是一種低精度的GPS軌跡數據，其定位精度是10~15 m。由於其採集環境較為複雜、採集過程非專業性，原始車載GPS軌跡數據內存在大量異常值及定位精度極差的軌跡點(

)。裝有IMU的專業測量車利用差分GPS方法採集的高精度DGPS軌跡數據

通過對比同步高低精度GPS軌跡數據的空間特徵發現：低精度GPS數據集的某個軌跡點與其鄰近的其他軌跡點之間的角度經常突然變大且漂移較遠，該軌跡點的定位精度一般較低。另外，根據GPS數據誤差分佈原理[

]，假設GPS位置數據的整體精度是5 m，則原始GPS數據集中，既存在一部分高精度定位GPS定位軌跡點，也存在一部分低於整體精度的GPS軌跡點。通常根據道路的線性特徵和車輛運動過程的運動慣性，在相對平直的道路段內，車輛行駛狀態的高精度GPS定位軌跡的線性特徵往往比較平滑，其平滑度在一定程度上反映了GPS軌跡數據的定位精度。如何從原始軌跡數據中濾選出可以滿足信息提取精度需求的軌跡數據，關鍵在於如何設定平滑度評價方法及參考，然後通過對濾選數據構成軌跡線的線性平滑度的控制，使得濾選數據的質量儘可能達到需求精度指標。

2 眾源GPS車載軌跡大數據自適應濾選

通過以上分析，本文提出了一種基於分割-濾選模型的眾源車載軌跡大數據自適應濾選方法。分割階段可以實現對軌跡數據自適應分割，將處於相同線性規律的子軌跡段作為濾選單元；濾選階段則通過構建子軌跡段的參考基線，計算軌跡點向量與參考基線的相似度，制定可以控制子軌跡段整體線性平滑度的濾選閾值，對軌跡數據進行分閾值濾選。

2.1 軌跡分割

軌跡分割是軌跡數據挖掘分析的前提。目前大部分軌跡分割方法主要從軌跡位置、採樣間隔、速度及其他移動特徵出發，制定相應的分割約束因子及約束閾值對完整軌跡進行分割[

-

]。本文提出的軌跡分割主要服務於高精度軌跡數據濾選，因此，軌跡分割約束因子主要由可以反映GPS軌跡數據定位精度的軌跡向量角度和距離構成。本文從軌跡數據的圖形複雜度及用戶需求角度出發，提出了一種軌跡分割因子閾值自適應方法。

2.1.1 顧忌角度和距離的軌跡分割演算法

分割約束因子是軌跡分割的關鍵。一般情況下，車載軌跡數據體現了移動目標直行、轉彎、掉頭行駛等行為，通過角度約束可以很好地將這些表現不同行駛行為的軌跡進行分割，得到保持同一駕駛行為的子軌跡段，而距離約束則可以將車輛在同一行駛方向不同位置行駛時記錄的軌跡進行區分。於是，採用GPS軌跡向量與整體軌跡行駛方向的夾角以及GPS軌跡點偏離整體軌跡行駛航線的距離，可以度量GPS軌跡點定位精度高低。因此本文從軌跡點的角度和距離出發，對整體軌跡進行分割。假設軌跡

={

12,…,

}，

和

分別為分割約束因子，其中

表示軌跡向量和的夾角，

表示

第1步：將軌跡

的起點

112第2步：從

3開始依次遍歷，計算當前點與其下一個軌跡點構成向量與起點向量的夾角及當前點到起點向量的垂直距離。如果與的夾角或者

到的垂直距離值其中之一大於角度閾值

或距離閾值

，則

t-1即為分割特徵點，並添加至分割點集

，

=3,4,…,

。第3步：將

1，並作為新的起點，連接

的下一個軌跡點

t+1，重複第2步計算，直到剩餘軌跡點與當前點及其向量之間的角度值和距離值都小於角度閾值與距離閾值。

2.1.2 軌跡分割閾值分析

分割閾值(角度閾值A，距離閾值D)決定了軌跡分割粒度的大小。目前，很多關於軌跡分割的研究在閾值設定過程中傾向於用戶自定義，其缺陷主要體現在兩個方面。一方面增加了用戶確定最佳分割閾值的困難，另一方面圖形複雜度不一的軌跡數據都採用同一個分割閾值，使得分割結果不理想。軌跡分割閾值的大小其實受制於兩個因素：①用戶分割需求；②軌跡數據自身的圖形複雜度。用戶分割需求通常是一種比較粗略的心理估算，在整體分割過程中具有規範整體分割閾值範圍的作用。軌跡數據自身的圖形複雜度則具體決定了該條軌跡在用戶分割需求的基礎上最終的分割閾值，即如果軌跡數據圖形複雜度高，被分割的粒度就應該大，分割閾值相對較小；如果軌跡數據圖形簡單，則被分割的粒度就相對較小，分割閾值也相對較大。本文從影響軌跡分割閾值的兩個因素出發，提出了一種顧及用戶分割需求及軌跡圖形複雜度的軌跡分割閾值確定方法。

,…,

}，則

的分割閾值

和D可以定義為

(1)

(2)

式中，

和

為常數項，在分割閾值確定過程中體現了用戶分割需求約束，具體值可以由用戶制定；ang表示軌跡點

到軌跡向量12,…,

n-2}，

ang為集合ang的標準差；dis表示軌跡點

到軌跡向量12,…,

n-1}，

dis為集合dis的標準差；

為軌跡

內所有軌跡點連線的長度與

按照式(1)和式(2)，當用戶需求確定后，即可計算出每一條軌跡的分割閾值，最終獲取最理想的軌跡分割結果。

2.2 軌跡濾選

按照正常的車輛行駛規則：車輛會遵守交通規則，沿著車道中心線的延伸方向穩定行駛除非遇到轉彎或者快速變換車道。因此，反映車輛真實行駛狀態的高精度GPS軌跡數據的線性連接應該是一條平滑且無明顯鋸齒狀的平滑線條，即處於同一條子軌跡段內的高精度軌跡點在航向和位置上存在較高的空間一致性。根據這個特點，本文利用RANSAC演算法原理，以直線方程作為數學模型，對每一個子軌跡段構建其參考基線。RANSAC演算法相較於其他線性擬合演算法，如最小二乘法、模糊加權擬合法，RANSAC演算法抗噪性強，可以不受噪音點的干擾，找出軌跡段內高度一致的軌跡點並擬合成線。

雖然參考基線並不能代表軌跡點真值的空間位置，但是參考基線是最能代表軌跡點的基線。軌跡濾選過程中，參考基線一般用來作為控制濾選軌跡整體線性平滑度的標尺。在參考基線構建過程中，需要選擇合適的模型去模擬軌跡行駛的線性特徵。本文採用直線方程作為RANSAC演算法模型(

)，利用子軌跡段內每一個軌跡點的位置構建參考基線方程，其中RANSAC演算法原理可以參見文獻[

]。另外，子軌跡段的參考基線本質上是一條沒有方向的直線段。本文為了方便後期濾選，將子軌跡段的前進方向作為參考標準，對參考基線賦予方向屬性，即參考基線的方向與子軌跡段的移動方向一致(

)。

2.2.1 向量相似度模型

參考基線在濾選的過程中，可以通過計運算元軌跡段內其他軌跡向量與參考基線向量的相似度，按照相似度閾值進行濾選。目前評估向量相似度的模型主要包含向量的模、夾角及向量間距離等因子[

-

]。由於行駛車輛的速度對GPS定位精度的影響可以忽略不計，因此，本文提出了一種顧及夾角和距離的向量相似度評價模型。假設子軌跡段為

={

,…,

根據軌跡點

的航向值及其空間位置，構成的向量與參考基線向量之間的相似度可定義為

式中，sim(

k

)表示軌跡向量

與基線向量

之間的相似度值；|

′

|表示軌跡向量點

與其投影在參考基線上的點

′

的垂直距離;角度

表示軌跡向量

1212=1。相似度sim的取值範圍為[0,1]。當sim=0時,表示兩者完全不相同;當sim=1表示兩者完全相同。相似度值越高，表示軌跡點與參考基線的相似程度越高，其軌跡點線性平滑度也越高。

2.2.2 濾選閾值分析

軌跡濾選最關鍵的一步是如何設定濾選閾值。假設相似度閾值與GPS定位精度存在某種函數關係如下

式中，

表示GPS軌跡數據的定位精度。當濾選數據的定位精度為

時，即可通過式(4)得到相應的相似度閾值。為了進一步理清相似度濾選閾值與數據定位精度之間的關係，本文在文獻[

]的基礎上，通過對不同採集區域、整體定位精度不同的大量低精度GPS軌跡數據及其同步高精度DGPS軌跡數據(精度為厘米級)的相似度進行計算，分析低精度軌跡點的定位誤差及其相似度的關係。在相似度計算過程中,採用式(3)所示相似度評估模型，權重參數參考文獻[

]，而軌跡點與其真值之間的距離參數|

k

′k|是該軌跡點的定位誤差。大量試驗結果表明，GPS軌跡數據的相似度與定位精度呈現穩定的指數分佈，如下

式中，a、b、c分別是相似度與定位精度函數關係式的係數，其具體值與相似度評價模型內距離和角度的權重係數息息相關，而與原始GPS數據集的整體定位精度不相關。因此，無論是來自哪種型號的GPS接收機，只要採用統一的相似度評價模型，則GPS數據定位誤差與GPS數據和其理想值之間相似度之間的函數關係是確定的。GPS軌跡點與參考基線之間的相似度實際上與GPS軌跡點與其真值之間的相似度存在差異，但是當參考基線被作為參考基準時，這種衡量GPS軌跡點與參考基線之間的相似度閾值可採用式(5)來確定。當濾選GPS軌跡數據的期望精度為τ時，可計算出相似度濾選閾值為f(τ)。

3 試驗分析

本文以武漢市作為GPS軌跡數據採集區域，利用多輛GPS測量車分不同周期對武漢市郊區和市區進行數據採集，其中測量車內的GPS接收器包括：Trimble R9、洛基山手持GPS接收器、智能手機(華為、iPhone 5、 魅族等)。所獲取的GPS數據主要包含3類：一類是由Trimble R9採集的低精度GPS軌跡數據，定位精度為5~10 m，採樣間隔為1 s；一類是由手持GPS接收器採集的低精度GPS軌跡數據，定位精度為5~10 m，採樣間隔為1 s；一類是由手機採集的GPS軌跡數據，定位精度為10~15 m。這3類數據的同步高精度數據由CORS基站系統採集，定位精度為0.05 m，採樣間隔為1 s。試驗數據一共包含900萬個GPS軌跡點，採集周期為1周，採集區域遍布武漢市郊區和市區，如圖 6所示。

在下述試驗中，低精度GPS軌跡數據將被作為待濾選數據，高精度DGPS軌跡數據(定位精度為厘米級)將作為參考值，以便對濾選結果進行評價和檢驗。

3.1 軌跡分割

按照軌跡分割演算法，需要對待分割軌跡的圖形複雜度進行計算，然後確定分割閾值。在確定每一條軌跡的分割閾值前，需要對常量α和β 賦值。α和β根據用戶需求設定，本文根據現有交通規則和道路建設標準，將常量α和β分別設為45°和30 m。每一條軌跡的最終分割閾值則通過計算該軌跡的圖形複雜度進行自適應確定。試驗結果如圖 7所示，其中實心圓表示原始的GPS軌跡數據，星型符號表示分割點。在進行濾選時，由於分割點在角度與距離上與其他軌跡點存在較大的差異，因此可以將其首先作為異常值去除，然後再對子軌跡段進行濾選。

軌跡濾選閾值決定了最終濾選數據的整體精度。本文利用文獻的模型，度量距離和角度因素對GPS測量值定位精度的結果，將相似度評價模型的權值分別設為0.87和0.13。從原始數據中選擇一部分採集於不同區域、擁有不同誤差分佈的低精度GPS軌跡數據作為試驗數據，分析這些GPS數據與其參考值的相似度及其測量誤差之間的函數關係(由於試驗數據採集於城市道路，真值獲取相對困難，因此在計算過程中將定位精度為厘米級的高精度差分數據作為GPS數據的參考真值)，確定相似度閾值和GPS定位精度函數模型的相關參數。試驗結果表明，不論GPS軌跡點集的定位精度是多少，每一個低精度GPS軌跡點的定位精度與其真值的相似度值遵從指數函數關係，其中係數

=1，

=-0.267 1，

=0，見

。

圖 8(a)的試驗數據採集於城市遮擋路段，圖 8(b)的試驗數據採集於城市半遮擋路段，其GPS接收器為Trimble R9。圖 8表明，即使GPS軌跡數據集整體誤差分佈不一樣，定位精度也存在差異，但是GPS軌跡數據的相似度及定位誤差存在穩定的指數分佈。另外，通過計算，兩類數據集的相似度與定位精度和指數模型的擬合相關度為0.992及0.986。因此，確定濾選數據的期望定位精度后，可利用GPS軌跡點的定位精度與其參考值的相似度指數函數關係式計算濾選閾值，見表 1。

表 1 濾選數據的期望精度與其對應的相似度閾值Tab. 1 The expected precision of filtering data and the corresponding similarity threshold

表選項

根據濾選演算法，構建子軌跡段的參考基線向量，計運算元軌跡段內各GPS軌跡向量與參考基線向量之間的相似度。在相似度計算過程中，距離和角度權值的大小與相似度閾值分析一樣都設定為0.87、0.13。然後，根據表 1的相似度閾值依次對原始GPS數據進行濾選(見圖 9)。

圖 9表示了試驗區內一部分軌跡數據進行分割后構建參考基線，然後按照濾選閾值進行濾選后的結果。其中，圖 9(a)展示了子軌跡段的參考基線，圖 9b反映了濾選閾值設定為3 m時的濾選結果。

3.4 濾選評價

為了進一步驗證分割濾選模型方法的有效性，本文對試驗區內的所有低精度GPS軌跡數據進行濾選，如圖 10(a)所示。通過比較濾選數據與其真值，計算不同閾值約束下獲取的濾選GPS數據測量誤差的平均值和標準差，見表 2。

表 2 濾選的GPS軌跡數據整體定位精度評估Tab. 2 Overall positioning accuracy evaluation of filter selected GPS trajectory data

表 2結果表明，分割-濾選模型可以實現眾源車載軌跡數據按需濾選，且經過濾選后原始數據的質量得到不同程度的改善，然而該方法同樣存在局限性。首先，當期望濾選精度為1 m或者更高時，濾選數據的定位精度無法滿足濾選需求，例如，對於3種GPS接收器採集的原始數據集，當濾選期望精度為1 m時，所濾選結果的整體精度與期望精度相差甚遠；其次，濾選數據最終的濾選結果與原始數據集內數據的定位精度息息相關，即原始數據集內如果沒有包含高精度的軌跡點，則該方法就會失效，如，由手機採集的GPS軌跡數據，其定位精度較低，導致濾選結果的整體精度與期望精度之間存在相對差異；最後，如果一條子軌跡段內的所有軌跡點定位精度都非常低，且保持了高度一致性，那麼就會導致參考基線出現錯誤，從而濾選結果失效。在未來的研究工作中，本文將繼續對眾源軌跡數據按需濾選進行研究。

4 總結

本文在國內外GPS軌跡數據優化方法的基礎上，提出了一種基於分割-濾選模型的眾源車載GPS軌跡大數據自適應濾選方法。該方法可以基於信息提取精度需求，從原始GPS軌跡數據集中濾選出滿足期望精度的軌跡數據。試驗結果表明，該方法可以實現眾源軌跡大數據按精度需求濾選，降低數據冗餘度，為未來不同精度需求的信息提取提供可靠的數據源。然而本文所提方法同樣存在局限性：①當期望精度高於原始GPS軌跡數據集內數據的最高精度，那麼濾選結果與期望精度存在較大差異；②當原始GPS軌跡數據集內數據精度達到期望精度，但其比例相對較少時，濾選結果不理想。未來研究中，本文將進一步通過分析低高同步GPS軌跡數據的空間特徵，對分割-濾選模型進行優化。

【引文格式】唐爐亮，楊雪，牛樂，等。 一種眾源車載GPS軌跡大數據自適應濾選方法[J]. 測繪學報，2016，45(12)：1455-1463. DOI: 10.11947/j.AGCS.2016.20160117

權威 | 專業 | 學術 | 前沿

微信投稿郵箱 | [email protected]

歡迎加入《測繪學報》作者QQ群： 297834524