基于四叉树分解与图割的彩色图像快速分割*

胡志立，郭 敏

(1.现代教育技术教育部重点实验室，陕西 西安 710062;2.陕西师范大学计算机科学学院，陕西 西安 710062)

1 引言

图像分割将图像划分为有意义的若干区域或者用于提取人们感兴趣的区域，它在计算机视觉、模式识别和图像工程等学科中都发挥着重要的作用。图割作为一种基于图论的组合优化方法，可以用来最小化计算机视觉中的能量函数问题。Greig D等[1]首次将图割应用于图像处理领域，同时他们最早提出使用功能强大的最小割/最大流算法来最小化计算机视觉中的能量函数；随着Boykov Y等[2,3]将其应用到图像分割领域，引发了国际上对图割理论及其应用的研究热潮。Boykov Y等[4]提出了基于增广路径的新方法：扩展移动(Expansion-moves)和交换移动(Swap-moves)，有效地提高了最小割/最大流算法的效率。Li Y等[5]首先利用分水岭(Watershed)算法对图像进行预分割，将图像分成很多内部颜色较为一致的小区域；然后将每个小区域作为一个节点，利用图割方法进行划分，得到最终分割的图像；利用小区域代替区域内部像素点构造出来的图的节点明显减少，然而由于预分割本身的时间较长，所以对图割时间上的改进较少。Blake A等[6]使用高斯混合模型GMM(Gaussian Mixture Model)对前景和背景颜色空间进行建模，从而能够较好地利用图像的颜色信息对彩色图像进行分割。Rother C等[7]提出的GrabCut采用多次迭代图割进行图像分割，它只需要用户指定一个围绕目标的矩形框便可提取感兴趣的目标，有效减少了用户交互量。

利用GrabCut多次迭代图割进行图像分割，在处理海量级图像数据时，耗时往往比较大。其切割实质是迭代使用图割进行高斯混和模型GMM参数估计，直到满足收敛条件，从而完成图像分割。整个过程中确定GMM参数成本高，这制约了整个算法的时效性。徐秋平等[8]引入多尺度分析方法，以塔式分解的多尺度图像序列代替原始图像进行GMM参数迭代估计，以较少样本快速确定GMM参数，分割精度不减而效率显著提高。徐秋平等[9]使用分水岭变换对图像进行预处理，以部分具有典型代表的样本点来估计GMM参数，这有效地提高了GrabCut算法的效率。韩守东等[10]利用多尺度非线性张量纹理特性(MSNST)描述图像的纹理特征并构建基于MSNST的GMM，使得MSNST能有效地与GrabCut结合；他们还提出一种自适应融合策略来调整混合因子，以有效地融合图像的色彩特征和MSNST纹理特征，从而得到比GrabCut更好的分割效果。韩守东等[11]在MSNST空间利用独立尺度分量形式黎曼协方差高斯混合模型(ICRGMM)在纹理聚类中的优势取代GMM，为了更精确地估计和更新统计参数，使用分量形式期望最大化代替GrabCut原有的K-means算法，使得算法能有效地分割纹理图像而且对自然场景图像也有不错的分割效果；韩守东等[12]使用高斯超像素来构建图割模型以实现加速，他们使用快速均值漂移算法对图像进行预分割，从而构建精简的加权图。为了准确而精炼地对先验知识进行参数化学习，他们还使用了分量形式的期望最大化混合高斯算法对用户交互进行聚类，使得算法在精确性方面和高效性方面都有较好的性能。

基于合并区域然后将整个区域看作一个超像素进行GMM参数估计以减小问题规模的思想，本文使用四叉树分解来得到区域内颜色相近的图像块，我们将整个区域块描述成超像素，每个超像素点对应着网络图的节点，相邻像素间的差异对应着边上的容量，以此构建精简的网络图，并用块内的RGB均值代替该块内的所有像素点的值进行高斯混合模型参数估计，从而减小问题规模，达到提高GrabCut算法时效的目的。

2 相关研究

2.1 四叉树分解

四叉树分解的目标是将原始图像逐步分成小块，操作的原理是将具有一致性(像素间的灰度差值小于给定的阈值)的像素分到同一小块中。四叉树分解过程如下：令R表示当前进行分解的图像区域，并选择一个属性Q(区域的像素间满足一致性标准)。如果有Q(R)=FALSE，则将该图像区域分割为四个象限区域。对于其中的任意一个区域，如果仍有Q(R)=FALSE，则将该象限区域再次细分为四个象限区域，以此类推，直到图像中的所有区域都满足一致性标准才停止。最后，四叉树分解的结果可能包括多种不同尺寸的方块。由此原理可知，当图像是正方形，且像素点的行数和列数是2的整数次幂时，四叉树分解算法是最适用的。对于其它图形可以通过适当填充来获得合适的图像。

