基于改進Fast-DTW的多維地磁序列匹配算法研究

摘 要：傳統(tǒng)單點的地磁匹配定位算法運算量大，且定位時效性及定位精度較差。針對該問題，采用基于序列的快速動態(tài)時間規(guī)整算法Fast-DTW實現(xiàn)多維的地磁序列匹配，并利用最長公共子序列LCS的有序聚類進行優(yōu)化。離線階段通過坐標轉(zhuǎn)換法構(gòu)建四維地磁指紋庫，在線階段進行實時地磁序列匹配，獲得定位結(jié)果。實驗結(jié)果表明，該算法的定位時效性及精度均有提升。

關鍵詞：地磁室內(nèi)定位；快速動態(tài)時間規(guī)整算法；最長公共子序列；地磁指紋庫

中圖分類號：TN966；P318 文獻標識碼：A 文章編號：2096-4706（2024）08-0089-05

0 引 言

基于全球定位系統(tǒng)的室外定位技術(shù)已誕生多年，經(jīng)歷不斷革新幾乎已達到可以滿足人們在室外日常出行的最大需求。但對于室內(nèi)定位方面，該技術(shù)還存在一定的局限性，衛(wèi)星信號在傳遞過程中被建筑物內(nèi)墻體以及一些室內(nèi)設備等層層削弱，傳遞至室內(nèi)時信號已十分微弱，無法繼續(xù)滿足正常的定位需要，實現(xiàn)室內(nèi)精確定位仍需選擇其他信號源進行參與[1]。目前研究較為深入的室內(nèi)定位信號源，包括藍牙、Wi-Fi、超寬帶、射頻識別等，均需要一定的基礎設備在室內(nèi)進行部署，且均需要一定的更新以及維護保證其穩(wěn)定運行[2]。利用室內(nèi)地磁信息實現(xiàn)定位無須考慮這些成本，室內(nèi)地磁信號無處不在，且由于建筑物的影響，室內(nèi)不同位置的地磁信號的分布也各有差異；同時地磁信號在穩(wěn)定抗干擾、室內(nèi)外無縫定位以及多源融合定位方面也有一定的可研究性[3]。

目前基于地磁信息的室內(nèi)定位主要是通過指紋定位的方式實現(xiàn)，指紋定位方式又分為兩種，分別是基于序列的磁匹配定位（Sequence-Based Magnetic Matching Positioning， SBMP）以及基于單點的磁匹配定位（Single Point-Based Magnetic Matching Positioning， SPMP）[4]，對此國內(nèi)外許多學者均有研究。基于序列的磁匹配定位技術(shù)以動態(tài)時間規(guī)整算法為主要應用，Chen等人[5]采用非磁航向和磁航向組合，將慣性遞歸信息集成到地磁DTW中，并對準靜態(tài)和非準靜態(tài)范圍進行劃分，提高匹配成功率和位置修正可靠性。Zhao等人提利用智能手機和眾包技術(shù)收集磁軌跡數(shù)據(jù)構(gòu)建室內(nèi)地圖，通過DTW聚類和親和傳播算法軌跡融合實現(xiàn)精準定位。金俊超等人[6]使用UCR策略對DTW算法進行改進，通過序列重排序及約束策略提高計算效率的同時提升定位精度。

單點的磁匹配定位技術(shù)相較于序列匹配，面臨分辨率更低、工作量更大且對匹配算法的性能要求更高的情況，往往需要以大量的數(shù)據(jù)集訓練實現(xiàn)精確定位，因此該技術(shù)通常以機器學習方法為主要應用，如BP神經(jīng)網(wǎng)絡、貝葉斯、加權(quán)K近鄰算法等[7-9]。本文基于DTW算法實現(xiàn)基于序列的磁匹配室內(nèi)定位，針對傳統(tǒng)DTW算法定位效率及定位精度較差的缺陷，采用最長公共子序列（Longest Common Subsequence， LCS）的有序聚類進行優(yōu)化，構(gòu)建基于LCS-Fast-DTW地磁序列匹配模型，并通過實驗驗證該模型的定位性能。

