基于二維碼和A*算法的室內(nèi)精準(zhǔn)定位導(dǎo)航系統(tǒng)

吳友寶，徐建閩

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

基于二維碼和A*算法的室內(nèi)精準(zhǔn)定位導(dǎo)航系統(tǒng)

吳友寶，徐建閩

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

隨著移動(dòng)互聯(lián)網(wǎng)的迅猛發(fā)展，基于位置的服務(wù)LBS（Location Based Services）在現(xiàn)代人的生活中起著至關(guān)重要的作用。由于室內(nèi)環(huán)境無法精確獲取GPS數(shù)據(jù)，導(dǎo)致室內(nèi)定位的需求一直得不到滿足。在歷時(shí)一個(gè)月調(diào)研了各階層有代表性的智能手機(jī)用戶的前提下，此文提出了基于二維碼的室內(nèi)精準(zhǔn)定位技術(shù)，以及基于A*算法的室內(nèi)語音導(dǎo)航技術(shù)。利用AutoCAD、PhotoShop和3DMax等軟件設(shè)計(jì)室內(nèi)平面圖，并在當(dāng)前流行的Android智能手機(jī)平臺下，設(shè)計(jì)開發(fā)了基于二維碼和A*算法的室內(nèi)定位系統(tǒng)。實(shí)際應(yīng)用表明，該系統(tǒng)具有精準(zhǔn)定位、人性導(dǎo)航和豐富信息的三大基礎(chǔ)功能，能夠滿足人們?nèi)粘Ｔ诖笮凸步ㄖ械幕拘枨蟆?/p>

二維碼；A*算法；室內(nèi)定位；室內(nèi)導(dǎo)航；智能手機(jī)

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

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

針對大型超市、公共場所、大型商場、醫(yī)院、停車場、圖書館等室內(nèi)建筑無法獲取 GPS數(shù)據(jù)、WiFi信號定位誤差大、RFID標(biāo)簽部署復(fù)雜且成本高等現(xiàn)狀，此文運(yùn)用現(xiàn)今流行的Android操作系統(tǒng)，設(shè)計(jì)開發(fā)了基于二維碼和A*算法[6-7]的室內(nèi)定位系統(tǒng)，具有精準(zhǔn)定位、人性導(dǎo)航和豐富信息的3大基礎(chǔ)功能，能夠滿足人們?nèi)粘Ｔ诖笮凸步ㄖ械幕拘枨蟆Ｔ撓到y(tǒng)主要優(yōu)勢包括：1）通過識別室內(nèi)建筑部署的二維碼實(shí)現(xiàn)定位，定位精度接近100%；2）基于A*算法和錄制好的離線語音包實(shí)現(xiàn)室內(nèi)導(dǎo)航；3）部署二維碼靈活、方便，無需安裝額外硬件來實(shí)現(xiàn)定位和導(dǎo)航，成本低；4）由于算法上不沖突，通過將二維碼定位技術(shù)與現(xiàn)有室內(nèi)定位技術(shù)如WiFi等相結(jié)合，達(dá)到優(yōu)劣互補(bǔ)的效果。綜上所述，該系統(tǒng)具有很大的實(shí)用價(jià)值。

1 基于室內(nèi)定位需求的用戶調(diào)研分析

為了解各階層有代表性的用戶對室內(nèi)定位服務(wù)的需求，此文選擇在網(wǎng)上發(fā)布問卷調(diào)查。由于態(tài)度8調(diào)查網(wǎng)是中國第一家自助網(wǎng)絡(luò)調(diào)查互動(dòng)平臺，提供專業(yè)的在線調(diào)查系統(tǒng)和權(quán)威的調(diào)查報(bào)告，因此選擇在該網(wǎng)站發(fā)布調(diào)研。在歷時(shí)一個(gè)月的調(diào)研中，共收回4 937份有效問卷。

通過調(diào)研發(fā)現(xiàn)，對于室內(nèi)定位服務(wù)有非常大的市場需求，并且大部分用戶可以接受掃描二維碼的方式來獲取定位。用戶最需要的功能正好是二維碼定位技術(shù)的優(yōu)勢所在[8-9]，而用戶需求不大的功能正好是二維碼定位技術(shù)的缺點(diǎn)[10-11]。因此，在設(shè)計(jì)系統(tǒng)時(shí)應(yīng)充分考慮用戶的各項(xiàng)需求，實(shí)現(xiàn)服務(wù)用戶、便利生活的宗旨。

2 室內(nèi)平面圖信息處理設(shè)計(jì)

2.1 室內(nèi)平面圖信息處理方式

室內(nèi)平面圖里蘊(yùn)含和處理信息的方式有很多種類，該系統(tǒng)采用的室內(nèi)平面圖[12-13]主要遵循以下幾個(gè)原則。

1）信息根據(jù)重要程度而設(shè)置相應(yīng)的處理方式；

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

3）盡量讓系統(tǒng)界面保持簡潔，詳細(xì)信息可以通過超鏈接跳轉(zhuǎn)；

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

2.2 室內(nèi)平面圖信息分層處理技術(shù)

在室內(nèi)平面圖顯示的過程中，當(dāng)平面圖縮小時(shí)，屏幕呈現(xiàn)的范圍會(huì)放大，此時(shí)可以隱藏次要信息，顯示主要圖像信息。反之，當(dāng)室內(nèi)平面圖放大時(shí)，屏幕呈現(xiàn)的范圍會(huì)縮小，此時(shí)將相對次要的信息也顯示出來，更加反映室內(nèi)平面圖的細(xì)節(jié)。

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

3 二維碼部署方案設(shè)計(jì)

3.1 二維碼特性

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

