【智能系统】手机惯导与RFID的盲人导航系统设计与实现

第14卷第3期 智能系统学报 Vol.14 No.3 2019年5月 CAAI Transactions on Intelligent Systems May 2019 D0:10.11992/tis.201804058 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180628.0904.002.html 手机惯导与RFD的盲人导航系统设计与实现 郇战，陈学杰，梁久祯 (常州大学信息科学与工程学院，江苏常州213164) 摘要：为了解决目前盲人自主出行困难的问题，结合惯性导航与RFD技术各自的优势和特点，提出一种基于 手机惯性导航和RFID相结合的设计方案。该方案基于固定式RFID标签群，生成盲人路线图.将随身移动式 RFID读卡器和个人智能手机相结合，完成盲人定位、路径规划和导航提醒。实验结果表明：该系统能够给盲人 提供安全便捷的导航服务，有助于解决盲人自主出行问题。 关键词：RFID标签；惯性导航：室内定位；盲人导航：最短路径；Dijkstra算法；矩形限制区域；动态时间规整 中图分类号：TP391.7文献标志码：A 文章编号：1673-4785(2019)03-0491-09 中文引用格式：郇战，陈学杰，梁久祯.手机惯导与RFID的盲人导航系统设计与实现J.智能系统学报，2019,14(3)： 491-499 英文引用格式：HUAN Zhan,,CHEN Xuejie,,LIANG Jiuzhen.Design and implementation of blind-navigation system based on RFID and smartphones'inertial navigationJ CAAI transactions on intelligent systems,2019,14(3):491-499. Design and implementation of blind-navigation system based on RFID and smartphones'inertial navigation HUAN Zhan,CHEN Xuejie,LIANG Jiuzhen (School of Information Science and Engineering,Changzhou University,Changzhou 213164,China) Abstract:To help the blind travel independently and conveniently,a design scheme is proposed by combining inertial navigation and radio-frequency identification(RFID)technology with their respective advantages and characteristics. The scheme,which is based on fixed RFID tags,can automatically generate the best route for the blind.With the help of a portable RFID reader installed in personal smartphones,the scheme can accomplish positioning,route planning,and voice prompting.The experimental results show that the system can provide a safe and convenient navigation service for the blind,thus solving their independent-traveling problems. Keywords:RFID tags;inertial navigation;indoor positioning;blind navigation;shortest path;Dijkstra algorithm;re- stricted rectangle searching area;dynamic time warping 根据世界卫生组织数据，目前盲人数量已超用的导航设备极为有限，小范围应用的有BM与 过1100万。由于视力的缺失让他们出行十分困 卡内基梅隆大学合作开发的可做盲人眼睛的新 难。随着科学技术的不断发展，用于常人的导航 型APP(NavCog)。APP可以将盲人周边环境处理 设备越来越多，其中绝大多数的设备都是基于 成3D空间模型，通过人脸扫描功能告诉盲人身 GPS的卫星导航)，由于GPS的民用室外精度在 边人的身份以及情绪，依靠蓝牙设备（蓝牙灯 10m以上，不能满足盲人对导航精度的要求，而塔)以及超声波提供准确的定位信息，通过语音 且在室内无法使用。目前，盲人自主出行可以使 和震动两种方式为盲人提供信息并进行导航。但 收稿日期：2018-04-26.网络出版日期：2018-06-28. 是，由于需要布设大量蓝牙设备，造价较高而不 基金项目：国家自然科学基金项目(61772248)：国家社会科学 基金重点项目(16AGL011). 能大范围使用。 通信作者：郇战.E-mail:hzh@cczu.edu.cn. 崔金琦等设计出基于RFID的校园导航系

