利用三元组稀疏矩阵技术改进HASM算法——以全球平均气温模拟为例

 采用预处理共轭梯度法(PCG)进行求解的高精度曲面建模(HASM)算法的计算过程需要大量矩阵计算,采用稀疏矩阵方式可以压缩存储空间。三元组稀疏矩阵存储是较为传统的稀疏矩阵存储结构,这种存储结构的稀疏矩阵技术已被广泛使用。根据HASM-PCG的特点,本文通过改进三元组稀疏矩阵的部分计算方式,调整HASM-PCG算法中的部分计算顺序,从而舍弃部分不需要存储的非零元素,提高了计算效率。根据全球1998-2008年的近3000个气象观测台站的气温观测数据,以及全球DEM数据,对20世纪末至21世纪初的11年来5、6、7、8月份的全球平均气温进行数字模拟。数值结果表明,采用改进的三元组稀疏矩阵技术有效地提高了HASM方法的模拟效率。     

局部型地形因子并行计算方法研究

 随着分析区域的扩展及需求精度的提高,数据-计算密集型地形分析亟需通过并行化来满足用户的时间响应需求。局部型地形因子是以一定半径的分析窗口(通常为3×3)计算且具有单元计算结果独立性的地形信息,是数字地形分析的基本参数。本文在分析局部型地形因子串行算法特征的基础上,以坡度算法为样本,对局部型地形因子的并行计算方法进行了深入研究。从数据并行的角度,对并行计算环境下的数据划分粒度、方式及结果融合策略进行了分析,构建了局部型地形因子的并行计算方法。利用SRTM陆地表面地形DEM数据,设计了坡度并行计算的实验以验证其方法的正确性和实用性。实验结果表明,本文提出的并行计算方法顾及了任务、数据及计算环境,可快速对局部型地形因子串行算法进行并行化改造,提高算法的执行效率,具有较好的并行性能。     

GPU加速的改进PAM聚类算法研究与应用

空间聚类是空间数据挖掘的重要方法,而K-Medoids是一种常用的空间聚类算法。K-Medoids聚类算法存在初始点选择问题,而且计算复杂。为了提高算法的有效性和时间效率,本文结合模拟退火算法思想,改进了传统的K-Medoids算法PAM,提出一种基于GPU计算的并行模拟退火PAM算法。类比矩阵乘法运算,定义了一种新的矩阵计算方法,可以有效减少数据在GPU全局内存和共享内存之间的传输,提高了算法在GPU中的执行效率。利用模拟退火算法搜索聚类中心点,保证了聚类结果的全局最优性。基于不同的数据集,将串行和并行模拟退火PAM算法以及已有的遗传PAM算法进行比较,结果表明并行模拟退火PAM算法聚类结果正确,且时间效率高。最后,应用本文改进算法对贵州省安监系统的安全监管隐患数据进行聚类分析,发现了隐患聚集中心,相关结果对政府的决策具有一定的实际应用价值。     

基于人工神经网络的多特征因子路网匹配算法

在综合考虑多个特征因子的线要素匹配时,根据经验知识确定各特征因子的权值会造成人为误差。针对该问题,本文提出了基于人工神经网络的多特征因子路网匹配算法,根据线要素的几何和拓扑特性选取长度、方向、形状、距离及拓扑5个特征因子的相似度作为路网匹配参考因子。首先,分别在参考图层和待匹配图层中选取样本数据组成样本对,计算样本数据的5个特征因子相似度,用样本数据的5个特征因子相似度和样本的匹配度组成学习模式对;然后,利用BP神经网络的误差反向传播机制自动学习调整各神经层之间的连接权值;最后,输入全部数据,计算参考图层的弧段和待匹配图层的弧段间的匹配度,实现综合多特征因子的路网匹配。实验结果表明,利用人工神经网络进行综合多特征因子的路网匹配可以提高匹配效率和匹配准确度。     

结合网状描述符和单应约束的近景影像直线匹配

针对现有立体影像直线匹配方法中的线描述子只依赖局部灰度特征导致可靠性较弱的问题,本文提出了一种结合网状描述符和单应约束的直线匹配方法。① 利用线特征检测算法（Line Segment Detector, LSD）提取参考影像及搜索影像中的直线段;② 根据角度约束和核线约束确定候选直线,缩小直线搜索范围,并计算参考直线与候选直线的重叠部分以确保端点一致;③ 利用直线段固定邻域内的同名点对构建网状描述符,选择3组不同的同名点对分别计算直线相似值,取其中最大值作为直线段的最终相似度从而确定同名直线对;④ 将未搜索到同名点对的直线段利用单应性矩阵映射至搜索影像,并根据3个判别准则得到最终的匹配结果。为了验证算法的有效性及鲁棒性,本文选取国际公开的标准测试数据集中5组近景影像进行实验,并与现有3种具有代表性的算法进行对比。结果显示本文算法的准确度及有效性均优于对比的3种算法,在匹配准确率与运行效率上最高有16.1%与49倍的提升,对于不同条件下的影像均能取得良好的直线匹配结果。     

