基于三維實(shí)景建模和Dijkstra 算法的校園導(dǎo)航應(yīng)用程序研發(fā)

劉詩(shī)雨 李澤鳴* 張力晗 段薈澤 劉忠博

(沈陽(yáng)工學(xué)院能源與水利學(xué)院,遼寧 撫順113122)

1 概述

經(jīng)濟(jì)全球化推動(dòng)人類社會(huì)科學(xué)技術(shù)快速發(fā)展,據(jù)美國(guó)Zenith 研究報(bào)告指出,到2018 下半年中國(guó)使用智能手機(jī)用戶數(shù)量將超過(guò)13 億人次,位居世界第一[1,2]。2020 年,5G 時(shí)代的到來(lái)更是將人們對(duì)智能手機(jī)的需求提升到了新的層次[3]。其中,導(dǎo)航定位服務(wù)作為手機(jī)用戶使用最頻繁的功能,對(duì)其定位精度和智能服務(wù)的要求愈發(fā)嚴(yán)苛。因此,研發(fā)高精度導(dǎo)航定位平臺(tái),提供便捷化、智能化的位置信息服務(wù)勢(shì)在必行。

經(jīng)歷十余年的發(fā)展,隨著全球定位系統(tǒng)技術(shù)的大規(guī)模普及,如今只需要擁有一臺(tái)智能手機(jī),便可以在陌生國(guó)度、陌生城市甚至陌生的街道里獲得滿足需求的位置信息,可實(shí)現(xiàn)輕松地找到通往目的地的最佳路徑。因此,為適應(yīng)數(shù)字化校園建設(shè)的要求,利用三維技術(shù)開(kāi)發(fā)校園范圍內(nèi)高精度導(dǎo)航定位系統(tǒng)極具實(shí)踐意義。

現(xiàn)如今高校的占地總面積越來(lái)越大,建筑物種類及數(shù)量越來(lái)越多,校內(nèi)的道路縱橫交錯(cuò)、錯(cuò)綜復(fù)雜,給在校師生以及來(lái)訪者帶來(lái)極大地不便。以沈陽(yáng)工學(xué)院為例,校園中每?jī)蓚€(gè)建筑物之間的路線并不唯一,為輔助師生及校外來(lái)訪者尋找最合適的路線,更加快速、準(zhǔn)確地獲得目的地信息,本研究研發(fā)了智慧校園高精度定位系統(tǒng)。本系統(tǒng)基于Android 操作平臺(tái),結(jié)合3D 攝影測(cè)量技術(shù),利用百度地圖API 接口和Dijkstra 最短路徑算法進(jìn)行研發(fā)。

2 關(guān)鍵技術(shù)研究

2.1 傾斜攝影與三維實(shí)景建模

近年來(lái),傾斜攝影技術(shù)是測(cè)繪領(lǐng)域發(fā)展起來(lái)的一項(xiàng)高新技術(shù)[4,5]。該技術(shù)能夠采集地面物體的高度、經(jīng)緯度以及多角度高分辨率影像的信息,突破了以往從垂直角度拍攝只能獲得正射影像的限制[6,7]。

以沈陽(yáng)工學(xué)院為例,進(jìn)行內(nèi)業(yè)與外業(yè)交互操作。在外業(yè)進(jìn)行3D 攝影測(cè)量飛行準(zhǔn)備時(shí),應(yīng)選擇對(duì)本次測(cè)量最有利的氣象條件,并盡可能的減少或避免地表植被和其他覆蓋物對(duì)攝影和測(cè)圖的不良影響。飛行過(guò)程中既要保證充足的光照度,又要避免過(guò)大的陰影。攝影時(shí)要選擇視野遮擋小并且無(wú)信號(hào)干擾,更要遠(yuǎn)離高層建筑物且人群較少的地點(diǎn)作為無(wú)人機(jī)的起降場(chǎng)地,以確保儀器安全和實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性。布設(shè)像控點(diǎn),像控點(diǎn)測(cè)量是使用RTK 進(jìn)行的。內(nèi)業(yè)中主要進(jìn)行空中三角測(cè)量加密計(jì)算,反復(fù)操作,直到控制點(diǎn)變綠,像素控制在0.6 內(nèi),第三到n 次空中三角計(jì)算。利用控制點(diǎn)時(shí),所有影像進(jìn)行精準(zhǔn)刺點(diǎn),完成空間后方交會(huì)與精準(zhǔn)相對(duì)定向。利用空間前方交會(huì),進(jìn)行絕對(duì)定向完成建模,最終得到高精度的三維實(shí)景模型。

2.2 最短路徑算法

2.2.1 計(jì)算任意兩點(diǎn)距離

