有限狀態(tài)自動機輔助的行人導航狀態(tài)匹配算法

方志祥，羅 浩，李 靈

1.武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079； 2.四川省第二測繪地理信息工程院，四川 成都 610100

?

有限狀態(tài)自動機輔助的行人導航狀態(tài)匹配算法

方志祥1，羅 浩2，李 靈1

1.武漢大學測繪遙感信息工程國家重點實驗室，湖北 武漢 430079； 2.四川省第二測繪地理信息工程院，四川 成都 610100

行人導航狀態(tài)的自動識別是行人導航研究的一個難點問題，對提升行人導航軟件服務(wù)的精準反饋與改善導航性能至關(guān)重要，此方面已有的研究工作很少。本文提出了一種基于有限狀態(tài)自動機的行人導航狀態(tài)匹配算法，其核心思想是在識別行人動作基礎(chǔ)上匹配行人當前導航狀態(tài)。利用谷歌眼鏡及智能手機采集的多種傳感器數(shù)據(jù)對行人動作進行識別，得到其動作特征參數(shù)；然后將行人導航狀態(tài)分為熟悉、陌生及迷路3類，根據(jù)有限狀態(tài)自動機理論建立狀態(tài)轉(zhuǎn)移模型，設(shè)計基于該模型的行人導航狀態(tài)匹配算法；最后，實現(xiàn)狀態(tài)匹配算法，通過試驗對該算法的有效性進行驗證。試驗結(jié)果表明，該算法能夠較好地識別行人導航過程中的狀態(tài)轉(zhuǎn)移，其中對熟悉向陌生狀態(tài)轉(zhuǎn)移識別準確度較高，對迷路狀態(tài)識別準確度達到90%。

行人導航；有限狀態(tài)自動機；動作識別；狀態(tài)匹配

行人導航服務(wù)成為基于位置的服務(wù)的研究熱點，智能移動設(shè)備的普及使得行人導航服務(wù)越來越便捷，由電子地圖、定位、路徑規(guī)劃和路徑引導等組成的行人導航系統(tǒng)廣泛應用在幫助行人沿規(guī)劃路徑到達目的地[1-2],行人導航通過導航地圖提供空間信息，完成路徑規(guī)劃等[3-5]。但是由于具體導航任務(wù)復雜度高，或現(xiàn)有路徑引導方式的不足等，行人還是會出現(xiàn)迷路狀況，導致無法按照既定規(guī)劃路線到達目的地。行人導航是對地理環(huán)境的認知與行人決策相結(jié)合的過程，個體對環(huán)境認知狀態(tài)的變化會引起不同的動作反應，行人的動作與狀態(tài)是相互關(guān)聯(lián)的，研究行人導航的實時狀態(tài)，及時發(fā)現(xiàn)和識別行人可能出現(xiàn)的迷路狀態(tài)，對于提高行人導航服務(wù)的成功率和舒適度具有重要意義。

人體的動作可以直接反映個體的狀態(tài)?，F(xiàn)有對人體動作識別的研究中，人體運動信息的獲取方式主要有兩種，基于視覺的和基于微慣性傳感器的?；谝曈X的人體運動監(jiān)測研究起步較早，在視頻監(jiān)控、虛擬現(xiàn)實等領(lǐng)域應用廣泛，涉及運動目標檢測、動作特征提取和動作特征理解[6-9]等主要技術(shù)。但是基于視覺的行為動作監(jiān)測對外部環(huán)境光線、背景等依賴較大，空間復雜性和時間差異性對此類研究的影響很大。隨著微機電系統(tǒng)(micro-electro-mechanical system，MEMS)的發(fā)展，加速度傳感器、陀螺儀等慣性傳感器充分體現(xiàn)在體積、靈敏度方面的優(yōu)勢，并且因其價格低廉，開始廣泛被集成到各類便攜智能設(shè)備中，如常見的智能手機以及各種新興的智能可穿戴設(shè)備，如手表、眼鏡等。利用這類智能穿戴設(shè)備采集人體運動數(shù)據(jù)具有諸多優(yōu)勢，如不受環(huán)境的約束和限制，能夠?qū)崟r準確地記錄人體的復雜運動信息。國內(nèi)外許多科研機構(gòu)開展了利用微傳感器對人體動作的監(jiān)測和識別研究。文獻[10]采用加速度信號和生命體征信號對跑步、上樓等5個動作應用多種分類方法進行了分類結(jié)果比較。文獻[11]利用人體傳感器網(wǎng)絡(luò)構(gòu)建了人體動作監(jiān)測平臺對日常人體的7種動作進行了分類和識別研究。文獻[12—14]利用智能設(shè)備等的慣性傳感器對行人步行動作等進行了識別方面的研究。谷歌眼鏡是谷歌公司推出的一款智能穿戴設(shè)備，其采用Android操作系統(tǒng)，搭載8種傳感器，佩戴在頭部，負擔小，可以作為人體動作識別研究中的良好數(shù)據(jù)采集工具，對研究頭部動作具有較大優(yōu)勢[15]。以上研究主要關(guān)注人體動作識別與分類，而沒有考慮實際應用中具體場景下人體運動特征與狀態(tài)相互關(guān)聯(lián)的特性，人體的動作是當前狀態(tài)下人體對外界條件變化做出的反應。在行人導航場景下，導航場景的變化會引起行人認知狀態(tài)的轉(zhuǎn)移和變化。對個體狀態(tài)的感知與識別方面，文獻[16]提出了一種用戶行為感知輔助的室內(nèi)行人定位方法，通過傳感器獲取行人在室內(nèi)特殊位置的相關(guān)行為狀態(tài)，結(jié)合室內(nèi)路網(wǎng)拓撲結(jié)構(gòu)進行輔助定位；在智能交通領(lǐng)域，文獻[17]結(jié)合近景和遠景，探索了在全天候的混合交通條件下，基于視覺感知的行人狀態(tài)跟蹤模型；文獻[18]研究行人交叉口過街這一典型情景，對行人的心理及行為進行分析，總結(jié)出多種影響行人心理和行為的因素。有限狀態(tài)自動機模型是一種表達有限個狀態(tài)以及在這些狀態(tài)間的轉(zhuǎn)移和動作的模型[19-21]，常用在計算機領(lǐng)域的識別研究中。有學者將其應用在在行人的狀態(tài)表達中并取得很好的效果，文獻[22]提出一種基于視頻跟蹤的行人過街狀態(tài)表達與分析方法，采用有限狀態(tài)自動機的方式對狀態(tài)進行表述；文獻[23]建立了一種基于人員行為細節(jié)的微觀離散仿真模型，采用蒙皮動畫和有限狀態(tài)機技術(shù)實現(xiàn)對人物行為和人物模型細節(jié)狀態(tài)的控制；文獻[24]構(gòu)造了姿勢序列有限狀態(tài)自動機，實現(xiàn)了對人體預定義動作的在線識別。

