图像分割是图像处理到图像分析的关键步骤,近年来受到越来越多的关注。谱聚类方法因其不受样本空间形状的限制,能够在任意样本空间上聚类,成为近年来比较流行的图像分割方法。然而谱聚类算法面临两个亟需解决的难题,一是,构造相似度矩阵的计算复杂度高达O(n2);二是,直接对拉普拉斯矩阵进行特征分解的计算复杂度高达O(n3)。谱聚类算法带来的高额计算成本制约了传统谱聚类方法在实际中的应用。本文研究基于谱聚类的图像分割算法主要从提升谱聚类算法运行效率方面进行研究,具体内容如下:一、针对谱聚类算法在图像分割中运行效率低下的问题,提出了一种基于四叉树分解的多尺度快速谱聚类算法(MFSC算法)。首先采用四叉树分解算法对图像进行预分割,得到“超像素”,以这些“超像素”作为分割的基本单位,构建基于超像素的相似度矩阵,随后利用四叉树分解得到的树形数据结构,将谱聚类中求解大规模矩阵的特征分解问题转化为多个较小的不同尺度上的特征分解问题。其中MFSC算法的复杂度为O(nlogn),n为图像像素个数,达到了线性级别。实验结果表明MFSC算法有效地提高了谱聚类算法的运行效率,并取得了较好的分割结果。二、虽然基于四叉树分解的多尺度谱聚类算法在图像分割领域取得了较好的效果。但四叉树分解算法仍有众多局限,同时构造相似度矩阵所需的尺度参数也极大地影响着谱聚类算法的分割结果。为此,本文提出了一种基于k-d树算法的多尺度快速谱聚类算法。用改进的k-d树算法来代替四叉树分解算法得到“超像素”,k-d树算法相较于四叉树分解更加灵活,应用面更广。此外,该算法在相似度矩阵构造时采用了局部尺度自适应设值尺度参数,解决尺度参数需要人工设置的问题。通过在人工数据集、UCI数据集和图像数据集上的验证,新的算法在拥有较好的聚类效果的同时,取得较高的执行效率。三、为了方便谱聚类算法的研究者对自己提出的算法进行研究分析,本文基于Qt平台,结合C++和Matlab设计出一套谱聚类算法分析评价系统。该系统中集成了本文提出的算法和多种目前主流的谱聚类算法,可根据用户需求,直观地分析对比不同谱聚类算法在分割结果和运行效率上的差异,给谱聚类算法的研究提供了便利。