設(shè)一個(gè)點(diǎn)P 的緯度和經(jīng)度分別為(αp,δp),另一個(gè)點(diǎn)Q的緯度和經(jīng)度分別為(αq,δq)。以0 度經(jīng)線為基準(zhǔn),東經(jīng)為正值,西經(jīng)為負(fù)值,北緯取( 90°- 當(dāng)前緯度),南緯取(90°+當(dāng)前緯度),則經(jīng)過(guò)上述處理過(guò)的兩點(diǎn)為(αp',δp')和(αq',δq'),由球面計(jì)算公式可以推導(dǎo)出P 點(diǎn)與Q 點(diǎn)之間的距離Dpq可以表示為:

其中,R 取值為6371km(既地球平均半徑)。

2.2.2 最短路徑算法

本系統(tǒng)的最短路徑算計(jì)算方法采用迪杰斯特拉(Dijkstra)算法,該算法是以不斷地進(jìn)行對(duì)頂點(diǎn)標(biāo)號(hào)來(lái)實(shí)現(xiàn)對(duì)最短路徑搜索的[8,9]。算法開(kāi)始后,每次標(biāo)號(hào)一個(gè)頂點(diǎn),標(biāo)號(hào)的值即為從給定源點(diǎn)到該點(diǎn)的最短路徑權(quán)值。在所有與固定源點(diǎn)有邊相連的頂點(diǎn)中找到離源點(diǎn)最近的頂點(diǎn),遞歸地設(shè)已找到當(dāng)前最短路徑的一部分- 由與源點(diǎn)距離最短的n 個(gè)結(jié)點(diǎn)和相應(yīng)的n 條最短路徑構(gòu)成,此時(shí),這n 個(gè)結(jié)點(diǎn)到源點(diǎn)的最短路徑權(quán)值將會(huì)成為它們各自的永久標(biāo)號(hào)[10-11]。

以沈陽(yáng)工學(xué)院為例:以求源樓為源點(diǎn),計(jì)算求源樓到(圖書(shū)館、求實(shí)樓、校史館、體育場(chǎng))的最短路徑,如圖1 所示。線上所標(biāo)注為相鄰線段之間的距離,即權(quán)值(注:此圖只為示意圖,目視長(zhǎng)度與相鄰距離并不對(duì)等)。以線相鄰線段之間的距離作為權(quán)值,在線上標(biāo)注出來(lái)。Dijkstra 算法在案例中具體實(shí)現(xiàn)如下[1]:

(1)在計(jì)算圖1 中的最短路徑時(shí),需要指定起點(diǎn)s(求源樓),從頂點(diǎn)s 開(kāi)始計(jì)算；

圖1 沈陽(yáng)工學(xué)院Dijkstra 路網(wǎng)示意圖(部分)

(2)引進(jìn)兩個(gè)集合S 和U。其中,S 記錄已求出的最短路徑頂點(diǎn)以及相應(yīng)最短路徑的長(zhǎng)度；U 記錄還未求出最短路徑的頂點(diǎn)以及其到起點(diǎn)s 的距離。初始時(shí),S 中只包含起點(diǎn)s；U 中則為除s 之外的全部頂點(diǎn)且U 中頂點(diǎn)路徑是s 到這些頂點(diǎn)的距離；

(3)從U 中找出最短距離路徑的頂點(diǎn)將其加入到S 中；

(4)更新U 中的頂點(diǎn)和頂點(diǎn)對(duì)應(yīng)的路徑；

(5)重復(fù)(3)～(4)操作,直到遍歷完所有頂點(diǎn)。

3 系統(tǒng)的總體設(shè)計(jì)

本系統(tǒng)以沈陽(yáng)工學(xué)院為例,調(diào)查了本校師生對(duì)校園導(dǎo)航的需求并整理獲得預(yù)期要實(shí)現(xiàn)的功能,主要包括導(dǎo)航信息的獲取、用戶個(gè)人賬號(hào)登錄、校園二維、三維地圖實(shí)景信息查看等,并向用戶提供實(shí)時(shí)定位功能,即無(wú)論用戶在校園任何位置,都能通過(guò)該系統(tǒng)進(jìn)行實(shí)時(shí)精準(zhǔn)定位；另外,系統(tǒng)還提供臨近位置的提醒功能,可以讓用戶及時(shí)獲取自己的所在地變化信息和周邊信息；最后,提供最佳路徑選擇服務(wù),用戶通過(guò)選擇當(dāng)前位置與目的地,系統(tǒng)將自動(dòng)選擇一條通往目的地的最佳路徑,為用戶提供便利,極大地減少了用戶的行程時(shí)間。

3.1 功能設(shè)計(jì)

