基于三維實景建模和Dijkstra 算法的校園導航應用程序研發

劉詩雨 李澤鳴* 張力晗 段薈澤 劉忠博

(沈陽工學院能源與水利學院,遼寧 撫順113122)

1 概述

經濟全球化推動人類社會科學技術快速發展,據美國Zenith 研究報告指出,到2018 下半年中國使用智能手機用戶數量將超過13 億人次,位居世界第一[1,2]。2020 年,5G 時代的到來更是將人們對智能手機的需求提升到了新的層次[3]。其中,導航定位服務作為手機用戶使用最頻繁的功能,對其定位精度和智能服務的要求愈發嚴苛。因此,研發高精度導航定位平臺,提供便捷化、智能化的位置信息服務勢在必行。

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

現如今高校的占地總面積越來越大,建筑物種類及數量越來越多,校內的道路縱橫交錯、錯綜復雜,給在校師生以及來訪者帶來極大地不便。以沈陽工學院為例,校園中每兩個建筑物之間的路線并不唯一,為輔助師生及校外來訪者尋找最合適的路線,更加快速、準確地獲得目的地信息,本研究研發了智慧校園高精度定位系統。本系統基于Android 操作平臺,結合3D 攝影測量技術,利用百度地圖API 接口和Dijkstra 最短路徑算法進行研發。

2 關鍵技術研究

2.1 傾斜攝影與三維實景建模

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

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

2.2 最短路徑算法

2.2.1 計算任意兩點距離

設一個點P 的緯度和經度分別為(αp,δp),另一個點Q的緯度和經度分別為(αq,δq)。以0 度經線為基準,東經為正值,西經為負值,北緯取( 90°- 當前緯度),南緯取(90°+當前緯度),則經過上述處理過的兩點為(αp',δp')和(αq',δq'),由球面計算公式可以推導出P 點與Q 點之間的距離Dpq可以表示為:

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

2.2.2 最短路徑算法

本系統的最短路徑算計算方法采用迪杰斯特拉(Dijkstra)算法,該算法是以不斷地進行對頂點標號來實現對最短路徑搜索的[8,9]。算法開始后,每次標號一個頂點,標號的值即為從給定源點到該點的最短路徑權值。在所有與固定源點有邊相連的頂點中找到離源點最近的頂點,遞歸地設已找到當前最短路徑的一部分- 由與源點距離最短的n 個結點和相應的n 條最短路徑構成,此時,這n 個結點到源點的最短路徑權值將會成為它們各自的永久標號[10-11]。

以沈陽工學院為例:以求源樓為源點,計算求源樓到(圖書館、求實樓、校史館、體育場)的最短路徑,如圖1 所示。線上所標注為相鄰線段之間的距離,即權值(注:此圖只為示意圖,目視長度與相鄰距離并不對等)。以線相鄰線段之間的距離作為權值,在線上標注出來。Dijkstra 算法在案例中具體實現如下[1]:

(1)在計算圖1 中的最短路徑時,需要指定起點s(求源樓),從頂點s 開始計算；

圖1 沈陽工學院Dijkstra 路網示意圖(部分)

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

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

(4)更新U 中的頂點和頂點對應的路徑；

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

3 系統的總體設計

本系統以沈陽工學院為例,調查了本校師生對校園導航的需求并整理獲得預期要實現的功能,主要包括導航信息的獲取、用戶個人賬號登錄、校園二維、三維地圖實景信息查看等,并向用戶提供實時定位功能,即無論用戶在校園任何位置,都能通過該系統進行實時精準定位；另外,系統還提供臨近位置的提醒功能,可以讓用戶及時獲取自己的所在地變化信息和周邊信息；最后,提供最佳路徑選擇服務,用戶通過選擇當前位置與目的地,系統將自動選擇一條通往目的地的最佳路徑,為用戶提供便利,極大地減少了用戶的行程時間。

3.1 功能設計

本系統為了滿足校園師生的日常需求,設計了以下功能:導航信息獲取、實時定位服務、臨近位置提醒、周邊信息搜索、最優路線規劃等功能。

3.2 實時定位服務

該系統可以隨時通過手機無線網絡對用戶當前的所在位置進行基站定位,向用戶提供當前所在位置的精準坐標,該位置信息會以功能區名稱的形式顯示在用戶手機的地圖上,然后用戶可根據自己的需要,獲取不同地點和功能區的位置信息。例如周邊教學樓的名稱、道路的名稱和超市等。系統將呈現兩種形式地圖供用戶選擇:

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

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

圖2 實時定位圖

3.3 最優路徑規劃

此功能區別于其他大尺度定位服務系統,基于定位信息獲取不同功能區的感興趣點(Points of Interest,POI)。當用戶提供所需路徑的起止點時,系統會根據起點和終點的位置進行路線規劃,結合百度地圖API 接口和Dijkstra 最短路徑算法,向用戶提供能夠到達目的地的最佳路線。

4 結論與討論

本研究在實現校園導航過程中主要針對校園特色進行了設計,利用三維模型更直觀的讓用戶了解到校園內部環境與布局情況,利用Dijkstra 算法可以較快且精準的計算最短路徑。通過本系統的實踐研發,加強了學校信息化建設。該系統為校內師生和外訪人員提供了一個全新的信息化服務平臺,并打造了一個對外宣傳學校的媒介,提升了學校知名度,為學校的信息化建設提供助力。在系統的研發過程中,既提升了學生的團隊協作能力,也增加了學生的實踐經驗。

在對本系統進行成果調研時發現以下問題:

(1)Android 手機續航問題一直是人們的詬病,因此在校園導航系統的功耗上,應改善功耗問題,使系統減少對手機正常續航的影響。

(2)在運行速度上,應優化后臺系統,減少數據冗余,如對重復區域影像適當舍棄等,使校園導航系統運行更加流暢和穩定。

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