图像分割是数字图像处理和计算机视觉中重要任务之一。本文研究的基于图论谱聚类分割方法是近几年来的图像分割领域的一个新的研究热点,基于图论的谱聚类基本思想是将一幅图像映射成一个无向加权图,将像素点映射为顶点,相邻的像素之间的视觉信息(比如灰度或距离)的相似度来定义权值。将图像按照某种划分建立特定函数,当函数达到最小值就得到图像的一个最佳分组。该方法具有高度的灵活性,它提供统一框架处理图像的灰度、纹理、噪声,适用于任何数字图像。本论文研究的最小最大割集(Min-max cut)充分体现了基于图论的谱聚类方法的最优准则,即子图内相似度最大,子图间相似性最小。将这个NP的准则转化为特征方程求解,但是这个方法存在求解大规模矩阵的特征向量的复杂问题,算法随着图像尺寸增大效率大大降低。图像映射为图构建过程中,边的构建方法不再简单的依据四邻域或八邻域,而以某顶点为中心将半径r内所有顶点与其进行关联。相似度计算函数的构造选用考虑了顶点之间的灰度和距离的高斯函数。相似度矩阵更真实反映像素之间的关系。为了降低最小最大割算法中顶点和边的数目,在介绍了分水岭算法的思想和主要缺陷后,将基于数学形态学的分水岭方法引入到最小最大割算法中,提出基于分水岭的最小最大割算法。首先,利用分水岭方法图像预分割,生成的过分割小区域转化为无向图中的顶点,相邻区域间的差异转化为边的权重,再利用最小最大割算法将小区进行合并操作。基于分水岭的最小最大割算法既能消除分水岭的过度分割现象,又能降低图中边的数目,获得图像的全局特征,提高最小最大算法分割效率。文中利用基于GPU的CUDA平台加速最小最大割算法,减少算法的运行时间。根据GPU适合处理计算密度高、计算逻辑相对简单的大规模数据的计算特性,理论上分析了最小最大割算法加速的可行性。根据最小最大割算法实现步骤,设计了基于GPU的最小最大割算法。实现了三对角矩阵k个特征值求解加速和其对应k个特征向量的K-means聚类加速。实验分析得出基于GPU的最小最大割算法加速比在1.5左右,得出的结论是大规模矩阵分块计算提高最小最大割算法加速比的主要途径。