基于K 近邻和动态时间规整算法的盲人物联网手杖系统

夏伦腾 ，张 莉 *

（1. 中南民族大学生物医学工程学院，武汉430070； 2. 中南民族大学检测与仪器校级工程中心，武汉430070）

0 引言

根据时代数据2016 年统计数据表明，我国盲人数量1 731 万，占全国总人口数量的1.26%，目前我国存在视力障碍的人数居世界第一［1］。由于盲人的视力障碍，他们摔倒或者迷路走丢的情况时有发生，而一旦发生摔倒之类的安全问题，很容易错过最佳的救助时间，对身体造成永久性的损害。在日常生活中，盲人使用的手杖功能单一［2］，这种手杖不能保证盲人的出行安全，同时盲人的监护人也不能实时了解盲人的身体状况和地理位置等情况。针对如今日益复杂的路面情况和交通状况，如何设计一款能够帮助盲人日常安全出行，并且能够实时监护盲人身体姿态信息和定位的盲人智能手杖系统，具有极大的应用价值。

物联网的概念在1999年被正式提出［3］，顾名思义就是“物与物相连的互联网”，其用户端延伸和扩展到了人和物之间进行信息交换和通信，目前国内对物联网的定义是：通过传感器无线射频识别技术、全球定位系统等信息传感设备，按约定协议，把任何物品和互联网连接起来进行信息交换和通信，以实现智能化识别、定位、跟踪、监控和管理的一种网络。机器学习方法在20 世纪80 年代被提出［4］，在如今互联网时代，数据量的累积是海量的，目前由海量数据构成的大数据时代已经到来，机器学习方法在大数据挖掘中起着重要的作用，因此，如何融合物联网技术与机器学习算法是当今物联网技术面临的重要技术问题之一。在操作用户应用方面，传统上大部分家庭安全系统操作监护界面都是利用手机应用或者计算机应用，目前微信已经成为了我们日常生活中一个必不可少的通信工具，很多人的关系链已经从通信录转移到了微信，所以在微信小程序上的监测可能会在一定程度上优于传统的计算机端。

本文提出了一种基于K 近邻（K-Nearest Neighbor，KNN）和动态时间规整（Dynamic Time Warping，DTW）算法的盲人物联网手杖系统，集传感器、物联网通信、机器学习和微信小程序为一体，是一款具备避障、定位、报警、通信和监护等多功能的集成系统，并且集成了微信小程序作为监护操作界面。该系统能够为盲人出行的便利和安全性提供有效的解决方案，在盲人出现摔倒或者迷路的情况时可以第一时间借由一个按键通过互联网进行远程求助，监护人则可以通过微信小程序查看盲人的安全情况。

1 系统方案设计

盲人物联网手杖系统总体框架如图1 所示，主要包括手杖（硬件）端、云端服务器和用户端三部分。通过物联网技术将一个单纯的辅助工具——盲人手杖与互联网相连，通过云端服务器的数据存储功能供用户端调取查询，用户端则利用目前的轻量级应用——微信小程序［5-6］作为核心的监护操作上位机。三个部分功能实施的具体内容如下：

1）手杖（硬件）端的功能包括：利用红外线传感器实现的避障，通过电位器调节的超声波避障，语音求助和远程通过全球移动通信系统（Global System for Mobile communications，GSM）求助，以及全球定位系统（Global Positioning System，GPS）和加速度计陀螺仪传感数据的采集、处理和传输。

2）云端服务器的功能包括：域名注册、域名解析、网站备案以及云服务器的搭建和数据库存储功能的实现、云函数的创建和调用、云端服务器应用程序接口（Application Programming Interface，API）和HTTP API的调用［7］。

3）微信小程序的微信标记语言（WeiXin Markup Language，WXML）、微信样式表（WeiXin Style Sheets，WXSS）和Java Script架构的编写。功能包括：调用服务器数据库中的GPS 定位数据信息、陀螺仪加速度计采集的传感信息数据和姿态报警信号数据，从而实现远程定位监护、监护盲人姿态信息［8］以及远程报警功能。另外还有异地天气查询、盲人安全新闻资讯和家庭成员登录等附加功能的设计。

