基于二維碼和A*算法的室內精準定位導航系統

吳友寶，徐建閩

（華南理工大學 土木與交通學院，廣東 廣州 510640）

基于二維碼和A*算法的室內精準定位導航系統

吳友寶，徐建閩

（華南理工大學 土木與交通學院，廣東 廣州 510640）

隨著移動互聯網的迅猛發展，基于位置的服務LBS（Location Based Services）在現代人的生活中起著至關重要的作用。由于室內環境無法精確獲取GPS數據，導致室內定位的需求一直得不到滿足。在歷時一個月調研了各階層有代表性的智能手機用戶的前提下，此文提出了基于二維碼的室內精準定位技術，以及基于A*算法的室內語音導航技術。利用AutoCAD、PhotoShop和3DMax等軟件設計室內平面圖，并在當前流行的Android智能手機平臺下，設計開發了基于二維碼和A*算法的室內定位系統。實際應用表明，該系統具有精準定位、人性導航和豐富信息的三大基礎功能，能夠滿足人們日常在大型公共建筑中的基本需求。

二維碼；A*算法；室內定位；室內導航；智能手機

隨著移動互聯網的快速發展，基于位置的服務 LBS（Location Based Services）廣泛應用于個人定位、貨物跟蹤和汽車導航等各個領域[1]。通過全球衛星定位系統（GPS）可實現室外定位服務，但在室內環境下無法接受GPS信號。由于停車場、大型商場、醫院、圖書館等公共建筑越來越趨向于大型化，導致人們在室內時無法準確獲取所在位置和目的地方位，在室內活動經常遇到種種不便。如果室內定位服務能夠精準地獲取地理位置，并且提供準確的室內導航，將為人們室內活動帶來極大的方便。

目前，基于室內的定位技術已有大量的研究成果。R.Want等提出了基于紅外線的室內定位技術，因傳播距離短不適合大規模應用[2]。S.T.Shih等提出了基于無線射頻識別的室內定位技術，因RFID標簽默認不提供信號強度信息，需要進行手工估計，造成誤差較大[3]。結合被動RFID標簽和WiFi RSSI信號，Y.C.Chen[4]提出了能夠在不同環境下在線標定多個射頻圖的自適應方法，精度雖達到2.13～2.81米，但部署環境時需要安裝額外的RFID閱讀器。谷歌手機地圖依靠GPS（室內一般也能搜索到2～3顆衛星）、WiFi信號、手機基站以及根據一些“盲點”（室內無GPS、WiFi或基站信號的地方）的具體位置實現室內定位，但存在著3～5 m的定位誤差，且成本非常高[5]。

針對大型超市、公共場所、大型商場、醫院、停車場、圖書館等室內建筑無法獲取 GPS數據、WiFi信號定位誤差大、RFID標簽部署復雜且成本高等現狀，此文運用現今流行的Android操作系統，設計開發了基于二維碼和A*算法[6-7]的室內定位系統，具有精準定位、人性導航和豐富信息的3大基礎功能，能夠滿足人們日常在大型公共建筑中的基本需求。該系統主要優勢包括：1）通過識別室內建筑部署的二維碼實現定位，定位精度接近100%；2）基于A*算法和錄制好的離線語音包實現室內導航；3）部署二維碼靈活、方便，無需安裝額外硬件來實現定位和導航，成本低；4）由于算法上不沖突，通過將二維碼定位技術與現有室內定位技術如WiFi等相結合，達到優劣互補的效果。綜上所述，該系統具有很大的實用價值。

1 基于室內定位需求的用戶調研分析

為了解各階層有代表性的用戶對室內定位服務的需求，此文選擇在網上發布問卷調查。由于態度8調查網是中國第一家自助網絡調查互動平臺，提供專業的在線調查系統和權威的調查報告，因此選擇在該網站發布調研。在歷時一個月的調研中，共收回4 937份有效問卷。

通過調研發現，對于室內定位服務有非常大的市場需求，并且大部分用戶可以接受掃描二維碼的方式來獲取定位。用戶最需要的功能正好是二維碼定位技術的優勢所在[8-9]，而用戶需求不大的功能正好是二維碼定位技術的缺點[10-11]。因此，在設計系統時應充分考慮用戶的各項需求，實現服務用戶、便利生活的宗旨。

2 室內平面圖信息處理設計

2.1 室內平面圖信息處理方式

室內平面圖里蘊含和處理信息的方式有很多種類，該系統采用的室內平面圖[12-13]主要遵循以下幾個原則。

1）信息根據重要程度而設置相應的處理方式；

2）信息處理的目的是讓信息更加直觀明了，靈活地對信息進行使用顏色處理；

