基于空間語義的室內(nèi)導航應用模型研究

周嘉藝，林志勇，石勇龍，李 楠

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079；2.武漢科技大學 資源與環(huán)境工程學院，湖北 武漢430081；3.湖北省測繪成果檔案館，湖北 武漢 430000）

基于空間語義的室內(nèi)導航應用模型研究

周嘉藝1，林志勇1，石勇龍2，李 楠3

（1.武漢大學 遙感信息工程學院，湖北 武漢 430079；2.武漢科技大學 資源與環(huán)境工程學院，湖北 武漢430081；3.湖北省測繪成果檔案館，湖北 武漢 430000）

室內(nèi)導航是當前空間信息應用領域的一個熱點問題，針對室內(nèi)空間和室內(nèi)導航應用需求的特點，提出了一種基于語義的室內(nèi)空間導航模型。該模型以圖論模型為理論基礎進行空間的幾何抽象和拓撲構建，在準確描述大型建筑室內(nèi)拓撲關系的基礎上，添加模型要素的屬性信息以及屬性與環(huán)境信息的語義關聯(lián)約束，使模型可以根據(jù)出行者的具體需求或環(huán)境的變化，改變模型的屬性信息，為精細化的導航服務提供基礎。

室內(nèi)導航；空間模型；圖論；語義

隨著經(jīng)濟的發(fā)展，大型公共建筑如機場、地鐵站、醫(yī)院、購物中心等內(nèi)部結構愈發(fā)復雜，迷路問題尤為突出[1-2]，使得室內(nèi)導航的需求變得愈發(fā)迫切。

導航歸根結底是尋找兩個或多個結點之間的最短（最優(yōu)）路徑，構建合適的空間模型是室內(nèi)導航的基礎。

在模型設計時，除了考慮建筑空間的結構特點，還要考慮用戶需求、環(huán)境因素對路徑規(guī)劃的影響。例如，對于有行動障礙的用戶須乘坐輪椅，那么針對他們設計的跨樓層導航路線就應避開樓梯而選擇無障礙的升降電梯，盡管這可能并不是距離最短的路線。又比如，某些通道或房間只在特定時間段或只針對特定人群開放，那么導航時也應該要考慮不同的用戶權限和時間因素。這些情況下，空間模型的拓撲關系并沒有發(fā)生變化，導航路線的差異性要通過模型要素的語義信息來體現(xiàn)。

國內(nèi)外學者提出了多種模型去描述室內(nèi)空間，如邊界模型、格網(wǎng)模型、圖論模型等。其中圖論模型由于在表達相鄰及可達性關系上具有天然的結構優(yōu)勢，而被廣泛研究[3]。

LEE等[4-7]按照圖論模型的思想，先后提出了CDM模型和IBE模型，用于描述三維室內(nèi)的拓撲關系，實現(xiàn)了幾何信息和拓撲信息的統(tǒng)一表達。但模型并未涉及環(huán)境、需求等語義信息。文獻[8]基于圖論模型的思想，提出了一種用戶可調(diào)節(jié)的室內(nèi)模型框架。該模型重點研究空間的拓撲構建和語義定義，但沒有介紹模型的幾何要素和屬性信息的構建。

本文在現(xiàn)有的研究基礎上，結合室內(nèi)導航需求的特點，以圖論模型為基礎，提出了一種改進的帶幾何信息和語義約束的空間拓撲模型。首先介紹了如何將復雜的室內(nèi)空間抽象為圖論模型，在準確描述室內(nèi)各空間位置間連通關系的基礎上，添加模型空間要素的屬性信息，以及屬性與環(huán)境信息相關聯(lián)的語義約束，使模型可以根據(jù)用戶的具體需求或環(huán)境的變化改變模型的屬性信息，從而實現(xiàn)精確靈活的室內(nèi)導航。

1 室內(nèi)空間拓撲模型構建方法

圖論模型采用數(shù)學中的概念如結點、邊、權值等，對空間實體進行抽象并構建拓撲關系。其基本思路是將室內(nèi)空間抽象為一個由結點和邊構成的圖，其中結點表示從室內(nèi)空間中預先定義的位置；邊則表示兩個位置結點之間的直接連通關系[9-10]。本章重點介紹如何將建筑室內(nèi)空間轉(zhuǎn)化為圖論模型的幾何抽象規(guī)則和拓撲描述方法。

1.1 空間要素抽象規(guī)則

