基于PDR和地理網格的室內外一體化定位方法

原 璟，程 承 旗，童 曉 沖，陳 東

(1.北京大學遙感與地理信息系統研究所，北京 100871；2.北京大學工學院，北京 100871；3.信息工程大學地理空間信息學院，河南 鄭州 450001;4.國家信息中心，北京 100045)

基于PDR和地理網格的室內外一體化定位方法

原 璟1，程 承 旗2*，童 曉 沖3，陳 東4

(1.北京大學遙感與地理信息系統研究所，北京 100871；2.北京大學工學院，北京 100871；3.信息工程大學地理空間信息學院，河南 鄭州 450001;4.國家信息中心，北京 100045)

為降低現有定位方法對基礎設施和電子地圖的依賴程度，該文結合環境中的二維碼信息與智能手機傳感器采集的數據，提出了一種基于行人航跡推算(PDR)技術和地理網格的室內外一體化定位方法。該方法由網格編碼提供室內外一體的位置信息，消除PDR定位過程中的累積誤差，并通過便捷的編碼運算實現位置的高效求解，最終以網格單元展示行人位置與行走軌跡。按照全球規則劃分、多層級嵌套及編碼可計算的地理網格選取原則，以GeoSOT為例開展實驗，定位誤差始終控制在行走距離的5%以內，證明了算法的可行性與有效性。該方法可用于通訊鏈路受阻或地圖難以獲得等特殊場景的輔助定位，對于室內外一體化定位技術的發展具有實用價值。

室內外定位；行人航跡推算(PDR)；地理網格；GeoSOT；智能手機

0 引言

隨著信息技術的發展，人們對地理空間4A(Anytime，Anywhere，Anybody，Anything)服務的需求不斷增長[1]，基于位置的服務(Location Based Services，LBS)逐漸成為人們日常生活的重要組成部分。定位技術作為LBS的基礎研究內容之一，受到學術界和導航工業界的廣泛關注。目前，衛星定位技術在室外的應用已經十分成熟，但在室內或一些特殊場景中，信號衰減、多徑干擾等原因造成衛星定位精度下降[2]，故常采用基于WiFi、藍牙、紅外線、超寬帶、ZigBee等技術的定位方式。與此同時，功能強大、靈活便攜的智能手機的普及使得LBS與定位技術更為大眾化。然而，現有定位系統大多面臨以下問題：1)定位過程依賴空間星座、基站等外部基礎設施，系統建設的工作量大、成本高；2)當電子地圖或室內平面結構圖難以獲得時，位置信息與地圖的關聯失敗，定位功能的應用受限。

行人航跡推算(Pedestrian Dead Reckoning，PDR)[3,4]是一種基于自包含傳感器的相對定位技術，其優勢在于定位的自主性與連續性，即僅依靠加速度計、陀螺儀、磁感應器等傳感器感知行人運動狀況與周圍環境條件，就能夠實現位置的遞歸計算。隨著低功率、多種類的傳感器在智能手機上的廣泛應用，PDR成為理想的輔助定位手段。該技術不需要復雜的基站建設，也不需要對移動設備進行擴展，定位過程無通信開銷。但缺點也十分明顯：定位初期必須依靠其他定位方式獲得初始位置，定位過程中誤差隨行走距離的增長逐漸累積。

地理網格是一種科學、簡明的定位參照系統[5]，網格單元劃分規則、無縫無疊、分級明確[6]，網格編碼描述地物的位置信息及空間關系[7,8]。目前，國內外應用較為成熟的網格與編碼包括美國國家格網(United States National Grid，USNG)[9]、加拿大自然區域編碼(Natural Area Code，NAC)[10]、谷歌開放位置碼(Open Location Code，OLC)[11]、中國國家地理格網[5]、2n一維整型數組的全球經緯度剖分網格(Geographic coordinate Subdividing grid with One dimension integral coding on 2n-Tree，GeoSOT)[12]等。地理網格既可以作為輔助圖層與地圖疊加顯示，也可以脫離地圖而單獨存在，提高了緊急救援、災難管理等場景中的定位效率。因此，PDR技術與地理網格共同應用于智能手機平臺，可以解決通訊鏈路受阻或地圖難以獲得等特殊場景下的定位問題，具有較強的實用性。本文設計了基于PDR與地理網格的室內外一體化定位方法，分析了地理網格選取原則，并以GeoSOT為例論述了PDR與地理網格在位置獲取、位置計算和位置展示3個方面的結合方法。