3）盡量讓系統界面保持簡潔，詳細信息可以通過超鏈接跳轉；

4）盡量讓用戶操作簡單方便。

2.2 室內平面圖信息分層處理技術

在室內平面圖顯示的過程中，當平面圖縮小時，屏幕呈現的范圍會放大，此時可以隱藏次要信息，顯示主要圖像信息。反之，當室內平面圖放大時，屏幕呈現的范圍會縮小，此時將相對次要的信息也顯示出來，更加反映室內平面圖的細節。

基于上述特征，該系統將室內平面圖的信息按照重要程度分成了2個數據層次，即對所需顯示的室內平面圖按照圖層的重要程度設置顯示參數，根據閾值控制是否顯示該圖層。劃分的地圖數據層次依次記為L1和L2，其中L1的圖層信息表示用戶最想了解的信息，如廁所、出入口、電梯等位置信息；L2表示從基本信息擴展的詳細信息，如商家促銷信息、醫院醫生的值班時間等。

3 二維碼部署方案設計

3.1 二維碼特性

確定二維碼部署位置前，需了解其特性[14-15]。

1）建設投入少。二維碼部署經濟，不需要購置專用軟硬件環境及設備；

2）不易受干擾。二維碼不依賴于無線電信號強度信息，不易受人活動和等社會動力學因素變化干擾；

3）方便快捷。二維碼標簽可采用普通打印紙，既可自行打印張貼于室內地面和墻上，也可通過屏幕設備進行顯示；

4）靈活性強。在實際使用過程中，可根據使用反饋情況增減導向標簽。根據系統使用統計，對于很少或者沒有被讀者掃描的標簽，可將其從系統中刪除。通過與讀者溝通，在適當的場所位置增加導視標簽。

3.2 二維碼部署方案

經過用戶調研反饋的結果，發現大部分用戶對實時定位的需求不大。因此，可以通過二維碼技術，在每一個重要的物理標識或其他關鍵位置點附上二維碼。用戶在查看物理標識系統時，通過手機掃描二維碼，便能訪問室內平面圖導向標識系統。

二維碼的部署不僅僅限于粘貼在墻上、柱子、地板、懸掛在過道或者展板上，形式非常多樣。對用戶而言，使用方便與否是評價系統好與壞最重要的標準。因此，二維碼要貼在顯而易見的地方。

綜上所述，二維碼的部署方案如表1所示。

表1 二維碼部署方案

4 系統設計與實現

4.1 室內平面圖設計

此文選擇Autodesk公司計算機輔助設計產品AutoCAD作為室內平面圖的設計。經過PhotoShop和3DMax美化后，能夠清晰直觀地展現室內建筑，滿足用戶的審美需求，如圖1所示。

在制作室內平面圖之前，需要充分考慮室內平面圖信息處理設計遵循的基本原則，以及圖層信息分層處理技術，詳見章節2。由于AutoCAD輸出的是位圖，為了便于后續處理，需通過PhotoShop將背景圖層變為白色，然后使用3DMax進行渲染，最后輸出用于室內定位導航的室內平面圖。

4.2 二維碼部署設計

考慮到二維碼部署的方案設計，應將其粘貼在顯而易見的位置，詳見章節3。部署完畢后，標記各個二維碼在室內平面圖中對應的地理位置。進一步的統計后，制作相應表并存儲到sqlite輕量級數據庫，實現用戶本地查詢位置信息。

圖1 室內平面圖

4.3 系統整體架構設計

此文采用二維碼生成器生成特定編碼規則的二維碼圖片，然后通過二維碼識別軟件對攜帶定位信息的二維碼圖片進行解碼并獲取超鏈接，接著利用此超鏈接訪問后臺搭建的Web服務器，訪問文件服務器并返回與二維碼對應的室內平面圖，最后在室內平面圖的基礎上進行二次開發，實現基于A*算法的離線語音導航功能。該系統具體架構設計如圖2、圖3所示。

圖2 系統整體架構設計

圖3 系統后臺架構設計

4.4 系統實現

此文基于當今流行的Android操作系統，采用Java語言，開發出一套基于二維碼和A*算法的室內精準定位導航系統。該系統的操作主界面如圖4所示，具體操作流程如下。

1）進入二維碼掃描界面，此時將攝像頭對準室內部署的二維碼即可；

2）當成功識別二維碼圖片后，跳轉下一個界面，屏幕中間彈出相應的室內平面圖；

3）用戶可在搜索欄輸入想要尋找的服務場所，如衛生間、打印店等，室內平面圖里高亮顯示對應場所；

