图像分割是将图像分割成各具特性的区域,并提取出感兴趣的目标,它是图像识别及跟踪的前提,该技术已广泛应用于军事、医学、智能交通、行人检测、产品检测、体育、遥感以及机器视觉等领域。基于图论的图像分割是以图论中的图为研究对象,利用图论的相关理论知识,对图像进行分割。由于图论中的图与图像具有很好的比对性,可充分利用图论中的相关理论知识对图像进行分割,同时还可减少由于图像离散化而造成的误差,从而获得较为准确的分割结果。本文围绕基于图论的图像分割特性及应用进行研究,利用图论中图的相关理论知识对图像进行准确高效的分割,对图像分析及处理起到一定的辅助作用。主要工作如下:1.通过最小化Ginzburg-Landau函数将图像分割问题描述为计算图像特征的最小化问题,利用图的特性将图像转换为加权无向图,并构建图模型。再通过求取相似度矩阵的特征值及相应的特征向量。接着利用图像灰度直方图统计相关信息,对原始图像进行层次聚类,获得聚类中心,并将该聚类中心作为模糊C均值算法的初始聚类中心;最后利用模糊C均值对构建的图模型进行聚类分割。该算法无需预先设置聚类数目,通过层次聚类自动搜索全局最佳聚类中心,有效提高了因引入图论后的分割速度。2.随着图像尺寸越来越大,直接基于像素处理的图像分割方法很难兼顾计算效率。针对此问题,在区域邻接图基础上引入了最近邻接图来优化全局搜索,用简单线性迭代聚类算法将图像分割成超像素小区域,利用区域邻接图和最近邻接图的邻接表数据结构来描述区域之间的关系,然后计算每个待合并区域与其所有邻接区域之间的不相似度函数值,最后将不相似度函数值最小的区域进行合并。该方法可以提取图像局部特征,获取图像的冗余信息,解决了搜索全局最优解难的问题,能较好的将最相似的区域进行合并,降低了合并计算的复杂度,大幅度提高了区域合并的准确性。3.谱聚类算法是将原始图像映射为加权无向图,以样本的相似程度为基础,能在任意形状样本空间上聚类且收敛于全局最优解。但是该算法在聚类过程中要计算样本的相似度矩阵,并且要对相似度矩阵对应的拉普拉斯矩阵进行特征分解,运算效率较低。针对此问题,利用均匀采样方法对图像进行初步采样,通过最小化Nystr?m扩展方法的误差,反复迭代计算使其采样点与像素点之间的误差最小,从而得到最终采样点,然后计算特征值及相应的特征向量,构造相似度矩阵,并对图像进行Nystr?m谱聚类分割。该算法运算量小,全局寻优能力强。4.较高的计算复杂度严重限制了谱聚类算法在图像分割中的应用,然而,谱聚类图像分割的方法中样本信息的选择是决定分割精度和速度的关键因素。针对此问题,提出了一种基于灰度图像的谱聚类图像分割方法。该方法结合图像特征信息,根据尺度变化,利用像素在不同尺度上的相似度关系,计算相似度矩阵与稀疏矩阵在边缘和区域上的最小误差,提取特征信息创建稀疏化的相似度矩阵,然后利用谱聚类的方法对图像进行分割运算。该算法不仅有效降低了谱聚类图像分割算法的计算量、节省了内存空间、提高了图像分割的精度,而且对噪声有更强的鲁棒性。