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

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

基于空間語義的室內(nèi)導(dǎo)航應(yīng)用模型研究

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

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

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

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

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

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

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

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

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

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

1 室內(nèi)空間拓?fù)淠Ｐ蜆?gòu)建方法

圖論模型采用數(shù)學(xué)中的概念如結(jié)點、邊、權(quán)值等，對空間實體進行抽象并構(gòu)建拓?fù)潢P(guān)系。其基本思路是將室內(nèi)空間抽象為一個由結(jié)點和邊構(gòu)成的圖，其中結(jié)點表示從室內(nèi)空間中預(yù)先定義的位置；邊則表示兩個位置結(jié)點之間的直接連通關(guān)系[9-10]。本章重點介紹如何將建筑室內(nèi)空間轉(zhuǎn)化為圖論模型的幾何抽象規(guī)則和拓?fù)涿枋龇椒ā?/p>

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

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

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

1.2 房間-走廊的拓?fù)錁?gòu)建

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

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

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

表 1 空間位置結(jié)點類型和定義

表 2 邊的類型和定義

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

圖1 中心線法構(gòu)建走廊-門的拓?fù)潢P(guān)系

1.3 結(jié)點間不可通視時的拓?fù)錁?gòu)建

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

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

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

以上兩種情況增加的通視結(jié)點對應(yīng)于表 1中的InnerPoint。

圖2 兩種不可通視的拓?fù)錁?gòu)建

1.4 建筑樓層間的垂直拓?fù)錁?gòu)建

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

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

2 面向?qū)Ш綉?yīng)用的幾何和語義改進方法

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

2.1 模型屬性存儲

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

表3 結(jié)點的屬性表

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

表4 邊的屬性表

2.2 模型語義約束

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

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

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

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

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

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

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

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

其中，T（time）表示當(dāng)前導(dǎo)航時間，UP（user permission）表示請求導(dǎo)航的用戶的權(quán)限， UL（user limitation）表示用戶的受限類型，R（requirement）表示用戶特定需求。

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

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

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

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

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

3 實 驗

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

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

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

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

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

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

圖4 抽象后的圖論模型

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

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

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

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

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

圖7 普通用戶的最短導(dǎo)航路徑

圖8 輪椅用戶的最短導(dǎo)航路徑

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

4 結(jié) 語

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

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

[1] 林雕,宋國民,鄧晨．基于圖的語義室內(nèi)導(dǎo)航模型構(gòu)建研究[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ǎo)航查詢研究[D]．中國科學(xué)技術(shù)大學(xué), 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] 林雕,宋國民,賈奮勵．面向位置服務(wù)的室內(nèi)空間模型研究進展[J]．導(dǎo)航定位學(xué)報, 2014(4)：17-21

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

[11] 趙磊,金培權(quán),張藍(lán)藍(lán),等．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。

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