1）建設(shè)投入少。二維碼部署經(jīng)濟(jì)，不需要購置專用軟硬件環(huán)境及設(shè)備；

2）不易受干擾。二維碼不依賴于無線電信號強(qiáng)度信息，不易受人活動(dòng)和等社會(huì)動(dòng)力學(xué)因素變化干擾；

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

4）靈活性強(qiáng)。在實(shí)際使用過程中，可根據(jù)使用反饋情況增減導(dǎo)向標(biāo)簽。根據(jù)系統(tǒng)使用統(tǒng)計(jì)，對于很少或者沒有被讀者掃描的標(biāo)簽，可將其從系統(tǒng)中刪除。通過與讀者溝通，在適當(dāng)?shù)膱鏊恢迷黾訉?dǎo)視標(biāo)簽。

3.2 二維碼部署方案

經(jīng)過用戶調(diào)研反饋的結(jié)果，發(fā)現(xiàn)大部分用戶對實(shí)時(shí)定位的需求不大。因此，可以通過二維碼技術(shù)，在每一個(gè)重要的物理標(biāo)識或其他關(guān)鍵位置點(diǎn)附上二維碼。用戶在查看物理標(biāo)識系統(tǒng)時(shí)，通過手機(jī)掃描二維碼，便能訪問室內(nèi)平面圖導(dǎo)向標(biāo)識系統(tǒng)。

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

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

表1 二維碼部署方案

4 系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

4.1 室內(nèi)平面圖設(shè)計(jì)

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

在制作室內(nèi)平面圖之前，需要充分考慮室內(nèi)平面圖信息處理設(shè)計(jì)遵循的基本原則，以及圖層信息分層處理技術(shù)，詳見章節(jié)2。由于AutoCAD輸出的是位圖，為了便于后續(xù)處理，需通過PhotoShop將背景圖層變?yōu)榘咨?，然后使?DMax進(jìn)行渲染，最后輸出用于室內(nèi)定位導(dǎo)航的室內(nèi)平面圖。

4.2 二維碼部署設(shè)計(jì)

考慮到二維碼部署的方案設(shè)計(jì)，應(yīng)將其粘貼在顯而易見的位置，詳見章節(jié)3。部署完畢后，標(biāo)記各個(gè)二維碼在室內(nèi)平面圖中對應(yīng)的地理位置。進(jìn)一步的統(tǒng)計(jì)后，制作相應(yīng)表并存儲(chǔ)到sqlite輕量級數(shù)據(jù)庫，實(shí)現(xiàn)用戶本地查詢位置信息。

圖1 室內(nèi)平面圖

4.3 系統(tǒng)整體架構(gòu)設(shè)計(jì)

此文采用二維碼生成器生成特定編碼規(guī)則的二維碼圖片，然后通過二維碼識別軟件對攜帶定位信息的二維碼圖片進(jìn)行解碼并獲取超鏈接，接著利用此超鏈接訪問后臺搭建的Web服務(wù)器，訪問文件服務(wù)器并返回與二維碼對應(yīng)的室內(nèi)平面圖，最后在室內(nèi)平面圖的基礎(chǔ)上進(jìn)行二次開發(fā)，實(shí)現(xiàn)基于A*算法的離線語音導(dǎo)航功能。該系統(tǒng)具體架構(gòu)設(shè)計(jì)如圖2、圖3所示。

圖2 系統(tǒng)整體架構(gòu)設(shè)計(jì)

圖3 系統(tǒng)后臺架構(gòu)設(shè)計(jì)

4.4 系統(tǒng)實(shí)現(xiàn)

此文基于當(dāng)今流行的Android操作系統(tǒng)，采用Java語言，開發(fā)出一套基于二維碼和A*算法的室內(nèi)精準(zhǔn)定位導(dǎo)航系統(tǒng)。該系統(tǒng)的操作主界面如圖4所示，具體操作流程如下。

1）進(jìn)入二維碼掃描界面，此時(shí)將攝像頭對準(zhǔn)室內(nèi)部署的二維碼即可；

2）當(dāng)成功識別二維碼圖片后，跳轉(zhuǎn)下一個(gè)界面，屏幕中間彈出相應(yīng)的室內(nèi)平面圖；

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

4）當(dāng)用戶點(diǎn)擊這些場所時(shí)，系統(tǒng)開始提供離線語音導(dǎo)航服務(wù)。

圖4 系統(tǒng)主界面

5 結(jié) 論

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

在人力資源不足的情況下，部分功能未能完全實(shí)現(xiàn)，以下幾點(diǎn)需要進(jìn)一步完善。

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

2）提供資訊平臺，讓物業(yè)管理人員實(shí)時(shí)發(fā)布室內(nèi)場所的最新消息。

3）對外提供接口，讓合作方實(shí)時(shí)更新室內(nèi)平面圖信息。

[1]周傲英，楊彬，金澈清，等.基于位置的服務(wù):架構(gòu)與進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（7）:1155-1171.

[2]Want R，HoPPer A，F(xiàn)aleao 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]錢紅昇，葛文鋒，鐘鳴，等.基于分層的改進(jìn)A*算法在路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，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的室內(nèi)導(dǎo)航定位系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[D].上海：東華大學(xué)，2013.

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

[11]任豪毅.基于二維碼的智能手機(jī)室內(nèi)定位方法[D].杭州：浙江大學(xué)，2013.

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

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

[14]宮雪.QR二維碼個(gè)性化設(shè)計(jì)及其應(yīng)用研究[D].北京：北京工業(yè)大學(xué)，2015.

[15]徐玲，蔣欣志，張杰，等.手機(jī)二維碼識別系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，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

國家自然科學(xué)基金資助項(xiàng)目（61174184）

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