葛倩，侯守明，趙文濤

(河南理工大學(xué)計算機科學(xué)與技術(shù)學(xué)院，河南焦作 454003)

0 引言

隨著科技的不斷進步，定位和導(dǎo)航技術(shù)不斷成熟，以手機為移動終端的定位系統(tǒng)在經(jīng)濟建設(shè)、改善民生、社會生活等方面都得到普遍應(yīng)用，例如:危險品運輸車定位追蹤[1]；無人機配送[2]；智能旅游等[3].尤其在智能旅游增強現(xiàn)實（AR）實景定位導(dǎo)航中，實時獲取高精度地理位置信息處于至關(guān)重要的位置.用戶通過AR實景定位導(dǎo)航系統(tǒng)獲取實時坐標信息，并為游客規(guī)劃清晰的旅游線路，省時、省心、省力的AR實景導(dǎo)航系統(tǒng)成為游客出行必不可少的工具.

目前，GPS系統(tǒng)是當(dāng)前全球應(yīng)用最為廣泛的導(dǎo)航和定位系統(tǒng)，通過用戶接收的檢測衛(wèi)星發(fā)送信號，從而對用戶所在位置坐標進行準確定位.但由于GPS定位系統(tǒng)受信號傳播誤差、衛(wèi)星特性誤差和用戶接收機內(nèi)在誤差等因素的影響，導(dǎo)致GPS系統(tǒng)定位精度低.為了提高GPS定位精度，近年，研究人員主要采用以下兩種技術(shù)方法進行研究.第一種研究通過借助輔助設(shè)備：任超等[4]將移動定位技術(shù)（GPSOne）應(yīng)用于智能手機定位系統(tǒng)，對其準確性和魯棒性進行研究分析；Zandbergen等[5]對比了輔助GPS（A-GPS）、W iFi和蜂窩定位技術(shù)，在此基礎(chǔ)上提高了高靈敏度GPS手機定位精準度[6].第二種研究利用智能手機自帶芯片的設(shè)計算法來提高定位的精準度：杜曉輝等[7]分別將最小二乘法和卡爾曼濾波應(yīng)用于靜態(tài)單點定位，并比較了二者的定位誤差，證明卡爾曼濾波算法可以有效地利用噪聲統(tǒng)計特征對坐標量進行估計，得到較好的定位精度；劉志忠等[8]使用卡爾曼濾波算法消除了GPS數(shù)據(jù)中較大的數(shù)據(jù)波動,并通過模糊C-均值聚類算法確定數(shù)據(jù)中心，驗證了此方法提高GPS定位的合理性；劉勝等[9]提出了一種基于模糊C-均值聚類算法和卡爾曼濾波算法的組合優(yōu)化方法，首先通過卡爾曼濾波算法對GPS數(shù)據(jù)去噪，然后使用模糊C-均值聚類分析，聚類中心點為最終定位坐標，降低了定位成本，提高了GPS單點定位的精準度；崔少星[10]則首先采用DBSCAB密度聚類算法去除偏離度較大的數(shù)據(jù)點，然后對所剩的數(shù)據(jù)進行算術(shù)均值運算，即獲得GPS精確定位的坐標數(shù)據(jù)信息；袁陽等[11]針對手機GPS定位系統(tǒng)采集的數(shù)據(jù)信息分別進行動態(tài)卡爾曼濾波和靜態(tài)卡爾曼濾波設(shè)計，實驗驗證了卡爾曼濾波算法對處理手機GPS原始數(shù)據(jù)定位的可行性，其中，動態(tài)低速卡爾曼濾波算法定位結(jié)果最好.

基于上述對GPS單點定位算法的研究，雖然有效控制了GPS定位誤差范圍，但定位精度還需提高.因此，本文提出使用卡爾曼濾波結(jié)合改進的DBSCAN聚類思想提高GPS定位精度.首先通過卡爾曼濾波去噪縮小誤差范圍，然后提出一種基于DBSCAN二次聚類加權(quán)重心的GPS定位誤差修正策略，進行二次去噪和聚類定位，并將此算法應(yīng)用于AR實景定位導(dǎo)航系統(tǒng)中，以低成本提高GPS定位的精準度，且有較好的魯棒性.

1 卡爾曼濾波模型及數(shù)據(jù)處理

卡爾曼濾波算法通過系統(tǒng)輸入、輸出的觀測數(shù)據(jù)計算線性系統(tǒng)狀態(tài)方程，將系統(tǒng)狀態(tài)進行最優(yōu)估計.由于受各種因素的影響，GPS采集到的數(shù)據(jù)存在很大波動，采用卡爾曼濾波算法能有效去除觀測數(shù)據(jù)中的噪聲和干擾信號，獲得可靠的定位信息.