1 多維指紋庫構(gòu)建

地磁室內(nèi)定位中，指紋定位的核心部分為離線階段及在線階段，如圖1所示。離線階段為地磁數(shù)據(jù)的采集、存儲，在實驗區(qū)域內(nèi)采集完整的位置信息以及對應的地磁信息，建立位置信息與地磁信息一一對應的數(shù)據(jù)庫即指紋庫；在線階段，通過智能手機在實驗路徑中獲取在線采集實時的地磁數(shù)據(jù)，利用匹配算法與指紋庫中的整體數(shù)據(jù)進行匹配，以此獲得最為接近的位置估計。由于室內(nèi)地磁場的分辨率較低，指紋庫中會存在較多不同空間位置對應相似地磁序列的情況，容易引起位置估計混淆，產(chǎn)生較大定位誤差[10]。因此，指紋庫的分辨率、匹配算法的性能都是實現(xiàn)精確地磁定位的關鍵因素。

在進行地磁數(shù)據(jù)的采集時，同一時間同一位置采集的地磁信息并不是唯一不變的，不僅僅受設備的硬件噪聲的干擾，最主要的原因是受采集設備本身姿態(tài)的限制。通過采集設備獲取的地磁X軸、Y軸、Z軸的數(shù)據(jù)是基于設備本身坐標系下的數(shù)據(jù)，該數(shù)據(jù)會隨著設備姿勢的變化而不斷變化，實際需要應用于室內(nèi)定位的地磁數(shù)據(jù)是基于地理坐標系下的穩(wěn)定的數(shù)據(jù)。因此通常有兩種方式來解決上述問題：

1）多數(shù)學者通過計算地磁模值的方式消除設備姿態(tài)的影響，計算式為：

（1）

其中，Mx、My、Mz分別表示智能手機采集的三軸數(shù)據(jù)。

2）還可通過坐標轉(zhuǎn)換的方法解決，即將采集的設備自身坐標系下的地磁三軸數(shù)據(jù)與旋轉(zhuǎn)矩陣相乘，即可獲得穩(wěn)定的地理坐標系下的三軸數(shù)據(jù)，可令 、、 分別表示轉(zhuǎn)換后的地理三軸數(shù)據(jù)。采集過程中手機姿態(tài)變化角度分別為俯仰角（φ）、航向角（γ）及橫滾角（θ）。該角度可直接由智能手機內(nèi)部的傳感器獲取。其轉(zhuǎn)換算式為：

（2）

其中，Cx、Cy、Cz分別表示俯仰角、航向角、橫滾角對應的旋轉(zhuǎn)矩陣。為進一步提升指紋庫的分辨率以及穩(wěn)定性，本文將位置信息與其對應的坐標轉(zhuǎn)換后的地磁三軸數(shù)據(jù)、地磁模值一起輸入構(gòu)建四維的地磁指紋庫。

2 LCS-Fast-DTW定位算法構(gòu)建

2.1 LCS算法

最長公共子序列（Longest Common Subsequence， LCS）通常被用來衡量數(shù)據(jù)之間的相似度，同時對于非線性序列在降噪及排列扭曲方面有較好的效果。使用智能手機在行走過程中采集地磁數(shù)據(jù)時，相同時間點采集的磁序列長度存在差異，且因設備以及外界因素，采集的數(shù)據(jù)不可避免地存在噪聲干擾，因此在進行序列匹配時可預先利用LCS算法找到最長的地磁數(shù)據(jù)子序列，抵消噪聲的影響，進一步提升算法的定位性能，LCS的具體計算原理如下。

假定存在二維數(shù)組D中存在序列X及序列Y，其中D[i]表示X序列中的前i個元素；D[ j]表示Y序列中的前j個元素，在此基礎上設定閾值σ，對于數(shù)組D的任意元素，可存在：

