林 雕，宋國民，鄧 晨

（鄭州測繪學(xué)院，河南 鄭州450052）

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

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

1 基于圖的語義室內(nèi)導(dǎo)航模型構(gòu)建

1．1 思路

傳統(tǒng)的室外導(dǎo)航主要是基于交通網(wǎng)絡(luò)數(shù)據(jù)模型完成［11］，但對于室內(nèi)而言則沒有同室外一樣明確的道路網(wǎng)絡(luò)，當(dāng)用戶從室外進(jìn)入室內(nèi)后，行為習(xí)慣也會隨之改變［12］，室內(nèi)外空間認(rèn)知特性上的差異導(dǎo)致用戶行為習(xí)慣的不同。因此，需針對室內(nèi)空間特性構(gòu)建適合于室內(nèi)的導(dǎo)航模型?；趫D論的建模方法將現(xiàn)實(shí)世界抽象表示為節(jié)點(diǎn)和邊構(gòu)成的圖，可以用于構(gòu)建室內(nèi)道路網(wǎng)絡(luò)模型。對于基于圖的室內(nèi)導(dǎo)航模型構(gòu)建主要需考慮以下幾個問題：

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

2）幾何和語義信息表達(dá)：模型中節(jié)點(diǎn)和邊需包含相應(yīng)的坐標(biāo)信息以便支持基于長度的最短路計算和路徑可視化。語義信息是實(shí)現(xiàn)室內(nèi)導(dǎo)航的關(guān)鍵所在，需將節(jié)點(diǎn)所表示的空間類型、通道的方向性、門的開關(guān)時間、節(jié)點(diǎn)之間的權(quán)值等語義信息通過節(jié)點(diǎn)和邊的屬性信息來表示。

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

1．2 基于圖的室內(nèi)導(dǎo)航概念模型

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

Exit＿Node：各空間實(shí)體的出口節(jié)點(diǎn)。

Stair＿Exit：表示樓梯出口節(jié)點(diǎn)，每個樓梯對應(yīng)有兩個節(jié)點(diǎn)，分別對應(yīng)于兩個不同樓層的出口。

Elevator＿Exit：表示電梯出口節(jié)點(diǎn)，電梯所能到達(dá)的每一個樓層的出口均需表示為節(jié)點(diǎn)。

Escalator＿Exit：表示自動扶梯出口節(jié)點(diǎn)，每個自動扶梯對應(yīng)有兩個節(jié)點(diǎn)，分別對應(yīng)于兩個不同樓層的出口。

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

Buil ding＿Exit：表示建筑物出口節(jié)點(diǎn)，用于建立室內(nèi)外之間的聯(lián)系，以便實(shí)現(xiàn)室內(nèi)外一體的路徑規(guī)劃。

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

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

Conner＿Point：表示通道盡頭的角落節(jié)點(diǎn)。

Inner＿Node：表示房間內(nèi)部節(jié)點(diǎn)，對于凹多邊形房間而言，通常需要在凹點(diǎn)處添加節(jié)點(diǎn)以便構(gòu)成室內(nèi)通視路網(wǎng)。

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

Inner＿Segment：表示房間內(nèi)部路徑片段，由Roo m＿Exit和Inner兩類節(jié)點(diǎn)構(gòu)成，主要用于房間內(nèi)部尋路。

Joint＿Seg ment：表示房間出口和過道的連接邊，由Door＿Point和對應(yīng)的 Roo m＿Door＿Exit以及Roo m＿Window＿Exit和對應(yīng)的 Window＿Point節(jié)點(diǎn)組成。

Corridor＿Seg ment表示各通道上的路徑片段，由通道上的 Cross＿Point、Window＿Point、Door＿Point、Conner＿Point節(jié)點(diǎn)構(gòu)成。

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

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

Transfer＿Edge：表示室內(nèi)外之間的連接邊，其中有一個節(jié)點(diǎn)是Building＿Exit。

圖1 室內(nèi)導(dǎo)航概念模型

1．3 幾何圖模型構(gòu)建方法

