基于GPU的全波形并行LM分解算法

波形分解是机载激光雷达全波形数据处理的重要基础工作,通过求解波形函数模型的参数,将波形数据利用具体的函数模型拟合出来,实现对全波形及其中各个子波形函数表达。LM(Levenberg-Marquardt)算法及其改进的算法是波形分解中对参数进行拟合求解的常用方法。针对LM算法在参数拟合计算的过程中存在大量迭代和矩阵运算,提出了基于线程块组和线程两级并行粒度的并行计算方案。将串行多次循环迭代求解参数改为单次并行计算取最佳值实现对参数的选择,将矩阵运算进行线程块的协同并行计算,实现了LM算法在通用计算图形处理器上的并行计算。实验证明,在规定阈值条件下,并行LM降低了算法的迭代次数,提高了波形分解LM算法的计算效率,为提高波形分解的处理效率提供了研究思路。     

改进的EM模型及其在激光雷达全波形数据分解中的应用

随着数据存储能力和处理速度的提高,小光斑机载激光雷达系统已经可以通过数字化采样来存储整个反射波形,而不仅仅是由系统提取出来的三维坐标(即离散点云).分析波形数据最重要的优点之一是可以在后处理过程中让使用者自己来提取三维坐标.一般的分解方法基于非线性最小二乘的多项式拟合,或者有设备厂商提供的简单阈值法,无法获得高精度的分解结果.本文使用改进的EM脉冲检测算法得到回波脉冲的位置和宽度,证明是一种性能可靠、精度较高的波形分解算法.     

大光斑激光雷达数据的森林冠层高度反演

针对传统的LM波形分解算法在GLAS大光斑波形数据处理中容易陷于局部最优解,限制了GLAS大光斑激光雷达数据在森林结构参数反演方面应用的问题,该文结合GLAS大光斑数据特征,引进优化后的EM算法对大光斑全波形数据进行分解,获取波形参数最优值。结合波形前缘长度和波形后缘长度,建立树高反演模型,并与LM分解算法建立的模型进行对比分析。研究结果表明,通过改进的EM算法对GLAS大光斑激光雷达数据进行处理,波形特征参数的获取更为精确,达到了较高的树高反演精度。     

基于激光雷达波形数据的点云生产

随着数据存储能力和处理速度的提高,小光斑机载激光雷达系统现在已经可以通过数字化采样来存储整个反射波形,而不仅仅是由系统提取出来的3维坐标(即离散点云).分析波形数据最重要的优点之一是可以在后处理过程中让使用者自己来提取3维坐标.一般的分解方法基于波形的局部最大值和波形的重心,或者有设备厂商提供的简单阈值法,无法获得高精度的分解结果.本文使用改进的EM脉冲检测算法来得到回波脉冲的位置和宽度,并能得到高质量的点云数据,为DSM(Digital Surface Model)和DTM(Digital Terrain Model)生产提供优质数据源.     

PC集群环境下的并行地理网络车辆路径算法

针对PC集群计算节点内存小、进程间通信速度慢的问题,本文设计了分布式的数据存储机制;提出了用同步变换规则代替解编码传输的进程间通信方式;基于邻域分解策略实现了禁忌搜索过程的并行化,发展了一种适用于PC集群环境的并行地理网络VRP算法。应用模拟路网数据进行了相关试验,结果表明：本文算法的计算结果与ArcGIS基本一致,二者平均偏差率在2.11%~2.87%之间;分布式数据存储策略有效地降低了各进程对内存的需求量,保证了算法的稳健性和扩展性;通过算法的并行化提高了VRP算法的求解效率;该算法具有良好的加速性能,8进程时在各测试数据集中的加速比均在4.46~6.32之间。     

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

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

本质矩阵优化分解的相对位姿估计

针对从影像恢复摄像机相对位姿的问题,提出了一种基于李群表示的本质矩阵快速分解的位姿估计算法。通过加权最小二乘方法优化了本质矩阵;利用本质矩阵和平移向量的关系求出了平移向量;由本质矩阵和位姿参数的等式关系建立目标函数,基于姿态的李群表示推导了旋转矩阵迭代估计过程;优化了唯一解确定的约束条件,避免了特征点的三维重建。仿真实验和真实图像实验表明提出的算法精度和鲁棒性均优于传统算法,算法效率得到明显提高。提出的算法避免了矩阵奇异值分解运算和大量的矩阵计算,而且只需对两组解进行唯一解确定,能够实现相对位姿的快速高精度估计。     

有界不确定性平差模型的迭代算法

