Image Segmentation Based On Normalized Cut And CUDA Parallel Implementation

Image segmentation is an important process in image processing and analysis, whose output result directly affects the subsequent processing. With relatively complete theory of mathematics, graph based image segmentation algorithm is being extensively researched. Normalized Cut is one of balancing algorithms of graph based image segmentation, not only does it has all advantages of graph based image segmentation algorithm, but also solve the drawbacks that Min-cut favors cutting small sets of isolated nodes. However, there is a high computational complexity problem for Normalized Cut method, which makes it hard for practical application.In order to solve this problem, this paper focuses on the research that utilize CUDA parallel computing platform to accelerate the process of Normalized Cut image segmentation. The main research contents are listed below:(1) This paper first introduces the traditional algorithm of Normalized Cut image segmentation algorithm, which aims at mining the process that can be parallelized and at researching parallel algorithm to replace the serial time-consuming process.(2) When converting image to affinity matrix, this paper utilizes the fact that weights between every two pixels are independent, which can launch multiple threads at the same time, which every thread calculates only one weight. This method can speedup the affinity matrix computation.(3) This paper use parallel reduction to replace traditional serial array summation algorithm and design a fast parallel matrix multiplication algorithm. Since these two operation appear in Normalized Cut algorithm so frequently that promote the execution performance of these two algorithms can significantly improve the overall efficiency of the algorithm.(4) In solving matrix eigenvalue stage, the paper improved the traditional Bisection algorithm to make it can concurrently compute sub-interval-nodes of interval tree. Solving matrix eigenvalue is one of the most time-consuming processes in the algorithm, which makes the parallel solving matrix eigenvalue has important significance to improve the overall performance of the algorithm.(5) The experiment shows that the parallel Normlized Cut algorithm not only segment the image reliably but also have a2.34times speed-up in performance.