一种面向海量浮动车数据的地图匹配方法

浮动车数据已广泛应用于交通监管、智能出行、城市规划等领域,地图匹配是浮动车数据关键技术之一,保障匹配算法精度的同时提高匹配效率,是面向海量浮动车数据地图匹配方法的难点。本文提出一种基于HMM（Hidden Markov Model）的地图匹配模型,相对传统模型尝试了多个方面的改进：在发射概率计算中引入航向角变量,并探讨了该变量对模型精度的影响;以格网对路网进行划分,构建哈希索引,实现候选路段快速查找;采用路径无权距离替代路径实际距离,并对路网进行预处理,根据浮动车有限时间内的活动范围构建路段转移矩阵,实现路段转移概率快速计算,以减小路径匹配算法时间复杂度。将模型应用于北京出租车轨迹数据匹配结果表明,对于采样时间间隔在1~120 s的浮动车数据模型切实可行。在满足匹配精度应用需求的前提下,模型效率有了较大幅度提升,能有效应用于海量浮动车数据地图匹配。     

基于CNN的空间数据自适应切分算法

针对空间数据划分方法无法自适应选择问题,本文提出了基于CNN的数据自适应划分算法（Adaptive Partition Algorithm for Space Vector Data- Convolutional Neural Networks,SVDAP-CNN）。该算法首先基于应用场景和其他相关资源实现特征描述和表达;其次基于层次聚类设计特征矩阵表达算法,体现特征间的局部相关性以减少方法选择时间和提高选择精度;最后通过CNN模型实现空间数据自适应划分。本文选取南海区域真实数据和模拟数据进行验证,与已有的数据划分方法选择算法进行比较。结果显示：针对真实数据,SVDAP-CNN算法的精度和时间效率分别提高了24.18%和25.67%;针对特征和特征间关系表达欠完备的模拟数据,SVDAP-CNN算法的精度和时间效率分别提高了27.02%和26.80%;针对选择结果易出错的数据切分方法,SVDAP-CNN算法的精度提高了19.92%,证明了该算法有较好的普适性;另外,本文结合南海区的实际应用证明了该算法的应用可行性。SVDAP-CNN算法的提出可为大数据量、多变的自动化空间应用分析提供技术支撑。     

基于拟牛顿法改进的3D正态分布变换点云配准算法

针对3D正态分布变换算法在大型场景点云数据配准时效率低的问题,提出一种基于拟牛顿法改进的3D正态分布变换算法。 3D正态分布变换算法主要通过牛顿迭代法进行两视点云最优转换参数求解,但是随着待配准点云数据量的增加,牛顿迭代法需要大量的时间计算Hessian矩阵,增加了算法整体的时间复杂度。本文算法通过拟牛顿法代替牛顿法求解Hessian,改善了3D正态分布变换算法针对大型场景点云数据配准需要大量时间去计算Hessian矩阵的问题。实验表明,本文算法针对大型点云数据不仅能够保持传统3D正态分布变换算法的配准精度,还能提高配准效率。     

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

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

一种异构多核架构快速查询多边形图层间空间关系的方法

目前,空间关系查询中常用的Plane Sweep 算法是一种串行方法,而关于多核CPU的并行查询算法,在面对海量数据查询时,由于CPU核心数及线程数量的限制,其难以满足查询效率需求。针对该问题,本文提出了一种全新的异构多核架构多边形图层间空间关系查询的并行算法。首先,利用STR 树索引过滤不相交的多边形;然后,对过滤后多边形的线段构建四叉树索引,利用CPU+GPU架构并行计算线段的相交以判断多边形环间的拓扑关系;再根据环间的拓扑关系计算多边形间的维度扩展九交模型(DE-9IM)参数值,据此确定多边形间的空间关系;最后,通过实验验证了该算法的准确性和高效性。实验表明,本算法能有效缩短大数据量的空间查询时间。在实验中逐渐增加目标数据集和源数据集多边形的数量,当两数据集都为50 000 个多边形时,以包含关系为例,相比于ArcGIS,本文提出的算法可达到2 倍的加速比。     

基于Hilbert空间分区和Geohash索引的并行Ripley's K函数

