快速图像分割和抠图技术研究

胡 亮, 金日浩, 赵 阔, 李 洁

(1. 吉林大学 计算机科学与技术学院, 长春 130012; 2.国网吉林省电力有限公司 电力科学研究院, 长春 130021)

0 引 言

在计算机视觉领域, 图像分割是将图像中具有不同含义的不同区域分割开来, 这些区域是不相互交叉的, 每个区域都满足特定区域的一致性[1]。典型的图像分割主要用于定位图像中目标区域及其边界, 简言之, 图像分割就是给图像每个像素都分配一个标签, 标注其所属区域的属性, 以此将一个图像分成若干个区域[2]。

目前的图像分割技术主要有基于聚类算法的图像分割、 基于直方图的图像分割和基于边缘检测的图像分割等。笔者针对基于图割理论的图像分割方法进行分析, 图割理论可有效实现图像分割, 通过将图像建模成一个有权无向图, 图像中的每个像素点代表图中的一个节点, 而边的权值则由像素点之间的亲和度决定, 并根据确定的标准完成图像分割。

1 相关工作

1.1 Graph cuts方法

1989年, Greig等[1]首次将图割理论引入到图像处理领域, 通过求解最大流最小割问题实现对分割结果的最大后验估计, 以此达到对图像分割的目的。Graph cuts作为图像分割和抠图领域内的经典算法, 得到了科研工作者的广泛关注后涌现出了很多基于Graph cuts的图像分割和抠图技术。在Graph cuts算法中需要构建一个能量函数, 通过解决最小化能量函数问题实现分割的目的, 而这个最小化能量函数的问题可转变成图的最大流最小割问题, 所以Graph cuts的本质就是构建一个有权无向图并求解其最大流最小割问题[3]。

Boykov等[4]在2001年提出的Graph cuts算法主要是针对灰度图像, 根据像素点的灰度值g={g1,…,gn,…,gN}和α值α={α1,…,αn,…,αN}建立灰度直方图, 其中αn∈{0,1}。前景和背景的灰度分布关系[5]

θ={h(z;α),α=0,1}

(1)

其中h(z,α)表示前景和背景的灰度直方图。

根据像素的前背景隶属度和相邻像素间的亲和关系, 构建能量函数[5]

E(α,θ,z)=U(α,θ,z)+V(α,z)

(2)

通过最小化能量函数可得到较好的分割结果。其中U(α,θ,z)为数据项, 由像素点的灰度值与直方图中α分布的符合程度决定, 反应了像素点的前景和背景隶属度[5]

U(α,θ,z)=∑n-log(h(z;α))

(3)

通过相邻像素点间的灰度差值和距离得出平滑项[5]

V(α,z)=γ∑(m,n)∈Cdis(m,n)-1[αn≠αm]exp{-β(zm-zn)2}

(4)

其中[·]表示一个函数, 若·为真, 则返回1, 否则, 返回0。C表示邻居像素点对的集合, dis(·)表示图像空间内的欧拉距离, 而β是一个全局的属性, 对相邻像素点灰度的差值进行量化, 保证了对结果影响的一致性。平滑项充分考虑了相邻像素点之间的关系, 在边缘区域相邻像素点间的灰度差值较大, 平滑项越小, 在边缘处分割使整个能量函数的值也越小。

在对能量函数及其各项定义后, 根据最大流最小割算法即可实现能量函数的全局最小化, 最终达到图像分割的目的。

1.2 Grabcut方法与分析

Grabcut方法是在Graph cuts的基础上将分割技术的目标转向彩色图像, 并对能量函数的数据项和平滑项做了相应改进。Rother等[6]将前景和背景像素分别建模成高斯混合模型, 更有效地表示前景和背景的颜色分布, 通过对一个迭代过程优化能量函数求解, 而且在交互方面Grabcut只需要用户提供一个矩形框, 不需要过多的线条即可完成对图像的分割。

