有限状态自动机辅助的行人导航状态匹配算法

方志祥，罗 浩，李 灵

1.武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉 430079； 2.四川省第二测绘地理信息工程院，四川 成都 610100



有限状态自动机辅助的行人导航状态匹配算法

方志祥1，罗 浩2，李 灵1

1.武汉大学测绘遥感信息工程国家重点实验室，湖北 武汉 430079； 2.四川省第二测绘地理信息工程院，四川 成都 610100

行人导航状态的自动识别是行人导航研究的一个难点问题，对提升行人导航软件服务的精准反馈与改善导航性能至关重要，此方面已有的研究工作很少。本文提出了一种基于有限状态自动机的行人导航状态匹配算法，其核心思想是在识别行人动作基础上匹配行人当前导航状态。利用谷歌眼镜及智能手机采集的多种传感器数据对行人动作进行识别，得到其动作特征参数；然后将行人导航状态分为熟悉、陌生及迷路3类，根据有限状态自动机理论建立状态转移模型，设计基于该模型的行人导航状态匹配算法；最后，实现状态匹配算法，通过试验对该算法的有效性进行验证。试验结果表明，该算法能够较好地识别行人导航过程中的状态转移，其中对熟悉向陌生状态转移识别准确度较高，对迷路状态识别准确度达到90%。

行人导航；有限状态自动机；动作识别；状态匹配

行人导航服务成为基于位置的服务的研究热点，智能移动设备的普及使得行人导航服务越来越便捷，由电子地图、定位、路径规划和路径引导等组成的行人导航系统广泛应用在帮助行人沿规划路径到达目的地[1-2],行人导航通过导航地图提供空间信息，完成路径规划等[3-5]。但是由于具体导航任务复杂度高，或现有路径引导方式的不足等，行人还是会出现迷路状况，导致无法按照既定规划路线到达目的地。行人导航是对地理环境的认知与行人决策相结合的过程，个体对环境认知状态的变化会引起不同的动作反应，行人的动作与状态是相互关联的，研究行人导航的实时状态，及时发现和识别行人可能出现的迷路状态，对于提高行人导航服务的成功率和舒适度具有重要意义。

人体的动作可以直接反映个体的状态。现有对人体动作识别的研究中，人体运动信息的获取方式主要有两种，基于视觉的和基于微惯性传感器的。基于视觉的人体运动监测研究起步较早，在视频监控、虚拟现实等领域应用广泛，涉及运动目标检测、动作特征提取和动作特征理解[6-9]等主要技术。但是基于视觉的行为动作监测对外部环境光线、背景等依赖较大，空间复杂性和时间差异性对此类研究的影响很大。随着微机电系统(micro-electro-mechanical system，MEMS)的发展，加速度传感器、陀螺仪等惯性传感器充分体现在体积、灵敏度方面的优势，并且因其价格低廉，开始广泛被集成到各类便携智能设备中，如常见的智能手机以及各种新兴的智能可穿戴设备，如手表、眼镜等。利用这类智能穿戴设备采集人体运动数据具有诸多优势，如不受环境的约束和限制，能够实时准确地记录人体的复杂运动信息。国内外许多科研机构开展了利用微传感器对人体动作的监测和识别研究。文献[10]采用加速度信号和生命体征信号对跑步、上楼等5个动作应用多种分类方法进行了分类结果比较。文献[11]利用人体传感器网络构建了人体动作监测平台对日常人体的7种动作进行了分类和识别研究。文献[12—14]利用智能设备等的惯性传感器对行人步行动作等进行了识别方面的研究。谷歌眼镜是谷歌公司推出的一款智能穿戴设备，其采用Android操作系统，搭载8种传感器，佩戴在头部，负担小，可以作为人体动作识别研究中的良好数据采集工具，对研究头部动作具有较大优势[15]。以上研究主要关注人体动作识别与分类，而没有考虑实际应用中具体场景下人体运动特征与状态相互关联的特性，人体的动作是当前状态下人体对外界条件变化做出的反应。在行人导航场景下，导航场景的变化会引起行人认知状态的转移和变化。对个体状态的感知与识别方面，文献[16]提出了一种用户行为感知辅助的室内行人定位方法，通过传感器获取行人在室内特殊位置的相关行为状态，结合室内路网拓扑结构进行辅助定位；在智能交通领域，文献[17]结合近景和远景，探索了在全天候的混合交通条件下，基于视觉感知的行人状态跟踪模型；文献[18]研究行人交叉口过街这一典型情景，对行人的心理及行为进行分析，总结出多种影响行人心理和行为的因素。有限状态自动机模型是一种表达有限个状态以及在这些状态间的转移和动作的模型[19-21]，常用在计算机领域的识别研究中。有学者将其应用在在行人的状态表达中并取得很好的效果，文献[22]提出一种基于视频跟踪的行人过街状态表达与分析方法，采用有限状态自动机的方式对状态进行表述；文献[23]建立了一种基于人员行为细节的微观离散仿真模型，采用蒙皮动画和有限状态机技术实现对人物行为和人物模型细节状态的控制；文献[24]构造了姿势序列有限状态自动机，实现了对人体预定义动作的在线识别。