1 PDR算法基礎

PDR定位以行人步態的生理學特征為基礎，利用加速度計檢測步頻、估算步長[13]，綜合陀螺儀、磁感應器求解航向，在初始位置已知的前提下根據式(1)逐步遞推行人位置，定位原理如圖1所示。

(1)

式中:(x1，y1)表示上一步位置，(x2，y2)表示當前位置，d為步長，θ為航向角。

圖1 PDR算法原理示意[14]

1.1 步頻檢測

步頻檢測的主要目的在于從連續的傳感器數據中識別跨步起點，便于后續步長、方向計算時以單步為單位進行數據處理，本文采用“平滑窗口+峰值探測+動態閾值”的方法檢測步頻[15,16]，具體步驟如下：

第一步，計算剔除重力加速度后的加速度模值a，為簡便起見，直接將線性加速度計的三軸輸出模值(alx，aly，alz)帶入式(2)計算:

(2)

第二步，根據式(3)，使用長度為2N+1的平滑窗口對加速度模值a濾波。

(3)

第三步，峰值探測用于消除身體抖動造成的計步誤差，包括：1)波峰大于閾值apeak；2)波谷小于閾值avalley；3)波峰與波谷的差大于閾值adiff；4)相鄰波峰之間的時間差大于閾值T。

第四步，以當前單步波峰和上一單步波谷的平均值作為動態閾值，加速度波形向上經過該值的時刻即為上一步的結束點和當前跨步的開始。

1.2 步長估算

步長估算可以使用常數/偽常數、線性、非線性、人工智能、單擺等[15]模型法，也可以利用身高或肌電信號等求解。綜合考慮算法復雜度、精度、可操作性等諸多因素，本文選擇式(4)所示的非線性模型[17]，訓練求得模型參數后估算步長。

(4)

式中:amax、amin分別為步頻檢測得到單步加速度模值的最大值和最小值，k1、k2為模型參數。

1.3 方向檢測

方向檢測由加速度計、陀螺儀和磁感應器綜合實現。首先根據加速度計和校準后的磁感應器計算載體坐標系與導航坐標系之間的旋轉矩陣，進而求得初始航向角，并以磁偏角修正。單步的航向以該步內所有采樣點航向角的平均值表示，其中每一個采樣點所對應的航向角以式(5)定義，即：當前時刻陀螺儀z軸輸出值ωiz小于等于閾值ωTh時，采用上一時刻的航向角θi-1；反之，由上一時刻航向角θi-1加陀螺儀積分得到的航向改變量Δθ求得。

(5)

2 地理網格選取原則

地理網格與PDR通過優勢互補，實現了對基礎設施和電子地圖依賴性小的室內外一體化定位。兩者的結合主要表現在：1)位置獲取：地理網格編碼為PDR初始位置輸入和累積誤差清零提供所在位置的絕對坐標；2)位置計算：在PDR算法基礎上，通過地理網格編碼運算實現行人位置的高效求解；3)位置展示：跨步結束時，以地理網格單元展示行人所在位置。

按照上述結合策略，定位參照系統地理網格的選取原則如下：1)全球規則劃分。規則劃分是地理網格提供位置信息的基本前提，全球統一保證了室內外或不同地域之間具有相同的位置表示方式。位置獲取方面，全球地理網格擴展了PDR因累積誤差而受限的定位范圍；位置計算方面，則有助于避免PDR在不同坐標系或量測單位下使用時復雜的轉換操作。2)多層級嵌套。地理網格體系提供了豐富的網格尺度，同層級網格之間無縫無疊、覆蓋全球，相鄰層級之間嚴格嵌套、轉換便捷。位置計算方面，小尺度網格對定位區域的精細表達保證了PDR算法的定位精度；位置展示方面，多尺度網格允許在最佳展示尺度基礎上以不同精度顯示行人位置。3)編碼可計算。地理網格編碼的計算能力是改進傳統PDR算法的重要保證，位移運算等形式的編碼運算實現了編碼與空間區域、編碼與編碼間的快速轉換。其中，編碼位移運算以地理網格間的方位關系與距離關系為基礎，有助于簡化位置計算過程，提高位置計算效率。