1）若X [i]與Y [ j]之間的距離小于預設的閾值，則D[i] [ j] = D[i-1] [ j-1] + 1，即在原有的最長公共子序列長度加1可得當前最長公共子序列長度。

2）若X [i]與Y [ j]之間的距離大于預設的閾值，則D[i] [ j] = max （D[i] [ j-1]，D[i-1] [ j]），即在原有及當前的最長公共序列中選取長度較大的那個。以此類推，直到可以計算出D的所有元素，最后C [n] [m]就是序列X和Y的最長公共子序列的長度。相似度S的計算式為：

（4）

其中，| LCS |為找到的最長公共子序列長度，| X |表示序列X的最長公共子序列的長度，| Y |表示序列Y的最長公共子序列的長度。

2.2 Fast-DTW算法

動態(tài)時間規(guī)整算法（Dynamic Time Warping， DTW）是一種根據(jù)序列之間的相似度進行匹配的算法，該算法可將兩個信號序列看作是在時間軸上分布的點序列，通過“扭曲”這兩個信號序列中的時間軸，可在所處不同時間間隔內(nèi)的信號之間找到其對應關系，因此被廣泛應用于語音識別、時間序列匹配和相似性搜索等領域。在地磁室內(nèi)定位中，需要利用DTW算法對實時采集的地磁序列與離線階段行人行走所構(gòu)建的地磁指紋庫中的序列組進行匹配。所構(gòu)建的指紋庫實際為一組較長的地磁序列，DTW的核心思想是創(chuàng)建一個代價矩陣，其中該矩陣的每個元素代表兩個地磁序列在某一點上的差異。該元素可用歐氏距離來表示，計算式為：

（5）

其中，m表示實時采集的地磁序列，Ml表示構(gòu)建的地磁指紋庫中第l個磁序列，d表示上述兩個序列之間的二維歐氏距離。隨后采用全局搜索的方式搜索通過代價矩陣的最短距離，同時設定一個滑動窗口，路徑的搜索空間被限制在該窗口，最終，計算出該路徑的所有點的代價之和，即累計距離之和，當這個距離總和最小時，即可確定兩個序列之間最佳匹配關系。

傳統(tǒng)DTW計算的時間以及空間的復雜度為N2，N為序列的長度，當定位面積較大時，相應的地磁序列的長度也較長，因此傳統(tǒng)DTW計算工作量巨大且效率隨之降低。因此在此基礎上，本文引入基于序列的快速動態(tài)時間規(guī)整算法（Fast Dynamic Time Warping， Fast-DTW）以降低計算的復雜程度。

Fast-DTW實際為DTW的近似解法，DTW算法通常直接對原始的序列進行處理及運算，F(xiàn)ast-DTW首先對原始序列下采樣處理，可設置下采樣率為k，因此每隔k個時間點取一個點，即可獲得新的較短的時間序列，在該較短的序列上運用傳統(tǒng)DTW算法，獲得初步序列粗略的對齊關系。隨后運用插值處理，將初步的DTW矩陣擴大到原始時間序列的長度，獲得在原始序列長度上粗略的對應關系。最后，在此基礎上對原始數(shù)據(jù)進行微調(diào)，以此獲得最終的最佳匹配關系。該方法可將計算的時間以及空間的復雜度降低為N，大大減少計算的復雜度。

2.3 LCS-Fast-DTW定位算法

由于地磁場的分辨率較低，在指紋庫序列足夠長時，會不可避免出現(xiàn)較多序列相似的情況；同時由于行走過程中的步頻不能保證統(tǒng)一，會出現(xiàn)部分數(shù)據(jù)丟失或產(chǎn)生額外數(shù)據(jù)情況的發(fā)生。因此Fast-DTW算法雖然可一定程度上降低計算復雜程度，但仍不能保證序列匹配的正確率，因此，本文利用最長公共子序列的有序聚類對齊其進行優(yōu)化，LCS算法的復雜性較低且可以更加精確的衡量地磁序列之間的相似性，具體優(yōu)化過程為：

