多核CPU的海量点云并行kNN算法

提出基于多核CPU的海量点云k最近邻(kNN)快速搜索算法.该算法先将点云数据按格网方式进行组织存储于外存;在搜索kNN点时,从搜索点所在的块向外扩张搜索;在多核CPU环境下采用多线程模式进行数据的内外存调度和kNN点搜索.当内存达到设定上限时,采用距离搜索点最远策略释放内存,降低内外存数据交换的频率.将该方法应用于基于kNN的滤波和格网化方法中,处理速度显著提高.     

基于CUDA的海量点云数据kNN查询算法

通过激光扫描技术获得的点云数据量十分巨大,如何利用k最近邻域(k-nearest neighbors,kNN)查询重建海量点云中各采样点间的拓扑关系,对点云数据的后续处理至关重要。在深入研究GPU编程技术的基础上,将GPU通用计算引入到点云数据的kNN查询问题中,提出一种通过CUDA实现的基于外存的双层查询结构。试验结果表明,该方法与传统算法相比在查询效率上有较大提升,最大增幅可达53.8%。     

海量车载激光扫描点云数据的快速可视化方法

当前车载激光扫描系统的数据量往往达到数十GB乃至TB级,海量激光点云数据的加载与查询对传统可视化方法提出了挑战。本文设计了一种基于内外存调度的三维可视化方法,突破了物理内存对显示数据量的限制。该方法首先利用双层四叉树索引数据结构实现外存储器上的点云数据管理与快速调度,基于该索引动态加载外存储器上的点云数据到内存,从而快速获取海量数据中的实时数据块;然后,利用多线程分时加载双层四叉树索引数据结构,实现激光点云数据外存到内存的实时传输与绘制。实验结果表明,本文方法不受点云数据量与物理内存大小限制,海量点云可视化效果流畅,适用于台式计算机或网络环境下的海量激光点云数据的调度管理与实时可视化。     

格网划分的最邻近点搜索方法

为了提高迭代最近点(ICP)算法中最邻近点搜索的存储和计算效率,本文通过对盒子结构方法优、缺点的深入分析,提出了基于格网划分的最邻近点搜索方法。该方法充分考虑了3D点云获取时的投影特性,将点云投影到某一坐标平面,并基于格网划分进行存储,使最邻近点的搜索限制在较小的范围。不同类型的模拟数据和实测数据试验均表明,该方法能够在不损失匹配精度和拉入范围的前提下,显著提高存储和计算效率。     

一种LiDAR点云生成格网DEM的快速算法

提出一种LiDAR点云快速生成DEM的算法。该算法首先将原始点云文件转换为点云流文件;然后对点云流文件的每个区块采用逐点内插法进行Delaunay三角剖分;最后对生成的三角网流文件进行格网划分,对每个格网点内插生成规则格网DEM。将原始点云文件转换为流文件后,可以对点云数据分块处理,处理完一个分块后即可释放内存,解决了普通计算机处理海量点云数据内存不足、效力低下的问题。     

一套基于虚拟格网的城区LiDAR点云数据滤波流程

针对城区LiDAR点云数据滤波问题,结合城市地区点云数据的特点,引入虚拟格网技术,提出一种基于坡度的城区LiDAR点云数据滤波流程。该流程首先根据点云密度构建虚拟格网;其次基于虚拟格网进行单一阈值法粗差剔除;然后依据最大建筑物边长进行地面种子点选取;最后,基于坡度进行地面点判断。实验方面,通过两组实验验证了该流程的可行性和有效性。     

基于格网化LIDAR点云数据坡度滤波方法的研究

LIDAR数据是目前生产DEM/DSM最为理想的数据源,利用机载激光雷达获取DEM/DSM数据是机载激光雷达最为直接的应用。本文提出了一种将LIDAR点云数据格网化与坡度滤波相结合的点云分类方法,该方法将数据格网化的概念用于LIDAR点云数据的预处理,避免了LIDAR点云数据内插或者平滑造成的信息损失,并且引入坡度突变对格网化处理后的LIDAR点云数据进行第二次地面点的选取,提高了LIDAR点云数据分类的效果。     

车载激光扫描数据中杆状地物提取

针对车载激光扫描数据中对杆状地物提取效果不够理想的问题,该文提出一种基于聚类的杆状地物提取方法。首先将原始点云投影到水平面并进行格网划分,以单个格网为数据处理单元去除地面点;再基于处理数据对格网进行点云探测并编号,赋予同一属性值利用八邻域搜索对地物点聚类;然后以聚类后单个点云块为处理单元,利用各类地物特征,如高度、投影点密度、投影面积及形状等,逐步排除其他地物点,实现对杆状地物的精细提取。试验验证了文中所述方法对道路环境中杆状地物提取的有效性。     

基于四叉树的LiDAR点云数据组织研究

针对传统的数据读取方法不能满足LiDAR点云数据量大的特点,基于Windows的内存映射机制,研究LiDAR点云数据组织,利用四叉树对LiDAR点云数据进行索引管理,并在LiDAR点云的三维场景绘制中对点云数据进行剪裁,减轻CPU的负担,提高其运算的效率.     

基于椭球面投影的散乱点云建立三角格网方法

空间点云数据建立三角格网是三维激光扫描数据处理中重要的处理内容之一。已有的点云三角格网建立方法的网形结构良好,但存在数据量大、计算效率低的特点。提出借助椭球面进行高斯投影建立点云的空间三角格网建立方法,有效地实现四周型点云数据格网建立过程。结合某矿井点云数据实例,对基于圆柱面和椭球面投影的两种方法建立的三角格网进行对比,结果表明,利用椭球面投影法建立三角格网能更有效地建立顶部和底部点云数据的拓扑关系。     