2 系统硬件设计

盲人物联网手杖系统的硬件端设计如图2 所示，以STM32F4103ZET6为核心处理器，集合了各类传感器：

1）红外线传感避障模块：本文采用的是以LM393 电压比较器为基础的红外线避障模块，位于盲人手杖的最前端。该模块对环境光线适应能力强，具有一对红外发射与接收管，发射管发射一定频率的红外线，当检测方向遇到障碍物时，红外线反射回来被接收管接收，经过电压比较器处理之后，模块绿色LED 灯亮起，模块输出端便会输出逻辑低电平，触发语音播放模块的提示语音及手柄处的震动电机提醒，其有效距离达到30 cm。该模块主要用于探测狭窄的过道以及台阶，确保盲人外出安全对及其对路况的掌握。

2）超声波传感测距避障模块［9］：本文采用的是HC-SR04超声波模块，位于手杖红外探头上方。该模块的最大的传感距离可以通过手柄电位器灵活调节，最大探测距离可以达到4 m，可以探测较远距离的障碍物。模块工作原理是采用IO触发测距，模块自动发送8个40 kHz的方波，探测是否有信号返回，有信号返回通过IO 输出一个逻辑高电平信号，所以当盲人与前方障碍物的距离小于最大的感应距离时，便会触发震动电机提醒以及语音提示前方障碍物的距离，保障盲人出行的安全。

3）求助语音及通信模块［10-11］：盲人可以通过按键触发语音播放模块中存储的求助语音向周围人群进行求助。同样地，可以通过另一个按键触发远程求助功能，远程求助通信通过SIM808 模块上的SIM 卡向指定的电话号码发送求助短信，短信内容包括盲人的固定求助短语及SIM808 模块采集的地理位置经纬度信息。

除了以上基本功能以外，本文还加入了GPS+通用分组无线服务（General Packet Radio Service，GPRS）定位功能［12］，经过定位模块传感器的数据采集，再通过GPRS 数据传输功能将定位数据传输至云端服务器数据库存储；基于MPU6050 加速度计陀螺仪传感模块的姿态监护功能［13］，将传感器采集到的三轴加速度和三轴角速度数据通过卡尔曼滤波（Kalman Filtering，KF）［14］姿态解算得出精确度极高的姿态角度数据，通过连接数据传输模块发送至云端服务器数据库存储，同时融合机器学习KNN&DTW 为基础的算法进行姿态识别，当输入传感器采集的角度数据之后，利用机器学习算法进行姿态分类，当分类为异常姿态时（如摔倒）会产生一个报警信号，再将此信号数据包通过GPRS 数据传输至云端服务器数据库存储。

图2 系统硬件设计框图Fig. 2 Block diagram of hardware design for the proposed system

3 系统软件设计及算法实现

为了保证手杖系统定位功能的实现和定位精准度与稳定性，以及加速度计陀螺仪姿态监护的稳定性和核心监护上位机功能的实现，用户端的监护查看操作都离不开程序的调度，本章主要介绍实现手杖核心功能的软件开发过程。

3.1 卡尔曼滤波姿态解算算法功能实现

本文研究利用MPU6050 获取相应位置的角加速度和加速度，再将二者数据利用已经相对比较成熟的KF 算法处理，融合计算出姿态角度，因为加速度计传感数据及陀螺仪传感原始数据具有一定程度的数据噪声，例如加速度计传感数据受带宽影响，陀螺仪状态易受震动、温度等影响。为解决这个问题，提高后续机器学习分类器姿态分类的精准度，本文在将加速度计和陀螺仪传感数据作为算法输入参数的基础上，添加了姿态角度数作为KNN&DTW 算法分类器的第三项对比参数。姿态角度是通过KF 算法融合加速度计及陀螺仪的传感测量数据得到的滤除噪声对于姿态最优估计的角度数据。