DOI: 10.11992/tis.201804058 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180628.0904.002.html 手机惯导与 RFID 的盲人导航系统设计与实现 郇战，陈学杰，梁久祯 （常州大学 信息科学与工程学院，江苏 常州 213164） 摘 要：为了解决目前盲人自主出行困难的问题，结合惯性导航与 RFID 技术各自的优势和特点，提出一种基于 手机惯性导航和 RFID 相结合的设计方案。该方案基于固定式 RFID 标签群，生成盲人路线图，将随身移动式 RFID 读卡器和个人智能手机相结合，完成盲人定位、路径规划和导航提醒。实验结果表明：该系统能够给盲人 提供安全便捷的导航服务，有助于解决盲人自主出行问题。 关键词：RFID 标签；惯性导航；室内定位；盲人导航；最短路径；Dijkstra 算法；矩形限制区域；动态时间规整 中图分类号：TP391.7 文献标志码：A 文章编号：1673−4785(2019)03−0491−09 中文引用格式：郇战, 陈学杰, 梁久祯. 手机惯导与 RFID 的盲人导航系统设计与实现[J]. 智能系统学报, 2019, 14(3): 491–499. 英文引用格式：HUAN Zhan, CHEN Xuejie, LIANG Jiuzhen. Design and implementation of blind-navigation system based on RFID and smartphones’ inertial navigation[J]. CAAI transactions on intelligent systems, 2019, 14(3): 491–499. Design and implementation of blind-navigation system based on RFID and smartphones’ inertial navigation HUAN Zhan，CHEN Xuejie，LIANG Jiuzhen (School of Information Science and Engineering, Changzhou University, Changzhou 213164, China) Abstract: To help the blind travel independently and conveniently, a design scheme is proposed by combining inertial navigation and radio-frequency identification (RFID) technology with their respective advantages and characteristics. The scheme, which is based on fixed RFID tags, can automatically generate the best route for the blind. With the help of a portable RFID reader installed in personal smartphones, the scheme can accomplish positioning, route planning, and voice prompting. The experimental results show that the system can provide a safe and convenient navigation service for the blind, thus solving their independent-traveling problems. Keywords: RFID tags; inertial navigation; indoor positioning; blind navigation; shortest path; Dijkstra algorithm; re￾stricted rectangle searching area; dynamic time warping 根据世界卫生组织数据，目前盲人数量已超 过 1 100 万。由于视力的缺失让他们出行十分困 难。随着科学技术的不断发展，用于常人的导航 设备越来越多，其中绝大多数的设备都是基于 GPS 的卫星导航[1] ，由于 GPS 的民用室外精度在 10 m 以上，不能满足盲人对导航精度的要求，而 且在室内无法使用。目前，盲人自主出行可以使 用的导航设备极为有限，小范围应用的有 IBM 与 卡内基梅隆大学合作开发的可做盲人眼睛的新 型 APP(NavCog)。APP 可以将盲人周边环境处理 成 3D 空间模型，通过人脸扫描功能告诉盲人身 边人的身份以及情绪，依靠蓝牙设备 (蓝牙灯 塔) 以及超声波提供准确的定位信息，通过语音 和震动两种方式为盲人提供信息并进行导航。但 是，由于需要布设大量蓝牙设备，造价较高而不 能大范围使用。 崔金琦等[2]设计出基于 RFID的校园导航系 收稿日期：2018−04−26. 网络出版日期：2018−06−28. 基金项目：国家自然科学基金项目 (61772248)；国家社会科学 基金重点项目 (16AGL011). 通信作者：郇战. E-mail: hzh@cczu.edu.cn. 第 14 卷第 3 期 智 能 系 统 学 报 Vol.14 No.3 2019 年 5 月 CAAI Transactions on Intelligent Systems May 2019

