基于GIS的室內(nèi)定位約束與優(yōu)化算法

林巍凌

(1.信息工程大學(xué)，河南 鄭州 450000；2.海軍兵種指揮學(xué)院，廣東 廣州 510430)

?

基于GIS的室內(nèi)定位約束與優(yōu)化算法

林巍凌1,2

(1.信息工程大學(xué)，河南 鄭州 450000；2.海軍兵種指揮學(xué)院，廣東 廣州 510430)

摘要：隨著室內(nèi)定位技術(shù)的不斷發(fā)展，室內(nèi)導(dǎo)航漸漸成為可能。但由于室內(nèi)定位精度和穩(wěn)定性較差，導(dǎo)致定位點(diǎn)漂移，導(dǎo)航引導(dǎo)錯誤，用戶體驗(yàn)感差，無法滿足室內(nèi)精細(xì)導(dǎo)航需求。文中根據(jù)室內(nèi)空間的特點(diǎn)，結(jié)合GIS空間分析與導(dǎo)航推測算法，設(shè)計出一種適合室內(nèi)定位約束與優(yōu)化算法，能在不影響定位效率的情況下很大程度上改善定位效果。經(jīng)實(shí)際場地實(shí)驗(yàn)，效果良好。

關(guān)鍵詞：室內(nèi)定位；定位約束；室內(nèi)地圖；DR；導(dǎo)航推測

隨著定位與導(dǎo)航技術(shù)應(yīng)用的普及，人們對定位信息的需求逐漸拓展到室內(nèi)，但不管是定位手段還是地圖表達(dá)，室內(nèi)一直是業(yè)界研究的一塊盲區(qū)。十多年以來，為了解決室外定位導(dǎo)航“最后一公里”的問題，科技巨頭和研究機(jī)構(gòu)在室內(nèi)定位技術(shù)方面開展了大量的研究，如基于移動通信網(wǎng)絡(luò)的輔助GPS(A-GPS)、偽衛(wèi)星(Pseudolite)、無線局域網(wǎng)(WLAN)、射頻標(biāo)簽(RFID)、Zigbee、藍(lán)牙(Bluetooth，BT)、超寬帶無線電(UltraWideBand，UWB)、地磁其他衛(wèi)星或地面數(shù)字通信及廣播信號、紅外定位、光跟蹤定位、計算機(jī)視覺定位、超聲波定位等。室內(nèi)定位技術(shù)的長足進(jìn)步，促進(jìn)室內(nèi)地圖研究的興起。谷歌于2011-11率先發(fā)布了室內(nèi)地圖，其中包括了美國、日本等國家的大型商場和機(jī)場。此后國內(nèi)地圖廠商，如百度、高德也相繼推出自己的室內(nèi)地圖產(chǎn)品。不少創(chuàng)業(yè)公司也不失時機(jī)地展開研究，企圖占有一席之地。有了室內(nèi)地圖，可以幫助用戶更加清晰地辨別每個樓層的建筑物平面布局，了解建筑物內(nèi)主要興趣點(diǎn)的分布，給用戶帶來全新的購物、休閑體驗(yàn)。據(jù)不完全統(tǒng)計，目前可做展示使用的室內(nèi)地圖普遍比例尺在1∶50，甚至更大，覆蓋全國300座城市，超過100萬個室內(nèi)興趣點(diǎn)。但由于室內(nèi)定位精度較差(通常在3～10m)，無法達(dá)到精細(xì)導(dǎo)航的需求，因此，本文提出一種室內(nèi)定位約束算法，在一定程度上對定位結(jié)果進(jìn)行修正，使定位效果更佳(并非提高定位精度)。

1室內(nèi)定位約束必要性

目前主流室內(nèi)定位技術(shù)均基于傳感器(Wi-Fi或者藍(lán)牙)進(jìn)行定位，而室內(nèi)環(huán)境錯綜復(fù)雜，干擾源多，信號反射、折射、衍射產(chǎn)生多徑傳播，室內(nèi)的溫度濕度變化，物體變動，人員流動都會對室內(nèi)定位精度產(chǎn)生影響(見表1)。不管采用哪種定位技術(shù)，都擺脫不了其自身的局限性。

表1　不同定位技術(shù)對比

