基于UCR-DTW的地磁序列定位算法

金俊超, 馬昌忠, 陳國良, 王俊鵬, 劉 奔

(1.中國礦業大學 自然資源部國土環境與災害監測重點實驗室,江蘇 徐州 221116; 2.中國礦業大學 環境與測繪學院,江蘇 徐州 221116)

目前,基于智能手機的室內定位技術有多種,如Wi-Fi技術、視覺技術、藍牙技術、超寬帶(ultra-wide band, UWB)技術、聲波技術、偽衛星技術、行人軌跡推算技術和5G技術等,但是這些技術都不完善,存在一些缺點。例如,Wi-Fi與藍牙定位技術精度低且受多路徑影響,UWB與偽衛星技術輔助設施布設成本昂貴,聲波定位技術的穿透能力較弱,行人軌跡推算技術具有誤差累積等。

地磁定位作為無源自主定位技術,具有不受多路徑效應與人體遮擋影響[1]、地磁場隨時間變化穩定且任意位置都具有獨特的地磁強度與方向[2]等優點,并且在室內建筑中由于鋼筋混凝土等材料的影響,室內地磁特征明顯,更有利于定位[3]。其中地磁序列定位由于精度高于點定位,相關研究成果豐富。文獻[4]提出一種基于軌跡匹配的地磁定位系統,該系統可以確保在沒有慣性傳感器輔助下,利用改進的Smith-Waterman算法實現局部路徑匹配,然后利用改進的Dijkstra模型完成行人軌跡構建,實現大型室內場景的定位;文獻[5]提出一種注意力機制引導下的基于多尺度信號序列的室內定位網絡,基于循環神經網絡提取各個尺度下的特征信息,然后利用注意力機制將多尺度特征拼接，生成融合特征來完成匹配定位,但是深度學習運算量較大,目前很難在智能手機端完成算法運算;文獻[6]提出了基于智能手機的地磁定位系統,首次將動態時間規整(dynamic time warping,DTW)算法應用于地磁序列定位中,精度達到80%以上,但是DTW算法的計算復雜度較高,導致計算效率低,無法滿足室內定位實時性的需求;文獻[7]針對地磁匹配的時間成本高問題,提出利用Wi-Fi信號輔助縮小匹配搜索區域,極大提高了地磁匹配效率,但是Wi-Fi指紋建庫較為繁瑣,前期需要消耗大量時間;文獻[8]針對DTW算法計算復雜度高與實時性差問題,將快速動態規整(fast dynamic time warping,FastDTW)算法用于地磁定位,利用粗粒度化方法縮短序列長度,減小計算復雜度,計算完成后再細粒度化地磁預規整路徑,規整到原來地磁序列大小來實現定位。但是,目前在地磁序列匹配相關研究中,關于DTW算法計算效率優化問題的解決方法較少,還需要進一步研究。

針對目前基于DTW的地磁定位算法計算效率低和定位時間長問題,本文提出利用加州大學河濱分校(University of California, Riverside,UCR)優化策略[9]來提高DTW算法計算效率,序列匹配時先利用重排序策略對序列進行重新排列,然后利用級聯下界約束策略在DTW計算前進行約束,提前篩選指紋庫內待匹配序列,將篩選得到的待匹配序列進行DTW計算,并利用全局約束策略與DTW提前拋棄策略對DTW計算進行約束。本文將基于UCR-DTW的地磁序列匹配定位算法稱為本文算法,實驗結果證明,地磁序列匹配效率得到了較大的提升。

1 基于UCR優化策略的DTW算法

1.1 DTW算法原理

DTW算法作為一種時間序列數據的相似性度量算法,可進行一對多的相似性匹配,匹配準確率高于歐式距離[9]。假設2條序列長度分別為m、n,構建距離矩陣dm×n后,逐步計算累積距離D(i,j),直到D(m,n)計算完成,時間計算復雜度為O(mn),無法滿足室內定位算法實時性的需求。D(i,j)計算公式為:

D(i,j)=d(i,j)+min[D(i-1,j),

D(i,j-1),D(i-1,j-1)]

(1)

其中:i、j分別為2條序列上的對應序列點位置編號;i=1,2,…,m;j=1,2,…,n;d(i,j)為前一步的累積距離。

1.2 UCR優化策略

基于滑動窗口的DTW算法原理如圖1所示。序列檢索匹配時,減少算法時間計算復雜度的方式主要是減少DTW算法的矩陣搜索區域、縮短匹配的序列長度和減少DTW算法的重復計算次數。而UCR優化策略就是綜合了上述第1種和第3種減少計算復雜度的方法。在數據庫檢索匹配時,對DTW結果值的計算進行條件約束,實現對數據庫內序列的快速篩選,提高序列匹配效率,其策略可以概括如下。

圖1 基于滑動窗口的DTW算法原理

(1) 全局約束。對DTW算法的計算范圍進行約束,減少DTW算法的矩陣搜索區域。

