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

王安義， 歐 雪

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

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

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

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

1 定位原理

1.1 PDR定位

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

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

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

(1)

從式(1)可知，在已知前一時(shí)刻位置的基礎(chǔ)上可以通過PDR解算出當(dāng)前時(shí)刻的位置。式(1)中有兩個(gè)關(guān)鍵參數(shù)S和θ，即當(dāng)前時(shí)刻的步長和邁步朝向。

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

(2)

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

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

1.2 地磁定位

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

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

在線匹配定位時(shí)，通過相關(guān)度量匹配、DTW等匹配算法將當(dāng)前時(shí)刻的地磁信息與地磁基準(zhǔn)庫中的數(shù)據(jù)進(jìn)行匹配[14]，確定當(dāng)前時(shí)刻的位置。

2 改進(jìn)的地磁定位匹配算法

分別優(yōu)化離線建庫和在線匹配兩個(gè)階段，改進(jìn)后的定位框圖如圖2所示。

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

離線建庫：采集定位區(qū)域的地磁信息并生成兩個(gè)不同分辨率的地磁基準(zhǔn)庫。

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

2.1 雙分辨率地磁基準(zhǔn)庫

利用連續(xù)采集法對定位區(qū)域進(jìn)行地磁數(shù)據(jù)采集時(shí)對采集人員的行走速度有極高的勻速要求，如果行走速度沒有固定，后續(xù)構(gòu)建的地磁基準(zhǔn)庫將出現(xiàn)不可忽略的誤差。不同行人行走速度各不相同，如果測試人員與數(shù)據(jù)采集人員行走模式和行走速度差異較大，將出現(xiàn)無法匹配的問題。因此選擇單點(diǎn)采集的方式采集用于構(gòu)建地磁指紋庫的地磁數(shù)據(jù)，用地磁模值作為地磁特征量，表達(dá)式為

(3)

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

針對單點(diǎn)采集費(fèi)時(shí)費(fèi)力問題，利用克里金插值算法[15]減少數(shù)據(jù)采集量,在已測得Pi點(diǎn)的地磁值的前提下，Pk點(diǎn)的地磁值可以表示為

(4)

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

(5)

(6)

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

通過設(shè)置不同插值密度可以構(gòu)建不同分辨率的地磁基準(zhǔn)庫。插值密度過低將造成地磁指紋過少出現(xiàn)較大定位誤差，插值密度過高將出現(xiàn)大量等值數(shù)據(jù)，在匹配階段將“一對多”情況，導(dǎo)致定位失敗?；谝陨峡紤]，將構(gòu)建雙密度的地磁基準(zhǔn)庫用于后續(xù)地磁匹配。

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

單點(diǎn)匹配簡單方便但利用的有效信息太少，容易出現(xiàn)誤匹配，嚴(yán)重影響定位精度。序列匹配可以有效提高匹配精度,但全局搜索的方式復(fù)雜且浪費(fèi)時(shí)間?；贒TW的序列匹配可以允許兩個(gè)匹配序列長度不一致，匹配方式靈活、效率更高。利用單點(diǎn)匹配和序列匹配結(jié)合的方式用于地磁匹配，達(dá)到定位目的，具體過程分為以下幾個(gè)步驟：

步驟一PDR解算出當(dāng)前時(shí)刻位置Pi。

步驟二在地磁基準(zhǔn)庫1中搜索與Pi歐式距離最近的N個(gè)地磁基準(zhǔn)點(diǎn)。

步驟三在N個(gè)點(diǎn)中搜索與此刻地磁值相似度最高的K個(gè)點(diǎn)，該K個(gè)點(diǎn)即為單點(diǎn)匹配結(jié)果及K條地磁基準(zhǔn)序列匹配終點(diǎn)。

步驟四利用DTW將當(dāng)前步伐(抬腳-落腳)內(nèi)的連續(xù)地磁序列與地磁基準(zhǔn)庫2中的K條地磁基準(zhǔn)序列進(jìn)行匹配。

步驟五最佳匹配的地磁基準(zhǔn)序列的終點(diǎn)Ki為解算出的當(dāng)前時(shí)刻位置。

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

(7)

式(7)中:d(i,j)為測試指紋序列T中的第i個(gè)位置的特征量mi與參考指紋序列K中第j個(gè)位置的特征量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)只允許到達(dá)水平格點(diǎn)(i-1,j)、豎直格點(diǎn)(i,j-1)以及對角格點(diǎn)(i-1,j-1)的三者之一，因此可以得到該幀到下一幀的最短距離為min[D(i-1,j),D(i,j-1),D(i-1,j-1)]，通過遞推計(jì)算出兩個(gè)序列的累積距離最小值

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

m,n≥2

(8)

依次連接各幀之間最小距離對應(yīng)的點(diǎn)得到測試指紋序列與參考指紋序列之間的規(guī)整路徑。

最終累積距離最小的地磁基準(zhǔn)序列的終點(diǎn)Ki即為輸出位置。

3 實(shí)驗(yàn)與分析

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

3.1 離線建庫

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

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

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

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

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

3.2 在線定位

在PDR中，對加速度進(jìn)行處理后用于步伐檢測，步伐檢測結(jié)果如圖5所示。

圖5 步伐檢測結(jié)果Fig.5 Step detection results

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

以一個(gè)隨機(jī)測試點(diǎn)為例，得到的單點(diǎn)匹配結(jié)果如圖6所示?；鶞?zhǔn)點(diǎn)與PDR地磁值相似度最高的5個(gè)點(diǎn)即為單點(diǎn)匹配結(jié)果，將作為接下來序列匹配的終點(diǎn)。

圖6 單點(diǎn)匹配結(jié)果Fig.6 Single point matching results

接著進(jìn)行DTW匹配，計(jì)算實(shí)驗(yàn)地磁序列與五條地磁基準(zhǔn)序列的最小累積距離，累積距離最小的地磁基準(zhǔn)序列與實(shí)驗(yàn)地磁序列的匹配情況如圖7所示。

圖7 DTW匹配結(jié)果Fig.7 DTW match results

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

表1 10組數(shù)據(jù)平均定位誤差Table 1 Average positioning error of 10 groups of data

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

4 結(jié)論

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