Grabcut方法中, 对前景和背景各建立一个高斯混合模型(GMM： Gaussian Mixture Model), 并且每个高斯混合模型都有K个高斯模型(GM： Gaussian Model)。每个像素在同一时间内, 只能属于一个GM, 用kn表示所属GM的序号, 而属于前景的GMM还是背景的GMM则由αn={0,1}表示。所以由(αn,kn)就能唯一确定一个GM, Grabcut的能量函数可表示为[5]

E(α,k,θ,z)=U(α,k,θ,z)+V(α,z)

(5)

其中k标识了像素所属的高斯模型, 由于数据项须考虑高斯混合模型----GMM, 所以定义数据项[5]

U(α,k,θ,z)=∑nD(αn,kn,θ,zn)

(6)

其中D(αn,kn,θ,zn)=-logp(zn|αn,kn,θ)-logπ(αn,kn),p(·)表示高斯概率,π(·)表示混合权重系数, 所以可表示为[5]

其中π,μ,Σ分别表示代表前景和背景颜色分布的2K个GM的权重、 平均值以及协方差, 其中k表示每个高斯混合模型所含有的高斯模型个数,π(αn,kn)值等于所有的第kn个GM的像素点所占区域与整个区域之比。与Graph cuts相比, 平滑项只是减少了图像空间内的欧拉距离[5]

V(α,z)=γ∑(m,n)∈C[αn≠αm]exp{-β‖zm-zn‖2}

(8)

与Graph cuts不同, Grabcut的能量函数通过不断迭代求最小值实现图像分割问题。在每次迭代的过程中, 根据上一次分割的结果对图像进行重新建模, 优化GMM模型的参数, 再根据新的GMM模型对图像进行分割, 直至能量函数减小幅度不明显时, 迭代自动结束。算法基本流程如下：

1) 根据用户提供的矩形框, 创建三分图, 矩形框内的像素标识为未知像素点, 矩形框外为已知背景像素点；

2) 建立初始的图像分割结果, 所有未知像素点为前景, 所有已知背景像素点为背景；

3) 根据初始的分类结果, 为前景和背景分别建立GMM；

4) 将每个前景像素分配到最适合的前景高斯模型中, 类似地, 将每个背景像素分配到最适合的背景高斯模型中；

5) 根据前景和背景中像素在GMM中新的分配方案更新GMM的参数；

6) 建立一个图, 并根据GMM参数信息和平滑项初始化该图, 利用求解最大流最小流算法获得前景和背景新的分配方案；

7) 重复4)～6), 直至能量趋于不变, 算法结束。

通过对迭代求解, 更加充分地保证了结果的质量, 同时也大大减少了所需的交互量, 使最初用户只需要提供一个简单的矩形框即可实现图像的分割。

2 快速抠图技术的分析

随着对抠图技术应用性的重视, 也有越来越多的科研工作者将研究重点转移到对抠图速度的提升上。在对已有抠图方法的研究基础上, 发掘影响抠图速度的主要因素, 研究新的、 快速的、 效果较好的抠图算法。同时, 也结合当前较为流行的并行技术对算法进行设计, 使抠图算法更适合在并行技术下运行, 进一步提高处理速度。

2.1 抠图技术耗时因素分析

在Closed-form方法等一些基于线条的抠图算法中, 由于用户交互量较少, 只提供了简单几条线条, 将少量的像素点标识为前景或背景。在这种前景和背景样本较少的情况下, 如果要取得较好的抠图效果, 可以通过两种方法实现：

1) 利用扩散算法或区域增长算法扩展已知区域, 增加前景和背景样本数量, 减少未知像素点的数量；

2) 对图像建立一个较好的数学模型, 通过求解复杂的数学问题完成抠图处理。