3 基于PDR和GeoSOT的室內外一體化定位方法

GeoSOT是按照四叉樹遞歸剖分的方式將全球劃分為具有明確區域位置和尺度特征的32級等經緯度網格體系，滿足PDR算法對地理網格選取所提的全部要求[18]。考慮到GeoSOT厘米級最細表達精度及其較強的編碼計算能力，本文以GeoSOT為例，詳述PDR與地理網格在位置獲取、位置計算與位置展示方面的結合方法。

3.1 位置獲取

位置獲取主要是為定位算法提供代表行人位置的地理網格編碼，實現途徑多樣。本文選擇存儲空間大、識別速度快的二維碼作為位置信息存儲與傳播的媒介，向其中存入四進制一維的GeoSOT編碼。行人通過智能手機掃描二維碼，獲得定位開始所需的初始位置網格編碼或累積誤差清零所需的中間位置網格編碼。這種位置獲取方式類似于在二維碼中存入停車位編號的地下停車場定位，目前已有部分應用實例，可行性較強，通過事先設置典型地物的位置二維碼即可完成定位區域初期建設，不僅能夠實現方便快捷、成本低廉的室內外一體化定位，還解決了通訊鏈路受阻等特殊場景下的定位問題。

3.2 位置計算

GeoSOT在全球范圍內具有統一的定位基礎，是室內外空間數據一體化組織的有效途徑，在實現步頻檢測、步長估算、方向檢測的基礎上，引入編碼位移操作改進按照式(1)計算位置的傳統PDR算法。編碼位移計算以二進制二維的GeoSOT網格編碼為輸入，在東北半球，代表經度的整型編碼加1表示向右平移1個網格，減法表示向左平移；代表緯度的整型編碼加1表示向上平移一個網格，減法表示向下平移。因此，圖2中兩個灰色網格所在位置之間的移動，通過左下角網格經度方向編碼加5、緯度方向編碼加3即可實現。

圖2 網格編碼位移計算原理示意

在網格編碼位移操作的基礎上，PDR位置計算流程如圖3所示。具體計算步驟如下：

第一步，獲得k位置的網格編碼Ck，若Ck是由掃描二維碼得到的四進制一維編碼，則進行編碼轉換得到二進制二維編碼；若Ck是位置計算得到的二進制二維編碼，則跳過轉換，直接進行下一步。

第二步，通過邊長計算函數求k位置第32級GeoSOT網格的邊長l。

第三步，根據式(6)計算步長所對應緯度方向、經度方向平移的網格個數。

(6)

式中:Nlat、Nlon分別為緯度方向和經度方向上平移的網格數，d代表步長，θ代表航向角，l代表網格邊長。

第四步，對k位置的網格編碼Ck進行編碼位移操作，求得k+1位置的網格編碼C。

第五步，若k+1位置存在二維碼，則掃碼獲取的CQR作為定位結果，同時清零PDR技術的累積誤差；若k+1位置不存在二維碼，則以計算結果C作為k+1位置的網格編碼。

將k+1位置網格編碼作為輸入可遞推得到下一位置網格編碼。另外，受定位范圍限制，通常網格邊長變化不大，位置遞推過程中可省略網格邊長計算，以最近一次掃碼后計算所得網格邊長代替即可。

圖3 位置計算流程

3.3 位置展示

位置展示是以地理網格單元覆蓋的空間區域形象化表達行人所在位置。理論上，當網格層級不高于位置獲取與位置計算所用層級時，任意滿足定位范圍與定位精度需求的層級均可設為位置展示網格層級，其中，最佳層級是邊長不大于行人步長的最大尺度網格所在層級，該層級網格對于PDR算法誤差具有較好的容錯性，兼顧了行人跨步的區分度以及行走軌跡的連續性。

行人步長約0.5～0.8 m[15]，根據文獻[19]，赤道地區第27級GeoSOT網格邊長約0.5 m，是邊長不大于行人步長的最大尺度網格。通常情況下，第27級GeoSOT網格可以保證相鄰跨步結束時，行人處于不同且鄰近的GeoSOT網格中，因此將其設為行人位置與行走軌跡展示的最佳網格。

4 實驗與分析

