空间聚类有效性评价方法对比与研究

空间聚类是当前地球信息科学与计算机科学领域共同关注的热点问题之一,常用来揭示空间数据分布规律以及发现空间数据异常。空间聚类有效性评价即对空间聚类结果进行定量、客观的评判,对于在实际应用中针对不同数据集选取最优的空间聚类算法以及确定最佳的聚类参数具有重要意义。首先选取并编程实现了数种空间聚类有效性评价方法,包括聚类中心的距离矩阵、距离方差、改进Hubert's统计、Davies-Bouldin、Calinski-Harabasz和基于信息论的空间聚类有效性评价方法等,同时提出了顾及簇间分离度和簇内紧凑度的空间聚类有效性评价方法,并通过试验分析验证了其可行性及有效性。然后在K-Means法对数据集进行聚类的基础上,对比研究了前述聚类有效性评价方法的特性及优缺点。     

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

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

基于多传感器融合式航迹起始算法

提出了一种基于聚类分析和Kalman 滤波相结合的多传感器航迹起始算法.根据多传感器同一时刻对同一目标的观测值在空间呈团状的特征,运用聚类的方法解决数据融合问题.采用一种改进的粒子群(PSO)优化算法对多传感器观测数据进行聚类,结合聚类中心和目标预测值,应用Kalman滤波器估计目标状态,从而实现航迹起始.实验结果表明,该方法有效.     

基于密度的线数据分组算法研究

目前,地理空间数据面临着由于数据量膨胀和计算量高速增长而引起算法效率低的问题,采用"分而治之"的数据分组策略提高运算效率已成为研究的热点。面向分布不均匀的线数据,本文提出了基于密度的线数据分组算法(简称LGAD)。首先,算法通过查找高密度区提取样本线段,保证了分组算法的起点落到高密区;其次,考虑线空间拓扑关系的复杂性,引用水平、垂直和夹角距离度量线段间距离,创建样本线段与其他线段的距离矩阵;最后,以距离矩阵和最优选择方法实现数据负载均衡分组。实验结果显示,对数据分组和分组后数据进行线段聚类的2个过程中,该算法体现了较好的时间优势,与串行计算相比,在分组数为2-12 时,平均比率达4.3,提高了应用的响应速度,具有较好的实际意义。     

基于反泄漏Fourier变换的地震数据重建方法

应用反泄漏Fourier重建方法,对空间方向采样不规则的地震数据进行规则化重建,引入GPU加速算法,将非均匀Fourier变换部分转化为矩阵乘法形式,将矩阵乘法部分应用于GPU加速算法加速处理。理论模型与实际数据测试结果验证该方法的有效性及合理性。     

基于MapReduce的网格化优化CURE算法的实现

针对CURE算法处理大量数据时聚类速度较慢的问题,一方面采用网格聚类方法对初始聚类对象进行网格预聚类处理,缩短初始化族聚类时间;另一方面采用MapReduce框架对算法进行并行性扩展,使其能够充分利用集群的计算和存储能力,从而加速海量数据的处理。以联合程序开发网站的数据集和MATLAB人工数据集作为测试数据集,对改进算法Grid-CURE进行实验分析。实验结果表明:方法可有效提升处理大数据的效率以及提升其抗噪声能力。     

基于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算法的提出可为大数据量、多变的自动化空间应用分析提供技术支撑。     

多边形叠加Vatti算法的VCS优化方法与GPU并行化

