曹夢凡 李佩玲 唐軻

摘要：針對盲人的出行需求，設(shè)計并開發(fā)了一款盲道導(dǎo)航軟件，引導(dǎo)盲人在盲道上行走，幫助盲人感知道路，保障盲人安全出行。該文首先介紹了該軟件的功能設(shè)計和數(shù)據(jù)組織方式。其次，就系統(tǒng)開發(fā)使用的關(guān)鍵技術(shù)，即Socket通信技術(shù)與基于Dijkstra算法的最短路徑規(guī)劃進行介紹。最后，使用該軟件在徐州選定的街區(qū)進行實地測試，探究軟件的可行性。

關(guān)鍵詞：盲道導(dǎo)航;Dijkstra算法;最短路徑規(guī)劃

中圖分類號：TP311? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）30-0082-04

開放科學(xué)（資源服務(wù)）標識碼（OSID）：

據(jù)相關(guān)數(shù)據(jù)統(tǒng)計，截至2018年中國盲人數(shù)量已達到1700萬人[1]。然而，我們在日常生活中很難看到盲人和視障患者的身影，出行難、出行機會少、出行范圍小已經(jīng)成為盲人群體亟待解決的問題。

人類獲取外部信息的最主要感官為視覺，因此視障人群很難判斷周圍物體的位置和相對關(guān)系，造成生活中的諸多不便[2]。如今盲人出行已有諸多無障礙設(shè)施和產(chǎn)品的幫助，但固定的無障礙設(shè)施使用場景限定，不足以滿足盲人的出行需求，這就需要便攜的導(dǎo)盲工具。當前盲人大多還是借助盲杖或?qū)と鲂?，市面上也開發(fā)出了多種導(dǎo)盲產(chǎn)品，例如電子導(dǎo)盲杖、導(dǎo)盲眼鏡、導(dǎo)盲機器人等[3]。盲杖簡單易使用，但功能單一，導(dǎo)盲犬靈活，但資源有限且受外界影響大，電子導(dǎo)盲產(chǎn)品設(shè)計先進、功能齊全，但價格昂貴，不足以普及。而導(dǎo)航系統(tǒng)操作方便、普及率高、成本低，為生活出行帶來了極大的便利。

針對盲人群體特殊的空間認知，綜合導(dǎo)航系統(tǒng)的優(yōu)點，本文旨在基于盲道建設(shè)上，專為盲人設(shè)計一款智能語音化的盲道導(dǎo)航系統(tǒng)，以解決盲人的出行問題，實現(xiàn)路徑引導(dǎo)，增強盲人的安全感與方向感。

1系統(tǒng)設(shè)計

1.1系統(tǒng)建設(shè)目標

通過外業(yè)調(diào)查、測繪采集以及內(nèi)業(yè)處理等工作，建立盲道地理空間數(shù)據(jù)庫，以該數(shù)據(jù)庫為基礎(chǔ)，依托計算機科學(xué)、地理信息系統(tǒng)（GIS）、移動互聯(lián)網(wǎng)等技術(shù)，設(shè)計并開發(fā)一套低成本、語音化的“基于路徑智能規(guī)劃的盲道搜索與導(dǎo)航系統(tǒng)”。該系統(tǒng)針對盲人設(shè)計，可以實現(xiàn)盲道路徑規(guī)劃與導(dǎo)航，通過設(shè)置常用地址簡化導(dǎo)航功能，在危險情況下可通過呼叫緊急聯(lián)系人和應(yīng)急報警功能實現(xiàn)盲人初步自救。本系統(tǒng)旨在解決盲人出行難、困難多、尋求幫助不便利的問題，為盲人出行提供便捷有力的服務(wù)。

1.2 系統(tǒng)功能設(shè)計

本盲道導(dǎo)航系統(tǒng)以百度地圖的Android地圖SDK、Android定位SDK為基礎(chǔ)，百度地圖SDK是基于Android開發(fā)語言編寫的應(yīng)用程序接口，在本項目中主要借助了地圖顯示、定位、點線繪制、路線規(guī)劃四項技術(shù)。

由于盲人對空間感知的不全面、對地理要素的認識缺少以及較低的應(yīng)急處理能力，盲人出行除了核心的盲道導(dǎo)航功能之外，他們還需要一些輔助功能來幫助他們在外行走時能夠應(yīng)對多變的環(huán)境狀況和不可預(yù)測的突發(fā)情況。因此，我們在結(jié)合現(xiàn)有導(dǎo)航軟件的基礎(chǔ)上，考慮到盲人群體的特殊性，簡化融合，在主菜單界面設(shè)計了以下五大主要功能：