圖論模型最終將整個建筑室內(nèi)空間抽象為由不同結點和邊構成的三維圖網(wǎng)，本節(jié)定義了室內(nèi)空間要素的幾何抽象規(guī)則，建立不同空間要素和不同抽象類型的一一對應關系。

結點是由具體的空間實體抽象而成，或者是為了描述連通性而增加的輔助性結點，具體的抽象類型和空間要素的定義如表 1所示。邊則是描述結點之間連通性的要素，具體抽象類型和空間要素的定義如表 2所示。

1.2 房間-走廊的拓撲構建

簡單的圖論模型是將房間和走廊抽象為結點，結點之間的連通關系抽象為邊，本文在上述方法上進行兩點改進：

1）增加門結點（對應于表 1中的Door結點）。用以區(qū)分同一房間的不同出口，尤其當出口開在房間不同方向時；

2）采用中心線法（centerline法）描述走廊。具體方法是先做走廊的中心線，如圖1b所示，圖1a中虛線表示走廊，結點表示門，再由各門結點向中心線做垂線，增加垂點結點（對應表 1中的CorridorNode），以此將各結點之間全部連通。

表 1 空間位置結點類型和定義

表 2 邊的類型和定義

由于在室內(nèi)導航應用中，走廊一般不作為興趣點或目的地，描述房間和走廊的連接關系時將走廊抽象為邊，可更方便計算不同房間結點之間的距離。

圖1 中心線法構建走廊-門的拓撲關系

1.3 結點間不可通視時的拓撲構建

室內(nèi)兩位置結點間若出現(xiàn)不可通視的情況，意味著這兩結點間被墻壁或障礙物阻隔，不能直接通行，在構建拓撲關系時需增加通視結點以保障通視。室內(nèi)空間有兩種可能的情況不通視，一種是凹多邊形的閉合區(qū)域，另一種是兩結點之間存在障礙物。

第一種情況的判定方法和步驟如圖2a所示：① 先判定該房間是否為凹多邊形。②若該多邊形為凹多邊形，再判定門之間是否通視，判定條件是連接兩個門結點，若連線有穿過該多邊形的邊，則不可通視。③ 若不可通視，則增加多邊形的凹點作為中間結點[1]。

第二種情況的判定方法和步驟如圖2b所示：①判斷空間內(nèi)是否有障礙物，判定條件是連接兩個位置結點，若連線穿過障礙物，則不可通視。②若不可通視，則由兩個門結點分別向障礙物頂點做連線，延長線交點即為中間結點。

以上兩種情況增加的通視結點對應于表 1中的InnerPoint。

圖2 兩種不可通視的拓撲構建

1.4 建筑樓層間的垂直拓撲構建

大型建筑內(nèi)通常會有多部自動扶梯，且上、下行比較復雜，給不了解建筑結構的用戶在樓層間行動帶來一定困難。因此本文在拓撲描述時將自動扶梯的不同出口、入口分別抽象為結點（對應于表 1中的Escalator結點），而結點間用帶方向的邊（表 2中的VerticalEdge）相連，以表示電梯的運行方向。

此外，大型建筑中樓梯和電梯還有特定的連接約束，如雙層的自動扶梯，或只停靠特定樓層的升降電梯，這些在拓撲構建時都要根據(jù)實際情況建立具體的連接關系。

2 面向?qū)Ш綉玫膸缀魏驼Z義改進方法

前面介紹了如何將三維建筑室內(nèi)空間抽象為由結點和邊構成的圖網(wǎng)模型。本節(jié)將重點介紹如何給模型增加必要的幾何屬性和語義約束，從而滿足不同環(huán)境和不同用戶群體的室內(nèi)導航需求。

2.1 模型屬性存儲

完整的圖論模型是一個帶權值的有向圖，其中邊的權值和方向通過模型各要素的屬性信息獲得。定義一個完整的結點所需的屬性信息包括圖層、ID號、所屬樓層號、相連的邊數(shù)量、相連的邊（用圖層_ID表示）、坐標、方向、可用性、功能，如表 3所示。

表3 結點的屬性表

定義邊所需的屬性信息包括圖層、ID、起始點、終止點、方向、可用性、權值，如表 4所示。其中，圖層Layer分別對應表 1、 2中的各結點和邊的抽象類型，可用性Active和方向Direction這兩個屬性值要根據(jù)室內(nèi)具體情況和用戶類型進行設定和調(diào)整，邊的權重值Weight取決于兩空間位置間的距離。當一條原本存在的邊（或結點）的可用性Active調(diào)整為N不可用時，需要將該邊（或與該結點直接相連的所有邊）的Weight值設為無窮大。通過上述屬性信息的補充，空間模型可完整地抽象為一個帶權值的有向圖，可以直接應用于室內(nèi)導航服務并規(guī)劃最佳路徑。