卡爾曼濾波模型由線性系統(tǒng)狀態(tài)的預(yù)測方程和觀測方程兩部分組成：式（1）、式（2）中：A為狀態(tài)轉(zhuǎn)移系數(shù)矩陣；xk和xk?1分別為k、k?1時刻的系統(tǒng)狀態(tài)變量；Wk?1為k?1時刻的過程激勵噪聲；Zk為觀測變量；H為測量系數(shù)矩陣；Vk為對應(yīng)經(jīng)緯度上的高斯白噪聲.卡爾曼濾波過程如下：

1）通過k?1時刻預(yù)測k時刻的狀態(tài)

2）通過k?1時刻估算k時刻的系統(tǒng)誤差Pk

式中，Q為觀測噪聲協(xié)方差矩陣。

3）更新卡爾曼增益Kk

式中，R為測量噪聲協(xié)方差矩陣.

4）由預(yù)測值、觀測值和更新后的卡爾曼增益，獲得k時刻最優(yōu)估計

5）在系統(tǒng)運行結(jié)束前，卡爾曼濾波需要計算當(dāng)前時刻的系統(tǒng)誤差，以便下一時刻進行計算.k時刻的系統(tǒng)誤差Pk

式中，I為單位矩陣.

我們將手機GPS系統(tǒng)采集到的數(shù)據(jù)，采用卡爾曼濾波算法處理分析.圖1（a）為原始GPS數(shù)據(jù)分布圖，圖1（b）為采用卡爾曼濾波后的GPS數(shù)據(jù)分布圖.由實驗分析可知，經(jīng)過卡爾曼濾波去噪，有效消除數(shù)據(jù)中較大的數(shù)據(jù)波動，經(jīng)緯度平均誤差被控制在5.2 m，但獲取更加精準的真實位置坐標點仍需進一步的數(shù)據(jù)處理.

圖1 卡爾曼濾波后的GPS數(shù)據(jù)分布

2 DBSCAN聚類加權(quán)重心定位模型

DBSCAN作為基本的聚類分析算法，研究的目的是盡可能形成密度可達的數(shù)據(jù)點最大簇，能快速進行聚類且對噪聲數(shù)據(jù)的區(qū)分，簇的形狀可任意構(gòu)成[12].采用改進的DBSCAN聚類思想對GPS采集的數(shù)據(jù)集進行二次聚類和二次去噪，并通過密度聚類分析，獲取更精確的位置坐標.

2.1 DBSCAN算法的相關(guān)定義

1）鄰域（Eps）：以對象p為核心，Eps為半徑的圓，即

式中：Nε(p)為以p為核心以Eps為半徑的圓內(nèi)數(shù)據(jù)對象；D為樣本數(shù)據(jù)；dist(p,q)為對象p、q兩者間的距離.

2）數(shù)據(jù)閾值（M inPts）：在Eps鄰域內(nèi)，所有數(shù)據(jù)對象的數(shù)量最小閾值即為數(shù)據(jù)閾值MinPts.

3）核心數(shù)據(jù)對象：對象p的Eps鄰域內(nèi)的樣本數(shù)大于或等于MinPts時，對象p即為核心數(shù)據(jù)對象.

4）直接密度可達：q在核心數(shù)據(jù)對象p的ε鄰域內(nèi)，即為對象q是從對象p的直接密度可達.

5）密度可達：在樣本數(shù)據(jù)集D中，若存在一串?dāng)?shù)據(jù)對象p,p1,p2,···,pn,q，并且對象p1是從對象p直接密度可達，對象pi+1是從對象pi直接密度可達，即對象q是從對象p密度可達.

6）密度相連:在樣本數(shù)據(jù)集D中,所有對象都是密度可達時，即稱為互為密度相連.

7）簇和噪聲：與核心數(shù)據(jù)對象p密度可達的所有對象即成為一個簇，不被包含在簇內(nèi)的點，即稱為噪聲點.

2.2 DBSCAN原理

DBSCAN算法主要思想是將鄰域內(nèi)密度相連的數(shù)據(jù)點的最大數(shù)據(jù)集歸類合并成一個簇，進而將所有各組密度相連的樣本劃為不同的類別.算法描述如下：

1）通過掃描整個數(shù)據(jù)集D，隨機選擇一個未分類的數(shù)據(jù)對象p；

2）根據(jù)對象數(shù)量Nε(p)和數(shù)據(jù)閾值MinPts進行判斷：若Nε(p)≥MinPts，則p為核心數(shù)據(jù)對象，并且找到從該核心數(shù)據(jù)對象p出發(fā)的Eps鄰域內(nèi)所有密度相連的數(shù)據(jù)對象，構(gòu)成一個簇；否則將p標記為噪聲；

