彩色图像分割是几乎所有中、高层彩色图像处理工作的基础。无论是中层的图像分析，还是高层的图像理解，都需要先对图像进行分割，再进行后面的特征提取、模式识别等工作。而且图像分割的质量将直接影响其后的中、高层处理工作的成败。因此，高质量的彩色图像分割方法一直是图像领域的研究重点。但是直到目前为止，彩色图像分割仍然是一个没有得到很好解决的问题。基于图论的彩色图像分割方法是目前效果最优的彩色图像分割方法之一。一般而言，图论方法是将原来的彩色图像分割问题转化为一个无向图的最优化问题，运用图论的算法实现对无向图的最优化，也就完成了对原彩色图像的分割。目前基于图论的彩色图像分割方法主要有两种：最小生成树(Minimal Spanning Tree)与最小割(Minimized Cut)。本文对两种基于图论的彩色图像分割方法—最小生成树和最小割都进行了较深入的研究。其中，第一种方法—最小生成树，本文提出了一种利用最小生成树的局部阈值实现彩色图像分割的方法，它不同于传统的最小生成树的全局阈值方法。该方法通过考查最小生成树构造过程中的区域一致性变化，计算出一个局部阈值，利用该局部阈值可分割出原彩色图像中的两个最终区域。对于图像中的剩余区域，重复上述过程继续进行分割，直至原图像中所有的区域都被分割出来。实验证明，本文的局部阈值方法比传统的全局阈值具有更好的分割效果。第二种方法—最小割，利用最小割的修正形式—归一割(Normalized Cut)，可以克服最小割易于分割出图像中的孤立点的缺点。但归一割的最小化问题是一个NP完备(Non-deterministic Polynomial Complete)问题，人们一般只能得到它的近似解。最近有人针对灰度图像的分割提出一种模糊迭代的归一割方法，巧妙地回避了求解归一割最小化的问题。本文主要研究利用这种方法解决彩色图像分割的问题，包括：在彩色空间下选取一种合适的相似性度量，以及用单链表的运算代替矩阵运算来计算归一割。实验证明，本文设计的方法能较好地应用于彩色图像分割。