基于地形数据的长距离越野路径快速规划方法研究

越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。     

基于动态极坐标参数化的遥感影像匹配方法

图像匹配作为三维重建至关重要的环节,其精度直接影响了平差优化、正射校正等模块的精度。对于城镇、农场等特征密集型区域,特征距离小,相似性强,易于匹配图像;而针对草地、沙漠等特征不明显区域,特征距离大,如果使用特征点匹配的方法,严格阈值下难以获得足够数量的匹配对,放宽阈值又将引入较多误匹配对,这也是导致稀疏点云不够均匀的原因之一。在此场景下,本文提出了基于动态极坐标参数化的无人机正视影像匹配算法,首先对图像做极坐标参数变化,采用动态策略解决极轴方向采样不均匀的问题,使用最小二乘法对得到的极坐标影像对做位移方向上的匹配,匹配后得到的旋转量和平移量,将该结果和SIFT算法的结果做比较。本文设计了2组实验,即参数已知的解算实验和参数未知的解算实验,且每组实验进行3次。在同等配置的计算机上,对两张7360像素×5400像素,32位的影像,本文方法的位姿解算时间相比SIFT的时间减少约57%,二者求得的位姿差通常小于1%。结论表明二者的结果在精度上表现相当,在时间上明显优于SIFT算法,具有实际的应用价值。     

“分形-视距”（FVD）多分辨率纹理生成及组织方法

纹理数据是三维建筑模型中的重要组成部分,通常会消耗大量的内存,导致模型较难实现流畅稳定的动态可视化。针对这个问题,本文提出了一种面向三维模型可视化的“分形-视距”（FVD）多分辨率纹理生成及纹理组织方法。该方法首先利用分形对纹理进行压缩并将其存入纹理数据库,然后按照视距及目标立面的可见性情况创建和组织对应纹理：当视距符合纹理调用条件且目标立面可见时,根据不同视距,执行多分辨率纹理创建,按照各类三维模型数据间的属性关系建立索引,存入关系数据库;当视距不符合纹理调用条件但该立面又可见时,利用纹理分割算法创建颜色纹理树,将节点合并表示立面纹理。最后根据变化的视角和距离调用相应纹理,实现三维模型的动态流畅可视化。本文选择山东省济南市历下区作为研究区域,使用的纹理数据共5290幅。实验结果表明,与3ds Max、SketchUp Pro相比,本文提出的方法减少内存占用分别约为36.5%和49.1%,帧速率提高约7%和10.9%,极大地提高了大场景三维模型可视化的渲染效率和速率。本文提出的方法在三维建筑模型渲染效率和视觉质量之间取得了很好的平衡,这一问题的改善将为建立智慧城市提供快速有效的科学支撑。     

基于改进蚁群算法的无人机低空公共航路构建方法

日益增加的无人机数量和飞手自由规划航线给航空安全带来极大隐患。构建一个安全、高效的航空飞行环境,可以为无人机活动设立隔离空域,并在隔离空域内规划无人机低空公共航路,以提高低空空域利用率,为无人机交通管理提供决策依据。本研究充分考虑无人机近地表飞行及其即时通讯等特点,以天津市为例,基于地理信息技术构建以多源地理空间数据为基础的无人机低空飞行环境,包括低空蜂窝网络环境、大气环境和政策空域环境等,并改进传统蚁群算法以搜索无人机最优路径,得到该区无人机低空公共航路网。研究结果表明,改进的蚁群算法大大提高了路径搜索效率,满足无人机航路规划的高时效性、动态更新等要求;并且天津市航路长度符合市场上现有的无人机最远航程要求,基本满足现有的无人机运输要求。本研究描述的无人机低空公共航路研究的核心算法和关键技术,可以为无人机管控系统提供核心技术支撑。     

面向山地徒步应急救援路径规划的改进蚁群算法研究

当消防事故发生在无明显道路或道路稀疏的野外复杂山区时,如何在复杂山地环境中规划安全、快速通过的路线至关重要。针对蚁群算法在复杂山地路径规划中容易陷入局部最优以及搜索时间较长的问题,本文提出一种适用于细粒度野外山地环境的徒步应急救援路径规划算法。本文首先根据已有文献分析地表信息与人类运动速度之间的关系,综合地表灌木盖度与地形坡度因素设计寻优算法的目标函数和启发函数;接着采用定向范围视野的蚂蚁搜索方式,决定蚁群算法寻优过程中每一步的网格选择;最后采用拉普拉斯分布调整初始信息素、添加隔离信息素、融合遗传算子与分组更新常规信息素的方法改进蚁群算法。将算法应用到400×400、1000×1000、5000×5000、10 000×10 000网格数的野外山地环境进行实验对比,实验结果表明,采用定向范围视野与优化启发函数的各蚁群算法在四组实验中均能得到可行路径,验证了方法的有效性;本文算法求解的路径质量优于另外三种算法,在四组实验中分别提高了0.52%～4.95%、4.71%～5.39%、2.26%～13.11%、3.84%～9.16%;此外,在野外三维山地环境中,定向范围视野的搜索方式缩减了搜索...     