3）重復(fù)步驟2），直到將數(shù)據(jù)集D中的所有數(shù)據(jù)遍歷完,即數(shù)據(jù)對象被歸為某一簇或者認定為噪聲，結(jié)束運行.

2.3 DBSCAN算法改進

為了進一步提高GPS定位精準度，我們對DBSCAN聚類思想提出改進.首先將分類后的數(shù)據(jù)進行二次聚類，將誤判為噪聲的點歸入最近的簇內(nèi)，然后在類中求算術(shù)均值和類間加權(quán)求重心，圖2是算法流程圖，算法步驟如下：

圖2 改進DBSCAN算法流程圖

1）輸入終止迭代條件φ以及最大迭代次數(shù)Maxtimes；

2）計算各簇中心

通過計算各個噪聲到簇中心點的距離，將誤判為噪聲的點歸入最近的簇內(nèi)，并重新計算該簇的中心點；

3）當(dāng)?shù)鷹l件滿足|E1?E2|<φ或者迭代次數(shù)為Maxtimes，結(jié)束算法，否則繼續(xù)迭代.

4）將經(jīng)過二次聚類的分類結(jié)果，求類中算術(shù)均值，即

5）類間加權(quán)求重心，即(Gx,Gy)

式中：H為數(shù)據(jù)集過濾后的數(shù)據(jù)總和；為加權(quán)之后的重心，即為最終GPS定位系統(tǒng)坐標.

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

GPS定位系統(tǒng)的精度容易受到環(huán)境因素影響，因此，本文以視野空曠的城市中心P1和偏僻的山谷P2為例，采用手機內(nèi)置的GPS集成設(shè)備，對固定地點每隔5 s輸出一次定位數(shù)據(jù)，將連續(xù)獲取的200個數(shù)據(jù)組成原始數(shù)據(jù)集進行算法測試.

同時，考慮到AR實景導(dǎo)航系統(tǒng)APP對移動終端設(shè)備高性價比的需求，本文采用中低端移動平臺華為暢享10手機作為算法測試平臺，該終端性能參數(shù)如表1所示.

表1 華為暢享10手機參數(shù)

詳細實驗步驟及結(jié)果分析如下：

1）采用卡爾曼濾波處理GPS采集到的經(jīng)緯度坐標數(shù)據(jù).圖3（a）為P1經(jīng)過卡爾曼濾波后的數(shù)據(jù)分布，經(jīng)緯度平均誤差為4.7m；圖3（b）為P2經(jīng)過卡爾曼濾波后的數(shù)據(jù)集分布，經(jīng)緯度平均誤差為7.8m.

圖3 卡爾曼濾波后的數(shù)據(jù)分布

2）使用改進后的DBSACN聚類思想對卡爾曼濾波后的GPS數(shù)據(jù)進行分析.由于GPS定位數(shù)據(jù)坐標的誤差只有萬分位以后的數(shù)據(jù)有變化，為了使實驗結(jié)果更加明顯，我們直接對變化的數(shù)據(jù)位數(shù)進行實驗分析.

由于不同的Eps和MinPts的參數(shù)值直接影響聚-類結(jié)果，本文采用李文杰等[14]提出了基于K-平均最臨近數(shù)據(jù)關(guān)聯(lián)與DBSCAN相結(jié)合的K-ANN-DBSCAN算法獲取參數(shù)，該算法根據(jù)數(shù)據(jù)集自身分布特點，自動選取最優(yōu)參數(shù)值，并得到高準確度的聚類結(jié)果.實驗結(jié)果顯示，P1點：Eps=1.1，MinPts=3；P2點：Eps=28，MinPts=5是最優(yōu)參數(shù)組合.

圖4（a）和圖4（b）分別為P1聚類前后的數(shù)據(jù)分布.圖5（a）和圖5（b）分別為P2聚類前后的數(shù)據(jù)分布.其中黑色為噪聲點，不同顏色為不同的簇.

實驗結(jié)果表明，P1和P2的數(shù)據(jù)被分為3簇，誤差較大的點被準確的標記為噪聲，誤判為噪聲點的數(shù)據(jù)經(jīng)過二次聚類歸為相應(yīng)的簇內(nèi)，聚類效果理想.

圖4 P1聚類前后數(shù)據(jù)分布

圖5 P2聚類前后的數(shù)據(jù)分布

3）我們對聚類實驗結(jié)果類中數(shù)據(jù)求均值，類間進行加權(quán)求重心.圖6（a）和圖6（b）分別為P1、P2加權(quán)求重心的聚類結(jié)果.其中三角形表示各簇中心點，五角星表示加權(quán)求得的重心，即GPS定位最終坐標點.