KF 算法可以用于计算估计过程的状态［15-16］，并使估计均方差最小。在单片机平台上利用KF 整合由陀螺仪和加速度计获得的原始数据［17］。陀螺仪的作用是测量角速度，通过对角速度的积分得到角度值，但其噪声大且极易受到环境的影响，因此不适合单独用于使用陀螺仪作为传感器得到姿态角度。本文系统使用加速度计测量角度与陀螺仪角度积分结果进行修改再积分，再通过系统中的线性系统状态方程输出观测数据，滤掉相关外在噪声，以获得姿态数据的最优估计，如图3所示。

图3 卡尔曼滤波姿态解算示意图Fig. 3 Schematic diagram of Kalman filter attitude calculation

二者数据融合的过程主要是通过卡尔曼滤波的标准方程并参考应用文献［18］中提出的姿态融合算法进行计算。本文假设盲人姿态角度为ψ，采用加速度计探测的作为姿态角度的常值偏差b，以ψ 与b 作为盲人姿态角度的状态方程，结合卡尔曼滤波标准方程得出状态方程（1）及观测方程（2）：

其中：ωgyro为包含固定偏差的陀螺仪输出角度；ψacce为手杖上处理过的加速度计角度值；ωg为陀螺仪采集测量中的误差，ωa为加速度计采集测量中的误差，本文假设ωg和ωa是相互独立且满足正态分布的白色噪声。设Ts为采样周期，可以得到离散系统的状态方程（3）和测量方程（4）：

根据KF 算法的标准方程，要想知道k 时刻的盲人姿态角度情况，就需要知道k - 1时刻的角度值，再通过预测得到的k时刻的预测值和高斯噪声的方差，在此基础之上通过KF算法进行递归运算直至估算出最优的姿态角度值。KF 的标准预测公式如下：

式（5）中X(k|k - 1)是根据上一状态预测的结果，X(k -1|k - 1)为上一次的最优结果另外还需要知道系统过程噪声协方差阵Q以及测量误差的协方差阵R进行校正，本文中Q和R的矩阵形式为：

其中q_acce和q_gyro分别为加速度计和陀螺仪测量值的协方差。对应的X(k|k - 1)的协方差参考式（6），其中P(k - 1|k -1)为X(k - 1|k - 1)对应的协方差，AT为A的转置矩阵，Q 的取值参考式（7）。式（5）、（6）的主要作用为系统状态的更新。姿态数据的最优估计X(k|k)计算公式如下：

其中的 Kg()为卡尔曼增益（Kalman gain，Kg）［19］，计算公式如下：

上述计算已经可以得出k状态下的最优估计X(k|k)，为了使该系统持续运转下去，还需要更新k 状态下X(k|k)的协方差，所以根据标准KF可得到：

3.2 基于机器学习算法的姿态预警功能设计

本文系统还融合了机器学习KNN&DTW 分类算法为基础的姿态异常进行报警的功能，实现过程为：将加速度计陀螺仪模块采集的传感器数据输入KNN&DTW 算法的分类器之中进行分类判断，分类器中预先已经训练过大量数据集，手动对训练数据集进行标记，包含5 个姿态常态标签，当输入实时传感器数据经过算法运算分析之后，若不属于任何一类常态行为的标签，就会分类为姿态异常，此时会输出一个报警信号，实现远程姿态安全的监护。

KNN 分类算法［20］：如果一个样本在特征空间中的k 个最相似（即特征空间中最邻近）的样本的大多数属于某一个类别，则该样本也属于这个类别。原始KNN 算法用于分类问题时，存在诸多可以改进的地方，例如样本属性特征的相关性不一致、算法中k 值的选取对分类结果有较大的影响等。针对这些缺点，可以采用特征选择剔除不相关的属性，亦可以通过改进距离函数来优化算法，本文使用的就是后者。KNN 算法的距离度量一般采用欧氏距离，但标准的欧氏距离在面对多属性特征空间划分时会变得不准确，所以本文在KNN 算法基础上融合了DTW 方法作为KNN 算法的距离度量，可以很好地解决这个问题，使分类结果更加准确。

