根据世界卫生组织数据，目前盲人数量已超过1 100万。由于视力的缺失让他们出行十分困难。随着科学技术的不断发展，用于常人的导航设备越来越多，其中绝大多数的设备都是基于GPS的卫星导航^[1]，由于GPS的民用室外精度在10 m以上，不能满足盲人对导航精度的要求，而且在室内无法使用。目前，盲人自主出行可以使用的导航设备极为有限，小范围应用的有IBM与卡内基梅隆大学合作开发的可做盲人眼睛的新型APP(NavCog)。APP可以将盲人周边环境处理成3D空间模型，通过人脸扫描功能告诉盲人身边人的身份以及情绪，依靠蓝牙设备(蓝牙灯塔)以及超声波提供准确的定位信息，通过语音和震动两种方式为盲人提供信息并进行导航。但是，由于需要布设大量蓝牙设备，造价较高而不能大范围使用。

崔金琦等^[2]设计出基于RFID的校园导航系统，并且在南京大学校园得以应用。但该系统是为一般人设计的，如果直接移植到盲人导航系统，就需要在路径网络中任意相连的两个结点之间的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所示。

1.4 导航流程设计

系统导航的基本流程为：盲人首先需要使用带有内置天线的导盲杖^[10]扫描到RFID标签以确定当前位置，之后通过语音选择目的地。随后系统进行路径规划，进而进行惯性导航^[11-16]，并且实时进行位置校准和语音提示，直至到达目的地。具体导航流程如图3所示。

1.5 数据库设计

系统采用SQLite轻型数据库来存储路径信息和定标点信息，为此设计两个数据表，分别是路径信息表(Route_Info)以及定标点信息表(Lable_Info)，分别存储每条路径的信息和定标点信息，具体包含的数据项分别如表1、表2所示。

2 系统实现 2.1 数据采集层实现

RFID标签铺设：最常见的RFID铺设方法有单排铺设和双排铺设方法，如图4、图5所示。

单排铺设方法感应半径较小，盲人使用导盲杖较难找到，并且相对于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；其次是从读写器到蓝牙串口模块，在这一过程主要就是根据读卡器所读取到的相关信息返回响应的信息。

2.3 数据处理层实现

在数据处理层主要涉及两个方面的工作：一是信息录入，二是信息查询。

信息录入：首先是录入各定标点信息，其次是对路径信息的录入。

信息查询：在系统中涉及的数据查询主要是定标点以及路径信息，系统采取基于SQLite的数据查询方式予以实现。盲人进入导航系统，系统打开读卡器，根据读卡器串口模块返回的值进行相关信息的查询。具体流程如图6所示。

2.4 导航服务层实现 2.4.1 惯性导航

徐向军^[17]提出一种惯性测量与航迹推算的室内定位方法，但其方法过于复杂，不容易和智能手机相结合。周婧等^[18]提出一种基于惯性导航的平面航迹推算方案，该方案需要携带两个陀螺仪和一部智能手机，如果用于盲人导航肯定会增加硬件成本；而且该方案虽然可以解决平面轨迹的推算问题，但是却无法推算上下运动的轨迹，因此该方案无法用于盲人导航。徐鼎等^[19]提出一种基于Android端的惯性导航算法，虽然其只需要一部Android手机，但是该方法只能推算平面轨迹，也不适用于盲人导航。

在综合多方面考虑后，系统将文献[20]提出的M5_DTW计步方法和文献[19]的惯导算法相结合，完成该系统惯性导航算法的设计。该算法分为模型建立和实时导航两部分。

在模型建立时，会采用M5模型树，其构造方法是：假设有样本集 $ T $ ，先计算 $ T $ 的标准差 $ {\rm{sd}}(T) $ ，之后依据不同的 ${\rm{sd}}(T) $ 将 T 进行划分，如果 T 的值波动很小或者 T 本身包含的实例就少也不需要对 T 进行进一步的划分。第 $ {i} $ 个测试将样本集 T 划分成子集 $ T_j $ ，并对该子集求标准差 $ {\mathop{\rm sd}\nolimits} ({T_i}) $ ，并且按照式(1)计算期望误差的减少量(SDR)。

