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

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

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

中圖分類(lèi)號(hào)：TN966；P318 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2024）08-0089-05

0 引 言

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

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

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

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

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

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

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

（1）

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

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

（2）

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

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

2.1 LCS算法

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

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

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

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

（4）

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

2.2 Fast-DTW算法

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

（5）

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

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

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

2.3 LCS-Fast-DTW定位算法

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

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

2）首先對(duì)所有測(cè)試集的地磁序列進(jìn)行LCS相似度計(jì)算，獲得相應(yīng)的相似度結(jié)果。

3）根據(jù)得到的LCSS相似度矩陣，使用K-means聚類(lèi)算法來(lái)劃分參考指紋庫(kù)，獲得相似度最大的聚類(lèi)標(biāo)簽和各個(gè)聚類(lèi)的中心點(diǎn)。

4）在獲得的聚類(lèi)結(jié)果中運(yùn)用Fast-DTW算法進(jìn)行計(jì)算，選擇距離最小的參考序列，其對(duì)應(yīng)的位置可認(rèn)為是最接近測(cè)試序列的實(shí)際位置。

3 實(shí)驗(yàn)與結(jié)論

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

本文的實(shí)驗(yàn)路徑從起點(diǎn)向西一直勻速行走至走廊終點(diǎn)處，行走距離為54 m。為使指紋庫(kù)的數(shù)據(jù)序列更為完整，采用克里金插值方式處理離線指紋庫(kù)。為減小采集設(shè)備的硬件磁性誤差以及設(shè)備姿勢(shì)輕微晃動(dòng)的影響，采用低通濾波對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。將在線階段采集的數(shù)據(jù)作為測(cè)試集輸入至構(gòu)建的LCS-Fast-DTW序列匹配模型中，并采用五折交叉驗(yàn)證法驗(yàn)證該模型的定位性能，并將相同的測(cè)試點(diǎn)位分別輸入至DTW算法、WKNN算法進(jìn)行對(duì)比，進(jìn)一步驗(yàn)證本文模型的定位性能，實(shí)驗(yàn)結(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%。因此，本文算法具有較高的定位精度。三種算法的不同定位指標(biāo)如表1所示。

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

4 結(jié) 論

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

參考文獻(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] 金俊超，馬昌忠，陳國(guó)良，等.基于UCR-DTW的地磁序列定位算法 [J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2021，44（11）：1551-1556.

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

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

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

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

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

收稿日期：2023-09-08

基金項(xiàng)目：安徽省重點(diǎn)研究與開(kāi)發(fā)計(jì)劃（202104a07020014）；安徽省科技重大專(zhuān)項(xiàng)（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