基于手機的室內數字平面圖構建方法

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

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

0 概述

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

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

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

1 室內平面圖自動構建方法

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

圖1 室內平面圖自動構建過程

1.1 行人軌跡獲取

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

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

1.1.1 行走周期識別及步數統計

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

Td=R0+T

(1)

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

(2)

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

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

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

(3)

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

Xk=Xk-1+Wk

(4)

Zk=Xk+Vk

(5)

1.1.3 方向確定

(6)

1.2 軌跡中標志點檢測

1.2.1 轉向點檢測

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

1.2.2 門位置檢測

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

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

ri=(si1,si2,…,sin)

(7)

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

(8)

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

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

圖2 門位置識別

1.2.3 樓梯位置檢測

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

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

(9)

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

假設Hu為直梯上樓的經驗閾值,Hd為直梯下樓的經驗閾值,H0為上下樓的經驗閾值。若a1>Hu,則為直梯上樓;若H0≤a1

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

(10)

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

1.3 平面圖自動構建

1.3.1 軌跡分段和聚類

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

圖3 軌跡類型

圖4 軌跡點聚類結果

1.3.2 房間構建

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

圖5 基于α-shape算法的房間形狀構建

1.3.3 走廊構建

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

P=XXT/m

(11)

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

1.3.4 室內地圖繪制

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

2 實驗與結果分析

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

圖7 行走路線

圖8 行走軌跡

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

圖9 房間形狀

圖10 走廊長和寬

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

圖11 構建完成的室內平面圖

圖12 調整后的室內平面圖

3 結束語

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

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