基于GrabCut的图像分割算法实现外文翻译资料

Abstract

The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (color) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimization. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for “border matting” has been developed to estimate simultaneously the alpha-matte around an object boundary and the coolers of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.

1 Introduction

This paper addresses the problem of efficient, interactive extraction of a foreground object in a complex environment whose background cannot be trivially subtracted. The resulting foreground object is an alpha-matte which reflects the proportion of foreground and background. The aim is to achieve high performance at the cost of only modest interactive effort on the part of the user. High performance in this task includes: accurate segmentation of object from background; subjectively convincing alpha values, in response to blur, mixed pixels and transparency. In general, degrees of interactive effort range from editing individual pixels, at the labor-intensive extreme, to merely touching foreground and/or background in a few locations.

1.1Previous approaches to interactive matting

In the following we describe briefly and compare several state of the art interactive tools for segmentation: Magic Wand, Intelligent Scissors, Graph Cut and Level Sets and for matting: Bayes Matting and Knockout. Fig. 2 shows their results on a matting task, together with degree of user interaction required to achieve those results.

Magic Wand starts with a user-specified point or region to compute a region of connected pixels such that all the selected pixels fall within some adjustable tolerance of the colour statistics of the specified region. While the user interface is straightforward, finding the correct tolerance level is often cumbersome and sometimes impossible. Fig. 2a shows the result using Magic Wand from Adobe Photoshop 7 [Adobe Systems Incorp. 2002]. Because the distribution in colour space of foreground and background pixels have a considerable overlap, a satisfactory segmentation is not achieved.

Intelligent Scissors (a.k.a. Live Wire or Magnetic Lasso) [Mortensen and Barrett 1995] allows a user to choose a “minimum cost contour” by roughly tracing the objectrsquo;s boundary with the mouse. As the mouse moves, the minimum cost path from the cursor position back to the last “seed” point is shown. If the computed path deviates from the desired one, additional user-specified “seed” points are necessary. In fig. 2b the Magnetic Lasso of Photoshop 7 was used. The main limitation of this tool is apparent: for highly texture (or un-textured) regions many alternative “minimal” paths exist. Therefore many user interactions (here 19) were necessary to obtain a satisfactory result. Snakes or Active Contours are a related approach for automatic refinement of a lasso [Kass et al. 1987].

Bayes matting models colour distributions probabilistically to achieve full alpha mattes [Chuang et al. 2001] which is based on [Ruzon and Tomasi 2000]. The user specifies a “trimap” T = {TB,TU ,TF } in which background and foreground regions TB and TF are marked, and alpha values are computed over the remaining region TU . High quality mattes can often be obtained (fig. 2c), but only when the TU region is not too large and the background/foreground colour distributions are sufficiently well separated. A considerable degree of user interaction is required to construct an internal and an external path.

Knockout 2 [Corel Corporation 2002] is a proprietary plug-in for Photoshop which is driven from a user-defined trimap, like Bayes matting, and its results are sometimes similar (fig. 2d), sometimes of less quality according to [Chuang et al. 2001].

Graph Cut [Boykov and Jolly 2001; Greig et al. 1989] is a powerful optimisation technique that can be used in a setting similar to Bayes Matting, including trimaps and probabilistic colour models, to achieve robust segmentation even in camouflage, when foreground and background colour distributions are not well separated. The system is explained in detail in section.2. Graph Cut techniques can also be used for image synthesis, like in [Kwatra et al. 2003] where a cut corresponds to the optimal smooth seam between two images, e.g. source and target image.

Level sets [Caselles et al. 1995] is a standard approach to image and texture segmentation. It is a method for front propagation by solving a corresponding partial differential equation, and is often used as an energy minimization tool. Its advantage is that almost any energy can be used. However, it computes only a local minimum which may depend on initialization. Therefore, in cases where the energy function can be minimized exactly via graph cuts, the latter method should be preferable. One such case was identified by [Boykov and Kolmogorov 2003] for computing geodesics and minimal surfaces in Riemannian space.

1.2 Proposed system: GrabCut

Ideally, a matting tool should be able to produce continuous alpha values over the entire inference region TU of the trimap, without any hard constraint that alpha values may only be 0 or 1. In that way, problems involving s

剩余内容已隐藏，支付完成后下载完整资料

摘要:

