丁磊 蔡德成

摘 要：導航路網是實現(xiàn)室內定位與導航服務的關鍵?，F(xiàn)有室內路網生成方法成本較高，且依賴于室內建筑CAD圖紙或室內二維平面圖等先驗知識，數(shù)據獲取過程繁瑣。提出一種服務于室內導航與定位的基礎路網模型，利用Project Tango設備采集路網模型所需原始數(shù)據，經過細粒度劃分得到室內空間適應性導航路網。實驗證明，該方法可在面向未知環(huán)境時，可更快速、高效地獲取較高精度的室內導航路網，且成本更低。

關鍵詞：Project Tango;室內導航;路網模型;運動追蹤

DOI：10. 11907/rjdk. 182392

中圖分類號：TP301

文獻標識碼：A文章編號：1672-7800（2019）006-0046-06

Abstract： In the application of indoor space positioning and navigation services， the navigation network is the key to realize indoor positioning and navigation services. At present，the method of generating indoor network is costly and relies on prior knowledge（such as indoor architectural CAD drawings or indoor two-dimensional plan），and the data acquisition process is cumbersome. This paper proposes a basic network model for indoor navigation and positioning，and uses Project Tango equipment to collect the original data needed for the network model，and obtains an adaptive navigation network for indoor space after f*87ine-grained division. The experiment proves that the method can realize the indoor navigation network with higher precision and faster and more efficient，and the cost is lower.

Key Words： Project Tango; indoor navigation; network model; motion tracking

0 引言

隨著城鎮(zhèn)化進程的加快，辦公樓、大型購物場所、地鐵站等大型建筑物日益增多。有研究表明，人們絕大部分時間都處在室內空間[1]。另一方面，隨著移動互聯(lián)網、新一代地理信息系統(tǒng)（GIS）、基于位置的服務（LBS）及普適計算、物聯(lián)網等技術的興起與快速發(fā)展，公眾對基于位置的室內移動信息服務需求與日俱增，如室內定位導航、商場移動導購、室內移動社交等[2]。因此室內定位、導航與位置服務技術備受關注。

與開放的室外空間相比，由于室內環(huán)境在空間布局、拓撲、環(huán)境限制、空間約束等方面更加復雜，使現(xiàn)有基于GNSS的室外導航位置服務技術無法完全適用于室內環(huán)境。室內空間路徑網絡拓撲結構與室外道路網存在較大差異，如室內房間、走廊、大廳等實體之間通過門、樓道等方式連通在一起，并且具有三維特性，使傳統(tǒng)歐式距離[3]和道路網路徑距離[4]計算方法無法用于計算精細的室內空間路徑距離。因此，為提供精準的室內導航服務，路徑距離計算大多依賴于底層拓撲網絡，與室外道路網不同的是，室內拓撲網絡常因為人為因素影響，如大型家具的移動等，導致拓撲網絡發(fā)生改變，在導航過程中，如果沒有及時更新已改變的拓撲網絡，會嚴重影響導航準確性。

對于室內導航服務而言，路徑導航問題依賴于精度較高的導航路網。Li等[5]提出一種基于圖的網格模型表達二維室內空間，該模型在不同層次結合室內空間結構和拓撲屬性，且隱式地集成度量屬性，但是模型以室內空間二維平面圖作為建模輸入，依賴于已有的室內空間二維平面圖。Schafer等[6]為在更大范圍內提供地圖生成解決方案，開發(fā)了地圖生成工具包，可解析標準CAD圖，自動生成室內空間拓撲網絡圖。Xuan等[7]提出一種從室內行人軌跡眾包數(shù)據中估算室內拓撲網絡圖的算法。Johnston等[8]提出利用激光掃描儀估算室內地圖的方法。

現(xiàn)有室內拓撲網絡圖獲取方法均依賴于先驗知識（如建筑物CAD圖、室內平面圖），或需要借助激光掃描儀獲取數(shù)據，其成本高、數(shù)據處理復雜，同時室內空間導航路網容易受到人為因素影響發(fā)生改變，需及時、快速地更新糾正該區(qū)域導航路網。因此本文提出一種基于Project Tango手機的室內導航路網生成方法，闡述其方法流程并進行實驗與分析，證明該方法可面向未知室內環(huán)境更快速高效地獲取較高精度的室內導航路網。