在第1种方法中, 扩散算法或区域增长算法的选取极为重要, 既要避免对样本的误选, 又要保证扩展尽可能大的区域。而这样的算法往往又较为耗时, 由于未知像素点的数量大大减少, 扩展后的处理可能时间代价较低, 但总体的时间消耗仍然很高。Closed-form方法是第2种方法的一个典型例子, 通过假定在一个小范围的像素的颜色值满足一个线性关系, 建立了一个大规模线性方程组, 其系数矩阵的行数和列数都是图像内像素点的数量。因此, 该方程组极为庞大, 求解该线性方程组对内存和时间也有较高的要求。虽然Closed-form方法提出对图像进行下采样, 减小图像的大小, 达到减小线性方程组进而减少计算时间的目的, 但在下采样和上采样时, 必然存在着数据的遗漏, 影响抠图效果。所以在对图像进行下采样处理时, 必须适当调节下采样次数, 避免对结果产生过大的影响。通过下采样, 使Closed-form方法的处理时间得到了一定的降低, 但仍存在较高的时间代价[7]。

在基于三分图的抠图技术中, 进行抠图处理前, 需要用户输入一个三分图标识已知前景区域、 已知背景区域和未知区域, 而三分图中未知区域的大小是影响抠图处理所需时间的重要因素, 应该尽量精确地减少未知区域面积, 所以三分图的制作也是一项很重要的工作, 这在一定程度上增加了基于三分图的抠图技术的应用代价。在多数基于三分图的抠图方法中, 影响抠图速度的主要因素有： 前景和背景样本的采样方式； 前景和背景样本的数量； 根据样本对颜色估计的算法的代价。

2.2 Shared Matting方法

2010年, Gastal等[8]对已有算法进行分析, 通过减少前景和背景样本数量的方式, 大大降低了颜色估计的计算量, 使抠图算法的运行时间降低了50%以上, 同时也保证了抠图结果的质量。算法中图像像素的处理是相互独立的, 可以很好地应用并行技术, 达到实时抠图效果。

对自然图像的抠图处理, 相邻像素的前景值F、 背景值B和α值具有较高的相似性。因此, 在Bayesian Matting方法中前景和背景样本过于集中, 颜色色度差值却较小, 造成了很多不必要的计算量。同时由于选取的相邻未知像素点样本过度重复, 导致相邻像素点亲和关系的优化结果不良。因此, 样本选取应该避免样本过于集中, 并保证与相邻未知像素点的样本保持一定的差异性。

Shared Matting方法根据未知像素点及其邻居的样本信息筛选最合适的元组(α,F,B), 并对α图像进行局部平滑处理, 保证α值的连续性, 使结果更加自然。

3 快速图像分割方法

在Closed-form等一些基于线条的抠图技术中, 在对边缘较为复杂的图像进行抠图处理时, 如果要实现较好的边缘提取效果, 必须进行大量的计算, 为抠图处理造成了巨大的时间代价。而在基于三分图的抠图技术中, 虽然抠图速度得到了一定提升, 但预输入的三分图是抠图处理的关键, 需要较为细致的工作完成对三分图的区域划分, 这也间接地增加了抠图处理时间。针对这些问题, 结合基于图割理论图像分割算法Grabcut和基于三分图的抠图算法Shared Matting建立了一个快速分割抠图系统[7], 以Grabcut的分割结果为基础, 为Shared Matting提供三分图, 既方便了用户交互, 也保证了处理时间, 同时也能获得较好的处理结果。

3.1 快速图像分割和抠图系统

系统利用Grabcut对图像进行简单分割, 并根据分割边缘进行简单扩散, 生成一个三分图, 为Shared Matting方法提供输入数据, 解决了之前基于线条的抠图技术和基于三分图的抠图技术遇到的问题。该方法将基于图割理论的图像分割、 三分图生成和基于三分图的抠图技术相结合, 建立了一个快速图像分割和抠图系统, 其处理流程如图1所示。该系统体现了图像分割和抠图各自的优势, 提高了算法效率。

图1 图像分割和抠图系统流程

3.2 前背景分割

