基于眾包的室內地圖自動構建算法*

吳偉，施學成，姚英彪2,

（1.蘇州中科安源信息技術有限公司，江蘇 蘇州 215024；2.杭州電子科技大學 探測預警與信息對抗研究院，浙江 杭州 310018；3.杭州電子科技大學 通信工程學院，浙江 杭州 310018）

0 引言

近年來，室內制圖領域百花齊放[1-3]，有的延續沿用傳統的室外地圖制作方法來制作室內地圖，即通過專業人員利用專業設備線下實地收集地圖繪制數據；有的利用互聯網用戶激勵方式去鼓勵用戶主動上傳地圖相關數據；還有的通過獲取建筑設計結構圖紙來重新繪制室內地圖。雖然上述這些方法都可以解決室內地圖繪制問題，但各自優缺點也十分明顯。比如通過專業人員和設備繪制得到的地圖質量無疑是最好的，但是存在人力成本較高的缺陷。此外，人員和設備有限，覆蓋面不廣，以及室內環境的易變性的問題給室內地圖的更新帶來很大麻煩。為了解決此類問題，基于眾包方式來構建室內地圖成為研究熱點。

文獻[4]提出了CrowdInside 系統，該系統首先基于眾包方式收集行人室內行走時的傳感器數據；其次利用行人行走過程中的活動點將軌跡進行分割，并通過片段長度、片段密度及片段中每步平均行走時間來區分房間區域和走廊區域內的軌跡；再次利用基于密度的聚類算法聚類房間區域的軌跡和走廊區域的軌跡；最后用α-shape 方法構建房間和走廊地圖。文獻[5]利用眾包采集到的Wi-Fi 指紋和識別出的用戶運動信息提取各房間區域形狀、房間鄰接關系等室內平面圖信息，并最終構建室內平面圖。上述研究雖然都構建了室內地圖，但其地圖自動算法構建程度低，且所構建的地圖與實際地圖貼合度較低。

針對上述問題，本文提出一種基于眾包的室內地圖自動構建方案。方案的核心包括兩點：（1）多條軌跡的自動合并與拓展；（2）基于軌跡點云數據的自動地圖構建?，F場實驗結果表明，相比于基于主成分分析（Principal Component Analysi，PCA）的地圖構建方法，本文提出的地圖自動構建方法在地圖交并比和位置誤差這兩個指標上都更好。

1 點云數據獲取模型

1.1 數據預處理

點云數據是指行人室內行走時的位置坐標集合，可通過行人航跡推算（Pedestrian Dead Reckoning，PDR）算法計算得到。由于行人室內行走時收集的傳感器數據包含著大量噪聲，因此需對傳感器數據進行去噪處理[6]。

文獻[7]通過實驗分析發現，相比于其他濾波器，巴特沃斯低通濾波器在保留原始數據的相關特征的基礎上，能很好地消除傳感器數據中的噪聲。因此，本文利用截止頻率為0.2π 的3 階低通濾波器來消除原始數據中的噪聲。

1.2 PDR 計算點云位置

PDR 是近年來在室內制圖領域被廣泛采用的算法，也是面向智能手機的算法中使用最多的[8-13]。如圖1 所示，PDR 利用行人室內行走過程中收集的加速度計、陀螺儀及磁力計數據來估計行人的步長、航向等信息，進而推算行人的位置坐標。

圖1 PDR 航跡推算

PDR 包括步態檢測、步長估計和方向角計算3個部分。步態檢測是指基于人一步內加速度表現為一個連續正負高峰的特點，判斷行人是否在行走。本文采用峰值檢測法[14]檢測步態。步長估計用于估計行人一步間的距離，本文利用式（1）估計第k步的步長lk。

式中：α，β，γ為參數；ak,max和ak,min分別為第k步合加速度的峰值和谷值；fk為行走頻率；vk為加速度方差。fk和vk滿足：

式中：和分別為第k步的起始時刻和終止時刻；ak,i為第k步內的第i個加速度值；為第k步的加速度均值；Nk為第k步內加速度采樣點的個數。

在方向角計算方面，由于陀螺儀不會受到磁場干擾且具有短距離精度高的特點[15]，因此本文利用陀螺儀來得到一步內方向角的變化量，其計算方式為：

式中：θk為由陀螺儀積分得到的第k步的方向角的變化量；M為第k步的陀螺儀采樣點的個數；ρi和Δt分別為陀螺儀Z軸采樣點的值和采樣間隔。

在得到每步步長、方向角后，則可得到行人位置的表達式為：

最終所有步坐標的集合即為PDR軌跡點云數據。

2 PDR 軌跡點云數據處理模型

2.1 軌跡簡化