·492· 智能系统学报 第14卷 统，并且在南京大学校园得以应用。但该系统是 数据库完成定标信息的录入；当所有定标信息都 为一般人设计的，如果直接移植到盲人导航系 录入完成后系统进人路径信息录入。路径绘制具 统，就需要在路径网络中任意相连的两个结点之 体流程如图2所示。 间的RFID标签采用连续的标签码，所需RFID数 (开始 量大，而且实施困难。 路径绘制N Y导航服务 针对上述问题，提出一种基于智能手机惯性 路径存金 导航与RFID标签B的盲人导航系统6。该系统 RFID标签铺设 语音输入起点和 终点、语音识别 以惯性导航为主要导航方式，为了避免惯性导航 数据采集层读取 定 RFID标签D信息 的累积误差问题，采用RFD标签作为定标点，用 导航服务层规划导 航路径并开始导航 于位置信息校准，从而解决了惯性导航累计误差 数据处理层录 人定标点信息 点信息 数据采集层读取定 和单纯RFID导航标签量巨大的问题，可以达到 标点RFID标签信息 盲人导航的要求。 结束录人少 航 数据处理层将定标 点信息与规划导航 1系统设计 选定路径起点和 路径信息进行匹配 终点定标点 1.1RFID选型 路 导航服务层实时 数据处理层读取定 给出语音提示导 如果RFID识别作用距离过长，盲人手中的 标点信息，确定并 航信息，直至导 RFID读写器在较远的距离很远就能扫描到 录入路径信息 信息录 航下一个定标点 1 RFD标签，会导致导航纠偏距离过长，致使系统 结束录入 导航结束 误差增大；如果识别作用距离过短，就会使RFD 读写器发现标签的距离变小，必须加大RFD标签 结束 的铺设密度，增加其部署数量，因此必须要选择识 图1 系统总体流程图 别距离适中的RFD标签。系统采用PM13.56MHz Fig.1 System overall flow chart 的高频RFD技术，它能够在距离1m以内（可以 (开始 通过天线适当调整)，运动速度在4m/s以内进行 保用双铺RFID方式 进入路径 识别，读写一个标签的平均耗时在2ms以内，可 信息录人 布局定标点 以满足盲人导航的一般要求。 进人定标点 选择路径起点 1.2系统结构设计 信息录人 和终点定标点 系统分为4层结构：数据采集层、数据传输 采用GPS定位机获 连接数据库， 层、数据处理层和导航服务层。 取梢准的经纬度坐标 读取定标点 标识信息 数据采集层通过读卡器读取RFID标签的 数据采集层读取 D信息；数据传输层通过蓝牙模块将其交付给数 RFID标签的D信息 连接数据库， 录入路径信息 据处理层：数据处理层连接数据库根据D进行查 连接数据库录人 询，并且将查询到的数据交付给导航服务层；导 定标点相关信息 录人结球N 航服务层先进行路径规划再将获得的数据进行匹 Y 配并且通过语音给出导航提示。 结束 根据上述分析得出：系统分为路径录入以及 图2路径绘制流程图 导航服务两大模块，具体流程如图1所示。 Fig.2 Path drawing flow chart 1.3路径绘制流程设计 1.4 导航流程设计 系统路径绘制的基本流程为：首先在事先规 系统导航的基本流程为：盲人首先需要使用 划的路径节点采用双铺RFID标签方式布局定标 带有内置天线的导盲杖O扫描到RFID标签以确 点，再采用GPS定位机获取定标点准确的经纬度 定当前位置，之后通过语音选择目的地。随后系 信息，由数据采集层通过读卡器读取RFID标签 统进行路径规划，进而进行惯性导航6，并且实 的ID信息，数据传输层通过蓝牙串口模块将 时进行位置校准和语音提示，直至到达目的地。 D信息传给数据处理层，最后由数据处理层连接 具体导航流程如图3所示

统，并且在南京大学校园得以应用。但该系统是 为一般人设计的，如果直接移植到盲人导航系 统，就需要在路径网络中任意相连的两个结点之 间的 RFID 标签采用连续的标签码，所需 RFID 数 量大，而且实施困难。 针对上述问题，提出一种基于智能手机惯性 导航与 RFID 标签[3-5]的盲人导航系统[6-9]。该系统 以惯性导航为主要导航方式，为了避免惯性导航 的累积误差问题，采用 RFID 标签作为定标点，用 于位置信息校准，从而解决了惯性导航累计误差 和单纯 RFID 导航标签量巨大的问题，可以达到 盲人导航的要求。 1 系统设计 1.1 RFID 选型 如果 RFID 识别作用距离过长，盲人手中的 RFID 读写器在较远的距离很远就能扫描 到 RFID 标签，会导致导航纠偏距离过长，致使系统 误差增大；如果识别作用距离过短，就会使 RFID 读写器发现标签的距离变小，必须加大 RFID 标签 的铺设密度，增加其部署数量，因此必须要选择识 别距离适中的 RFID 标签。系统采用 PJM 13.56 MHz 的高频 RFID 技术，它能够在距离 1 m 以内 (可以 通过天线适当调整)，运动速度在 4 m/s 以内进行 识别，读写一个标签的平均耗时在 2 ms 以内，可 以满足盲人导航的一般要求。 1.2 系统结构设计 系统分为 4 层结构：数据采集层、数据传输 层、数据处理层和导航服务层。 数据采集层通过读卡器读取 RFID 标签的 ID 信息；数据传输层通过蓝牙模块将其交付给数 据处理层；数据处理层连接数据库根据 ID 进行查 询，并且将查询到的数据交付给导航服务层；导 航服务层先进行路径规划再将获得的数据进行匹 配并且通过语音给出导航提示。 根据上述分析得出：系统分为路径录入以及 导航服务两大模块，具体流程如图 1 所示。 1.3 路径绘制流程设计 系统路径绘制的基本流程为：首先在事先规 划的路径节点采用双铺 RFID 标签方式布局定标 点，再采用 GPS 定位机获取定标点准确的经纬度 信息，由数据采集层通过读卡器读取 RFID 标签 的 ID 信息，数据传输层通过蓝牙串口模块将 ID 信息传给数据处理层，最后由数据处理层连接 数据库完成定标信息的录入；当所有定标信息都 录入完成后系统进入路径信息录入。路径绘制具 体流程如图 2 所示。 开始 路径存在 RFID 标签铺设 数据处理层录 入定标点信息 结束录入 选定路径起点和 终点定标点 数据处理层读取定 标点信息，确定并 录入路径信息 结束录入 语音输入起点和 终点、语音识别 导航服务层规划导 航路径并开始导航 数据采集层读取定 标点 RFID 标签信息 数据处理层将定标 点信息与规划导航 路径信息进行匹配 导航服务层实时 给出语音提示导 航信息，直至导 航下一个定标点 导航结束 结束 路径绘制 导航服务 定 标 点 信 息 录 入 路 径 信 息 录 入 盲 人 导 航 实 现 Y N Y N Y N N Y 数据采集层读取 RFID 标签 ID 信息 图 1 系统总体流程图 Fig. 1 System overall flow chart 开始 采用双铺 RFID 方式 布局定标点 采用 GPS 定位机获 取精准的经纬度坐标 数据采集层读取 RFID 标签的 ID 信息 连接数据库录入 定标点相关信息 录入结束 进入路径 信息录入 选择路径起点 和终点定标点 连接数据库， 读取定标点 标识信息 连接数据库， 录入路径信息 录入结束 Y 结束 Y N N 进入定标点 信息录入 图 2 路径绘制流程图 Fig. 2 Path drawing flow chart 1.4 导航流程设计 系统导航的基本流程为：盲人首先需要使用 带有内置天线的导盲杖[10]扫描到 RFID 标签以确 定当前位置，之后通过语音选择目的地。随后系 统进行路径规划，进而进行惯性导航[11-16] ，并且实 时进行位置校准和语音提示，直至到达目的地。 具体导航流程如图 3 所示。 ·492· 智 能 系 统 学 报 第 14 卷

第3期 郇战，等：手机惯导与RFD的盲人导航系统设计与实现 ·493· 确定起始位置 语音选择日的地 2系统实现 系统规划到下移除 2.1数据采集层实现 RFID路径 RFID标签铺设：最常见的RFID铺设方法有 单排铺设和双排铺设方法，如图4、图5所示。 语音和震动提示 惯性导航 感应区域 判断走偏 语音和震 标签 动提示 判断到达 下一定标点 语音和展 Y 图4单排铺设 动提示 Fig.4 Single row laying 偏离定标点 NI 到达目的地 感应区域 感应区域 RFID标签 区 RFID标签 导航结束 图3导航流程图 Fig.3 Navigational flow chart 图5双排铺设 Fig.5 Double row laying 1.5数据库设计 单排铺设方法感应半径较小，盲人使用导盲 系统采用SQLite轻型数据库来存储路径信 杖较难找到，并且相对于RFID具体方位具有不 息和定标点信息，为此设计两个数据表，分别是 确定性，所以系统采用双排铺设方法。双排铺设 路径信息表(Route Info)以及定标点信息表(Lable 方法感应面积较大，盲人使用导盲杖较容易找到。 Info),分别存储每条路径的信息和定标点信息，具 测量发现，手机惯性导航系统的误差范围在 体包含的数据项分别如表1、表2所示。 2%以内，即经过20m距离后产生的偏差在±0.4m 表1路径信息表(Route Info) 以内。实际应用中，RFD的可靠感应距离在0.5m Table 1 Path information table(Route Info) 左右（可以通过天线调整好），设双排铺设的标签 列含义 列名 类型 约束 间距为0.75m时，正面可感应的宽度为1.75m 路径唯一标识 Roadld int 主键 左右，两标签重合感应区域宽度为0.25m。当盲 路径起点定标点Id LableFrist varchar(20) 非空 人同时读取到两张RFID卡时，可以将惯性导航 路径终点定标点Id LableEnd varchar(20) 非空 的累计误差减小到±0.125m以内，若再经过20m 方向 非空 的距离，累积误差不会超过±0.525m(双排铺设时 Direction double 正面可感应的宽度为1.75m),可以正确找到下一 距离 Distance double 非空 组标签。 权重 Weight double 非空 数据采集方法：采集RFD数据时，使用内置 表2定标点信息表(Label_Info) 天线的导盲杖作为数据采集工具。RFID读写器 Table 2 Fixed punctuation information table 通过天线与RFID电子标签进行无线通信，实现 列含义 列名 类型 约束 对标签识别码和内存数据的读出或写入操作。 定标点唯一标识 Lableld varchar(20) 主键 2.2通信传输层实现 第一个RFID号 系统主要有两个方向的数据传输，涉及两种 FirstRFID varchar(20) 非空 第二个RFID号 数据通信格式：首先是从智能手机到读写模块，在 SecondRFID varchar(20) 非空 定标点经度 Longitude double 非空 这一过程主要是由蓝牙串口模块发送读卡指令给读 定标点纬度 写模块，系统中使用的读卡命令是0507FFF001006A50: Latitude double 非空 定标点高度 非空 其次是从读写器到蓝牙串口模块，在这一过程主 Height double 要就是根据读卡器所读取到的相关信息返回响应 定标点名称 LableName varchar(20) 非空 的信息

确定起始位置， 语音选择目的地 系统规划到下移除 RFID 路径 语音和震动提示 惯性导航 判断走偏 Y 偏离定标点 N 语音和震 动提示 Y 到达目的地 N 导航结束 Y N 判断到达 下一定标点 语音和震 动提示 N Y 图 3 导航流程图 Fig. 3 Navigational flow chart 1.5 数据库设计 系统采用 SQLite 轻型数据库来存储路径信 息和定标点信息，为此设计两个数据表，分别是 路径信息表 (Route_Info) 以及定标点信息表 (Lable_ Info)，分别存储每条路径的信息和定标点信息，具 体包含的数据项分别如表 1、表 2 所示。 表 1 路径信息表 (Route_Info) Table 1 Path information table(Route_Info) 列含义 列名 类型 约束 路径唯一标识 _RoadId int 主键 路径起点定标点 Id LableFrist varchar(20) 非空 路径终点定标点 Id LableEnd varchar(20) 非空 方向 Direction double 非空 距离 Distance double 非空 权重 Weight double 非空 表 2 定标点信息表 (Label_Info) Table 2 Fixed punctuation information table 列含义 列名 类型 约束 定标点唯一标识 LableId varchar(20) 主键 第一个 RFID 号 FirstRFID varchar(20) 非空 第二个 RFID 号 SecondRFID varchar(20) 非空 定标点经度 Longitude double 非空 定标点纬度 Latitude double 非空 定标点高度 Height double 非空 定标点名称 LableName varchar(20) 非空 2 系统实现 2.1 数据采集层实现 RFID 标签铺设：最常见的 RFID 铺设方法有 单排铺设和双排铺设方法，如图 4、图 5 所示。 标签 感应区域 图 4 单排铺设 Fig. 4 Single row laying 感应区域 RFID 标签 感应区域 RFID 标签 重 合 区 域 图 5 双排铺设 Fig. 5 Double row laying 单排铺设方法感应半径较小，盲人使用导盲 杖较难找到，并且相对于 RFID 具体方位具有不 确定性，所以系统采用双排铺设方法。双排铺设 方法感应面积较大，盲人使用导盲杖较容易找到。 测量发现，手机惯性导航系统的误差范围在 ±2% 以内，即经过 20 m 距离后产生的偏差在±0.4 m 以内。实际应用中，RFID 的可靠感应距离在 0.5 m 左右 (可以通过天线调整好)，设双排铺设的标签 间距为 0.75 m 时，正面可感应的宽度为 1.75 m 左右，两标签重合感应区域宽度为 0.25 m。当盲 人同时读取到两张 RFID 卡时，可以将惯性导航 的累计误差减小到±0.125 m 以内，若再经过 20 m 的距离，累积误差不会超过±0.525 m(双排铺设时 正面可感应的宽度为 1.75 m)，可以正确找到下一 组标签。 数据采集方法：采集 RFID 数据时，使用内置 天线的导盲杖作为数据采集工具。RFID 读写器 通过天线与 RFID 电子标签进行无线通信，实现 对标签识别码和内存数据的读出或写入操作。 2.2 通信传输层实现 系统主要有两个方向的数据传输，涉及两种 数据通信格式：首先是从智能手机到读写模块，在 这一过程主要是由蓝牙串口模块发送读卡指令给读 写模块，系统中使用的读卡命令是 0507FFF001006A50； 其次是从读写器到蓝牙串口模块，在这一过程主 要就是根据读卡器所读取到的相关信息返回响应 的信息。 第 3 期 郇战，等：手机惯导与 RFID 的盲人导航系统设计与实现 ·493·

·494· 智能系统学报 第14卷 2.3数据处理层实现 在模型建立时，会采用M5模型树，其构造方 在数据处理层主要涉及两个方面的工作：一 法是：假设有样本集T,先计算T的标准差sd(T), 是信息录入，二是信息查询。 之后依据不同的sd(T)将T进行划分，如果T的 信息录人：首先是录入各定标点信息，其次是 值波动很小或者T本身包含的实例就少也不需要 对路径信息的录入。 对T进行进一步的划分。第i个测试将样本集T 信息查询：在系统中涉及的数据查询主要是 划分成子集T,并对该子集求标准差sd(T),并且 定标点以及路径信息，系统采取基于SQLite的数 按照式(1)计算期望误差的减少量(SDR)。 据查询方式予以实现。盲人进入导航系统，系统 sD=dn-∑H sd(T) (1) 打开读卡器，根据读卡器串口模块返回的值进行 相关信息的查询。具体流程如图6所示。 在计算完样本所有的可能标准差之后，在其 中选择期望误差的减少量（所有计算的误差减少 开始 量中最大的)作为最终期望误差的减少量。最后 对每一个所划分出的子集建立回归模型，按照式 启动读卡器 (2)生成回归等式LM(T)。 读卡器读取RFID 标签值 LM(T)=∑kxC) (2) 读取成功 N 式中：C为样本中的属性值；N为属性的个数；k 为属性相关系数。 数据库无此卡，读 Y 取下一张RFD卡 通过RFD标签 模型建立具体步骤如下： 值进行数据匹配 1)标记状态：盲人在监护人的陪同下采集不 同行走状态下的加速度数据，系统会给不同状态 N 匹配成功 标记相对应的值。在平时出行过程中盲人一般产 y 生4种运动状态数据，即噪声、静止、步行、上下 返回根据RFD标签值检索出对应的 经纬度坐标、方向距离和相对位置 楼梯，系统分别给它们标记-10、0、10、20。 2)数据预处理：为了达到对加速度数据去噪 结束 的目的，系统采用10点的平滑滤波对数据进行预 图6信息查询流程图 处理。 Fig.6 Information query flow chart 3)特征提取：提取波峰均值、波峰方差、单步 2.4导航服务层实现 间隔均值、单步间隔方差以及波峰之间的时间间 2.4.1惯性导航 隔方差。 徐向军提出一种惯性测量与航迹推算的室 4)模型建立：利用M5模型树根据所选取的 特征进行有监督的机器学习，最后输出分类模型。 内定位方法，但其方法过于复杂，不容易和智能 在实时导航时，系统先要采集盲人正常行走 手机相结合。周婧等提出一种基于惯性导航的 的步长，然后根据步数、步长以及方向来确定盲 平面航迹推算方案，该方案需要携带两个陀螺仪 人的位置，在计步时会用到动态时间规整算法 和一部智能手机，如果用于盲人导航肯定会增加 (dynamic time warping,DTW) 硬件成本；而且该方案虽然可以解决平面轨迹的 DTW是一种衡量两个时间序列之间相似度 推算问题，但是却无法推算上下运动的轨迹，因 的算法，其算法思想是：令要计算相似度的两个 此该方案无法用于盲人导航。徐鼎等提出一种 时间列为X和Y,长度分别为X和Y;把路径规 基于Android端的惯性导航算法，虽然其只需要 整成W=w,w2,…,wg。Max(X,YD≤K≤X+Y, 一部Android手机，但是该方法只能推算平面轨w的形式为（亿，），式中i、j分别为X和Y中的坐 迹，也不适用于盲人导航。 标，规整路径W必须从w,=(1,1)开始到 在综合多方面考虑后，系统将文献[20]提出 wm=X,YD结束。另外，W中的(，)的i、j必 的M5DTW计步方法和文献[19]的惯导算法相结 须是单调的，即w=(位，，wk1=(,),i≤≤i+1, 合，完成该系统惯性导航算法的设计。该算法分 j≤了≤j+1;最后需要得到最短的一个规整路径， 为模型建立和实时导航两部分。 DisW=觉DsIw,W,系统中Disw,w)为欧

2.3 数据处理层实现 在数据处理层主要涉及两个方面的工作：一 是信息录入，二是信息查询。 信息录入：首先是录入各定标点信息，其次是 对路径信息的录入。 信息查询：在系统中涉及的数据查询主要是 定标点以及路径信息，系统采取基于 SQLite 的数 据查询方式予以实现。盲人进入导航系统，系统 打开读卡器，根据读卡器串口模块返回的值进行 相关信息的查询。具体流程如图 6 所示。 Y 开始 启动读卡器 读卡器读取 RFID 标签值 读取成功 N 通过 RFID 标签 值进行数据匹配 匹配成功 返回根据 RFID 标签值检索出对应的 经纬度坐标、方向距离和相对位置 结束 数据库无此卡，读 取下一张 RFID 卡 N Y 图 6 信息查询流程图 Fig. 6 Information query flow chart 2.4 导航服务层实现 2.4.1 惯性导航 徐向军[17]提出一种惯性测量与航迹推算的室 内定位方法，但其方法过于复杂，不容易和智能 手机相结合。周婧等[18]提出一种基于惯性导航的 平面航迹推算方案，该方案需要携带两个陀螺仪 和一部智能手机，如果用于盲人导航肯定会增加 硬件成本；而且该方案虽然可以解决平面轨迹的 推算问题，但是却无法推算上下运动的轨迹，因 此该方案无法用于盲人导航。徐鼎等[19]提出一种 基于 Android 端的惯性导航算法，虽然其只需要 一部 Android 手机，但是该方法只能推算平面轨 迹，也不适用于盲人导航。 在综合多方面考虑后，系统将文献[20]提出 的 M5_DTW 计步方法和文献[19]的惯导算法相结 合，完成该系统惯性导航算法的设计。该算法分 为模型建立和实时导航两部分。 T T sd(T) sd(T) i Tj sd(Ti) 在模型建立时，会采用 M5 模型树，其构造方 法是：假设有样本集 ，先计算 的标准差 ， 之后依据不同的 将 T 进行划分，如果 T 的 值波动很小或者 T 本身包含的实例就少也不需要 对 T 进行进一步的划分。第 个测试将样本集 T 划分成子集 ，并对该子集求标准差 ，并且 按照式 (1) 计算期望误差的减少量 (SDR)。 SDR = sd(T)− ∑ i |Ti | |T| ×sd(Ti) (1) LM(Ti) 在计算完样本所有的可能标准差之后，在其 中选择期望误差的减少量 (所有计算的误差减少 量中最大的) 作为最终期望误差的减少量。最后 对每一个所划分出的子集建立回归模型，按照式 (2) 生成回归等式 。 LM(Ti) = ∑N i=1 (ki ×Ci) (2) 式中： C 为样本中的属性值； N 为属性的个数； k 为属性相关系数。 模型建立具体步骤如下： 1) 标记状态：盲人在监护人的陪同下采集不 同行走状态下的加速度数据，系统会给不同状态 标记相对应的值。在平时出行过程中盲人一般产 生 4 种运动状态数据，即噪声、静止、步行、上下 楼梯，系统分别给它们标记–10、0、10、20。 2) 数据预处理：为了达到对加速度数据去噪 的目的，系统采用 10 点的平滑滤波对数据进行预 处理。 3) 特征提取：提取波峰均值、波峰方差、单步 间隔均值、单步间隔方差以及波峰之间的时间间 隔方差。 4) 模型建立：利用 M5 模型树根据所选取的 特征进行有监督的机器学习，最后输出分类模型。 在实时导航时，系统先要采集盲人正常行走 的步长，然后根据步数、步长以及方向来确定盲 人的位置，在计步时会用到动态时间规整算法 (dynamic time warping，DTW)。 |X| |Y| W = w1,w2,··· ,wk Max(|X|,|Y|) ⩽ K ⩽ |X|+|Y| wk (i, j) i j X Y W w1 = (1,1) wk = (|X|,|Y|) W (i, j) i j wk = (i, j),wk+1 = (i ′ , j ′ ),i ⩽ i ′ ⩽ i+1, j ⩽ j ′ ⩽ j+1 Dist(W) = k∑=K k=1 Dist(wki,wk j) Dist(wki,wk j) DTW 是一种衡量两个时间序列之间相似度 的算法，其算法思想是：令要计算相似度的两个 时间列为 X 和 Y，长度分别为 和 ；把路径规 整 成 。 ， 的形式为 ，式中 、 分别为 和 中的坐 标，规整路径 必 须 从 开始到 结束。另外， 中的 的 、 必 须是单调的，即 ；最后需要得到最短的一个规整路径， ，系统中 为欧 ·494· 智 能 系 统 学 报 第 14 卷