行人的行為體現(xiàn)了對當前環(huán)境的認知狀態(tài)，現(xiàn)有研究中較少涉及對行人導航狀態(tài)的研究。本文提出一種基于有限狀態(tài)自動機(finite state machine，F(xiàn)SM)的行人導航狀態(tài)匹配算法，對行人導航過程中的狀態(tài)變化進行識別和分析。首先采集谷歌眼鏡和手機的多源傳感器數(shù)據(jù)，提取動作特征參數(shù)，對導航過程中行人動作進行識別；其次對行人導航狀態(tài)和相應典型代表動作組合通過有限狀態(tài)自動機進行表述，建立狀態(tài)轉(zhuǎn)移模型；最后通過基于轉(zhuǎn)移模型的匹配算法對行人導航狀態(tài)進行識別。主要原理如圖1所示。

圖1 主要技術(shù)原理Fig.1 Technology and principle flow chart

1 行人導航狀態(tài)

行人導航狀態(tài)是行人在跟隨導航系統(tǒng)引導過程中對于實際環(huán)境與當前路徑的認知狀態(tài)，根據(jù)實際經(jīng)驗，可以將行人導航狀態(tài)描述為由熟悉、陌生和迷路3類狀態(tài)的組合和過渡。

(1) 熟悉狀態(tài)：該狀態(tài)具有完整認知、完全對應、任意到達等特性，對規(guī)劃路段有完整的認知，能與現(xiàn)實場景中的路徑完全對應，具體體現(xiàn)在可以畫出路徑及周邊環(huán)境的認知地圖，并且能夠不借助外部指示到達認知地圖上任意地點。

(2) 陌生狀態(tài)：該狀態(tài)具有部分認知、部分對應、可以到達等特性。對規(guī)劃路段認知較少，但仍能與現(xiàn)實場景中的路徑對應，具體體現(xiàn)在知道自身方位、目的地方位、路徑信息，并且可以不借助外部指示沿路徑到達目的地。

(3) 迷路狀態(tài)：該狀態(tài)具有極少認知、無法對應、不能到達等特性。對規(guī)劃路段認知較少，無法與現(xiàn)實場景中的路徑對應，不借助外部指示不能按預定路線到達目的地。值得注意的是，此迷路狀態(tài)既包含需要問路、打車等較深層次(花費較長時間、精力)的狀態(tài)又包含經(jīng)過簡單對比匹配地圖路徑較淺層次(花費較短時間、精力)的狀態(tài)。

2 行人導航狀態(tài)代表性動作

借鑒行人交通行為研究，設(shè)計調(diào)查問卷針對行人在實際使用手機導航中的體驗和表現(xiàn)，在問卷網(wǎng)(www.wenjuan.com)上編輯并發(fā)布，篇幅所限此處不列出內(nèi)容，訪問鏈接為https:∥www.wenjuan.com/s/YzUfEvU/，總瀏覽量384，獲取有效調(diào)查問卷300份，平均答題時長10 min 41 s。根據(jù)調(diào)查結(jié)果，得出行人導航3種狀態(tài)的代表性動作如表1所示。

表1 狀態(tài)代表性動作Tab.1 The state representative actions