基于室内路网的跨楼层路径规划技术的设计与实现

随着室内定位技术、BIM-GIS技术和室内地图研究的发展,室内位置服务需求日益旺盛。作为室内位置服务的关键技术之一,室内路径规划成为研究与应用热点。但是早先的路径规划技术往往基于单层网络拓扑模型而设计,由于模型缺少楼层之间的连通信息,而不能实现跨楼层导航算法分析;而后随着跨楼层导航算法的出现,跨楼层的路径规划、导航及定位得以实现,但这些跨楼层导航算法基于楼层连接通达规则,往往需要多次遍历楼层信息,运算效率低下。针对这一问题,本文利用电梯、扶梯、楼梯等楼层间连接信息,设计、实现了基于楼层连接表的室内多层路网分析模型,并采用逐层分析的方法和多次网络分析,实现室内跨楼层的带有多个途经点路径分析。整个技术框架包括跨楼层路网生成模块、位置点接收模块、网络分析模块、循环控制模块。算法方面,本研究采用双向遍历的A*最短路径分析算法,通过网络路径分析,最终将满足约束条件的规划路径显示在移动设备上,帮助用户实现跨楼层、多途经点的定位与路径导航。     

SA*：一种多线程路径规划算法

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。     

利用双重索引快速构建道路网络连通拓扑

路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISO GDF4.0模型对道路连通拓扑的定义,结合最优路径规划对道路网络连通拓扑的要求,提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分,新道路生成过程中,首先,自上而下地打断道路形成直线段集并求交点,然后,自下而上地重构直线段集以生成新道路。在打断道路求交点过程中,对道路建立R-tree空间索引,显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引,使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明,本文提出的拓扑生成算法具有较高的执行效率。     

基于圆盘概化模型的岩溶裂隙渗流路径构建算法

岩溶裂隙网络的识别与重构,一直是岩溶地下水资源和岩溶区地质环境保护研究的热点与难点。基于地表原始裂隙数据、经过克里格插值后的地表裂隙数据、以及通过蒙特卡洛预测得到的地下裂隙数据,本文针对三维裂隙构造中的水流通路识别模块,提出了一种基于圆盘模型的渗流路径构建方法,采用有向图的数据结构来模拟圆盘模型概化后水流沿裂隙的渗流路径,并以邻接矩阵的形式存储其渗流路径数据。同时,为满足大规模裂隙数据快速求交的需要,本文给出了三维R树索引算法缩减遍历各个采样点所用的时间,提高了整套算法运行的效率。最后,以北京市房山区张坊地区地表采样裂隙数据为基础,借助遥感地质调查、重点岩溶区精细地质测量及取样分析等手段,开展三维裂隙空间网络分布模型研究,对岩溶裂隙渗流路径构建算法进行计算机仿真实现,为张坊地区岩溶发育机理的研究及岩溶水裂隙数值模拟提供可视化的分析手段。     

一种基于SuperMap GIS的改进Dijkstra算法

为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。     

基于邻接节点聚合的多层级MQA-A~*路径规划算法

针对执行A~*算法的计算机资源消耗随网格规模的扩大而急剧增长的问题,提出了一种基于邻接节点聚合的多层级MQA-A~*(multiscale quarter aggregation-A~*)栅格路径规划算法。算法聚合邻接节点为抽象节点,从原始栅格地图起始逐层构造高层级抽象地图,通过A~*算法在高层级抽象地图上规划粗糙路径,并基于抽象网格内部连通属性及抽象网格间的连接信息将粗糙路径向低层级抽象地图逐层细化,最终得到原始栅格地图上的路径规划方案。实验结果表明,MQA-A~*栅格路径规划算法可以在保障规划路径长度的基础上大幅缩减计算机的内存消耗及算法计算时间,高层级抽象网格上的MQA-A~*算法的计算加速比随扩展节点占比提升而提高。     

基于Ex-Dewey前缀编码与R树的GML空间数据索引机制

大量GML空间数据的出现,使其有效性的查询处理面临严峻挑战。索引技术是决定数据查询性能的重要因素之一。鉴于GML空间数据XML格式编码的特点,为充分利用Dewey前缀编码方案并消除原方案中节点的插入、删除影响其后趋同胞节点及其子孙节点编码的变更等缺点,论文提出了一种扩展的Dewey编码方案--Ex-Dewey,用以实现对GML文档数据的整体编码和非空间数据的索引构建。研究给出了Ex-Dewey前缀编码的GML非空间数据索引构成模式与处理策略;结合Ex-Dewey,提出GML空间数据索引基于R树的构建,给出了索引构成模式与处理策略。GML空间与非空间数据索引构建,既独立又紧密关联,共同实现GML空间数据的索引。该索引机制意在用于原生GML空间数据库索引构建或单纯GML文档集索引构建中。