局部颜色模型的交互式Graph－Cut分割算法

郑加明，陈昭炯

(福州大学数学与计算机科学学院，福建福州 350108)

局部颜色模型的交互式Graph－Cut分割算法

郑加明，陈昭炯

(福州大学数学与计算机科学学院，福建福州 350108)

由于目前大多数交互式Graph－Cut分割算法很难达到精确分割且实时交互的效果.对此，提出一种基于局部颜色模型的改进算法.该算法利用Mean－Shift预分割，建立基于局部颜色模型的交互式分割框架，并将像素级的Graph－Cut算法转化为基于区域的算法进行快速求解.预分割之后的区域保持了原有图像的结构，不仅提高了采用局部颜色模型估计分布的准确性，而且基于区域Graph－Cut的算法明显降低了计算的复杂度.实验结果表明，改进后的算法不仅保证了分割的精确性，而且还达到了实时交互.

Graph－Cut;交互式图像分割;Mean－Shift;实时交互性

交互式图像分割方法主要用于提取静态图像或视频序列中的前景目标，其目的是希望通过尽量少的用户交互，快速精确地提取出感兴趣的对象，该方法在一定程度上解决了全自动分割存在的通用性差和分割效果不精确等问题.

近年来，有关交互式图像分割的算法已越来越多，如蛇形算法［1］、交互式 Graph－Cut分割算法［2］、Grabcut［3］和 Lazy snapping［4］等.其中，交互式 Graph－Cut分割算法将交互式图像分割转化为求解一个包含区域和边界信息能量函数的最小化过程，很好地将图像的区域信息与边界信息结合起来，分割的效果较为准确.

然而，大多数交互式 Graph－Cut分割算法还很难达到交互式分割所要求的快速精确分割的效果.这主要由两方面原因造成的.一方面，由于图像的像素个数一般是海量的，因而基于像素级的Graph－Cut算法的计算量和储存量过大.为了解决此问题，可以通过对图像进行预分割来降低算法的计算复杂度.如文献［4］提出的Lazy snapping算法，将图像进行分水岭过分割，建立基于区域的Graph－Cut算法，在一定程度上实现了实时交互.但是采用分水岭过分割，对原有图像的结构会造成破坏，需要更多的交互以弥补过分割带来的错误，另一方面，采用全局颜色模型不能反映图像的空间结构，对复杂图像分布的估计不准确.如文献［3－6］提出的改进 Graph－Cut算法，都采用高斯混合模型(Gaussian mixture model，GMM)对前景和背景的颜色分布进行估计.采用高斯混合模型虽然比文献［2］采用直方图进行分布估计要准确，却耗费了大量的时间，影响分割的速度.而且这种采用全局颜色模型的算法，很难反映图像的空间信息，不能准确估计复杂图像的分布.

为了在保证分割效果精确的同时，提高交互式分割的效率，提出一种基于局部颜色模型的交互式Graph－Cut分割算法.新算法采用 Mean－Shift对图像进行预分割，利用预分割之后的区域集来估计前景和背景分布的候选局部颜色模型，并建立基于区域的 Graph－Cut模型.由于 Mean－Shift能够很好地分析具有多峰分布的特征空间［7］，因此所建立的候选局部颜色模型能够较好地估计出图像的分布.又由于Mean－Shift分割考虑了图像的颜色特征和空间信息，分割后的区域能够很好地保持原有图像的结构，因此采用基于区域的Graph－Cut模型，可以大大减少每次交互的计算量.而且在每次迭代时，前景和背景分布的模型可根据用户标记直接选取候选模型来重新建立分布，进一步减少了交互的延迟时间.另外，还根据前景和背景局部颜色模型的重叠程度，计算估计分布可能造成的错误率，自适应地调整模型的参数.从实际检验的结果看，改进后的算法不仅保证了分割的精确性，还明显减少了交互延迟时间.

1 交互式Graph－Cut分割框架

1.1 交互式图像分割的能量函数

交互式图像分割问题实际上是一个二值标记组合优化问题.通常，将一幅图像看作一个无向图G=＜V，E＞，其中顶点集V对应所有的像素，边集E对应各个像素与相邻像素的邻接关系.二值标记组合优化问题的目标就是根据图G，按照一定原则，找到一个最优解X，解中每个顶点都标记上惟一的标签(背景为“back”，前景为“fore”).最优解X可以采用E(X)能量函数求得:

