基于PMVS算法的大规模数据细粒度并行优化方法

三维多视角立体视觉算法（patch-based multi-view stereo，PMVS）以其良好的三维重建效果广泛应用于数字城市等领域，但用于大规模计算时算法的执行效率低下。针对此，提出了一种细粒度并行优化方法，从任务划分和负载均衡、主系统存储和GPU存储、通信开销等3方面加以优化；同时，设计了基于面片的PMVS算法特征提取的GPU和多线程并行改造方法，实现了CPUs_GPUs多粒度协同并行。实验结果表明，基于CPU多线程策略能实现4倍加速比，基于统一计算设备架构（compute unified device architecture，CUDA）并行策略能实现最高34倍加速比，而提出的策略在CUDA并行策略的基础上实现了30%的性能提升，可以用于其他领域大数据处理中快速调度计算资源。     

一种面向CPU/GPU异构环境的协同并行空间插值算法

CPU/GPU异构混合系统是一种新型高性能计算平台,但现有并行空间插值算法仅依赖CPU或GPU进行加速,迫切需要研究协同并行空间插值算法以充分利用异构计算资源,进一步提升插值效率。以薄板样条函数插值为例,提出一种CPU/GPU协同并行插值算法以加速海量激光雷达（light detector & ranger,LiDAR）点云生成数字高程模型（DEM）。通过插值任务的分解与抽象封装以屏蔽底层硬件执行模式的差异性,同时在多级协同并行框架基础上设计了Greedy-SET动态调度策略,策略顾及底层硬件能力的差异性,以实现异构并行资源的充分利用和良好负载均衡。实验表明,协同并行插值算法在高性能工作站上取得19.6倍的加速比,相比单一CPU或GPU并行算法,其效率提升分别达到54%和44%,实现了高效的协同并行处理。     

一种利用GPU加速的轨迹线热力图生成显示方法

为解决大数据量带来的热力图生成效率低的问题,引入基于图形处理器(graphic processing unit,GPU)的并行计算方法,并结合轨迹线模型,提出了一种利用GPU加速的轨迹线热力图生成显示方法。首先,针对轨迹点分布不均、邻域半径设置不合理等条件下产生的热力值不连续、不均等问题,采用轨迹线模型提升了热力图的效果。其次,针对大规模数据计算产生的热力图生成效率低的问题,通过GPU并行计算并配合内核函数参数调优、循环展开、像素缓冲对象显示等策略大幅提升算法计算效率。实验结果表明,所提方法较传统的基于中央处理器（central processing unit, CPU）的方法计算效率提升了5~30倍,且随着图像分辨率和轨迹数据的增加,算法加速比有逐步上升的趋势。     

多级存储优化的大规模全局光照快速计算

针对大规模复杂场景渲染的全局光照计算量大从而影响其渲染实时性的问题，提出了一种基于多级分辨率纹理存储结构的改进体素锥追踪全局光照算法。算法首先采用基于人眼视觉特性的多级分辨率纹理存储结构高效存储光照信息，并在直接光照计算时，结合存储结果特点，然后采用混合存储的GPU硬件加速与无贡献节点丢弃的软件加速相结合方法，进一步提高光照渲染效率，最后基于多级纹理及闭合体节点自适应合并对锥波滤器进行改进，实现全局光照的高效计算。试验结果表明，改进算法减少了光照计算量，降低了系统内存占用，并取得了与经典算法相近的场景光照渲染效果，从而验证了其在大规模光照计算的有效性。     

CPU和GPU协同的多光谱影像快速波段配准方法

随着遥感影像数据量的飞速增长,传统的串行波段配准方法已无法满足大数据多光谱影像的实时配准需求。针对该问题,提出了一种CPU和GPU协同的多光谱影像快速波段配准方法。首先进行计算量和并行度分析,将同名点匹配和微分纠正映射至GPU执行,仿射变换系数拟合仍驻留在CPU执行。其次通过核函数任务映射和基本设置,使算法步骤在GPU上可执行,并设计了3种性能优化方法(访存优化、指令优化、传输计算堆叠),进一步提高了波段配准的执行效率。在NVIDIA Tesla M2050 GPU和Intel Xeon E5650 CPU组成的实验平台上,对遥感26号卫星多光谱影像的实验表明,使用该方法加速后的波段配准执行时间仅为3.25 s,与传统串行方法相比,加速比达到了32.32倍,可以满足大数据多光谱影像的近实时配准需求。     

