随着基于图论的图像分割在视觉领域的广泛运用,图像处理中速度和实时性的研究成为人们关注的焦点。并行计算是解决速度问题的一类重要方法,在统一计算架构体系(CUDA)出现后,图像处理器(GPU)成为一种重要的高层次多核心。并行处理器。研究图像分割在GPU中的应用对解决速度问题有重要意义。本论文主要研究在GPU上基于图论的图像分割算法的并行加速问题,改进了基于压入与重标记算法的图像分割,给出了改进的压入与重标记算法针对GPU的设计和实现。首先,本文对压入与重标记算法进行了并行化,对图像映射图中的能量函数进行了改进。在算法并行化的过程中,针对更新顶点时存在的同步性问题,论文利用分阶段的思想和全局重标记方法,使得实现过程中顶点状态有效的更新。在构图过程中针对能量函数的数据模型与CUDA体系不匹配的问题,论文利用Kolmogorov的数据模型将能量函数改进为适合CUDA体系的数据模型,提升了图像映射过程的速度。通过对算法进行模拟实验得出压入与重标记算法的并行化和对能量函数的改进在时间上具有较好的检验结果。其次,本文在研究GPU的基础上,完成了CUDA体系下并行压入与重标记算法的存储器配置和任务划分,给出了改进的压入与重标记算法针对GPU的设计和实现。GPU的传输带宽和任务划分是影响处理速度的主要因素,论文通过设计全局内存、纹理内存和常数内存为基础的存储器配置,运用纹理内存和常数内存的缓存机制,从而增加了传输带宽和减少了任务通信。根据GPU的硬件特性,将CUDA实现中任务按照存储器的缓存规模完成有效划分和管理。最后实验表明论文对基于压入与重标记算法图像分割的改进以及针对GPU上的设计和实现在速度方面得到了改善。