定位精度和穩(wěn)定性差在實(shí)際導(dǎo)航應(yīng)用中表現(xiàn)為定位點(diǎn)跳躍、穿越、倒退、偏離路線、方向錯誤、引導(dǎo)錯誤等。這些問題解決不了，室內(nèi)精細(xì)導(dǎo)航就無從談起。在室內(nèi)定位技術(shù)尚不成熟的情況下，只能利用算法對其進(jìn)行優(yōu)化、修正，以期達(dá)到更好的定位效果。

2室內(nèi)定位約束與優(yōu)化

室外車載導(dǎo)航系統(tǒng)可以采用多種車輛定位方式，例如GPS、INS(InertialNavigationSystem)、DR(DeadReckoning)，且車載導(dǎo)航系統(tǒng)能從車輛中獲取各種狀態(tài)參數(shù)，例如速度、行進(jìn)角度、轉(zhuǎn)數(shù)等等，融合道路數(shù)據(jù)可以對定位點(diǎn)做到非常精準(zhǔn)位置估計。而室內(nèi)由于環(huán)境限定，能融合的數(shù)據(jù)比較少，且室內(nèi)空間開放，沒有顯性的道路要素，要素排列緊密，因此，室內(nèi)道路約束難度要遠(yuǎn)遠(yuǎn)大于室外。

2.1數(shù)據(jù)準(zhǔn)備

室內(nèi)定位約束同樣需要各種數(shù)據(jù)的支持，在室內(nèi)環(huán)境中，為了獲得更強(qiáng)的普適性，可以利用的數(shù)據(jù)大致有3類:①終端傳感器數(shù)據(jù)。包括終端的電子羅盤、加速度計等。②與定位匹配的矢量地圖數(shù)據(jù)。包括地圖要素、道路拓?fù)鋽?shù)據(jù)等。③用戶行為數(shù)據(jù)。包括用戶行進(jìn)的歷史軌跡、行為習(xí)慣等。

2.1.1傳感器數(shù)據(jù)

目前，絕大部分的智能移動終端都配備各種傳感器，主要有重力傳感器、距離傳感器、電子羅盤、光線傳感器、三軸陀螺儀、紅外傳感器、計步器傳感器，部分設(shè)備還配備氣壓傳感器、磁場傳感器等。這些傳感器數(shù)據(jù)對定位約束提供極大的幫助,如表2所示。

表2　主要傳感器提供數(shù)據(jù)及其作用

因此，盡可能多的收集并利用移動終端傳感器數(shù)據(jù)，對于室內(nèi)定位的約束優(yōu)化將起到至關(guān)重要的作用。

2.1.2地圖數(shù)據(jù)

定位離開地圖的配合將會變得難以理解。定位通過地圖進(jìn)行表達(dá)，因此，地圖數(shù)據(jù)給定位提供最基本的數(shù)學(xué)基礎(chǔ)和載體。同時定位提供給用戶最基本的方位指示，可以說定位與地圖相輔相成。因此，地圖數(shù)據(jù)能夠提供給定位很多輔助，是定位約束優(yōu)化最為基本也是最為重要的手段。

室內(nèi)地圖數(shù)據(jù)大致包括要素信息以及拓?fù)湫畔?。由于室?nèi)是開放空間，沒有顯性的道路要素，道路要素通常也不明確表達(dá)。所有室內(nèi)道路拓?fù)渚鶠樵谏a(chǎn)室內(nèi)地圖時生成。在導(dǎo)航時，調(diào)用道路拓?fù)鋽?shù)據(jù)進(jìn)行路徑規(guī)劃，從而顯示出模擬的路線。在室外導(dǎo)航系統(tǒng)中，定位約束可以簡單地將定位點(diǎn)約束到規(guī)劃路線上即可，但在室內(nèi)這么處理會導(dǎo)致很多問題，如圖1所示。

圖1　室內(nèi)道路約束常見問題

因此，要解決這些問題光靠道路拓?fù)鋽?shù)據(jù)遠(yuǎn)遠(yuǎn)不夠，需要專門制作用于定位約束的數(shù)據(jù)，且不同的約束文件，產(chǎn)生的效果也不同。

2.1.3用戶行為數(shù)據(jù)