基于NDT和ICP融合的点云配准方法

针对传统迭代最近点算法高精度低效率与正态分布变换算法高效率低精度的问题,提出了基于NDT与ICP融合的点云配准方法。首先通过NDT算法选择合适的网格参数将待匹配的点云向目标点云拉近以提高配准效率,完成粗配准,其次使用KD树加速的ICP算法求解变换矩阵以提高配准的计算效率。通过实验表明,本文方法匹配速度相比NDT算法和ICP算法有明显提高,且精度高于NDT算法。     

利用GPU的R树细粒度并行STR方法批量构建

大数据时代,需要对海量空间数据更快速地建立高效索引,使用递归排序网格(STR)方法构建的R树具有优秀的查询性能,但构建效率不高。本文利用基于计算机图形处理器(GPU)的通用计算具有细粒度可并行性的特点,提出了一种基于STR算法的R树GPU并行构建算法,使用线性数据结构存储R树,并且用整体排序代替分段排序,细化算法的并行粒度。实验结果表明,同CPU算法相比,本文算法的加速比最高可达27倍,并且呈现出随着数据量增大而变大的趋势。本文算法充分利用GPU的并行处理能力,高效构建了性能优越的R树空间索引。     

自适应分块加权Wallis并行匀色

针对区域范围内多幅待镶嵌影像之间的色彩差异问题,提出一种基于GPU的分块加权Wallis并行匀色算法。首先,根据变异系数对影像自适应分块并利用双线性插值确定每一个像素的变换参数,利用加权Wallis变换消除影像间的色彩差异。然后,为了控制区域整体的匀色质量,利用Voronoi图和Dijkstra算法确定影像间的处理顺序。最后,利用GPU技术进行并行任务设计并从配置划分、存储器访问和指令吞吐量等方面进行优化,提高算法运算效率。实验结果表明,本文方法既能有效地消除影像间色彩差异,又能消除影像间的对比度差异。与CPU串行算法相比,GPU并行算法显著减少了计算时间,加速比最高达到60倍以上。     

基于多GPU的Harris角点检测并行算法

提出了一种基于多图形处理器(graphic processing unit,GPU)设计思想的Harris角点检测并行算法,使用众多线程将计算中耗时的影像高斯卷积平滑滤波部分改造成单指令多线程(single instruction multi-ple thread,SIMT)模式,并采用GPU中共享存储器、常数存储器和锁页内存机制在统一计算设备架构(com-pute unified device archetecture,CUDA)上完成影像角点检测的全过程。实验结果表明,基于多GPU的Har-ris角点检测并行算法比CPU上的串行算法可获得最高达60倍的加速比,其执行效率明显提高,对于大规模数据处理呈现出良好的实时处理能力。     

图划分支持下的大规模点要素并行缓冲分析方法

缓冲分析是解决邻近度问题的基础工具,由于算法本身包含大量的复杂运算,处理效率亟待优化。针对大规模点要素的缓冲分析,引入图表达建立了面向数据和分析过程的空间计算域,通过图划分实现了任务的均衡分割。图式化的空间计算域首先从图节点和图边两个角度定义了点要素及其空间关系的处理函数,然后对相应的时间复杂度进行拟合,获取了图节点和图边的计算权重,最后利用图划分方法实现了缓冲分析的均衡分割,从而构建与计算资源相匹配的并行任务。实验结果表明,基于图划分实现的并行缓冲分析方法在负载均衡性和整体性能方面优于主流的四叉树和规则格网划分方法,可为大规模矢量数据的空间分析优化提供参考。     

基于GPGPU的并行影像匹配算法