2.2 图割简介

图割是一种基于图论的组合优化方法，它将一幅图像映射成一个网络图，并建立关于标号的能量函数；然后运用最大流/最小割算法对网络图进行切割，得到网络图的最小割，即能量函数的最小值。设G=(V,E)为一个带有非负边权的有向图，其中V为顶点集，对应图像的像素点集P，E为边集。V包含两个特殊的顶点，通常一个称为源S，一个称为汇T。每个顶点有两个边，连接源和汇的边称为t-links，反映当前顶点对于标记的偏好程度；邻域连接n-links反映了顶点之间的差异性。最小割就是图G所有割中容量最小的割，它可根据Ford L和Fulkerson D[13]提出的网络流理论，通过求网络图的最大流而得到。

2.3 GrabCut算法

GrabCut将图像表示为矢量Z={z1,z2,…,zn,…,zN}，将该图像的分割表示为求每个像素点的值α={α1,α2,…,αn,…,αN}，αn∈{0,1}，其中0表示背景，1表示前景。GrabCut使用两个GMM，一个对应背景，另一个对应前景。每个GMM由K个高斯模型混合而成(通常K=5)，每个像素有一个参数kn(kn∈{1,…,K})，参数来自前景还是背景取决于αn的取值。GrabCut算法的Gibbs能量函数形式为[7]：

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

(1)

其中，θ代表图像的GMM参数。

数据项U定义为：

(2)

其中：

D(αn,kn,θ,zn)=

-logp(zn|αn,kn,θ)-logπ(αn,kn)

(3)

其中，p(·)为高斯概率分布；π(·)为混合权重系数，也就是kn为某一个值的像素数占总的像素数的比例。

于是有：

D(αn,kn,θ,zn)=-logπ(αn,kn)+

0.5log det∑(αn,kn)+0.5[zn-

μ(αn,kn)]T∑(αn,kn)-1[zn-μ(αn,kn)]

(4)

那么，参数θ可表示为：

θ={π(α,k),μ(α,k),

∑(α,k),α=0,1,k=1,…,K}

(5)

平滑项V可用RGB空间的欧几里德距离求得：

(6)

GrabCut算法的主要流程如下：

整个GMM参数的迭代估计是在TU中进行的，根据标定的背景区域和未知区域初始化GMM，以下述(1)～(3)对TU迭代直至收敛：

如果当前得到的能量值记为E(i)，上次迭代输出的能量值为E(i-1)，那么可以将能量变化率定义为：Rate=(E(i-1)-E(i))/E(i-1)，可以将能量变化率是否小于给定的阈值作为判断GMM参数估计是否收敛的条件。算法收敛后，TF=TU,这样就分隔出所需的前景部分。

3 基于四叉树分解和GrabCut的彩色图像分割方法

3.1 GrabCut算法改进分析

从GrabCut算法的流程可知，其N次迭代收敛过程可分为两部分：前N-1次迭代使用最大流进行分割，目的是学习、修正GMM参数，第N次分割实现最终的图像分割。既然前N-1次分割是为了确定GMM参数，而每次使用最大流去最小化能量函数的时间开销往往比较大，那么使用超像素的方法合并相似的区域，然后再对该块状图构造网络图并求解该网络图的最大流/最小割，这样就可以有效减少确定GMM参数的时间消耗。最后，为了使得分割结果尽可能地接近原始算法的精度，我们使用最终得到的GMM参数对原始图像的TU部分进行分割，从而得到最终结果。

对于一幅2N×2N(如果图像不是2N×2N，可以适当地进行填充)的图像，给定阈值进行四叉树分解，能够快速地找到图像中满足一致性标准的正方形区域。对于灰度图像，灰度变化值小于给定阈值的像素将会被合并到同一个区域；对于彩色图像，在RGB分量上变化的均值小于给定阈值的像素会被合并到同一个区域。阈值设置得越高，就会有越多的像素被划分到同一分块中，从而分割速度越快，然而过高的阈值使得图像细节丧失过多，使得最终出现过分割。

综上所述，本文提出的改进思路是：设置适当的阈值进行四叉树分解，得到区域内相似度比较高且拓扑结构相对规则的块状图，进而使用各个块中的RGB均值作为该块的超像素值，然后再进行GMM参数估计，最后为保证精度，我们使用得到的GMM参数对原始的图像进行分割，从而达到提高分割速度而精度不减的目的。对于默认的阈值，如果分割结果跟原算法相比存在明显的过分割，可以降低阈值，直到达到原算法的精度。一般情况下，待提取目标的边界两侧在颜色上会有一定程度的差异，只要设置好适当的阈值，本文的算法便是可行的。