表4 邊的屬性表

2.2 模型語義約束

不同場景下（不同用戶權限、用戶受限類型、時間、需求）最優(yōu)導航路徑應該是不同的，這些差異通過模型要素的屬性信息來體現(xiàn)。本節(jié)定義了一套描述外界信息與屬性信息的關聯(lián)規(guī)則，通過將不同的室內(nèi)導航情況抽象為具體的數(shù)學公式，使模型在獲取外界信息后能自適應的調(diào)整并更新對應的屬性信息。

定義1：本文將室內(nèi)空間模型的屬性要素定義為一個七元組IndoorSpace[11]，其定義為

其中， N表示所有結點（Node）的集合；E表示所有邊（Edge）的集合；L為圖層（Layer），圖層類型參見表 1和表 2；ID為結點和邊的序號，是整數(shù)集；A表示結點的通行狀態(tài)（Active）；D和W分別代表邊的方向（Direction）和權重值（Weight）。且Layer、ID、Active、Direction、Weight 這5個參數(shù)分別對應表 3、 4中的同名屬性類，點和邊的Direction參數(shù)的取值和含義參見定義3、定義4。

定義2：對于結點集合N和邊集合E，有f：L×ID→NUE，當l1≠l2(l1,l2∈L)時，即使有i=k(i,k∈ID∈Z)，并不等于f (l1,i)=f (l2,k)。即ID號不唯一，但通過圖層L和ID號可以共同確定任意結點和邊。

定義3：對于邊集合E，有Direction(E)→ (-1,1)∈Z，該公式定義了邊的通行方向。當：

例如大型建筑內(nèi)的自動扶梯就是單向通行，而樓梯和升降梯則是雙向通行。

該定義可以用于描述諸如博物館、火車站等大型建筑內(nèi)，部分場館的出口和入口只允許單向通行的情況。

定義5：本文將導航時所獲取的外界環(huán)境要素用一個四元組IndoorCondition表示，其定義為：

其中，T（time）表示當前導航時間，UP（user permission）表示請求導航的用戶的權限， UL（user limitation）表示用戶的受限類型，R（requirement）表示用戶特定需求。

定義6：對于結點集合N，以及時間信息T、用戶權限UP和可用性A，有g：N×T→A和h：N×UP→A，其中A為Y(Yes)或N(No)。

例如：對于上班時間開關門的結點，有g(n1,′8:00am-6:00pm′)=Y；對于只針對內(nèi)部員工開放的結點，有h(n2,′staff ′)=Y。

定義7：對于邊集合E，以及用戶受限類型UL和可用性A，有j：E×UL→A，其中A為Y或N。

例如：樓梯對于使用輪椅的用戶而言，有j(e3,′wheelchair′)=N。

語義約束是模型屬性和真實環(huán)境的接口，當真實環(huán)境或用戶需求發(fā)生改變時，根據(jù)上述語義規(guī)則，模型的屬性信息會自動發(fā)生改變，最終使得路徑規(guī)劃策略也作出相應調(diào)整，以此來滿足不同情境下的導航需求，實現(xiàn)精細化和最優(yōu)化的室內(nèi)導航。

3 實 驗

本節(jié)將通過實驗來驗證本文所提出的圖論模型的可行性，以及當室內(nèi)環(huán)境發(fā)生改變后模型的有效性。實驗主要分為4個步驟：

1）將原始數(shù)據(jù)抽象為圖論模型。2）為室內(nèi)空間要素建立屬性表。

3）選擇出發(fā)點和目的地，采用最短路徑算法（Dijkstra等）規(guī)劃出最短路徑。

4）改變某要素的屬性值，重新規(guī)劃最短路徑。

本實驗采用的原始數(shù)據(jù)為天津市港口醫(yī)院一至二樓的CAD平面圖，如圖3所示。采用文章所述方法進行幾何抽象和拓撲構建后得到的圖論模型如圖4所示。

圖3 天津市港口醫(yī)院一樓和二樓的平面圖

圖4 抽象后的圖論模型

按照§2．3所述給各要素建立屬性表，按照真實數(shù)據(jù)添加屬性值?，F(xiàn)假設起始點為一樓的電梯口，目的地是同在一樓的房間A，采用Dijkstra算法進行計算，得到的路線如圖5所示。