提出一种基于GPGPU的CUDA架构快速影像匹配并行算法,它能够在SIMT模式下完成高性能并行计算。并行算法根据GPU的并行结构和硬件特点,采用执行配置技术、高速存储技术和全局存储技术三种加速技术,优化数据存储结构,提高数据访问效率。实验结果表明,并行算法充分利用GPU的并行处理能力,在处理1280×1024分辨率的8位灰度图像时可达到最高多处理器warp占有率,速度是基于CPU实现的7倍。CUDA在高运算强度数据处理中呈现出的实时处理能力和计算能力,为进一步加速影像匹配性能和GPU通用计算提供了新的方法和思路。     

GPU-CA模型下的溃坝洪水演进实时模拟与分析

基于元胞自动机(CA)的局部并行计算特性和统一计算设备架构(CUDA)并行计算架构,提出了GPU-CA的溃坝洪水演进计算模型,重点探讨了溃坝洪水演进元胞自动机模型、GPU模型映射、计算优化、CPU/GPU协同的溃坝洪水演进模拟与分析等关键问题,研发了原型系统,并选择了案例进行初步试验。试验结果表明,在保证溃坝洪水演进模拟结果有效性的情况下,与基于CPU-CA串行计算模式相比,基于GPU-CA的溃坝洪水演进模型计算可提高计算效率,加速比随着元胞格网分辨率的提升而增加,当元胞格网的大小为10m时,模型计算效率的加速比可以达到15.9倍,可支持实时溃坝洪水演进模拟分析与风险评估。     

三维点云数据实时管理的Hash map方法

本文基于机器视觉探讨数字摄影测量三维构像下的智能数据处理要素之一：海量点云高效管理技术,提出了一种基于GPU的hash map三维点云数据组织的改进算法,算法可以高效地完成数据的动态插入、更新和索引,而不受数据规模限制。同时,通过传感器位置姿态估计当前活动范围,进行主机与GPU的数据交换,保证了GPU的低内存占用率。在搭载不同等级显卡（GTX960、GTX1050、GTX1060）的计算机设备上试验,本文算法均可以达到60 fps以上的帧率（单帧处理点云数：2.11×10⁵）,证明算法满足了三维构像中三维点云数据高效管理的要求。     

大规模遥感影像全球金字塔并行构建方法

金字塔模型是大规模遥感影像可视化的基础,是在保证精度的前提下,采用不同分辨率的数据来提高渲染速度,从而在网络环境下实现大规模数据共享、服务和辅助决策支持。在构造金字塔的过程中,由于遥感数据经常会突破内存的容量,同时会产生大量的小瓦片,小瓦片存贮非常耗时,传统的串行算法很难满足应用需求。本文提出了一种并行大规模遥感影像的全球金字塔构造算法,利用图形处理器(graphics processing unit,GPU)的高带宽完成费时的重采样计算,使用多线程实现数据的输入和输出,在普通的计算机上实现大规模影像的全球金字塔的快速构建。首先,采用二级分解策略突破GPU、CPU和磁盘的存储瓶颈;然后,利用多线程策略加速数据在内存和磁盘之间的传输,并采用锁页内存来消除GPU全局延迟的影响;最后,用GPU完成大规模的并行重采样计算,并利用四叉树策略提高显存中数据的重复利用率。实验结果表明,本文方法可以明显地提高全球金字塔的构造速度。     

基于网络Voronoi图的大规模多仓库物流配送路径优化

由于存在多约束和多个优化目标,物流配送决策非常困难。针对城市多仓库物流配送问题,提出基于网络Voronoi图的空间启发式优化方法。从空间角度,将多仓库物流配送优化分解为区域分割和路径优化两个空间子问题。基于网络Voronoi覆盖进行服务区域初始划分,顾及仓库容量差异,进行区域边界修正,并创建初始解。路径优化将局部搜索范围限定在网络K近邻内,只搜索最有可能的空间邻域,迭代改进解的质量。该算法最小化路径数量和路径长度。利用深圳市的大规模多仓库物流配送问题测试算法性能。试验结果表明：本文方法能够在15min内求解6400个客户点的大规模物流配送问题,解的质量优于ArcGIS约10.8%,计算时间约为其21.2%。     

