基于Dijkstra算法的盲道导航软件的设计与开发.docx

    基于Dijkstra算法的盲道导航软件的设计与开发    曹梦凡 李佩玲 唐轲Summary：针对盲人的出行需求，设计并开发了一款盲道导航软件，引导盲人在盲道上行走，帮助盲人感知道路，保障盲人安全出行该文首先介绍了该软件的功能设计和数据组织方式其次，就系统开发使用的关键技术，即Socket通信技术与基于Dijkstra算法的最短路径规划进行介绍最后，使用该软件在徐州选定的街区进行实地测试，探究软件的可行性Key：盲道导航;Dijkstra算法;最短路径规划：TP311        ：A：1009-3044（2021）30-0082-04开放科学（资源服务）标识码（OSID）：据相关数据统计，截至2018年中国盲人数量已达到1700万人[1]然而，我们在日常生活中很难看到盲人和视障患者的身影，出行难、出行机会少、出行范围小已经成为盲人群体亟待解决的问题人类获取外部信息的最主要感官为视觉，因此视障人群很难判断周围物体的位置和相对关系，造成生活中的诸多不便[2]如今盲人出行已有诸多无障碍设施和产品的帮助，但固定的无障碍设施使用场景限定，不足以满足盲人的出行需求，这就需要便携的导盲工具。

当前盲人大多还是借助盲杖或导盲犬出行，市面上也开发出了多种导盲产品，例如电子导盲杖、导盲眼镜、导盲机器人等[3]盲杖简单易使用，但功能单一，导盲犬灵活，但资源有限且受外界影响大，电子导盲产品设计先进、功能齐全，但价格昂贵，不足以普及而导航系统操作方便、普及率高、成本低，为生活出行带来了极大的便利针对盲人群体特殊的空间认知，综合导航系统的优点，本文旨在基于盲道建设上，专为盲人设计一款智能语音化的盲道导航系统，以解决盲人的出行问题，实现路径引导，增强盲人的安全感与方向感1系统设计1.1系统建设目标通过外业调查、测绘采集以及内业处理等工作，建立盲道地理空间数据库，以该数据库为基础，依托计算机科学、地理信息系统（GIS）、移动互联网等技术，设计并开发一套低成本、语音化的“基于路径智能规划的盲道搜索与导航系统”该系统针对盲人设计，可以实现盲道路径规划与导航，通过设置常用地址简化导航功能，在危险情况下可通过呼叫紧急联系人和应急报警功能实现盲人初步自救本系统旨在解决盲人出行难、困难多、寻求帮助不便利的问题，为盲人出行提供便捷有力的服务1.2 系统功能设计本盲道导航系统以百度地图的Android地图SDK、Android定位SDK为基础，百度地图SDK是基于Android开发语言编写的应用程序接口，在本项目中主要借助了地图显示、定位、点线绘制、路线规划四项技术。

由于盲人对空间感知的不全面、对地理要素的认识缺少以及较低的应急处理能力，盲人出行除了核心的盲道导航功能之外，他们还需要一些辅助功能来帮助他们在外行走时能够应对多变的环境状况和不可预测的突发情况因此，我们在结合现有导航软件的基础上，考虑到盲人群体的特殊性，简化融合，在主菜单界面设计了以下五大主要功能：1）发送位置信息用户可通过该功能向紧急联系人以短信的形式发送实时位置信息该功能利用Android中的SmsManager（短信管理器）管理短信操作，首先获取收信人号码和短信文字内容包括时间、位置、经度、纬度相关字符串，通过SmsManager类和sendTextMessage（）方法调用系统的短信接口进行短信发送，当用户确认相关内容后即发送给收信人2）当前位置播报盲人无法以视觉方式去认识客观世界，他们只能通过触觉、听觉等其他非视觉感知方式去获取外界信息，因而，他们所感知的地理信息也与常人不同[1]即使是弱视力的视障人士也很难在复杂的外界环境信息中准确地作出判断，这些都极大程度地阻碍了他们在行走中判断方位、获取地理要素以及作出相应反应的能力所以，对于盲人来说，知晓自己当前所处位置是十分重要的当前位置播报”功能调取用户当前GPS定位信息，通过BDLocation类的各种getLatitude（）、getLongitude（）等get方法获得一系列定位相关的全部结果，并以语音播报形式告知用户，包括时间、位置、经纬度。