用戶行為數(shù)據(jù)主要包括用戶的歷史軌跡、行走習(xí)慣、用戶行為習(xí)慣等。這些數(shù)據(jù)需要經(jīng)過長時間的搜集并處理之后才能運(yùn)用?？梢杂脕眍A(yù)測用戶下一步的行為，對定位點(diǎn)進(jìn)行一定預(yù)判，達(dá)到優(yōu)化的目的。

2.2算法設(shè)計

通過分析定位點(diǎn)精度不穩(wěn)定產(chǎn)生的問題，歸納起來大概有以下兩類：一是定位點(diǎn)漂移；二是導(dǎo)航錯誤問題。定位點(diǎn)漂移問題解決重點(diǎn)在于將定位點(diǎn)約束到一定范圍內(nèi)，使其在可接受范圍內(nèi)移動。導(dǎo)航錯誤問題主要表現(xiàn)為倒退、偏離航線、錯誤方向等。在室外，解決這類問題主要手段是道路匹配和導(dǎo)航推測(DeadReckoning，DR)。在室內(nèi)，通過融合智能終端傳感器的信息，也可以使用類似方法。因此，整個算法流程如圖2所示。

圖2　定位約束算法流程

1)獲取一個定位點(diǎn)，根據(jù)地圖的數(shù)學(xué)基礎(chǔ)進(jìn)行坐標(biāo)變換，形成一個初始定位點(diǎn)。

2)利用前期處理出來的約束數(shù)據(jù)對定位點(diǎn)進(jìn)行約束修正，保證定位點(diǎn)位于有效區(qū)域內(nèi)，為后續(xù)道路匹配和DR提供一個較好的結(jié)果。

3)對定位點(diǎn)進(jìn)行路網(wǎng)匹配，使定位點(diǎn)盡可能沿著既定路線移動。

4)利用傳感器數(shù)據(jù)以及用戶行為數(shù)據(jù)對航跡進(jìn)行預(yù)測，從而進(jìn)一步優(yōu)化定位點(diǎn)。

5)將定位點(diǎn)輸出至地圖，并將用戶的本次定位進(jìn)行記錄，將作為下一次導(dǎo)航推測的依據(jù)。

2.3算法實(shí)現(xiàn)

2.3.1定位約束文件生成

定位約束文件主要用來對原始定位點(diǎn)進(jìn)行初步的篩選和優(yōu)化，對后續(xù)定位預(yù)測起到至關(guān)重要的作用。本文提出兩種比較有效的生成方案。

方案1：柵格法

柵格法的中心思想是將地圖按一定比例柵格化，并按可通行區(qū)域和不可通行區(qū)域進(jìn)行二值化(黑色為不可通行區(qū)，白色為可通行區(qū)域)，具體步驟如下：

1)讀取室內(nèi)地圖，并按照一個像素0.5m的比例尺生成黑色柵格圖像。

2)遍歷地圖要素，若為可通達(dá)區(qū)域，則在圖像上繪制成白色。

3)遍歷所有路網(wǎng)，并對其做緩沖區(qū)，并對緩沖區(qū)填充成白色。

4)對生成的二值圖像做優(yōu)化處理，例如膨脹、腐蝕，去除一些微小的孤島和干擾面。如圖3所示。

圖3　柵格定位約束文件生成示意圖

使用柵格法制作定位約束數(shù)據(jù)有很多優(yōu)點(diǎn)：制作簡便，數(shù)據(jù)量小，計算效率高，容易理解，修改方便等；但也有不可避免的缺點(diǎn)，例如可通行區(qū)域根據(jù)路網(wǎng)生成，限定太死，定位點(diǎn)很容易卡死；柵格數(shù)據(jù)只能用于判定定位點(diǎn)是否位于有效區(qū)內(nèi)，用于空間分析效率低，因此不適合用于復(fù)雜度更高的運(yùn)算；而矢量方案則可以彌補(bǔ)這些不足。

方案2：矢量法

矢量法區(qū)別于柵格法之處在于用幾何形狀來描述有效區(qū)域。生成有效區(qū)時，可以假定室內(nèi)區(qū)域所有區(qū)域均可以到達(dá)，然后將不可到達(dá)區(qū)域(例如天井、墻壁等)扣除后就是最終的定位約束區(qū)域。