1）發(fā)送位置信息

用戶可通過該功能向緊急聯(lián)系人以短信的形式發(fā)送實時位置信息。該功能利用Android中的SmsManager（短信管理器）管理短信操作，首先獲取收信人號碼和短信文字內(nèi)容包括時間、位置、經(jīng)度、緯度相關(guān)字符串，通過SmsManager類和sendTextMessage（）方法調(diào)用系統(tǒng)的短信接口進行短信發(fā)送，當用戶確認相關(guān)內(nèi)容后即發(fā)送給收信人。

2）當前位置播報

盲人無法以視覺方式去認識客觀世界，他們只能通過觸覺、聽覺等其他非視覺感知方式去獲取外界信息，因而，他們所感知的地理信息也與常人不同[1]。即使是弱視力的視障人士也很難在復(fù)雜的外界環(huán)境信息中準確地作出判斷，這些都極大程度地阻礙了他們在行走中判斷方位、獲取地理要素以及作出相應(yīng)反應(yīng)的能力。所以，對于盲人來說，知曉自己當前所處位置是十分重要的?！爱斍拔恢貌蟆惫δ苷{(diào)取用戶當前GPS定位信息，通過BDLocation類的各種getLatitude（）、getLongitude（）等get方法獲得一系列定位相關(guān)的全部結(jié)果，并以語音播報形式告知用戶，包括時間、位置、經(jīng)緯度。其中，語音播報采用Android原生的TTS（TextToSpeech）接口，其基本使用主要通過實例并初始化TTS對象，使用textToSpeech.speak（）方法進行簡單播報，并可用setPitch（）和setSpeechRate（）方法控制音調(diào)和語速。

3）選擇常用地址

鑒于盲人出行的不便利，他們出行往往去向幾處固定的地點。在系統(tǒng)設(shè)置中，允許盲人進行常用地址的編輯與存儲，添加方式分為手動輸入和設(shè)定當前位置為常用地址兩種方式。盲人在需要導(dǎo)航時可直接通過該功能呼出常用地址列表，選擇地址進行導(dǎo)航，提高便利性，高效完成固定路線的導(dǎo)航。

4）呼叫緊急聯(lián)系人

“呼叫緊急聯(lián)系人”功能幫助盲人在盲道導(dǎo)航中也能快速向緊急聯(lián)系人撥號，完成及時便捷的通話。該功能同樣使用Android平臺TelephonyManager（電話管理器）調(diào)用撥號器撥打指定電話號碼，主要為getSystemService（）獲得TelephonyManager的服務(wù)對象，將電話號碼轉(zhuǎn)為uri，實例化intent，設(shè)置ACTION_CALL和uri參數(shù)跳轉(zhuǎn)到撥號界面直接撥打電話。

5）應(yīng)急報警

考慮到盲人易遇危險以及遇到危險后難以尋求幫助的情況，我們設(shè)計了應(yīng)急報警的功能模塊。在該功能模塊中，盲人可向常用報警電話快速撥號。

1.3 數(shù)據(jù)庫設(shè)計

為實現(xiàn)盲道導(dǎo)航系統(tǒng)的導(dǎo)航功能和登錄等其他基本功能，本系統(tǒng)利用SQL Server數(shù)據(jù)庫存儲數(shù)據(jù)，主要包括地理空間數(shù)據(jù)庫和用戶數(shù)據(jù)庫。為方便測試，本項目團隊在江蘇省徐州市云龍湖景區(qū)東南方向的一個街區(qū)（34°13′7″N-34°13′41″N，117°9′8″E-117°10′1″E）采集盲道數(shù)據(jù)，該街區(qū)地圖如圖2所示。

1.3.1 地理空間數(shù)據(jù)組織

地理數(shù)據(jù)即為試驗區(qū)域采集所得的盲道上的點數(shù)據(jù)及其連成的盲道線數(shù)據(jù)。盲道上點數(shù)據(jù)是通過RTK（Real-time kinematic，實時動態(tài)載波相位差分測量技術(shù)）獲取的厘米級精度的數(shù)據(jù)，保證了盲道位置信息的準確性，從而一定程度上提高移動終端的定位精度。點數(shù)據(jù)組織結(jié)構(gòu)如表1所示，為保證點可被檢索，將點號設(shè)置為主鍵且作為唯一標識字段。

獲得的點數(shù)據(jù)按實際情況依順序連接得到盲道線數(shù)據(jù)，對該數(shù)據(jù)進行處理，在CAD中結(jié)合路的拐點和道路實際狀況將其打斷，最終在試驗區(qū)中得到30條盲道線段;然后在ArcGIS 10.2中獲取每條線段的長度。為便于后續(xù)盲道路徑規(guī)劃算法實現(xiàn)，為每條線段編號，并存儲每條線段鄰接的線號集合，線數(shù)據(jù)組織如表2所示。為避免后續(xù)算法執(zhí)行時每次都遍歷所有線，每條路段都將被存儲為一個獨立的表，根據(jù)起點和終點的實際情況，對需要的盲道線數(shù)據(jù)進行數(shù)據(jù)調(diào)取，減少客戶端訪問服務(wù)器的次數(shù)，保證該系統(tǒng)的健壯性。

1.3.2用戶數(shù)據(jù)組織

用戶信息表用來存儲用戶注冊時提交的個人信息以及與用戶綁定的緊急聯(lián)系人的聯(lián)系方式，為每一位用戶分配唯一的用戶ID來標識不同用戶。用戶信息的存儲結(jié)構(gòu)如表3所示。

2 系統(tǒng)關(guān)鍵技術(shù)

2.1 Socket通信技術(shù)

本軟件采用Socket（套接字）實現(xiàn)客戶端與服務(wù)器端雙向可靠連接的實時通信。Socket是支持TCP/IP協(xié)議的網(wǎng)絡(luò)通信的基本操作單元[4]，它是應(yīng)用層與TCP/IP協(xié)議族通信的復(fù)雜操作抽象化的一組通信接口[5]，具有穩(wěn)定、傳輸數(shù)據(jù)量小的特點，適合于客戶端與服務(wù)器端之間的信息實時交互。

在通信過程中，客戶端是主動的，服務(wù)端是被動的。在服務(wù)端，首先創(chuàng)建服務(wù)器Socket對象，將其與一個特定地址（IP地址+端口號）綁定，服務(wù)端監(jiān)聽器持續(xù)監(jiān)聽該端口，等待客戶端發(fā)送連接請求;在客戶端，同樣創(chuàng)建Socket對象，由連接服務(wù)器的線程connectThread向服務(wù)器發(fā)送連接請求，從而建立起二者連接。此時，客戶端可以向服務(wù)端請求盲道數(shù)據(jù)，服務(wù)端從數(shù)據(jù)庫調(diào)出數(shù)據(jù)，并將其轉(zhuǎn)換成字符串，由SendCallback（）函數(shù)調(diào)起數(shù)據(jù)發(fā)送線程將字符串發(fā)送給客戶端，完成服務(wù)端與客戶端的數(shù)據(jù)傳輸?？蛻舳说陌l(fā)送數(shù)據(jù)線程sendThread、接收數(shù)據(jù)線程ReceiveThread與服務(wù)器端的發(fā)送信息線程SendData、接受信息線程ReceiveCallback相互合作完成數(shù)據(jù)的傳輸。Socket通信過程如圖3所示。

2.2基于Dijkstra算法的盲道路徑規(guī)劃

2.2.1 Dijkstra算法的基本原理

Dijkstra算法是1959年由荷蘭計算機科學(xué)家Dijkstra提出的圖論中求最短路徑的常用算法[6]。該算法可求得圖中一點到其他任一頂點的最短路徑[7]。它是求解單源最短路徑問題所使用的最廣泛和最經(jīng)典的算法。

Dijkstra算法執(zhí)行的基本步驟是：首先建立一個用于保存已找到最短路徑的結(jié)點集合T和一個用于保存源結(jié)點[v0]到其余結(jié)點[vi]的最短距離的數(shù)組D，然后按以下步驟進行：

1）初始化：遍歷所有結(jié)點，初始化數(shù)組D，其中[v0]的最短路徑被賦值為[D0=0]，對于[v0]能直接到達的點的最短路徑[Di]賦值為[v0]與[vi]的距離，不能直接到達的結(jié)點的最短路徑賦值為無窮大。集合T初始化為[T=v0]。

2）更新結(jié)點集合T：從數(shù)組D中選取最小值，將該值對應(yīng)的結(jié)點加入集合T中。

3）判斷新加入集合T的結(jié)點是否有其他出度，若有，判斷其最短路徑是否比數(shù)組D中的值小，如果是，就替換數(shù)組D中的值。

4）重復(fù)2）、3），直至集合T包含所有結(jié)點。

2.2.2盲道最短路徑規(guī)劃

在選取最短路徑算法時，需要遵循以下3個原則：①算法運行速度快;②盡可能少地占用系統(tǒng)資源;③算法具有較好的穩(wěn)定性[8]。Dijkstra算法可以得出最短路徑的最優(yōu)解，但是由于它需要遍歷計算所有結(jié)點，將每一個結(jié)點作為集合中的對象參與算法運算，所以在數(shù)據(jù)量繁多的時候運算速度不是很理想，效率相對較低。

為了在一定程度上提高算法的計算效率，我們將算法的輸入集進行優(yōu)化，將盲道路段抽象為結(jié)點，路段長度抽象為邊。同時需要保證每一條盲道線數(shù)據(jù)首尾相接，端點重合，使得抽象后的結(jié)點在算法空間中的數(shù)據(jù)意義保持不變。抽象后就只需遍歷線集而非點集，從而減少了算法運行時所需的數(shù)據(jù)量。這樣，原本的源結(jié)點就轉(zhuǎn)變?yōu)槌橄蠛蟮钠瘘c所在路段。

