Improved Push-Relabel Algorithm For Graph Cuts And Design And Implementation On The GPU

With Image segmentation based on graph theory widely being used in the visual field, speed and real-time researches of image have become the focus of attention. Parallel computing is an important way to solve the speed problem. After launched the Compute Unified Device Architecture (CUDA) from NVidia, the graphics processing unit (GPU) is a highly parallel programmable processor. This thesis concerning Image segmentation on GPU has important significance.This thesis focusing on the research of image segmentation based on graph theory on GPU is of great significance to solve the problem of real-time image processing further. This thesis has improved Push-Relabel algorithm for graph cuts and has proposed designed implementation about improved Push-Relabel algorithm for graph cuts on GPU.Firstly this thesis presents a basic parallel implementation of the Push-Relabel algorithm and improves the energy function of the model to improve the processing speed. In the process of push operation, this thesis uses division technology to solve the synchronization problem in update nodes process. In the process of label operation, this thesis uses the global relabeling technology and the definition of different states for the vertex to update. For the problem of one-dimensional data model of patterned energy function not matched to the architecture of CUDA on GPU, this thesis uses the2-D grid data construction of Kolmogorov to improve energy function on CUDA to accelerate the speed of operation. The simulation experiments for parallelization Push-Relabel algorithm and improvement of the energy function have good test results in terms of speed.Secondly this thesis designs a memory configuration and task of the parallelization Push-Relabel algorithm to further improve the performance of the algorithm according to the characteristics GPU system and proposes designed implementation about improved Push-Relabel algorithm for graph cuts on GPU. Through the research of the parallelization Push-Relabel algorithm on the GPU, this thesis gives the corresponding design and implementation for solving the bandwidth and division of tasks, which affect the speed efficiency of algorithm. Through configuring memory based on global memory texture memory and constant memory, and especially focusing on using the cache mechanisms of texture memory and constant memory, this thesis completes to reduce the impact of bandwidth and to improve task communication. According to the features of GPU hardware, this thesis gives the task of the algorithm effectively management to match algorithms and hardware implementations. At last, the experiments test time of foreground-background segmentation and compare speedup of different groups, which show design and improvement can enhance the performance of the implementation.