表2是本文算法計算得到的經(jīng)緯度坐標值與真實坐標位置的誤差分析.經(jīng)過計算可得P1坐標平均誤差是2.1m；P2坐標平均誤差是3.4m.本文提出的算法經(jīng)計算接近真實坐標，符合GPS系統(tǒng)定位誤差3～5m的要求.

圖6 P1、P2加權(quán)求重心的聚類結(jié)果

表2 P1和P2定位誤差的比較

4）為了驗證改進后DBSCAN算法的可靠性和準確性，我們以學(xué)校圖書館廣場為例進行GPS數(shù)據(jù)采集，并與DBSCAN+算術(shù)均值算法[10]和擴展卡爾曼濾波算法[11]進行對比分析.表3是文獻[10]和文獻[11]的算法和本文算法在不同方向和維度的定位誤差的比較分析結(jié)果.在文獻[11]算法中我們主要針對低速動態(tài)卡爾曼濾波算法與本文算法的對比分析.

表3 不同算法定位精度數(shù)據(jù)對比

實驗證明，本文算法與文獻[10]算法相比較,在東向、北向定位精度分別提高10.72%和9.79%，在2D和3D不同維度分別提高9.81%和10.31%；與文獻[11]算法相比較,在東向、北向定位精度分別提高6.40%和6.02%，在2D和3D不同維度分別提高6.36%和8.74%.本文算法有效控制了誤差范圍，進一步提高了GPS的定位精度.

圖7～9分別是通過文獻[10]、文獻[11]算法和本文算法優(yōu)化處理后的GPS數(shù)據(jù)分布.由圖可知，本文算法相較文獻[10]、文獻[11]算法噪聲點數(shù)量明顯減少，數(shù)據(jù)誤差控制在更小的范圍內(nèi)且集中向真實坐標點靠近.

另外，我們將此算法應(yīng)用于開發(fā)的AR校園實景定位導(dǎo)航系統(tǒng)，通過在校園選擇多地點進行測試，總體定位誤差在3～5m，路徑規(guī)劃時間不足0.1 s，系統(tǒng)的流暢性完全滿足AR實景導(dǎo)航系統(tǒng)的要求.如圖10是不同方向AR實景導(dǎo)航路徑效果圖，圖10（a）是西南方向，圖10（b）是北方向；其中圖的上部分是衛(wèi)星導(dǎo)航地圖，下部分顯示實景地圖.

圖7 文獻[10]算法定位實驗結(jié)果

圖8 文獻[11]算法定位實驗結(jié)果

圖10 AR實景導(dǎo)航不同方向效果展示

4 結(jié)語

本文提出的使用基于卡爾曼濾波算法能有效控制誤差范圍，通過DBSCAN二次聚類加權(quán)重心修正GPS的單點定位誤差的組合定位優(yōu)化算法，與文獻[10]和文獻[11]的GPS定位算法相比，綜合定位精度進一步得到提高，平均提高10.16%和6.88%左右，定位精度進一步得到提高。

基于智能手機自帶GPS系統(tǒng)通過本文提出改進算法來提高定位的精準度，具有成本低，使用方便的優(yōu)勢，能夠滿足移動端AR實景導(dǎo)航系統(tǒng)定位精度、實時性和魯棒性的需求.

本文未考慮復(fù)雜惡劣環(huán)境下GPS單點定位精度準確性和可靠性的問題.最近的研究表明，通過5G移動通信、多定位系統(tǒng)的組合[15]可以有效改善此問題.例如，彭勇等[16]提出對卡爾曼濾波算法做出改進設(shè)計，并將其應(yīng)用于組合系統(tǒng)導(dǎo)航定位，提高了定位導(dǎo)航系統(tǒng)的精確度和穩(wěn)定性；Zhao等[17]通過對北斗衛(wèi)星導(dǎo)航系統(tǒng)（BDS）/GPS/低地球軌道（LEO）組合仿真，并在惡劣環(huán)境下進行模擬測試證明，多定位系統(tǒng)組合比單一定位系統(tǒng)的性能和定位精有所提高，但實現(xiàn)相對復(fù)雜；高曉等[18]將GPS/BDS組合系統(tǒng)應(yīng)用于無人機中，改善無人機動態(tài)定位精度和可靠性.

由此，如何將本文算法進一步拓展應(yīng)用于BDS/GPS/LEO組合系統(tǒng)導(dǎo)航定位，提高在復(fù)雜環(huán)境下的AR實景導(dǎo)航系統(tǒng)的定位精度將是我們下一步的研究工作.