静态图像中高效，互动的前景/背景分割的问题在图像编辑中具有重要的现实意义。 古典图像分割工具使用纹理（颜色）信息，例如 魔术棒或边缘（对比度）信息，例如 智能剪刀 最近，已经开发了一种基于图形优化的方法，其成功地组合了两种类型的信息。 在本文中，我们在三个方面扩展了图形化方法。 首先，我们开发了一个更强大的迭代版本的优化。 其次，使用迭代算法的功能来大大简化给定质量结果所需的用户交互。 第三，已经开发了一种用于“边缘消光”的鲁棒算法，以同时估计物体边界周围的alpha-matte和前景像素的颜色。 我们认为，对于中等困难的例子，此方法胜过有同样竞争力的其他工具。

1介绍

本文解决了复杂环境中前景对象的高效交互提取问题，其背景不能被简单地减去。 所得到的前景对象是反映前景和背景比例的-matte。 其目的是为了实现高性能而牺牲用户方面的部分交互努力。 此任务中的高性能包括：从背景准确分割对象; 主观令人信服的值，以应对模糊，混合像素和透明度。 一般来说，交互努力的程度范围从在劳动密集型极端中编辑个人像素，到仅仅接触几个位置的前景或者背景。

1.1交互式消光的前期方法

在下文中，我们简要描述和比较几种最新的交互式分割工具：魔术棒，智能剪刀，图形切割和水平套装以及垫子：贝叶垫和敲击。 图2显示了他们在消光任务上的结果，以及实现这些结果所需的用户交互程度。

魔术棒以用户指定的点或区域开始，以计算连接像素的区域，使得所有选定的像素落在指定区域的颜色统计信息的一些可调容差范围内。虽然用户界面很简单，但找到正确的容差级别往往很麻烦，有时候也是不可能的。图2a显示了使用Adobe Photoshop 7的魔术棒[Adobe Systems Incorp.2002]。因为前景和背景像素的颜色空间分布有相当大的重叠，所以不能实现令人满意的分割。

智能剪刀（a.k.a. Live Wire或Magnetic Lasso）[Mortensen和Barrett 1995]允许用户通过粗略地跟踪鼠标的对象边界来选择“最小成本轮廓”。当鼠标移动时，显示从光标位置返回到最后“种子”点的最小成本路径。如果计算出的路径偏离所需的路径，则需要额外的用户指定的“种子”点。在图中2b使用Photoshop 7的磁性套索。该工具的主要限制是显而易见的：对于高度纹理（或非纹理）区域，存在许多备选的“最小”路径。因此，为了获得令人满意的结果，需要许多用户交互（这里是19）。蛇或活动轮廓是自动细化套索的相关方法[Kass et al. 1987]。

贝叶斯消光模拟颜色分布概率地实现完全的阿尔法哑光[Chuang et al. 2001]，其基于[Ruzon和Tomasi 2000]。用户指定其中标记了背景和前景区域TB和TF的“trimap”T = {TB，TU，TF}，并且在剩余区域TU上计算alpha;值。通常可以获得高质量的哑光（图2c），但只有当TU区域不太大并且背景和前景色分布足够好地分离时。需要相当程度的用户交互来构建内部和外部路径。

Knockout 2 [Corel Corporation 2002]是Photoshop的专有插件，它是从用户定义的微调驱动的，如贝叶斯消光，其结果有时类似（图2d），有时根据[Chuang et al. 2001]。

Graph Cut [Boykov and Jolly 2001; Greig al.1989]是一种强大的优化技术，可以在类似于Bayes Matting的设置中使用，包括微分和概率颜色模型，以便在即使前景和背景颜色分布没有很好分离的情况下也能在伪装中实现强大的分割。系统在第2节中详细说明, Graph Cut技术也可用于图像合成，如[Kwatra et al. 2003]其中切割对应于两个图像之间的最佳平滑缝，比如来源和目标图像。

水平仪[Caselles et al. 1995]是图像和纹理分割的标准方法。它是通过求解相应的偏微分方程来进行前向传播的方法，并且经常被用作能量最小化工具。它的优点是几乎可以使用任何能量。但是，它仅计算可能依赖于初始化的局部最小值。因此，在可以通过图形切割精确地最小化能量函数的情况下，后一种方法应该是优选的。 [Boykov和Kolmogorov 2003]确定了一个这样的情况，用于计算黎曼空间中的测地线和最小表面。

1.2推荐系统：GrabCut

理想情况下，消光工具应该能够在三角形的整个推理区域TU上产生连续的alpha;值，而没有任何严格的约束，alpha;值只能为0或1.这样，涉及烟雾，头发，树木等的问题。可以自动处理。然而，根据我们的经验，旨在解决普通消光问题的技术[Ruzon和Tomasi 2000; Chuang等2001]在前景和背景颜色分布上做到充分分离，但在伪装方面不是很成功。事实上，甚至一般的消光问题在伪装中都是无法解决的，因为人类会发现很难察觉整个哑光。这使得我们对这个问题的研究不那么有意义但却是一种更可实现的形式。

