Research On Adaptive Parallel Vectorization Algorithm

Fast data conversion from large remote sensing image to vector is one of the key techniques to integrate Remote Sensing and Geographical Information System. The result of spatial analysis from Remote Sensing images is always needed to be vectorized, so is the thematic geo-information. Therefore, raster vectorization technology has drawn more attention on informatization in the field of agriculture, land and resources and other industries. With the rapid development of earth observation program, the amount of daily acquired geo-data grows exponentially. Traditional methods cannot meet the demand of high efficiency. Thus, research on fast raster-to-vector data conversion in large scale has typical and practical significance. Recently, parallel computing is undergoing rapid progress, and its outstanding computing power motivates large-scale raster data vectorization issue. However, the studys on vectorization parallel algorithms, so far, has some defects:simplex of data partition methodologies, topology remedy originated by inappropriate partition. These shortages limit the vectorization efficiency.Given the shortages mentioned above, this thesis has made thorough research on polygon vectorization serial algorithms and analyzes the potential of parallelism for these algorithms. This dissertation improves the traditional vertorization method, designs a serial vectorzation algorithm suitable for parallelizing. In addition, this dissertation proposes adaptive data-partition method, designs and implements three polygon vectorization parallel algorithms accordingly. Finally, the algorithms are tested by adopting different scale of data and then analyze experimental resultsThe contents of the thesis are as follows:(1) Conduct further study about the procedures of classic vectorization algorithms; analyze the parallelism of each algorithm. Improve the algorithm by combining parallel advantages of two classic algorithms and propose an improved serial polygon algorithm suitable for parallelizing.(2) Summarize the traditional raster image data-partition methods and the corresponding applicable scope and analyze the disadvantage when tradition partition methods are applied to parallel-vectorization. To avoid the defects, this paper studies the relationship between raster complexity and computation-scale of vectorization and then proposes both adaptive static and dynamic data-partition method for vectorization on the premise that the polygon topology is complete.(3) Develop three parallel algorithms for vectorization based on the data-partition method above. Carry out experiments in clustered environment to test accuracy and efficiency of parallel algorithms, and then analyze the result.Experimental result shows that the improved serial algorithm is more suitable for parallel processing. The proposed data-partition methods can guarantee the completeness of polygon topology and assign approximately equal quantity of vectorization task to each process. The parallel algorithms for polygon vectorization proposed in this thesis have achieved much higher speed-up ratio than traditional algorithm.