基于行人航位推算的后向地磁匹配算法

王安義， 歐 雪

(西安科技大學通信與信息工程學院， 西安 710054)

隨著信息時代的到來，人們越來越依賴基于位置的服務(location based service，LBS)。在室外環境中，全球定位系統(global positioning system，GPS)能夠提供準確的LBS，然而在室內環境中，GPS信號受到建筑物的遮擋，不能提供準確的定位服務，因此全球導航衛星系統(global navigation satellite system，GNSS)技術無法應用到室內環境中[1]。室內環境一般比較復雜，建筑物內部結構的復雜性、室內物品的擺放等的影響將會造成無線信號的多徑傳播、非視距接收，因此基于無線信號傳播的室內定位方法具有一定局限性[2]。行人航位推算(pedestrian dead reckoning，PDR)是低成本便攜式設備中航跡推算思想的延伸[3]，通過步數和步長計算距離，并通過磁力計和陀螺儀確定方向，能保持較高的定位精度，成為一種新興的定位方法。

中外對PDR和地磁融合定位[4]的研究已取得一些成果；芬蘭IndoorAtlas公司開發的一款利用地磁信息定位的軟件可以達到2～3 m的定位精度[5]；文獻[6]利用移動機器人，結合動態時間規整(dynamic time warping, DTW)和粒子濾波算法進行地磁定位，定位精度優于1 m，但考慮行人和機器人移動方式的不同，算法的可移植性尚待商榷；文獻[7-8]提出一種指紋快速采集方法用于構建地磁指紋庫從而進行快速定位，該方法需要數據集人員勻速行走連續采集地磁數據后，再將數據均勻分配到采集路線上的各個點，對采集人員行走過程穩定性要求極高，實際操作難度太大；文獻[9-10]利用慣性導航結合地磁進行室內定位，有效彌補了慣性傳感器長期使用不穩定的缺點，但只使用了單點地磁值作為匹配對象，在地磁分辨率不高的區域將出現誤匹配；文獻[11]提出一種增強型粒子濾波法用于提高室內手機定位系統的定位精度，可以實現1～2 m的定位精度，但是算法過于復雜。

針對上述問題，現提出一種基于PDR的后向地磁匹配算法，將單點匹配和序列匹配進行融合。整個過程依賴于智能手機獲取行人實時的加速度測量值、陀螺儀測量值和磁力計測量值。在地磁匹配階段，首先利用K最近鄰(K-nearest neighbor, KNN)算法計算與PDR解算得到的當前時刻位置最近的N個地磁基準點和該N個地磁基準點中與當前時刻地磁模值相似度最大的K個地磁基準點，然后將當前時刻與上一時刻(一個步伐)的地磁序列與K個地磁基準點作為終點的K條基準地磁序列進行DTW匹配，匹配度最高的基準地磁序列的終點即為當前時刻最優位置。

1 定位原理

1.1 PDR定位

PDR利用慣性傳感器得到的數據來計算行人相對位置從而實現定位[12]，其定位原理如圖1所示。

圖1 PDR定位原理圖Fig.1 PDR positioning schematic diagram

k-1時刻位置Pk-1的坐標為 (xk-1,yk-1)，行人從點Pk-1運動到點Pk(xk,yk)時，利用行走的距離Sk和航向角θk可以通過式(1)得到P1的坐標為

(1)

從式(1)可知，在已知前一時刻位置的基礎上可以通過PDR解算出當前時刻的位置。式(1)中有兩個關鍵參數S和θ，即當前時刻的步長和邁步朝向。

在實際的行走過程中，距離S為每一個步伐內的步長。S可以通過加速度計算得到，行人手持的智能手機內置加速度計可以實時記錄行走時三維加速度值。利用加速度差值計算步長[13]，表達式為

(2)

式(2)中:k1和k2為固定常數；γ為補償參數；Tstep為該步的時間長度；Δa為一個步伐內的加速度差值的平均數；amax和amin分別為一個步伐內加速度最大值和最小值。

航向角θ可以通過磁力計測量值進行坐標系換算和陀螺儀測量值積分得到，通過粒子濾波算法融合磁力計和陀螺儀的方向角，最終確定θ的值。

1.2 地磁定位

地磁定位是指紋定位的一種，由離線構建地磁基準庫、在線匹配定位兩個階段構成。首先采集室內區域地磁場特征信息，得到地磁指紋庫，經過處理得到較高分辨率的地磁基準庫。當行人經過該區域時，隨身攜帶的智能手機內置的磁力計實時獲取地磁場的特征值信息，并利用相關算法與地磁基準庫中地磁信息進行匹配。通過計算后確定當前地磁信息與地磁基準庫中的最相似點即匹配點，最終確定出行人的精確位置。