4）當用戶點擊這些場所時，系統開始提供離線語音導航服務。

圖4 系統主界面

5 結 論

對于用戶來說，室內定位系統能節省時間和精力，還能及時了解各場所最新資訊，擁有更佳的室內體驗。此文基于用戶調研情況，“以精確定位為基礎功能，導航為輔助功能，其他擴展信息為附加功能”的設計理念，提出了基于手機二維碼和A*算法的室內精準定位導航系統。在滿足用戶對定位和導航的基本需求前提下，提供用戶對附加功能的擴展需求，可廣泛應用于大型超市、公共場所、大型商場、醫院、停車場、圖書館等室內建筑，具有良好的實用價值。

在人力資源不足的情況下，部分功能未能完全實現，以下幾點需要進一步完善。

1）增加離線保存地圖的功能，讓用戶在離線情況下也能實現精確定位。

2）提供資訊平臺，讓物業管理人員實時發布室內場所的最新消息。

3）對外提供接口，讓合作方實時更新室內平面圖信息。

[1]周傲英，楊彬，金澈清，等.基于位置的服務:架構與進展[J].計算機學報，2011，34（7）:1155-1171.

[2]Want R，HoPPer A，Faleao V.The active badge location system[J].ACM Transactions on Information System，1992，10（1）:91-100.

[3]Shih ST，Hsieh K，Chen PY.An improvement approach ofindoor location sensing using active RFID[C]//Proceedings of the 1st Intemational Conference on Innovative Computing，Information and Control，IEEE，2006:453-459.

[4]Chen YC，Chiang JR，ChuH，et al.Sensor-Assisted Wi-Fi Indoor Location System for Adapting to Environmental Dynamics[C]//ACM international symposium on modeling，analysis and simulation of wireless and mobile systems，2005: 118-125.

[5]Ibrahim A，Ibrahim D.Real-time GPS based outdoor WiFi localization system with map display[J].Advances in Engineering Software，2010，41（9）:1080-1086.

[6]Fei Xu.QR Codes and library bibliographic records[J].VINE，2014，44（3）:345-356.

[7]錢紅昇，葛文鋒，鐘鳴，等.基于分層的改進A*算法在路徑規劃中的應用[J].計算機工程與應用，2014（7）:225-229.

[8]Yucheng Guo，Lei Cao.Study of location and navigation services in complex indoor scenes based on the Android mobile computing platform[J].Proceedings-11th International Symposium on Distributed Computing and Applications to Business，Engineering and Science，2012:91-93.

[9]胡天琨.基于Android的室內導航定位系統設計與實現[D].上海：東華大學，2013.

[10]陳文建，王曉蒙，彭玲，等.一種基于二維碼的室內定位方法[J].測繪科學，2016（7）:1-8.

[11]任豪毅.基于二維碼的智能手機室內定位方法[D].杭州：浙江大學，2013.

[12]史曉云.室內平面效果圖制作方法探究[J].長江大學學報：自然版，2011，8（6）:95-98.

[13]武敏杰.AutoCA D平面制圖的教學改革與探索[J].無線互聯科技，2015（1）:236-236.

[14]宮雪.QR二維碼個性化設計及其應用研究[D].北京：北京工業大學，2015.

[15]徐玲，蔣欣志，張杰，等.手機二維碼識別系統的設計與實現[J].計算機應用，2012，32（5）:1474-1476.

The indoor precise location and navigation system based on two-dimensional code and A*algorithm

WU You-bao，XU Jian-min
（School of Civil Engineering and Transportation，South China University of Technology，Guangzhou 510640，China）

With the rapid development of mobile Internet，the Location-Based Services（LBS）play a vital role in modern life. Due to unable to accept the GPS data in the indoor environment，the indoor location technology has been unable to meet demand.This paper put forward the indoor precise location technology based on two-dimensional code and the indoor voice navigation technology based on A*algorithm，after investigating all levels of representative smart phone users for a whole month.This paper designed interior plan through the AutoCAD，PhotoShop and 3DMax.And based on the Android mobile phone system which is popular all over the world，this paper designed and developed the indoor precise location and navigation system based on two-dimensional code and A*algorithm.The practical applications show that with three basic functions of precise location，user-friendly navigation and a wealth of information，this system can satisfy the basic requirements in the large public buildings in daily life.

two-dimensional code；A*algorithm；indoor location；indoor navigation；smart phone

TN929.53

A

1674－6236（2016）23-0023-03

2016-03-22稿件編號：201603298

國家自然科學基金資助項目（61174184）

吳友寶（1990—），男，廣東梅州人，碩士研究生。研究方向：交通與計算機。