基于圖的語義室內導航模型構建研究

林 雕，宋國民，鄧 晨

（鄭州測繪學院，河南 鄭州450052）

隨著城市化進程不斷加快，大型建筑物內部構造變得愈加復雜，加重人們的空間認知負擔，使得室內尋路變得更加困難，特別是在商場等大型公共場所，室內“迷路”的情況尤為突出［1］，室內導航也因此得到更多的關注。室內空間模型則是實現室內導航的基礎和關鍵所在。目前已提出多種面向室內導航的空間模型，早期常見的符號模型將室內空間對象表示為帶有特定ID標識的符號元素［2］，用于表達室內空間元素的相互關系。這類模型符合人的空間認知特性，但缺少對室內的幾何描述，且只能給出粗略的路徑描述。為實現對室內幾何和拓撲的統一描述，Lee等利用對偶圖的方法將室內空間抽象表示為節點和邊［3］，并通過中軸變換的方式將二維的通道轉換為一維的線，構建3維室內拓撲數據模型。這種幾何圖的建模方式得到廣泛的認可，主要用于構建室內道路網絡［4－5］。Yuan等則認為“門－門”的建模方式更加符合用戶的行為習慣［6］，提出將門抽象表示為節點，門之間的連接表示為邊，該模型可以支持非繞行的最優室內尋路并通過增加可視點的方式保證節點之間的通視性。文獻［7－8］等也均采用這種室內空間抽象方式。另外，文獻［9－10］等則重點考慮用戶相關因素（如移動能力、尋路的喜好等）對建模的影響，側重于室內本體建模，并依據本體之間的推理關系來實現個性化的路徑導航。這類模型通常缺少對圖模型具體構建方式的描述，且沒有將可視性納入考慮。

在當前已有室內空間模型中，多數模型在建模過程中只考慮部分導航相關的影響因素，適用范圍有限。針對該問題，本文基于圖論的建模方法，綜合考慮用戶室內移動特征、幾何和語義信息表達以及路徑規劃效率等多個導航相關的影響因素，提出一種支持多情景應用并符合用戶空間認知特性的室內導航空間模型。

1 基于圖的語義室內導航模型構建

1．1 思路

傳統的室外導航主要是基于交通網絡數據模型完成［11］，但對于室內而言則沒有同室外一樣明確的道路網絡，當用戶從室外進入室內后，行為習慣也會隨之改變［12］，室內外空間認知特性上的差異導致用戶行為習慣的不同。因此，需針對室內空間特性構建適合于室內的導航模型。基于圖論的建模方法將現實世界抽象表示為節點和邊構成的圖，可以用于構建室內道路網絡模型。對于基于圖的室內導航模型構建主要需考慮以下幾個問題：

1）用戶室內移動特征：不同于室外路網，室內空間沒有明確的路徑信息，用戶在室內移動具有更大的隨意性，但同時又具有一定的規律性［7］。一般情況下兩個房間之間的移動借助于室內過道且沿著過道中間行走，此時可用中軸線表示過道。房間內部的移動則按照門到門的方式，可將門抽象表示為節點。同時，可視性在室內尋路過程中有很重要的作用，可通過增加可視節點的方式保證通視。例如，對呈L狀的房間而言，在構建路網時可將兩個門之間的凹點表示為可視點。

2）幾何和語義信息表達：模型中節點和邊需包含相應的坐標信息以便支持基于長度的最短路計算和路徑可視化。語義信息是實現室內導航的關鍵所在，需將節點所表示的空間類型、通道的方向性、門的開關時間、節點之間的權值等語義信息通過節點和邊的屬性信息來表示。

3）路徑規劃效率：室內空間相對狹小，用戶移動更加自由，對路徑規劃的實時性提出了更高要求，特別是在計算能力有限的移動平臺環境下，因此要求室內導航模型應盡可能的簡單，以便實現高效的路徑規劃。對于基于圖的空間模型而言，主要通過減少圖元數的方式來提高路徑規劃效率。對于有多個出口的過道而言，相對于中軸線法，若采用“門－門”建模方式會大幅增加模型中的圖元數，使得路徑規劃的查詢效率有所下降[8]。

1．2 基于圖的室內導航概念模型

室內空間中包含有諸多構件，導航模型中則需要重點描述和路徑相關的空間對象。綜合考慮用戶室內移動特征、幾何和語義信息表達、路徑規劃效率等要求，利用圖的建模方法提出室內導航概念模型（見圖1），該模型中各元素與室內構件之間存在一一對應關系，可用于支持室內的導航推理。下面給出圖1中各元素的具體解釋：