矢量法生成的定位約束文件為矢量數(shù)據(jù)，可以將其認(rèn)為是實(shí)體要素，可以跟任何其他要素進(jìn)行空間關(guān)系判斷和進(jìn)行空間分析；另外可以看出，矢量定位約束文件能最大程度的描述出可通行區(qū)域，從而可以更精準(zhǔn)地對定位進(jìn)行約束。但矢量定位數(shù)據(jù)量比較大，且隨著要素復(fù)雜度變高數(shù)據(jù)量也隨著變大。不過，矢量數(shù)據(jù)理解起來不如柵格數(shù)據(jù)直觀，修改也比柵格數(shù)據(jù)要麻煩，如圖4所示。

圖4　矢量定位約束文件示意圖

由于兩種方案都有不可避免的缺點(diǎn)，本文采取的策略為當(dāng)室內(nèi)地圖較為簡單時直接調(diào)用柵格方案；當(dāng)室內(nèi)地圖要素多，且復(fù)雜度高時，將先利用柵格方案快速糾正，若糾正不理想，則調(diào)用矢量方案進(jìn)行進(jìn)一步校正，從而達(dá)到最好的效果。通過實(shí)際驗(yàn)證，在大部分情況下柵格方案在效率上表現(xiàn)得更為優(yōu)秀；而矢量方案則效果更好。通過結(jié)合兩者，可以在很大程度上改善定位效果。

2.3.2道路匹配算法

在矢量地圖表達(dá)模型中，道路要素是由弧段和節(jié)點(diǎn)抽象的?；《尾荒苡蟹种В挥衅鹗脊?jié)點(diǎn)和終止節(jié)點(diǎn)。節(jié)點(diǎn)用來表達(dá)弧段的關(guān)聯(lián)關(guān)系和幾何位置。道路通常由若干條弧段組合而成，如圖5所示。

圖5中1～9為節(jié)點(diǎn)，[1,2,3,4]、[4,5,6,7]、[4,9,8]構(gòu)成3條弧段。假設(shè)用戶從節(jié)點(diǎn)8走向節(jié)點(diǎn)9，其中G點(diǎn)為定位點(diǎn)坐標(biāo)，P點(diǎn)為用戶實(shí)際位置，那么Ek表示定位點(diǎn)到用戶實(shí)際位置的誤差，該誤差為定位誤差與定位點(diǎn)坐標(biāo)轉(zhuǎn)換誤差的綜合。

圖5　道路抽象示意圖弧段[8,9]的方程表示為

(1)

建立用戶運(yùn)動的卡爾曼濾波離散化狀態(tài)方程式(2)和觀測方程式(3)。

(2)

(3)

卡爾曼濾波器的狀態(tài)變量為U=(Xk,Yk,vx,vy,ax,ay,ex,ey)，其中Xk，Yk為x方向和y方向的位置分量；vx，vy為x方向和y方向的速度分量;ax，ay為x方向和y方向的加速度分量；ex,ey為綜合誤差在x方向和y方向的分量；wk為高斯白噪聲；方差為Q。其中：

式中：T為卡爾曼濾波器狀態(tài)估計的更新時間，τ為相關(guān)時間系數(shù)。

將原始定位點(diǎn)坐標(biāo)G與速度信息vx和vy作為外部觀測量，系統(tǒng)的觀測方程的觀測變量為A=(Xk,Yk,vx,vy)，w(k)為高斯白噪聲，方差為R。觀測方程的觀測矩陣為

當(dāng)用戶在某條道路上行進(jìn)時，軌跡點(diǎn)實(shí)際位置P應(yīng)滿足式(1)，即道路對用戶行進(jìn)狀態(tài)起到了約束作用，成為系統(tǒng)模型的約束條件。道路方程式(1)、系統(tǒng)狀態(tài)方程式(2)和觀測方程式(3)構(gòu)成了道路約束條件的系統(tǒng)模型，根據(jù)廣義最小二乘法原理可以推導(dǎo)出帶約束條件的卡爾曼濾波算法，得到公式如下：

(4)

通過該算法，不斷地將定位點(diǎn)往道路上進(jìn)行糾正，從而達(dá)到抑制定位點(diǎn)漂移的作用，但由于室內(nèi)道路是人為界定，因此，糾正過后也許并不是最佳選擇。另外道路約束不能解決導(dǎo)航時停頓、倒退等狀態(tài)問題，這就需要依靠導(dǎo)航推測算法來解決。