三维散乱点云的Voronoi拓扑近邻点集查询算法

提出一种三维散乱点云的Voronoi拓扑近邻点集查询算法,该算法改进R*-tree建立三维散乱点云的空间索引结构,采用动态扩展空心球算法获取样点的k近邻点集,通过偏心扩展和自适应扩展获取样点拓扑近邻参考数据,生成该局部点集的Voronoi图,查询样点Voronoi邻域获取样点拓扑近邻点集。通过算法时间复杂度分析及相关实验,证明该算法可快速、准确地获取任意复杂散乱点云的Voronoi拓扑近邻点集。     

利用空间微分块与动态球策略的k近邻搜索算法研究

提出了一种基于空间微分块与动态球判定策略的k近邻快速搜索算法。该算法以空间包围盒为基础,首先对空间进行微分块,将离散点分配到子空间;然后,以计算点为球心建立动态球,确定k近邻候选点。球半径可根据空间包围盒的大小、离散点数量和k近邻点数进行估算和优化。实验结果表明,该算法可快速完成k近邻搜索,运行稳定可靠。     

Rapid K-Neighbor Identification Algorithm for the Sphere

Spatial searching, such as the identification of k-nearest neighbors to a point, is one of the most time-intensive tasks in vector-based geographic information systems transformational or analytical operations, and as such continues to impede many studies. While a number of computationally efficient k-neighbor searching algorithms have been developed for d-dimensional monotonic coordinate axes, these methods are inappropriate for spherical coordinates necessary in many global studies. This article briefly examines the assumptions and resulting limitations of k-neighbor searching algorithms with spherical coordinates. One of the simplest, yet most efficient k-neighbor searching algorithms is applicable to spherical applications, if constrained. Comparisons between the processing efficiency of the brute-force searching method commonly in use, a constrained heuristic k-neighbor searching algorithm, and a modified k-neighbor algorithm indicate processing times may be decreased by as much as 99% using such rapid searching methods in global geographic applications.     

Out‐of‐Core GPU‐based Change Detection in Massive 3D Point Clouds

If sites, cities, and landscapes are captured at different points in time using technology such as LiDAR, large collections of 3D point clouds result. Their efficient storage, processing, analysis, and presentation constitute a challenging task because of limited computation, memory, and time resources. In this work, we present an approach to detect changes in massive 3D point clouds based on an out‐of‐core spatial data structure that is designed to store data acquired at different points in time and to efficiently attribute 3D points with distance information. Based on this data structure, we present and evaluate different processing schemes optimized for performing the calculation on the CPU and GPU. In addition, we present a point‐based rendering technique adapted for attributed 3D point clouds, to enable effective out‐of‐core real‐time visualization of the computation results. Our approach enables conclusions to be drawn about temporal changes in large highly accurate 3D geodata sets of a captured area at reasonable preprocessing and rendering times. We evaluate our approach with two data sets from different points in time for the urban area of a city, describe its characteristics, and report on applications.     

适用于多值曲面修复的空洞边界提取方法及应用

摘要：针对常用的空洞边界提取方法在噪声干扰和投影单值方面的缺点,提出一种能克服投影重叠问题而适用于多值曲面修复的空洞边界自动提取方法。首先求出散乱点云的K近邻,利用推进式逐层求解法ALS将各近邻域点投影至平面;然后在平面内进行网格划分及提取边界网格,在此基础上应用最小凸包法提取边界线;最后,进行空洞边界与物体本身边界的识别,为了验证其有效性,将该方法应用于后续的空洞填充及曲面重构中,并用测量采样点到所建曲面模型的最大距离和平均距离为定量评价指标进行精度分析及评价。试验结果表明,采用ALS以及最小凸包法能够保留特征和避免投影重叠,所提取的空洞边界精确,能够满足后续建模的需要。     

基于探测球的固定式扫描海量点云自动定向方法

地面固定式扫描点云首先要将自由坐标系的点云纳入国家坐标系,而单站扫描的点云数据量极大,无法在可视环境下进行拼接。针对现有方法对海量点云拼接的不足,提出一种基于探测球的固定式扫描海量点云自动定向方法,该方法通过数据关联技术读取海量点云、建立标靶搜索环、球拟合确定标靶候选点、全组合距离匹配法确定同名点及坐标转换参数解算等,完成点云的自动定向过程。通过实验验证文中算法的有效性及可行性。     

基于k-d树的机载LIDAR点云滤波处理

点云数据滤波处理是获取高精度数字地面模型的关键,而滤波的基本原理是基于某一邻域内高程的突变。在海量、离散的点云数据中,搜索某一邻域的速度将直接影响滤波处理的效率。应用k-d树组织点云数据,不需要先验地知道点云数据间的拓扑关系便可以快速确定其中某一点的邻域点集,从而大大地提高滤波速度。     

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

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

遥感影像CVA变化检测的CUDA并行算法设计

随着遥感影像数据量以及复杂程度的日益增加,遥感图像的快速处理成为实际应用过程中亟需解决的问题。为了实现遥感影像的实时变化检测,针对基于变化矢量分析CVA的变化检测算法,设计了一种基于统一计算设备构架CUDA的并行处理模型。首先利用地理空间数据提取库GDAL实现大数据量遥感影像的分块读取、操作和保存;其次将基于变化矢量分析的变化检测过程分为变化强度检测、映射表构建和变化方向检测,并借助CUDA C将变化矢量分析算法的3个步骤嵌入到CPU和GPU组成的异构平台上进行实验;最后利用该模型对不同数据量的遥感影像进行CVA变化检测并作对比分析。实验结果表明:与CPU串行相比,基于GPU/CUDA的遥感影像CVA的变化检测速度提高了10倍左右;在一定程度上,达到了实时变化检测的效果。     

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

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