${\mathop{\rm SDR}\nolimits} = {\mathop{\rm sd}\nolimits} (T) - \sum\limits_i^{} {\frac{{\left| {{T_i}} \right|}}{{\left| T \right|}}} \times {\mathop{\rm sd}\nolimits} ({T_i})$

(1)

在计算完样本所有的可能标准差之后，在其中选择期望误差的减少量(所有计算的误差减少量中最大的)作为最终期望误差的减少量。最后对每一个所划分出的子集建立回归模型，按照式(2)生成回归等式 ${\mathop{\rm LM}\nolimits} ({T_i})$ 。

${\mathop{\rm LM}\nolimits} ({T_i}) = \sum\limits_{i = 1}^N {({k_i} \times {C_i})}$

(2)

式中： $ C $ 为样本中的属性值； $ N $ 为属性的个数； $ k $ 为属性相关系数。

模型建立具体步骤如下：

1)标记状态：盲人在监护人的陪同下采集不同行走状态下的加速度数据，系统会给不同状态标记相对应的值。在平时出行过程中盲人一般产生4种运动状态数据，即噪声、静止、步行、上下楼梯，系统分别给它们标记–10、0、10、20。

2)数据预处理：为了达到对加速度数据去噪的目的，系统采用10点的平滑滤波对数据进行预处理。

3)特征提取：提取波峰均值、波峰方差、单步间隔均值、单步间隔方差以及波峰之间的时间间隔方差。

4)模型建立：利用M5模型树根据所选取的特征进行有监督的机器学习，最后输出分类模型。

在实时导航时，系统先要采集盲人正常行走的步长，然后根据步数、步长以及方向来确定盲人的位置，在计步时会用到动态时间规整算法(dynamic time warping，DTW)。

DTW是一种衡量两个时间序列之间相似度的算法，其算法思想是：令要计算相似度的两个时间列为 X 和 Y，长度分别为 $\left| X \right|$ 和 $\left| Y \right|$ ；把路径规整成 $W = {w_1},{w_2},\cdots,{w_k}$ 。 ${\mathop{\rm Max}\nolimits} (\left| X \right|,\left| Y \right|) \leqslant K \leqslant \left| X \right| + \left| Y \right|$ ， ${w_k}$ 的形式为 $(i,j)$ ，式中 $i$ 、 $j$ 分别为 $X$ 和 $Y$ 中的坐标，规整路径 $W$ 必须从 ${w_1} = (1,1)$ 开始到 ${w_k} = (\left| X \right|,\left| Y \right|)$ 结束。另外， $W$ 中的 $(i,j)$ 的 $i$ 、 $j$ 必须是单调的，即 ${w_k} = (i,j),$ ${w_{k + 1}} = ({i'},{j'}),i \leqslant {i'} \leqslant i + 1,$ $j \leqslant {j'} \leqslant j + 1$ ；最后需要得到最短的一个规整路径， ${\mathop{\rm Dist}\nolimits} (W) = \sum\limits_{k = 1}^{k = K} {{\mathop{\rm Dist}\nolimits} ({w_{ki}},{w_{kj}})} $ ，系统中 ${\mathop{\rm Dist}\nolimits} ({w_{ki}},{w_{kj}})$ 为欧式距离；在实现DTW算法时采用动态规划的思想，其核心见式(3)：

$\begin{array}{c} D(i,j) = {\mathop{\rm Dist}\nolimits} (i,j) + \min [D(i - 1,j),\\ D(i,j - 1),2D(i - 1,j - 1)] \end{array}$