為驗證基于PDR和地理網格的室內外一體化定位方法的可行性與有效性，本文選用GeoSOT網格及其編碼，設計如下實驗。1)實驗平臺：智能手機vivo X3t，Android4.2.1操作系統，包含加速度傳感器、線性加速度傳感器、磁感應器、陀螺儀、攝像頭等，定位系統初始界面如圖4所示。2)實驗場地：北京華宇時尚購物中心F1層，室內結構及參考行走路線如圖5所示。參考路線分為兩段，第一段從室外開始向南行走，后轉彎，經商場大門由室外進入室內，再次轉彎后繼續向南行走至位置改正點；第二段是商場內一個矩形通道。3)實驗方法：開始前準備好GeoSOT位置二維碼，測試者勻速行走，憑經驗保持手機水平，避免過度傾斜，整個定位過程全部離線進行。測試者首先在初始位置掃描GeoSOT位置二維碼，持手機原地旋轉360°校準磁感應器讀數，然后啟動定位功能，隨測試者逐步向前行走，手機可實時計算當前位置，并在系統中更新顯示。到達改正點后，暫停傳感器數據獲取，掃描二維碼并清除累積誤差，然后重新啟動數據獲取及定位功能。

圖4 定位系統主界面

圖5 測試場地室內結構及參考行走路線

結果表明：使用和行人步長相近的第27級GeoSOT網格(測試地區網格的經向邊長約0.48 m，緯向邊長約0.37 m)展示行人位置，并將其與參考路線疊加顯示，兩者基本一致(圖6)。測試前程的理論航向約為180°→90°→180°，但陀螺儀漂移和累積誤差的存在導致第二階段航向角不斷減小，直接影響到第三階段航向。測試后程的理論航向約為90°→180°→270°→360°(0°)，第三階段的累積誤差影響到第四階段航向。這一現象在圖6中十分明顯，測試前程的第二次拐彎、測試后程的第三次拐彎角度改變量均近似90°，卻因累積誤差導致了航向偏離，由此可見掃描二維碼并清零累積誤差的必要性。

圖6 位置計算結果與參考路線對比

表1顯示了定位測試中其余指標的情況，兩組測試的定位誤差始終保持在行走距離的5%以內，其中測試后程的行走距離達到百米級別，總計步長度與參考距離的誤差約1.5 m，終點距其理論位置約3.4 m。另外，為減小身體抖動引入的誤差，測試者慢速前行，因此步頻較低，步長偏小。

表1 定位測試結果

綜上，基于PDR和GeoSOT的室內外一體化定位方法較為準確地反映了行人的位置信息，在采用PDR基礎算法計算步長和航向的情況下，行走距離誤差、終點及其理論位置誤差均小于5%，定位精度達到目前大多數系統的水平。另外，定位全程無通信開銷，不依賴于電子地圖。該實驗對PDR與其余地理網格結合的室內外一體化定位方法具有一定的參考價值，一定程度上證明了PDR與地理網格聯合定位的可行性與有效性。

5 結語

智能手機功能的日益完善，使得發展一種對外部基礎設施和電子地圖依賴性小的定位方法成為可能。本文將定位技術與地理網格結合，提出了一種基于PDR和地理網格的室內外一體化定位方法。該方法以地理網格為定位參照系統，按照PDR的算法原理，在獲得網格編碼提供的位置信息的基礎上，借助智能手機傳感器依次完成步頻檢測、步長估算和方向檢測，通過編碼的位移運算實現位置的高效求解，并以網格單元可視化表達行人所在位置。在PDR和GeoSOT結合的定位實驗中，總體定位誤差能夠控制在行走距離的5%以內，且定位精度通過增加環境中二維碼數量等方式可以進一步提高，為特殊場景下的定位問題提供了解決思路。目前研究僅局限于二維環境下地理網格與PDR技術的結合，下一步可將三維立體網格引入，如GeoSOT-3D[19]，發展適用性更強的三維室內外一體化定位算法。

[1] 歐陽斌.基于嵌入式傳感器的室內定位技術的研究[D].天津：天津大學，2013.

[2] 任慧君.半自動的室內定位與導航[D].上海：華東師范大學，2015.

[3] JUDD T.A personal dead reckoning module[A].Proceedings of ION GPS-97[C].1997.47-51.

[4] LEVI R，JUDD T.Dead reckoning navigational system using accelerometer to measure foot impacts:U.S.Patent,US5583776[P].1996-12-10.

[5] 國家測繪局.GB/T 12409-2009 地理格網[S].北京：中國標準出版社，2009.

