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

葛倩，侯守明，趙文濤

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

0 引言

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

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

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

1 卡爾曼濾波模型及數據處理

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

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

1）通過k?1時刻預測k時刻的狀態

2）通過k?1時刻估算k時刻的系統誤差Pk

式中，Q為觀測噪聲協方差矩陣。

3）更新卡爾曼增益Kk

式中，R為測量噪聲協方差矩陣.

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

5）在系統運行結束前，卡爾曼濾波需要計算當前時刻的系統誤差，以便下一時刻進行計算.k時刻的系統誤差Pk

式中，I為單位矩陣.

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

圖1 卡爾曼濾波后的GPS數據分布

2 DBSCAN聚類加權重心定位模型

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

2.1 DBSCAN算法的相關定義

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

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

2）數據閾值（M inPts）：在Eps鄰域內，所有數據對象的數量最小閾值即為數據閾值MinPts.

3）核心數據對象：對象p的Eps鄰域內的樣本數大于或等于MinPts時，對象p即為核心數據對象.

4）直接密度可達：q在核心數據對象p的ε鄰域內，即為對象q是從對象p的直接密度可達.

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

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

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

2.2 DBSCAN原理

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

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

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

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

2.3 DBSCAN算法改進

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

圖2 改進DBSCAN算法流程圖

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

2）計算各簇中心

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

3）當迭代條件滿足|E1?E2|<φ或者迭代次數為Maxtimes，結束算法，否則繼續迭代.

4）將經過二次聚類的分類結果，求類中算術均值，即

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

式中：H為數據集過濾后的數據總和；為加權之后的重心，即為最終GPS定位系統坐標.

3 實驗結果與分析

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

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

表1 華為暢享10手機參數

詳細實驗步驟及結果分析如下：

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

圖3 卡爾曼濾波后的數據分布

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

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

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

實驗結果表明，P1和P2的數據被分為3簇，誤差較大的點被準確的標記為噪聲，誤判為噪聲點的數據經過二次聚類歸為相應的簇內，聚類效果理想.

圖4 P1聚類前后數據分布

圖5 P2聚類前后的數據分布

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

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

圖6 P1、P2加權求重心的聚類結果

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

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

表3 不同算法定位精度數據對比

實驗證明，本文算法與文獻[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]算法和本文算法優化處理后的GPS數據分布.由圖可知，本文算法相較文獻[10]、文獻[11]算法噪聲點數量明顯減少，數據誤差控制在更小的范圍內且集中向真實坐標點靠近.

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

圖7 文獻[10]算法定位實驗結果

圖8 文獻[11]算法定位實驗結果

圖10 AR實景導航不同方向效果展示

4 結語

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

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

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

由此，如何將本文算法進一步拓展應用于BDS/GPS/LEO組合系統導航定位，提高在復雜環境下的AR實景導航系統的定位精度將是我們下一步的研究工作.