單純的只表示空間拓?fù)潢P(guān)系的圖模型不能滿足距離量算、路徑可視化的要求，需給節(jié)點(diǎn)和邊附上相應(yīng)的坐標(biāo)信息，構(gòu)建一個三維的室內(nèi)道路網(wǎng)絡(luò)，其中主要包括出口節(jié)點(diǎn)定位點(diǎn)求取、走廊中軸線求取以及內(nèi)點(diǎn)求取。

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

圖2 門對應(yīng)定位點(diǎn)

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

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

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

圖4 凹多邊形內(nèi)部節(jié)點(diǎn)連接

1．4 基于模型的語義信息表達(dá)

語義信息是實(shí)現(xiàn)個性化室內(nèi)導(dǎo)航的關(guān)鍵，由于室內(nèi)空間的語義信息眾多，這里重點(diǎn)考慮與導(dǎo)航相關(guān)的語義信息表達(dá)，常見的有以下幾類：

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

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

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

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

1．5 圖模型數(shù)據(jù)結(jié)構(gòu)

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

表1 節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)表

表2 邊結(jié)構(gòu)數(shù)據(jù)表

2 基于模型的路徑規(guī)劃

在室內(nèi)導(dǎo)航模型基礎(chǔ)上主要通過以下兩個步驟來實(shí)現(xiàn)路徑規(guī)劃。

2．1 根據(jù)當(dāng)前應(yīng)用情景，更新路網(wǎng)中節(jié)點(diǎn)和邊的屬性信息

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

2．2 最優(yōu)路徑計算

在完成路網(wǎng)屬性值更新后，則可根據(jù)用戶的需求選定相應(yīng)節(jié)點(diǎn)作為路徑規(guī)劃的起點(diǎn)和終點(diǎn)。然而，一般情況下的室內(nèi)尋路通常是將某個特定的房間作為用戶的目標(biāo)位置，此時可分別將該目標(biāo)區(qū)域?qū)?yīng)所有可用出口節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，將距離當(dāng)前用戶位置最近的節(jié)點(diǎn)作為路徑規(guī)劃起點(diǎn)，選用成熟的路徑規(guī)劃算法（例如Dij kstra算法）計算起點(diǎn)到目標(biāo)區(qū)域不同出口之間的權(quán)值，最后選用權(quán)值最小的路徑作為最優(yōu)路徑。

3 結(jié)束語

本文基于圖論的方法構(gòu)建一種語義室內(nèi)導(dǎo)航模型。該模型綜合考慮幾何、拓?fù)洹⒄Z言三類信息的表達(dá)，且通過增加內(nèi)點(diǎn)的方式保證房間內(nèi)部的可視性，模型中節(jié)點(diǎn)和邊與室內(nèi)實(shí)體之間存在一一對應(yīng)關(guān)系，可用于支持室內(nèi)的導(dǎo)航推理，并可通過更新模型中節(jié)點(diǎn)和邊屬性值的方式建立情景和模型之間的聯(lián)系以便支持不同情景應(yīng)用下的室內(nèi)導(dǎo)航，為構(gòu)建情景感知的室內(nèi)導(dǎo)航模型提供借鑒和新的思路。此處沒有給出用戶相關(guān)因素的具體建模，實(shí)際應(yīng)用中可根據(jù)需要定義相適應(yīng)的用戶模型，利用本文所提的屬性值更新方法實(shí)現(xiàn)不同情景下的路徑導(dǎo)航。

［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］ 穆宣社，游雄．支持突發(fā)事件應(yīng)急反應(yīng)的建筑物內(nèi)部交通網(wǎng)絡(luò)分析［J］．測繪科學(xué)技術(shù)學(xué)報，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］張曉楠，任志國，曹一冰，等．交通運(yùn)輸最短路徑分析系統(tǒng)的設(shè)計與實(shí)現(xiàn)［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結(jié)構(gòu)的街道中軸線提取及網(wǎng)絡(luò)模型建立［J］．測繪學(xué)報，2000，29（4）：348－354．

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

［15］盧偉，魏峰遠(yuǎn)，張碩，等．基于Zig Bee的室內(nèi)位置服務(wù)應(yīng)用研究［J］．測繪與空間地理信息，2014，37（10）：75－77．