一種提高DTW運(yùn)算效率的地磁匹配組合導(dǎo)航算法

張東麗，尚俊娜,保金宏

(杭州電子科技大學(xué)通信工程學(xué)院,浙江 杭州 310018)

0 引 言

近年來(lái)，導(dǎo)航定位技術(shù)不斷發(fā)展，組合導(dǎo)航可以彌補(bǔ)單種導(dǎo)航方式的缺陷，綜合多種導(dǎo)航方式的優(yōu)勢(shì)，受到業(yè)界的青睞。常見(jiàn)的導(dǎo)航方式有GPS導(dǎo)航、天文導(dǎo)航、地形匹配導(dǎo)航和地磁導(dǎo)航等，其中地磁導(dǎo)航具有無(wú)需信號(hào)基站、成本低廉、安全性高等優(yōu)勢(shì)，成為具有廣泛應(yīng)用潛力的輔助導(dǎo)航方式[1-2]?；诘卮艌?chǎng)的定位技術(shù)具有全天時(shí)、全地域、無(wú)源性、無(wú)輻射、低功耗等特點(diǎn)，成為定位領(lǐng)域的研究熱點(diǎn)[3]。文獻(xiàn)[4]首先利用Wi-Fi得到定位數(shù)據(jù)，然后根據(jù)定位數(shù)據(jù)確定地磁數(shù)據(jù)庫(kù)所需匹配的范圍，這一方式使得地磁匹配算法的運(yùn)算量降低。胡金平等[5]采用改進(jìn)的序列匹配算法進(jìn)行語(yǔ)音序列匹配，有效提高了系統(tǒng)的識(shí)別率。針對(duì)地磁序列匹配導(dǎo)航定位中動(dòng)態(tài)時(shí)間規(guī)整算法計(jì)算時(shí)間長(zhǎng)、實(shí)時(shí)性差等問(wèn)題，本文提出一種基于減少動(dòng)態(tài)時(shí)間規(guī)整(Dynamic Time Warping，DTW)運(yùn)算量的地磁匹配算法，通過(guò)減少重復(fù)計(jì)算量來(lái)降低算法的復(fù)雜度，在保證定位精度的基礎(chǔ)上，提高了運(yùn)行效率。

1 地磁匹配組合導(dǎo)航

1.1 地磁序列匹配組合導(dǎo)航定位原理

地磁定位分為離線階段、在線階段。離線階段包括地磁數(shù)據(jù)空間對(duì)齊和基準(zhǔn)位置參考坐標(biāo)系的建立；在線階段即地磁序列匹配階段。序列匹配過(guò)程中易發(fā)生誤匹配問(wèn)題，因此本文引入高精度慣性導(dǎo)航系統(tǒng)(Inertial Navigation System, INS)為地磁匹配提供空間里程基準(zhǔn)服務(wù)[6]。

1.2 地磁匹配算法

如果2個(gè)序列需要進(jìn)行相似度比較，常用的方法是DTW匹配算法[7-8]。假設(shè)有2條不同的時(shí)間序列Q(q1,q2,…,qi,…,qn)和C(c1,c2,…,cj,…,cm)，令D(n×m，n≠m)，D為累積距離矩陣。D中的元素d(i,j)=(qi-cj)2代表Q中點(diǎn)qi和C中點(diǎn)cj之間的歐式距離，在D中動(dòng)態(tài)規(guī)劃的思想是從起點(diǎn)d(1,1)到d(n,m)之間找到一條累積距離最小的路徑，也就是動(dòng)態(tài)規(guī)整的距離[9]。DTW匹配算法執(zhí)行過(guò)程中的路徑L在計(jì)算距離矩陣時(shí)遵循以下原則：

(1)邊界性：初始點(diǎn)必須為(1,1)，且max(m,n)≤dL≤m+n，dL為路徑L的長(zhǎng)度。

(2)連續(xù)性：路徑L中的元素是連續(xù)的。

(3)單調(diào)性：L經(jīng)過(guò)(i,j)的之前一步只能是(i-1,j)，(i,j-1)，(i-1,j-1)中的1個(gè)點(diǎn)，而點(diǎn)(i,j)選擇這3個(gè)點(diǎn)中的最小值所對(duì)應(yīng)的點(diǎn)作為前一個(gè)點(diǎn)，進(jìn)而得到累積距離D(i,j)。具體方式如下：

(1)

式中，D(i,j)為累積匹配距離，d(i,j)為2個(gè)地磁序列之間的距離。

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

2.1 DTW算法的改進(jìn)

圖1 匹配路徑約束示意圖