第3期 郇战，等：手机惯导与RFD的盲人导航系统设计与实现 ·495· 式距离；在实现DTW算法时采用动态规划的思 标为S(x,y,终点坐标为D(xa,ya)由此得椭圆中 想，其核心见式(3)： 心点坐标为(a,b),其中，a=(x,+x)/2, D(i,j)=Dist(i,)+min[D(i-1,), b=y,+y)/2。P为长轴与x、y轴正方向的夹角， (3) Di,i-1),2Di-1,j-1)] p=arctan(y,-ya/x,-xa》。椭圆长轴为2A=0×Ea; 式中Di,)表示长度为i和j的两个时间序列之 椭圆短轴为B=√A2-(Oa-y)+(4-x))/4,由此 间的规整路径距离。 可得椭圆的方程为 实时导航具体步骤如下： [K-a)cos+0-b创sin9+ 1)步长提取：盲人在监护人陪同下采用多次 A2 [-(x-a)sin+(y-b)coso2 (4) 采样取平均的方法采集盲人在正常行走下的步长。 二1 B 2)数据采集：智能手机采集实时数据，由于 再对椭圆方程式(4)分别对x和y求偏导数， 统计步数一般需要在实时的状态，采用时间窗口 得到x和y的极值分别为 的方式对数据进行采集，每次统计一个时间窗口 的步数以及该时间窗口内的方向。 Xm=aA2cos2+B'sin' (5) 3)数据预处理：与训练模型过程一样，采用 ym=b±√A2sin2p+B2cos2p (6) 10点平滑滤波对数据进行预处理。 由式(2)、式(3)可以分别得到x和y的最小 4)特征提取与分类输出：提取波峰均值、波 值xn、ym和最大值xax、yma,由此构成椭圆的最 峰方差、单步间隔均值、单步间隔方差以及波峰 小外接矩形，如图7所示。 之间的时间间隔方差，将这些特征输入已经建立 (Xmin:ym) (y) 好的M5分类器中，得到所属分类。 5)计步：使用DTW算法，选择与之相似度最 高的状态，如果不是噪声则记为一步，并且记录 该步的状态。 P sd 6)位置推算：结合步幅的属性、步长以及方 E sd 向推算出实时位置。 2.4.2矩形限制区域Dijkstra算法的描述 路径规划作为导航服务层的核心环节。系统 将路径规划问题抽象成从起点到终点的单源最短 (Xmin ymin) (化ms,ya) 路径问题，为此系统采用常用的矩形限制区域的 图7椭圆及矩形限制搜索区域 Dijkstra算法解决这一问题。首先，由录入的定标 Fig.7 Ellipse and rectangle-restricted search area 点以及路径信息构成带权值的有向图G(V,E),其 系统利用矩形限制搜索区域算法求起点和终 中定标点视为图中的顶点V,路径视为边，并且路 点间最短路径的算法步骤如下： 径的权重(Weight)设置为对应边的权值W;其次， 1)初始时，C只包含起点，即C={S},v的距 在相应的矩形区域内使用Dijkstra算法产生该带 离为0。U包含除S外的其他顶点，即U={其余顶 权值有向图从指定起点到终点权值最小的路径； 点}。若S与U中顶点u有边，则<4，>正常有权 最后，实时导航并给出语音提示。 值W;若u不是S的邻接点，则<u,S>权值为o。 针对经典Dijkstra算法在搜索过程中存在缺 2)根据起点S(x,y)和终点Dxu,ya),计算A、 乏导航方向性以及大量冗余计算等诸多问题，文 B、a、b、P,构造椭圆方程，确定椭圆区域。 献[21]-[22]提出矩形限制搜索区域算法，其基本 3)根据已经确定的椭圆方程计算xn、xmax 思想是：首先，以导航的起点(S)和终点(D)为焦 ym、yx,确定最后搜索的矩形区域。 点，选取合适的椭圆区域；其次，根据所确定的椭 4)从U中选取一个在矩形区域内且权值最 圆区域求出最小包含矩形，并以此为限制区域。 小的顶点k,把k加入C中（在初始状态下权值按 在求限制区域时，最为关键的就是要确定椭圆长 照式(7)计算)。 轴的长度，由文献[17]可知，定义比例系数 5)以k为新考虑的中间点，修改U中各顶点 O=Pa/Ed,其中Pa为起点和终点的最短路径， 的权值；若从起点S到顶点u的权值（经过顶点 E为起点和终点的欧氏距离，通过统计分析方法 )比原来权值（不经过顶点k)小，则修改顶点 得到置信水平达到95%的比例系数θ；设起点坐 u的权值