针对现有的有界不确定性平差模型算法较为复杂且没有顾及权重的问题,该文提出了一种无需奇异值分解的迭代算法及其一种加权方法。直接采用了迭代算法求解有界不确定性平差模型的min-max准则,推导出了未知参数估值,算法概念简单,易于实现,收敛速度更快。基于该文提出的迭代算法,当系数矩阵和观测向量各自均不等权时,采用了一种加权方法,并推导了其解算过程。算例结果表明:该文提出的迭代算法是可行的,并且解算效率更高;加权后的迭代算法是有效的。     

流域最佳管理措施情景优化算法的并行化

流域最佳管理措施(beneficial management practices,BMPs)情景优化问题是一个典型的复杂地理计算问题,目前所常用的BMPs情景优化算法需要结合流域模型进行大量的迭代运算,因而花费大量计算时间,难以满足实际应用的要求。本文针对目前代表性的BMPs情景优化算法——ε支配多目标遗传算法(ε-NSGA-II),采用主从式并行策略,利用MPI并行编程库实现了该优化算法的并行化。在江西省赣江上游的梅川江流域(面积为6 366km2)进行BMPs情景优化的应用案例表明,并行化的优化算法当运行于集群机时,加速比随着核数(8~512核)的增加而递增,当核数为512时,加速比达到最大值(310);并行效率随着核数的增加逐渐下降,最高值0.91,最低值0.61,取得了明显的加速效果。     

北斗/惯导的快速混合高斯UKF算法

为进一步改善北斗/惯导中无迹卡尔曼滤波的精度,针对导航系统中噪声随机模型本质上的非高斯分布特性,结合有限高斯概率分布可近似任意概率密度函数的理论,以混合高斯UKF滤波为框架,提出了一种快速混合高斯UKF算法。该算法使用奇异值分解替代无迹变换产生采样点中的协方差平方根计算,和迭代中构造有限分量混合高斯模型二次近似后验二阶矩减少子滤波器数量的思路,改善了传统算法子滤波器数量随迭代次数成指数变化而增加计算成本的状况,一定程度上提高了计算的实时性。通过对北斗/惯导紧耦合系统的数据仿真实验,结果分析表明:相对于传统算法,本文提出的新算法在保证滤波精度的同时,计算量较低、实时性较好,适合于处理非高斯非线性北斗/惯导组合导航定位的滤波计算问题。     

A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs

This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10⁸ polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.     

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

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

CUDA和OpenCV图像并行处理方法研究

CUDA架构与传统GPU通用计算相比,编程更简单、应用领域更广泛,将CUDA架构引入到图像处理中可以提高图像的处理效率。本文提出了一种基于CUDA和OpenCV的图像并行处理方法,实现了图像二值化以及融合,经实验结果表明基于该方法可以提高图像处理效率;将该方法集成到MFC框架,能够应用到实际工程开发领域。     

An efficient data organization and scheduling strategy for accelerating large vector data rendering

Rendering large volumes of vector data is computationally intensive and therefore time consuming, leading to lower efficiency and poorer interactive experience. Graphics processing units (GPUs) are powerful tools in data parallel processing but lie idle most of the time. In this study, we propose an approach to improve the performance of vector data rendering by using the parallel computing capability of many‐core GPUs. Vertex transformation, largely a mathematical calculation that does not require communication with the host storage device, is a time‐consuming procedure because all coordinates of each vector feature need to be transformed to screen vertices. Use of a GPU enables optimization of a general‐purpose mathematical calculation, enabling the procedure to be executed in parallel on a many‐core GPU and optimized effectively. This study mainly focuses on: (1) an organization and storage strategy for vector data based on equal pitch alignment, which can adapt to the GPU's calculating characteristics; (2) a paging‐coalescing transfer and memory access strategy for vector data between the CPU and the GPU; and (3) a balancing allocation strategy to take full advantage of all processing cores of the GPU. Experimental results demonstrate that the approach proposed can significantly improve the efficiency of vector data rendering.     

基于多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倍的加速比,其执行效率明显提高,对于大规模数据处理呈现出良好的实时处理能力。     

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

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

GPU并行区域网平差

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

基于 GPU 的 GNSS 信号跟踪设计与实现

软件接收机在数据后处理、算法设计与分析等方面发挥着重要的作用。由于传统的软件接收机均是由CPU 处理器实现,处理效率低下。图像处理单元是高度并行化的处理器,将导航信号处理中并行程度高且对时间要求最为严格的跟踪环节与GPU 的并行处理结构有机结合,能大大提升程序的效率。本文解决了采用GPU实现信号跟踪的关键技术,给出了相关的设计方案,并实现。试验结果表明：采用GPU 实现信号的跟踪,其效率提升了112.5倍。     

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

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