基于QTM的球面Voronoi图生成算法与应用

发布时间：2018-05-30 19:39

本文选题：球面Voronoi图 + 确定归属算法　；参考：《中国矿业大学(北京)》2016年博士论文

【摘要】：随着全球生态环境、社会经济一体化的不断深入,人们的研究区域逐渐从局部区域扩大到整个地球。而摄影测量、遥感、全球定位系统等现代对地观测技术的快速发展,使得全球大范围、多尺度、多时相数据的获取成为可能。为了在全球范围内有效地管理和分析空间数据,需要构建一个全球的、连续的、多尺度的动态数据模型。球面Voronoi图(简称V图),具有自然邻近、动态稳定等优良特性,已成为全球空间信息管理与分析的最有潜力的解决方案之一。针对现有的球面V图生成算法,在生成V图的精度和效率方面存在的诸多问题,本文从球面V图的生成算法、动态维护及其应用方面进行了研究,主要工作总结如下:(1)提出基于QTM的球面V图确定归属生成算法球面四元三角网(Quaternary Triangular Mesh,QTM)相对于传统的经纬度格网较为均匀。本文将QTM格网单元视作平面栅格算法中的像素(最小单元),计算每个格网单元到所有种子点格网的距离,并通过比较得到最近的种子点作为相应QTM格网单元的归属,从而生成基于QTM的球面V图。实验结果表明,该算法能够将生成的球面V图的误差控制在两个格网以内,初步解决了现有球面V图栅格生成算法的精度问题。(2)利用GPU对确定归属算法进行优化(硬件优化)确定归属算法需要计算并比较球面上每一个QTM格网单元到所有种子点的距离,算法计算量较大,具有计算密集型的特点;同时,对于每一个格网单元所进行的处理是基本一致的,且不同格网单元之间的处理相互独立,互不影响,算法具有指令一致性和相互独立性的特点,这非常适合于GPU单指令多数据流(Single Instruction Multiple Data,SIMD)的计算模型。本文采用GPU统一计算设备架构(Compute Unified Device Architecture,CUDA)对算法进行实现,并从GPU全局内存、共享内存、常量内存、寄存器等内存的使用及访问方式等方面对确定归属算法进行优化,以从整体上提高算法的效率。实验结果表明,利用GPU并行计算对算法进行优化后,效率可提高两个数量级以上。(3)利用双向扫描方法对确定归属算法进行改进(算法优化)QTM格网单元往往与其邻近格网具有相同的最近种子点,因此可利用QTM格网的邻近特性,通过邻近格网传递最近种子点。将球面按QTM的方式剖分后,依次按从左到右、从上到下和从右到左、从下到上的顺序对球面三角形单元进行扫描,并在扫描过程中通过计算和比较格网到其邻近格网最近种子点的距离,得到当前格网的最近种子点,进而得到球面V图。实验结果表明,该改进算法大大减少了确定归属算法中不必要的计算,在同一层次下,球面V图生成时间基本恒定(与种子点数无关)。(4)利用QTM格网的层次性对确定归属算法进行改进(尺度优化)相同种子点在不同层次QTM格网上生成的V图仅在Voronoi边界处有所不同。因此,可首先利用低层次的格网生成球面V图,并根据QTM格网及其三邻近格网的归属信息提取构成Voronoi区域边界的QTM格网;然后对边界格网进行再次剖分,利用确定归属算法确定边界格网子格网的归属,以此得到更高层次的球面V图,重复该步骤直至达到相应层次。实验结果表明,算法效率较确定归属算法有较大提高,且能够生成更高层次的球面V图。(5)实验系统设计开发与应用以.Net框架为基础,利用C#、C++语言及GPU并行编程架构——CUDA开发了基于QTM的球面Voronoi图算法与应用实验系统。在该系统中,利用全球各国的首都、主要河流、主要湖泊等数据对本文提出的各球面Voronoi图生成算法进行了实验,并从效率、精度等方面对各算法及应用进行了分析;同时,在系统中还给出了球面Voronoi图的动态维护操作方法和基于栅格Voronoi图的球面自然邻近插值方法,并对基于质心Voronoi图的全球地形自适应建模方法进行了初步的探索与实验。
[Abstract]:With the global ecological environment and the deepening of social and economic integration, people's research areas have gradually expanded from local areas to the whole earth. The rapid development of modern earth observation technology, such as photogrammetry, remote sensing and global positioning system, makes it possible to obtain large scale, multi-scale and multi phase data in the world. The effective management and analysis of spatial data in the surrounding area requires the construction of a global, continuous, multi-scale dynamic data model. The spherical Voronoi graph (V map), with natural proximity and dynamic stability, has become one of the most potential solutions for the global spatial information management and analysis. The existing spherical V maps are generated. The algorithm, in order to generate the precision and efficiency of V graph, this paper studies the generation algorithm, dynamic maintenance and application of the spherical V graph. The main work is summarized as follows: (1) a spherical V graph based on QTM is proposed to determine the ascription generation algorithm spherical four element triangle net (Quaternary Triangular Mesh, QTM) relative to the traditional one. The latitude and longitude grid is more uniform. This paper treats the QTM grid unit as the pixel (minimum element) in the plane grid algorithm, calculates the distance from each grid unit to the grid of all seed points, and obtains the nearest seed point as the corresponding QTM grid unit by comparison, thus generating the spherical V map based on the QTM. The experimental results show that this calculation is used. The method can control the error of the generated spherical V graph within two grid. The precision problem of the grid generation algorithm of the existing spherical V graph is solved preliminarily. (2) using GPU to optimize the ascription algorithm (hardware optimization) to determine the ascription algorithm and compare the distance of every QTM grid unit on the spherical surface to all the seed points. At the same time, the processing of each grid unit is basically the same, and the processing between the different grid units is independent and does not affect each other. The algorithm has the characteristics of instruction consistency and mutual independence, which is not often suitable for the GPU single instruction multiple data flow (Single Instruction Mu). The calculation model of ltiple Data, SIMD). This paper uses GPU unified computing device architecture (Compute Unified Device Architecture, CUDA) to implement the algorithm, and optimizes the ascription algorithm from the aspects of GPU global memory, shared memory, constant memory, register and other memory usage and access methods to improve the algorithm from the whole. Efficiency. The experimental results show that the efficiency can be increased by two orders of magnitude above the algorithm by using GPU parallel computing. (3) using bidirectional scanning method to improve the ascription algorithm (algorithm optimization), the QTM grid unit often has the same nearest seed point as its adjacent grid, so it can make use of the adjacent characteristics of the QTM grid. The nearest seed is passed by the adjacent grid. After dividing the sphere by QTM, the spherical triangular element is scanned in order from left to right, from upper to bottom and from right to left, from bottom to upper, and the nearest species of current grid is obtained by calculating and comparing the distance between the grid and the nearest seed point of its adjacent grid. The experimental results show that the improved algorithm greatly reduces the unnecessary calculation in the ascription algorithm. At the same level, the generation time of the spherical V graph is basically constant (independent of the number of seed points) at the same level. (4) using the hierarchy of the QTM grid to improve the classification algorithm (scale optimization) the same seed points are different. The V graph generated in the hierarchical QTM grid is only different at the boundary of the Voronoi. Therefore, we can first use the low-level grid to generate the spherical V map, and extract the QTM grid that constitutes the boundary of the Voronoi region according to the QTM grid and its three adjacent grid. Then the boundary grid is re divided and the ascription algorithm is used to determine the boundary. In order to get a higher level of spherical V map and repeat the step up to the corresponding level, the experimental results show that the algorithm efficiency is better than the ascription algorithm and can generate a higher level of spherical V graph. (5) the design and development of the experimental system are based on the.Net framework, using C#, C++ language and GPU, and Line programming architecture - CUDA has developed a QTM based spherical Voronoi map algorithm and an application experiment system. In this system, experiments are carried out using the data of the capital, main rivers and main lakes of all countries in this paper, and the algorithms and applications are analyzed in terms of efficiency, accuracy and so on. At the same time, the dynamic maintenance operation method of the spherical Voronoi graph and the spherical natural neighborhood interpolation method based on the grid Voronoi graph are also given in the system, and the global terrain adaptive modeling method based on the centroid Voronoi diagram is preliminarily explored and experimentation.
【学位授予单位】：中国矿业大学(北京)
【学位级别】：博士
【学位授予年份】：2016
【分类号】：P208

【参考文献】