行人的行为体现了对当前环境的认知状态，现有研究中较少涉及对行人导航状态的研究。本文提出一种基于有限状态自动机(finite state machine，FSM)的行人导航状态匹配算法，对行人导航过程中的状态变化进行识别和分析。首先采集谷歌眼镜和手机的多源传感器数据，提取动作特征参数，对导航过程中行人动作进行识别；其次对行人导航状态和相应典型代表动作组合通过有限状态自动机进行表述，建立状态转移模型；最后通过基于转移模型的匹配算法对行人导航状态进行识别。主要原理如图1所示。

图1 主要技术原理Fig.1 Technology and principle flow chart

1 行人导航状态

行人导航状态是行人在跟随导航系统引导过程中对于实际环境与当前路径的认知状态，根据实际经验，可以将行人导航状态描述为由熟悉、陌生和迷路3类状态的组合和过渡。

(1) 熟悉状态：该状态具有完整认知、完全对应、任意到达等特性，对规划路段有完整的认知，能与现实场景中的路径完全对应，具体体现在可以画出路径及周边环境的认知地图，并且能够不借助外部指示到达认知地图上任意地点。

(2) 陌生状态：该状态具有部分认知、部分对应、可以到达等特性。对规划路段认知较少，但仍能与现实场景中的路径对应，具体体现在知道自身方位、目的地方位、路径信息，并且可以不借助外部指示沿路径到达目的地。

(3) 迷路状态：该状态具有极少认知、无法对应、不能到达等特性。对规划路段认知较少，无法与现实场景中的路径对应，不借助外部指示不能按预定路线到达目的地。值得注意的是，此迷路状态既包含需要问路、打车等较深层次(花费较长时间、精力)的状态又包含经过简单对比匹配地图路径较浅层次(花费较短时间、精力)的状态。

2 行人导航状态代表性动作

借鉴行人交通行为研究，设计调查问卷针对行人在实际使用手机导航中的体验和表现，在问卷网(www.wenjuan.com)上编辑并发布，篇幅所限此处不列出内容，访问链接为https:∥www.wenjuan.com/s/YzUfEvU/，总浏览量384，获取有效调查问卷300份，平均答题时长10 min 41 s。根据调查结果，得出行人导航3种状态的代表性动作如表1所示。

表1 状态代表性动作Tab.1 The state representative actions

结合实际行人导航经验进行分析：当行人对导航路径熟悉时，信心十足，迈步频率平稳，头部会有随机的左右、上下摆动；当行人对导航路径陌生时，缺乏对环境的认知导致信心的缺失，为了确认自己走的路径与导航规划路径相符，会经常性地放慢脚步对比周围环境与导航地图，从而表现出“左顾右盼”与“迈步频率时快时慢”的行为，此时的头部运动是有目的性的；当行人处于迷路状态时，需要重新识路，“问路”与“寻找对比地图显示的地标”是典型行为，从而表现出“停止行走”、“四处张望”。

