基于手機的室內(nèi)數(shù)字平面圖構(gòu)建方法

趙鵬飆,劉 歌,羅 磊,周 瑞

(1.電子科技大學 信息與軟件工程學院,成都 610054; 2.河南漯河職業(yè)技術(shù)學院,河南 漯河 462000)

0 概述

隨著定位導(dǎo)航技術(shù)的發(fā)展,各種基于位置的服務(wù)對地圖的需求日益增大。室外地圖構(gòu)建經(jīng)過多年發(fā)展已擁有成熟的方法,通常由專業(yè)人員通過專業(yè)設(shè)備采集數(shù)據(jù),再通過專業(yè)地理軟件處理并繪制地圖。此外,借助全球定位系統(tǒng)(Global Positioning System,GPS),也可以自動構(gòu)建室外數(shù)字地圖,如OpenStreetMap項目。但是室內(nèi)地圖的構(gòu)建一直是迄待解決的問題,也是阻礙基于位置的服務(wù)在室內(nèi)獲得廣泛應(yīng)用的主要因素之一。目前室內(nèi)地圖的構(gòu)建主要是由測繪人員測量室內(nèi)數(shù)據(jù)并繪制地圖或者基于建筑設(shè)計結(jié)構(gòu)圖繪制平面圖。這些方法盡管能夠進行部分樓宇的數(shù)字地圖構(gòu)建,但是由于高成本及私密性等原因,多數(shù)室內(nèi)環(huán)境無法采用專業(yè)方法進行地圖繪制,而建筑設(shè)計結(jié)構(gòu)圖也往往由于各種原因無法獲得,導(dǎo)致大量室內(nèi)環(huán)境無可用地圖,室內(nèi)定位無法實施。

近年來,隨著手機傳感技術(shù)的發(fā)展,加速度計、陀螺儀等傳感器已成為智能手機的標配,極大促進了基于智能手機的行人活動識別和行人航位推算(PDR)技術(shù)[1]。通過對智能手機傳感器數(shù)據(jù)的采集和處理,可以獲得行人當前活動狀態(tài)和行走軌跡。根據(jù)大量普通用戶在室內(nèi)的行走軌跡和活動,采用復(fù)雜數(shù)據(jù)分析算法,就可以獲得室內(nèi)區(qū)域的房間和走廊結(jié)構(gòu),從而自動構(gòu)建出室內(nèi)數(shù)字平面圖。文獻[2]率先提出利用智能手機構(gòu)建室內(nèi)地圖,并實現(xiàn)了環(huán)形矩形走廊的構(gòu)建。即時定位與地圖構(gòu)建(SLAM)[3]的概念由Smith等在1988年提出,主要用于機器人在未知環(huán)境下自動構(gòu)建室內(nèi)地圖。文獻[4]實現(xiàn)了SmartSLAM系統(tǒng),包括實時定位,室內(nèi)地圖創(chuàng)建和指紋地圖構(gòu)建。文獻[5]提出CrowdInside系統(tǒng),通過眾包方式采集行人行走軌跡,實現(xiàn)室內(nèi)平面圖的自動構(gòu)建。文獻[6]利用事先已知的WiFi指紋庫結(jié)合運動信息動態(tài)構(gòu)建室內(nèi)平面圖,并提出判斷走廊上房間順序和走廊鄰接關(guān)系的算法。文獻[7]利用慣性傳感器及拍攝圖像的數(shù)據(jù)信息構(gòu)建平面圖。文獻[8]提出語法增強算法來幫助室內(nèi)地圖的構(gòu)建。

為能夠在已知信息較少的情況下精確構(gòu)建包括房間和走廊的室內(nèi)平面圖,本文提出一種簡單易行的室內(nèi)數(shù)字平面圖自動構(gòu)建方法。根據(jù)手機采集的行人軌跡特征和WiFi信號,結(jié)合聚類算法識別出門位置和樓梯位置等標志點,并使用PCA算法來計算走廊的長和寬,從而構(gòu)建走廊的大小形狀,最后采用α-shape算法繪制各房間的形狀。

1 室內(nèi)平面圖自動構(gòu)建方法