結(jié)合實際行人導航經(jīng)驗進行分析：當行人對導航路徑熟悉時，信心十足，邁步頻率平穩(wěn)，頭部會有隨機的左右、上下擺動；當行人對導航路徑陌生時，缺乏對環(huán)境的認知導致信心的缺失，為了確認自己走的路徑與導航規(guī)劃路徑相符，會經(jīng)常性地放慢腳步對比周圍環(huán)境與導航地圖，從而表現(xiàn)出“左顧右盼”與“邁步頻率時快時慢”的行為，此時的頭部運動是有目的性的；當行人處于迷路狀態(tài)時，需要重新識路，“問路”與“尋找對比地圖顯示的地標”是典型行為，從而表現(xiàn)出“停止行走”、“四處張望”。

對上述各狀態(tài)的代表性動作進行總結(jié)，將其歸納為兩類主要動作，一類為行人的行走動作，一類為行人的頭部動作。其中行走動作又分為靜止狀態(tài)，即停止行走；行走狀態(tài)，即有位移狀態(tài)，包括平地步行、上樓梯、下樓梯、上斜坡、下斜坡等動作。頭部動作包括頭部的上下動作，即抬頭與低頭，對應行人審視導航環(huán)境和獲取導航信息的動作；另一部分是頭部的左右動作，即左視和右視，對應行人對環(huán)境的確認過程，尋找標志物等動作。

定義行人動作特征向量來描述動作特征數(shù)據(jù)，實現(xiàn)對不同導航狀態(tài)下的行人代表性動作的識別。行人動作特征包括行走動作特征參數(shù)和頭部動作特征參數(shù)，其中行走動作特征包括行走狀態(tài)特征和頻率參數(shù)。

2.1 行走動作及特征

研究人行走周期中作用力的變化可以發(fā)現(xiàn)：當行人發(fā)力用腳蹬地時，地面對腳掌有反作用力，即刻產(chǎn)生豎直向加速度并逐漸增大，與此同時人身體重心開始上移，當重心不再上升時，豎直向加速度停止增加，隨后從最大值逐漸變小，下一次邁步時重復[25]。建立人體行走狀態(tài)下的三軸坐標系(前向軸、側(cè)向軸和垂直軸)，將其與設(shè)備坐標系和全局坐標系進行對應。如圖2所示，設(shè)備坐標系的Y軸對應人體坐標系的垂向軸和全局坐標系中的ZE軸。

圖2 坐標系示意Fig.2 Coordinate systems

提取行走狀態(tài)下谷歌眼鏡的加速度傳感器信號，可以發(fā)現(xiàn)設(shè)備坐標系中對應人體豎直向的Y軸加速度存在周期性的變化，對該軸加速度信號處理分析，可以提取其代表性特征。如圖3中所示，Y軸信號規(guī)律明顯，具有周期性特征。

圖3 加速度信號Fig.3 Acceleration signal curve

為獲取行人的行走動作信息，本文采用基于谷歌傳感器的曲線擬合計步算法來探測人體的邁步和靜止動作[12]。采用傳感器數(shù)據(jù)融合的方法，利用旋轉(zhuǎn)矢量傳感器數(shù)據(jù)和加速度傳感器數(shù)據(jù)提取人體運動過程中垂向軸的加速度信號，通過快速傅里葉變換去除信號噪聲得到光滑曲線，采用最小二乘法對一個周期內(nèi)的加速度信號進行擬合得到二次曲線，其特殊的幾何特征可以作為動作識別的特征。對行走動作識別的基礎(chǔ)上，結(jié)合時間信息，可進一步得到頻率信息。進行多次試驗統(tǒng)計多場景下100步范圍內(nèi)的邁步頻率標準差(表2)，該指標可以反映行人邁步動作的平穩(wěn)程度。表中所示，平地、上斜坡、下斜坡(0.17左右)較上樓和下樓(0.25左右)穩(wěn)定，整體來講，標準差均在0.3以下。由此定義100步范圍內(nèi)邁步頻率標準差小于0.3為邁步平穩(wěn)的判斷標準。

表2 多場景下邁步頻率統(tǒng)計Tab.2 The statistics of stride frequency

2.2 頭部動作及特征

研究人體頭部的動作，以人的頸部為原點，肩為橫軸，豎直軸為縱軸，人的頭部運動主要包括抬頭、低頭、左轉(zhuǎn)、右轉(zhuǎn)、左偏(偏離豎直軸)、右偏(偏離豎直軸)6種基本動作。在導航環(huán)境下，人眼獲取導航信息和環(huán)境信息會伴隨抬頭、低頭及左視右視的動作，故行人頭部動作研究主要針對抬頭、低頭、左轉(zhuǎn)、右轉(zhuǎn)這4個動作。

頭部繞頸部的上下左右運動，將其對應到谷歌眼鏡設(shè)備坐標系中，分別體現(xiàn)為設(shè)備繞不同軸的運動，帶來不同角度在一定范圍內(nèi)的變化。同時，其在時間軸上也具備一定的持續(xù)時間特征。

