随着计算机科学技术的快速发展,多媒体技术和数字图像处理技术的日趋成熟,人们与信息的交互愈发频繁。相比文字与语音,图像可以展示更加丰富的信息,因而成为了人们的一种重要信息来源。图像分析是对图像感兴趣的目标进行观测的方法,常被用来对图像建立整体描述。图像分割是图像分析的重要组成部分,对于理解和分析图像信息有着极大的作用。只有先通过图像分割将感兴趣的目标分离,才能在此基础上对目标进一步处理,进行特征提取和测量操作。然而随着图像分辨率的增大,图的复杂度也随之增大,计算速度愈发缓慢,已成为一个亟待解决的问题。本文分析了基于图论的图像分割算法的理论及其研究现状,研究了并行化的基础知识和具体实现,分别给出了对算法两个步骤的优化。首先针对无向图复杂度大的问题,本文提出了新的能量函数系数,用以评估该像素点属于前景的概率和该像素点属于背景的概率的差异。以此为基础,对t-links(无向图中顶点与源点和汇点相连的边)的数量进行缩减,舍弃每对t-links中权值较小的一条边,将保留的边通过新的能量函数系数进行加权计算,在保证不影响图像分割结果的同时,降低无向图的复杂度。然后针对算法运行速度慢的问题,本文改进压入与重标记的具体过程,将压入操作划分为Push和Pull两步独立完成,并引入新的重标记操作,减少算法迭代次数,提高算法运行速率。最后,将上述两步改进结合在一起,综合提升算法整体运行效率。本文采用了三幅基准图像作为测试数据,运用并行化的理论,充分利用CUDA体系结构的特性,对算法进行并行实现,并设计对比实验来验证本文算法改进点的有效性。最终的实验结果表明,本文提出的图像分割算法改进点能成倍的提升算法运行效率。