根據(jù)1.2節(jié)的討論可以看出，DTW算法需要不斷按照式(1)去尋找累積矩陣元素(i,j)，直到最后1個(gè)元素(m,n)。算法每次執(zhí)行都會(huì)從第1個(gè)元素到最后1個(gè)元素，時(shí)間復(fù)雜度為o(mn)。當(dāng)序列長(zhǎng)度比較長(zhǎng)時(shí)，產(chǎn)生更多的多余計(jì)算，計(jì)算復(fù)雜度更大。某些情況下，DTW算法將一個(gè)序列上的一點(diǎn)映射到另一條序列上多個(gè)點(diǎn)，導(dǎo)致病態(tài)規(guī)整。因此，如何提高匹配算法的運(yùn)算速率并避免發(fā)生病態(tài)規(guī)整成為研究的難點(diǎn)和熱點(diǎn)。為了解決上述難題，Itakura[10]研究了一種約束窗口，將DTW的路徑L控制在一個(gè)菱形中，將規(guī)整路徑控制在對(duì)角線周圍，每次計(jì)算匹配距離矩陣、累積距離矩陣都用不到菱形外的網(wǎng)格點(diǎn)。運(yùn)用這種全局約束計(jì)算每列中的每個(gè)點(diǎn)匹配距離時(shí)，只用到前一列的3個(gè)網(wǎng)格點(diǎn)，不僅減少了計(jì)算的次數(shù)和存儲(chǔ)的數(shù)量，還避免了因?yàn)樗阉鞣秶鄬?dǎo)致的病態(tài)規(guī)整。通常將這個(gè)約束窗口的一條邊斜率設(shè)為1/2，令其為k1。另外一條邊的斜率設(shè)為2，令其為k2，規(guī)整的路線從(1,1)開(kāi)始到(n,m)結(jié)束。匹配路徑約束示意圖如圖1所示。

圖1中，Xa和Xb表示的是斜率為k1和k2的2條邊的不同的交點(diǎn)，C和Q表示待匹配的序列，E(n,m)表示路徑規(guī)整的終點(diǎn)。當(dāng)Xa

(2)

因?yàn)閄a和Xb取最鄰近的整數(shù)，所以m，n長(zhǎng)度限制條件為：

(3)

如果都不符合以上情況，說(shuō)明兩段序列相差太多，不能執(zhí)行動(dòng)態(tài)匹配的規(guī)整。

DTW匹配算法需要計(jì)算2個(gè)序列中每個(gè)點(diǎn)之間的距離，加約束窗口后的DTW匹配算法只要計(jì)算橫坐標(biāo)與(ymin,ymax)內(nèi)點(diǎn)之間的距離即可，無(wú)需計(jì)算與約束窗口外縱坐標(biāo)點(diǎn)之間的距離。(ymin,ymax)的取值范圍如下：

(4)

(5)

還有一種情況是Xa>Xb，彎折匹配的3段轉(zhuǎn)換為(1,Xb)，(Xb+1,Xa)，(Xa+1,n)。

加約束窗口后的動(dòng)態(tài)規(guī)劃過(guò)程中，X軸向前滑動(dòng)一步需要比較的Y軸上的長(zhǎng)度與加約束窗口前不同，但是特點(diǎn)是相同的。累積距離為：

(6)

圖2 累積距離矢量的動(dòng)態(tài)更新圖解

橫坐標(biāo)每向右移動(dòng)一次，就要使用上一列的累計(jì)距離D來(lái)計(jì)算當(dāng)前列的累計(jì)距離。矢量d用來(lái)保存當(dāng)前需要計(jì)算的列累計(jì)距離，矢量D只保存上一列的累積距離，這樣，每計(jì)算一列就更新一次D和d，需要保存的內(nèi)容可以減少很多。最后得到D中的第m個(gè)元素即為所求的2個(gè)序列之間的匹配距離。累計(jì)距離圖解過(guò)程如圖2所示。

本文中的歐氏距離d(i,j)代表2個(gè)序列之間的點(diǎn)的真實(shí)距離。n維空間的距離計(jì)算公式如下：

(7)

本文進(jìn)行動(dòng)態(tài)規(guī)劃時(shí)，歐氏距離的計(jì)算和對(duì)比采用的是平方值而不是平方根，縮減了每一次計(jì)算規(guī)劃路徑的復(fù)雜度，最后對(duì)輸出結(jié)果開(kāi)根號(hào)即可得到歐氏距離。

2.2 基于改進(jìn)的DTW算法的地磁匹配方法

根據(jù)2.1節(jié)討論可知，采用改進(jìn)DTW匹配算法進(jìn)行匹配定位時(shí)，要匹配到具有最小的相似距離的地磁序列。令在線實(shí)時(shí)測(cè)量的地磁序列長(zhǎng)度為s，測(cè)量結(jié)果為Bs=(B1,B2,…,Bs)，數(shù)據(jù)庫(kù)的地磁序列長(zhǎng)度為t(t>s)，令Bt=(B1,B2,…,Bt)。在Bs中選取從第1個(gè)數(shù)據(jù)開(kāi)始到第s個(gè)數(shù)據(jù)結(jié)束的片段，再使用改進(jìn)后的DTW匹配算法將該片段與序列Bs進(jìn)行對(duì)比計(jì)算，得到兩序列中最短的距離。以此類推，直到計(jì)算完所有的序列，再采用2.1節(jié)中累計(jì)距離矢量更新步驟計(jì)算出累計(jì)距離D，最后得到D中的第m個(gè)元素所對(duì)應(yīng)的位置坐標(biāo)。

