在图像识别技术的实现过程中,图像分割是一个重要的预处理环节,图像分割效果,直接影响着后续的分类、目标识别、图像分析、图像理解等过程的结果。针对着不同的图像特点,目前已经提出了错综复杂的图像分割算法。其中基于图论的图像分割算法是近几年研究的热点,这类算法着眼于全局,更注重局部数据的处理,比一般方法可以获得更佳的效果,并且图论理论有着比较完备的数学理论基础,将其用于图像处理有着较好的应用前景。本文详细介绍了图论算法的基本理论,将一幅图像映射成一个加权的无向图,将像素点映射为节点,相邻的像素之间的视觉性质(比如灰度信息或纹理)的相似度来定义相应的边的权值,图像的分割结果可以通过对图的最小割方法来获得。通过分析近些年基于图论的图像分割的现状可知,目前研究的重点主要是对最优割集准则的设计和优化改进,本文详细研究了Normalized Cut算法,这种算法很好的解决了直接使用最小割方法的缺陷,将这个NP-hard的准则转化为特征方程的求解,在数学上给出了完美的解答,但是这种方法存在着求解大规模矩阵的特征向量的复杂问题,而且随着图像尺寸的增大,计算规模也在增大,分割速度变得很慢,从而使该算法在实际应用中效率大大降低。为此,本文对原有算法进行了如下改进和创新以提高算法的效率:(1)通过小波变换进行高低分辨率图像的映射,大大缩短了Normalized Cut算法消耗时长,并且可以很好的保留原始算法的优点;(2)通过阈值法的初始粗分割,然后应用Normalized Cut算法。本文引入的信息熵算法的改进算法更加准确的确定分割阈值,更有效的分析图像特征,对信息熵的改进也是本文的创新之一,并且改进了区域之间权值矩阵的确定;(3)通过分水岭粗分割,然后映射到区间上利用归一化割进行分割,并且引入灰关联度的理论衡量像素间相似度来指导图像的分割过程;(4)引入区域生长法对图像实现粗分割,重新定义了种子点的选取法则,改进了区域生长的准则,并且考虑到了零星区域的合并,给出了零星区域合并的规则,最大限度的保留了原始图像的特征,然后利用重新定义的区域间的权值函数来构造权值矩阵,最后实现归一化分割。(5)针对最小割集准则存在着易于分割出图像孤立点的问题,参考NormalizedCut算法模型,引入加权割的概念,通过求最小加权割来实现同时达到类间最大相异性和类内最大一致性的图像分割目的。(6)在详细介绍了对最小生成树算法的基本思想、实现算法、分割准则的基础上,分析了该方法的优缺点,优化分割准则,确定目标函数来指导分割过程,定义节点和区域间的权值函数,充分考虑像素点之间的空间关系。