1 Project Tango技術

2014年，谷歌成立Project Tango項目并推出一系列搭載攝像頭、各種運動傳感器和處理芯片的手機、平板等移動設備（見圖1），用于繪制逼真的三維場景，為AR、VR等應用奠定了基礎，并為開發(fā)者提供面向C、JAVA、UNITY三大語言的API以實現(xiàn)應用開發(fā)[9]。

Project Tango平臺三大核心技術是運動追蹤、深度感知和區(qū)域學習，在各種傳感器、攝像頭、IMU等硬件基礎上，利用機器視覺技術和圖像處理算法等，整合3個維度的數(shù)據，描述Project Tango設備自身運動姿態(tài)、趨勢和周圍環(huán)境信息（例如周圍環(huán)境三維點云數(shù)據）。設備參數(shù)見表1。

運動追蹤是基于單目攝像頭技術，在IMU、加速度計和陀螺儀的基礎上添加廣角攝像頭視覺特征識別[10]，計算特征點在幀與幀之間的相對位置變化，識別相機移動距離及運動姿態(tài)。但此時并沒有獲得深度數(shù)據，且單目攝像頭技術無法辨別大面積無特征點的環(huán)境，如全黑或全白區(qū)域。

深度感知可檢測物體或障礙物表面及形狀，目前常見的解決方案主要包括結構光和TOF，根據激光從發(fā)射到返回的時間長短計算物體或障礙物距離攝像頭的真實距離，將所有點的距離信息生成三維點云圖，在Project Tango Core的優(yōu)化下，結合運動追蹤中獲得的特征點即可動態(tài)獲得室內空間單元模型[11]。

區(qū)域學習是將運動追蹤獲得的特征點數(shù)據與深度感知獲得的深度數(shù)據融合匹配成場景信息，當檢測到新場景時，會與已有或預設場景進行匹配，并且同步修正運動追蹤的數(shù)據，即區(qū)域學習是運動追蹤和深度感知的結合，通過數(shù)據庫不斷擴充和匹配，實現(xiàn)場景學習的目的，模擬人類感知世界[11]。

本文提出的方法充分利用Project Tango深度感知和運動追蹤技術，經實驗證明該方法采集獲取室內導航路網的過程簡單、快速且獲得的室內導航路網精度較高。

2 室內導航路網模型

在室內空間導航中，導航路徑非常重要，然而室內導航路徑不同于室外導航路徑，因受房間、門、墻等室內實體要素限制，在空間布局、拓撲網絡、空間約束等方面具有特殊性，傳統(tǒng)歐式距離和道路網路徑距離在室內空間導航中存在較大缺陷，因此需構建室內導航網絡以規(guī)劃導航路徑及計算路徑距離。室內導航路網屬于2.5維結構，本部分從空間幾何、拓撲等方面描述室內環(huán)境[12]。

2.1 室內基礎導航路網

拓撲關系是導航網絡主要表達內容，如包含、鄰接、連通、覆蓋等。在室內空間中，各實體要素之間的拓撲關系主要是鄰接及連通關系。本文首先通過結合圖模型[13]、節(jié)點關系模型[14-15]和地標導航數(shù)據模型[16]構建室內基礎導航網絡，表達室內空間基本輪廓。

節(jié)點關系模型是由Lee等[14-15]提出的一種可簡化表達室內空間實體要素間復雜拓撲關系的數(shù)據模型，如建筑物中房間之間的連接或連通關系。地標導航數(shù)據模型是由湯欣怡[16]提出的一種利用地標輔助室內導航的路網模型，該模型在導航路網決策點處選擇一個顯著性最強的空間實體要素作為該決策點的地標。在節(jié)點關系模型和地標導航數(shù)據模型的基礎上，本文提出一種表達室內空間關鍵節(jié)點間連接關系的數(shù)據模型——室內基礎導航路網。

室內基礎導航路網根據室內空間單元基本結構生成，表達室內空間單元基本形狀、單元間連通拓撲關系、連通距離及角度，該結構是實現(xiàn)室內導航與路徑規(guī)劃的基礎。

