图像分割是计算机视觉中一个基础而重要的问题。由于计算机对于图像内容的理解存在很大的局限性,近年来,加入用户指导的交互式图像分割被深入研究,并在与数字图像处理相关的诸多领域获得了广泛的应用。交互式图像分割的研究目的是通过尽可能简便而直观的人机交互,快速而准确地提取出图像中具有高层语义的前景物体。但是,随着数码技术的快速发展,数码成像设备所生成的图像分辨率不断增大,目前基于全局优化的交互式分割系统虽然能为用户提供友好的交互界面,却逐渐失去了实时输出精确反馈的能力。因此,如何使用户通过简明的交互方式,对于高分辨率图像进行分割时能获得实时而准确的反馈结果,是本文研究的重点。我们一方面从用户的交互方式出发,设计与之对应的高效分割算法；另一方面,我们利用已经普及的多核处理器对相关的优化算法加以并行。本文的主要研究内容及创新成果如下：1.通过对交互式图像分割中用户交互方式的研究,我们提出了一种渐进式分割算法,它由于与用户的交互方式相匹配而有效避免了冗余计算,同时通过局部的颜色建模对优化问题进行简化,从而提高了优化求解的速度；渐进式分割算法可与多尺度图窄带分割算法无缝地结合,降低了对窄带进行优化的计算复杂度。另外,我们提出了一种自适应窄带上采样算法,它利用多尺度间图像本身的先验信息进一步地减少窄带中参与优化的像素数目,提升了系统的性能。2.为了加速图分割优化问题的求解,我们提出了两种基于图划分策略的并行最大流算法。我们通过将图以动态或静态的方式划分为若干子图,有效地避免了线程间同步锁操作所带来的额外开销,使多核处理器能够以多线程在各个子图上独立地进行最大流运算,从而在多核平台上提高了最大流算法的性能。这两种并行算法不仅能够运用于交互式图像分割中,也可在双目视觉、三维表面拟合等多种计算机视觉与图形学的问题中被广泛运用。3.我们设计了一个新的交互式图像分割系统(Paint Selection),它不仅融合了前面所提出的渐进式分割算法,自适应窄带上采样算法以及基于多核处理器的图分割优化算法,也包含了三个新的界面元素,即分割工具的可交替性(使用户能用任何分割工具以任意顺序完成分割),笔画竞争机制(智能地处理交互中矛盾输入的问题)以及动态局部窗口(随着用户放大图像局部区域而提高分割精度),与现有的交互界面相比,对用户更加友好,提高了用户的工作效率。4.我们设计了一个新的精细抠图界面(Paint Matting),使用户对于高分辨率的图像能够轻松而快速地完成从二元分割到图像编辑操作(如背景替换、色调调整)的衔接工作。Paint Matting通过局部化的更新方式加快了运算速度,并利用多线程技术避免了交互中界面阻塞的问题,有效地提升了界面的用户友好性与可用性。