顧及航向角變化的軌跡丟失點補全方法

李 翔, 李瑞祥

(1.信息工程大學 地理空間信息學院，河南 鄭州 450001；2．31682部隊，甘肅 蘭州 730000)

隨著便攜式GPS采集設備的廣泛使用，大量反映移動載體及其用戶的實時軌跡數據被積累。這些軌跡數據能夠有效地反映移動對象的行為特征和規律習慣等深層信息[1-3]。然而在數據采集過程中，GPS設備會受到多路徑效應影響及一些明顯遮蔽物的干擾，特別是在當今立體化的大都市，衛星信號往往會被高大樹林、立交橋或者高層建筑物等遮蔽物干擾，造成一定時間段內軌跡數據的缺失[4]。軌跡數據的缺失無論是對后續的軌跡行為分析挖掘還是軌跡特征提取或軌跡匹配都造成較大影響，同時制約軌跡數據的使用性和有效性，因此軌跡缺失補全方法研究成為國內外專家學者的研究焦點[5-8]。

按照通行區域有無路網地圖，將軌跡缺失的補全方式分為兩類情況。第一類是路網已知條件下的軌跡補全，該情況下通常根據軌跡的具體特征結合多種地圖匹配算法進行軌跡點的補償和修正，具有良好的匹配修正效果[9]。第二類是當前通行區域路網地圖未知時，軌跡補全的問題相對復雜，有些問題通過時間序列中的值缺失方法解決[10]，有些問題通過矩陣填充的方法解決[11]，還有些問題根據實際情況運用數據挖掘的方法進行分析[12]。不同于傳統的統計數據，軌跡數據具有經緯坐標、速度、方向等多維空間信息，一方面由于軌跡數據的缺失并不是隨機的，另一方面由于信號干擾情況的不確定性導致數據缺失的時間相對較長，因此以軌跡聚類或者簡單插值的補全方法并不能直接應用于軌跡數據的修補當中去[13-14]。針對軌跡數據的特點，徐超等提出了一種個人出行軌跡中軌道交通段GPS信號缺失修補算法，借助站點的語義信息來進行缺失軌跡補全[15]。按照軌跡重建的規律，馮濤采用隱性馬爾可夫模型對軌跡進行還原[16]。Shen根據運動軌跡的特征規律分別采用基于面積比相似度和上下文歷史信息的方法進行軌跡缺失數據的補全[17-18]。Li Yang則以小采樣的GPS軌跡樣本作為參考，通過先驗知識進行缺失軌跡的糾正和修補[19]。潘苗苗等人提出一種基于統計推斷的軌跡濾波方法，在不依賴路網數據的條件下，構建規則推斷模型，通過濾波的方法完成軌跡數據的處理[20]。Tong等人基于互聯網上公交車行駛軌跡數據樣本設計一種軌跡數據提取和缺失數據恢復的框架，按照軌跡聚類、軌跡清洗和軌跡連接三步驟，通過結合軌跡上下文信息進行數據連接和線性插值，取得良好的修補效果[21]。

以上補全軌跡數據方法在一定的領域內都有較好的應用效果，然而在路網未知的條件下，尤其是一些無法顯示的特殊路段(例如住宅小區內部、鄉鎮曠野或者自由空間等)的地圖，其軌跡數據缺乏歷史規律和道路規則性，大多數缺失的軌跡會被舍棄或者簡單預估處理，嚴重影響軌跡信息的準確性和可用性[22]。基于上述問題，本文結合軌跡的航向角變化提出顧及航向角的軌跡丟失點補全算法，針對一定時間段內的軌跡丟失數據進行補全和修復。

1 軌跡丟失點的分類及判斷

1.1 單個面目標變化類型描述

數據冗余是指重復出現在一個數據集合中的數據[23]。而數據采集過程造成數據冗余的因素有很多，例如數據采集車在行駛過程中遇到道路施工、交通擁堵等情況車速較低時，GPS接收機仍會按照采樣間隔繼續接收點位坐標數據；還有當GPS設備出現故障或者受外界干擾出現信號突然中斷時，其在短時間內仍會重復記錄最后一個定位點的坐標數據[24]；此外，復雜城市路況以及交通信號燈的限制等引起的臨時停車，同樣會產生許多不必要的冗余數據[25]。冗余數據的存在會影響后續軌跡的可用性，其次這些不必要的軌跡數據點顯示在地圖上則會形成“毛刺”，在一定程度影響了可視化的效果，因此必須要將這些冗余數據點刪除。