圖1中的設(shè)備坐標系中，X軸為俯仰軸，Y軸為航向軸，Z軸為橫滾軸，谷歌眼鏡上搭載的方向傳感器記錄的3個角度值分別對應俯仰角、航向角和橫滾角。頭部的動作中，抬頭、低頭動作是設(shè)備繞俯仰軸上下運動的過程，對應俯仰角(pitch angle)的變化。左轉(zhuǎn)、右轉(zhuǎn)動作是設(shè)備繞航向軸旋轉(zhuǎn)的運動，方位角(azimuth)可以用來衡量此類動作。由于人體頭部的左轉(zhuǎn)右轉(zhuǎn)是相對于人的軀體方向而言的，因此將人的軀體正面朝向定位為正視方向，頭部方位角相對于正視方向的變化趨勢可以反映頭部的運動趨勢。

圖4是低頭抬頭引起的俯仰角變化，以及頭部左轉(zhuǎn)右轉(zhuǎn)引起的方位角變化，均具有明顯的角度范圍變化特征。人體頭部繞頸部運動都有一定的幅度限制，因此確定每個動作的角度范圍，即代表了動作特征，進一步可識別特定動作。

對行人低頭和抬頭時，俯仰角的變化進行統(tǒng)計，如圖5所示，發(fā)現(xiàn)試驗結(jié)果存在個體差異但大致規(guī)律明顯，將平視動作的角度范圍設(shè)為-10°～10°、低頭動作的角度范圍設(shè)為10°～60°、抬頭動作的角度范圍設(shè)為-10°～-60°，可通過俯仰角大小特征識別抬頭、低頭動作。

圖5 低頭抬頭角度數(shù)據(jù)統(tǒng)計Fig.5 The statistics of head up, head down experimental data

對行人頭部左轉(zhuǎn)和右轉(zhuǎn)引起的方位角變化進行試驗分析，這里將導航手機獲取的軀體方位角視為人體的正視方向，試驗者在正視狀態(tài)下行走得到的頭部方位角與軀體方位角之差的統(tǒng)計如下圖6所示。正視狀態(tài)下，兩者之差均在10°范圍內(nèi)。

圖6 正視試驗數(shù)據(jù)統(tǒng)計Fig.6 The statistics of facing experimental data

由于方位角具有以正北方向為參考方向，范圍為0°～360°的特性，進一步確定頭部左右轉(zhuǎn)動的具體特征判斷條件如下。

設(shè)正視方位角為DM，正視方位角范圍閾值為Dx，Dx設(shè)為10°，谷歌眼鏡獲取的頭部方位角為DG，則：

(1) 若90°

(2) 若0°≤DM≤90°，當-Dx≤DG≤Dx時為正視；當Dx

(3) 若270°≤DM<360°，當-Dx≤DM-DG≤Dx時為正視；當Dx270°時為右轉(zhuǎn)。

3 行人導航狀態(tài)FSM構(gòu)造及其匹配算法

3.1 行走導航狀態(tài)FSM模型

行人導航狀態(tài)間的轉(zhuǎn)移體現(xiàn)為不同的動作組合，人體穿戴的傳感器設(shè)備可以捕捉到人體動作信息，且具有一定的數(shù)據(jù)特征。按2.1節(jié)和2.2節(jié)中的方法可以得到代表動作的參數(shù)特征，通過運動數(shù)據(jù)特征可以識別預定義的幾類代表動作。有限狀態(tài)自動機是表示有限個狀態(tài)以及在這些狀態(tài)之間的轉(zhuǎn)移和動作等模型，支持各種復雜行為的建模。本文采用基于有限狀態(tài)自動機的方法對行人的行為狀態(tài)進行表達。有限狀態(tài)自動機擁有有限數(shù)量的狀態(tài)，狀態(tài)間可以互相遷移，輸入動作決定如何執(zhí)行狀態(tài)間的遷移。將識別的行人動作組合序列作為輸入動作，使用有限狀態(tài)自動機檢測行人導航狀態(tài)的轉(zhuǎn)移。

利用有限狀態(tài)自動機研究行人導航過程中行人狀態(tài)的轉(zhuǎn)移，將有限狀態(tài)自動機用如下4元組表示

M=(S,A,δ,F)

式中，S=(S1,S2,S3)為有限狀態(tài)集，S1代表行人導航的熟悉狀態(tài)，S2代表陌生狀態(tài)，S3代表迷路狀態(tài)；A=(A1,A2,…,An)為輸入動作集，表示輸入已識別的行走動作和頭部動作特征向量，這里的n=5。表3給出了本文描述的行人導航基本動作。導航狀態(tài)判別的所對應狀態(tài)轉(zhuǎn)移FSM模型如圖7所示，δ是狀態(tài)轉(zhuǎn)移函數(shù)，定義為：S*A→S，表示動作序列FSM從當前狀態(tài)轉(zhuǎn)換到后繼狀態(tài)。F是最終狀態(tài)的集合，是S的子集，可能為空。表4給出了狀態(tài)轉(zhuǎn)移表。

表3 動作定義表Tab.3 Definition of actions

表4 狀態(tài)轉(zhuǎn)移表Tab.4 State transition table

圖7 狀態(tài)轉(zhuǎn)移FSM模型Fig.7 State transition diagram