室內基礎路網節(jié)點包括空間內節(jié)點、轉彎點和終止點。其中，空間內節(jié)點定義為室內開闊區(qū)域（如大廳，房間等）的邊界節(jié)點，處理走廊時建立中軸[17]對空間結構進行抽象，中軸上產生的中間節(jié)點即為轉彎節(jié)點，中軸端點即為終止節(jié)點。

如圖2所示，空間內節(jié)點為空間結構中空間實體（大廳、房間等）的邊界節(jié)點，障礙物空間實體沒有邊界節(jié)點。

對于常規(guī)建筑來說，走廊形狀一般是狹長的。當處理走廊時，建立該區(qū)域中軸對其連通路徑進行表達，并在相應位置插入轉彎節(jié)點，如圖3所示。該空間為長方形ABCD，由于AC邊連接3個空間實體，BD邊也連接3個空間實體，即會出現(xiàn)邊AB被分解為4段、BD邊被分為3段的情況，在這種情況下，網絡模型使用中軸抽象走廊ABCD，產生5個轉彎節(jié)點。另外，終止節(jié)點用于封閉中軸線，終止節(jié)點的位置根據中軸生成的算法確定。

在垂直通道的處理上，傾斜空間使用中軸[17]及兩個終止節(jié)點表示，轉換空間由于連接了兩個傾斜空間，也處理為中軸表示，并插入轉彎節(jié)點，連接到相鄰傾斜空間上的終止節(jié)點，如圖4所示。

2.2 室內適應性導航路網

與室內基礎路網相比，室內適應性路網對開闊空間進行了進一步細化，如圖5所示。在室內基礎路網的基礎上，適應性路網首先根據語義信息確定室內開闊的自由空間，如大廳、房間等（狹長區(qū)域為寬度小于閾值的走廊、樓梯等），對開闊空間對應的面進行格網剖分，將格網中心點作為新的節(jié)點，根據四方向或八方向鄰接關系建立格網中心點的邊，并通過與連接空間內節(jié)點之間的連通邊，將開闊的空間形成的格網-圖模型連接到室內基礎路網中 ，形成在狹長區(qū)域使用中軸表達、在開闊區(qū)域使用格網—圖表達的適應性室內路網。格網—圖模型是對空間細粒度離散化表達，以格網單元中心點作為節(jié)點，以格網八方向連通關系作為邊，連接相鄰節(jié)點構成的網絡模型。格網—圖模型的粒度根據格網單元的邊長確定，格網單元越小，中心點越密集，格網—圖模型的分辨率越高。格網—圖模型可進行精度更高的路徑規(guī)劃。

2.3 室內導航路網數(shù)據模型

本文提出室內基礎導航路網數(shù)據模型IBNNDM（Indoor Basic Navigation Network Data Model）的形式化定義為：

IBNNDM=（Node，Edge，LandMark，Room，Storey，Building）。

其中，Node是節(jié)點集合，代表基礎路網中的節(jié)點;Edge是邊集合，代表兩節(jié)點間的連接關系;LandMark是地標集合，代表節(jié)點附近的地標;Room是室內房間集合，代表室內所有房間（包括大廳）;Storey是樓層集合，代表節(jié)點所在樓層;Building是建筑物集合，代表節(jié)點及邊所在建筑物。

建筑對象（Building）是人們日?；顒拥氖覂瓤臻g，每棟建筑均包含多個樓層（Storey），每個樓層包含多個房間（Room），每個房間又包含若干個節(jié)點（Node）和路網的邊（Edge）。一個路網節(jié)點可能分布著多個候選地標，路網的邊代表該兩節(jié)點間具有連通關系。該數(shù)據模型的關鍵在于如何組織Project Tango設備采集到原始室內空間數(shù)據，最后生成室內導航路網。

IBNNDM模型中每個對象類的實現(xiàn)及屬性見表2-表7。構建室內導航路網僅需獲得表2-表7中的數(shù)據即可。

3 室內導航路網模型構建

3.1 坐標系轉換