軌跡簡化指的是將PDR 得到的行人軌跡表示為只包括關鍵點（起點、轉彎點、開門點、終點）的有序集合。本文規定所有軌跡的起點相同，將軌跡最后一步定義為終點，開門點通過特定動作識別。轉彎點需滿足兩個條件：（1）轉彎點所在步的航向角變化量的絕對值為局部最大值，且大于閾值Thrθlow；（2）以轉彎點所在步為中心、窗口長度為len的窗口內，方向角變化量總和的絕對值大于閾值Thrθhigh，即：

則認為第k步為轉彎點所在步，由此，一條軌跡可簡化為：

Trani為第i條簡化軌跡，in為當前軌跡第n個關鍵點，滿足：

式中：Type(·)代表關鍵點種類，起始點、轉彎點、開門點、終點賦值分別為0，1，2，3。

本文利用信息矩陣Mesi記錄編號為i的簡化軌跡的關鍵點編號、種類、方向角、位置等信息，如圖2 所示。

圖2 軌跡簡化

圖2 中，i1為軌跡起始點，i5為軌跡終點，其余為軌跡轉彎點，矩陣Mesi為對應的軌跡信息矩陣。在簡化所有軌跡后，得到了所有簡化軌跡對應的軌跡信息矩陣集合Mes。

2.2 軌跡合并

在得到所有簡化軌跡后，下一步是合并所有簡化軌跡。本文用方陣Mop來記錄所有軌跡中關鍵點之間的連通關系，方陣維度等于識別出的不同關鍵點數量。具體來說，當第j個和第k個關鍵點連通時（即存在直線軌跡），Mj,kop賦值為1，否則為0。軌跡合并的具體步驟如下：

（1）利用第1 條軌跡Tran1的信息初始化方陣Mop。

（2）從集合Mes中取出一個軌跡信息矩陣Mesot，將Mop與Mesot進行合并。具體來說，先檢測關鍵點的相似性，若相似則更新Mop對應關鍵點信息（方向角、空間位置及相似點集合LS）；若不相似，則拓展Mop方陣來記錄Mesot中的不相似的關鍵點（即更新軌跡連通信息）。

軌跡合并的偽代碼如下：

代碼第1 行確定循環次數為Mesot包含的關鍵點數目，代碼第3 行初始化Mop當前處理點集合Pop1，代碼第4 行遍歷Mesot中關鍵點。代碼第6行SD(·)用于判斷Pop1中是否存在和Pot相似的點，SD(Pot,Pop1)會依次遍歷Pop1中的關鍵點，若Pop1中存在關鍵點滿足以下條件，則返回為True:

式中：Pot為對應Mesot中的關鍵點；Type(·)，Angle(·)，PosX(·)，PosY(·)分別用于獲取關鍵點在Mes中的種類、方向角以及X和Y的坐標信息。

關鍵點相似需滿足關鍵點的種類相同、方向角差值的絕對值小于或大于（相同轉彎點轉向不同的情況）、空間距離小于的條件。本文設定為20，為150，為2.5。

代碼第7 行RP(·)函數用于更新軌跡信息矩陣Mesop中對應相似點的值和更新相似點集合LS，相似點集合指的是每一關鍵點及與其相似的點的并集，用于后續點云數據的提取。圖3、圖4 為軌跡合并和更新后的Mop及相似點序列示意圖。

圖3中A1與B1判斷為相似，A2與B2判斷為相似，因此更新A1與A2的相似點集合和，如圖4所示。

圖3 軌跡合并

圖4 更新后的M op 及相似點序列

代碼第9 行FN(·)用于更新Pop1，獲取下一個連通區域。代碼第11 行EM(·)通過拓展Mop記錄連通信息，EM(·)偽代碼如下：

圖4 為更新后的Mop及相似點序列。SD(·)函數判斷A3與B3不相似，因此進行矩陣拓展，首先拓展行（對應代碼第3 行），其次拓展列（對應代碼第5 和12 行），最后記錄連通信息（對應代碼第6 和10 行）。由此通過拓展Mop維度記錄了Mesot中的連通信息。合并所有簡化軌跡后得到記錄了室內所有關鍵點連通信息的方陣Mopa，下一步將進行地圖構建。

3 地圖構建模型

3.1 點云數據提取

構建室內地圖首先需要提取所有PDR 軌跡中位于相同區域的點云數據，本文提出一種基于廣度優先思想的點云數據提取方法，具體步驟為：

（1）根據Mopa得到與Cur相連的關鍵點集合為ConsCur；

（2）從ConsCur中取出一個點ConCur(ConCur∈ConsCur)；