對行人導航過程中識別的行人基本動作進行標識定義，如表3所示。在實際行人導航過程中，行人在不同狀態(tài)下的動作通常較為復雜，可以理解為是多個上述基本動作的組合序列。構(gòu)建的有限狀態(tài)機模型中，動作集中A1代表的動作為行走，邁步頻率不穩(wěn)定，且伴隨頭部左右運動；A2代表行走且步伐穩(wěn)定，對于這類由陌生向熟悉狀態(tài)的轉(zhuǎn)移，行人沒有了導航的需求，實際情況中可以不作判斷；A3代表陌生狀態(tài)的再次確認，動作表現(xiàn)與A1相同；A4代表行人由陌生狀態(tài)進入迷路狀態(tài)前的動作，表現(xiàn)為停止行走，且頭部左右運動；A5表示行人脫離迷路狀態(tài)，對當前路徑環(huán)境建立起了一定的認知，動作表現(xiàn)為重新開始行走。對動作序列FSM中的輸入動作集進行分析，其對應的動作特征組合如下：

A1：a1∧a2，其中a1∈(B,C,D,E,F)，a2∈(H∧I∧(K∨L))

A2：a1，其中a1∈(B,C,D,E,F)，頻率穩(wěn)定

A4：A∧(H∨I)∧(K∨L)

a5：a1，其中a1∈(B,C,D,E,F)

其中,ai∧aj表示動作ai與aj同時出現(xiàn)，即行人同時做出這兩個動作；ai∨aj表示兩個動作中出現(xiàn)任一個。

構(gòu)造行人導航狀態(tài)轉(zhuǎn)移的有限狀態(tài)自動機模型，可以將行人當前動作與狀態(tài)聯(lián)系起來，通過狀態(tài)轉(zhuǎn)移函數(shù)，可以識別和判斷狀態(tài)轉(zhuǎn)移過程，用于幫助確定行人當前導航狀態(tài)。

3.2 匹配算法

在上述研究的基礎(chǔ)上，本問題提出基于狀態(tài)自動機的行人導航狀態(tài)匹配算法，其匹配算法的流程如圖8所示。

圖8 匹配算法流程Fig.8 The flow diagram of the matching algorithm

該算法主要流程簡要描述如下。

(1) 設(shè)置狀態(tài)機初始狀態(tài)S；

(2) 輸入導航終端的傳感器數(shù)據(jù),包括旋轉(zhuǎn)矢量傳感器數(shù)據(jù)、加速度傳感器、方向傳感器數(shù)據(jù)等，識別行走動作及其特征、頭部動作及其特征，構(gòu)成動作輸入集合；

(3) 根據(jù)狀態(tài)轉(zhuǎn)移表4和狀態(tài)轉(zhuǎn)移FSM模型，進行判斷，符合A1、A2、A4、A5狀態(tài)某一狀態(tài)轉(zhuǎn)移條件，則將狀態(tài)S更新至相應狀態(tài)，并輸出結(jié)果；

(4) 重復步驟(1)—(3)，直至處理完全部傳感器數(shù)據(jù)集。

4 試驗分析

4.1 試驗結(jié)果

本文采取實地試驗的方式采集試驗數(shù)據(jù)，試驗設(shè)計時首先選擇合適的起終點，選擇百度地圖進行路徑規(guī)劃得到試驗用的導航路線。經(jīng)過前期調(diào)研工作，試驗區(qū)域選在武漢大學和華中師范大學校園內(nèi)，起點選在武漢大學信息學部內(nèi)，將華中師范大學天門樓作為終點，得到導航路線如圖9(a)所示，全程步行距離約1.48 km，參與試驗的志愿者均未走過此路線，適合進行試驗。4名志愿者參與試驗中，分別佩戴谷歌眼鏡，根據(jù)手機上給出的如圖9(a)中所示的導航路線信息，從起點沿給定路線走到終點。在行走過程中，以25 Hz的頻率記錄谷歌眼鏡的傳感器數(shù)據(jù)，包括時間、加速度傳感器、旋轉(zhuǎn)矢量傳感器、方向傳感器和陀螺儀數(shù)據(jù)。將記錄的數(shù)據(jù)作為匹配算法的輸入信息，基于確定的動作特征判斷參數(shù)和有限狀態(tài)自動機的狀態(tài)轉(zhuǎn)移模型，利用本文提出的匹配算法對試驗數(shù)據(jù)進行處理得到匹配結(jié)果。

圖9 試驗場景與試驗結(jié)果示意Fig.9 Experimental scenario and results

圖9(b)—(e)分別展示了4名試驗者的狀態(tài)識別結(jié)果，其中圖上藍色路徑表示熟悉路段、黃色路徑表示陌生路段，黑色點表示熟悉向陌生轉(zhuǎn)移處、綠色點表示陌生狀態(tài)再次確認處、紅色點表示陌生向迷路轉(zhuǎn)移處，迷路向陌生轉(zhuǎn)移處緊挨著紅色點故圖上不標出。

這里以試驗者1為代表，對試驗過程中出現(xiàn)左顧右盼動作時發(fā)生的狀態(tài)轉(zhuǎn)移進行統(tǒng)計，主要涵蓋陌生和迷路狀態(tài)。統(tǒng)計結(jié)果如表5所示，其結(jié)果與圖9(b)對應。

表5 試驗一狀態(tài)匹配統(tǒng)計Tab.5 Statistics of state matching of experiment 1