本文提出的地圖構(gòu)建方法如圖1所示,首先通過PDR對手機采集的傳感器數(shù)據(jù)進行計算得到每一步的位置坐標,并將坐標點連接為行人軌跡,然后通過標志點識別算法確定轉(zhuǎn)彎、門位置和樓梯位置,根據(jù)門位置將軌跡劃分為房間軌跡和走廊軌跡,最后通過聚類和主成分分析(PCA)算法確定走廊的長和寬,通過聚類和α-shape算法對各房間進行繪制,完成整個室內(nèi)數(shù)字平面圖的自動構(gòu)建。

圖1 室內(nèi)平面圖自動構(gòu)建過程

1.1 行人軌跡獲取

室內(nèi)行人軌跡獲取采用基于手機傳感器的PDR,主要用到三軸加速度計、三軸磁力計、三軸陀螺儀和氣壓計。本文采用文獻[9]中提出的PDR算法,首先采集原始加速度數(shù)據(jù)并進行平滑,然后根據(jù)平滑后的加速度數(shù)據(jù)識別行走狀態(tài),通過有限狀態(tài)機識別行走周期并計步,步長根據(jù)其和加速度的關(guān)系進行估算,采用卡爾曼濾波根據(jù)相鄰步長之間的關(guān)系對步長進行調(diào)整,方向計算采用加速度計和磁力計。

PDR算法對行人步數(shù)、步長和行走方向進行估算,結(jié)合初始位置,就能實現(xiàn)對室內(nèi)行人的實時位置追蹤。本文將行人的位置點表示為:{t,(x,y),o,r,a},其中,t表示行人在該位置點的時間,(x,y)為當前位置坐標,o表示當前方向,r表示在該位置點采集的WiFi指紋,即AP列表及信號強度,a表示該位置點屬性,如轉(zhuǎn)彎、門位置或樓梯。

1.1.1 行走周期識別及步數(shù)統(tǒng)計

一個行走周期從靜止狀態(tài)開始,經(jīng)過波峰狀態(tài)和波谷狀態(tài)后,便完成了一個完整的行走周期,計步一次。通過設(shè)定狀態(tài)閾值,可以判斷并識別行走狀態(tài),包括靜止狀態(tài)閾值、波峰狀態(tài)閾值和波谷狀態(tài)閾值。由于存在傳感器噪聲,同時人的行走動作存在不規(guī)律性,有限狀態(tài)機中的狀態(tài)轉(zhuǎn)換可能會出現(xiàn)錯誤轉(zhuǎn)換情況。因此,算法根據(jù)加速度數(shù)據(jù)的變化動態(tài)設(shè)定狀態(tài)閾值。假設(shè)Td表示動態(tài)設(shè)定的狀態(tài)閥值,T表示固定的狀態(tài)閾值:

Td=R0+T

(1)

其中,R0為動態(tài)設(shè)定的零參考值,其值根據(jù)加速度數(shù)據(jù)的實時變化動態(tài)設(shè)置。這樣狀態(tài)閾值就隨零參考值和實時加速度數(shù)據(jù)動態(tài)變化,從而準確識別狀態(tài),減少錯誤的狀態(tài)轉(zhuǎn)換。狀態(tài)的準確識別也保證了每個行走周期的起止時間的精確確定,從而提高步長計算的精度。零參考值R0的取值為本周期內(nèi)所有狀態(tài)的狀態(tài)分界值的平均:

(2)

其中,n為本周期的狀態(tài)數(shù),bi為狀態(tài)i的狀態(tài)分界值。波峰狀態(tài)的狀態(tài)分界值為本狀態(tài)加速度峰值和前一狀態(tài)加速度谷值的平均;波谷狀態(tài)的狀態(tài)分界值為本狀態(tài)加速度谷值和前一狀態(tài)加速度峰值的平均;靜止狀態(tài)的狀態(tài)分界值為本狀態(tài)中所有加速度的均值。

1.1.2 基于卡爾曼濾波的步長計算

研究人體行走模型可以建立步長和行走中軀干的垂直位移之間的關(guān)系,進而獲得行走周期中步長和z軸加速度之間的關(guān)系,從而根據(jù)z軸加速度計算步長。假設(shè)l代表步長,h為常數(shù),N為一個周期內(nèi)加速度樣本數(shù),ai、amax和amin分別為該周期中第i個加速度樣本、加速度峰值和谷值,文獻[10]提出的步長計算公式為:

(3)

