图像处理广泛应用在医学图像、遥感云图、指纹识别、人脸检测、地质勘探等领域。图像分割是图像处理过程中的一个关键步骤,为图像检索、图像分析提供有效的信息,使更高层次的图像处理成为可能。常见的图像分割方法归纳为基于边界检测和边缘连接的方法、基于区域的分割方法和结合特定理论工具的分割方法三大类。近几年,将图论方法与其他方法结合,使图像分割转变为最优化问题,成为国内外图像分割领域研究的热点。本文详细阐述了基于图论的图像分割方法,在分析最小生成树方法的概念、原理的基础上,针对Kruskal算法无法根据新生成区域修改加权区域邻接图的不足,提出一种改进的Kruskal算法:区域合并后,重新计算新区域与相邻区域的权重,修改WRAG和边的排列顺序。改进算法使WRAG更接近原图像的特征。为了降低Kruskal算法中节点和边的数目,在介绍了分水岭算法的思想、基本模型和主要缺陷后,将基于数学形态学的分水岭方法引入最小生成树方法中,提出K - VW方法。首先,利用分水岭方法对梯度图像预分割,生成的过度分割区域转化为无向图中的节点,相邻区域间的差异转化为边的权重,构造加权区域邻接图(WRAG),再利用改进的Kruskal算法,结合Deepthi Narayan提出的合并准则,通过区域内部差异函数、阈值函数,比较区域内部差异和外部差异,利用图像自身信息,将符合合并准则的区域进行合并操作。基于分水岭的最小生成树方法既能消除分水岭的过度分割现象,又能降低边的数目,获得图像的全局特征,保持较好的区域一致性。最后,本文通过对多幅彩色图像的对比实验,验证K - VW方法的分割效果。实验表明:对于前景、背景对比明显,区域内部特征变化缓慢,区域边缘部分特征变化剧烈的彩色图像,本文的方法分割效果较好,具有较强的适用性和较高的实用价值。对于包含较多噪声和细节的彩色图像,分割结果会存在冗余区域和错误边界的现象,需要进一步改进。