采用动态负载均衡的LiDAR数据生成DEM并行算法

随着高性能计算的发展,并行技术已经广泛应用于LiDAR数据的分析处理。本文针对现有LiDAR数据生成DEM并行算法所存在的负载不均衡问题,设计并实现了动态负载均衡的LiDAR数据生成DEM并行算法。该算法采用主从式并行策略,管理进程负责LiDAR点云的高效自适应条带划分,计算进程负责LiDAR点云生成DEM的计算。本文设计了任务量的动态调度策略:首先,由所有进程并行创建任务量由大到小排列的待处理任务队列;然后,管理进程根据计算进程的反馈对待处理任务进行动态分配,以达到负载均衡。在24 核集群环境下,用30 GB(约12 亿点)LiDAR数据对本文算法进行测试,生成分辨率为1 m的格网DEM,算法加速比峰值达到15.16;同时,与静态调度策略进行对比实验,结果显示本文的动态负载均衡策略可更好地保证进程间的负载均衡,有效地提高了LiDAR生成DEM并行算法的整体效率。     

基于Pfafstetter规则的流域编码算法并行化方法

流域编码是以子流域划分进行流域相关研究的重要内容。Pfafstetter 流域编码以编码唯一、顾及流域拓扑关系及编码效率高等优点而被广泛采用。本文在流域相关研究的分析范围不断增大、数据精度越来越高的需求背景下,以Pfafstetter 编码为基础,对流域编码并行化方法进行研究。首先,分析了Pfafstetter 编码不全面和码位不一致的问题,改进了Pfafstetter 编码规则;然后,从数据并行的角度,讨论了并行计算环境下的数据划分及并行化策略,进而设计了流域编码并行算法;最后,利用长江中上游流域SRTM数据,在集群系统上对流域编码并行算法的正确性和并行性能进行了测试。实验结果表明,本文设计实现的流域编码并行算法可获取与实际较为一致的计算结果,且提高了编码计算效率,可为基于子流域划分的流域分析并行化提供参考。     

基于空间填充曲线排列码划分的并行缓冲区算法

缓冲区计算是地理信息系统空间分析的基本功能之一。在矢量缓冲区研究方面,以往大多聚焦缓冲区生成算法,这些优化方法在单机计算环境中针对大规模空间数量数据的计算效率提升是有限的,因而需要并行环境下的改进方法来进一步破解计算瓶颈。本文基于Map Reduce计算模型和分布式内存计算框架,提出了一种基于空间填充曲线排列码划分的并行缓冲区分析算法(SPBM),基于空间填充曲线编码进行数据排序和范围划分,对跨越网格的数据采用近似切分方法,在考虑负载均衡的前提下对任务并行分解,之后按照给定深度的"树状"方式进行结果合并。本文在单机和集群两种环境下利用实际道路网等数据进行了实验。同等环境下,相较于目前流行的GIS软件——QGIS和Post GIS计算性能提升明显,相较于现有其他并行优化方法效率提升超过50%。这样的优化分析方法对于GIS中其他矢量分析算法的并行算法也具有一定的借鉴意义。     

利用MapReduce的异常轨迹检测并行算法

异常轨迹检测是移动对象数据挖掘的一个重要研究领域。TRAOD(TRAjectory Outlier Dectection Algorithm)算法是一种经典的异常轨迹检测算法,但它对于海量轨迹数据的异常检测效率低。为提高海量轨迹数据集的异常检测效率,本文提出了一种利用MapReduce 的异常轨迹检测并行算法(Parallel algorithm for TRAjectory Outlier Detection, PTRAOD),并在此基础上提出了网格索引的异常轨迹检测并行算法(Grid-based Parallel algorithmfor TRAjectory Outlier Dectection, GPTRAOD)。GPTRAOD算法在PTRAOD算法的基础上,利用网格索引实现区域查询,进一步提高算法效率。将PTRAOD算法和GPTRAOD算法在Hadoop 平台上加以实现,结果表明:本文提出的2 个并行检测算法,能实现异常轨迹的检测;GPTRAOD算法的效率优于PTRAOD算法;GPTRAOD算法具有较高的可扩展性和较好的加速比。     