Exit＿Node：各空間實體的出口節點。

Stair＿Exit：表示樓梯出口節點，每個樓梯對應有兩個節點，分別對應于兩個不同樓層的出口。

Elevator＿Exit：表示電梯出口節點，電梯所能到達的每一個樓層的出口均需表示為節點。

Escalator＿Exit：表示自動扶梯出口節點，每個自動扶梯對應有兩個節點，分別對應于兩個不同樓層的出口。

Room＿Exit：表示房間出口節點，包括Room＿Door＿Exit和 Roo m＿Window＿Exit兩類，其中Roo m＿Door＿Exit表示房間對應的門節點，Room＿Window＿Exit表示房間對應的靠近室外的窗戶節點，在緊急救災等特殊情況下作為室內的通行路徑，正常情況下將其設置為不可通行點。

Buil ding＿Exit：表示建筑物出口節點，用于建立室內外之間的聯系，以便實現室內外一體的路徑規劃。

Corridor＿Node：表示通道上的所有節點。Cross＿Point：表示兩個通道的交叉節點。Window＿Point：表示 Roo m＿Window＿Exit在通道上的垂直投影點。

Door＿Point：表示 Roo m＿Door＿Exit在通道上的垂直投影點，以此建立通道和房間之間的連接。

Conner＿Point：表示通道盡頭的角落節點。

Inner＿Node：表示房間內部節點，對于凹多邊形房間而言，通常需要在凹點處添加節點以便構成室內通視路網。

Horizonal＿Edge：表示水平方向上的連接邊，主要用于同一樓層兩個位置之間的路徑規劃。

Inner＿Segment：表示房間內部路徑片段，由Roo m＿Exit和Inner兩類節點構成，主要用于房間內部尋路。

Joint＿Seg ment：表示房間出口和過道的連接邊，由Door＿Point和對應的 Roo m＿Door＿Exit以及Roo m＿Window＿Exit和對應的 Window＿Point節點組成。

Corridor＿Seg ment表示各通道上的路徑片段，由通道上的 Cross＿Point、Window＿Point、Door＿Point、Conner＿Point節點構成。

Connect＿Seg ment：表示水平方向和垂直方向的連接邊，通常由Corridor節點和Stair＿Exit、Elevator＿Exit、Escalator＿Exit三類節點組成。

Vertical＿Edge表示垂直方向的連接邊，主要用于樓層之間的路徑規劃，包括有樓梯、電梯、扶梯，分別由 Stair＿Exit、Elevator＿Exit、Escalator＿Exit三類節點組成。

Transfer＿Edge：表示室內外之間的連接邊，其中有一個節點是Building＿Exit。

圖1 室內導航概念模型

1．3 幾何圖模型構建方法

單純的只表示空間拓撲關系的圖模型不能滿足距離量算、路徑可視化的要求，需給節點和邊附上相應的坐標信息，構建一個三維的室內道路網絡，其中主要包括出口節點定位點求取、走廊中軸線求取以及內點求取。

出口節點定位點求取：在幾何平面圖上，通常將門等出口表示為一維的線，此時選取該線中點作為節點定位點。如圖2所示，取門線的中點作為門的定位點，同樣的方法可用于處理電梯、樓梯、自動扶梯、建筑物出口等。

圖2 門對應定位點

通道中軸線求取：通過中軸變換的方式可將通道從二維的面轉換為一維的線，針對通道的一般外形特征，選用基于Delaunay三角剖分的中線法作為室內通道提取算法。主要原理如下：1）提取通道多邊形輪廓特征點；2）對多邊形邊界弧段上的矢量點做加密處理，使得有更多間距接近的點參與構網；3）以多邊形邊界為約束條件構建約束Delaunay三角網；4）按照三角形所擁有的鄰近三角形數量，將三角形分為三種類型：I類三角形的中軸線定義為其重心與非邊界邊中點的連線；II類三角形的中軸線定義為其兩條非邊界邊各自中點的連線；III類三角形的中軸線定義為其重心分別與三條非邊界邊中點的連線，最終得到對應的通道中軸線（如圖3所示），基于Delaunay三角剖分的中線法的細節可參閱文獻［13－15］。

圖3 通道中軸線提取示意圖