(2) 下界約束。DTW下界(lower bound,LB)值LB(Q,C)與DTW計算結果值DTW(Q,C)滿足的不等式為:

DTW(Q,C)≥LB(Q,C)

(2)

其中:Q為查詢序列;C為待匹配序列。

利用下界計算復雜度低的優勢,首先計算LB值,當LB值大于閾值bsf時,提前拋棄參與本次匹配的子序列,減少DTW算法的計算次數。本文利用Kim下界[10]和Keogh下界[11]。

(3) 自適應下界拋棄。利用閾值bsf約束下界計算。當LB值超過閾值時,DTW計算結果值也大于LB值,表明該條待匹配序列不是最優匹配序列,可以進行拋棄,減少DTW的重復計算次數。

(4) 序列重排序。按標準化值調整參與Keogh下界計算的序列值順序,保證Keogh下界的LB值累加速度更快,達到下界拋棄條件,以達到加速效果。

(5) 下界計算對象轉換。改進Keogh下界,保證改進Keogh下界值LBKeogh2(Q,C)優于Keogh下界值LBKeogh(Q,C),滿足的條件為:

DTW(Q,C)≥LBKeogh2(Q,C)≥LBKeogh(Q,C)

(3)

(6)自適應DTW計算拋棄。利用Keogh下界歷史值對DTW結果值的計算進行約束,當前DTW計算累積值大于LB值時,可以提前拋棄匹配序列,減少完整DTW算法的執行次數。

(7) 級聯下界。利用不同下界計算復雜度從低到高進行計算,當計算復雜度較低的下界大于閾值時,可提前拋棄待匹配子序列,減少完整DTW結果值的計算次數。本文將Kim下界、Keogh下界和改進Keogh下界進行級聯。

2 地磁定位方法

2.1 地磁序列匹配定位原理

地磁序列匹配定位分為離線采集階段和在線匹配階段，具體流程如圖2所示。

圖2 地磁序列匹配定位流程

離線采集階段主要進行地磁指紋序列采集,將預處理后的地磁指紋序列與實際位置坐標建立映射關系,建立地磁指紋庫;在線匹配階段主要實時采集固定長度的地磁指紋序列,將預處理后的地磁序列與地磁指紋庫進行指紋序列比對,確定最優定位結果。

2.2 本文算法

基于UCR-DTW的地磁序列定位算法流程如圖3所示。

圖3 基于UCR-DTW的地磁序列定位算法流程

手機磁力計可以獲取某位置點磁場強度的三軸分量Mx、My、Mz。將三軸分量作為地磁指紋時,雖然精度高,但是易受手機姿態影響[4]。本文選取地磁模值M作為地磁指紋,其計算公式為:

(4)

在地磁序列匹配時,為確保兩條序列的空間覆蓋范圍基本一致,本文利用波峰檢測算法與Kim步長估計算法進行距離估計,獲取查詢序列。文獻[12]研究表明，2.5 m左右的地磁序列匹配時誤匹配現象較少,因此本文取2.5 m左右的地磁序列作為一個軌跡段進行匹配。當下界計算時,為了保證兩條序列長度相同,利用分段聚合近似算法(piecewise aggregate approximation, PAA)[13]對序列長度進行擴充與縮減。

假設查詢序列為Q,其長度為m,待匹配序列為C,其長度為n,其中n?m。最優DTW計算結果值作為閾值bsf實現自動更新。匹配時,對查詢序列Q進行標準化用于序列重排序,利用滑動窗口算法獲取待匹配子序列,以下界約束策略與下界級聯策略判斷是否對待匹配子序列進行提前拋棄;在Kim下界計算時,利用閾值進行條件約束,并以重排序策略和下界拋棄策略對2類Keogh下界計算進行約束;最后利用全局約束策略與DTW拋棄策略在DTW算法計算時進行約束,將計算返回的DTW結果值與閾值進行比較,更新最優閾值和對應序列坐標,獲取序列坐標最后一組坐標(x,y)作為當前定位結果。重復上述計算,獲取最優DTW計算結果值對應的定位坐標。

3 實驗與數據分析

本次實驗基于Matlab平臺,利用聯想Y7000P筆記本(搭載i7-10875i處理器)進行試驗。為了確保實驗數據的可靠性,本次實驗利用文獻[14]在伊利諾斯大學采集制作的MagPIE數據集對DTW算法、FastDTW算法與本文算法進行比較測試。數據集內包含無人車采集和行人手持獲取2類數據。為證明本文算法的實用性,實驗選擇行人手持模式,同時選擇面積為470 m2的Loomis實驗室的地磁數據。選擇第1條、第2條和第3條訓練序列作為指紋庫序列,3條序列的長度依次為4 541、4 092、4 318,3條軌跡左右間隔0.5 m左右,指紋庫內總序列長度為12 951,走廊總長度為100 m左右,地磁序列與指紋庫軌跡如圖4所示?，F實應用中,多種軌跡段與行走速度存在差異;為減少誤匹配現象出現次數,本文選取軌跡段為2.5 m的地磁序列進行算法測試。所有軌跡段均為正常行走狀態下(不存在奔跑等現象,只存在行走速度差異)獲取得到,軌跡近似直線行走,不存在原地踏步、轉圈等特殊情況。