面向地形数据的点云简化算法

针对地形点云数据量大、表面特征复杂多样等特点,提出面向地形数据的点云简化算法。基于K-D Tree搜索各点K邻域,构建点集空间拓扑关系|应用移动最小二乘法计算各点曲率,通过曲率的划分,在平缓区域按距离进行简化,保证整个算法的效率|在突变区域根据曲率简化,确保曲率变化大的关键特征信息不丢失,从而实现点云数据的简化。利用基于熵理论的定量评价方法,通过实例验证该方法的可行性和普适性。     

三维海量点云数据的组织与索引方法

三维点云是三维GIS重要的数据来源,也是三维GIS对地学空间对象、现象进行表达、描述以及建模的重要手段。点云数据的高效组织是对其进行各种分析处理的基础,为此本文在对三维坐标点按照一定的规则进行排序的基础上,采用规则空间八叉树与平衡二叉树相结合的嵌套复合结构进行组织,大大加速了三维点数据基于坐标的查询检索,为海量点云数据的进一步分析操作奠定了基础。最后,文中对该复合组织结构进行了内外存相统一的设计与实现,并验证了该方法的正确性及有效性。     

三维城市模型数据划分及分布式存储方法

随着信息获取技术的快速发展,地理信息数据每天以TB级的数量增加。三维城市模型数据作为三维GIS的重要内容,在数字城市和智慧城市建设过程中发挥重要作用。由于三维城市模型数据结构复杂,其数据量具有海量性,因此,高效地对三维城市模型进行划分及存储,以满足数据的长效管理及三维GIS系统的快速可视化数据调度和空间辅助决策需求,成为近年的研究热点。以往的数据划分方法导致划分区域在数据调度中变化频繁,使数据更新和管理变得困难,需寻找一种更为稳定且具有普适性的数据划分方法。本文分析了现有三维城市模型数据划分方法的不足,提出了基于拓扑关系模型的大比例尺图幅划分方法,并对划分后三维模型数据进行统一命名编码;借助非关系数据库MongoDB强大的海量数据组织及高效的多并发访问功能,构建了MongoDB分片集群服务器;对三维城市模型数据进行了单元划分,并采用规则建模软件City Engine进行建模,得到三维城市模型,借助非关系数据库软件MongoDB进行数据存储实验。结果表明,基于拓扑关系模型的大比例尺图幅划分方法适用于三维城市模型数据划分,划分后数据的存储效率明显提高,MongoDB数据库的多并发访问效率具有良好的稳定性。     

空间点集自动概括方法的优化设计

在考虑空间点集整体结构的前提下,从系统的观点和人类视觉的角度出发,把空间点集划分成三个子集:边界点子集、聚集中心子集和内部点子集。对于边界点子集采用并改进Delaunay三角网方法确定边界点以及边界点的取舍;对于聚集中心,采用模糊聚类分析方法确定中心点子集的组成。最后在确定边界点子集和聚集中心子集的前提下,设计内部点子集自动化简的最优化方法。     

基于移动多核GPU的并行二维DCT变换实现方法

传统的基于CPU的串行程序所实现的二维DCT变换算法时间复杂度高变换效率低,难以满足许多应用的实时要求.特别是在当代以嵌入式处理器为核心的移动端信息处理终端,有限的CPU性能更加难以实现快速的DCT变换.值得欣慰的是新一代嵌入式处理器提供了支持GPGPU技术的GPU,为解决复杂的移动计算问题提供了高效的并行化解决途径.基于最新的ARM Cortex-A15内嵌GPU Mali-T604及OpenCL框架设计实现了一种针对二维DCT变换的并行化加速方案并实测了优化效果,实验结果表明文中的并行方案能够提高二维DCT变换的效率,在输人数据量足够大的条件下能够达到近20倍的加速比.     