本文在數據采集過程中設定的采樣間隔為1 s，按照平均30 km/h的行車速度計算，一般相鄰的數據采集車軌跡點之間的直線距離在10 m左右。因此設定閾值dmin對軌跡采集點進行冗余判斷，dmin表示數據采集車輛1 s內行進的距離，如圖1所示。假設點Pi和Pi+1為采集到某條軌跡上的相鄰兩點，由于兩點坐標已知，計算出兩點間的直線距離d，若兩點間距離d小于間隔閾值，即d

圖1 冗余數據的處理規則

1.2 軌跡丟失點的判斷規則

當數據采集車經過茂密林蔭道、高大建筑群、立交橋等路段時，GPS衛星信號會受到不同程度的干擾甚至中斷，其數據觀測質量相對較差，經過RTK系統動態差分計算后會出現一定區域內的數據空白和缺失；此外，如果RTK系統的數據通訊傳輸出現臨時故障，造成流動站接收機無法獲取被測點的觀測數據，也會導致短時間內的數據中斷，引起采集數據丟失。如圖2和圖3所示，兩個采樣軌跡點之間較大的空白區域，即是存在數據丟失。

圖2 軌跡數據丟失點示例1

圖3 軌跡數據丟失點示例2

本文將這些缺失的觀測數據點稱為丟失點，由于采樣率為1 s/次，通過判斷相鄰兩個采樣點之間的采樣時間間隔(超過2 s即存在丟失點)或是按照1.1節的相鄰距離進行丟失點判斷。如圖4所示，圖中點P2和點P3之間的距離d超過了閾值，那么這兩點之間的虛線區域范圍內則認定出現了數據丟失。

圖4 軌跡數據丟失點的判斷規則

2 顧及航向角變化的軌跡丟失點補全方法

2.1 航向角對軌跡丟失點的影響

數據丟失破壞了軌跡的完整性和連續性，會對后續的數據組織管理以及輔助定位匹配計算產生不良的影響，因此需要進行丟失點數據的重構和補全[26]。針對采集過程中較小的空白區域，通常采用線性插值方法進行數據坐標計算及數據編輯。而對于較長空白時段的丟失點數據，則需要通過丟失區域前后相關點進行擬合后再插值，并結合當前區域其他形式的道路數據(如遙感影像圖、Google地圖等)進行補充和糾正[27]。無論數據空白區域大或小，都要結合數據丟失前后區域的采集點數據信息進行丟失點的計算和分析，為了保證軌跡線性的一致性且減少計算量，假設在插值過程中數據空白區域中各丟失點的采樣間隔是相同的，即在補全的路段上呈均勻分布。圖5中距離數據丟失區域最近的前后兩點為P2，P3(后文簡稱為“前后點”)，d12和d34分別為前后點的采樣間隔，通過它們各自的前后點狀態可以計算出當前的行進趨勢和航向角α2，α3，即采集經過該點的速度方向，那么根據α2和α3的異同可以將丟失點補全方式分為兩種情況。

圖5 丟失點前后點航向變化較小的情況

(1)

(2)

(3)

式中：β為前后點連線方向與前后點速度方向的夾角;j為當前插入點的ID，j=1,2,3,…,n。

根據式(3)的插值計算方法，可以簡單快捷獲取插入點的坐標，且精度可以滿足應用，大部分情況下的數據丟失空白區都可采用該方法進行補全。但該方法只適用于前后點直線距離不大且丟失點位于前后點連線上的情況，如果出現距離較大或者丟失點不在前后點連線上的情況時，還需要結合該地區的其他數據源信息進行補充和糾正。

如圖6所示的幾種特殊路況的數據丟失區域，圖6(a)為數據空白區域中數據采集車輛經過環形立交橋下層路段造成數據丟失；圖6(b)為數據空白區域中數據采集車輛為了避開施工、禁行、擁堵或者有障礙建筑的路段進行了繞行；圖6(c)中前后點的縱向距離較大，說明數據采集車可能通過多次轉彎進入了一條新的道路。這些特殊路況的數據丟失，如果只采用一般線性插值方法，就會得到錯誤的插值結果，造成采集到的實際軌跡數據不準確，影響后續輔助定位匹配的結果。而圖6(d)中的丟失點軌跡長度如果不長，可認為是行駛過程中駕駛員進行了超車或者避讓等行為，可將該軌跡擬合為直線路段并按照式(3)的方法進行插值計算。