[6] 白鳳文，許華燕.國家地理格網在數字城市建設中的應用[J].測繪通報，2012(4)：92-94.

[7] 陳會仙，張小霞，劉緒友，等.國家地理格網編碼與二維條碼的集成應用之探討[J].測繪科學，2013，38(4)：152-154.

[8] 兀偉，李朋德，張坤，等.基于位置服務的地理格網編碼設計[J].測繪通報，2013(2)：41-44.

[9] FGDC.FGDC-STD-011-2001 United States National Grid[S].Reston,Virginia,2001.

[10] 馮淳.地理格網參考系統的建立與應用[D].西安：長安大學，2006.

[11] Open Location Code:An open source standard for addresses,independent of building numbers and street names[EB/OL].https://github.com/google/open-location-code/blob/master/docs/olc_definition.adoc，2015.

[12] 程承旗，鄭承迅.一種統一現有經緯度剖分網格的方法：中國，CN102609525A[P].2012-07-25.

[13] 田國會，張慶賓，丁娜娜.基于WT-UKF的PDR/GPS組合定位算法[J].控制與決策，2015，30(1)：86-90.

[14] 陳國良，張言哲，汪云甲，等.WiFi-PDR室內組合定位的無跡卡爾曼濾波算法[J].測繪學報，2015，44(12)：1314-1321.

[15] 陳偉.基于GPS和自包含傳感器的行人室內外無縫定位算法研究[D].合肥：中國科學技術大學，2010.

[16] 張世哲.基于慣性傳感器和WiFi的室內定位系統的設計與實現[D].北京：北京郵電大學，2012.

[17] 徐偉.基于Android手機的室內定位技術研究與實現[D].武漢：華中師范大學，2014.

[18] 呂雪鋒，廖永豐，程承旗，等.基于GeoSOT區位標識的多源遙感數據組織研究[J].北京大學學報(自然科學版)，2014，50(2)：331-340.

[19] 郭輝.地球空間立體剖分格網研究[D].北京：北京大學，2012.

Integration of Indoor and Outdoor Positioning Method Based on PDR and Geographic Grid

YUAN Jing1，CHENG Cheng-qi2，TONG Xiao-chong3，CHEN Dong4

(1.InstituteofRemoteSensingandGeographicInformationSystem,PekingUniversity,Beijing100871；2.CollegeofEngineering,PekingUniversity,Beijing100871；3.InstituteofSurveyingandMapping,InformationEngineeringUniversity,Zhengzhou450001；4.StateInformationCenter,Beijing100045,China)

In order to reduce current positioning methods′ dependence on infrastructures and electronic maps,this paper proposes a novel indoor-outdoor integrated positioning method whose implementation uses QR codes and smartphone sensor data.This method is based on Pedestrian Dead Reckoning(PDR) technology and geographic grid,meaning that its design refers to PDR algorithm and its positioning reference chooses geographic grid.PDR and geographic grid have complementary advantages on position acquisition,calculation and presentation.To be specific,firstly the method obtains indoor-outdoor integrated positions in the format of geographic grid codes and eliminates accumulated errors of PDR.Secondly,based on the estimations of step counts,step sizes and step directions,positions can be figured out efficiently through simple code calculation.Finally,positions and routes of the pedestrian are showed by grid cells.According to geographic grid selection principles which consist of global subdivision,multi-level nesting and computable codes,GeoSOT is selected and used in experiments.Experiments show that positioning errors are controlled within 5% of walking distance all the time.The feasibility and effectiveness of the algorithm are demonstrated to a certain extent.Hence,this method can be used as an assisted positioning approach in some special situations where positioning devices fail to get signals or maps are hard to obtain.Additionally,the method has high practical value for the development of indoor-outdoor integrated positioning technology.

indoor-outdoor positioning；Pedestrian Dead Reckoning(PDR)；geographic grid； GeoSOT；smartphone

2016-04-06；

2016-06-15

測繪地理信息公益性行業科研專項“地名地址地理位置模型及可視化表達關鍵技術”(201512020)

原璟(1991-)，女，碩士研究生，主要研究方向為空間信息科學。*通訊作者E-mail：ccq@pku.edu.cn

10.3969/j.issn.1672-0504.2016.06.006

P208

A

1672-0504(2016)06-0032-05