1）數(shù)據(jù)預處理，對采集的地磁數(shù)據(jù)劃分整體樣本集以及測試集。

2）首先對所有測試集的地磁序列進行LCS相似度計算，獲得相應的相似度結(jié)果。

3）根據(jù)得到的LCSS相似度矩陣，使用K-means聚類算法來劃分參考指紋庫，獲得相似度最大的聚類標簽和各個聚類的中心點。

4）在獲得的聚類結(jié)果中運用Fast-DTW算法進行計算，選擇距離最小的參考序列，其對應的位置可認為是最接近測試序列的實際位置。

3 實驗與結(jié)論

試驗場地設在安徽理工大學空間信息與測繪工程學院的五樓走廊，該走廊長為54 m，寬為2.4 m，走廊較為空曠且無大型電磁設備等干擾，試驗場地具體情況如圖2所示。將整個實驗區(qū)域用1.2 m×1.2 m的網(wǎng)格均勻劃分，并通過往返勻速行走的方式在每個網(wǎng)格節(jié)點處采集地磁數(shù)據(jù)，直至將實驗區(qū)域內(nèi)所有位置的數(shù)據(jù)采集完畢。本文使用的采集設備為iPhone12，采集軟件為開源的物理采集軟件，可采集加速度數(shù)據(jù)、陀螺儀數(shù)據(jù)、地磁三軸數(shù)據(jù)等，采集頻率為50 Hz，每個點位采集15 s，采集過程中盡可能保證設備姿勢不變。離線階段數(shù)據(jù)采集完成后，規(guī)劃實驗路徑，在線階段在路徑中勻速行走并采集在線地磁數(shù)據(jù)，用于后續(xù)的磁序列匹配。

本文的實驗路徑從起點向西一直勻速行走至走廊終點處，行走距離為54 m。為使指紋庫的數(shù)據(jù)序列更為完整，采用克里金插值方式處理離線指紋庫。為減小采集設備的硬件磁性誤差以及設備姿勢輕微晃動的影響，采用低通濾波對數(shù)據(jù)進行預處理。將在線階段采集的數(shù)據(jù)作為測試集輸入至構(gòu)建的LCS-Fast-DTW序列匹配模型中，并采用五折交叉驗證法驗證該模型的定位性能，并將相同的測試點位分別輸入至DTW算法、WKNN算法進行對比，進一步驗證本文模型的定位性能，實驗結(jié)果如圖3所示。

由圖3可知，LCS-Fast-DTW算法的定位誤差集中在2.5 m以內(nèi)，占比為77.8%，DTW算法的定位誤差集中在3 m以內(nèi)，占比為72.2%，WKNN算法的定位誤差集中在3.5 m以內(nèi)，占比為79.1%，這三種算法在誤差1 m以內(nèi)的占比分別為36.1%、31.9%及23.6%。因此，本文算法具有較高的定位精度。三種算法的不同定位指標如表1所示。

由表1可知，本文算法的平均定位誤差、定位標準差以及定位時間均低于其他兩種算法，在保證定位精度的同時兼具定位穩(wěn)定性及定位時效性，具有最佳定位性能，可有效應用于地磁室內(nèi)定位。

4 結(jié) 論

本文以地磁室內(nèi)定位為主要研究內(nèi)容，在傳統(tǒng)地磁模值的基礎上利用坐標轉(zhuǎn)換方法構(gòu)建四維的地磁指紋庫，基于DTW算法進行磁序列匹配實現(xiàn)定位，并利用最長公共子序列的有序聚類對其進行優(yōu)化。實驗結(jié)果表明，本文構(gòu)建的LCS-Fast-DTW算法具有較好的定位性能，可有效應用于室內(nèi)定位，同時，該定位方式可為地磁與其他定位信號源進一步結(jié)合實現(xiàn)多源融合定位提供研究基礎，也可為井下、隧道等特殊場景定位提供一定的參考。

參考文獻：