人行走中速度的變化是一個漸變的過程,導(dǎo)致人行走中相鄰2步的步長可能不同但差異不大。因此,可以在式(3)計算當前步長的基礎(chǔ)上,結(jié)合上一步步長對該計算結(jié)果進行微調(diào)。本文采用卡爾曼濾波[11]結(jié)合基礎(chǔ)算法進行步長計算。將步長作為系統(tǒng)狀態(tài)Xk,將基礎(chǔ)算法得到的步長作為量測值Zk。假設(shè)第k步步長Xk和第k-1步的步長Xk-1相等,步長的逐漸變化使用系統(tǒng)噪聲Wk來表示。由于量測值代表的也是步長,因此量測矩陣為1,量測噪聲用來表示基礎(chǔ)步長算法的計算誤差。系統(tǒng)狀態(tài)方程式和量測方程式為:

Xk=Xk-1+Wk

(4)

Zk=Xk+Vk

(5)

1.1.3 方向確定

(6)

1.2 軌跡中標志點檢測

1.2.1 轉(zhuǎn)向點檢測

行人在室內(nèi)行走過程中,如果在某個位置發(fā)生左轉(zhuǎn)或右轉(zhuǎn),則稱該位置為轉(zhuǎn)向點。在室內(nèi)環(huán)境中,行人一般會在門口、走廊拐角、室內(nèi)拐角等位置發(fā)生轉(zhuǎn)向動作,因此可以將軌跡中的轉(zhuǎn)向點作為一種室內(nèi)標志點,并在后續(xù)處理中作為軌跡分割點。每當檢測到行人步數(shù)發(fā)生變化時,也就是新軌跡點產(chǎn)生時,轉(zhuǎn)向點檢測算法進行轉(zhuǎn)向點檢測。首先判斷當前一步和前一步方向的變化值是否大于閾值Δ,如果大于Δ,則判定當前位置為轉(zhuǎn)向點,否則將當前方向變化值臨時存儲起來;如果出現(xiàn)連續(xù)n步轉(zhuǎn)向,且n步轉(zhuǎn)向累積值大于Δ,也將最后一個位置點判定為轉(zhuǎn)向點,否則判定為沒有發(fā)生轉(zhuǎn)向。

1.2.2 門位置檢測

門位置檢測不僅關(guān)系到房間類型和走廊類型軌跡的區(qū)分,同時也是室內(nèi)地圖的重要標志點。由于人在進門和出門時通常會有轉(zhuǎn)向動作,同時由于墻體影響室內(nèi)外的WiFi信號不同,因此首先根據(jù)轉(zhuǎn)向點檢測算法檢測出行人軌跡中的轉(zhuǎn)向點位置,然后再根據(jù)WiFi信號進一步判斷是否是門位置,包括2步:

1)一次識別。由于WiFi信號在穿墻后會有較大衰減,導(dǎo)致手機接收到的WiFi信號強度在房間內(nèi)部和走廊上通常會不同。假設(shè)ri表示一個WiFi信號指紋:

ri=(si1,si2,…,sin)

(7)

其中,n表示接收到信號的AP個數(shù),sik表示接收到的第k個AP的信號強度。2個WiFi指紋ri和rj之間的平均曼哈頓距離可以由下式計算得到:

(8)

如果相鄰2步的d(ri,rj)大于閾值Wd,則初步判斷當前位置為門口,否則不是。通過該方法能夠得到如圖2(a)所示結(jié)果,小圓圈為軌跡中識別出的門位置,三角形為真實門位置。從中可以看出,有一些轉(zhuǎn)向點被誤檢測為門位置,同時還存在一些門位置沒有被檢測出來,因此需要二次識別。

2)二次識別。對一次識別得到的所有門位置采用基于密度的聚類(DBSCAN)算法進行聚類。DBSCAN算法[13]可以自動識別出遠離聚類中心的噪聲數(shù)據(jù),即上面提到的誤識別的門位置。n個聚類簇對應(yīng)n個聚類中心,將每個聚類中心的半徑為R的圓范圍內(nèi)的門位置點標記為該軌跡上的門位置點,從而完成門位置點的二次識別,如圖2(b)所示。

圖2 門位置識別

1.2.3 樓梯位置檢測

