第6卷第4期 智能系统学报 Vol.6 No.4 2011年8月 CAAI Transactions on Intelligent Systems Aug.2011 doi:10.3969/i.i8sn.1673-4785.2011.04.006 局部颜色模型的交互式Graph-Cut分割算法 郑加明，陈昭炯 (福州大学数学与计算机科学学院，福建福州350108) 摘要：由于目前大多数交互式Gph-Cut分割算法很难达到精确分割且实时交互的效果.对此，提出一种基于局部 颜色模型的改进算法.该算法利用Mea-Shif预分割，建立基于局部颜色模型的交互式分割框架，并将像素级的 Gph-Cut算法转化为基于区域的算法进行快速求解.预分割之后的区域保持了原有图像的结构，不仅提高了采用局 部颜色模型估计分布的准确性，而且基于区域Gph-Cut的算法明显降低了计算的复杂度.实验结果表明，改进后的 算法不仅保证了分割的精确性，而且还达到了实时交互. 关键词：Graph-Cut;交互式图像分割；Mean-Shit;实时交互性 中图分类号：TP391文献标识码：A文章编号：16734785(2011)04031806 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) Abstract: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 pro- posed 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 esti- mation 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. Keywords:Graph-Cut;interactive image segmentation;Mean-Shift;real time interactivity 交互式图像分割方法主要用于提取静态图像或 然而，大多数交互式Graph-Cut分割算法还很 视频序列中的前景目标，其目的是希望通过尽量少 难达到交互式分割所要求的快速精确分割的效果. 的用户交互，快速精确地提取出感兴趣的对象，该方 这主要由两方面原因造成的.一方面，由于图像的像 法在一定程度上解决了全自动分割存在的通用性差 素个数一般是海量的，因而基于像素级的Graph-Cut 和分割效果不精确等问题. 算法的计算量和储存量过大.为了解决此问题，可以 近年来，有关交互式图像分割的算法已越来越 通过对图像进行预分割来降低算法的计算复杂度， 多，如蛇形算法、交互式Graph-Cut分割算法2]、 如文献[4]提出的Lazy snapping算法，将图像进行 Grabcut3]和Lazy snapping4等.其中，交互式Graph- 分水岭过分割，建立基于区域的Graph-Cut算法，在 Cut分割算法将交互式图像分割转化为求解一个包 一定程度上实现了实时交互.但是采用分水岭过分 含区域和边界信息能量函数的最小化过程，很好地 割，对原有图像的结构会造成破坏，需要更多的交互 将图像的区域信息与边界信息结合起来，分割的效 以弥补过分割带来的错误，另一方面，采用全局颜色 果较为准确 模型不能反映图像的空间结构，对复杂图像分布的 估计不准确.如文献[36]提出的改进Graph-Cut算 收稿日期：20100605. 基金项目：国家自然科学基金资助项目(60805042)：福建省自然科学 法，都采用高斯混合模型(Gaussian mixture model, 基金资助项目(2010J01329). GMM)对前景和背景的颜色分布进行估计.采用高 通信作者：陈昭炯.E-mail:chenzj(@fau.edu.cm
第4期 郑加明，等：局部颜色模型的交互式Graph-Cut分割算法 ·319· 斯混合模型虽然比文献[2]采用直方图进行分布估 通常，R(:)用来反映像素x:颜色特征适合前景或 计要准确，却耗费了大量的时间，影响分割的速度. 者背景颜色分布的程度. 而且这种采用全局颜色模型的算法，很难反映图像 边界项B(X)用来刻画解X的边界信息，其定 的空间信息，不能准确估计复杂图像的分布， 义形式如下： 为了在保证分割效果精确的同时，提高交互式 B(X)=∑B(x,)8(x,). 分割的效率，提出一种基于局部颜色模型的交互式 (ij)eB Graph-Cut分割算法.新算法采用Mean-Shif对图像 式中：6(x:,)= 1,:≠9 B(x,)用来衡量 进行预分割，利用预分割之后的区域集来估计前景 10,otherwise. 和背景分布的候选局部颜色模型，并建立基于区域 像素x:与像素x的平滑程度 的Graph-Cut模型.由于Mean-Shif能够很好地分析 为了求解能量函数E(X)的最优解，Graph-Cut 具有多峰分布的特征空间)，因此所建立的候选局 算法在无向图G=的基础上构建源点s和 部颜色模型能够较好地估计出图像的分布.又由于 汇点t的s-t网络流图.源点、汇点与图G中的每个 Mean-Shi近分割考虑了图像的颜色特征和空间信 顶点由一条边相连，边的权重由R(x:)计算得到.图 息，分割后的区域能够很好地保持原有图像的结构， G中顶点邻接边的权重由B(x,x)计算得到. 因此采用基于区域的Graph-Cut模型，可以大大减 Graph-Cut算法利用最大流/最小割原理2]，通过求 少每次交互的计算量.而且在每次迭代时，前景和背 s-t网络流图中的最大流，解得能量的最小值，即最 景分布的模型可根据用户标记直接选取候选模型来 小割。 重新建立分布，进一步减少了交互的延迟时间.另 2改进的交互式Graph-Cut分割算法 外，还根据前景和背景局部颜色模型的重叠程度，计 算估计分布可能造成的错误率，自适应地调整模型 2.1基于局部颜色模型的能量函数构造 的参数.从实际检验的结果看，改进后的算法不仅保 局部颜色模型融合了原有图像的空间结构与颜 证了分割的精确性，还明显减少了交互延迟时间. 色信息，可以更好地估计复杂图像的分布.因此，采 用局部颜色模型对前景和背景的分布进行估计，构 交互式Graph-Cut分割框架 造基于局部颜色模型的能量函数. 1.1交互式图像分割的能量函数 利用Mean-Shif预分割来估计前景和背景分布 交互式图像分割问题实际上是一个二值标记组 的候选局部颜色模型.先对图像中所有个像素 合优化问题.通常，将一幅图像看作一个无向图G= {a=l,2,n经过Mean-Shi过滤，再合并相似区域 ,其中顶点集V对应所有的像素，边集E 和小区域，得到m个聚簇.这m个聚簇的集合就是 对应各个像素与相邻像素的邻接关系.二值标记组 图像分布的m个模式，也就是候选局部颜色模型 合优化问题的目标就是根据图G,按照一定原则，找 {C,}p=l,…m对于每一个像素名所属的局部颜色 到一个最优解X,解中每个顶点都标记上惟一的标 模型为L:={pla∈C。},对应的模式特征值为y:= 签（背景为“back”,前景为“fore”).最优解X可以 {M(p)la:∈C,}.接着，根据用户标记从候选局部颜 采用E(X)能量函数求得： 色模型{C,,=12,“,m中选取前景和背景颜色模型. E(X)=R(X)+AB(X). 设用户标记的g个前景种子集合为{F。},h个背景 式中：R(X)是用来反应区域信息的区域项能量， 种子集合为{B}.如果云∈{F},则候选局部颜色 B(X)是用来反应边界信息的边界项能量，区域项与 模型中的L:模型晋升为前景颜色模型.若晋升num 边界项的比重由参数入确定， (F)个局部颜色模型为前景颜色模型，将其定义为 1.2 Graph-Cut算法求最小化能量函数的过程 0e.同样，可以得到num(B)个局部颜色模型为背景 Graph-Cut算法需要用户采用基于笔画的交互 颜色模型，定义为Bg·则像素：属于前景和背景分 形式对前景和背景进行标记，被标记上的像素称为 布的概率为P(aI0p)和P(aI0a).当用户添加新的 前景或背景种子，并根据前景和背景种子估计前景 标记时，前景和背景分布的模型根据用户标记直接 和背景的颜色分布， 从候选模型中选取，不需要重新进行Mean-Shif分 区域项R(X)用来惩罚解X与观察数据不一致 割，提高了算法的效率. 的程度.一般可以将区域项定义为如下形式： 为了达到实时交互，将预分割后的区域作为图 R(X)=∑R(x). 的顶点，并在此基础上构造基于局部颜色模型的能 量函数.设基于区域的图结构为G=,其
·320 智能系统学报 第6卷 中顶点p的值为该区域的模式特征值M(p),若区 2.3改进算法的基本步骤 域中任一个像素与另一区域中某像素满足8邻域 采用候选局部颜色模型，并建立基于区域的交 关系，则这2个区域对应的顶点是相邻关系.本文所 互式Graph-Cut分割框架，算法的基本步骤如下. 定义的种子是指包含前景或背景种子的区域块.对 1)对输人图像进行Mean-Shit预分割，建立m 于误分割产生的错误结果，可以对局部区域进行基 个候选局部颜色模型{C,,=12,m预分割的参数 于像素的Graph-Cut分割.对此，将主要研究基于区 设置参考文献[7]所提供的数据.如果存在过多误 域的交互式Graph-Cut分割算法，构造基于局部颜 分割的效果（同一区域同时包含前景和背景），可以 色模型的能量函数如下： 通过调整参数诚少误分割带来的错误。 E(X)=u∑R()+A∑(x,x)6(x,) 2)用户采用基于笔画的交互方式对输入图像 e (iEE 进行前景和背景标记，产生前景和背景种子集合 (1) {F,和{B..根据用户标记从候选局部颜色模型 式中：以为自适应因子，由前景与背景颜色模型估计 {C,pl,2,m选取前景和背景颜色模型0p和0g 分布产生的错误率ρ确定，可定义为 3)将预分割后的区域作为图G的顶点，建立基 u= 1-p,p<; (2) 于区域的交互式Graph-Cut分割框架.计算顶点i与 10, otherwise. 前景和背景种子在颜色特征空间上的最短距离d 式中：δ为常量因子，P可根据贝叶斯分类的错误率 和d: 定义为 d=min‖M(i)-0rl, ∑P(M(p)I0g） ∑P(M(p)I8F p= 4=i9IM()-6.. num(F) num(B) 4)根据表1，计算3种类型顶点区域项的值.其 3 中，So（i)和St(i)区域值的计算方法为： 2.2利用最大流原理求解能量函数的最小值 Sm(i)=u·neigh(i)·P(il0r), 将能量函数(1)中的区域项和边界项能量映射 Set(i)=u·neigh(i)·P(il0g) 到s-t网络流图，并将图G中的顶点分为前景种子、 其中，顶点属于前景和背景的概率P(i1Op)和 背景种子和未确定区域3种类型.其中，未确定区域 P(0g)按照以下方法计算： 是指除了用户标记过的前景和背景种子外的其他区 d 域.顶点与源点s、汇点t连接的权重分别为R(xa) P(i1）=+d+1' 和R(xk).不同类型顶点，所对应的R(x)和 d R(xk)的值如表1所示.为了保证种子确定属于前 P(ila）=++1 景或者背景，L()必须大于顶点i邻接边权重的总 和.根据顶点i的邻接边条数neigh(i)不同，L(i)的 自适应因子4根据式(2)、(3)计算得到，常量因子8取 计算方法如下： 为0.8.同样，根据式(4)计算边界项的能量 L()=λneigh()+1. 5)通过最大流原理，求解能量函数(1)的最小 当顶点属于未确定区域，根据前景和背景分 值，求得分割结果 布计算顶点i区域项的值So(i)和S4(i).另外将 6)用户根据分割的结果，决定是否添加新的标 边界项能量定义为相邻顶点x:和x的权值： 记或者删除之前的标记.如果分割结果达到用户的 B(x）=exp- LM(i)-M》L2 要求，则算法结束，输出分割结果.如果用户仍然对 (4) 分割结果不满意，则添加新的标记，或者删除之前的 式中：σ为所有邻接边权重的平均值， 标记，并转到2). 表1区域项的值 通过基本流程可以看出，本文算法建立在基于 Table 1 Region term values 区域的交互式Graph-Cut分割框架上，计算量比基 顶点类型 R(xn） R(xat） 于像素的Graph-Cut算法大大减少.且在整个交互 过程只需要建立一次图像的分布模型，即候选局部 i属于前景种子 L() 0 颜色模型.这些都有利于分割算法满足实时交互. i属于背景种子 0 L() i属于未确定区域 S。(i) S(i) 3实验结果分析 为了验证改进算法的有效性，在2.20GHz
第4期 郑加明，等：局部颜色模型的交互式Graph-Cut分割算法 321 CPU,1GB内存的PC机上，通过Microsoft VC+6.0 3.2错误率及自适应情况 实现本文算法.利用Berkeley图像分割图库(ht- 为了验证改进后的算法也能达到分割效果精 tp://www.eecs.berkeley.edu/Research/Projects/CS/ 确，在用户标记一样的情况下，将本文算法与文献 vision/grouping/segbench/,)和文献[8]提供的测试 [2]算法的分割错误率进行比较分析.对分割图库 图库进行测试，从交互延迟时间、分割错误率及自适 的图像进行分割，分割错误率的对比结果如图1所 应情况分析算法的性能， 示，其具体的错误率见表3.最终统计出文献[2]算 3.1交互延迟时间对比 法的平均错误率为1.95%，而本文算法的平均错误 假设一幅图像的像素点个数为N,像素相邻关 率为1.01% 系对应的总边数为E,则采用像素级的Graph-Cut求 ☒文献2]算法涵木文算法 解所耗费的时间复杂度为O(NE2)9o.图像预处 理后的区域个数为m,边数为e,Mean-Shi算法预 处理时间为O(N2),交互延迟时间表示用户标记之 后Graph-Cut求解所耗费的时间，如果每次交互操 作都需要预处理，则交互延迟时间的复杂度为0 10 20 40 图像 (N2+me2).一般情况下，边数与顶点数的比例为常 数，则原算法的时间复杂度为0(E),新算法为0 图1分割的错误率对比 (N2+e3),即O(e3).由于预处理后所计算的顶点数 Fig.1 Comparison of error rates 和边数明显减少，与原算法的时间复杂度相比，新算 法的执行效率更高.当图像分辨率提高时，图像的像 素个数增加，但区域数不变，新算法的效率提高得更 显著.另外，本文算法一般只需要采用一次Mean- Shi分割就可完成预处理，进一步减少了交互过程 的计算量. 将本文算法的交互延迟时间与文献[2]及 Grabcut算法进行对比，3个算法所对应的延迟时间 如表2所示。 表2交互延迟时间对比 Table 2 Comparison of interactive lag time s 图像 文献[2] Grabeut 本文 143090 1.079 3.703 0.016 doll 1.891 3.563 0.015 GT01 2.547 6.531 0.031 GT19 4.141 7.703 0.047 65019 1.219 2.125 0.015 85048 1.141 2.297 0.002 carsten 3.828 8.031 0.156 227092 1.203 2.141 0.001 (a原图及川户标记 (b)文款12 (c本文 stone2 2.219 3.922 0.032 图2“shrinking bias'”现象对比(F和B对应前景和背 文献[2]算法和本文算法的用户交互形式是一 景标记) 样的，都是采用基于笔画的形式进行的.而Grabcut Fig.2 Comparison of the "shrinking bias"phenomenon 算法则先采用矩形框将分割对象框住，先自动迭代 Graph-Cut算法会产生“shrinking bias'”错误s] 地完成初步分割.这里Grabcut算法的交互延迟时 不能准确分割含细长对象的图像，影响分割的精确 间表示为初步分割的时间.通过以上对比实验，发现 性.对此，比较了文献[2]算法与本文算法对含有细 改进后的算法只需要很短的交互延迟时间，达到了 长对象图像的分割错误率.图2列举了其中的2组 实时交互的效果。 对比实验结果，可以看出本文算法可以在一定程度 上缓解“shrinking bias'”现象
·322 智能系统学报 第6卷 改进算法增加了自适应因子，可以适用于大部 举了各种不同形状和类型图像分割的结果.实验表 分图像的分割（其中本文入值设置为0.8）.图3列 明，本文算法可以自适应于各种不同类型的图像. a)p=0.01=0.99 (b)p=0.02=0.98 (c)p=0.19=0.8 (d)p=0.1254=0.875 (e)p0.5=0.5 (f)p=0.5=0.5 图3不同类型图像的分割结果 Fig 3 The segmentation results of different types of images 表3分割错误率对比 Table 3 Comparison of error rates % 图像文献[2] 本文 图像 文献[2]本文 图像 文献[2] 本文 图像 文献[2]本文 21077 1.91 0.71 208001 0.83 0.56 bool 2.41 0.96 person1 3.25 0.61 24077 1.83 1.39 209070 2.51 2.31 bush 1.91 1.46 person2 1.54 0.41 37073 3.49 1.60 227092 3.32 1.38 ceramic 1.36 1.11 person3 1.02 0.50 65019 0.47 1.04 271008 0.82 0.92 cross 1.24 1.24 person4 1.51 0.52 69020 4.51 1.68 304074 1.50 0.99 dol 0.54 0.43 person5 1.83 0.55 86016 0.37 0.44 326038 4.09 2.51 elefant 0.74 0.66 person6 0.71 0.71 106024 1.02 0.48 376043 2.56 1.12 flower 3.23 0.36 person7 0.52 0.34 124084 2.97 1.44 388016 1.67 0.93 fullmoon 0.20 0.01 person8 2.50 1.22 153077 6.03 3.14 bananal 1.78 1.33 grave 1.15 0.50 scissors 2.14 0.99 153093 1.54 1.01 banana2 1.97 1.26 llama 1.90 0.88 sheep 0.54 0.23 181079 5.12 1.34 banana3 2.55 1.19 memorial 1.95 1.75 stonel 0.40 0.23 1890803.48 1.28 book 3.01 1.30 music 1.33 1.10 stone2 0.56 0.24 4 结束语 进一步的改进 本文采用局部颜色模型对前景和背景颜色分布 参考文献： 进行估计，并建立了基于区域的交互式Graph-Cut [1]KASS M,WITKIN A,TERZOLPOULOS D.Snakes:active 分割的框架.实验表明这一改进是有效的，不仅可以 contour models[J].Interational Joumal of Computer Vi- 更好地估计颜色分布，保持了分割效果的精确性，而 sion,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-
第4期 郑加明，等：局部颜色模型的交互式Gaph-Cut分割算法 ·323 teractive foreground extraction using iterated graph cuts [9]YUNRI Y,BOYKOV,KOLMOGOROV V.An experimental [J].ACM Transactions on Graphics,2004,23(3):309- comparison of min-cut/max-flow algorithms for energy mini- 314. mization in vision[J].IEEE Transactions on Pattern Analy- [4]LI Yin,SUN Jian,TANG Chikeung,et al.Lazy snapping sis and Machine Intelligence,2004,26(9):1124-1137. [C]//Computer Graphics Proceedings,Annual Conference [10]KOLMOGOROV V,ZABIH R.What energy functions can Series(ACM SIGGRAPH).Los Angeles,USA,2004:303- be minimized via graph cuts[J].IEEE Transactions on 308. Pattern Analysis and Machine Intelligence,2004,26(2): [5]VICENTE A,KOLMOGOROV V,ROTHER C.Graph cut 147-159. based image segmentation with connectivity priors [C]/ 作者简介： Proceeding of IEEE Interational Conference on CVPR.S. 郑加明，男，1986年生，硕士研究 1.],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. 陈昭炯，女，1964年生，教授，主要 [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): 金项目，发表学术论文50余篇. 603619. [8]RHEMANN C,ROTHER C,WANG J.A perceptually mo- tivated online benchmark for image matting[C]//Proceed- ings of IEEE Intemational Conference on CVPR.2009: 1826-1833 2011第6届智能系统与知识工程国际会议(ISKE2011) 2011 International Conference on Intelligent Systems and Knowledge Engineering (ISKE 2011) 2011第6届智能系统与知识工程国际会议(ISKE2011)将于2011年12月15日~17日在上海召开.已 成功在06年上海、07年成都、08年厦门、09年成都、10年杭州召开.此次会议将由上海交通大学主办，加州 州立大学，西南交通大学，比利时核研究中心等协办.本次会议将征集有关智能系统、知识工程等领域的论 文，主要范围包括（但不限于）：智能计算，机器学习，模式识别，知识发现，模糊推理与概率推理，自然语言处 理，语音及图像处理及识别，知识管理，内容管理，多agent系统，新型智能计算（如分布式计算，云计算、服务 计算、普适计算等)，智能控制，智能系统与知识工程在工业、商务、医疗、科学及政务等领域的应用.所有被 录用的论文将被Ei Compendex与ISTP全文检索. 主要范围包括（但不限于）：智能计算，机器学习，模式识别，知识发现，模糊推理与概率推理，自然语言 处理，语音及图像处理及识别，知识管理，内容管理，多gt系统，新型智能计算（如分布式计算、云计算、服 务计算、普适计算等)，智能控制，智能系统与知识工程在工业、商务、医疗、科学及政务等领域的应用.所有 被录用的论文将被Ei Compendex与ISTP全文检索.部分优秀论文推荐到EI期刊发表.现在您提交论文后 20天左右，我们将给您发出是否录用的通知. Web site:http://iske2011.sjtu.edu.cn