本系統(tǒng)為了滿足校園師生的日常需求,設(shè)計(jì)了以下功能:導(dǎo)航信息獲取、實(shí)時(shí)定位服務(wù)、臨近位置提醒、周邊信息搜索、最優(yōu)路線規(guī)劃等功能。

3.2 實(shí)時(shí)定位服務(wù)

該系統(tǒng)可以隨時(shí)通過(guò)手機(jī)無(wú)線網(wǎng)絡(luò)對(duì)用戶當(dāng)前的所在位置進(jìn)行基站定位,向用戶提供當(dāng)前所在位置的精準(zhǔn)坐標(biāo),該位置信息會(huì)以功能區(qū)名稱的形式顯示在用戶手機(jī)的地圖上,然后用戶可根據(jù)自己的需要,獲取不同地點(diǎn)和功能區(qū)的位置信息。例如周邊教學(xué)樓的名稱、道路的名稱和超市等。系統(tǒng)將呈現(xiàn)兩種形式地圖供用戶選擇:

3.2.1 交通線路圖(包含每條道路的名稱,用戶所在方位),主要提供線狀路徑,方便用戶對(duì)所需路線進(jìn)行篩選；

3.2.2 三維立體地圖,顯示周邊建筑物群及名稱(求源樓和博思樓等),方便用戶對(duì)周圍功能區(qū)信息進(jìn)行獲取。該地圖形式是通過(guò)使用大疆Phantom 4 Pro 無(wú)人機(jī)采集校園主要教學(xué)樓的正射影像與傾斜影像,再將影像導(dǎo)入到Context Capture Center Engine 軟件與Context Capture Center Master 中進(jìn)行照片對(duì)齊,匹配影像同名特征點(diǎn),生成密集點(diǎn)云數(shù)據(jù)。然后按照影像處理的一般流程,依次進(jìn)行三維重建、計(jì)算三角點(diǎn)顏色和紋理映射操作等,最終得到高精度的三維實(shí)景模型,如圖2 所示。

圖2 實(shí)時(shí)定位圖

3.3 最優(yōu)路徑規(guī)劃

此功能區(qū)別于其他大尺度定位服務(wù)系統(tǒng),基于定位信息獲取不同功能區(qū)的感興趣點(diǎn)(Points of Interest,POI)。當(dāng)用戶提供所需路徑的起止點(diǎn)時(shí),系統(tǒng)會(huì)根據(jù)起點(diǎn)和終點(diǎn)的位置進(jìn)行路線規(guī)劃,結(jié)合百度地圖API 接口和Dijkstra 最短路徑算法,向用戶提供能夠到達(dá)目的地的最佳路線。

4 結(jié)論與討論

本研究在實(shí)現(xiàn)校園導(dǎo)航過(guò)程中主要針對(duì)校園特色進(jìn)行了設(shè)計(jì),利用三維模型更直觀的讓用戶了解到校園內(nèi)部環(huán)境與布局情況,利用Dijkstra 算法可以較快且精準(zhǔn)的計(jì)算最短路徑。通過(guò)本系統(tǒng)的實(shí)踐研發(fā),加強(qiáng)了學(xué)校信息化建設(shè)。該系統(tǒng)為校內(nèi)師生和外訪人員提供了一個(gè)全新的信息化服務(wù)平臺(tái),并打造了一個(gè)對(duì)外宣傳學(xué)校的媒介,提升了學(xué)校知名度,為學(xué)校的信息化建設(shè)提供助力。在系統(tǒng)的研發(fā)過(guò)程中,既提升了學(xué)生的團(tuán)隊(duì)協(xié)作能力,也增加了學(xué)生的實(shí)踐經(jīng)驗(yàn)。

在對(duì)本系統(tǒng)進(jìn)行成果調(diào)研時(shí)發(fā)現(xiàn)以下問(wèn)題:

(1)Android 手機(jī)續(xù)航問(wèn)題一直是人們的詬病,因此在校園導(dǎo)航系統(tǒng)的功耗上,應(yīng)改善功耗問(wèn)題,使系統(tǒng)減少對(duì)手機(jī)正常續(xù)航的影響。

(2)在運(yùn)行速度上,應(yīng)優(yōu)化后臺(tái)系統(tǒng),減少數(shù)據(jù)冗余,如對(duì)重復(fù)區(qū)域影像適當(dāng)舍棄等,使校園導(dǎo)航系統(tǒng)運(yùn)行更加流暢和穩(wěn)定。

(3)本系統(tǒng)建立的校園虛擬環(huán)境只是簡(jiǎn)單的三維全景,與真正的三維空間還有較大差距,今后仍需進(jìn)一步研究,將虛擬三維校園環(huán)境設(shè)計(jì)得更加逼真,更符合校園規(guī)劃要求且實(shí)用價(jià)值更高。