动态时间规整（DTW）由日本学者Itakura 在1970 年提出［21］，是一种衡量两个长度不同的时间序列的相似度的方法，在模板匹配、手势识别、数据挖掘和信息检索等领域应用广泛。DTW 是一个典型的优化问题，它用满足一定条件的时间规整函数描述测试模板和参考模板的时间对应关系，求解两模板匹配时累计距离最小所对应的规整函数。如序列（11）、（12）所示，分别为参考时间序列数据集Q 和测试时间序列数据集C，它们的长度分别为n、m，Q和C的特征点分别为q和c。

DTW 非常适合对具有不同频率或异相的序列进行分类，所以用DTW 分类一个人是走路、站立还是坐下就非常适合，图4（b）显示了DTW 距离矩阵的表现方式，通过测量Q、C之间的距离来计算每个像元，黑色路径代表最佳路径，代表两个序列的最佳比对。使用动态编程技术在Python 中实现DTW 对于距离矩阵的运算，实现主要依靠三个关键步骤：

1）计算两个序列之间的动态时间规整距离；

2）计算Q、C之间的距离矩阵；

3）通过式（1）、（2）进行KNN 计算预测类别的标记和分类数据集的概率。

算法的实施过程是：通过KNN&DTW 算法计算两个时间序列特征点到特征点的相似程度，在盲人手杖系统中则是将传感器训练数据样本和参考数据样本进行相似度匹配。DTW 使用所有相似点之间的距离的和（称之为规整路径距离（Warp Path Distance，WPD））来衡量两个时间序列之间的相似性，利用全局路径窗口（Warping Window，WW）（如图4（b））显示全距离矩阵的最佳路径。如式（13），最佳路径的计算主要是计算两个时间序列节点间的最短距离，例如q1与c1，利用shortestpaths()表示最短距离的运算，再通过SUM()进行累加运算。

手动对测试样本进行标记，本文设计了5 类标签，分别是站立、坐、行走、下楼和上楼。可通过计算两个序列之间的动态时间规整距离的方法计算两个序列之间的DTW 距离，也可以通过计算Q、C之间的距离矩阵的方法来计算两个集合的距离，这是支撑KNN&DTW 分类算法的两种方法；之后再利用预测方法进行两个方面的预测：1）预测的类标签；2）KNN 标签计数概率。

图4 KNN&DTW 算法示意图Fig. 4 Schematic diagram of KNN&DTW algorithm

3.3 用户端（微信端）功能设计

微信小程序作为监护应用相较于原生应用具有更优的便捷性和可操作性，基于现代人的社交习惯，微信端的通知情况比原生应用要更加及时；微信端集成了家庭监护人成员安全登录、盲人地理位置查询、姿态角度查询及姿态异常报警监护功能，此外还附加了如天气查询、一键远程报警、盲人安全小资讯等功能，完善了盲人物联网手杖集成系统。用户端微信小程序的功能流程框图如图5所示。

4 系统测试结果与讨论

4.1 陀螺仪加速度计传感器数据采集

为了对KNN&DTW 算法分类器进行训练，需要采集大量的传感数据同时贴近盲人的日常生活行为姿态，本文将以MPU6050 为核心传感器的加速度计陀螺仪模块固定在盲人手杖的握把处，因为考虑到盲人在日常生活中，握把处的动作幅度相对整个身体来讲是最小的，所以数据噪声相对而言也较少。本文测试人员为实验室的10 位实验人员，分别在实验室和楼梯间进行数据的采集和测试。