為實現(xiàn)在盲道上的導(dǎo)航，需要將盲人引導(dǎo)到盲道上，因此需要將整個導(dǎo)航路徑分解成三部分：①盲人所在起點--盲道上起點;②盲道上起點--盲道上終點;③盲道上終點--目的地。其中，①和③采用百度地圖提供的找路算法，②采用本文提出的基于Dijkstra優(yōu)化的盲道尋徑算法。

盲道最短路徑規(guī)劃主要包括以下4個步驟：

1）計算垂點。獲取盲人所在起點和終點后，計算兩點到盲道線集中最鄰近的路段的垂點d1、d2，并確定垂點所在線的線號及其相鄰兩點在該線段上的編號。以d1、d2為分割點將所在路段分割為兩條路段，得到新線集SL。SL根據(jù)下一步驟尋徑路線的順逆情況而不同，本文研究區(qū)域內(nèi)該線集共計30條線段，d1、d2分別作為盲道上的初始起點和初始終點。

2）當d1、d2在同一條路段上時，由d1、d2及其間結(jié)點組成初始尋徑結(jié)果點集Rinitial。當d1、d2不在同一條盲道路段上時，執(zhí)行尋徑算法。由于線被抽象成點，納入矩陣計算的線長按線段上點序分為順序行走和逆序行走，兩種不同的情況會導(dǎo)致線的鄰接關(guān)系和路徑長度發(fā)生改變。因此我們將依據(jù)（1）中得到的新線集SL構(gòu)建4個不同的鄰接矩陣M，分別對應(yīng)①d1所在線順序走出，d2所在線順序進入;②d1所在線順序走出，d2所在線逆序進入;③d1所在線逆序走出，d2所在線順序進入;④d1所在線逆序走出，d2所在線逆序進入四種情況。因此，N×N的鄰接矩陣M根據(jù)式（1）賦值：