其中，语音播报采用Android原生的TTS（TextToSpeech）接口，其基本使用主要通过实例并初始化TTS对象，使用textToSpeech.speak（）方法进行简单播报，并可用setPitch（）和setSpeechRate（）方法控制音调和语速3）选择常用地址鉴于盲人出行的不便利，他们出行往往去向几处固定的地点在系统设置中，允许盲人进行常用地址的编辑与存储，添加方式分为手动输入和设定当前位置为常用地址两种方式盲人在需要导航时可直接通过该功能呼出常用地址列表，选择地址进行导航，提高便利性，高效完成固定路线的导航4）呼叫紧急联系人“呼叫紧急联系人”功能帮助盲人在盲道导航中也能快速向紧急联系人拨号，完成及时便捷的通话该功能同样使用Android平台TelephonyManager（管理器）调用拨号器拨打指定号码，主要为getSystemService（）获得TelephonyManager的服務对象，将号码转为uri，实例化intent，设置ACTION_CALL和uri参数跳转到拨号界面直接拨打5）应急报警考虑到盲人易遇危险以及遇到危险后难以寻求帮助的情况，我们设计了应急报警的功能模块。

在该功能模块中，盲人可向常用报警快速拨号1.3 数据库设计为实现盲道导航系统的导航功能和登录等其他基本功能，本系统利用SQL Server数据库存储数据，主要包括地理空间数据库和用户数据库为方便测试，本项目团队在江苏省徐州市云龙湖景区东南方向的一个街区（34°13′7″N-34°13′41″N，117°9′8″E-117°10′1″E）采集盲道数据，该街区地图如图2所示1.3.1 地理空间数据组织地理数据即为试验区域采集所得的盲道上的点数据及其连成的盲道线数据盲道上点数据是通过RTK（Real-time kinematic，实时动态载波相位差分测量技术）获取的厘米级精度的数据，保证了盲道位置信息的准确性，从而一定程度上提高移动终端的定位精度点数据组织结构如表1所示，为保證点可被检索，将点号设置为主键且作为唯一标识字段获得的点数据按实际情况依顺序连接得到盲道线数据，对该数据进行处理，在CAD中结合路的拐点和道路实际状况将其打断，最终在试验区中得到30条盲道线段;然后在ArcGIS 10.2中获取每条线段的长度为便于后续盲道路径规划算法实现，为每条线段编号，并存储每条线段邻接的线号集合，线数据组织如表2所示。

为避免后续算法执行时每次都遍历所有线，每条路段都将被存储为一个独立的表，根据起点和终点的实际情况，对需要的盲道线数据进行数据调取，减少客户端访问服务器的次数，保证该系统的健壮性1.3.2用户数据组织用户信息表用来存储用户注册时提交的个人信息以及与用户绑定的紧急联系人的联系方式，为每一位用户分配唯一的用户ID来标识不同用户用户信息的存储结构如表3所示2 系统关键技术2.1 Socket通信技术本软件采用Socket（套接字）实现客户端与服务器端双向可靠连接的实时通信Socket是支持TCP/IP协议的网络通信的基本操作单元[4]，它是应用层与TCP/IP协议族通信的复杂操作抽象化的一组通信接口[5]，具有稳定、传输数据量小的特点，适合于客户端与服务器端之间的信息实时交互在通信过程中，客户端是主动的，服务端是被动的在服务端，首先创建服务器Socket对象，将其与一个特定地址（IP地址+端口号）绑定，服务端监听器持续监听该端口，等待客户端发送连接请求;在客户端，同样创建Socket对象，由连接服务器的线程connectThread向服务器发送连接请求，从而建立起二者连接此时，客户端可以向服务端请求盲道数据，服务端从数据库调出数据，并将其转换成字符串，由SendCallback（）函数调起数据发送线程将字符串发送给客户端，完成服务端与客户端的数据传输。