2.3.3DR算法

航位推測最早應(yīng)用于航海的航行定位中，是一種利用物體現(xiàn)在位置及速度推測未來位置和方向的航海技術(shù)。由于需要使用加速度計、磁羅盤、陀螺儀，成本高，尺寸大，因此，并沒有在其他交通領(lǐng)域廣泛推廣。近年來，隨著微電子技術(shù)的發(fā)展，這些設(shè)備的重量、體積、成本都極大降低，使航位推測法可以在車載、智能終端中得以應(yīng)用。本文也將利用DR技術(shù)來對定位點(diǎn)進(jìn)行預(yù)測與推算，從而使定位點(diǎn)更加平滑與真實(shí)。

假設(shè)行人運(yùn)動均在二維平面上，在短時間內(nèi)可以認(rèn)為行人在做直線運(yùn)動，獲取起始點(diǎn)位置信息，就可以通過算法預(yù)測下一刻精確的位置信息及其坐標(biāo)軸上的偏移量，如下式：

或者

式中：O(x,y)為目標(biāo)點(diǎn)；R(x,y)為起始點(diǎn)；v為速度；a為加速度；Δt為時間差。

整個推測過程需要確定兩個關(guān)鍵因素：行進(jìn)位移S和行進(jìn)方向角θ。

1)獲取行進(jìn)距離。行進(jìn)的位可以通過經(jīng)典計步器原理計算獲取。人們在行進(jìn)過程中，會在垂直和水平方向產(chǎn)生加速度，并產(chǎn)生周期性變化，利用這個原理可以用于計算行走步數(shù)，如圖6所示。

圖6　人們邁步加速度變化示意圖

若智能移動終端配備計步器傳感器，則可直接獲取數(shù)據(jù)。

2)獲取行進(jìn)方向角。智能移動終端一般配備電子羅盤，通過該傳感器即可得到絕對航向角(0°～360°)。方法簡單易用，但電子羅盤極易受到干擾，導(dǎo)致角度精度不穩(wěn)定。若對角度精度要求較高可以利用捷聯(lián)航向角來替代絕對航向角度。捷聯(lián)航向角計算方法為：獲取智能移動終端三軸陀螺儀數(shù)據(jù)，對其進(jìn)行積分運(yùn)算并結(jié)合初始航向角進(jìn)行一定角度轉(zhuǎn)化而得。捷聯(lián)航向角獲取不受外界干擾，當(dāng)電子羅盤角度不穩(wěn)定時，可以用于輔助計算前進(jìn)方向信息。

通過航行推測，可以在很大程度上優(yōu)化定位效果，防止絕大部分導(dǎo)航問題的出現(xiàn)。

3現(xiàn)場實(shí)驗(yàn)

本文用于測試的手機(jī)為GoogleNexus5，配備了重力傳感器、電子羅盤、三軸陀螺儀以及計步器傳感器。詳細(xì)測試如圖7所示。

圖7　實(shí)地測試結(jié)果

圖7中，虛線表示的是實(shí)際的路網(wǎng)信息；虛線表示實(shí)際定位點(diǎn)形成的軌跡；粗實(shí)線是經(jīng)過定位約束優(yōu)化后形成的軌跡。本次測試總共采集了312個定位點(diǎn)，定位點(diǎn)間隔約1s，行走距離約120m，按正常速度(約5km/h)，計步器計算步數(shù)約252步，定位精度平均3.5m，方向誤差±2.5°?？梢钥闯觯?jīng)過約束和優(yōu)化后，定位效果得到明顯改善；圓圈所在之處出現(xiàn)倒退的現(xiàn)象由于采用了航位推測，也被正確糾正。

4結(jié)束語

本文針對室內(nèi)定位的特點(diǎn)設(shè)計了適合室內(nèi)定位約束優(yōu)化算法，對于改善和提高定位效果起到了重要作用，能為室內(nèi)精細(xì)導(dǎo)航提供有效輔助。

參考文獻(xiàn)：

[1]汪苑，林錦國.幾種常用室內(nèi)定位技術(shù)的探討[J].中國儀器儀表,2011(2):54-57.

[2]宋敏，申閆春.室內(nèi)定位航位推算法的研究與實(shí)現(xiàn)[J].計算機(jī)工程,2013,39(7):293-297.

