图像分割是图像处理和分析中的重要过程,它的输出结果直接影响着后续的处理效果.基于图论的图像分割算法由于有比较完备的数学理论基础,最近获得了广泛研究.Normalized Cut是一种平衡的基于图论的图像分割方法,不仅拥有其它图论图像分割算法的优点,并且解决了Min-Cut算法倾向于分割孤立结点的问题.然而,Normalized Cut存在计算复杂度高,分割速度慢等问题.针对该问题,本论文研究利用CUDA并行计算平台对Normalized Cut图像分割算法进行加速,提高算法在实际应用的执行速度.主要研究内容有：(1)介绍传统的Normalized Cut图像分割算法,目的是挖掘可以进行并行化的过程,研究并行化算法替代耗时的串行执行过程.(2)在将图像映射为相似度矩阵时,论文利用任意两像素点之间的权值与其它像素点无关的特点,启动多个平行线程,每一个线程负责计算两像素点间的权值,这种方法加速相似矩阵计算.(3)利用并行规约算法替代传统的数组求和,设计一种高速并行矩阵乘法替代串行的矩阵乘法,由于数组求和和矩阵乘法在Normalized Cut算法中出现频率高,提高这两种算法的执行性能会显著地提高整体算法的效率.(4)在求解矩阵特征值阶段,论文改进了传统的二分法(Bisection),使其平行地计算同层区间结点的子区间结点.求解矩阵特征值是整个算法较耗时的过程之一,并行化求解矩阵特征值会对提高整体算法的性能有重要意义.(5)实验结果证实了Normalized Cut并行算法不仅能正确分割图像,而且在性能方面获得了2.34倍的加速.