对上述各状态的代表性动作进行总结，将其归纳为两类主要动作，一类为行人的行走动作，一类为行人的头部动作。其中行走动作又分为静止状态，即停止行走；行走状态，即有位移状态，包括平地步行、上楼梯、下楼梯、上斜坡、下斜坡等动作。头部动作包括头部的上下动作，即抬头与低头，对应行人审视导航环境和获取导航信息的动作；另一部分是头部的左右动作，即左视和右视，对应行人对环境的确认过程，寻找标志物等动作。

定义行人动作特征向量来描述动作特征数据，实现对不同导航状态下的行人代表性动作的识别。行人动作特征包括行走动作特征参数和头部动作特征参数，其中行走动作特征包括行走状态特征和频率参数。

2.1 行走动作及特征

研究人行走周期中作用力的变化可以发现：当行人发力用脚蹬地时，地面对脚掌有反作用力，即刻产生竖直向加速度并逐渐增大，与此同时人身体重心开始上移，当重心不再上升时，竖直向加速度停止增加，随后从最大值逐渐变小，下一次迈步时重复[25]。建立人体行走状态下的三轴坐标系(前向轴、侧向轴和垂直轴)，将其与设备坐标系和全局坐标系进行对应。如图2所示，设备坐标系的Y轴对应人体坐标系的垂向轴和全局坐标系中的ZE轴。

图2 坐标系示意Fig.2 Coordinate systems

提取行走状态下谷歌眼镜的加速度传感器信号，可以发现设备坐标系中对应人体竖直向的Y轴加速度存在周期性的变化，对该轴加速度信号处理分析，可以提取其代表性特征。如图3中所示，Y轴信号规律明显，具有周期性特征。

图3 加速度信号Fig.3 Acceleration signal curve

为获取行人的行走动作信息，本文采用基于谷歌传感器的曲线拟合计步算法来探测人体的迈步和静止动作[12]。采用传感器数据融合的方法，利用旋转矢量传感器数据和加速度传感器数据提取人体运动过程中垂向轴的加速度信号，通过快速傅里叶变换去除信号噪声得到光滑曲线，采用最小二乘法对一个周期内的加速度信号进行拟合得到二次曲线，其特殊的几何特征可以作为动作识别的特征。对行走动作识别的基础上，结合时间信息，可进一步得到频率信息。进行多次试验统计多场景下100步范围内的迈步频率标准差(表2)，该指标可以反映行人迈步动作的平稳程度。表中所示，平地、上斜坡、下斜坡(0.17左右)较上楼和下楼(0.25左右)稳定，整体来讲，标准差均在0.3以下。由此定义100步范围内迈步频率标准差小于0.3为迈步平稳的判断标准。

表2 多场景下迈步频率统计Tab.2 The statistics of stride frequency

2.2 头部动作及特征

研究人体头部的动作，以人的颈部为原点，肩为横轴，竖直轴为纵轴，人的头部运动主要包括抬头、低头、左转、右转、左偏(偏离竖直轴)、右偏(偏离竖直轴)6种基本动作。在导航环境下，人眼获取导航信息和环境信息会伴随抬头、低头及左视右视的动作，故行人头部动作研究主要针对抬头、低头、左转、右转这4个动作。

头部绕颈部的上下左右运动，将其对应到谷歌眼镜设备坐标系中，分别体现为设备绕不同轴的运动，带来不同角度在一定范围内的变化。同时，其在时间轴上也具备一定的持续时间特征。

图1中的设备坐标系中，X轴为俯仰轴，Y轴为航向轴，Z轴为横滚轴，谷歌眼镜上搭载的方向传感器记录的3个角度值分别对应俯仰角、航向角和横滚角。头部的动作中，抬头、低头动作是设备绕俯仰轴上下运动的过程，对应俯仰角(pitch angle)的变化。左转、右转动作是设备绕航向轴旋转的运动，方位角(azimuth)可以用来衡量此类动作。由于人体头部的左转右转是相对于人的躯体方向而言的，因此将人的躯体正面朝向定位为正视方向，头部方位角相对于正视方向的变化趋势可以反映头部的运动趋势。

