Research On Parallel Polygonization Algorithm Of Raster

Raster has been the most commonly used data source for GIS. However, it is usually converted to vector for its large amount, low positioning accuracy, and difficulty to express spatial topological relations. So polygonization of raster forms an important part of spatial data conversion. As aerospace remote sensing is developing towards multi-sensor, multi-platform, multi-angle and high spatial resolution, high spectral resolution, high phase resolution, high radiometric resolution direction, remote sensing image is showing an explosive growth. The traditional polygonization algorithm cannot meet the need for vector information extracting, so it’s of great theoretical significance and practical value to explore parallel polygonization algorithm under new hardware architecture. However, scholars has been staying in the stage of improving efficiency by mending existed automatically polygon building algorithms. A small number of researchers focus on the study of parallel polygonization, data is divided into equal rows in their research, and the result is written into the topological data structure file, which usually cannot meet the need of entity structure in applications.In this dissertation, the study begins at the traditional polygonization method based on topology building, explores the parallel polygonization algorithm under data parallel mode, and focus on the raster data partitioning, topology building in block, and stitching between blocks. In addition, this dissertation explores the key technologies including task scheduling strategy and task mapping process. Base on the above, this dissertation implements the algorithm in parallel environment, analyzes the performance and scalability of parallel algorithm. The main contents are listed as follows:(1) Raster data partitioning methods analysis. By summarizing the common raster data partitioning methods and analyzing the two influencing factors, this dissertation put forwards a raster partitioning method based on run-statistical data. This method takes the raster complexity into consideration in some degree, which makes the similar complexity among blocks and the similar executing time for block topology building.(2) Parallel topology building research. Based on the proposed polygonization algorithm, especially the process of topology building between feature point, edge and polygon, this dissertation explores the block topology building and block stitching by extracting the points on boundaries and recording the connection information.(3) Parallel polygonization algorithm design. By combining the PCAM model in parallel algorithm design theory, this dissertation designs the parallel algorithm follow the process of process-task decomposition, task scheduling and task mapping, and explores the dynamic data distributing and block stitching strategy under master-slave model.(4) Parallel polygonization algorithm implementing and testing. This dissertation implements the parallel algorithm in parallel computing environment. Tests are made for different size of data. At last, the execution time, speed up and scalability are evaluated.In summary, this dissertation put forwards a raster partitioning method based on run-statistical data, resolves the key issue of parallel polygonization-parallel topology building, designs the parallel algorithm under master-slave mode and implements it in parallel computing environment. The result illustrates that the adopted data partitioning method achieves a more stable speed up, parallel topology building is the key point to improve the algorithm efficiency, and master-slave mode can effectively achieve the dynamic allocation of data blocks and block stitching.