(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算法产生该带权值有向图从指定起点到终点权值最小的路径；最后，实时导航并给出语音提示。

针对经典Dijkstra算法在搜索过程中存在缺乏导航方向性以及大量冗余计算等诸多问题，文献[21]-[22]提出矩形限制搜索区域算法，其基本思想是：首先，以导航的起点(S)和终点(D)为焦点，选取合适的椭圆区域；其次，根据所确定的椭圆区域求出最小包含矩形，并以此为限制区域。在求限制区域时，最为关键的就是要确定椭圆长轴的长度，由文献[17]可知，定义比例系数 $\theta = {P_{sd}}/{E_{sd}}$ ，其中 ${P_{sd}}$ 为起点和终点的最短路径， ${E_{sd}}$ 为起点和终点的欧氏距离，通过统计分析方法得到置信水平达到95%的比例系数 $\theta $ ；设起点坐标为 $S({x_s},{y_s})$ ，终点坐标为 $D({x_d},{y_d})$ 由此得椭圆中心点坐标为 $(a,b)$ ，其中， $a=({x_s}+{x_d})/2$ ， $b=({y_s}+{y_d})/2$ 。 $\varphi $ 为长轴与x、y 轴正方向的夹角， $\varphi=\arctan (({y_s} - {y_d})/$ $({x_s} - {x_d}))$ 。椭圆长轴为 $2A=\theta\times {E_{sd}}$ ；椭圆短轴为 $B = \sqrt {{A^2}-({{({y_d} - {y_s})}^2}+{{({x_d}-{x_s})}^2})/4} $ ，由此可得椭圆的方程为

$\begin{array}{c} \displaystyle\frac{{{{\left[ {\left( {x - a} \right)\cos \;\varphi + \left( {y - b} \right)\sin \varphi } \right]}^2}}}{{{A^2}}}{\rm{ + }} \\ \displaystyle\frac{{{{\left[ { - \left( {x - a} \right){\rm{sin}}\;\varphi + \left( {y - b} \right){\rm{cos}}\;\varphi } \right]}^2}}}{{{B^2}}}{\rm{ = }}1 \end{array}$

(4)

再对椭圆方程式(4)分别对x和y求偏导数，得到x和y的极值分别为

${x_m} = a \pm \sqrt {{A^2}{{\cos }^2}\varphi + {B^2}{{\sin }^2}\varphi }$

(5)

${y_m} = b \pm \sqrt {{A^2}{{\sin }^2}\varphi + {B^2}{{\cos }^2}\varphi }$

(6)

由式(2)、式(3)可以分别得到x和y的最小值 ${x_{\min }}$ 、 ${y_{\min }}$ 和最大值 ${x_{\max }}$ 、 ${y_{\max }}$ ，由此构成椭圆的最小外接矩形，如图7所示。

系统利用矩形限制搜索区域算法求起点和终点间最短路径的算法步骤如下：

1)初始时，C只包含起点，即C＝{S}，v的距离为0。U包含除S外的其他顶点，即U={其余顶点}。若S与U中顶点u有边，则<u, S>正常有权值W；若u不是S的邻接点，则<u, S >权值为∞。

2)根据起点 $S({x_s},{y_s})$ 和终点 $D({x_d},{y_d})$ ，计算 $A$ 、 $B$ 、 $a$ 、 $b$ 、 $\varphi $ ，构造椭圆方程，确定椭圆区域。

3)根据已经确定的椭圆方程计算 ${x_{\min }}\text{、}{x_{\max }}\text{、}$ ${y_{\min }}\text{、}{y_{\max }}$ ，确定最后搜索的矩形区域 。

4)从U中选取一个在矩形区域内且权值最小的顶点k，把k加入C中(在初始状态下权值按照式(7)计算)。

5)以k为新考虑的中间点，修改U中各顶点的权值；若从起点S到顶点u的权值(经过顶点k)比原来权值(不经过顶点k)小，则修改顶点u的权值。

6)重复步骤4)、5)，直到找到从S到D的一条路径(即所规划路径)。

2.4.3 路径权重初始与更新

路径权重的初始化和更新，决定着最终导航路径成败，各自算法如下。

系统初始的权重：

$w = \frac{{{D_{Ai}}}}{{{{\min }_{1 \leqslant i \leqslant k}}({D_{Ak}})}}$

(7)

式中： ${D_{Ai}}$ 为起点 $A$ 到终点 $i$ 路径的距离； ${\min _{1 \leqslant i \leqslant k}}({D_{Ak}})$ 为起点 $A$ 到终点k的最小距离。