注:表示識別有誤

按照上述方法可以得到4次試驗中的統(tǒng)計數(shù)據(jù)，試驗過程中全程跟蹤觀察試驗者并用拍照的方式輔助記錄其真實狀態(tài)，將利用本文方法得到的匹配結(jié)果與真實記錄進行對比得到匹配準確度的統(tǒng)計如表6所示。

從表6中可以看出，算法對熟悉向陌生狀態(tài)的判斷識別的準確度為100%；算法對迷路點的確認準確度高且穩(wěn)定(平均90%左右)；算法對于陌生狀態(tài)的再確認識別準確度較高(平均60%左右)。

4.2 討 論

本文算法是利用微傳感器數(shù)據(jù)識別特定環(huán)境下的行人特征動作，進而匹配行人所處狀態(tài)。算法的準確度和普適性取決于兩方面：行走導航狀態(tài)FSM模型的可靠性；匹配算法的準確性；FSM模型的建立涉及認知、心理、習慣等不易定量分析的概念，本文采用問卷調(diào)查的方式獲取了較為準確的建模基礎(chǔ)資料，基本能夠反映真實狀態(tài)。匹配算法的準確性可從4.1試驗結(jié)果部分得出，相對而言，算法對陌生狀態(tài)的再確認相對于迷路識別準確度較低。實際情況下，迷路與陌生狀態(tài)再確認均發(fā)生在陌生路段中，均是行人對導航路徑不確認的表現(xiàn)，但迷路所代表的不確認程度相對更大。圖10更直觀地展示了試驗者“不確定”點的分布及本算法的識別結(jié)果。

表6 匹配準確度Tab.6 The statistics of matching accuracy

圖10 試驗者“不確定”點分布Fig.10 Distribution map

由表6可知本試驗中同一環(huán)境下，4名試驗者表現(xiàn)出不確定次數(shù)分別為12、10、14、11，其分布如圖10所示，圖中帶斜杠的點表示未識別出。由圖10可知此環(huán)境下較容易給行人造成困惑的地點分布大致相同(實際環(huán)境中這些點多為岔道口或建筑物樹蔭遮蔽嚴重的地點)而個體差異主要體現(xiàn)在迷路點與陌生狀態(tài)再確認點的分布上，更謹慎或者認知相對較差的行人迷路次數(shù)多一些，試驗者1與試驗者3對比明顯，同一個“不確定”點前者多視為迷路點。而后者多視為陌生狀態(tài)再確認點。此外，陌生路段通常在整個導航路段中占據(jù)絕大部分，所以不確定點的出現(xiàn)幾率相對于其他點大得多，所以個體的差異性在本文模型中的迷路點與陌生狀態(tài)再確認點的分布上表現(xiàn)得較為明顯。

算法識別機制上，迷路有“停止行走”和“左顧右盼”兩個識別特征，陌生狀態(tài)再確認有“邁步頻率不穩(wěn)定”和“左顧右盼”兩個識別特征?！巴Ｖ剐凶摺迸c“邁步頻率不穩(wěn)定”均是行走動作的特征，兩者比較而言：“停止行走”由一個獨立的瞬時變量(走、停)識別，“邁步是否平穩(wěn)”則必須有一個參照變量(邁步頻率標準差)，而該參照變量是一個過程變量(需要一定的時間才能確定)?！白箢櫽遗巍笔穷^部動作特征，與“停止行走”和“邁步頻率不穩(wěn)定”屬于相對獨立的兩個系統(tǒng)，因此，當這兩個特征分別與“左顧右盼”結(jié)合作為判斷標準時，后者有可能出現(xiàn)超前或滯后，從而導致“陌生狀態(tài)再確認”識別不準確。為改善算法，需要確定更為精準、可靠的識別特征或者進一步的判斷機制。在更廣泛的調(diào)查基礎(chǔ)上建立更完善的行走導航狀態(tài)FSM模型，建立自適應機制以降低個體差異的影響，增加模型的容錯率，這是筆者下一步研究的方向之一。

5 結(jié) 論

本文提出的導航環(huán)境下行人有限狀態(tài)轉(zhuǎn)移模型及匹配算法，將處于導航環(huán)境下的行人動作及狀態(tài)與環(huán)境認知聯(lián)系起來，先通過調(diào)查建立狀態(tài)分類規(guī)則，提取每類狀態(tài)的典型動作和特征參數(shù)，再根據(jù)識別動作來判斷所處狀態(tài)。本文實現(xiàn)并驗證所提出方法的可行性和有效性，試驗結(jié)果表明匹配算法對于識別行人狀態(tài)達到較高的準確度。在本文的研究中，僅對于典型的動作和狀態(tài)進行了研究，更加精細的行為識別模型有待進一步深入研究。未來的研究工作中，將考慮將本文算法識別出的行人導航過程中導航狀態(tài)轉(zhuǎn)移結(jié)果作為基礎(chǔ)，研究導航環(huán)境下行人容易出現(xiàn)陌生或迷路的地點，在這些地點上提供更精細化的路徑導航服務(wù)，幫助提升導航成功率。