圖6 幾種特殊路況的數據丟失區域

2)數據丟失區域前后點航向變化較大，即|α2-α3|>30°。與情況(1)不同，此時前后點速度方向之間有一個夾角，可記為α，如圖7所示。若α較小，則前后點行駛方向變化不大，可能是超車或者避讓行為引起的，可按照情況(1)的方法進行處理；如α較大(本文取為α=30°作為閾值)，則采集車輛的行駛方向發生了變化，通常是完成了一個轉彎的動作。此時如果仍按照情況(1)的方法進行丟失點插值計算將得到錯誤的結果，因此需要通過前后點的坐標和速度方向等信息進行擬合計算，從而確定出丟失點的位置和分布。

圖7 丟失點前后點航向變化較大的情況

由于轉彎過程中采集車輛的軌跡是一條曲線，利用局部多項式法進行擬合并插值。假設數據采集車的采樣間隔不變，選取前點P2向前(包括P2在內)和后點P3向后(包括P3在內)k個已知采集數據點，構造y=f(x)的關系多項式

(4)

式中：ai(i=0,1,…,2k-1.)為待定系數。根據2k個已知點，利用最小二乘法可計算出各系數值，從而獲得擬合曲線方程，再根據采樣間隔即可確定出丟失點的坐標位置。

圖8 彎曲弧線軌跡丟失區域

2.2 軌跡丟失點的補全方法

由于數據采集車的行駛方向發生了較大變化，一般情況下認為是完成了轉彎行為并進入了新的路段，也不排除一些盤山公路或者繞湖公路等特殊情況。根據道路設計規范和準則，道路線性一般是由直線、緩和曲線和圓曲線組成的，結合車輛駕駛的常識，轉彎行為的車輛行駛軌跡應為道路中的圓曲線部分。因此，為了保證采集軌跡的平滑過渡和完整性，本文將情況(2)丟失點的補全方法分為兩步，第一找到圓曲線的起止點，第二擬合出轉彎曲線并進行插值，獲得丟失點位置。

圖9 圓曲線的起止點

(x-long0)2+(y-lat0)2=R2.

(5)

那么根據該段圓曲線的弧線長度，便可得知該段圓曲線上的丟失點數量，其計算方法為：

(6)

(7)

最后根據圓曲線的方程和丟失點的數量，通過二分法循環插值計算便可補全圓曲線上的數據丟失點。

圖10 圓曲線的擬合插值結果

對于數據丟失點的坐標數據補全完成后，還要根據前后點的具體情況相應補充屬性數據信息，以保證數據的完整性。上述數據丟失的補全方法能夠適用于大多數信號干擾或者遮蔽引起的數據丟失，然而丟失點的坐標位置都是根據前后數據采集點的參考信息進行分析和確定的，針對數據丟失較小的區域效果較好。但因為前后點提供的狀態信息有限，用于數據丟失區域較大或者路況比較特殊的路段時，存在一定的不可靠因素，會造成丟失點插值和補充有誤，需要通過當前地區的其他輔助道路信息和后續更多的采集點進一步修正。

3 實驗分析

本文采集的軌跡數據包括北京市西五環晉元橋阜石路地區以及密云地區的車載GPS-RTK軌跡數據集。數據的采集時間為2016-03—04期間，數據的采樣頻率為1 s/次，從GPS接收機的測量手薄中導出后，采用.txt格式儲存，共有73 347個采集軌跡點，每個軌跡點主要包括經度、緯度、高程、時間等數據類型。

為了消除軌跡數據采集過程存在的多種不確定因素造成的誤差，滿足實際軌跡在計算機中準確的抽象表達，需要對采集到的原始GPS-RTK軌跡數據進行預處理，并對處理后軌跡數據的精度進行評價分析。

3.1 算法的性能分析

從采集到的GPS-RTK軌跡數據集中提取一段有較高遮蔽物的數據，如表1所示。

表1 出現丟失區域的軌跡數據

數據采集車行駛過程中，由于茂密樹林、高大建筑物或者立交橋的遮蔽，引起GPS接收機的信號干擾或者短暫中斷，出現表1中點N153和點N154之間的數據丟失。按照前文所述的數據處理方法，需要首先判斷數據丟失區域前后點處的航向變化情況，根據點N153和點N154處的航向角計算，其航向變化小于30°，則認為此時采集車行駛在直線道路，采用情況(1)的方法插值計算丟失即可，經過插值計算的結果如表2所示。