圖4 指紋庫地磁序列和指紋庫軌跡

3.1 數據預處理

由于數據采集時已經對磁力計進行了校準,本次實驗主要對地磁數據中的白噪聲進行處理。利用小波變換算法對序列進行過濾,結果如圖5所示。

圖5 地磁序列濾波前后對比

由圖5可知,過濾后數據與原始數據基本一致,證明數據集的數據質量較好,滿足實驗要求。將獲取的地磁強度與數據集中Tango獲取的高精度實際地理位置進行一對一映射,構建地磁指紋庫。

3.2 算法運行效率

在測試集內,隨機選取100條軌跡長度2.5 m左右的測試序列進行匹配定位,在獲取軌跡長度基本不變的條件下,滑動窗口長度按照行人速度大小的不同進行隨機變化,基本保持在60～95左右。地磁指紋庫中存有3條路徑的指紋序列,共12 951條地磁指紋數據,每次定位都需要遍歷1次指紋庫,最后取定位時間均值作為最終定位時間,分別將本文算法與FastDTW算法、DTW算法進行比較,結果見表1所列。

表1 3種算法平均定位時間 單位:s

從表1可以看出:當指紋庫中的待匹配序列長度為4 092時,采用DTW算法和FastDTW算法的平均計算時間分別為2.311 9、2.636 6 s,在動態定位時,行人正常行走速度保持在0.69～1.82 m/s之間[12],每執行1次算法計算,行人將行走1.8～ 4.0 m距離,導致計算出的定位結果與實際行人位置差異較大,無法滿足實時定位的需求;而本文算法的平均時間為0.192 5 s,行人行走0.1～0.3 m左右,與實際行人位置差異較小,基本滿足實時定位需求；同時,隨著待匹配序列長度的不斷增加,DTW算法與FastDTW算法計算時間會隨之線性增長,而本文算法的計算時間增長較慢,且耗時極短。相比于DTW算法,本文算法的計算時間減少高達90%以上,可見UCR策略的加速效果;而FastDTW算法的計算時間無明顯提升(該現象已經在文獻[15]中進行了分析)。FastDTW算法的確能夠增速,但是對于查詢序列的長度存在要求,隨著查詢序列長度增加,FastDTW算法的增速才能夠體現,當查詢序列大于100以上時,FastDTW算法有明顯的提速效果。在指紋庫待匹配序列長度為4 092時,以滑動窗口長度為100、150、200進行實驗,結果見表2所列。

表2 不同滑動窗口長度下算法平均定位時間 單位:s

從表2可以看出,FastDTW算法隨著滑動窗口長度增加,增速效果明顯,計算效率也逐漸提升,但本文算法的計算效率還是明顯強于其他2種算法,同時滑動窗口長度增加對本文算法計算時間的影響較小。

3.3 算法定位精度

為研究本文算法對定位精度的影響,利用上述構建完成的指紋庫進一步進行測試。隨機選取100條測試序列,其軌跡長度為2.5m左右,序列長度不一(序列長度為60～95之間)。本文算法、DTW算法和FastDTW算法的定位誤差分布結果和累積分布函數(cumulative distribution function,CDF)曲線分別如圖6、圖7所示。

圖6 算法定位誤差分布

圖7 算法定位誤差CDF曲線

由圖6可知,本文算法和其他2種算法相似,都存在個別定位誤差極大的點,誤差保持在30 m以上,本文將其當作粗差進行處理。由圖7可知,當定位誤差達到25 m左右時,CDF曲線已經趨于平穩,即后續的定位誤差點發生了嚴重誤匹配,可視為粗差,本文利用聚類函數對其進行剔除。將本文算法、DTW算法和FastDTW算法獲得的定位誤差結果進行誤匹配率(V)、平均定位誤差(E)和均方根誤差(root mean square error, RMSE)計算,計算結果見表3所列。V、E、RMSE計算公式分別為:

其中:qmis為誤匹配序列數;qall為測試序列總數,本文qall=100;ei為每條測試序列的匹配誤差;n為序列總數,本文n=100。

從表3可以看出:3種算法的平均定位誤差基本保持一致;從RMSE看,UCR優化策略對于DTW算法的精度不會產生顯著影響,RMSE也基本一致;而誤匹配率保持在21%左右,這主要是由于單獨使用地磁強度作為指紋,導致地磁指紋特征在大區域內還是存在一定的相似度。

表3 3種算法誤匹配率和誤差對比

4 結 論

針對經典DTW算法計算效率低,無法滿足室內定位實時性的需求,本文提出一種基于UCR優化策略的地磁序列定位算法。該算法利用UCR優化策略對DTW算法進行優化,在保證定位精度基本不變的情況下,加速效果明顯;相比于DTW算法與FastDTW算法,在地磁序列匹配應用中,地磁序列匹配效率提高了90%以上。