3.2 块状图的生成

由于四叉树分解总是将满足一致性的区域分解成大小相同的四个正方形区域，所以首先要将不是2N×2N的图像填充成使N尽可能小的2N×2N的图像再将其转换成灰度图像，然后进行四叉树分解，最后分别将此分解应用到彩色图像的RGB分量上。考虑到直接对填充后的图像进行处理，填充的区域会拥有较多的块数(如将一幅513×513的图像填充成1 024×1 024)，这样会增加额外的处理时间，我们将分解后的图像裁剪成原始大小，然后对裁剪后的图像建立每块的索引，并将方形区域内每个像素的RGB值用该区域的RGB均值代替。将分块图中的每个分块看作一个超像素，整个超像素图可记作B={b1,b2,…,bn,…,bN}，N为节点个数。对于一幅牡丹图像的处理效果如图1所示(由图1b可以看出，四叉树分解算法可以在一定程度上保持原有的边界信息和颜色信息，对原有边界信息和颜色信息保持得越好，最终的分割结果就越接近GrabCut算法的精度)。

Figure 1 Comparison of quadtree decomposition result and orignal image图1 四叉树分解预处理结果与原始图像对比图

3.3 GMM参数迭代估计

3.3.1 初始化GMM参数

3.3.2 最小割进行分割

Figure 2 Network graph and minmum cuts图2 网络图与最小割

Figure 3 Results of the first cut图3 第一次分割的结果

3.3.3 更新GMM参数、判断收敛及后续处理

每一次最小割分割之后都会将TU中的节点分割成前景或者背景并输出当前的能量值，将TU中的前景节点作为样本估计前景GMM参数，TU中的背景节点及TB作为样本估计背景GMM参数。按照初始化GMM参数的方法计算kn、μ(α,k)、∑(α,k)、π(α,k)，并以此更新GMM参数。判断收敛的方法与GrabCut一致。程序收敛以后分割的结果锯齿现象十分明显，为了保证处理的结果更接近GrabCut算法，我们用得到的GMM参数对原始像素图的TU部分进行一次分割得到最终结果。

3.4 算法的实现步骤

综上所述，基于四叉树与GrabCut的彩色图像快速分割主要实现步骤如下：

(1)输入彩色图像I，将其填充成使得N尽可能小的2N×2N的图像，再将其转换成灰度图像，然后进行四叉树分解，再将分解后的图像裁剪成原始大小，然后根据此分解，生成块状图，并建立关于每块的索引。

(2)根据块索引，初始化分块图的GMM：

②对于bn∈TB，有αn=0；bn∈TU，有αn=1；其中αn=0代表背景，αn=1代表前景，并以此初始化GMM。

(3)迭代估计GMM参数：

①初始化GMM参数。

②学习GMM参数。

③对超像素图构造网络图，并用最小割进行分割。

④迭代①～③直至满足收敛条件。

(4)根据所得到的GMM参数对原始图像I构造S-T网络，并用最小割算法进行分割。

(5)输出分割的结果。

4 实验结果与分析

本文实验平台为：64位Windows 7,Matlab R2011a,Microsoft Visual Studio 2010,CPU:Core i5-2450M,RAM:8 GB。对于每一幅图像，人工设置一个矩形框选中目标区域，然后输出GrabCut算法、基于分水岭变换改进的GrabCut算法[8]和本文算法所提取到的目标、二值的分割结果及三者的时间消耗对比图。无论是使用分水岭算法预处理得到分块图还是使用本文算法预处理得到分块图，都因问题规模的减小导致有时改进的算法会比GrabCut算法早收敛，为了方便得到三者的时间消耗对比图，我们使用规定最大迭代次数这种方法进行处理，只要GrabCut算法已经收敛,就不会对实验结果造成较大的影响。对于图1中的原始图片分割的效果如图4所示。

Figure 4 Comparison of segmentation of three algorithms图4 三种算法分割效果对比图

由实验结果可看出，本文算法的精度与GrabCut基本一致，但时间上要优于GrabCut。本文算法的时间消耗是1.295 s，GrabCut算法耗时8.814 s，本文算法的时间消耗仅占GrabCut算法的14.69%，通常情况下，基于分水岭变换改进的GrabCut算法与本文算法在时间上的改进大致相当，且能达到GrabCut算法的精度。