客户端的发送数据线程sendThread、接收数据线程ReceiveThread与服务器端的发送信息线程SendData、接受信息线程ReceiveCallback相互合作完成数据的传输Socket通信过程如图3所示2.2基于Dijkstra算法的盲道路径规划2.2.1 Dijkstra算法的基本原理Dijkstra算法是1959年由荷兰计算机科学家Dijkstra提出的图论中求最短路径的常用算法[6]该算法可求得图中一点到其他任一顶点的最短路径[7]它是求解单源最短路径问题所使用的最广泛和最经典的算法Dijkstra算法执行的基本步骤是：首先建立一个用于保存已找到最短路径的结点集合T和一个用于保存源结点[v0]到其余结点[vi]的最短距离的数组D，然后按以下步骤进行：1）初始化：遍历所有结点，初始化数组D，其中[v0]的最短路径被赋值为[D0=0]，对于[v0]能直接到达的点的最短路径[Di]赋值为[v0]与[vi]的距离，不能直接到达的结点的最短路径赋值为无穷大集合T初始化为[T=v0]2）更新结点集合T：从数组D中选取最小值，将该值对应的结点加入集合T中3）判断新加入集合T的结点是否有其他出度，若有，判断其最短路径是否比数组D中的值小，如果是，就替换数组D中的值。

4）重复2）、3），直至集合T包含所有结点2.2.2盲道最短路径规划在选取最短路径算法时，需要遵循以下3个原则：①算法运行速度快;②尽可能少地占用系统资源;③算法具有较好的稳定性[8]Dijkstra算法可以得出最短路径的最优解，但是由于它需要遍历计算所有结点，将每一个结点作为集合中的对象参与算法运算，所以在数据量繁多的时候运算速度不是很理想，效率相对较低为了在一定程度上提高算法的计算效率，我们将算法的输入集进行优化，将盲道路段抽象为结点，路段长度抽象为边同时需要保证每一条盲道线数据首尾相接，端点重合，使得抽象后的结点在算法空间中的数据意义保持不变抽象后就只需遍历线集而非点集，从而减少了算法运行时所需的数据量这样，原本的源结点就转变为抽象后的起点所在路段为实现在盲道上的导航，需要将盲人引导到盲道上，因此需要将整个导航路径分解成三部分：①盲人所在起点--盲道上起点;②盲道上起点--盲道上终点;③盲道上终点--目的地其中，①和③采用百度地图提供的找路算法，②采用本文提出的基于Dijkstra优化的盲道寻径算法盲道最短路径规划主要包括以下4个步骤：1）计算垂点获取盲人所在起点和终点后，计算两点到盲道线集中最邻近的路段的垂点d1、d2，并确定垂点所的线号及其相邻两点在该线段上的编号。

以d1、d2为分割点将所在路段分割为两条路段，得到新线集SLSL根据下一步骤寻径路线的顺逆情况而不同，本文研究区域内该线集共计30条线段，d1、d2分别作为盲道上的初始起点和初始终点2）当d1、d2在同一条路段上时，由d1、d2及其间结点组成初始寻径结果点集Rinitial当d1、d2不在同一条盲道路段上时，执行寻径算法由于线被抽象成点，纳入矩阵计算的线长按线段上点序分为顺序行走和逆序行走，两种不同的情况会导致线的邻接关系和路径长度发生改变因此我们将依据（1）中得到的新线集SL构建4个不同的邻接矩阵M，分别对应①d1所顺序走出，d2所顺序进入;②d1所顺序走出，d2所逆序进入;③d1所逆序走出，d2所顺序进入;④d1所逆序走出，d2所逆序进入四种情况因此，N×N的邻接矩阵M根据式（1）赋值：[Mij=∞ ，  li、lj不邻接|lj| ，  li、lj邻接i，j∈1，2，…，N]          。