式中:R(X)是用来反应区域信息的区域项能量，B(X)是用来反应边界信息的边界项能量，区域项与边界项的比重由参数λ确定.

1.2 Graph－Cut算法求最小化能量函数的过程

Graph－Cut算法需要用户采用基于笔画的交互形式对前景和背景进行标记，被标记上的像素称为前景或背景种子，并根据前景和背景种子估计前景和背景的颜色分布.

区域项R(X)用来惩罚解X与观察数据不一致的程度.一般可以将区域项定义为如下形式:通常，R(xi)用来反映像素xi颜色特征适合前景或者背景颜色分布的程度.

边界项B(X)用来刻画解X的边界信息，其定义形式如下:

为了求解能量函数E(X)的最优解，Graph－Cut算法在无向图G=＜V，E＞的基础上构建源点s和汇点t的s－t网络流图.源点、汇点与图G中的每个顶点由一条边相连，边的权重由R(xi)计算得到.图G中顶点邻接边的权重由B(xi，xj)计算得到.Graph－Cut算法利用最大流/最小割原理［2］，通过求s－t网络流图中的最大流，解得能量的最小值，即最小割.

2 改进的交互式Graph－Cut分割算法

2.1 基于局部颜色模型的能量函数构造

局部颜色模型融合了原有图像的空间结构与颜色信息，可以更好地估计复杂图像的分布.因此，采用局部颜色模型对前景和背景的分布进行估计，构造基于局部颜色模型的能量函数.

利用Mean－Shift预分割来估计前景和背景分布的候选局部颜色模型.先对图像中所有n个像素{zi}i=1，2，…，n经过 Mean－Shift过滤，再合并相似区域和小区域，得到m个聚簇.这m个聚簇的集合就是图像分布的m个模式，也就是候选局部颜色模型{Cp}p=1，2，…，m.对于每一个像素zi所属的局部颜色模型为Li={p|zi∈Cp}，对应的模式特征值为yi={M(p)|zi∈Cp}.接着，根据用户标记从候选局部颜色模型{Cp}p=1，2，…，m中选取前景和背景颜色模型.设用户标记的g个前景种子集合为{Fg}，h个背景种子集合为{Bh}.如果zi∈ {Fg}，则候选局部颜色模型中的Li模型晋升为前景颜色模型.若晋升num(F)个局部颜色模型为前景颜色模型，将其定义为θF.同样，可以得到num(B)个局部颜色模型为背景颜色模型，定义为θB.则像素zi属于前景和背景分布的概率为P(zi|θF)和P(zi|θB).当用户添加新的标记时，前景和背景分布的模型根据用户标记直接从候选模型中选取，不需要重新进行Mean－Shift分割，提高了算法的效率.

为了达到实时交互，将预分割后的区域作为图的顶点，并在此基础上构造基于局部颜色模型的能量函数.设基于区域的图结构为G'=＜V'，E'＞，其中顶点p的值为该区域的模式特征值M(p)，若区域中任一个像素与另一区域中某像素满足8－邻域关系，则这2个区域对应的顶点是相邻关系.本文所定义的种子是指包含前景或背景种子的区域块.对于误分割产生的错误结果，可以对局部区域进行基于像素的Graph－Cut分割.对此，将主要研究基于区域的交互式Graph－Cut分割算法，构造基于局部颜色模型的能量函数如下:

式中:μ为自适应因子，由前景与背景颜色模型估计分布产生的错误率ρ确定，可定义为

式中:δ为常量因子，ρ可根据贝叶斯分类的错误率定义为

2.2 利用最大流原理求解能量函数的最小值

将能量函数(1)中的区域项和边界项能量映射到s－t网络流图，并将图G'中的顶点分为前景种子、背景种子和未确定区域3种类型.其中，未确定区域是指除了用户标记过的前景和背景种子外的其他区域.顶点与源点s、汇点t连接的权重分别为R(xfore)和R(xback).不同类型顶点，所对应的R(xfore)和R(xback)的值如表1所示.为了保证种子确定属于前景或者背景，L(i)必须大于顶点i邻接边权重的总和.根据顶点i的邻接边条数neigh(i)不同，L(i)的计算方法如下:

当顶点i属于未确定区域，根据前景和背景分布计算顶点i区域项的值Sfore(i)和Sback(i).另外将边界项能量定义为相邻顶点xi和xj的权值:

式中:σ为所有邻接边权重的平均值.

表1 区域项的值Table 1 Region term values

2.3 改进算法的基本步骤

