基于卡爾曼濾波和改進(jìn)DBSCAN聚類組合的GPS定位算法

葛倩，侯守明，趙文濤

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

0 引言

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

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

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

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

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

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

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

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

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

3）更新卡爾曼增益Kk

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

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

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

式中，I為單位矩陣.

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

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

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

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

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時(shí)，對象p即為核心數(shù)據(jù)對象.

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

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

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

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

2.2 DBSCAN原理

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

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

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

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

2.3 DBSCAN算法改進(jìn)

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

圖2 改進(jìn)DBSCAN算法流程圖

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

2）計(jì)算各簇中心

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

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)坐標(biāo).

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

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

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

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

詳細(xì)實(shí)驗(yàn)步驟及結(jié)果分析如下：

1）采用卡爾曼濾波處理GPS采集到的經(jīng)緯度坐標(biāo)數(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）使用改進(jìn)后的DBSACN聚類思想對卡爾曼濾波后的GPS數(shù)據(jù)進(jìn)行分析.由于GPS定位數(shù)據(jù)坐標(biāo)的誤差只有萬分位以后的數(shù)據(jù)有變化，為了使實(shí)驗(yàn)結(jié)果更加明顯，我們直接對變化的數(shù)據(jù)位數(shù)進(jìn)行實(shí)驗(yàn)分析.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖7 文獻(xiàn)[10]算法定位實(shí)驗(yàn)結(jié)果

圖8 文獻(xiàn)[11]算法定位實(shí)驗(yàn)結(jié)果

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

4 結(jié)語

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

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

本文未考慮復(fù)雜惡劣環(huán)境下GPS單點(diǎn)定位精度準(zhǔn)確性和可靠性的問題.最近的研究表明，通過5G移動通信、多定位系統(tǒng)的組合[15]可以有效改善此問題.例如，彭勇等[16]提出對卡爾曼濾波算法做出改進(jìn)設(shè)計(jì)，并將其應(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)境下進(jìn)行模擬測試證明，多定位系統(tǒng)組合比單一定位系統(tǒng)的性能和定位精有所提高，但實(shí)現(xiàn)相對復(fù)雜；高曉等[18]將GPS/BDS組合系統(tǒng)應(yīng)用于無人機(jī)中，改善無人機(jī)動態(tài)定位精度和可靠性.

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