图4是低头抬头引起的俯仰角变化，以及头部左转右转引起的方位角变化，均具有明显的角度范围变化特征。人体头部绕颈部运动都有一定的幅度限制，因此确定每个动作的角度范围，即代表了动作特征，进一步可识别特定动作。

对行人低头和抬头时，俯仰角的变化进行统计，如图5所示，发现试验结果存在个体差异但大致规律明显，将平视动作的角度范围设为-10°～10°、低头动作的角度范围设为10°～60°、抬头动作的角度范围设为-10°～-60°，可通过俯仰角大小特征识别抬头、低头动作。

图5 低头抬头角度数据统计Fig.5 The statistics of head up, head down experimental data

对行人头部左转和右转引起的方位角变化进行试验分析，这里将导航手机获取的躯体方位角视为人体的正视方向，试验者在正视状态下行走得到的头部方位角与躯体方位角之差的统计如下图6所示。正视状态下，两者之差均在10°范围内。

图6 正视试验数据统计Fig.6 The statistics of facing experimental data

由于方位角具有以正北方向为参考方向，范围为0°～360°的特性，进一步确定头部左右转动的具体特征判断条件如下。

设正视方位角为DM，正视方位角范围阈值为Dx，Dx设为10°，谷歌眼镜获取的头部方位角为DG，则：

(1) 若90°

(2) 若0°≤DM≤90°，当-Dx≤DG≤Dx时为正视；当Dx

(3) 若270°≤DM<360°，当-Dx≤DM-DG≤Dx时为正视；当Dx270°时为右转。

3 行人导航状态FSM构造及其匹配算法

3.1 行走导航状态FSM模型

行人导航状态间的转移体现为不同的动作组合，人体穿戴的传感器设备可以捕捉到人体动作信息，且具有一定的数据特征。按2.1节和2.2节中的方法可以得到代表动作的参数特征，通过运动数据特征可以识别预定义的几类代表动作。有限状态自动机是表示有限个状态以及在这些状态之间的转移和动作等模型，支持各种复杂行为的建模。本文采用基于有限状态自动机的方法对行人的行为状态进行表达。有限状态自动机拥有有限数量的状态，状态间可以互相迁移，输入动作决定如何执行状态间的迁移。将识别的行人动作组合序列作为输入动作，使用有限状态自动机检测行人导航状态的转移。

利用有限状态自动机研究行人导航过程中行人状态的转移，将有限状态自动机用如下4元组表示

M=(S,A,δ,F)

式中，S=(S1,S2,S3)为有限状态集，S1代表行人导航的熟悉状态，S2代表陌生状态，S3代表迷路状态；A=(A1,A2,…,An)为输入动作集，表示输入已识别的行走动作和头部动作特征向量，这里的n=5。表3给出了本文描述的行人导航基本动作。导航状态判别的所对应状态转移FSM模型如图7所示，δ是状态转移函数，定义为：S*A→S，表示动作序列FSM从当前状态转换到后继状态。F是最终状态的集合，是S的子集，可能为空。表4给出了状态转移表。

表3 动作定义表Tab.3 Definition of actions

表4 状态转移表Tab.4 State transition table

图7 状态转移FSM模型Fig.7 State transition diagram

对行人导航过程中识别的行人基本动作进行标识定义，如表3所示。在实际行人导航过程中，行人在不同状态下的动作通常较为复杂，可以理解为是多个上述基本动作的组合序列。构建的有限状态机模型中，动作集中A1代表的动作为行走，迈步频率不稳定，且伴随头部左右运动；A2代表行走且步伐稳定，对于这类由陌生向熟悉状态的转移，行人没有了导航的需求，实际情况中可以不作判断；A3代表陌生状态的再次确认，动作表现与A1相同；A4代表行人由陌生状态进入迷路状态前的动作，表现为停止行走，且头部左右运动；A5表示行人脱离迷路状态，对当前路径环境建立起了一定的认知，动作表现为重新开始行走。对动作序列FSM中的输入动作集进行分析，其对应的动作特征组合如下：

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