采用候选局部颜色模型，并建立基于区域的交互式Graph－Cut分割框架，算法的基本步骤如下.

1)对输入图像进行Mean－Shift预分割，建立m个候选局部颜色模型{Cp}p=1，2，…，m.预分割的参数设置参考文献［7］所提供的数据.如果存在过多误分割的效果(同一区域同时包含前景和背景)，可以通过调整参数减少误分割带来的错误.

2)用户采用基于笔画的交互方式对输入图像进行前景和背景标记，产生前景和背景种子集合{Fg}和{Bh}.根据用户标记从候选局部颜色模型{Cp}p=1，2，…，m选取前景和背景颜色模型 θF和 θB.

3)将预分割后的区域作为图G＇的顶点，建立基于区域的交互式Graph－Cut分割框架.计算顶点i与前景和背景种子在颜色特征空间上的最短距离和

4)根据表1，计算3种类型顶点区域项的值.其中，Sfore(i)和Sback(i)区域值的计算方法为:

其中，顶点属于前景和背景的概率P(i|θF)和P(i|θB)按照以下方法计算:

自适应因子μ根据式(2)、(3)计算得到，常量因子δ取为0.8.同样，根据式(4)计算边界项的能量.

5)通过最大流原理，求解能量函数(1)的最小值，求得分割结果.

6)用户根据分割的结果，决定是否添加新的标记或者删除之前的标记.如果分割结果达到用户的要求，则算法结束，输出分割结果.如果用户仍然对分割结果不满意，则添加新的标记，或者删除之前的标记，并转到2).

通过基本流程可以看出，本文算法建立在基于区域的交互式Graph－Cut分割框架上，计算量比基于像素的Graph－Cut算法大大减少.且在整个交互过程只需要建立一次图像的分布模型，即候选局部颜色模型.这些都有利于分割算法满足实时交互.

3 实验结果分析

为了验证改进算法的有效性，在2.20 GHz CPU，1 GB内存的PC机上，通过Microsoft VC++6.0实现本文算法.利用 Berkeley图像分割图库(http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/)和文献［8］提供的测试图库进行测试，从交互延迟时间、分割错误率及自适应情况分析算法的性能.

3.1 交互延迟时间对比

假设一幅图像的像素点个数为N，像素相邻关系对应的总边数为E，则采用像素级的Graph－Cut求解所耗费的时间复杂度为O(NE2)［9－10］.图像预处理后的区域个数为m，边数为e，Mean－Shift算法预处理时间为O(N2).交互延迟时间表示用户标记之后Graph－Cut求解所耗费的时间，如果每次交互操作都需要预处理，则交互延迟时间的复杂度为O(N2+me2).一般情况下，边数与顶点数的比例为常数，则原算法的时间复杂度为O(E3)，新算法为O(N2+e3)，即O(e3).由于预处理后所计算的顶点数和边数明显减少，与原算法的时间复杂度相比，新算法的执行效率更高.当图像分辨率提高时，图像的像素个数增加，但区域数不变，新算法的效率提高得更显著.另外，本文算法一般只需要采用一次Mean－Shift分割就可完成预处理，进一步减少了交互过程的计算量.

将本文算法的交互延迟时间与文献［2］及Grabcut算法进行对比，3个算法所对应的延迟时间如表2所示.

表2 交互延迟时间对比Table 2 Comparison of interactive lag time s

文献［2］算法和本文算法的用户交互形式是一样的，都是采用基于笔画的形式进行的.而Grabcut算法则先采用矩形框将分割对象框住，先自动迭代地完成初步分割.这里Grabcut算法的交互延迟时间表示为初步分割的时间.通过以上对比实验，发现改进后的算法只需要很短的交互延迟时间，达到了实时交互的效果.

3.2 错误率及自适应情况

为了验证改进后的算法也能达到分割效果精确，在用户标记一样的情况下，将本文算法与文献［2］算法的分割错误率进行比较分析.对分割图库的图像进行分割，分割错误率的对比结果如图1所示，其具体的错误率见表3.最终统计出文献［2］算法的平均错误率为1.95%，而本文算法的平均错误率为1.01%.

图1 分割的错误率对比Fig.1 Comparison of error rates

图2 “shrinking bias”现象对比(F和B对应前景和背景标记)Fig.2 Comparison of the“shrinking bias”phenomenon

Graph－Cut算法会产生“shrinking bias”错误［5］，不能准确分割含细长对象的图像，影响分割的精确性.对此，比较了文献［2］算法与本文算法对含有细长对象图像的分割错误率.图2列举了其中的2组对比实验结果，可以看出本文算法可以在一定程度上缓解“shrinking bias”现象.

