一種基于聚類及幾何特征的北斗軌跡糾偏抽稀方法

周雅靜 王得舉

（1.寧波城市職業技術學院 浙江省寧波市 315000 2.上海普適導航科技股份有限公司 上海市 200000）

北斗定位終端在接收信號差、外界干擾等因素下，會出現位置漂移現象。漂移現象會造成航程數據顯著增加，出現較大的統計錯誤；同時軌跡位置在前端UI 渲染展示時，會出現雜亂無章的連線，UI 效果也不美觀。因此需要研究對漂移點的糾正。

北斗定位終端在上報位置的時候，一般都是定時回報位置數據，在有地面通信網絡的情況下，其報告周期一般比較小，會上報大量的數據。大量的點在對外輸出及展示等情況下是不利的。需要尋找關鍵有價值的位置點并保留下來、剔除不影響整體軌跡的低價值位置點，來整體提升系統的效率。

本文通過對位置聚類及幾何特征的研究，形成一種能對軌跡點進行糾正、抽稀的方法，使得軌跡展示效果快速、平滑并保留重要的輪廓特征點。

1 糾正算法

發生發散漂移的判定規則是在較短的時間間隔內，位置發生劇烈的變化。

對于一批待糾正的軌跡點序列，每一點其包括的元素為經度、維度、時間等屬性。軌跡序列使用P={p1,p2,……,pn}表示，其中pi表示某點的相關信息。糾正算法采取滑動軌跡序列窗口方式[1]，滑動窗口是指在軌跡序列中，截取的固定長度的連續子序列，并不斷向前推進窗口滑動，完成序列的遍歷。

滑動窗口長度以WinLen 表示（默認5 個點），設計目標在一個滑動窗口長度內，可以糾正一個軌跡點的發散漂移。

從P={p1,p2,……,pn}中，取第一窗口作為開始滑動窗口。系統默認開始窗口序列點未發生漂移現象。待檢測點為緊接著該窗口內的下一點。計算待檢測點和第一窗口最后點的時間間隔TDF，時間間隔閾值是系統給定的超參數。如果時間間隔TDF 大于間隔閾值，不進行糾正算法，窗口向前滑動一位作為新的窗口，窗口的元素始終為WinLen 個。待檢測點下移一位。重復待檢測點和第一窗口最后點的時間間隔判斷。

如果時間間隔TDF 小于設定參數，則進行新的距離判斷流程：計算滑窗內相鄰兩點的球面距離間隔，求其窗內距離間隔平均值記為APW，并計算待檢測點和滑動窗口最后點的位置間隔PDF；如果PDF 小于APW 的設定倍數（默認2.0），認為不是漂散點，繼續采取滑窗和檢測點都前移一位的方式，繼續采取上述先判定時間后判定距離的方式。如果PDF 大于APW 的設定倍數（默認2.0），認為是漂散點，采取差值的方式進行位置糾正，糾正的方式是取滑窗內后兩點修正。修正公式為：

x,y 分表表示經緯度。當進行差值糾正時，為減少累計效應，影響整體軌跡效果，這時候整個窗口向前滑動WinLen 個單位，待檢測點向前移動WinLen 個單位。開始新的檢測流程。

2 形成骨架

從P={p1,p2,……,pn}中取子序列P1={p1,p2,……,pi}、 P2={p1,p2, ……,pi+1}。計算P1 中任意兩點最遠距離為D1MAX，計算P2 中任意兩點最遠距離為D2MAX；如果D2MAX-D1MAX 小于給定聚類距離超參閾值，認為pi+1點的加入P1 不會改變P1 的聚集態勢，可以繼續檢測下一個點，因此這時候 i=i+1，增加新的一個點到P1、P2 子序列中，重復上述檢測；如果D2MAX-D1MAX 大于給定聚類距離超參閾值，認為pi+1點不能加入P1 子序列中；這時候P1 子序列的質心點pm代替P1 子序列，P1 原點位被抽稀掉。新選取子序列P1，P2 在i 序號的基礎上作為起點，重復計算直到P 序列被遍歷完全。

圖1：拐點示意圖

圖2：折點示意圖

圖3：未處理的漂點

求出質心點計算公式：

3 骨架抽稀

軌跡上的特征點是指描述軌跡走向、輪廓的重要點。通常是拐點或折線點，重要的點在抽稀過程中要保留，只能抽稀掉非重要的點。

拐點，又稱反曲點，在數學上指改變曲線向上或向下方向的點，直觀地說拐點是使切線穿越曲線的點，即連續曲線的凹弧與凸弧的分界點。若該曲線圖形的函數在拐點有二階導數，則二階導數在拐點處異號或不存在。

通過相鄰的四點（A,B,C,D）進行檢測，對（AB,BC,CD）線段集，判斷（ABXBC）、（BCXCD）叉乘結果是否相異來判斷[2]。

對于折線點，采用三點來檢測夾角∠ABC 來判斷。∠ABC 通過計算|AB|，|BC|，|AC|線段長度，反余弦函數來計算完成。系統給定兩個角度閾值超參。一個是較大角度閾值，一個是較小角度閾值。自適應選擇其中之一作為當前閾值進行角度檢測。當∠ABC 小于當前角度閾值的時候。認為點B 是折線點，在抽稀過程中要保留。

自適應選擇作當前角度閾值的策略方法是：

當前點B 被抽稀掉的時候，說明下一個點對于保持輪廓相對重要，因此當前角度取較小角度閾值，增加下一點被保留的可能性；

當前點B 被作為重要點保留的時候，下一個點對于保持輪廓不重要，當前角度取較大的角度閾值，減少下一點被保留的可能性。

4 實驗效果

在圖3 為原始的未處理的漂點，可以看到漂移比較嚴重。經過算法糾正后，漂點得到糾正，效果良好，如圖4 所示。

圖5 為原始軌跡圖，有2257 個點位；圖6 為經過算法計算后的點位，僅有1029 個點位，相對原始數據，數據量大幅度減少，同時保留的軌跡的特征和輪廓。

圖4：糾正漂點后的軌跡

圖5：2257 個的原始軌跡

圖6：抽稀后軌跡1029 個點