[Mij=∞ ，? li、lj不鄰接|lj| ，? li、lj鄰接i，j∈1，2，…，N]? ? ? ? ? ?（1）

其中[li、lj]為任意兩條盲道路段，[|lj|]為[lj]路段的長度，N為總路段數(shù)。

生成鄰接矩陣后依照傳統(tǒng)Dijkstra算法獲得最短路徑樹，將初始尋徑結(jié)果點集Rinitial連成線即為初始導(dǎo)航路徑。

此時，將該盲道導(dǎo)航路徑與盲道外的百度尋徑結(jié)果拼接，理論上拼接結(jié)果即為用戶起點到目的地的完整導(dǎo)航路徑。但經(jīng)測試發(fā)現(xiàn)，由于百度地圖導(dǎo)航的數(shù)據(jù)源中并不包含盲道數(shù)據(jù)，拼接結(jié)果可能存在路徑相交或重疊的情況，如圖4所示。因此，執(zhí)行步驟3）及步驟4），對該導(dǎo)航路徑進行調(diào)整。

（藍色點：用戶導(dǎo)航起點;藍色線：百度導(dǎo)航路徑;紅色：盲道路徑）

3）計算初始導(dǎo)航路徑的頭尾分別與百度地圖的尋徑結(jié)果的第一個交點，將兩個交點定義為盲道上的新起點[d1']和新終點[d2']。

4）根據(jù)[d1']、[d2']，重新生成結(jié)果集，得到更新后的尋徑結(jié)果Rupdate，將其與百度尋徑結(jié)果拼接，將最終導(dǎo)航結(jié)果點集Rfinal可視化。

盲道路徑規(guī)劃的流程圖如圖5所示。

