栅格数据矢量化并行算法研究

发布时间：2018-04-24 19:14

本文选题：栅格数据矢量化 + 数据划分　；参考：《南京大学》2013年硕士论文

【摘要】：遥感栅格数据是地理信息系统中最常用的数据源之一,由于其数据量大、定位精度低、难以表达空间拓扑关系等缺点,在现实应用中往往需要将其转换为矢量数据,因此栅格数据矢量化操作成为空间数据转换的重要内容之一。随着航空航天遥感朝着多传感器、多平台、多角度和高空间分辨率、高光谱分辨率、高时相分辨率、高辐射分辨率的方向发展,栅格数据量呈现爆炸式增长,传统的栅格矢量化算法已经不能满足矢量信息提取的需要,因此探索新型硬件架构下的栅格数据矢量化并行算法具有重大理论意义和实用价值。然而长期以来对栅格数据矢量化的研究还多数停留在通过改进现有算法以提高效率的阶段,仅有的涉及栅格数据矢量化并行算法的研究,多采用均等的数据按行划分方法,转换结果为拓扑数据结构,不能满足实际应用中对简单矢量实体结构的需求。本文以传统的基于拓扑关系的栅格数据矢量化算法为基础,研究数据并行模式下的栅格数据矢量化并行方法,重点探索栅格数据划分、数据块内部拓扑构建以及数据块拼接方法,探讨栅格数据矢量化的任务调度策略和任务映射方法等并行关键技术,设计并实现基于拓扑关系的栅格数据矢量化并行算法,并对该算法的时间性能和可扩展性进行评估。论文的主要研究内容包括：(1)栅格数据划分方法分析。总结常见的栅格数据划分方法、分析影响栅格数据划分的两个重要因素——栅格数据存储结构和栅格处理算法类型,针对栅格数据矢量化对数据划分的要求,提出基于游程统计的栅格数据划分方法,使得每个进程所处理的栅格区域内的数据复杂度相接近,进而平衡各数据块的内部拓扑构建时间,减少进程间等待。(2)并行拓扑构建方法研究。在分析基于拓扑关系的栅格数据矢量化串行算法中各要素之间拓扑关系构建过程的基础上,通过提取数据块边界处的特征点,分别记录其在上下数据块中的连接信息,研究数据行划分下的数据块内部拓扑构建和数据块拼接等关键问题。(3)栅格数据矢量化并行算法设计。结合并行算法设计中的PCAM模型,按照任务分解、任务调度以及任务映射的研究思路,完成栅格数据矢量化的并行算法详细设计,重点探索主从模式下的数据块动态分配策略和数据拼接策略。(4)栅格数据矢量化并行算法实现与测试。在并行软硬件环境支持下编程实现栅格数据矢量化并行算法,并选择不同规模的数据对算法进行测试,评估该并行算法的运行时间、加速比等时间性能和可扩展性。综上所述,本文提出了考虑栅格数据复杂度的基于游程统计的栅格数据划分方法；突破了并行拓扑构建这一栅格数据并行矢量化的关键问题；设计了主从模式的栅格数据矢量化并行算法,并在并行环境下编程实现。研究结果表明：基于游程统计的栅格数据划分方法能够获得更加稳定的并行加速比,并行拓扑构建是提高栅格数据矢量化效率的关键,主从模式可以有效实现数据块的动态分配和数据块拼接。
[Abstract]:Remote sensing raster data is one of the most commonly used data sources in geographic information system. Because of its large amount of data, low positioning precision and difficult to express spatial topology, it is often needed to convert it into vector data in practical applications, so the raster data vectorization operation becomes one of the important contents of spatial data conversion. Space remote sensing has developed towards multi-sensor, multi platform, multi angle and high spatial resolution, high spectral resolution, high phase resolution and high radiative resolution, and the grid data amount presents an explosive growth. The traditional grid vectorization algorithm can not meet the need of vector information extraction. Therefore, the grid grid under the new hardware architecture is explored. The parallel algorithm of data vectorization has great theoretical significance and practical value. However, for a long time, the research of grid data vectorization is still mostly in the stage of improving the efficiency by improving the existing algorithms. Only the parallel algorithm of grid data vectorization is studied. For the topology data structure, the requirement of the simple vector entity structure can not be met. Based on the traditional raster data vectorization algorithm based on the topology relation, the grid data vectorization and parallel method under the data parallel mode is studied, and the grid number is divided, the topology of the data block is built and the data block is built. The parallel key technologies such as task scheduling strategy and task mapping method of grid data vectorization are discussed. The parallel algorithm of grid data Vectorization Based on topology is designed and implemented. The time performance and extensibility of the algorithm are evaluated. The main contents of this paper are as follows: (1) grid data partition method The common grid data partition method is summarized, and the grid data storage structure and grid processing algorithm type are analyzed, which affect grid data partition. In view of the requirement of grid data vectorization to data division, the raster data classification method based on travel statistics is proposed, which makes the grid area processed by each process. The internal data complexity is close, then the internal topology construction time of each data block is balanced, and the inter process waiting is reduced. (2) the study of the parallel topology construction method. On the basis of the analysis of the topology relationship between the elements in the grid data vectorization serial algorithm based on the topology relation, the feature points at the boundary of the data block are extracted. To record the connection information in the up and down data blocks respectively, study the key problems of the topology construction and data block splicing of the data block under the data division. (3) the grid data vectorization parallel algorithm design, combined with the PCAM model in the parallel algorithm design, according to the task decomposition, task scheduling and task mapping research ideas, complete the grid. The parallel algorithm of lattice data vectorization is designed in detail, focusing on the dynamic allocation strategy and data splicing strategy of the data block in the master-slave mode. (4) the implementation and testing of the grid data vectorization parallel algorithm. The running time of the parallel algorithm and the time performance and extensibility of the acceleration ratio are evaluated. In summary, this paper presents a method of grid data partition based on run statistics, which considers the complexity of grid data, and breaks through the key problem of constructing the parallel vector quantization of the grid data in parallel topology, and designs the grid of the master-slave mode. The parallel algorithm of lattice data vectorization is implemented in parallel environment. The results show that the raster data partition method based on travel statistics can obtain a more stable parallel acceleration ratio. Parallel topology construction is the key to improve the efficiency of grid data vectorization. The master slave mode can effectively realize the dynamic distribution and number of data blocks. According to the block splicing.

【学位授予单位】：南京大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：P208

【参考文献】