[1] 張星, 李清泉, 方志祥, 等.顧及地標與道路分支的行人導航路徑選擇算法[J].武漢大學學報(信息科學版), 2013, 38(10): 1239-1242.ZHANG Xing, LI Qingquan, FANG Zhixiang, et al.Landmark and Branch-based Pedestrian Route Complexity and Selection Algorithm[J].Geomatics and Information Science of Wuhan University, 2013, 38(10): 1239-1242.

[2] 陳玥璐, 武剛, 陳飛翔.基于地標的行人導航路徑引導方法[J].地理與地理信息科學, 2015, 31(1): 17-22.CHEN Yuelu, WU Gang, CHEN Feixiang.Route Directions Method of Pedestrian Navigation Based on Landmark[J].Geography and Geo-Information Science, 2015, 31(1): 17-22.

[3] 李清泉, 李秋萍, 方志祥.一種基于時空擁擠度的應急疏散路徑優(yōu)化方法[J].測繪學報, 2011, 40(4): 517-523.LI Qingquan, LI Qiuping, FANG Zhixiang.An Emergency Evacuation Routing Optimization Method Based on Space-time Congestion Concept[J].Acta Geodaetica et Cartographica Sinica, 2011, 40(4): 517-523.

[4] 于海璁, 陸鋒.一種基于遺傳算法的多模式多標準路徑規(guī)劃方法[J].測繪學報, 2014, 43(1): 89-96.YU Haicong, LU Feng.A Multi-modal Multi-criteria Route Planning Method Based on Genetic Algorithm[J].Acta Geodaetica et Cartographica Sinica, 2014, 43(1): 89-96.

[5] FANG Zhixiang, LI Qingquan, ZHANG Xing.A GIS Data Model for Landmark-based Pedestrian Navigation[J].International Journal of Geographical Information Science, 2012, 26(5): 817-838.

[6] 李瑞峰, 王亮亮, 王珂.人體動作行為識別研究綜述[J].模式識別與人工智能, 2014, 27(1): 35-48.LI Ruifeng, WANG Liangliang, WANG Ke.A Survey of Human Body Action Recognition[J].Pattern Recognition and Artificial Intelligence, 2014, 27(1): 35-48.

[7] 凌志剛, 趙春暉, 梁彥, 等.基于視覺的人行為理解綜述[J].計算機應用研究, 2008, 25(9): 2570-2578.LING Zhigang, ZHAO Chunhui, LIANG Yan, et al.Survey on Vision-based Human Action Understanding[J].Application Research of Computers, 2008, 25(9): 2570-2578.

[8] POPPE R.A Survey on Vision-based Human Action Recognition[J].Image and Vision Computing, 2010, 28(6): 976-990

[9] WEINLAND D, RONFARD R, BOYER E.A Survey of Vision-based Methods for Action Representation, Segmentation and Recognition[J].Computer Vision and Image Understanding, 2011, 115(2): 224-241.

[11] 陳野, 王哲龍, 李政霖, 等.基于BSN和神經(jīng)網(wǎng)絡(luò)的人體日常動作識別方法[J].大連理工大學學報, 2013, 53(6): 893-897.CHEN Ye, WANG Zhelong, LI Zhenglin, et al.Human Daily Activity Recognition Method Based on BSN and Neural Network[J].Journal of Dalian University of Technology, 2013, 53(6): 893-897.

[12] 羅浩, 方志祥, 蕭世倫.基于谷歌眼鏡傳感器的曲線擬合計步算法[J].計算機工程與應用, 2016, 52(18): 40-45, 67.LUO Hao, FANG Zhixiang, XIAO Shilun.Curve Fitting Step Counting Algorithm Based on Google Glass Sensor[J].Computer Engineering and Applications, 2016, 52(18): 40-45, 67.

[13] 陳國良, 張言哲, 楊洲.一種基于手機傳感器自相關(guān)分析的計步器實現(xiàn)方法[J].中國慣性技術(shù)學報, 2014, 22(6): 794-798.CHEN Guoliang, ZHANG Yanzhe, YANG Zhou.Realization of Pedometer with Auto-correlation Analysis Based on Mobile Phone Sensor[J].Journal of Chinese Inertial Technology, 2014, 22(6): 794-798.

[14] YANG Xiuxin, DINH A, CHEN Li.Implementation of a Wearerable Real-time System for Physical Activity Recognition Based on Naive Bayes Classifier[C]∥Proceedings of International Conference on Bioinformatics and Biomedical Technology.Chengdu, China: IEEE, 2010: 101-105.

[15] 楊凱鵬, 張德珍, 崔皓.谷歌眼鏡產(chǎn)品及其專利布局分析[J].中國發(fā)明與專利, 2014(1): 40-45.YANG Kaipeng, ZHANG Dezhen, CUI Hao.Google Glasses Products and Patent Distribution Analysis[J].China Invention & Patent, 2014(1): 40-45.

[16] 周寶定, 李清泉, 毛慶洲, 等.用戶行為感知輔助的室內(nèi)行人定位[J].武漢大學學報(信息科學版), 2014, 39(6): 719-723.ZHOU Baoding, LI Qingquan, MAO Qingzhou, et al.User Activity Awareness Assisted Indoor Pedestrian Localization[J].Geomatics and Information Science of Wuhan University, 2014, 39(6): 719-723.