首先，我们使用迭代图切割获得“硬”分割（第2和3部分）。之后是边框填充（第4部分），其中alpha;值在硬分割边界周围的窄条带中计算。最后，除了边界之外，完全透明度还没有被GrabCut处理。然而，根据我们的经验，可以使用Chuang等人的消光刷这在充分免费伪装的地区工作良好。

我们的方法的新颖性首先在于分割的处理。我们对图形切割机制进行了两个增强：“迭代估计”和“不完整标签”，这一点可以使给定质量结果的用户交互程度大大降低（图2f）。这允许GrabCut在用户上放轻载，其交互只是简单地拖动所需对象周围的矩形。在这样做时，用户指示背景区域，并且不需要标记前景区域。其次，我们开发了一种新的alpha计算机制，用于边界消光，其中alpha;值被正规化以减少可见的图像伪影。

2 Graphcut图形切割

首先，Boykov和Jolly的分割方法详细描述了构建基础的GrabCut的一些细节。

2.1图像分割

他们的论文[Boykov和Jolly 2001]提供了一个单色图像的分割，给出了一个初始的trimap T.图像是灰度值的数组z =（z1，...，zn，...，zN），由（单）索引n。图像的分割被表示为每个像素处的“不透明度”值alpha;=（alpha;1，...，alpha;N）的数组。通常0le;alpha;nle;1，但对于分割alpha;nisin;{0,1}，背景为0，前景为1。参数theta;描述图像前景和背景灰度分布，由灰度值直方图组成：

（1）

一个用于背景，一个用于前景。直方图直接从相应的微调区域TB，TF的标记像素组装。 （直方图在灰度级范围内归一化为1：R z h（z;alpha;）= 1）分割任务是从给定图像数据z和模型theta;推断未知不透明度变量alpha;。

2.2能量最小化分割

能量函数E被定义为使得其最小值应对应于良好的分割，其意义在于它被观察到的前景和背景灰度级直方图指导，并且不透明度是“一致的”，反映了趋于稳定的趋势对象这是由“Gibbs”能量捕获的形式：

（2）

给定直方图模型theta;，数据项U评估不透明度分布alpha;对数据z的拟合，并被定义为：

（3）

平滑度术语可以写成

（4）

其中[phi;]表示对于谓词phi;取值0,1的指标函数，C是相邻像素对的集合，其中dis（·）是相邻像素的欧几里得距离。这种能源促进了类似灰色地区的一致性。实际上通过将像素定义为邻居，如果它们在水平/垂直或对角线（8路连通性）相邻，则可获得良好的结果。当常数beta;= 0时，平滑度术语简单地是众所周知的Ising之前，在任何地方鼓励光滑度，达到由常数gamma;确定的程度。然而，已经显示[Boykov和Jolly 2001]，设定beta;gt; 0更有效，因为这放松了高对比度区域的平滑度趋势。选择常数beta;[Boykov和Jolly 2001]为：

，（5）

其中h·i表示对图像样本的期望。这种beta;的选择确保（4）中的指数项在高对比度和低对比度之间适当地切换。通过对15个图像的训练集合优化基于地面真实性能，获得常数gamma;为50。它被证明是广泛的图像的通用设置（参见[Blake等人2004]）。现在，能量模型是完全定义的，分割可以估计为全局最小值：

. （6）

最小化使用标准最小切割算法完成[Boykov和Jolly 2001; Kolmogorov和Zabih 2002]。该算法构成了硬分割的基础，下一节概述了GrabCut中新的硬分割算法的三个发展。首先，通过高斯混合模型（GMM）代替直方图将单色图像模型替换为颜色。其次，一次性最小切割估计算法被替换为估计和参数学习之间交替的更强大的迭代过程。第三，通过允许不完整的标签来放宽对交互式用户的需求 - 用户仅指定了微调的结构，这可以通过在对象周围放置一个矩形或套索来完成。

3 GrabCut分割算法

本节介绍GrabCut硬分割算法的新颖部分：迭代估计和不完全标注。

3.1颜色数据建模

现在，图像由RGB颜色空间中的像素zn组成。由于构建足够的色彩空间直方图是不切实际的，我们遵循已经用于软分割的实践[Ruzon和Tomasi 2000; Chuang al. 2001]并使用GMM。每个GMM，一个用于背景，一个用于前景，被认为是具有K个分量的全协方差高斯混合（通常为K = 5）。为了处理GMM，在优化框架中，引入了一个附加向量k = {k1，...，kn，...，kN}，其中knisin;{1，... K}，赋值根据alpha;n= 0或11，对于每个像素，独特的GMM分量，来自背景或前景模型的一个分量。吉布斯能量[公式 (2) ]用于分割现在变成了

