基于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（）函數調起數據發送線程將字符串發送給客戶端，完成服務端與客戶端的數據傳輸?？蛻舳说陌l送數據線程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.

【通聯編輯：代影】