传感器数据采集中，考虑到信号的相似性和行为动作的连贯性，通过对盲人日常姿态和行为习惯［22］的分析，连贯动作的切换间会产生较大的传感曲线的变化，例如从上楼转换为下楼、坐转换为站立等，而这种变化容易造成对于异常姿态的误报警，大大降低姿态识别的准确率。所以在本文的实验过程中，分别对上楼和下楼、站立和坐传感数据进行同时采集，而将行走作为单独采集的传感数据。加速度的单位以重力加速度g（取9.8 m/s2）为基本单位，陀螺仪采集数据单位为def/s，经卡尔曼滤波姿态融合角度数据单位为def。测试中利用深圳维特智能科技有限公司的上位机程序记录传感器各类数据，通过OriginLab公司开发的Origin软件绘制各类传感曲线，如图6。图6中的三条曲线分别为X轴、Y轴和Z轴数据，图（a）～（i）分别包括加速度计的传感数据曲线、陀螺仪传感数据曲线和经过卡尔曼滤波姿态解算输出的姿态角度传感数据曲线。

从图6 的姿态传感器测试传感数据可以看出，不同姿态下的三轴传感器数据均有不同的特征，本文将各种传感器实时采集的各轴传感数据时间序列与参考的各轴传感数据时间序列的特征点一一进行比对，识别二者的相似度，从而进行姿态分类，识别出盲人的姿态情况，以达到对异常姿态的预警、保障盲人的生命生活安全的目的。

图5 用户端软件功能流程Fig. 5 Flowchart of user-end software functions

4.2 基于机器学习算法的姿态预警功能测试

目前市面上最先进的盲人智能手杖基本上以传感器探测路面障碍物情况为主，少数盲人智能手杖具备通信求助功能以及定位功能，基本没有一款智能手杖具备姿态识别及姿态监护的功能。本文不仅在手杖端加入了姿态识别的功能，并且所采用的机器学习方法进行姿态识别区别于传统的姿态角系统，姿态角系统通过机械地设定各轴变化角度，当变化角度大于限定范围时，便会输出报警信号，不能智能识别复杂的行为姿态。本文系统的优势在于：以机器学习算法KNN&DTW来智能地判断盲人姿态安全状况并辅以微信小程序通知求助，极大地降低了姿态识别误报警的可能性。将上述5 类姿态的数据各1 000组进行交叉验证训练，然后将训练好的分类器模型与姿态角系统中设定的异常姿态功能［23］同时测试。测试中将随机输入10 组姿态角度数据，并且与手杖实际状态进行对比，传感器采集结果及对比结果如表1、2 所示，将同一个姿态角X轴、Y轴和Z轴角度数据作为输入数据，持续时间为手杖传感器在该角度所持续的时间，在姿态角度预警系统中默认正常姿态范围为：X轴 -40°至 40°，Y轴 -25°至 25°，Z轴-20 至20°；两组表格中实验序号一致则代表为同一组实验，例如表1中实验序号1采集的三轴角度是支撑表2实验序号1输出结果的实验数据。

图7 陀螺仪硬件连接及传感数据采集Fig. 7 Gyroscope hardware connection and sensor data acquisition

表1 传感数据的采集结果Tab. 1 Acquisition results of sensing data

表2 姿态预警系统的预警结果Tab. 2 Warning results of attitude warning system

如表1 序号3 采集结果及表2 对比实验结果所示，在靠近临界值的角度分析结果，系统设定的范围精度并不高，不能准确地判断出正确的姿态结果；考虑到盲人出行实际情况，在表1，表中测试序号2、7 和9，模拟手杖摔到地上迅速捡起等情况，系统的报警结果就不太准确，连续测试了10 组不同的姿态情况下的角度数据，姿态角度系统的准确率只有50%，而经过数据集训练的分类器结果输出有100%的准确率。10 组测试数据显示：相较于姿态角度预警系统，该算法的姿态识别准确率提高了50 个百分点，在较小样本测试的结果较好。当后期将测试数据加大至100 组时，KNN&DTW 的准确率均在86%左右，相较于传统的设定姿态角度范围的预警系统的准确率55%具有相当大的优势，充分体现了本文所应用的机器学习分类器的性能良好，能够达到一个很好的姿态监护效果。

4.3 GPS定位功能测试