（7）

也取决于GMM组件变量k。现在定义数据项U，考虑到颜色GMM模型

（8）

其中 = minus;log p(zn | alpha;n, kn,theta;)minus;logpi;(alpha;n, kn)，p（·）是高斯概率分布，pi;（·）加权系数，使（达到常数）：

（9）

因此，现在模型的参数

（10）

即权重pi;，表示mu;和对于背景和前景分布的2K高斯分量的协方差Sigma;。平滑度V与单色情况（4）基本上不变，除了使用欧几里德距离在颜色空间中计算对比度项：

（11）

3.2迭代能量最小化的分割

GrabCut中的新能量最小化方案反复运行，代替了以前的一次算法[Boykov和Jolly 2001]。这具有允许自动细化不透明度alpha;的优点，因为来自初始微调的TU区域的新标记的像素被用于细化颜色GMM参数theta;。 GrabCut系统的主要元素如图1所示。步骤1很简单，通过简单地枚举每个像素的kn值来完成。步骤2是实现一组高斯参数的估计过程，如下。对于前景模型中的给定GMM分量k，定义像素F（k）= {zn：kn = k和alpha;n= 1}的子集。平均mu;（alpha;，k）和协方差Sigma;（alpha;，k）以标准方式估计，因为F（k）和权重中像素值的样本均值和协方差为pi;（alpha;，k）= | F（k） | /Sigma;k| F（k）|，其中| S |表示集合S的大小。最后，步骤3是使用最小剪切的全局优化，与[Boykov和Jolly 2001]完全相同。算法的结构保证了适当的收敛性。这是因为迭代最小化的步骤1至3中的每一个可以被示为相对于三组变量k，theta;，alpha;的总能量E的最小化。因此，E单调减少，这在图中的实践说明了这一点。因此，算法至少保证了收敛于E的局部最小值。可以直接检测何时E不再显着降低，并自动终止迭代。迭代最小化的实际益处。图2e和2f说明了相对于单次图割[Boykov和Jolly 2001]方法，在GrabCut中迭代最小化的额外功率如何可以显著减少完成分割任务所需的用户交互量。这在两个方面是显而易见的。首先，在初始化和优化之后，需要用户编辑的程度会降低。第二，初始交互可以更简单，例如通过允许用户不完整的标签，如下所述。

3.3用户交互和不完整的trimaps

迭代最小化算法可以增加用户交互的多功能性。特别地，不完整的标签变得可行，其中，代替完整的微调T，用户仅需要指定背景区域TB，使TF = 0。完全没有很难的前景标记。迭代最小化（图3）通过允许随后可以缩回的一些像素（在前景中）的临时标签来处理这种不完备性;只有背景标签TB被认为是坚定的 - 保证不被稍后收回。 （当然，一个互补的方案，只有前台的公司标签也是一种可能性。）在我们的实现中，初始TB由用户确定为标记矩形外部的像素条（以红色标记图2f）。

4透明度

考虑到消光工具应该能够产生连续的alpha;值，我们现在描述一种机制，通过这种机制，如上所述，可以通过“边界消光”来增强分割，其中允许在周围的狭窄条带中具有完全透明性分割边界。这足以应对在光滑对象边界处存在模糊和混合像素时消光的问题。技术问题是：估计条纹的alphamap而不产生人工制品，并能够恢复前景色，没有背景颜色渗色。

4.1边框垫

边框填充从封闭的轮廓C开始，通过从前一部分的迭代硬分割将多义线拟合到分割边界而获得。计算出一个新的微分{TB，TU，TF}，其中TU是C中任一边的宽度plusmn;w像素的带中的像素集合（我们使用w = 6）。目标是计算地图alpha;n，nisin;TU，为了强壮地做到这一点，对于TU内的alpha;轮廓的形状，假定强模型。该模型的形式基于[Mortensen和Barrett 1999]，但有两个重要的补充：正则化以提高估计的alpha;图的质量;以及用于在整个TU中估计alpha;的动态规划（DP）算法。

4.2前景估计

这里的目的是估计前景像素颜色，而不会从源图像的背景中渗出颜色。由于使用了概率算法，Bayes matting可以发生这种渗色，其目的是从混合像素中剥离背景分量，但不能精确地进行。剥离过程的残留物可

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[139847]，资料为PDF文档或Word文档，PDF文档可免费转换为Word