论文部分内容阅读
遥感栅格数据是地理信息系统中最常用的数据源之一,由于其数据量大、定位精度低、难以表达空间拓扑关系等缺点,在现实应用中往往需要将其转换为矢量数据,因此栅格数据矢量化操作成为空间数据转换的重要内容之一。随着航空航天遥感朝着多传感器、多平台、多角度和高空间分辨率、高光谱分辨率、高时相分辨率、高辐射分辨率的方向发展,栅格数据量呈现爆炸式增长,传统的栅格矢量化算法已经不能满足矢量信息提取的需要,因此探索新型硬件架构下的栅格数据矢量化并行算法具有重大理论意义和实用价值。然而长期以来对栅格数据矢量化的研究还多数停留在通过改进现有算法以提高效率的阶段,仅有的涉及栅格数据矢量化并行算法的研究,多采用均等的数据按行划分方法,转换结果为拓扑数据结构,不能满足实际应用中对简单矢量实体结构的需求。本文以传统的基于拓扑关系的栅格数据矢量化算法为基础,研究数据并行模式下的栅格数据矢量化并行方法,重点探索栅格数据划分、数据块内部拓扑构建以及数据块拼接方法,探讨栅格数据矢量化的任务调度策略和任务映射方法等并行关键技术,设计并实现基于拓扑关系的栅格数据矢量化并行算法,并对该算法的时间性能和可扩展性进行评估。论文的主要研究内容包括:(1)栅格数据划分方法分析。总结常见的栅格数据划分方法、分析影响栅格数据划分的两个重要因素——栅格数据存储结构和栅格处理算法类型,针对栅格数据矢量化对数据划分的要求,提出基于游程统计的栅格数据划分方法,使得每个进程所处理的栅格区域内的数据复杂度相接近,进而平衡各数据块的内部拓扑构建时间,减少进程间等待。(2)并行拓扑构建方法研究。在分析基于拓扑关系的栅格数据矢量化串行算法中各要素之间拓扑关系构建过程的基础上,通过提取数据块边界处的特征点,分别记录其在上下数据块中的连接信息,研究数据行划分下的数据块内部拓扑构建和数据块拼接等关键问题。(3)栅格数据矢量化并行算法设计。结合并行算法设计中的PCAM模型,按照任务分解、任务调度以及任务映射的研究思路,完成栅格数据矢量化的并行算法详细设计,重点探索主从模式下的数据块动态分配策略和数据拼接策略。(4)栅格数据矢量化并行算法实现与测试。在并行软硬件环境支持下编程实现栅格数据矢量化并行算法,并选择不同规模的数据对算法进行测试,评估该并行算法的运行时间、加速比等时间性能和可扩展性。综上所述,本文提出了考虑栅格数据复杂度的基于游程统计的栅格数据划分方法;突破了并行拓扑构建这一栅格数据并行矢量化的关键问题;设计了主从模式的栅格数据矢量化并行算法,并在并行环境下编程实现。研究结果表明:基于游程统计的栅格数据划分方法能够获得更加稳定的并行加速比,并行拓扑构建是提高栅格数据矢量化效率的关键,主从模式可以有效实现数据块的动态分配和数据块拼接。