本文系统中手杖的GPS定位功能通过远程通过微信小程序界面查询盲人的实时地理位置实现。在手杖中配置了一块GPS+GPRS/GSM 定位数据传输模块，采用了SIM808 定位通信模块，通过模块进行GPS 信号数据的采集，并利用GPRS 进行数据传输，将盲人地理位置信息以及速度信息以符合NEMA-0813协议的格式数据发送到云服务器。NEMA0183是美国国家海洋电子协会（National Marine Electronics Association，NMEA）制定的标准格式，目前已成了GPS 导航设备统一的海事无线电技术委员会（Radio Technical Commission for Maritime services，RTCM）标准协议，协议内容指令如表3所示。

表3 NEMA-0183协议具体指令信息Tab. 3 NEMA-0183 protocol specific instruction information

实验测试地点为学校操场，持手杖多次移动位置，并在一个位置多次测量地理位置数据，将测试的经纬度信息通过串口显示出来，将NEMA-0183 格式的经纬度数据及其他数据换算成标准经纬度的格式，再通过GPS 经纬度测试工具进行查询显示；同时与测试地点的实际标准经纬度进行比较，实际经纬度信息由百度地图采集所得，用于对比测试手杖定位模块的定位精度。测试在学校操场不同的地方利用不同的定位模块进行了多次定位采集，具体测试数据如表4 所示（以NEMA格式数据显示例如E11 423.234 7 即东经114°23′14.082″，地图1″误差约等于30.9 m，三者误差比为三者经纬度定位误差距离之比）。

由于盲人个体的特殊性，求助时间一分一秒都显得尤为重要，所以手杖的定位精度直接影响着盲人救护的及时性，但市面上多款盲人手杖的定位功能极易受到信号强度、天气、温度等多因素的影响。考虑到成本以及定位精度等问题，本文将NEO-6M-001、GU620 以及SIM808 定位传感器进行精度对比测试［24］。从结果可知，GU620 以及 SIM808 定位精度较高（误差距离基本小于1 m），NEO-6M-001 定位精度对比二者稍差（误差距离均大于1 m）；又由于GU620 定位模块的成本较高，并且没有GPRS 数据传输功能而需另外外接，所以本文采用价格低廉的SIM808 模块并且集成GPRS 数据传输模块，可以实现定位数据的云端传输，恰好体现了盲人手杖的物联网概念和微信小程序端查询、监护的功能需求。

综上所述，本文设计结合物联网技术的盲人手杖所实现的定位功能精度较高，能够保证盲人的出行定位监护功能的实现。

表4 GPS定位测试结果对比Tab. 4 Comparison of GPS positioning test results

5 结语

本文融合KNN&DTW 方法及物联网技术，以盲人手杖为核心开发了一套完整的监护系统，从盲人本身的生活出行情况和监护人的日常监护两个方面保障了盲人的安全出行。本文除了具备市场上手杖已具备的红外线传感避障和超声波避障功能以外，还加入了远程求助通信功能，在盲人遇到危险时能快速求助；市场上盲人手杖只能够通过短信发送定位信息进行求助，本文研究则将GPS 定位的功能通过GPRS 通信模块实现云端服务器的传输，利用微信小程序查询和实时地图显示，更加直观地帮助监护人监护到盲人的地理位置情况；最重要的是在手杖中加入了加速度计及陀螺仪模块，通过KF姿态解算后输出的姿态角度来查看盲人的姿态情况，亦通过GPRS数据传输至云端服务器，同样是利用微信小程序调取传感数据信息；同时加入了融合机器学习算法的姿态异常监护功能，加入机器学习KNN&DTW 算法，通过大量数据集进行测试，手动对姿态状况进行标签标记，从而使分类器可以识别盲人正常行为的姿态情况，避免误报警现象频发；监护人可以通过微信小程序远程呼叫救护车，最大限度保障了盲人的安全。本文在算法应用中加入了几种基本的姿态情况，对于较复杂的行为判断仍有较大的研究潜力。