對于結(jié)點數(shù)量為n的圖，傳統(tǒng)Dijkstra算法求解最短路徑需要迭代n-1次，在最差情況下的時間復(fù)雜度為[On2]。以本文研究區(qū)域為例，共計188個結(jié)點，30條盲道路段。則優(yōu)化輸入集的Dijkstra算法的時間復(fù)雜度為8×[O302]，而Dijkstra算法的時間復(fù)雜度為O（[1882]），可見優(yōu)化后的算法時間復(fù)雜度更低，計算機執(zhí)行算法的工作量更小。

3 系統(tǒng)測試

基于以上研究和技術(shù)支持，我們設(shè)計開發(fā)了一套具有語音功能、盲道尋找、應(yīng)急報警處理等功能的盲道搜索與導(dǎo)航系統(tǒng)，并于實地進行系統(tǒng)測試。研究范圍為江蘇省徐州市泉山區(qū)金山南路、金山東路、泰山路、三環(huán)南路之間約占1.2平方公里的區(qū)域（圖2），該區(qū)域內(nèi)有許多居民小區(qū)、社會福利院、派出所、文娛場所，大部分街道較為開闊，連接道路之間有必要的斑馬線，盲道相對完整和連續(xù)。

安裝該App到手機并打開，在用戶允許相關(guān)權(quán)限后，進入地圖顯示界面并定位到用戶當前位置，在上方輸入框中輸入導(dǎo)航目的地，點擊“導(dǎo)航”按鈕即開始路徑導(dǎo)航，在導(dǎo)航過程中，系統(tǒng)會根據(jù)用戶實時位置進行語音提醒，為用戶提供基礎(chǔ)的路徑語音導(dǎo)航。點擊“菜單”呼出主菜單界面，如圖6，我們?yōu)槊總€功能按鈕分配足夠大的屏幕占比，便于盲人進行操作。

實地系統(tǒng)測試中，在范圍內(nèi)隨機選擇兩處地點分別作為起點和終點，進行盲道路徑導(dǎo)航。例如，我們以金山花園小區(qū)內(nèi)某一居民樓為起點，以龍潤山莊為終點，此次盲道路徑規(guī)劃的導(dǎo)航路線如圖7所示。在整個導(dǎo)航過程中，主要在基礎(chǔ)導(dǎo)航、道路變向、偏離路線、達到終點這些情況下對用戶進行語音提示，見表4。

在本次測試過程中，能較好地完成用戶起點到盲道的引導(dǎo)、盲道上的路徑規(guī)劃和導(dǎo)航以及最后到目的地終點的路線，在導(dǎo)航中同時有輔助語音播報，提醒用戶方位和距離等，進而完成路線引導(dǎo)。

4 結(jié)束語

綜合利用RTK高精度定位、衛(wèi)星定位、基于Dijkstra的最短路徑規(guī)劃、Socket通信等技術(shù)開發(fā)移動端盲人導(dǎo)航系統(tǒng)，引導(dǎo)盲人在盲道上安全行走。除基礎(chǔ)盲道導(dǎo)航功能外，還為該類特殊用戶群體提供實時位置反饋、常用地址設(shè)置、緊急聯(lián)系人呼叫、應(yīng)急報警等服務(wù)，方便盲人使用并為盲人出行提供有力的安全保障。

本系統(tǒng)進行盲道最短路徑規(guī)劃時優(yōu)化了輸入集，在經(jīng)典Dijkstra算法的基礎(chǔ)上，將線要素抽象成點要素，提高了算法的運算效率，降低了求解最短路徑的時間復(fù)雜度。本系統(tǒng)可有效幫助盲人出行，降低他們的出行困擾，實現(xiàn)路徑引導(dǎo)，增強盲人的安全感、方向感，使盲人的空間認知更清晰，具有較好的應(yīng)用價值。可針對不同地區(qū)的城市發(fā)展情況、道路環(huán)境以及盲道的設(shè)置擴展和調(diào)整系統(tǒng)，在實踐中改進和提高，向?qū)嵱没较蚺Α?/p>

參考文獻：

[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] 寇樹芳，武帥.無障礙設(shè)計中的盲人用戶產(chǎn)品研究[J].科教導(dǎo)刊（上旬刊），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（跨國電氣電子工程師學(xué)會北京分會），2011：4.

[5] 甄泰航.基于Socket通信的社交應(yīng)用軟件[J].電子技術(shù)與軟件工程，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算法優(yōu)化及在GIS系統(tǒng)中求最佳路徑的應(yīng)用[J].遙感技術(shù)與應(yīng)用，2013，28（5）：866-870.

[8] 李元臣，劉維群.基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析[J].微計算機應(yīng)用，2004（3）：295-298，362.

【通聯(lián)編輯：代影】