Tango設備采用參照定位的方法，即相對于初始位置的一種定位方式，不涉及到衛(wèi)星定位。它根據硬件設備傳感器，比如重力傳感器、IMU陀螺儀等，獲取移動設備相對于初始位置的位移和旋轉角度，從而構建一個局部參照坐標系——起始點為坐標原點，將Z軸設置為與重力對齊，Z +指向上方，并且XY平面平行于與重力垂直的方向，且X軸指向設備屏幕右邊，Y軸垂直于X軸、Z軸構建的平面指向X正方向逆時針旋轉90°的反向，如圖6所示。由于不能保證每次采集開始時設備構建的局部參照坐標系X、Y軸方向和大地坐標系統(tǒng)一致，所以需將局部參照坐標系轉換到大地坐標系（僅統(tǒng)一坐標軸方向，不統(tǒng)一坐標原點）。

3.2 原始數(shù)據采集

調用 Project Tango API，通過重寫onPoseAvailable 的方法，可以獲取相機當前姿態(tài)與初始位置的相對位置關系，返回一個三元組表示位置信息。遇到上文定義的3類節(jié)點時便記錄下該位置坐標值、節(jié)點類型及所屬對偶空間編號，并與上一個采集節(jié)點連接，構成連接邊，同時檢測該節(jié)點是否與已記錄節(jié)點重合。如果重合，則將該節(jié)點與之前采集的節(jié)點進行連接，繼續(xù)進行直到采集工作結束。

原始數(shù)據采集流程如圖7所示。

3.3 適應性導航路網生成

通過以上流程采集的只是室內基礎導航路網，對其開闊區(qū)域進一步細化得到室內適應性導航路網。根據室內基礎路網標記的節(jié)點類型，對全部節(jié)點是空間內節(jié)點且在同一個對偶空間里構成封閉多邊形對應的面進行格網劃分，然后將其連接到基礎路網上，形成格網—圖表達的室內適應性導航路網。

格網劃分步驟包括：首先獲取每個開闊區(qū)域的外包絡矩形（見圖8（a）），然后根據導航與定位精度的需要對開闊區(qū)域進行不同尺寸的規(guī)則格網劃分，本文以1m為劃分尺寸標準。對外包絡矩形進行格網劃分后得到格網圖（見圖8（b）），再計算出格網中心點作為新節(jié)點，根據四方向鄰接關系建立格網中心點的邊（見圖8（c）），然后在開闊區(qū)域剔除對應多邊形之外的節(jié)點，將起始和結束節(jié)點均保留在該多邊形內連接邊上，其余連接邊剔除（見圖8（d）），最后將其連接到基礎路網上。

4 實驗與分析

為驗證模型與方法的可行性，選取中國地質大學（武漢）地理信息系統(tǒng)研究中心（見圖9）作為實驗場地，其單層面積為3 300m2。該場景中總共有4個實驗室、1個學術報告廳、1個研究室，這5個場所經常有相關辦公人員和學生出入，每個房間均有多個門可以通過。環(huán)境復雜多樣，可滿足測試要求。

4.1 路網生成效率分析

本文主要從兩個方面分析所提方法的效率，一是該方法消耗的物資成本，二是該方法生成室內路網消耗的時間成本。由于不需要任何先驗知識（如室內平面圖），減少了室內平面圖生成需消耗的人力和物力，且使用的設備是一個價值僅3 000元左右的Tango智能移動設備，相比于激光掃描儀，本文方法設備成本低。同時本文設計了一個時間成本對比實驗，將利用ArcGIS從室內平面圖獲取導航路網（記為實驗A）與本文提出的方法（記為實驗B）進行結果對比。實驗地點依然選擇中國地質大學（武漢）地理信息系統(tǒng)研究中心，實驗結果如表8所示。

4.2 路網精度分析

為避免實驗偶然性，一共進行4次原始數(shù)據采集，隨機選取3個節(jié)點計算測量值與真實值真誤差和方差。為保證實驗有效性，此處作3點約束：①實驗場地光照良好，無光線昏暗之處;②每次實驗人員手持Tango設備采集數(shù)據時盡量做到每次速度勻速且大致相等;③實驗場地無大片全白或者全黑區(qū)域。