一种快速生成平面Delaunay三角网的横向扩张法

目前已有多种基于平面上离散点集构造Delaunay三角网的算法,其中三角网扩张法、逐点插入法的平均时间复杂度为O(n²),分治算法和其他分块合并算法能使平均时间复杂度接近线性,但增加了算法的复杂性,从而使浮点计算误差错误发生的机率增大。本文作者提出了一种新算法:将用于构网的离散点集先按横坐标从小到大排序,在空间上表现为从左到右排列;然后先以点序列中的前三个点作为初始三角网,每次将剩余点集中最左边的点联入三角网,最终得到一个三角剖分,再用LOP法优化三角剖分。该算法的优势是具有快速的三角剖分过程,使整体的平均时间复杂度为O(n),并且构网效率高,算法简单。     

面向地表上、下集成的二维/三维单纯形剖分算法实验

对地上实体、地形表面和地下实体的集成建模是国内外研究的热点。本文以单纯复形理论,提出了一种以约束Delaunay三角网为纽带,用边界表示模型-不规则三角网-四面体格网的集成空间数据模型,对地上实体、地表和地下空间对象进行无缝集成。用边界表示模型表达地面上复杂的对象,用不规则三角网表达地形,用四面体格网表示地质体对象。对传统的逐点插入法构建约束Delaunay三角网算法进行改进,生成约束Delaunay三角网,对地上实体和地表进行集成。其对不同的地层数据分别进行Delaunay三角剖分,构成四面体剖分的上下边界,构建上、下地层之间的侧边界,形成空腔,进而对空腔进行四面体剖分,形成分层表达的地质体对象。同时设计了一个原型系统,对算法进行验证,展示了其实验结果。     

������������Tarjan�㷨��PS����Ʒָ���������

???????PSInSAR????????ж????????????????????????????????Tarjan????PS?????????????????????????????Envisat????SAR????????????PSInSAR?????????????????????Ч???????????????????????????????????????????????????????????????д???PS????????????????????????????     

一种有效的离散数据场等值线生成方法

给出了一种有效的离散数据三角形网格等值线生成算法，首先在Delaunay三角剖分算法中引入了闭合点概念，通过在三角形网格生成过程中动态删除闭合点，减少搜索点集大小，提高了原来三角形剖分算法的速度；其次在三角形网格等值线生成算法中提出了凸边和凸边三角形的概念，通过建立凸边链表和凸边三角形链表，并以凸边进行等值线跟踪，简化了三角形网格等值线搜索算法，提高了等值线生成效率。最后在气象天气图离散站点数据基础上给出了详细测试数据，并给出了天气图等值线绘制效果图。     

基于可靠匹配点约束的遥感影像密集匹配

针对现有由稀到密的加密匹配算法中,初始匹配点可靠性低将导致迭代匹配拓展过程存在较多误匹配的问题,提出一种基于可靠匹配点约束的遥感影像密集匹配算法。首先,利用SIFT匹配点约束直线匹配获得的同名直线构建虚拟匹配点集,结合虚拟匹配点集和SIFT匹配点集建立初始匹配点集;然后,依次采用局部影像信息和局部几何约束对初始匹配点集进行检核剔除错误匹配,主要体现在利用指纹信息和梯度信息构建匹配点局部区域约束剔除较为明显的误匹配点,利用匹配三角网构建局部几何约束剔除由相似纹理产生的误匹配点,得到优化后的可靠匹配点;最后,基于可靠匹配点构建的Delaunay三角网,以三角形重心为加密匹配基元,结合核线约束和仿射变换对其进行迭代匹配拓展,得到最终匹配点集。选取4组资源三号卫星前视数据和后视数据进行实验,结果表明：利用局部纹理特征和局部几何双重约束模型可有效剔除误匹配点得到可靠匹配点,通过可靠匹配点进行迭代匹配拓展得到的密集匹配结果相较于对比算法具有更高匹配精度,在4组数据上其平均匹配精度为95%,具有较好的匹配稳定性。     