[17] 孫承岳.結(jié)合近景和遠景分析的行人狀態(tài)跟蹤[D].北京: 北京交通大學, 2014.SUN Chengyue.The Tracking of Pedestrians’ Status Based on the Analysis of Far-view Video and Near-view Video[M].Beijing: Beijing Jiaotong University, 2014.

[18] 劉光新, 李克平, 倪穎.交叉口行人過街心理及交通行為分析[J].交通科技與經(jīng)濟, 2008, 10(5): 58-61.LIU Guangxin, LI Keping, NI Ying.An Overview on Pedestrian Psychology and Behavior when Crossing Intersections[J].Technology & Economy in Areas of Communications, 2008, 10(5): 58-61.

[19] YIN Yongfeng, Liu Bin, NI Hongying.Real-time Embedded Software Testing Method Based on Extended Finite State Machine[J].Journal of Systems Engineering and Electronics, 2012, 23(2): 276-285.

[20] ANDERSON J A.Automata Theory with Modern Applications[M].Cambridge: Cambridge University Press, 2006: 105-108.

[21] WAGNER F, SCHMUKI R, WAGNER T, et al.Modeling Software with Finite State Machines: A Practical Approach[M].Boca Raton, FL: CRC Press, 2006.

[22] 胡宏宇, 王殿海, 孫迪.基于視頻跟蹤方法的行人過街狀態(tài)表達與分析[J].交通信息與安全, 2009, 27(3): 43-47.HU Hongyu, WANG Dianhai, SUN Di.Representation and Analysis of Pedestrian Crossing States Based on Video Tracking[J].Journal of Transport Information and Safety, 2009, 27(3): 43-47.

[23] 胡清梅, 方衛(wèi)寧, 郭北苑, 等.基于行人運動模型的人群疏散三維仿真[J].北京交通大學學報, 2009, 33(4): 34-37.HU Qingmei, FANG Weining, GUO Beiyuan, et al.3-D Simulation of Crowd Evacuation Based on a Pedestrian Movement Model[J].Journal of Beijing Jiaotong University, 2009, 33(4): 34-37.

[24] 林水強, 吳亞東, 余芳, 等.姿勢序列有限狀態(tài)機動作識別方法[J].計算機輔助設(shè)計與圖形學學報, 2014, 26(9): 1403-1411.LIN Shuiqiang, WU Yadon, YU Fang, et al.Posture Sequence Finite-State Machine Method for Motion Recognition[J].Journal of Computer-aided Design & Computer Graphics, 2014, 26(9): 1403-1411.

[25] 許睿.行人導航系統(tǒng)算法研究與應用實現(xiàn)[D].南京: 南京航空航天大學, 2008.XU Rui.Research and Application on Navigation Algorithm of Pedestrian Navigation System[D].Nanjing: Nanjing University of Aeronautics and Astronautics, 2008.

(責任編輯：宋啟凡)

A Finite State Machine Aided Pedestrian Navigation State Matching Algorithm

FANG Zhixiang1，LUO Hao2，LI Ling1

1.State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China； 2.Second School in Surveying，Mapping and Geographic Information, Sichuan Province, Chengdu 610100, China

The automatic identification of pedestrian’s navigation state is a difficult problem in pedestrian navigation research.It is important to improve the precision feedback and navigation performance of pedestrian navigation services, and few researches have been done in this field.This paper proposes a pedestrian navigation state matching algorithm based on finite state machine (FSM).The main idea of this method is to identify the pedestrian navigation state on the basis of recognizing pedestrian’s actions.The pedestrian’s action characteristics are recognized by using multiple sensor data collected by Google glass and mobile phone.Then, the pedestrian navigation states are divided into familiar, unfamiliar and lost state.The state transition model is established according to the FSM theory, and the pedestrian navigation state matching algorithm based on the model is designed.Finally, this algorithm is implemented, and experiments are conducted to validate its effectiveness.Experimental results show that the proposed algorithm can reach a good precision of recognizing the state transitions during pedestrian navigation process, and especially the accuracy of recognizing lost state achieves 90%.

pedestrian navigation; finite state machine; action recognition; navigation state matching

The National Natural Science Foundation of China (No.413714420)

FANG Zhixiang(1977—)，male，professor，PhD supervisor，majors in pedestrian navigation theory and application, and space-time behavior modeling and application.

方志祥，羅浩，李靈.有限狀態(tài)自動機輔助的行人導航狀態(tài)匹配算法[J].測繪學報，2017,46(3)：371-380.

10.11947/j.AGCS.2017.20160530.

FANG Zhixiang，LUO Hao，LI Ling.A Finite State Machine Aided Pedestrian Navigation State Matching Algorithm[J].Acta Geodaetica et Cartographica Sinica,2017,46(3):371-380.DOI:10.11947/j.AGCS.2017.20160530.

P208

A

1001-1595(2017)03-0371-10

國家自然科學基金面上項目(413714420)

2016-10-24

修回日期：2017-03-09

方志祥(1977—)，男，教授，博士生導師，研究方向為行人導航、時空行為建模與應用。

E-mail：zxfang@whu.edu.cn