在前背景分割部分主要使用第2节研究的Grabcut方法。因为其初始交互只需一个简单的矩形框, 并通过前景和背景进行高斯混合建模, 能较好地表现其颜色的分布情况, 保证了分割结果的质量, 也间接地减少了用户的进一步交互。通过用户交互的一个矩形框, 对图像完成初始分割。如果对分割结果不满意, 可以通过前景画笔和背景画笔指定源图像中的完全前景区域和完全背景区域, 更新Grabcut中的GMM模型, 重新计算最大流最小割的分割结果, 直至得到满意的结果。

3.3 三分图生成

目前已有一些生成三分图的方法, 但都不能很好地符合笔者所建立的快速图像分割和抠图系统的要求。例如文献[9]中, 根据在前景轮廓附近的前景和背景区域输入的不连续前景线段和背景线段, 使用Munsell颜色空间中的颜色相似性度量算法作为其生长准则, 利用区域生长算法扩展已知前景和背景区域, 最终获得一个较好的三分图。虽然在获得的三分图中未知区域较小, 但该三分图生成算法时间代价过高, 不适合笔者所建立的系统在时间上的要求。笔者利用一个较为简单方法生成三分图, 避免在该步骤上花费过多时间。在前背景分割基础上, 针对前景轮廓边缘进行扩展, 将轮廓附近的像素点标识为未知, 再利用Shared Matting进行抠图处理。

3.4 抠图处理

根据生成的三分图和输入的源图像进行抠图处理。在笔者所建立的快速图像分割和抠图系统中, 采用Shared Matting方法进行抠图处理。这是因为Shared Matting方法在文献[10]中所建立的抠图效果评测系统取得很好排名(目前排在第2位), 不仅在串行运行的情况下也有较大优势, 而且在算法的每步中, 对像素点的处理是相互独立的, 适合并行性优化。

4 系统设计及结果分析

图2 快速图像分割和抠图系统架构图

根据对快速图像分割和抠图系统分析, 对系统的架构进行设计。以QT图形交互界面为中心, 将前背景分割、 三分图生成和抠图处理作为3个独立模块, 通过三者之间协同工作, 完成对输入图像的抠图处理(见图2)。图2中(1)是将用户的交互操作和图像导入到前背景分割模块进行分割处理, 图2中(2)表示将分割结果返回到交互界面并进行展示, 图2中(3)是将分割结果和用户设定参数输入到三分图生成模块中, 图2中(4)将生成的三分图返回交互界面, 图2中(5)将图像和最终的三分图生成结果输入到抠图处理模块, 图2中(6)将抠图处理结果返回到交互界面进行展示(见图3)。

图3 图形交互界面展示

菜单栏： 包括File、 Segmentation、 Matting、 PenWidth和Help 5个菜单项, 分别负责控制打开文件、 前背景分割、 三分图生成及抠图、 设置画笔宽度和系统概述5个功能模块。全面考虑了用户的需求, 涵盖了实际中常用的所有功能。

工具栏： 通过将图标与菜单栏中的相应功能结合, 使交互变得更加人性化, 增加了系统的易用性。视图区包括Viewer1和Viewer2两个视图。将人工交互和结果在两个独立的视图中同时呈现给用户, 方便用户交互操作。其中Viewer1主要用于源图像的显示和人工交互, Viewer2主要用于结果展示, 也为Viewer1中的交互提供了参考。

状态栏： 针对每个按键和按钮都提供了相应信息, 提示用户当前鼠标所位于的按钮或按键功能, 提高了系统易用性, 降低了系统对使用者要求。

如上所述, 笔者提供了一个简洁而功能非常完善的图像交互界面, 只需一个输入图像, 再经过简单的交互操作就能在很短的时间内得到一个效果良好的抠图结果。

将图像界面和已实现的算法相结合, 建立了一个界面友好的快速图像分割和抠图系统。结合实验样例展示的系统主界面如图4所示。

图4 主界面及样例演示