A2：a1，其中a1∈(B,C,D,E,F)，频率稳定

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

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

其中,ai∧aj表示动作ai与aj同时出现，即行人同时做出这两个动作；ai∨aj表示两个动作中出现任一个。

构造行人导航状态转移的有限状态自动机模型，可以将行人当前动作与状态联系起来，通过状态转移函数，可以识别和判断状态转移过程，用于帮助确定行人当前导航状态。

3.2 匹配算法

在上述研究的基础上，本问题提出基于状态自动机的行人导航状态匹配算法，其匹配算法的流程如图8所示。

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

该算法主要流程简要描述如下。

(1) 设置状态机初始状态S；

(2) 输入导航终端的传感器数据,包括旋转矢量传感器数据、加速度传感器、方向传感器数据等，识别行走动作及其特征、头部动作及其特征，构成动作输入集合；

(3) 根据状态转移表4和状态转移FSM模型，进行判断，符合A1、A2、A4、A5状态某一状态转移条件，则将状态S更新至相应状态，并输出结果；

(4) 重复步骤(1)—(3)，直至处理完全部传感器数据集。

4 试验分析

4.1 试验结果

本文采取实地试验的方式采集试验数据，试验设计时首先选择合适的起终点，选择百度地图进行路径规划得到试验用的导航路线。经过前期调研工作，试验区域选在武汉大学和华中师范大学校园内，起点选在武汉大学信息学部内，将华中师范大学天门楼作为终点，得到导航路线如图9(a)所示，全程步行距离约1.48 km，参与试验的志愿者均未走过此路线，适合进行试验。4名志愿者参与试验中，分别佩戴谷歌眼镜，根据手机上给出的如图9(a)中所示的导航路线信息，从起点沿给定路线走到终点。在行走过程中，以25 Hz的频率记录谷歌眼镜的传感器数据，包括时间、加速度传感器、旋转矢量传感器、方向传感器和陀螺仪数据。将记录的数据作为匹配算法的输入信息，基于确定的动作特征判断参数和有限状态自动机的状态转移模型，利用本文提出的匹配算法对试验数据进行处理得到匹配结果。

图9 试验场景与试验结果示意Fig.9 Experimental scenario and results

图9(b)—(e)分别展示了4名试验者的状态识别结果，其中图上蓝色路径表示熟悉路段、黄色路径表示陌生路段，黑色点表示熟悉向陌生转移处、绿色点表示陌生状态再次确认处、红色点表示陌生向迷路转移处，迷路向陌生转移处紧挨着红色点故图上不标出。

这里以试验者1为代表，对试验过程中出现左顾右盼动作时发生的状态转移进行统计，主要涵盖陌生和迷路状态。统计结果如表5所示，其结果与图9(b)对应。

表5 试验一状态匹配统计Tab.5 Statistics of state matching of experiment 1

注:表示识别有误

按照上述方法可以得到4次试验中的统计数据，试验过程中全程跟踪观察试验者并用拍照的方式辅助记录其真实状态，将利用本文方法得到的匹配结果与真实记录进行对比得到匹配准确度的统计如表6所示。

从表6中可以看出，算法对熟悉向陌生状态的判断识别的准确度为100%；算法对迷路点的确认准确度高且稳定(平均90%左右)；算法对于陌生状态的再确认识别准确度较高(平均60%左右)。

4.2 讨 论

本文算法是利用微传感器数据识别特定环境下的行人特征动作，进而匹配行人所处状态。算法的准确度和普适性取决于两方面：行走导航状态FSM模型的可靠性；匹配算法的准确性；FSM模型的建立涉及认知、心理、习惯等不易定量分析的概念，本文采用问卷调查的方式获取了较为准确的建模基础资料，基本能够反映真实状态。匹配算法的准确性可从4.1试验结果部分得出，相对而言，算法对陌生状态的再确认相对于迷路识别准确度较低。实际情况下，迷路与陌生状态再确认均发生在陌生路段中，均是行人对导航路径不确认的表现，但迷路所代表的不确认程度相对更大。图10更直观地展示了试验者“不确定”点的分布及本算法的识别结果。