（3）根據點Cur和ConCur的相似點集合獲取在Cur與ConCur間的PDR 軌跡編號；

（4）從對應編號的PDR 軌跡中取出位于這兩個點之間的每一步的坐標；

（5）重復步驟（1）到步驟（4），直到遍歷完ConsCur。

圖5 為點云數據提取示意圖。

圖5 點云數據提取

假設A1-A2-A3-A4，A1-A2-B3-B4，A1-A2-C3-C4和A1-A2-D3為Mopa記錄的室內連通信息，以提取A1-A2段子地圖為例，假設A1，A2的相似點集合分別為：

由可知，有4 條軌跡（A，B，C，D）經過A1。由可知，有編號為A，B，C的3 條軌跡經過A2，則編號為A，B，C的3 條軌跡包含了A1-A2段子地圖所需的點云數據。在得到經過該子地圖內的行人軌跡編號后，利用關鍵點的步數信息即可提取對應軌跡中的點云數據。

上述A1段子地圖獲取到的點云數據可表示為：

3.2 地圖構建

本文地圖構建是利用柵格將每一段子地圖進行覆蓋，然后統計有效柵格，最后對得到的有效柵格進行規則化處理，從而完成子地圖的構建。

同一子地圖內的點云數據表示為：

式中：m為該段子地圖內點云數目。

本文采用邊長為l的正方形作為基本柵格將子地圖覆蓋（柵格區域用Sq表示），假設第i行第j列的柵格中心點坐標為：

則柵格4 個頂點（Q，R，S，T）的坐標為：

若存在Pv滿足：

則認為Pv點云落入當前柵格中。若當前柵格落入的點云數目超過閾值Thrnum，則認為該柵格是有效的，由此可以得到所有有效柵格區域，如圖6 所示。

圖6 柵格規則化

由圖6 可以看出，有效柵格區域存在“空洞”情況，為了使構建的地圖貼近實際地圖，本文對其規則化處理。首先定義Averow為Sq有效行的平均有效柵格數（有效行指的是有效柵格數不為0的行），Avecol為Sq有效列的平均有效柵格數，則有：

式中：Count(Sq)為Sq中有效柵格的數目；NumR，NumC分別為Sq中有效行數和有效列數。本文將有效柵格數目超過Averow的有效行的最小、最大行下標區間視為有效行范圍，將有效柵格數目超過Avecol的有效列的最小、最大列下標區間視為有效列范圍，并將位于有效范圍內的柵格視為有效柵格，由此完成了有效柵格規則化處理。

最終基于廣度優先思想分別構建子地圖，并重復上述步驟，得到完整的室內地圖。

4 實驗結果與分析

本文將從地圖構造、地圖精度等方面評估基于本文所提算法構建的地圖與基于α-shape[16]、基于主成分分析法[17]構建的室內地圖的優劣，并評估所提算法的性能。

4.1 實驗設置

本次實驗選取了4 位志愿者，分別讓其水平持Oneplus 8、榮耀20S、小米5 及Google Nexus 5 手機采集數據，這4 部手機均內置加速度計、磁力計、陀螺儀等慣性傳感器，采樣頻率為50 Hz。實驗場地如圖7 所示。

圖7 實驗場地

實驗場地主要由一條走廊及兩種大小不一的共計6 個房間組成，走廊由若干個規格為0.6 m×0.6 m的地磚塊鋪設而成，長約52 m，寬約3 m；大房間（房間1 和房間2）長約13.2 m，寬約8.4 m；小房間（房間3～6）長約9 m，寬約6.6 m。志愿者水平持智能手機沿著室內區域不構成封閉軌跡正常行走，并以50 Hz 的采樣頻率采集三軸加速度、陀螺儀及磁力計數據。所有軌跡起點保持一致，志愿者點擊“開始采集”按鈕則開始采集數據，在到達盡頭時點擊“結束采集”按鈕結束采集。本文共采集了80 條志愿者室內行走的軌跡數據，將得到的數據文本文件利用MATLAB 處理并進行實驗仿真。

4.2 地圖構造分析

基于PDR 算法計算得到的80 條行人室內軌跡點云數據如圖8 所示。

圖8 采集的80 條軌跡點云數據

圖9 為利用邊長為0.6 m 的正方形柵格覆蓋房間1 所得到的有效區域圖，其中，圓圈為各柵格中心點，柵格區域為構建出的房間有效區域，判定閾值Thrnum設置為2。構建的房間1 地圖的有效區域長寬為22×13 個柵格長度。

圖9 柵格邊長為0.6 m 時構建的房間1 區域圖