在構建地磁基準庫時，首先需要采集定位區域的地磁信息。單點采集和連續采集是最常用的兩種地磁數據采集方式。單點采集是指按一定采樣間隔記錄定位區域的地磁信息，然后通過插值算法增加數據密度。連續采集是指采集人員手持采集儀器在定位區域按路線勻速行走，再將采集的數據均勻分配在行走路線上。

在線匹配定位時，通過相關度量匹配、DTW等匹配算法將當前時刻的地磁信息與地磁基準庫中的數據進行匹配[14]，確定當前時刻的位置。

2 改進的地磁定位匹配算法

分別優化離線建庫和在線匹配兩個階段，改進后的定位框圖如圖2所示。

圖2 地磁定位框圖Fig.2 Magnetic positioning block diagram

離線建庫：采集定位區域的地磁信息并生成兩個不同分辨率的地磁基準庫。

在線匹配：將實時的單點地磁信息與地磁基準庫1作單點匹配，并利用DTW算法將實時的地磁序列與地磁基準2作序列匹配，最終輸出位置。

2.1 雙分辨率地磁基準庫

利用連續采集法對定位區域進行地磁數據采集時對采集人員的行走速度有極高的勻速要求，如果行走速度沒有固定，后續構建的地磁基準庫將出現不可忽略的誤差。不同行人行走速度各不相同，如果測試人員與數據采集人員行走模式和行走速度差異較大，將出現無法匹配的問題。因此選擇單點采集的方式采集用于構建地磁指紋庫的地磁數據，用地磁模值作為地磁特征量，表達式為

(3)

式(3)中：Mi為點Pi(xi,yi)的地磁值；Mx、My、Mz分別為手機載體坐標中三軸磁力值。

針對單點采集費時費力問題，利用克里金插值算法[15]減少數據采集量,在已測得Pi點的地磁值的前提下，Pk點的地磁值可以表示為

(4)

式(4)中：λi為每個采樣點的權值，與插值點和采樣的距離及采樣點空間分布有關。λi需要滿足條件

(5)

(6)

式中：γ(Pi,Pj)為樣本點Pi與Pj的半變異值；γ(Pi,Pk)為樣本點Pi與插值點Pk的半變異值；φ為滿足方差最小化條件的拉格朗日常數。

通過設置不同插值密度可以構建不同分辨率的地磁基準庫。插值密度過低將造成地磁指紋過少出現較大定位誤差，插值密度過高將出現大量等值數據，在匹配階段將“一對多”情況，導致定位失敗。基于以上考慮，將構建雙密度的地磁基準庫用于后續地磁匹配。

2.2 基于DTW的后向地磁匹配算法

單點匹配簡單方便但利用的有效信息太少，容易出現誤匹配，嚴重影響定位精度。序列匹配可以有效提高匹配精度,但全局搜索的方式復雜且浪費時間。基于DTW的序列匹配可以允許兩個匹配序列長度不一致，匹配方式靈活、效率更高。利用單點匹配和序列匹配結合的方式用于地磁匹配，達到定位目的，具體過程分為以下幾個步驟：

步驟一PDR解算出當前時刻位置Pi。

步驟二在地磁基準庫1中搜索與Pi歐式距離最近的N個地磁基準點。

步驟三在N個點中搜索與此刻地磁值相似度最高的K個點，該K個點即為單點匹配結果及K條地磁基準序列匹配終點。

步驟四利用DTW將當前步伐(抬腳-落腳)內的連續地磁序列與地磁基準庫2中的K條地磁基準序列進行匹配。

步驟五最佳匹配的地磁基準序列的終點Ki為解算出的當前時刻位置。

假設地磁測試指紋序列T和參考指紋序列K的長度分別為m和n，T={m1,m2,…,mm}，K={M1,M2,…,Mn}，序列T中所有元素與K中所有元素構成的距離矩陣可以表示為

(7)

式(7)中:d(i,j)為測試指紋序列T中的第i個位置的特征量mi與參考指紋序列K中第j個位置的特征量Mj之間的距離。首先初始化累積距離矩陣，即D(1,1)=(1,1)，則有D(1,2)=D(1,1)+d(1,2)，D(2,1)=D(1,1)+d(2,1)。由于(i,j)只允許到達水平格點(i-1,j)、豎直格點(i,j-1)以及對角格點(i-1,j-1)的三者之一，因此可以得到該幀到下一幀的最短距離為min[D(i-1,j),D(i,j-1),D(i-1,j-1)]，通過遞推計算出兩個序列的累積距離最小值