一种基于GPU的DEM并行插值算法

采用Open CL框架下的CPU/GPU平台,借助GPU在并行浮点运算方面的巨大优势,提出了DEM并行插值算法;同时以反距离加权插值算法为例,分析了传统插值算法和并行插值算法之间的优缺点与适应性。最后,通过对比实验对两类算法进行了比较。实验表明,当插值点数较少时,GPU并行插值算法效率低于传统算法;然而,当插值点数很高时,并行插值算法的计算效率较传统插值算法有了显著提高,加速的效果甚至高达137倍。实验证明GPU并行插值算法具有很强的可行性。     

面向汛旱情监测的遥感影像GPU并行处理算法

针对面向汛旱情监测应用中遥感影像处理耗时过长的问题,包括辐射校正、几何纠正、遥感指数计算等过程,对其业务化工作流程进行了分解分析。结合统一计算架构(compute unified device architecture,CUDA)的存储结构和程序设计模型,将数据处理过程划分为数据读取、直方图统计、栅格分割、波段计算、重采样和数据输出等模块,对波段计算及重采样等模块设计了并行处理方案,并通过实验确定了栅格划分的最佳尺度,基于栅格数组图形处理器(graphics processing unit,GPU)映射方法加速了数据传输效率,最终提出了基于CUDA架构CPU-GPU协同的并行处理算法。实验结果表明,辐射校正及遥感指数计算的波段计算模块可节约58.9%的时间;几何纠正效果最为显著,最邻近像元重采样和双线性内插重采样模块的最终加速比分别能够达到9倍和7倍以上。     

GPU并行区域网平差

为了进一步解决大数据量带来的平差效率低下的问题,引入GPU并行计算技术,同时使用预条件共轭梯度法以及不精确牛顿解法求解区域网平差过程中的法方程,构建了适用于GPU并行计算的全新的区域网平差技术流程。本文方法避免了存储法方程系数矩阵,而是在需要的时候实时的计算该矩阵,使得本文算法相较于传统的算法所需的计算机内存空间大幅减少(仅需要存储平差原始数据即可),平差计算速度明显提升,同时计算精度与传统方法相当。初步试验证明,本文的方法在普通电脑上仅需要约1.5min即可完成对4500张影像、近900万像点数据的平差计算,且计算精度达到子像素级。     

一种求解学区划分问题的混合启发式算法

针对目前求解学区划分问题算法搜索过程缺乏记忆,搜索效率不高,容易陷入局部最优而收敛慢等问题,该文提出一种多启动(M)框架下,迭代禁忌搜索(ITS)算法与模拟退火(SA)算法混合的M-ITS-SA算法。该算法包括构造初始解、禁忌搜索、SA算法优化与求解等。运用K-Medoids模型对学校分组后,采用M-ITS-SA算法对学区进行划分与优化,并从多个分区方案中求解最优分区方案。学区划分实验结果表明:该文提出的M-ITS-SA算法能够保证分区的空间连续性,适用于单校和多校划片,并在入学总距离上与混合元启发算法(M-ILS-SPP)保持相当的同时,大大降低了超额招生人数和总用时,具有良好的寻优能力和收敛性,优于M-ILS-SPP算法。     

时空谱多星协同任务规划算法研究

介绍了多星协同任务规划的重要性以及时空谱多星协同任务规划的优点,基于时间、空间和光谱协同观测约束优化模型,以金矿尾矿库污染、水资源污染和耕地荒漠化问题为例ꎬ分别在新疆伊犁河流域尾矿库区域、塔里木河流域和阿克苏区域随机生成观测任务,根据观测任务选取了多个成像卫星,通过仿真实验研究了基于启发式规则的贪婪算法、遗传算法、爬山算法对模型的求解效率和优化结果.验证了引入适宜度的必要性ꎬ以未观测点、任务适宜度、优先级、任务总价值为比较指标ꎬ综合分析和比较任务的总价值,验证了贪婪算法在本文模型中优于遗传算法和爬山算法.