作为二阶点模式分析方法,Ripley's K函数（简称K函数）以距离为自变量探测不同尺度下点事件的分布模式及演变规律,在生态学、经济学、地理学等诸多领域得到广泛应用。然而,随着点规模的增加,估计与模拟阶段点对距离遍历计算时间开销激增,严重制约了K函数的应用,算法流程优化与并行加速成为应对海量点数据下K函数性能瓶颈及可计算性问题的关键技术手段。针对默认数据分区未考虑点事件空间邻近性导致跨节点通讯成本高昂且K函数距离阈值较大时索引优化失效的现象,本文提出一种基于空间填充曲线的K函数优化加速方法。该方法采用Hilbert曲线构建空间分区,在顾及数据空间邻近性的前提下减少分区间数据倾斜和通讯开销;在分区基础上,利用Geohash编码改进各分区内本地空间索引策略加速点对距离计算。本文以湖北省工商企业注册数据为例,通过对比实验分析了默认分区无索引、KDB分区组合R树索引、本文Hilbert分区组合Geohash索引算法在不同数据规模、距离阈值、集群规模下的计算耗时。结果表明,300 000点数据规模下本文方法的时间开销约为默认分区无索引方法的1/4,9台节点下加速比超过3.6倍。因此,该方法能有效提升分布式环境下K函数计算性能并具有良好的可伸缩性,可为其他点模式分析方法的优化提供参考。     

基于C-SOM和Spark的并行空间离群挖掘方法及应用

空间离群挖掘可以发现空间数据集中非空间属性值与邻域中其他空间对象明显不同的空间对象。随着空间数据量的快速增加,传统集中式处理模式面临单机性能瓶颈、难以扩展等问题,已逐渐不能满足应用需要。因此,本文根据Spark并行计算框架,充分利用Spark快速内存计算和扩展性的优势,提出了一种基于考虑约束条件的空间离群挖掘算法（C-SOM）和Spark的并行空间离群挖掘算法和原型系统。该并行算法以C-SOM为核心,并行地在多个计算节点对全局数据集和各局部数据集执行C-SOM算法,得到全局离群和局部离群。轻量级的原型系统基于Spark实现了该并行算法,采用Browser/Server架构,提供给用户可视化的操作界面,简洁实用。最后,通过福建省东南沿海土壤化学元素调查数据和人工合成数据的离群分析,验证了该并行算法和原型系统的合理性、有效性和高效性。     

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

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

基于异构集群计算的地统计面插值并行算法

地统计面插值算法在空间统计分析中有广泛应用,其目的是通过一组面要素的某已知属性值估算另一组面要素的属性值。地统计面插值算法多是基于克里金（Kriging）插值及其衍生算法。克里金插值算法考虑属性在空间位置上的变异性,需计算要素之间的协方差,是典型的计算密集型算法。本文分析了基于克里金插值的地统计算法计算过程,该算法中面要素间协方差计算相互独立,可作为并行计算单元划分。另外,面要素间协方差计算可使用快速傅里叶变换（FFT）快速计算,而FFT是一种非常适合并行处理的计算密集型算法。本文根据算法特征设计了基于异构集群计算的并行算法,并使用MPI+CUDA实现了该算法。实验结果表明,本文实现的算法比使用MPI实现的CPU集群的算法有更好的性能,具备良好的可扩展性,并且随着插值精度提高表现出更好的性能。     

景观指数的并行计算方法

随着地理信息科学和系统的发展,GIS数据的时空分辨率和数据量呈现爆炸式的增长趋势。传统的基于个人计算机的景观指数计算软件难以有效快速地完成海量数据的空间分析。针对该问题,本文提出了一个高效的景观指数并行计算方法。首先对原有的并查集连通域标记算法进行了2点改进：① 在第2次遍历数据时,增加了计算斑块面积、周长等斑块基本信息的功能,为景观指数的计算提供必要参数;② 在第2次遍历过程中,增加了重新标记连续序号的功能,减少了原有算法在合并操作后造成的序号不连续,需要重新遍历数据的开销。在此基础上,本文利用MPI并行编程库,采用数据分割和主从进程协同的并行计算模式实现了景观指数的并行计算。实验表明,在保证计算正确性的基础上,本文的并行算法大幅度提高了景观指数的计算性能,为快速分析大规模数据的景观形态和格局提供了有效手段。     

基于CUDA的IDW并行算法及其实验分析

近些年来,空间数据获取技术得到了迅猛的提高,例如LIDAR,通常可以产生成千上万个点,这对计算机的处理能力提出了挑战.最近,图形处理器(GPU)的计算能力得到了巨大的提升,致使GPU的通用计算引起了关注.GPU是流处理器的集合,最近的设备的流处理器超过240个,浮点峰值比CPU快10多倍.在GPU上编程和编译的环境称计...     

一种基于信息网格的空间数据分解算法

针对空间数据库数据海量且分布的特点,为了能从这些空间数据中更加有效的收集信息和发现知识,介绍了基于信息网格的空间数据挖掘计算模型,在分析空间数据划分一般原则和方法的基础上,针对该计算模型给出了一个数据划分的初步算法,并通过模拟实验对算法的时间性能进行了评价与分析。