Research On Parallel Segmentation Method Of Remote Sensing Image Combining Minimum Spanning Tree And Union-Find Set

The information contents of ground objects in high-resolution remote sensing images present more abundant and complex,and its data is increasing explosively.How to quickly and accurately achieve accurate segmentation of large-scale high-resolution remote sensing images is an urgent problem to be solved in the current industry.Using traditional segmentation methods to segment large-scale high-resolution remote sensing images has high spatial and temporal complexity,which makes it difficult to segment images effectively and the segmentation time is too long.Moreover,using deep learning to segment large-scale high-resolution remote sensing images requires long-term learning and training on a large number of data sets,and requires relatively high hardware.It may also cause problems such as memory overflow and model incompatibility.In order to achieve efficient and accurate image segmentation,this thesis takes the large-scale high-resolution remote sensing image as the object for effective expression and efficient image segmentation,designs and implements a remote sensing image parallel segmentation method combining minimum spanning tree and union-find set.The major contents of this thesis are as follows:（1）The study proposes a fast MST solution method of graph and a minimum heterogeneous region segmentation method combined with union-find set.Based on the representation of the graph and solving the minimum spanning tree of the graph,the minimum heterogeneous region is segmented according to the minimum heterogeneity criterion to obtain the initial segmentation result.Then,the initial segmentation result is clustered by the FCM algorithm combined with the Hidden Markov Random Field,and get the final segmentation result.In order to speed up the MST solution of image graphs,propose a Kruskal algorithm combining path compression and rank merging.The realization process of the algorithm is represented by color simulation images,and the solution time before and after the algorithm improvement is analyzed by experiments.In order to speed up the segmentation of the minimally heterogeneous region,the minimally heterogeneous region segmentation method is proposed combined with union-find set.Finally,experiments are carried out to verify the correctness,feasibility and effectiveness of this method.（2）The study proposes a parallel segmentation method of image sub blocks based on MST and union-find set.Based on the consideration of multi-core CPU environment and parallelism,the construction of multi-core parallel image graph is proposed based on the image segmentation into sub-blocks.Dividing the image into multiple threads in the form of grid,and quickly construct the graph and edge sorting of image pixel 8 neighborhood in parallel.Based on the MST model of the image,the sub-block parallel minimal heterogeneous region segmentation method is proposed based on image sub-block segmentation and multi-core parallel solution.Through real-time thread communication,the method takes into account the minimum heterogeneous region merging between sub-blocks,and has almost the same segmentation results as the serial segmentation method and a good segmentation time speedup ratio.The,combining the sub-block parallel method to find a parallel FCM clustering segmentation algorithm.Finally,through experiments to analyze speedup ratio between the parallel method and the serial method in this thesis,and the segmentation effect and segmentation time are compared with the comparison method.Experiments show that the segmentation speed of the parallel method in this thesis is10.83 times higher than the serial method for a high-resolution remote sensing image with 67 million pixels,and the segmentation speed of 4.87 times higher than the comparison method,and the method in this thesis has a better segmentation effect than the comparison method.The above results verify the feasibility and effectiveness of the parallel segmentation method.