Vatti算法是常用的矢量多边形裁剪算法之一,在其构建扫描束实现交点计算的过程中,二叉树的数据结构和递归计算方法导致其计算效率受矢量多边形边界顶点数量影响显著。本文针对Vatti算法执行过程中较为耗时的扫描束构建环节,提出了一种多边形边界顶点预排序的优化方法——VCS（Vertex Coordinate Pre-Sorting）方法,并基于该方法实现了对Vatti算法的GPU细粒度并行化。VCS方法使用双向链表对Vatti算法原有的二叉树数据结构进行了替换,以较小的额外存储空间取得了多边形边界顶点信息查找效率的明显提升。在GPU环境下采用双调排序算法对多边形边界顶点数组元素进行并行化排序并过滤出有效值,克服了原始算法使用二叉树存储导致效率低下的问题。实验结果表明,改进后的算法与原始算法相比,具有相同的计算精度;当多边形顶点数量为92万,CUDA每个线程块中的线程数量为32时,使用VCS优化方法,与采用CPU计算构建扫描束方法相比,GPU并行化方法获得了39.6倍的相对加速比,矢量多边形叠加分析算法效率总体上提升了4.9倍。     

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

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

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

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

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

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

Retinex图像增强在GPU平台上的实现

伴随着无人机时代的到来,对海量数据处理的实时性要求越来越高。本文在GPU（Graphic Processing Unit）平台上实现了Retinex图像增强算法的并行处理,提升了Retinex图像增强算法处理高分辨率数字图像的处理速度。首先,通过数据合并访问和内存数据交互技术实现了数据的快速访问,缩短了数据在不同种类内存间的传输时间,提升了数据访问的效率;然后,采用内核指令优化和数据并行计算技术,实现了Retinex图像增强算法在GPU平台上的多核程序设计;最后,采用主机端和设备端的异步执行模式,在数据传输的同时进行内核数据的并行计算,通过任务级的并行进一步缩短了算法在GPU平台上的执行时间。研究表明,对于不同分辨率的图像,Retinex图像增强算法的处理速度相比于CPU平台均有数十倍的提高,如处理一帧分辨率为2048像元×2048像元的图像仅需要38.04 ms,算法的处理速度较CPU提高了40倍。     

网络地理信息服务中用户空间访问聚集行为研究

研究网络地理信息服务用户的访问行为,有利于了解用户地理信息兴趣、实现按需服务。本文基于全空间信息系统建模的理论,构建用户-访问城市关系网络,研究用户访问的空间聚集性。顾及到关系网络中行为关系强度的表达需要同时考虑用户访问行为、城市关联关系和城市结构,仅用单一的用户访问行为数据会存在偏差,本文提出了基于矩阵分解的数据融合方法,对网络地理信息服务中用户访问数据、城市关联数据以及城市的POI（兴趣点）数据进行融合,表达用户-城市访问关联强度。在此基础上,基于关系网络聚类方法实现用户的聚集模式挖掘。考虑到只以空间距离实现聚类的方法无法兼顾关系网络中用户对不同城市的访问偏好特征,本文在FCM（模糊C均值聚类算法）的基础上以用户对城市的访问概率定义访问偏好提出PFCM算法,同时兼顾关系网络中城市间的空间距离和访问行为关系强度,减小聚类结果的偏差。本研究通过用户访问的空间聚类表达用户访问的空间兴趣偏好,有助于理解用户访问行为与城市之间的相互关系,为网络地理信息服务在数据缓存和提前推送等方面的性能提升提供指引,从而更好的服务于用户访问。     

耦合卡尔曼滤波和多层次聚类的中国PM2.5时空分布分析

近年来,细颗粒物污染尤其是PM_2.5受到人们越来越多的关注,研究PM_2.5的时空分布规律也具有越来越重大的意义。传统的遥感反演方法模型复杂,且不能揭示近地表面的PM_2.5分布规律。地面监测站的建设为PM_2.5的研究提供了更实时的观测数据,但由于测量噪声的影响,观测数据存在不准确的极端异常值。为了揭示中国PM_2.5的时空分布特征,本研究采用Kalman滤波对2015年中国338个城市的空气质量监测网络大数据进行最佳估计,并分析其时空特征。同时,根据中国各城市的PM_2.5浓度的时序分布,采用基于DTW的K-Medoids聚类方法将其分为4个等级,并采用q统计量来评估PM_2.5浓度分布的空间分层异质性。结果表明,采用Kalman滤波能有效去除数据噪声,峰值信噪比（PSNR）明显增大。在时空分布上,中国PM_2.5时间分布曲线呈现“U”形,冬季PM_2.5浓度明显高于夏季,且日变化曲线呈现“W”形;秋冬季PM_2.5浓度的空间分层异质性非常显著,且空间分布呈现“双核分布”,重污染区主要分布在华北平原、新疆等地,西藏、广东、云南等地是稳定的空气质量优良区。     