室內(nèi)環(huán)境往往是多樓層,樓梯位置是重要室內(nèi)標志點。上下樓方式包括樓梯、扶梯和直梯。通過手機內(nèi)置的氣壓計可以獲得海拔高度,通過海拔高度的變化可以判斷出行人是否進行上下樓,但要區(qū)分上下樓方式,則需要加入三軸加速度數(shù)據(jù)。識別過程包括2步:

1)識別直梯上下樓。首先采用移動平均算法對海拔高度數(shù)據(jù)進行平滑,平滑后的海拔高度序列H={h1,h2,…,hn}通過下式做線性擬合[14]:

(9)

其中,p(x)=a0+a1x為擬合得到的表達式,a1為斜率。

假設(shè)Hu為直梯上樓的經(jīng)驗閾值,Hd為直梯下樓的經(jīng)驗閾值,H0為上下樓的經(jīng)驗閾值。若a1>Hu,則為直梯上樓;若H0≤a1

2)識別樓梯和扶梯。首先求出加速度量級:

(10)

其中,(ax,ay,az)為三軸加速度數(shù)據(jù)。假設(shè)Au和Ad分別為樓梯上樓和樓梯下樓的加速度量級閾值。根據(jù)上一級識別的結(jié)果,如果是扶梯或樓梯上樓,若am

1.3 平面圖自動構(gòu)建

1.3.1 軌跡分段和聚類

根據(jù)門位置,系統(tǒng)將行人軌跡劃分成房間類型和走廊類型,如圖3所示,然后使用DBSCAN算法分別對房間類型軌跡點和走廊類型軌跡點進行聚類,同時去除噪聲數(shù)據(jù)。聚類后的房間或走廊軌跡點如圖4所示,其中圓點和方點是聚類簇中的點,而星形表示噪聲點。

圖3 軌跡類型

圖4 軌跡點聚類結(jié)果

1.3.2 房間構(gòu)建

房間構(gòu)建就是解決從聚類后的二維點集構(gòu)建平面形狀的問題。通過二維點集構(gòu)建平面形狀最簡單快捷的方法是找出點集的凸包作為平面形狀,即包含點集中所有點的最小凸多邊形。但實際的房間形狀往往不會剛好就是點集的凸包,為了更加準確地構(gòu)建出房間形狀,本文采用α-shape算法來構(gòu)建房間形狀[5]。α-shape算法[15]是一種在歐幾里得平面中通過簡單線性曲線表示有限點集平面的算法。通過該算法,可以得到由聚類后的房間點集確定的一個集合平面,即房間形狀,如圖5所示。由于房間內(nèi)部通常有家具等物品,因此通過該方法實際上獲得的是房間可達區(qū)域的形狀和大小。

圖5 基于α-shape算法的房間形狀構(gòu)建

1.3.3 走廊構(gòu)建

走廊通常為矩形,具有長度和寬度,構(gòu)建走廊就是通過走廊軌跡點坐標計算走廊的長和寬。通過PCA[15]可以獲得走廊軌跡點數(shù)據(jù)集的主方向和次方向,將數(shù)據(jù)集向主方向壓縮可以得到走廊的長度,而將數(shù)據(jù)集向次方向壓縮可以得到走廊的寬度。假設(shè)走廊軌跡點數(shù)據(jù)集為X={(xi,yi)|i=1,2,…,m},m為軌跡點個數(shù)。首先計算點集X的協(xié)方差矩陣:

P=XXT/m

(11)

圖6 基于PCA算法的走廊的長和寬計算

1.3.4 室內(nèi)地圖繪制

通過走廊構(gòu)建和房間構(gòu)建,可以得到各條走廊的長寬以及各個房間的位置和形狀,然后根據(jù)軌跡點的坐標將各個房間和走廊連接起來構(gòu)成完整的室內(nèi)平面圖。通過這種方法構(gòu)建的室內(nèi)平面圖可以正確反映房間和走廊的相對位置,房間的排列順序以及走廊和房間的形狀大小。房間的形狀和大小由房間中的行人軌跡決定,反映的是可訪問的房間區(qū)域,和房間的真實大小及形狀可能不完全相同。對于走廊來說,因為走廊通常不會被障礙物占用,所以構(gòu)建出的走廊通常能夠代表真實走廊。

2 實驗與結(jié)果分析