內點求取：凹多邊形房間內部兩個門之間可能存在不可視的情況，通過增加節點作為路徑的中間點確保房間內部的可視性，主要步驟包括：①判定多邊形的凹凸性質，如存在內角大于180°的多邊形則為凹多邊形，否則為凸多邊形；②如果是凹多邊形，判斷兩個門之間是否可視，判定方法為連接兩個門線中點，若連線在多邊形內則表示可視，否則不可視；③若兩個門之間不可視則增加凹點作為其中間點，凹點的選取原則為保證兩個門之間的路線最短。例如，圖4中門d2和門d3之間存在不可視的情況，此時可添加凹點v作為路徑中間節點以確保房間內部節點的可視性。

圖4 凹多邊形內部節點連接

1．4 基于模型的語義信息表達

語義信息是實現個性化室內導航的關鍵，由于室內空間的語義信息眾多，這里重點考慮與導航相關的語義信息表達，常見的有以下幾類：

1）門的私有或公有屬性，例如某些房間只有特定的用戶可以進入，一般不能將其作為普通用戶的通行路徑。

2）門、電梯等出口開關時間，通常情況下室內中某些場所有其固定的開關時間，例如超過某個時間點，電梯將不可以使用。

3）通道的方向性，與室外類似室內空間中也有部分單向通道，例如上下樓的扶梯只限定于某一個特定的方向。

一般通過給節點和邊附加屬性信息的方式來實現語義信息表達，由于各節點和邊所描述的對象有所不同，對應的語義信息也有所差異，借鑒文獻［8］所提的N×ID→SI（其中N表示節點編號、ID表示語義信息類型，SI表示具體的語義信息）語義信息表達方式，通過節點的唯一編號指定各節點所表達的語義信息，同樣可將該方法擴展應用于邊的語義信息描述。例如，對于一個Room＿Door＿Exit類型的節點n3，可附加一個可進入時間的屬性（n3，accessibility）＝“08：00－20：00”，用來表示該門的開關時間在08：00－20：00之間。另外，針對室內單向道路較少的特點，為減少建模工作量，避免構建有向圖模型，同樣將其作為屬性信息描述，如對于邊e3而言，（e3，direction）＝1，表示該邊的方向是從首節點到尾節點，－1表示反向，0則表示該邊是雙向通行的。實際應用中可根據需求，給節點和邊增加更多的語義信息，如電梯的等待時間、承載人數等。

1．5 圖模型數據結構

圖模型中主要包括節點和邊兩類，根據室內導航應用需求，主要考慮幾何、拓撲、語義三類相關信息，采用如表1、表2的基本數據結構。其中，節點表中存儲的基本信息包括節點編號、類型、是否可用、所在樓層、相連邊數、連接邊編號以及對應的幾何坐標；邊表中存儲的基本信息包括邊編號、類型、首尾節點編號、是否可用、權值、方向以及對應的幾何坐標。另外，節點類型（Node＿Type 和邊類型（Arc＿Type）分別和圖1中各元素類型相對應。Active屬性表示對應的節點或邊是否可用，若節點不可用則將該點設置為路徑規劃的繞行點，邊不可用則將其對應的權值設置為無窮大。需要指出一點，可根據實際應用需求，利用章節1．4中所提語義信息描述方式來對表1和表2中的基本數據結構作相應擴展。

表1 節點數據結構表

表2 邊結構數據表

2 基于模型的路徑規劃

在室內導航模型基礎上主要通過以下兩個步驟來實現路徑規劃。

2．1 根據當前應用情景，更新路網中節點和邊的屬性信息

主要通過更新節點Active、邊Active和Weight 3個屬性項的值來建立情景與導航之間的聯系。首先判斷當前時間下哪些節點和邊為不可用，假設當前時間為21：00，且有（n3，accessibility）＝08：00－20：00，則可以推斷出n3所表示的門是不可進的，此時應將n3對應的Active屬性值設置為“N”，然后將其對應的屬性為Joint＿Seg ment的邊權值設置為無窮大表示該門與過道之間不可通行；其次根據用戶身份信息來排除不適合的路徑節點和邊，例如，對于一個坐輪椅的用戶而言，則不能將樓梯或者是自動扶梯作為其上下樓的通行路徑，此時應將類型為Stair和Escalator的邊Active屬性值設置為“N”，表示該路徑不可通行，其他的一些用戶相關的語義信息還包括用戶年齡、移動能力、感知能力、用戶特權等，分別對應于不同的路徑選擇規則；最后判斷用戶的喜好對路徑的影響，如當用戶推著嬰兒車上樓時則更加偏向于帶電梯的路徑，即使有可能導致繞路。實際應用中還存在其他的一些情況需單獨考慮，如在發生火災情況下，應將電梯排除在所選路徑之外，同時可將窗戶作為特殊的通行路徑，另外還需給模型附加上更多的語義信息（如走廊的最大人流量、區域的煙霧濃度等），并建立相應的數學模型來實現對邊權值的更新，以便規劃出一條合理的撤退路線。