表2 數據丟失區域的插值補全結果

圖11是進行丟失點補全處理前的直線路段軌跡數據；圖12是經過丟失點補全處理后的直線道路軌跡數據。

圖11 丟失點補全處理前的直線路段軌跡數據

圖12 丟失點補全處理后的直線路段軌跡數據

而針對丟失區域前后點航向變化較大情況，則認為采集車完成了轉彎或者駛入了新的道路，倘若丟失區域過大還要根據實地情況考慮道路的幾何形狀進行具體處理。圖13是進行丟失點補全處理前的轉彎道路軌跡數據；圖14是經過丟失點補全處理后的轉彎道路軌跡數據。通過對軌跡進行丟失點補全處理，保證了軌跡的連續性和完整性。

3.2 與其他算法的對比實驗

為了驗證本文提出算法的性能，對實驗區域內的多條軌跡數據分別采用平均插值算法、K-modes聚類算法、文獻[29]中的最小二乘支持向量機算法(LSSVM)和本文算法進行軌跡補全修復仿真實驗，分別對4種算法的軌跡點補全召回度、與真實點的標準差、時間等方面進行統計分析。

圖14 丟失點補全處理后的轉彎道路軌跡數據

其具體實驗統計結果如表3所示。

表3 4種軌跡補全算法的比較

圖15表示4種算法補全軌跡缺失數據的結果。其中紅色線為本文算法結果，黑色線為實際地圖上的缺失軌跡段，綠色線為平均插值算法的結果，紫色線為K-modes聚類算法的結果，藍色線為LSSVM算法的結果。由圖可知(看出)，本文算法補全結果相對比較準確。

圖15 4種算法補全結果與原始軌跡的對比圖

此外，實驗還對比了4種算法的補全效率，由圖16中可以看出，隨著軌跡丟失點數量的增多處理時間也會隨之增長，在軌跡丟失點數量相同的條件下，平均插值算法的處理速度最快，而K-modes算法處理所花費的時間最長，而LSSVM算法的變化不確定性較大，這是由于機器學習效果取決于輸入軌跡樣本的質量，軌跡質量高計算效率也隨著提高，反之減小。相比較而言，本文算法則具有相對較好的補全效率，且增長曲線較為穩定。

圖16 4種算法軌跡補全時間與點數量的關系

綜上所述，傳統的插值算法計算效率較高，但是補全的準確度有一定不足，聚類算法在穩定性和準確性上具有一定優勢但需要一定處理時間，而作為當前熱門的基于機器學習的LSSVM算法從結果上來看，需要較好的軌跡數據源作為學習樣本，如果數據樣本質量參差不齊，則補全結果會出現很大的不確定性。本文提出的算法軌跡丟失點處理結果綜合性能較為穩定，能夠適用于路網未知條件下的軌跡丟失點的補全修復工作。

4 結束語

針對GPS獲取軌跡數據的過程中會因為信號丟失或者干擾等影響造成軌跡數據的缺失問題，本研究結合軌跡航向角的動態變化情況，提出一種顧及航向角變化的丟失軌跡點補全方法在路網未知時(尤其是地圖無法表示道路信息)快速準確地對軌跡丟失點進行補全和修復；根據軌跡丟失點的情況分類，界定丟失點的判斷規則；針對軌跡丟失前后節點的航向角變化，設計不同的補全策略和具體方法；最后利用提出算法對不同類型的軌跡丟失情況進行補全實驗分析，結果表明在路網未知的條件下，該算法能夠快速、準確地完成缺失軌跡點的補全工作，具有一定的實用價值。

在軌跡丟失時間段較短的過程中，提出算法具有良好的作用特征，但倘若存在信號長時間缺失引起的軌跡點丟失，則會產生更多的不確定性，所以針對存在大量軌跡丟失的數據需要謹慎采用人工補全和修復，盡量選擇去重新采集數據或者摒棄不用，以免造成原始數據的錯誤。

未來研究工作包括：①路網未知路段的軌跡測量可以采用慣性導航等自主定位方法進行數據獲取，在增加數據源的同時也可以采用軌跡匹配的方法進行軌跡補全；②針對一些比較特殊的路段還需要配合實地一些交通規則、物理限制等具體先驗知識的應用，提高軌跡補全結果的真實性和準確性。