表6 匹配准确度Tab.6 The statistics of matching accuracy

图10 试验者“不确定”点分布Fig.10 Distribution map

由表6可知本试验中同一环境下，4名试验者表现出不确定次数分别为12、10、14、11，其分布如图10所示，图中带斜杠的点表示未识别出。由图10可知此环境下较容易给行人造成困惑的地点分布大致相同(实际环境中这些点多为岔道口或建筑物树荫遮蔽严重的地点)而个体差异主要体现在迷路点与陌生状态再确认点的分布上，更谨慎或者认知相对较差的行人迷路次数多一些，试验者1与试验者3对比明显，同一个“不确定”点前者多视为迷路点。而后者多视为陌生状态再确认点。此外，陌生路段通常在整个导航路段中占据绝大部分，所以不确定点的出现几率相对于其他点大得多，所以个体的差异性在本文模型中的迷路点与陌生状态再确认点的分布上表现得较为明显。

算法识别机制上，迷路有“停止行走”和“左顾右盼”两个识别特征，陌生状态再确认有“迈步频率不稳定”和“左顾右盼”两个识别特征。“停止行走”与“迈步频率不稳定”均是行走动作的特征，两者比较而言：“停止行走”由一个独立的瞬时变量(走、停)识别，“迈步是否平稳”则必须有一个参照变量(迈步频率标准差)，而该参照变量是一个过程变量(需要一定的时间才能确定)。“左顾右盼”是头部动作特征，与“停止行走”和“迈步频率不稳定”属于相对独立的两个系统，因此，当这两个特征分别与“左顾右盼”结合作为判断标准时，后者有可能出现超前或滞后，从而导致“陌生状态再确认”识别不准确。为改善算法，需要确定更为精准、可靠的识别特征或者进一步的判断机制。在更广泛的调查基础上建立更完善的行走导航状态FSM模型，建立自适应机制以降低个体差异的影响，增加模型的容错率，这是笔者下一步研究的方向之一。

5 结 论

本文提出的导航环境下行人有限状态转移模型及匹配算法，将处于导航环境下的行人动作及状态与环境认知联系起来，先通过调查建立状态分类规则，提取每类状态的典型动作和特征参数，再根据识别动作来判断所处状态。本文实现并验证所提出方法的可行性和有效性，试验结果表明匹配算法对于识别行人状态达到较高的准确度。在本文的研究中，仅对于典型的动作和状态进行了研究，更加精细的行为识别模型有待进一步深入研究。未来的研究工作中，将考虑将本文算法识别出的行人导航过程中导航状态转移结果作为基础，研究导航环境下行人容易出现陌生或迷路的地点，在这些地点上提供更精细化的路径导航服务，帮助提升导航成功率。

[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] 李清泉, 李秋萍, 方志祥.一种基于时空拥挤度的应急疏散路径优化方法[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] 于海璁, 陆锋.一种基于遗传算法的多模式多标准路径规划方法[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].大连理工大学学报, 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] 陈国良, 张言哲, 杨洲.一种基于手机传感器自相关分析的计步器实现方法[J].中国惯性技术学报, 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] 杨凯鹏, 张德珍, 崔皓.谷歌眼镜产品及其专利布局分析[J].中国发明与专利, 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] 周宝定, 李清泉, 毛庆洲, 等.用户行为感知辅助的室内行人定位[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] 孙承岳.结合近景和远景分析的行人状态跟踪[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].交通科技与经济, 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] 胡宏宇, 王殿海, 孙迪.基于视频跟踪方法的行人过街状态表达与分析[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] 胡清梅, 方卫宁, 郭北苑, 等.基于行人运动模型的人群疏散三维仿真[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] 林水强, 吴亚东, 余芳, 等.姿势序列有限状态机动作识别方法[J].计算机辅助设计与图形学学报, 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] 许睿.行人导航系统算法研究与应用实现[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.

方志祥，罗浩，李灵.有限状态自动机辅助的行人导航状态匹配算法[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