圖5 從電梯口到房間A的最短路徑

為驗證當室內(nèi)空間連接關系發(fā)生改變時模型依舊有效，現(xiàn)假設房間A的西門在下午6點以后將不可使用。修改此門結點的屬性值，將該點的Active值從Y改為N，此時，與該門結點相連的邊的權值Weight變?yōu)闊o限大。重新計算更新后的最短路徑如圖6所示。

再假設現(xiàn)在要規(guī)劃從一樓的某個起始點去二樓房間B的最短路徑，對于普通用戶而言，最短路徑是經(jīng)過中央大廳的手扶電梯到達二樓的房間B。若用戶換成了輪椅用戶，那么去其他樓層就只能搭乘升降電梯，通過修改用戶受限類型，模型會自動將樓梯和手扶電梯的Active值設為N，當前情況下可行的最短路徑也將發(fā)生改變。兩種用戶受限類型的三維導航路徑對比如圖7、 8所示。

圖6 改變屬性值后的最短路徑

圖7 普通用戶的最短導航路徑

圖8 輪椅用戶的最短導航路徑

通過兩組對比實驗，證明了本文提出的模型可以有效的進行路徑規(guī)劃；同時當外部環(huán)境或用戶需求改變時，模型可以根據(jù)預先設定的語義約束，自適應的做出調(diào)整，從而保證不同情況下導航的準確性和適用性。

4 結 語

本文提出了一種改進的面向室內(nèi)導航應用的空間模型，模型定義了空間要素的抽象規(guī)則，最終得到一個包含完整拓撲關系的圖論模型；在此基礎上增加模型的坐標、方向、權值等屬性信息，使其能應用于室內(nèi)導航算法；最后增加環(huán)境、需求及模型屬性相關聯(lián)的語義約束，使模型可以根據(jù)真實環(huán)境和用戶需求的改變自適應的進行調(diào)節(jié)。

最后通過實驗證明了該模型能夠方便的描述大型建筑的空間拓撲關系，并基于現(xiàn)有路徑規(guī)劃算法進行準確的室內(nèi)導航。同時，當室內(nèi)空間因環(huán)境或用戶需求發(fā)生改變時，模型也能自適應的做出調(diào)整，滿足精確靈活的導航需求。

[1] 林雕,宋國民,鄧晨．基于圖的語義室內(nèi)導航模型構建研究[J]．測繪工程,2015(1)：48-52

[2] SCHOUGAARD K R, Gr O Nb Ae K K, Scharling T． Indoor Pedestrian Navigation Based on Hybrid route Planning and Location Modeling[M]．Pervasive Computing． Springer,2012：289-306

[3] 李千元． 面向室內(nèi)空間的語義約束導航查詢研究[D]．中國科學技術大學, 2014

[4] LEE J． A Three-Dimensional Data Model for Representing Topological Relationships between Spatial Entities in Built-Environments[D]． The Ohio State University, 2001

[5] LWW J, KWAN M． A Combinatorial Data Model for Representing Topological Relations Among 3D Geographical Features in Micro-Spatial Environments[J]．International Journal of Geographical Information Science, 2005,19(10)：1 039-1 056

[6] LEE J． A Three-Dimensional Navigable Data Model to Support Emergency Response in Microspatial Built-Environments[J]． Annals of the Association of American Geographers, 2007,97(3)：18

[7] 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

[8] MARCUS G, ALEXANDER Z． Formal Definition of a User-Adaptive and Length-Optimal Routing Graph for Complex Indoor Environments[J]．Geo-Spatial Information Science, 2011(2)：119-128

[9] 林雕,宋國民,賈奮勵．面向位置服務的室內(nèi)空間模型研究進展[J]．導航定位學報, 2014(4)：17-21

[10] 張寅寶,張威巍,孫衛(wèi)新．面向位置服務的室內(nèi)空間數(shù)據(jù)模型研究[J]．測繪與空間地理信息, 2014(11)：11-13

[11] 趙磊,金培權,張藍藍,等．LayeredModel：一個面向室內(nèi)空間的移動對象數(shù)據(jù)模型[J]．計算機研究與發(fā)展,2011(S3)：274-281

P208

B文章編號：1672-4623（2017）06-0010-04

10.3969/j.issn.1672-4623.2017.06.003

周嘉藝，碩士研究生，研究方向為室內(nèi)GIS、三維GIS。

2016-03-09。

項目來源：國家自然科學基金資助項目（41271449、41171350）。