系统提供两种更新权重的方法，即手动更新和自动更新。手动更新是由盲人监护人根据实际的路径情况进行赋值：如果是增加路径权重，监护人只能赋值三类值(原始权重的1.5倍、2陪以及无穷)；如果是减少路径权重，系统则会先判断当前路径权重是否为0，如果为0则不再进行权重更新，若不为0则每次减少初始权重的五分之一。自动更新时，系统会先判断上次该路径权重更新时间是否超过一天，即判断当前时间(NowT)减去上次更新时间(LastT)是否大于1，如果大于1则增加权重，小于1则减少权重。自动更新减少权重的算法和手动更新一致，但在增加权重时，会先判断当前权重是否大于初始权重，若大于则不进行权重更新，若不大于则每次增加初始权重的五分之一。具体的算法流程如图8所示。

2.4.4 导航纠偏

数据处理层提取读卡器返回的ID信息，并进行数据库匹配检索，再根据数据库返回的定标点经纬度、路径地磁方向提示用户进行位置纠偏与方向矫正。当用户成功读取到两张RFID标签时，视为位置正确，即纠偏成功；否则，定义方位纠偏事件。纠偏成功后，利用惯性导航系统进行对下一定标点的导航，直至导航结束。

2.4.5 语音提示及反馈

鉴于盲人这一特殊群体，语音提示是系统必不可少的部分。系统主要在两个方面需要用到语音技术：首先是系统通过盲人发出的语音信息来确定需要导航的起点和终点；其次是导航时的语音提示信息。为了避免给系统带来过多的复杂性，在系统中选用已经得到广泛使用的讯飞语音API^[23]开发出适合于系统的语音提示及反馈。

3 实验与结果分析

为了验证系统的可行性，在盲校选取20名盲人学生进行导航实验。图9为盲人在测试中所穿戴设备的效果图；图10、图11分别是简单和复杂路径导航图，测试结果分别见表3、表4。

通过表3的数据分析得出：20名测试人员一共进行了204次导航测试，一共走过3 580个定标点，一共发生6次错失标签的情况，走失率为0.17%，盲人导航的成功率为97.06%。通过表4的数据分析得出：20名测试人员一共进行了164次导航测试，一共走过5 840个定标点，一共发生11次错失标签的情况，走失率为0.188%，盲人导航的成功率为96.34%，整体导航精度为0.469 7 m。鉴于盲人群体的特殊性，在系统设计之初就提出定标点的导航精度要小于0.5 m，因为在这一范围内盲人可以较好地辨别出方向和距离，如果超出这一范围盲人极易发生走失情况，测试结果显示没有任何一组测试的平均导航精度超过0.5 m；同时，简单路径以及复杂路径导航规划成功率分别为97.06%、96.34%，都大于95%，达到基于矩形区域限制Dijkstra导航算法的设计要求。

NavCog3^[24]利用低功耗蓝牙作为信标点(蓝牙灯塔)，结合惯性导航为盲人自主出行提供导航服务；为了达到更高的精度，蓝牙灯塔之间的间隔为7~10 m，而且为了让无线电波有更好的可到达性，灯塔的高度为2~3.5 m。最终的实验结果表明：NavCog3的平均导航误差为1.65 m。相对于NavCog3，系统采用纯RFID标签路径布局方式(每隔20 m布局一组)RFID标签，1 km需要100个RFID标签，每个标签的成本为0.3元，1 km的成本为30元)，成本低廉利于大范围推广，并且平均导航误差为0.467 9 m优越于NavCog3。

4 结束语

系统采用手机惯性导航结合RFID射频识别技术，不仅解决了惯性导航无法消除的累计误差问题，而且解决了纯RFID导航标签过多铺设困难的问题。为了扩大感应范围提高导航精度，采用了RFID双铺布局方式；为了体现导航的方向性、降低系统计算冗余，采用修正了的Dijkstra导航算法，可以根据盲人路径行走频率以及路况等实际情形动态地变更路径的权值，使系统导航出来的路径更加安全可靠。实验结果表明：系统简单和复杂路径导航成功率分别为97.06%和96.34，定标点平均导航误差为0.467 9 m，可以胜任盲人日常自主出行的导航服务。在未来可以将RFID标签嵌入盲道砖中，在进一步提高导航精度的同时，还可以大幅度减少标签使用量。