式距离；在实现 DTW 算法时采用动态规划的思 想，其核心见式 (3)： D(i, j) = Dist(i, j)+min[D(i−1, j), D(i, j−1),2D(i−1, j−1)] (3) 式中 D(i, j) 表示长度为 i 和 j 的两个时间序列之 间的规整路径距离。 实时导航具体步骤如下： 1) 步长提取：盲人在监护人陪同下采用多次 采样取平均的方法采集盲人在正常行走下的步长。 2) 数据采集：智能手机采集实时数据，由于 统计步数一般需要在实时的状态，采用时间窗口 的方式对数据进行采集，每次统计一个时间窗口 的步数以及该时间窗口内的方向。 3) 数据预处理：与训练模型过程一样，采用 10 点平滑滤波对数据进行预处理。 4) 特征提取与分类输出：提取波峰均值、波 峰方差、单步间隔均值、单步间隔方差以及波峰 之间的时间间隔方差，将这些特征输入已经建立 好的 M5 分类器中，得到所属分类。 5) 计步：使用 DTW 算法，选择与之相似度最 高的状态，如果不是噪声则记为一步，并且记录 该步的状态。 6) 位置推算：结合步幅的属性、步长以及方 向推算出实时位置。 2.4.2 矩形限制区域 Dijkstra 算法的描述 路径规划作为导航服务层的核心环节。系统 将路径规划问题抽象成从起点到终点的单源最短 路径问题，为此系统采用常用的矩形限制区域的 Dijkstra 算法解决这一问题。首先，由录入的定标 点以及路径信息构成带权值的有向图 G(V, E)，其 中定标点视为图中的顶点 V，路径视为边，并且路 径的权重 (Weight) 设置为对应边的权值 W；其次， 在相应的矩形区域内使用 Dijkstra 算法产生该带 权值有向图从指定起点到终点权值最小的路径； 最后，实时导航并给出语音提示。 θ = Psd/Esd Psd Esd θ 针对经典 Dijkstra 算法在搜索过程中存在缺 乏导航方向性以及大量冗余计算等诸多问题，文 献[21]-[22]提出矩形限制搜索区域算法，其基本 思想是：首先，以导航的起点 (S) 和终点 (D) 为焦 点，选取合适的椭圆区域；其次，根据所确定的椭 圆区域求出最小包含矩形，并以此为限制区域。 在求限制区域时，最为关键的就是要确定椭圆长 轴的长度，由文献 [ 1 7 ] 可知，定义比例系数 ，其中 为起点和终点的最短路径， 为起点和终点的欧氏距离，通过统计分析方法 得到置信水平达到 95% 的比例系数 ；设起点坐 S (xs , ys) D(xd, yd) (a,b) a = (xs + xd)/2 b = (ys +yd)/2 φ φ = arctan((ys −yd)/(xs − xd)) 2A = θ× Esd B = √ A2 −((yd −ys) 2 +(xd − xs) 2 )/4 标为 ，终点坐标为 由此得椭圆中 心点坐标为 ，其中， ， 。 为长轴与 x、y 轴正方向的夹角， 。椭圆长轴为 ； 椭圆短轴为 ，由此 可得椭圆的方程为 [ (x−a) cos φ+(y−b)sinφ ]2 A2 + [ −(x−a)sin φ+(y−b) cos φ ]2 B2 =1 (4) 再对椭圆方程式 (4) 分别对 x 和 y 求偏导数， 得到 x 和 y 的极值分别为 xm = a± √ A2cos2φ+ B2sin2 φ (5) ym = b± √ A2sin2 φ+ B2cos2φ (6) xmin ymin xmax ymax 由式 (2)、式 (3) 可以分别得到 x 和 y 的最小 值 、 和最大值 、 ，由此构成椭圆的最 小外接矩形，如图 7 所示。 (xmin, ymax) (xmax, ymax) (xmin, ymin) (xmax, ymin) D E_sd P_sd S 图 7 椭圆及矩形限制搜索区域 Fig. 7 Ellipse and rectangle-restricted search area 系统利用矩形限制搜索区域算法求起点和终 点间最短路径的算法步骤如下： 1) 初始时，C 只包含起点，即 C＝{S}，v 的距 离为 0。U 包含除 S 外的其他顶点，即 U={其余顶 点}。若 S 与 U 中顶点 u 有边，则<u, S>正常有权 值 W；若 u 不是 S 的邻接点，则<u, S >权值为∞。 S (xs , ys) D(xd, yd) A B a b φ 2) 根据起点 和终点 ，计算 、 、 、 、 ，构造椭圆方程，确定椭圆区域。 xmin、xmax、 ymin、ymax 3) 根据已经确定的椭圆方程计算 ，确定最后搜索的矩形区域 。 4) 从 U 中选取一个在矩形区域内且权值最 小的顶点 k，把 k 加入 C 中 (在初始状态下权值按 照式 (7) 计算)。 5) 以 k 为新考虑的中间点，修改 U 中各顶点 的权值；若从起点 S 到顶点 u 的权值 (经过顶点 k) 比原来权值 (不经过顶点 k) 小，则修改顶点 u 的权值。 第 3 期 郇战，等：手机惯导与 RFID 的盲人导航系统设计与实现 ·495·