基于三维实景建模和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)本系统建立的校园虚拟环境只是简单的三维全景,与真正的三维空间还有较大差距,今后仍需进一步研究,将虚拟三维校园环境设计得更加逼真,更符合校园规划要求且实用价值更高。