改进算法增加了自适应因子，可以适用于大部分图像的分割(其中本文λ值设置为0.8).图3列举了各种不同形状和类型图像分割的结果.实验表明，本文算法可以自适应于各种不同类型的图像.

图3 不同类型图像的分割结果Fig 3 The segmentation results of different types of images

表3 分割错误率对比Table 3 Comparison of error rates %

4 结束语

本文采用局部颜色模型对前景和背景颜色分布进行估计，并建立了基于区域的交互式Graph－Cut分割的框架.实验表明这一改进是有效的，不仅可以更好地估计颜色分布，保持了分割效果的精确性，而且每次迭代不需要重新建立分布，减少了交互延迟时间，达到了实时交互的效果.但是当前景与背景存在过多相似颜色时，与其他算法一样，本文算法也会产生比较大的分割错误率，今后将针对这一问题做进一步的改进.

［1］KASS M，WITKIN A，TERZOLPOULOS D.Snakes:active contour models［J］.International Journal of Computer Vision，1988，1(4):321－331.

［2］YUNRI Y，JOLLY B M P.Interactive graph cuts for optimal boundary and region segmentation of objects in N－D images［C］//Proceedings of International Conference on Computer Vision.Vancouver，Canada，2001，1:105－112.

［3］ROTHER C，KOLMOGOROV V，BLAKE A.Grabcut－in－teractive foreground extraction using iterated graph cuts［J］.ACM Transactions on Graphics，2004，23(3):309－314.

［4］LI Yin，SUN Jian，TANG Chikeung，et al.Lazy snapping［C］//Computer Graphics Proceedings，Annual Conference Series(ACM SIGGRAPH).Los Angeles，USA，2004:303－308.

［5］VICENTE A，KOLMOGOROV V，ROTHER C.Graph cut based image segmentation with connectivity priors［C］//Proceeding of IEEE International Conference on CVPR.［S.l.］，2008:1－8.

［6］刘陈，李凤霞，张艳.图割与泛形信息结合［J］.计算机辅助设计与图形学学报，2009，21(12):1753－1760.

LIU Chen，LI Fengxia，ZHANG Yan.An interactive object cutout algorithm based on graph－cut and generalized shape prior［J］.Journal of Computer－aided Design ＆ Computer Graphics，2009，21(12):1753－1760.

［7］COMANICIU D，MEER P.Mean shift:a robust approach toward feature space analysis［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(5):603－619.

［8］RHEMANN C，ROTHER C，WANG J.A perceptually motivated online benchmark for image matting［C］//Proceedings of IEEE International Conference on CVPR.2009:1826－1833.

［9］YUNRI Y，BOYKOV，KOLMOGOROV V.An experimental comparison of min－cut/max－flow algorithms for energy minimization in vision［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(9):1124－1137.

［10］KOLMOGOROV V，ZABIH R.What energy functions can be minimized via graph cuts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26(2):147－159.

郑加明，男，1986年生，硕士研究生，主要研究方向为图形图像处理.

陈昭炯，女，1964年生，教授，主要研究方向为图形图像处理与智能算法设计等，主持及参与多项国家和省级基金项目，发表学术论文50余篇.

Interactive Graph-Cut for image segmentation using local color models

ZHENG Jiaming，CHEN Zhaojiong
(College of Mathematics and Computer Science，Fuzhou University，Fuzhou 350108，China)

Most interactive segmentation algorithms based on Graph－Cut do not usually lend themselves to real time applications with accurate segmentation.In this paper，an improved algorithm using local color models was proposed to deal with the problem.Using Mean－Shift technology，the proposed algorithm built an interactive image segmentation framework based on local color models.A Graph－Cut algorithm was then applied to the pre－segmented regions instead of image pixels.The pre－segmented regions preserve the image structure，which improves the estimation accuracy of distribution based on local color models and dramatically reduces the computational complexity.Experimental results show that the proposed algorithm has good real time interactivity with accurate segmentation.

Graph－Cut;interactive image segmentation;Mean－Shift;real time interactivity

TP391

A

1673－4785(2011)04－0318－06

10.3969/j.issn.1673－4785.2011.04.006

2010－06－05.

国家自然科学基金资助项目(60805042);福建省自然科学基金资助项目(2010J01329).

陈昭炯.E－mail:chenzj@fzu.edu.cn.