根据测试结果可看出, 在对每个具有代表性的图像进行处理中, 均取得较好的处理结果。笔者所建立的快速图像分割和抠图系统中, 利用Grabcut算法对前景进行分割, 根据分割结果生成三分图, 避免了三分图制作的繁琐工作, 并以此作为Shared Matting方法输入, 得到最终抠图结果。如果分割结果中前景部分存在大范围的完全背景区域, 则应该在生成三分图前进行交互, 优化分割结果。如果在分割结果中前景部分存在透明区域或毛发较多区域, 则不需要优化分割结果, 只需在生成三分图后, 对三分图进行优化即可。再利用生成的三分图, 使用Shared Matting方法进行抠图处理。系统所使用的算法主要包括改进后的Grabcut算法、 三分图生成算法和Shard Matting算法, 并行优化后的Shard Matting方法和改进后的Grabcut方法时间代价均很小, 而三分图生成算法在并行优化前的时间复杂度也仅为O(n)(n为像素数量)。因此系统总的时间消耗很小, 能在很短的时间内完成抠图处理。

5 结 语

笔者从目前抠图技术研究现状和趋势入手, 总结并归纳了现有的经典抠图技术。经过严谨的理论研究和实验仿真, 结果表明, 该系统适用性较强, 可用性较好, 并且能在短时间内利用较少的交互量取得很理想的抠图效果。在今后的研究工作中, 需要对以下几个方面进行进一步研究。

1) 笔者所使用的三分图生成算法只考虑了图像空间的距离, 可以结合颜色空间的距离建立其他模型改进算法, 并使算法能在边缘处自动适应宽度, 减少对三分图的优化, 增加算法适用范围。

2) 基于线条的抠图技术往往根据少量简单的线条即可实现抠图, 并得到较好的抠图效果。可以结合在基于线条的抠图技术中所采用的模型, 对系统中基于三分图的抠图技术进行优化修改, 提升抠图质量。

参考文献：

[1]PORTER T, DUFF T. Compositing Digital Images [J]. Proceedings of ACM SIGGRAPH, Computer Graphics, 1984, 18(3): 253-259.

[2]EVIN A, LISCHINSKI D, WEISS Y. A Closed Form Solution to Natural Image Matting [J]. International Journal of Computer Vision, 2009, 82(2): 113-132.

[3]GRADY L, SCHIWIETZ T, AHARON S, et al. Random Walks for Interactive Alpha-Matting [C]∥Proceedings of VIIP 2005. Spain: [s.n.], 2005: 423-429.

[4]BOYKOV Y, JOLLY M P. Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in N-D Images [C]∥International Conference on Computer Vision-ICCV. Vancouver BC: [s.n.], 2001: 105-112.

[5]BERMAN A, DADOURIAN A, VLAHOS P. Method for Removing from an Image the Background Surrounding a Selected Object : US, Patent 6, 134, 346[P], 2000-10-07.

[6]ROTHER C, KOLMOGOROV V, BLAKE A. Grabcut-Interactive Foreground Extraction Using Iterated Graph Cut [J]. ACM Trans Graph, 2004, 23(3): 309-314.

[7]WANG J, COHEN M F. Optimized Color Sampling for Robust Matting [C]∥Proceedings of CVPR, IEEE Conference on Minneapolis. MN: IEEE Computer Society, 2007: 1-8.

[8]GASTAL E S L, OLIVEIRA M M. Shared Sampling for Real-Time Alpha Matting [J]. Eurographics, Computer Graphics Forum, 2010, 29(2): 575-584.

[9]BERMAN A, VLAHOS P, DADOURIAN A. Comprehensive Method for Removing from an Image the Background Surrounding a Selected Object: US, Patent 6, 134, 345[P], 2000-10-17.

[10]CHUANG Y Y, CURLESS B, SALESIN D, et al. A Bayesian Approach to Digital Matting [C]∥Proceedings of IEEE Computer Vision and Pattern Recognition (CVPR 2001). Kauai, Hawaii: IEEE Computer Society, 2001: 264-271.