[3]HIGHTOWERJ，BORRIELLOG.LocationSystemsforUbiquitousComputing[J].JournalofComputer，2001，34(8).

[4]劉艷,鮑遠(yuǎn)律,左峻疆.基于GIS的導(dǎo)航系統(tǒng)地圖匹配算法[J].微型機(jī)與應(yīng)用,2005(6):52-53.

[5]COLLIERWC.In-vehicleRouteGuidanceSystemsUsingMapMatchedDeadReckoning[C].ProceedingsofIEEEPosition，LocationandNavigationSymposium，1990.

[6]畢軍,付夢印，張宇河.基于D-S證據(jù)推理的車輛導(dǎo)航系統(tǒng)地圖匹配算法[J].北京理工大學(xué)學(xué)報,2002,22(3):393-395.

[7]伍小潔,房建成.一種帶速度觀測量的GPS動態(tài)定位自適應(yīng)卡爾曼濾波算法[J].中國慣性技術(shù)學(xué)報,2000,8(3)：27-32.

[8]楊廣龍,孔勇平,鐘致民，等.基于多模指紋匹配的室內(nèi)定位系統(tǒng)設(shè)計與實(shí)現(xiàn)[J].計算機(jī)工程與設(shè)計，2013，34(5)：1896-1901.

[9]馬海兵，黃智偉，黃樂樂，等.基于ArcGIS的室內(nèi)地圖服務(wù)系統(tǒng)的設(shè)計與實(shí)現(xiàn)[J].測繪與空間地理信息，2015，38(3)：92-94.

[10] 孫偉，丁偉，徐愛功，等.基于微慣性技術(shù)的室內(nèi)定位理論及應(yīng)用[J].測繪與空間地理信息，2015，38(9)：84-88.

[11]CHENX,SCHONFELDD,KHOKHARA.Localizationandtrajectoryestimationofmobileobjectswithasinglesensor.2007.

[12]DIFC，F(xiàn)ICCOM，RUSSOS.Indoorandoutdoorlocationbasedservicesforportablewirelessdevices[C].Proc25thIEEEInternationalConferenceonDistributedComputingSystemsWorkshops,2005.

[13] 楊華,劉軍發(fā),陳益強(qiáng).一種基于多終端動態(tài)協(xié)同的室內(nèi)定位方法[J].計算機(jī)應(yīng)用研究,2012，29(7):2457-2461.

[14] 楊凱，郭英，畢京學(xué).基于安卓平臺的室內(nèi)實(shí)時定位[J].測繪科學(xué)，2015，40(6)：125-128.

[15] 沈田.無線室內(nèi)定位系統(tǒng)研究[J].中國新通信,2009(17):34-35.

[16] 鄒坤,修春娣,楊東凱.基于感知概率的室內(nèi)定位算法[J].全球定位系統(tǒng),2013，38(6):7-11.

[17] 朱志慧.基于多元回歸方法對室內(nèi)定位適應(yīng)性的研究[J].電腦與電信,2011(4):61-62.

[責(zé)任編輯：劉文霞]

DOI:10.19349/j.cnki.issn1006-7949.2016.10.003

收稿日期：2015-06-06；修回日期：2015-09-30

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(41471336)

作者簡介：林巍凌(1979-)，男，講師，博士研究生.

中圖分類號：P228;TP391

文獻(xiàn)標(biāo)識碼：A

文章編號：1006-7949(2016)10-0010-07

Indoor positioning constraints and optimization algorithm based on GIS

LIN Weiling1,2

(1.InformationEngineeringUniversity，Zhengzhou450000，China;2.NavalArmsCommandAcademy，Guangzhou510430，China)

Abstract：With the continuous development of indoor positioning technology，indoor navigation becomes possible gradually.But due to the low accuracy and poor stability of indoor positioning，the drift of positioning points，guiding the navigation error，and less user-friendly effect，cannot meet the fine interior navigation requirements.This paper,combined with GIS spatial analysis and reckoning algorithm，designs a suitable indoor positioning constraints and optimization algorithm based on the characteristics of the indoor space，which can greatly improve the positioning performance.Throught the experiments，the effect proves good.

Key words：indoor positioning;positioning constraints;indoor map;DR;dead reckoning