[1] GEOK T K，AUNG K Z，AUNG M S，et al. Review of Indoor Positioning： Radio Wave Technology [J/OL].Applied Sciences，2021，11（1）：279（2020-12-30）[2023-08-08].https：//doi.org/10.3390/app11010279.

[2] PASCACIO P，CASTELEYN S，TORRES-SOSPEDRA J，et al. Collaborative Indoor Positioning Systems： A Systematic Review [J/OL].Sensors，2021，21（3）：1002.（2021-02-02）[2023-08-08].https：//doi.org/10.3390/s21031002.

[3] SONG S S，F(xiàn)ENG F，XU J S. Review of Geomagnetic Indoor Positioning [C]//2020 IEEE 4th International Conference on Frontiers of Sensors Technologies （ICFST）.Shanghai：IEEE，2020：30-33.

[4] SUN M，WANG Y J，XU S L，et al. Indoor Geomagnetic Positioning Using the Enhanced Genetic Algorithm-Based Extreme Learning Machine [J].IEEE Transactions on Instrumentation and Measurement，2021，70：1-11.

[5] CHEN J W，ZHANG W C，WEI D Y，et al. Research on Indoor Constraint Location Method of Mobile Phone Aided by Magnetic Features [C]//2022 IEEE 12th International Conference on Indoor Positioning and Indoor Navigation （IPIN）.Beijing：IEEE，2022：1-7.

[6] 金俊超，馬昌忠，陳國良，等.基于UCR-DTW的地磁序列定位算法 [J].合肥工業(yè)大學學報：自然科學版，2021，44（11）：1551-1556.

[7] 韓雨辰，余學祥，仲臣，等.融合光照強度的地磁室內(nèi)定位方法研究 [J].測繪科學，2022，47（7）：35-42.

[8] 王安義，歐雪.基于粒子濾波的PDR/地磁指紋室內(nèi)定位 [J].測繪通報，2021（1）：24-28.

[9] 馬躍欣，馮秀芳.基于有序聚類和MSKPCA的室內(nèi)定位算法 [J].計算機工程與設計，2021，42（4）：963-968.

[10] 孫猛，汪云甲，周家鵬，等.一種基于快速動態(tài)時間規(guī)整的地磁定位算法 [J].測繪科學，2020，45（8）：77-82.

作者簡介：姚霆宇（1998—），男，回族，安徽安慶人，碩士在讀，研究方向：室內(nèi)定位方向。

收稿日期：2023-09-08

基金項目：安徽省重點研究與開發(fā)計劃（202104a07020014）；安徽省科技重大專項（202103a05020026）

DOI：10.19850/j.cnki.2096-4706.2024.08.020

Research on Multidimensional Geomagnetic Sequence Matching Algorithm

Based on Improved Fast-DTW

YAO Tingyu1，2，3， YU Xuexiang1，2，3， HAN Yuchen1，2，3， ZHU Ping1，2，3

（1.School of Spatial Information and Surveying Engineering， Anhui University of Science and Technology， Huainan 232001， China;

2.Key Laboratory of Aviation-aerospace-ground Cooperative Monitoring and Early Warning of Coal Mining-induced Disasters of Anhui Higher Education Institutes， Anhui University of Science and Technology， Huainan 232001， China;

3.Coal Industry Engineering Research Center of Mining Area Environmental and Disaster Cooperative Monitoring， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： The traditional geomagnetic matching positioning algorithms based on single points have a large computational overhead and relatively poor positioning timeliness and accuracy. To address this issue， this paper uses the Fast Dynamic Time Warping （Fast-DTW） algorithm based on sequences to implement multi-dimensional geomagnetic sequence matching， and optimizes it using ordered clustering of the Longest Common Subsequence （LCS）. During the offline phase， a four-dimensional geomagnetic fingerprint database is constructed by coordinate transformation methods. In the online phase， real-time geomagnetic sequence is matched to obtain positioning results. The experimental results show that the positioning timeliness and accuracy of the algorithm have been improved.

Keywords： geomagnetic indoor positioning; Fast-DTW; LCS; geomagnetic fingerprint database