图像分割指的是利用图像的某些低维视觉特征,按照一定的相似性准则将图像划分为一系列彼此互不重叠的匀质区域,并将感兴趣目标分离出来的技术和过程。该技术是特征提取和目标识别等众多高层应用的基础,因此被广泛应用于通信、军事、遥感、气象、医学、智能交通、农业及工业自动化检测等诸多领域。然而,由于物质的复杂性、多样性和随机性等特点,加之人类缺乏对视觉系统的深层认知以及图像分割算法本身所具有的“病态”性质,迄今为止,尚未有十分成熟的分割方法能够满足各种不同应用环境的需求。因此,深入研究图像分割技术,设计准确高效且具有普遍适用性的分割算法,对促进图像处理和计算机视觉的发展具有十分重要的意义。传统的自动图像分割方法由于缺乏图像的先验信息,很难取得理想的分割结果,在实际应用中有着很大的局限性。近年来,交互式的图像分割方法由于融入了用户的经验知识和主观要求,可以更加准确而细致地提取出目标对象的轮廓,正在变得越来越主流。然而,该类算法的分割效果在很大程度上依赖于用户提供的先验信息,且人工交互过程费时费力,这在一定程度上限制了交互式分割算法的实时性和可用性。针对上述问题,本论文围绕基于图论的交互式图像分割算法展开研究,重点研究了显著性检测方法与基于图论的交互式随机游走算法相结合的自动图像分割算法,并提出了基于熵率超像素分割的显著性检测方法。此外,结合多尺度非线性结构张量、矩阵、维数约简、流形学习等技术优势和数学理论,提出了新的特征建模方法,并将其运用于自动图像分割和交互式多类目标分割算法,取得了令人满意的分割结果。本论文的创新性研究成果可归纳为如下几个部分：首先,本文提出了一种基于熵率超像素分割的视觉显著性提取方法。针对现有的显著性方法中存在的效率比较低以及效果比较差等问题,本文首先对输入的原始图像进行熵率超像素分割,以便保留图像相关的局部结构同时去除不必要的细节,然后以超像素为单元计算全局对比度,得到超像素区域的显著性值。基于熵率超像素的显著性检测方法不仅可以一致高亮整个目标区域,并可以清晰地指明物体的轮廓。其次,针对传统交互式随机游走算法费时费力且分割效果易受先验信息影响的问题,本文提出了融合显著性种子点和交互式随机游走算法的自动图像分割方法。具体地,算法首先通过基于熵率超像素分割的视觉显著性提取方法和近邻传播聚类算法自动得到前、背景种子点信息。然后将获取的显著性种子点作为启发信息,代替人工交互,使用交互式随机游走算法实现全自动分割。然而,由于提取到的种子点有错误标记现象,因此,本文利用Grabcut算法对取得的种子点进行修正,它通过迭代机制进行参数的更新和学习。此外,为了提高算法的分割效果,我们提出了一种将局部近邻的L*a*b+颜色信息、多尺度非线性结构张量纹理信息以及空间位置信息通过协方差矩阵有机结合的新的特征描述算子。最后,进一步提出了通过协方差矩阵将局部近邻的颜色、紧致的多尺度非线性结构张量纹理以及空间信息相结合的特征描述算子,并将其用于交互式多目标图像分割算法的研究。多尺度非线性结构张量具有全方向和多尺度的纹理描述能力,然而,将其拆分成一系列标量形式的独立分量与其它信息进行有机结合时,破坏了其本身所具有的矩阵结构的整体性。针对这个问题,本文通过对多尺度非线性结构张量的各个尺度使用Isomap非线性维数约简方式进行降维,去除了多尺度非线性结构张量纹理特征中冗余信息,得到紧致的纹理特征。