D(m,n)=d(m,n)+min[D(m-1,n),D(m,n-1),D(m-1,n-1)]，

m,n≥2

(8)

依次連接各幀之間最小距離對應的點得到測試指紋序列與參考指紋序列之間的規整路徑。

最終累積距離最小的地磁基準序列的終點Ki即為輸出位置。

3 實驗與分析

為了驗證本文算法的有效性，在西安科技大學北院3號教學樓四樓走廊進行實驗。該樓層為實驗室集中樓層，有大量電子儀器，能夠較好地檢驗算法的抗干擾性。實驗所用的手機型號為iphone 8，實驗所用數據來源于手機內置的磁力計、加速度計、陀螺儀和計時器。實驗人員先用定點法采集實驗區域地磁數據，再隨機行走形成若干條待定位路徑用于測試算法。

3.1 離線建庫

在構建地磁指紋庫過程中，利用地磚將定位區域劃分為90 cm × 60 cm的長方形小區域。采集時實驗人員在每個長方形頂點距離地面約1 m處以50 Hz的采樣頻率連續采集5 s，然后對每個采樣點的三維磁場數據進行求模值、濾波和平均處理，得到地磁指紋庫如圖3所示。

圖3 地磁指紋庫Fig.3 Geomagnetic fingerprint library

圖4 不同插值間隔生成的地磁基準庫Fig.4 Geomagnetic reference library generated by different interpolation intervals

圖4為插值后的地磁基準庫分辨率示意圖，由地磁指紋庫進行克里金插值處理后生成。為了比較不同插值間隔對地磁分辨率的影響，選取了三組插值間隔進行分析比較，分別為0.2 m×0.4 m，0.1 m×0.2 m和0.05 m×0.1 m。

通過觀察分析可知，適當縮小插值間隔可以提高地磁基準庫分辨率，如圖4(b)分辨率高于圖4(a)。然而插值間隔與分辨率并不是嚴格呈反比關系，圖4(c)插值間隔在圖4(b)基礎上縮小了10倍，但分辨率并沒有明顯提高。考慮到行人的身體寬度，30～40 cm的定位誤差都是可以接受的，因此在單點匹配時選用的地磁基準庫1的插值間隔為0.2 m×0.4 m。考慮到PDR過程采樣頻率的影響，序列匹配的地磁基準庫插值間隔為0.1 m×0.2 m。

3.2 在線定位

在PDR中，對加速度進行處理后用于步伐檢測，步伐檢測結果如圖5所示。

圖5 步伐檢測結果Fig.5 Step detection results

圖5中，一個完整的步伐由A→B→C→D→E組成，其中點A、點C和點E代表加速度過零點，點B和點D分別代表加速度峰值和谷值。用一個步伐結束時刻(點E)的磁力計測量值與地磁基準庫1進行單點匹配，用一個步伐內(點A至點E)的地磁序列與地磁基準庫2進行DTW匹配。

以一個隨機測試點為例，得到的單點匹配結果如圖6所示。基準點與PDR地磁值相似度最高的5個點即為單點匹配結果，將作為接下來序列匹配的終點。

圖6 單點匹配結果Fig.6 Single point matching results

接著進行DTW匹配，計算實驗地磁序列與五條地磁基準序列的最小累積距離，累積距離最小的地磁基準序列與實驗地磁序列的匹配情況如圖7所示。

圖7 DTW匹配結果Fig.7 DTW match results

實驗人員選擇兩條路徑，每一條路徑以任意速度行走五次，共獲取10組待定位數據。在給定初始位置的前提下，通過本文算法解算出位置信息，得到的平均位誤差如表1所示。

表1 10組數據平均定位誤差Table 1 Average positioning error of 10 groups of data

從表1中可以分析得到，10組數據平均定位誤差均小于1.5 m，其中最大平均定位誤差為1.26 m，最小平均定位誤差為0.52 m。路徑一的定位效果明顯路徑二，通過分析原始地磁數據得知，路徑二的地磁變化更明顯，更有利于地磁匹配，因此定位精度更高。

4 結論

針對常用地磁匹配算法存在的匹配搜索范圍過廣、時間過長的問題，提出構建雙分辨率地磁基準庫，并融合單點匹配和序列匹配提高匹配效率。比較了不同插值間隔的克里金插值方法對地磁分辨效果的影響，以此為根據選取兩組不同插值間隔用于構建雙分辨率地磁基準庫，同時改進基于DTW的后向地磁序列匹配算法。經過實驗驗證，本文算法最大定位誤差小于1.5 m，可以滿足普通室內定位需求。