基于线激光扫描的岩石激光钻孔的三维重建和可视化

激光钻进岩石形成的钻孔的孔形较为复杂,具有较小的孔直径和较高的孔壁粗糙度,使得利用传统方法进行钻孔尺寸的测量较为困难。为了精确钻孔测量和方便孔形研究,提出了一种基于线激光扫描及逆向建模的钻孔建模方法。首先,搭建了线激光扫描平台,建立了空间坐标系,以获取钻孔的三维坐标,构建了钻孔的初始点云数据。其次,在MATLAB中对获取的点云数据进行无效点移除及多视角点云配准,其中,无效点移除利用顺序查找法实现,多视角点云配准则基于迭代最近点（ICP）算法,包括初始配准和精确配准两个阶段。最后,基于Delaunay三角网格划分及曲面重建算法,实现了钻孔模型的重建和可视化。此外,还采用滴液法和切割法进行实际钻孔容积值测量及钻孔轮廓线获取,并与由点云重建的钻孔模型上获取的测算结果进行对比分析,以验证所述方法建立的钻孔模型的精度。结果表明:重建的钻孔模型与实际钻孔之间的误差小于4%,重建的模型能够满足激光岩石钻进钻孔的测量要求,证实了所述方法的可行性。与传统测量方法相比,所述方法属于非接触、非破坏性方法,可重复性测量。      

基于TCP-InSAR的采动区铁路动态沉降监测与时序分析

为高效获取采动区长时间序列形变,监控煤炭开采对矿区铁路的影响,研究一种基于TCP-InSAR(temporarily coherent point interferometric synthetic aperture radar)的采动区铁路形变监测方法。该方法根据时间序列SAR影像间的相干性,选取临时相干点构建Delaunay三角网,并通过离群值探测去除具有相位模糊度的TCP间的弧段,最后采用最小二乘解算得到区域地表变形。实验使用2016-10～2017-04时间段内的15景Sentinel-1A数据,利用TCP-InSAR技术获得某矿区的铁路形变。结果表明,受采动影响,该时间段内铁路最大下沉值为95mm,最大倾斜坡度为0.37‰。利用TCP-InSAR技术可实现采动区内铁路长时间的动态形变监测。     

基于Coons曲面的似大地水准面精化算法研究

针对线状或带状GPS水准点控制的似大地水准面,提出Coons曲面内插模型。先将GPS水准点拟合成曲线,再通过曲线构造曲面,尽可能减少传统拟合算法由点直接推面的精度消耗。分别运用最小二乘法、最小二乘配置法、移动内插法和Coons曲面法对线状GPS水准点控制的似大地水准面进行拟合,结果表明,基于Coons曲面的内插模型算法精度最高。     

基于N-KD树的空间点数据分组算法

随着科学技术的进步,地理空间数据的分析处理面临着数据量膨胀和计算量高速增长的双重挑战,为了解决海量数据处理速度慢的问题,本文针对空间分布不均匀的点数据,从数据并行的角度,以保持数据的空间邻近性及保证数据分组后各组数据量负载均衡为目标,提出基于N-KD树（Number-K Dimension Tree）数据动态分组的方法,其是一种面向实时变化（数据量和数据空间范围变化）的空间数据动态分组方法。该方法借鉴K-D树的创建和最临近点搜索的思想,通过方差判断数据分布稀疏程度,利用最临近点搜索方法处理边界点,实现空间范围的不均等切分,保证数据分组后各组数据量基本均衡。试验表明,该方法具有较好的动态分组效果与较高的计算效率;支持各种分布状态的空间点数据的分组;分组后各组数据量负载均衡;分组算法本身有支持并行、支持分布式协同工作模式的特点。