圖10 為基于α-shape 方法構建的房間1 區域示意圖，由圖10 和圖11 可以看出，柵格法相較于α-shape 方法，其所構建的室內地圖更貼近于實際地圖，且能消除部分異常軌跡點的干擾，但基于柵格法構建的室內地圖精度會受柵格邊長l影響。

圖10 基于α-shape 法構建的房間1 區域圖

圖11 為利用邊長為0.8 m 的正方形柵格覆蓋房間1 所得到的有效區域圖。

圖11 柵格邊長為0.8 m 時構建的房間1 區域圖

用邊長為0.8 m 的柵格構建的房間1 有效區域長寬為19×10 個柵格長度。為探究在本文實驗環境下的最佳柵格邊長l，本文固定有效柵格判定閾值Thrnum為2，調整柵格邊長長度l，并將所得到的房間長寬結果匯總于表1。

表1 柵格邊長結果

本文主要考慮了柵格邊長在1 m 范圍內的情況。由表1 可知，柵格邊長為0.6 m 時構建的房間長寬與實際長寬更相符，因此后續地圖構建時皆用邊長為0.6 m 的柵格l 來構建，最終構建的平面圖見圖12。

圖12 基于柵格法構建的室內地圖

圖12 中，柵格覆蓋區域為所構建的房間地圖，無柵格覆蓋的區域為所構建的走廊地圖?；跂鸥穹嫿ǖ氖覂鹊貓D精度依賴有效柵格的分布，在軌跡較少的情形下，表現為有效柵格分布較稀疏，會導致構建出的地圖精度較低（房間6）。為進一步分析本文所提算法所構建的室內地圖的優越性，本文基于文獻[17]利用PCA 構建室內地圖，并將其作為對比算法來評估所構建地圖的精確性。

圖13 為一段PCA 壓縮室內走廊區域點云數據得到的區域長寬示意圖，兩段實線分別為PCA 投影得到的區域長寬，圖14 為利用PCA 構建的室內地圖。

圖13 基于PCA 構建的子地圖

圖14 基于PCA 構建的室內地圖

由圖14 可看出，基于PCA 構建的室內地圖存在兩個缺陷：（1）投影長度依賴數據點的空間位置，數據點若分布較離散，即聚攏性較低，則投影長寬誤差會變大，表現為在房間地圖構建時，兩相鄰房間區域已出現重合現象（房間3、4，房間5、6）；（2）基于PCA 構建的地圖的區域中心位置難以確認，若依賴點云數據中心位置去確認區域位置，會受點云數據分布密度影響，即點云中心位置并不代表實際區域中心位置。基于柵格法構建的室內地圖則通過有效柵格閾值Thrnum和規則化有效柵格的方式篩除了部分異常點云數據，進而解決了相鄰房間重疊問題。

4.3 地圖精度分析

本文將從兩個指標評測所提出的地圖構建算法的優劣性，一是利用交并比（Intersection Over Union，IOU）去衡量本文所提出的室內地圖構建方案與實際地圖的吻合度，二是基于房間位置誤差及走廊位置誤差去評估關鍵點位置精度。IOU 定義為：

式中：Areap和Areat分別代表所構建的地圖區域和實際真實區域；IOU為兩者的交并比。IOU在理想狀態下為1，但由于實際傳感器精度和地圖構建算法影響，IOU值往往達不到理想值。表2 給出了本文所提算法構建的房間及走廊的位置誤差及交并比等性能指標。

表2 本文所提算法構建的地圖精度

表2 中房間和走廊的位置誤差分別為房間頂點位置、走廊頂點位置與實際位置的歐氏距離均值。表2 中房間1 和2 的軌跡數量最多且位置誤差相對較小，因而交并比較大。房間4、房間5 及房間6一方面由于行走距離較遠而導致位置誤差較大，另一方面則因為軌跡數量相對較少且并未完全覆蓋房間區域，導致交并比下降。本文提出的算法構建的地圖的平均位置誤差在1.94 m 左右，平均交并比在0.63 左右。

表3 為基于PCA 構建的室內各區域的精度表。由PCA 構建的地圖的位置誤差在2.87 m 左右，交并比在0.49 左右?？梢钥闯觯疚乃崴惴o論在區域交并比，還是在位置誤差上均優于基于PCA的地圖構建算法，且位置誤差降低了32.4%，交并比提高了28.6%，由此可知基于本文方法構建的地圖精度較高。

表3 基于PCA 構建的地圖精度

5 結語

針對地圖構建及維護過程中存在的成本較高的問題，提出了一種只需PDR 軌跡點云數據便能自動構建室內地圖的方案。實驗結果表明，相比基于PCA 的地圖構建方法，本文提出的地圖自動構建方法在地圖交并比上提高了28.6%，在位置誤差上降低了32.4%。