基于CUDA的地表水动态模拟并行方法

如何高效地动态监测、模拟和预测地表水过程是防灾减灾中亟待解决的问题,也是科学化的国土整治、区域规划、环境保护和水资源管理的基础。因此,本文利用统一计算设备架构(CUDA)对基于不规则三角网(TIN)的地表水动态模拟算法进行并行化改进,提出了一种基于CUDA的地表水动态模拟并行方法,旨在对任意时刻的地表水进行快速、高精度的动态模拟,从而满足实际的应用需求。该算法从高精度的数字高程模型(DEM)中提取地形特征点和流域线,生成受流域线约束的TIN。在此基础上,根据TIN表面的三角面坐标数据获取水流方向,再结合任意位置的降雨源点追踪得到流水线网络。基于曼宁公式,利用流水线流速计算核函数得到每条流水线上雨滴的流速,结合预设的时间,利用汇流量统计核函数得到该时刻的地表汇流量。具体的并行化过程包括数据的传输,CUDA中线程的划分和流水线流速计算核函数和汇流量统计核函数的实现。本文选取位于加拿大新布伦瑞克西北部的BBW(Black Brook Watershed)流域作为实验样区,将该算法与改进前的方法进行对比表明,该模型在保持精度的同时,大幅提高了模拟效率,加速比达到11.2;另外,通过与SWAT(Soil and Water Assessment Tool)模型进行对比,结果表明,该并行方法的Nash系数提高了88%,相关系数提高了5%。     

基于GPU并行加速的叠前逆时偏移方法

为了提高复杂地下介质的成像精度和偏移算法的计算效率,提出可高效对地下复杂构造进行准确成像的GPU加速叠前逆时偏移方法.该方法采用双程声波方程进行波场延拓,突破倾角限制,借助于高阶有限差分方法实现叠前逆时偏移成像;利用GPU(Graphic Processing Unit)并行加速技术对波场延拓和成像进行计算,相比于传统算法,其计算效率有较大提高,可以解决叠前逆时偏移算法计算量过大问题;在获取波场信息过程中,也采用随机边界条件,实施以计算换存储策略,解决逆时偏移计算中的海量存储问题.模型测试结果表明,该方法能够高效和高精度地对地下复杂地质体成像.     

基于MapReduce的空间敏感性分析并行算法设计

近年来,随着遥感空间数据广泛应用于生态系统,推动了区域尺度生态遥感参数模型的发展。敏感性分析对识别模型关键参数,降低模型不确定性和完善模型具有重要作用。区域尺度的生态遥感参数模型,在进行模型参数敏感性分析时,由于涉及到空间数据的复杂运算,单机环境无法满足快速分析的要求。为了提高生态遥感参数模型空间敏感性分析效率,本文以青藏高原为研究区域,利用植被光合模型VPM(Vegetation Photosynthesis Model)和开源云计算平台Hadoop,设计和实现了基于Sobol′的生态遥感参数模型空间敏感性分析并行算法,并在实验室集群环境下进行算法分析,验证了算法的有效性和适用性。该算法的核心是利用MapReduce并行编程技术,对空间敏感性分析中的地图抽样和模型迭代过程进行任务分割,将分割后的子任务分配至不同的计算节点进行并行计算。实验表明,本文提出的并行策略,能有效缩短地图抽样和模型迭代计算时间,相比于单机算法,并行算法的运行速度提高了14倍左右。     

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

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