張東麗，尚俊娜,保金宏

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

0 引 言

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

1 地磁匹配組合導航

1.1 地磁序列匹配組合導航定位原理

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

1.2 地磁匹配算法

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

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

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

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

(1)

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

2 地磁匹配算法的改進

2.1 DTW算法的改進

圖1 匹配路徑約束示意圖

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

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

(2)

因為Xa和Xb取最鄰近的整數(shù)，所以m，n長度限制條件為：

(3)

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

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

(4)

(5)

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

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

(6)

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

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

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

(7)

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

2.2 基于改進的DTW算法的地磁匹配方法

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

2.3 基于改進DTW算法的地磁匹配組合導航

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

圖3 基于改進DTW算法的地磁匹配組合導航流程圖

3 仿真實驗結(jié)果與分析

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

表1 實驗參數(shù)

3.1 定位結(jié)果

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

圖4 不同匹配算法定位軌跡對比

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

3.2 算法運行效率

用在一個位置定位100次來得到一次定位的平均時間，DTW匹配算法和改進的DTW匹配算法的定位時間對比結(jié)果如表2所示。

表2 不同算法定位時間平均值

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

3.3 算法定位精度

因為匹配窗口一般都是設(shè)為總序列的1/30～1/10，實驗的地磁數(shù)據(jù)序列為530，在此范圍內(nèi)匹配序列越長，匹配準確率越高，所以，本實驗采用的匹配窗口為60，得到定位誤差和累積誤差對比結(jié)果如圖6所示。2種匹配算法組合導航的定位誤差對比如表3所示。

圖6 不同地磁匹配算法組合導航誤差對比

表3 不同匹配算法組合導航誤差對比

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

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

4 結(jié)束語

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