本文算法在运用于图像分辨率比较高且细节较少的情况下效果更好，图5和图6是对一组图像测试的结果(其中企鹅图像(680×509)、猎人图像(680×500)、鲸图像(1 024×720))。表1是对伯克利图像分割测试图库的另一组图片测试的结果。

Table 1 Time comparison between our algorithm and GrabCut

Figure 5 Segmentation resutls of three algorithms图5 三种算法分割效果图

Figure 6 Time comparison among three algorithms图6 三种算法分割时间对比图

从上面的图和表可以看出，本文算法的分割效果与GrabCut非常接近，有的图像人眼很难分辨两种算法分割结果的优劣，而时间上明显优于GrabCut。基于分水岭变换改进的GrabCut算法与本文算法一样，都明显提高了算法的时效性，而且精度上与GrabCut算法十分接近。

5 结束语

GrabCut是一种优秀的交互式图像分割算法，其用户交互量少且分割精度高，然而它为了达到一定分割精度而采用多次迭代图割的方式求解GMM参数，这使得处理海量级图像数据时，时效性很低。针对该问题，本文使用了合并相似区域然后将整个区域看作一个超像素进行GMM参数估计以减小问题规模的思想，并用四叉树分解予以实现。实验结果表明，改进的方法在加快GMM参数估计的同时，基本上保持了和原算法相当的分割效果，这表明了该思想的可行性及有效性。此外，合并相似区域然后将整个区域看作一个超像素进行处理的改进思想也可以推广到基于图割理论进行图像分割、图像镶嵌、图像拼接等其他算法中。

[1] Greig D, Porteous B, Seheult A. Exact maximum a posteriori estimation for binary images[J]. Journal of the Royal Statistical Society(Series B), 1989, 51(2):271-279.

[2] Boykov Y,Jolly M P.Interactive organ segmentation using graph cuts[C]∥Proc of the 3rd International Conference on Medical Image Computing and Computer-Assisted Intervention, 2000:276-286.

[3] Boykov Y,Jolly M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images[C]∥Proc of the 8th IEEE International Conference on Computer Vision, 2001:105-112.

[4] Boykov Y,Veksler O,Zabih R.Fast approximate energy minimization via graph cuts[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11):1222-1239.

[5] Li Y, Sun J, Tang C K, et al. Lazy snapping[J]. ACM Transactions on Graphics, 2004, 23(3):303-308.

[6] Blake A, Rother C, Brown M, et al. Interactive image segmentation using an adaptive GMMRF model[C]∥Proc of the 8th European Conference on Computer Vision, 2004:428-441.

[7] Rother C,Kologorov V, Blake A.“GrabCut”:Interactive foreground extraction using iterated graph cuts[C]∥Proc of the ACM SIGGRAPH Conference, 2004:309-314.

[8] Xu Qiu-ping, Guo Min, Wang Ya-rong. Fast image segmentation algorithm based on multiscale analysis and graph cuts[J]. Application Research of Computer, 2009,26(10):3989-3991.(in Chinese)

[9] Xu Qiu-ping, Guo Min, Wang Ya-rong. Fast color image segmentation based on watershed transform and graph cuts[J]. Computer Engineering, 2009,35(19):210-215.(in Chinese)

[10] Han S D, Tao W B, Wang D S, et al. Image segmentation based on grabcut framework integrating multiscale nonlinear structure tensor[J]. IEEE Transactions on Image Processing, 2009, 18(10):2289-2302.

[11] Han S D, Tao W B, Wu X L. Texture segmentation using independent-scale component-wise riemannian-covariance Gaussian mixture model in KL measure based multi-scale nonlinear structure tensor space[J]. Pattern Recognition, 2011,44(3):503-518.

[12] Han Shou-dong, Zhao Yong, Tao Wen-bing, et al. Gaussian super-pixel based fast image segmentation using Graph-Cuts[J]. Acta Automatica Sinica, 2011,37(1):11-20.(in Chinese)

[13] Ford L,Fulkerson D.Flows in networks[M] .New Jersey:Princeton University Press, 1962.

附中文参考文献：

[8] 徐秋平,郭敏,王亚荣.基于多尺度分析与图割的快速图像分割算法[J].计算机应用研究, 2009,26(10),3989-3991.

[9] 徐秋平,郭敏,王亚荣.基于分水岭变换和图割的彩色图像快速分割[J].计算机工程, 2009,35(19),210-215.

[12] 韩守东, 赵勇, 陶文兵, 等. 基于高斯超像素的快速Graph Cuts图像分割方法[J]. 自动化学报, 2011, 37(1):11-20.