图像分割是计算机视觉中一个基本而核心的问题。是目标识别、目标跟踪、智能交通和医学图像处理等领域的基础。虽然近年来有关图像分割的研究成果越来越多,但由于图像分割本身所具有的难度,仍然存在众多问题,因此,图像分割仍然是计算机视觉中重要的理论问题,同时有很强的应用背景。基于图论优化的图像分割技术由于其良好的分割特性,近十年成为国际上图像分割领域的一个新的研究热点。主要特点有:图像特性与图论特性之间存在良好的对应关系,可以将图像的全局分割与局部信息处理相结合,减少由于图像离散化造成的误差,从而获得良好的分割结果。该方法的本质是将图像分割问题转化为最优化问题,通过能量代价函数最小化实现图像分割。传统的基于图的分割算法主要是利用图像的某些已有的特征进行研究,将基于图像特征的分割算法与基于图的分割算法结合起来。本文从图的结构性质入手,对图的划分相关参数进行探索,结合约束条件,利用组合优化和伪流等优化方法设计新的分割算法。在基于伪流和改进的OneCut图像分割、基于超像素和Normalized Cuts的有监督图像分割、基于伪流和超像素的图像分割、基于人脸检测和Biased Normalized Cuts的自动人物图像分割方法和基于人脸检测和细胞自动机的全自动人物图像分割几方面提出了几个有效的分割算法。论文的主要工作如下:（1）提出了一种基于混合能量约束和伪流的图像分割模型。Tang,Gorelick,Veksler和Boykov提出了一种新的图像分割模型,使用表观模型和基于归一化直方图的图割。该模型对于交互式图像分割非常有效。但是,当目标和背景颜色的相似时,直方图的一些直条的值可能彼此非常接近,该模型容易分割出现孤立点。为了提高该算法和相关算法的性能,提出在能量函数中引入新的空间距离和轮廓方向能量约束,改变能量图构造方式,最后,使用Hochbaum的伪流算法来计算新能量图的最大流。通过在公开数据集上进行的对比实验,本文提出的方法的分割结果优于OneCut,Random Walker,Normalized Random Walker,Normalized Lazy Random Walker,Pseudo-Bound Optimization,Trust Region Convexity 和 Semi-Supervised Normalized Cuts 方法。（2）提出了一种新的基于超像素、必连约束和勿连约束的交互式归一化割的图像分割方法。针对SSNCuts在图像分割中存在的如下缺陷:图片中目标较小、存在多个相似的目标和目标中间含有背景区域的时候,分割效果不好;分割时需要提供更多的交互信息;标记的选取对分割结果影响非常大;很多时候,在标记种子点的时候,无法预测分割的结果,标记非常费时费力;分割速度慢。本文提出了一种新的方法:首先由用户粗略标记对象和背景的位置和主要特征来引入交互信息。接下来,使用mean shift将图像过分割为超像素,并且用每个超像素作为顶点来创建图。选择使用Bhattacharyya系数来衡量两个区域之间的相似度。然后加入必连约束和勿连约束。最后应用Ncuts方法来划分这些区域。该方法不仅成功的克服了 SSNCuts中的缺陷,而且大大的提高了分割的准确性和分割效率。最后,提出融合超像素和伪流算法的图像分割方法,在目标和背景颜色相似、或在目标和背景对比不是很明显或纹理比较复杂时都获得了很好的分割,有效的提高了分割的准确性和分割效率。（3）提出了一种基于人脸检测和细胞自动机的全自动人物图像分割方法。人物图像具有人体姿态的多样性、衣服颜色和纹理的各异性、存在噪声、低对比度、光照不均匀以及背景的复杂性,以至于人物分割面临着巨大的挑战。论文首先用人脸检测算法识别人脸,得到面部轮廓;再根据识别出的人脸位置建立目标和背景种子点生成模型,并得到目标和背景的种子点;最后用细胞自动机进行像素标记任务,得到目标和背景两部分结果。算法不仅实现了全自动的分割人物图像,而且获得了比较理想的分割结果。（4）提出了一种基于人脸检测和Biased Normalized Cuts的自动人物图像分割方法。在分割算法中,设计了种子点自动估计模型,根据人脸特征检测出人物图像中的人脸,再根据识别出的人脸自动产生约束种子点。最后将产生的种子点作为Biased Normalized Cuts的约束条件进行图像分割,然后基于之前的种子点集合和分割结果进行区域合并,图像划分为两部分（目标和背景）。实验结果表明,提出的分割方法能自动和较准确地对人物图像进行分割,并有效的提高了分割效率。该方法对传统基于Ncut的图像分割方法进行了改进,将问题从无约束的优化问题转换成带约束的优化问题。