2.3 基于改進(jìn)DTW算法的地磁匹配組合導(dǎo)航

室外地磁匹配組合導(dǎo)航的實(shí)現(xiàn)主要分為兩部分[11]。第一部分為建立離散地磁數(shù)據(jù)庫(kù)，采用GPS482結(jié)合磁強(qiáng)計(jì)建立離散地磁數(shù)據(jù)庫(kù)。第二部分為在線匹配過(guò)程，將地磁傳感器測(cè)量出的數(shù)據(jù)和數(shù)據(jù)庫(kù)中的數(shù)據(jù)做匹配，本實(shí)驗(yàn)使用的匹配算法是改進(jìn)的DTW匹配算法。同時(shí)利用慣導(dǎo)測(cè)得的位置信息進(jìn)行修正，kalman濾波器[12]融合兩者定位信息，得到最終結(jié)果。具體過(guò)程如圖3所示。

圖3 基于改進(jìn)DTW算法的地磁匹配組合導(dǎo)航流程圖

3 仿真實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)中，首先進(jìn)行地磁場(chǎng)數(shù)據(jù)的采集，使用巡航車搭載GPS482模塊以及JY901模塊實(shí)驗(yàn)對(duì)應(yīng)的匹配窗口大小分別為20，40，60，地磁匹配導(dǎo)航定位位置更新時(shí)間為1 s，實(shí)驗(yàn)參數(shù)如表1所示。

表1 實(shí)驗(yàn)參數(shù)

3.1 定位結(jié)果

實(shí)驗(yàn)分別采用DTW匹配算法和改進(jìn)DTW匹配算法解算測(cè)試軌跡，定位軌跡如圖4所示。將不同匹配算法的地磁匹配組合導(dǎo)航定位軌跡在Google地圖上顯示，結(jié)果如圖5所示，不同匹配算法得到軌跡的表示形式與圖4相同。

圖4 不同匹配算法定位軌跡對(duì)比

圖5 不同匹配算法在Google地圖上的定位軌跡

3.2 算法運(yùn)行效率

用在一個(gè)位置定位100次來(lái)得到一次定位的平均時(shí)間，DTW匹配算法和改進(jìn)的DTW匹配算法的定位時(shí)間對(duì)比結(jié)果如表2所示。

表2 不同算法定位時(shí)間平均值

從表2可以看出，在匹配窗口為20，40，60時(shí)，改進(jìn)的DTW匹配算法定位運(yùn)行時(shí)間比傳統(tǒng)DTW匹配算法定位效率分別提升了29.2%，41.1%，59.8%。運(yùn)算效率平均提升了43.37%。

3.3 算法定位精度

因?yàn)槠ヅ浯翱谝话愣际窃O(shè)為總序列的1/30～1/10，實(shí)驗(yàn)的地磁數(shù)據(jù)序列為530，在此范圍內(nèi)匹配序列越長(zhǎng)，匹配準(zhǔn)確率越高，所以，本實(shí)驗(yàn)采用的匹配窗口為60，得到定位誤差和累積誤差對(duì)比結(jié)果如圖6所示。2種匹配算法組合導(dǎo)航的定位誤差對(duì)比如表3所示。

圖6 不同地磁匹配算法組合導(dǎo)航誤差對(duì)比

表3 不同匹配算法組合導(dǎo)航誤差對(duì)比

從圖6、表3可以看出，2種匹配算法的平均精度差別不大，改進(jìn)的DTW匹配算法定位誤差比傳統(tǒng)DTW匹配算法的平均精度減小了0.22 m。

綜合以上分析發(fā)現(xiàn)，改進(jìn)的DTW匹配算法定位性能比傳統(tǒng)DTW匹配算法定位性能好，并且耗時(shí)少。

4 結(jié)束語(yǔ)

針對(duì)DTW匹配算法存在病態(tài)規(guī)整、時(shí)間復(fù)雜度較高等缺點(diǎn)，本文提出一種改進(jìn)的DTW匹配算法，在序列匹配過(guò)程中添加Itakura約束窗口，減少了算法運(yùn)算復(fù)雜度。在保證定位精度的基礎(chǔ)上，提高了運(yùn)行效率。但是，由于場(chǎng)地及設(shè)備的限制，實(shí)驗(yàn)環(huán)境較為簡(jiǎn)單，后續(xù)將繼續(xù)改進(jìn)算法使其在更為復(fù)雜環(huán)境下快速精確地定位目標(biāo)。