2．2 最優路徑計算

在完成路網屬性值更新后，則可根據用戶的需求選定相應節點作為路徑規劃的起點和終點。然而，一般情況下的室內尋路通常是將某個特定的房間作為用戶的目標位置，此時可分別將該目標區域對應所有可用出口節點作為目標節點，將距離當前用戶位置最近的節點作為路徑規劃起點，選用成熟的路徑規劃算法（例如Dij kstra算法）計算起點到目標區域不同出口之間的權值，最后選用權值最小的路徑作為最優路徑。

3 結束語

本文基于圖論的方法構建一種語義室內導航模型。該模型綜合考慮幾何、拓撲、語言三類信息的表達，且通過增加內點的方式保證房間內部的可視性，模型中節點和邊與室內實體之間存在一一對應關系，可用于支持室內的導航推理，并可通過更新模型中節點和邊屬性值的方式建立情景和模型之間的聯系以便支持不同情景應用下的室內導航，為構建情景感知的室內導航模型提供借鑒和新的思路。此處沒有給出用戶相關因素的具體建模，實際應用中可根據需要定義相適應的用戶模型，利用本文所提的屬性值更新方法實現不同情景下的路徑導航。

［1］ SCHOUGAARD，KARI R，KAJ G，et al．Indoor pedestrian navigation based on hybrid route planning and location modeling［J］．Pervasive Co mputing，2012：289－306．

［2］ BRUMITT B，STEVEN SHAFER．Topological world modeling using semantic spaces［C］／／Proceedings of t he Wor kshop on Location Modeling for Ubiquitous Computing，Ubi Comp．Vol．2001：55－61．

［3］ LEE JIYEONG．A Spatial Access－Oriented Implementation of a 3－D GIS Topological Data Model for Urban Entities［J］．Geoinf or matica，2004，8（3）：237－264．

［4］ THILL J C，DAO T H D，ZHOU Y．Traveling in the t hree－di mensional city：applications in route planning，accessibility assess ment，location analysis and beyond［J］．Journal of Transport Geography，2011，19（3）：405－421．

［5］ 穆宣社，游雄．支持突發事件應急反應的建筑物內部交通網絡分析［J］．測繪科學技術學報，2007，23（6）：408－410．

［6］ YUAN WENJIE，MARKUS S．Inav：An indoor navigation model supporting length－dependent opti mal routing［J］．Geospatial Thinking，2010：299－313．

［7］ LIU L，ZLATANOVA S．A door－to－door path finding approach for indoor navigation［C］／／Proceedings of GeoInf or mation For Disaster Management Conference．2011：3－8．

［8］ GOETZ M，ZIPF A．For mal definition of a user－adaptive and length－opti mal routing graph f or complex indoor environ ments［J］．Geo－Spatial Infor mation Science，2011，14（2）：119－128．

［9］ ANAGNOSTOPOULOS C，TSETSOS V，KIKIRAS P．Onto Nav：A semantic indoor navigation system［C］／／1ST Workshop on Semantics in Mobile Environments（SME05），AYIA．2005．

［10］DUDAS P M，GHAFOURIAN M，KARI MI H A．ONALIN：Ontology and algorith m for indoor routing［C］／／Mobile Data Management：Systems，Services and Middleware，2009．MDM＇09．Tenth International Conference on．IEEE，2009：720－725．

［11］張曉楠，任志國，曹一冰，等．交通運輸最短路徑分析系統的設計與實現［J］．測繪工程，2014，23（1）：25－30．

［12］GILLIéRON P Y，MERMINOD B．Personal navigation system for indoor applications［C］／／11th IAIN World Congress．2003：21－24．

［13］艾廷華，郭仁忠．基于約束Delaunay結構的街道中軸線提取及網絡模型建立［J］．測繪學報，2000，29（4）：348－354．

［14］李萌，李偉，錢凌韜．基于文本挖掘的個性化地圖服務模型研究［J］．測繪與空間地理信息，2014，37（5）：39－41．

［15］盧偉，魏峰遠，張碩，等．基于Zig Bee的室內位置服務應用研究［J］．測繪與空間地理信息，2014，37（10）：75－77．