本文選擇學校主樓4樓區(qū)域作為地圖構(gòu)建的實驗環(huán)境。多名不同實驗者分別手持三星Galaxy S3、三星Galaxy Note2以及紅米Note3手機在不同時間進行傳感器數(shù)據(jù)采集,包括加速度、角速度、磁場強度、海拔高度以及每檢測到新的一步時的WiFi指紋。實驗者的行走路線如圖7中的直線所示,起始位置是412房間斜對面的樓梯位置,行走過程中沒有對實驗員的速度和行走方式進行約束,每條行走軌跡也不需要將所有路徑走一遍,最終收集89條軌跡路徑,包括在走廊兩端的上下樓動作。采用PDR獲得的行走軌跡如圖8所示。

圖7 行走路線

圖8 行走軌跡

對收集到的軌跡數(shù)據(jù)首先通過標志點檢測算法識別出軌跡中的轉(zhuǎn)彎、門位置和樓梯位置,然后劃分出房間類型的軌跡數(shù)據(jù)和走廊類型的軌跡數(shù)據(jù)。對房間類型軌跡使用DBSCAN算法聚類后得到7個聚類簇,對應(yīng)該區(qū)域中的8個房間,其中416和418-1由于門位置較近和誤差原因被聚類為一個簇。對每個聚類簇使用α-shape算法得到每個房間的邊界軌跡點,即房間形狀,如圖9所示。對走廊類型的軌跡數(shù)據(jù)采用PCA算法進行數(shù)據(jù)降維處理獲取主方向和次方向。圖10展示了對圖7中長走廊的處理過程,對短走廊的處理過程與此類似。圖10(a)首先獲得走廊上行人軌跡數(shù)據(jù)變化的主方向和次方向,圖10(b)是將軌跡點數(shù)據(jù)集向變化主方向投影的結(jié)果,而圖10(c)是將軌跡點數(shù)據(jù)集向變化次方向投影的結(jié)果。由于數(shù)據(jù)變化的主方向和次方向分別對應(yīng)的是走廊的長和寬,所以對投影降維后的數(shù)據(jù)進行排序就可以分別找出長和寬的2個端點坐標,從而確定走廊的長和寬。

圖9 房間形狀

圖10 走廊長和寬

根據(jù)房間和走廊的構(gòu)建結(jié)果,可以得到構(gòu)建完成的室內(nèi)平面圖,如圖11所示,同時樓梯的位置也根據(jù)上下樓動作的識別標在圖中。如果事先知道該實驗環(huán)境中的房間是長方形的,那么可以對構(gòu)建出來的室內(nèi)平面圖作進一步調(diào)整。首先通過圍成每一個房間的軌跡點求得房間的中心位置坐標,本文定義與走廊平行的邊為房間的長邊,與走廊垂直的邊為房間的寬邊,通過圍成每個房間的點計算得到房間長寬,結(jié)合房間中心即可將房間形狀調(diào)整為長方形。經(jīng)過調(diào)整,使平面圖更加規(guī)整,符合實際,如圖12所示。

圖11 構(gòu)建完成的室內(nèi)平面圖

圖12 調(diào)整后的室內(nèi)平面圖

3 結(jié)束語

為方便快捷地繪制室內(nèi)地圖,本文提出一種室內(nèi)平面圖自動構(gòu)建方法。該方法首先通過智能手機采集傳感器數(shù)據(jù),通過PDR確定行人行走軌跡,然后通過標志點檢測算法識別出軌跡中的轉(zhuǎn)彎、門位置和樓梯位置,并對軌跡進行走廊類型和房間類型的劃分。房間構(gòu)建采用聚類和α-shape算法,而走廊構(gòu)建采用聚類和PCA算法,最后根據(jù)各房間和各走廊的坐標完成整個室內(nèi)平面圖的構(gòu)建。當室內(nèi)由于重新裝修或布置導(dǎo)致室內(nèi)環(huán)境發(fā)生變化時,該方法能夠迅速反映出這種變化并自動創(chuàng)建新的平面圖。

該方法依賴于較精確的PDR系統(tǒng)來獲得行人軌跡。如果航位推算精度過低,系統(tǒng)則無法構(gòu)建地圖。另外,由于采用的是行人的行走軌跡,該方法構(gòu)建出的實際上是室內(nèi)可通達區(qū)域的平面圖,對于無法通達的區(qū)域則無法構(gòu)建相關(guān)平面圖,因此,下一步將針對上述問題進行研究。