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

曹梦凡 李佩玲 唐轲

摘要：针对盲人的出行需求，设计并开发了一款盲道导航软件，引导盲人在盲道上行走，帮助盲人感知道路，保障盲人安全出行。该文首先介绍了该软件的功能设计和数据组织方式。其次，就系统开发使用的关键技术，即Socket通信技术与基于Dijkstra算法的最短路径规划进行介绍。最后，使用该软件在徐州选定的街区进行实地测试，探究软件的可行性。

关键词：盲道导航;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为分割点将所在路段分割为两条路段，得到新线集SL。SL根据下一步骤寻径路线的顺逆情况而不同，本文研究区域内该线集共计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]           （1）

其中[li、lj]为任意两条盲道路段，[|lj|]为[lj]路段的长度，N为总路段数。

生成邻接矩阵后依照传统Dijkstra算法获得最短路径树，将初始寻径结果点集Rinitial连成线即为初始导航路径。

此时，将该盲道导航路径与盲道外的百度寻径结果拼接，理论上拼接结果即为用户起点到目的地的完整导航路径。但经测试发现，由于百度地图导航的数据源中并不包含盲道数据，拼接结果可能存在路径相交或重叠的情况，如图4所示。因此，执行步骤3）及步骤4），对该导航路径进行调整。

（蓝色点：用户导航起点;蓝色线：百度导航路径;红色：盲道路径）

3）计算初始导航路径的头尾分别与百度地图的寻径结果的第一个交点，将两个交点定义为盲道上的新起点[d1']和新终点[d2']。

4）根据[d1']、[d2']，重新生成结果集，得到更新后的寻径结果Rupdate，将其与百度寻径结果拼接，将最终导航结果点集Rfinal可视化。

盲道路径规划的流程图如图5所示。

对于结点数量为n的图，传统Dijkstra算法求解最短路径需要迭代n-1次，在最差情况下的时间复杂度为[On2]。以本文研究区域为例，共计188个结点，30条盲道路段。则优化输入集的Dijkstra算法的时间复杂度为8×[O302]，而Dijkstra算法的时间复杂度为O（[1882]），可见优化后的算法时间复杂度更低，计算机执行算法的工作量更小。

3 系统测试

基于以上研究和技术支持，我们设计开发了一套具有语音功能、盲道寻找、应急报警处理等功能的盲道搜索与导航系统，并于实地进行系统测试。研究范围为江苏省徐州市泉山区金山南路、金山东路、泰山路、三环南路之间约占1.2平方公里的区域（图2），该区域内有许多居民小区、社会福利院、派出所、文娱场所，大部分街道较为开阔，连接道路之间有必要的斑马线，盲道相对完整和连续。

安装该App到手机并打开，在用户允许相关权限后，进入地图显示界面并定位到用户当前位置，在上方输入框中输入导航目的地，点击“导航”按钮即开始路径导航，在导航过程中，系统会根据用户实时位置进行语音提醒，为用户提供基础的路径语音导航。点击“菜单”呼出主菜单界面，如图6，我们为每个功能按钮分配足够大的屏幕占比，便于盲人进行操作。

实地系统测试中，在范围内随机选择两处地点分别作为起点和终点，進行盲道路径导航。例如，我们以金山花园小区内某一居民楼为起点，以龙润山庄为终点，此次盲道路径规划的导航路线如图7所示。在整个导航过程中，主要在基础导航、道路变向、偏离路线、达到终点这些情况下对用户进行语音提示，见表4。

在本次测试过程中，能较好地完成用户起点到盲道的引导、盲道上的路径规划和导航以及最后到目的地终点的路线，在导航中同时有辅助语音播报，提醒用户方位和距离等，进而完成路线引导。

4 结束语

综合利用RTK高精度定位、卫星定位、基于Dijkstra的最短路径规划、Socket通信等技术开发移动端盲人导航系统，引导盲人在盲道上安全行走。除基础盲道导航功能外，还为该类特殊用户群体提供实时位置反馈、常用地址设置、紧急联系人呼叫、应急报警等服务，方便盲人使用并为盲人出行提供有力的安全保障。

本系统进行盲道最短路径规划时优化了输入集，在经典Dijkstra算法的基础上，将线要素抽象成点要素，提高了算法的运算效率，降低了求解最短路径的时间复杂度。本系统可有效帮助盲人出行，降低他们的出行困扰，实现路径引导，增强盲人的安全感、方向感，使盲人的空间认知更清晰，具有较好的应用价值。可针对不同地区的城市发展情况、道路环境以及盲道的设置扩展和调整系统，在实践中改进和提高，向实用化方向努力。

参考文献：

[1] 翁宝凤，罗秀锋.盲人地理空间认知的研究[J].测绘与空间地理信息，2020，43（11）：15-18.

[2] Fernandes H，Concei??o N，Paredes H，et al.Providing accessibility to blind people using GIS[J].Universal Access in the Information Society，2012，11（4）：399-407.

[3] 寇树芳，武帅.无障碍设计中的盲人用户产品研究[J].科教导刊（上旬刊），2013（13）：171-172.

[4]Bo Li.Department of Computer Science，Chongqing Education College. Design and Implementation of Web-based Laboratory Management System in Colleges and Universities[C]//. IEEE、IACSIT.Proceedings of 2011 3rd International Conference on Computer Research and Development（ICCRD 2011） VOL.02.IEEE、IACSIT：IEEE BEIJING SECTION（跨国电气电子工程师学会北京分会），2011：4.

[5] 甄泰航.基于Socket通信的社交应用软件[J].电子技术与软件工程，2020（16）：30-33.

[6] Dijkstra E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）：269-271.

[7] 苏宝莉，李宁.Dijkstra算法优化及在GIS系统中求最佳路径的应用[J].遥感技术与应用，2013，28（5）：866-870.

[8] 李元臣，刘维群.基于Dijkstra算法的网络最短路径分析[J].微计算机应用，2004（3）：295-298，362.

【通联编辑：代影】