經過實驗得到結果如表9、表10所示。

由以上兩表可知隨機選取的3個節(jié)點測量值方差均很小，所以可以判斷測量數(shù)據較為精確。

5 結語

本文針對室內空間導航與定位服務對室內適應性路網的需求，提出一種基于Project Tango手機的室內導航路網生成方法。與現(xiàn)有路網生成方法相比，該方法可面向未知的復雜室內環(huán)境，形成快速、低成本、高精度的室內適應性導航路網。目前智能設備室內導航系統(tǒng)缺乏大量已繪制好的路網，無法有效導航、定位，本文方法可彌補該項不足，且與文獻[8]的方法相比，本文使用的Project Tango設備成本更低。實驗結果表明，該方法能生成滿足室內導航與定位要求的路網。

但目前該方法還存在一些不足之處：首先作為一個半自動方法，時耗不小;另外一個樓層的采集工作必須一次性完成，若中途停止，會導致兩次采集工作坐標系原點不同，需后期人工進行數(shù)據合并。后續(xù)將進行路網實際應用，將本文方法應用于實際導航與定位應用，并進行方法完善，以期實現(xiàn)室內導航路網完全自動化生成。

參考文獻：

[1] WORBOVS M. Modeling indoor space[C]. Proceedings of the 3rd ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness， 2011： 1-6.

[2] 劉兆宏，王科，豐江帆，等. 矢量室內地圖建模與制作方法[J]. 數(shù)字通信， 2012（4）：77-80.

[3] HJALTASON G R，SAMET H. Distance browsing in spatial databases[J]. ACM Transactions on Database Systems （TODS）， 1999， 24（2）： 265-318.

[4] ZHANG J，PAPADIAS D，MOURATIDIS K， et al. Query processing in spatial network databases[C]. the 29th International Conference On Very Large Data Bases ，2003：802-813.

[5] LI X，CLARAMUNT C，RAY C. A grid graph-based model for the analysis of 2D indoor spaces[J]. Computers， Environment and Urban Systems， 2010， 34： 532-540.

[6] SCHAFER M，KNAPP C，SAMARJIT C. Automatic generation of topological indoor maps for real-time map-based localization and tracking[C]. 2011 International Conference on Indoor Positioning and Indoor Navigation， 2011： 1-8.

[7] XUAN Y G，SENGUPTA R，F(xiàn)ALLAH Y. Crowd souring indoor maps with mobile sensors[M]. Berlin： Springer Berlin Heidelberg， 2012.

[8] JOHNSTON M，ZAKHOR A. Estimating building floor-plans from exterior using laser scanners[C]. SPIE，2008：68050.

[9] 千尋. Project Tango：3D影像觸手可及[J]. 計算機應用文摘， 2014（11）：72.

[10] HESCH J A，KOTTAS D G，BOWMAN S L，et al. Camera-IMU- based localization：observability analysis and consistency improvement[J]. ?The International Journal of Robotics Research， 2014， 33（1）： 182-201.

[11] 洪程. 基于Project Tango的SLAM技術研究[D]. ?武漢：武漢大學， 2017.

[12] 徐戰(zhàn)亞，鐘賽尚，王媛湲. 一種易于更新的室內導航路網構建方法[J]. 計算機仿真， 2015（12）： 267-271，275.

[13] BECKER C，DüRR F. On location models for ubiquitous computing[J]. ?Personal and Ubiquitous Computing， 2005， 9（1）： 20-31.

[14] LEE J. 3D GIS for geo-coding human activity in micro-scale urban environments[M]. Berlin： Springer Berlin Heidelberg， 2004.

[15] LEE J， ZLATANOVA S. A 3D data model and topological analyses for emergency response in urban areas[J]. Geospatial Information Technology for Emergency Response，2008，143： C168.

[16] 湯欣怡. 面向室內行人的地標導航方法研究——以大型室內商場為例[D]. 武漢：中國地質大學（武漢）， 2017.

[17] TANEJA S，AKINCI B，GARRETT J H，et al. Algorithms for automated generation of navigation models from building information models to support indoor map-matching[J]. Automation in Construction， 2016， 61： 24-41.

（責任編輯：江 艷）