一种改进的One-Cut交互式图像分割算法*

2018-07-05唐晶磊

计算机工程与科学 2018年6期

王栋，唐晶磊

(西北农林科技大学信息工程学院,陕西西安 712100)

1 引言

图像分割是图像处理到图像分析的关键步骤[1]。图像分割是将一幅图像划分成互不相交(重叠)的一些区域，而每个区域内的像素具有大体相似的性质(灰度、彩色)或结构(对于纹理图像)[2]。常用的图像分割方法主要有基于阈值的分割方法、基于边缘的分割方法[3]、基于区域的分割方法[4]、基于分水岭的分割方法和基于能量的分割方法等[5]。但是，基于区域的分割方法常面临分割速度过慢的问题，而基于阈值、边缘或分水岭的分割方法却存在对图像噪声敏感的缺点。近年来，以数学模型中的能量函数作为基本结构的分割算法独树一帜，并以其在分割精度及分割效率等方面的优势，日趋成为一种广泛使用的分割算法[6]。

在基于能量的图像分割方法中，图割算法是一种基于图论的组合优化技术，可用来最小化图像分割中的能量函数问题。它首先建立能量函数，并将一幅图像转化为一个网络图，然后利用最大流/最小割[7]算法对网络图进行切割，得到网络图的最小割，最后将网络图映射为图像分割结果[8]。

依据先验知识不同可将图割算法分为两类[9]。(1)假设已知表观模型，对图像进行分割的算法。(2)假设已知表观模型的类型，需估算模型参数，并对图像进行分割的算法。

第一类算法所用模型结合了空间正则项和表观对数似然函数。这类问题相对简单，而且存在大量取得全局最优解的方法。表观模型对于常用的图割算法是非常重要的。最基本的目标分割能量模型[10,11]结合边界正则项|∂S|和表观对数似然函数。本文使用θ1和θ0表示前景和背景的颜色分布。用I表示待分割图像，则第p个像素点Ip属于类别Sp的概率为Pr(Ip|θSp)。表观模型如式(1)和式(2)所示。

(1)

|∂S|=∑{p,q}∈Mωpq|sp-sq|

(2)

其中,Ω为图像中所有像素的集合，sp为标记分割结果S⊂Ω的二值指示变量，M为图像中所有相邻像素点之间边的集合。利用此能量项的优势在于，可通过一些成熟的算法如graph cut[12]、continuous relaxations[13,14]等求得它的全局最优解。

但在实际应用中，很难获得表观模型参数θ1和θ0等先验知识。因此，常将模型参数作为第二类算法所用模型[15 - 17]的附加变量，如式(3)所示。

(3)

交互式分割GrabCut算法[17]就用到此类模型。GrabCut算法根据用户输入的包围盒初始化模型参数θ1和θ0。通过迭代以下两个步骤可得该模型全局最优解[17]。首先，固定参数θ1和θ0，并最优化目标函数，如利用graph cut算法来最优化目标函数(1)[18]。然后，固定分割结果S，并最优化模型参数θ1和θ0。但是,这类模型的求解是一个NP-hard[19]问题，即随着图中节点数的增多，问题的求解将变得费时，故对较大的图像进行分割时，会导致图像分割速度变慢[20]。同时，随着颜色区间数目的增加，GrabCut算法对局部最优解的敏感性会降低，导致图像分割精度下降。国内外学者已经在该领域做出了大量的研究。

胡志立等[21]利用四叉树分解算法对图像进行划分区域，使得区域内的分块相似度较高，从而简化网络图的结构；同时，使用分块内像素点的均值，估算高斯混合模型中的参数，从而降低问题复杂度，提高图像分割的效率。时永刚等[22]提出了一种基于图割和水平集方法的图像分割方法。首先选取对比度和清晰度较高的初始参考图像；其次使用霍夫森林算法检测目标区域，并对前景、背景进行均值聚类，从而估计直方图分布；再次获取图割模型能量函数，分割出目标整体；最后通过形态学处理得到相邻图像目标候选区域，并重复上述分割。戴庆焰等[23]改进简单线性迭代聚类算法，并利用该算法分割图像，得到超像素图像；然后以超像素为基本单元，构建能量函数；最后利用Graph cut算法进行分割。这些方法都是基于GrabCut算法深入研究的，取得了较好分割效果的同时提高了分割效率，但这些方法都面临NP-hard问题。

在图割算法中，由于GrabCut算法在求取能量函数全局最优解时会出现NP-hard问题，致使其应用受到一定的限制。而One-Cut算法[9]利用一种新的距离项(L1距离)表示目标和背景表观模型间的相似度，可用此能量项避免NP-hard问题。即One-Cut算法不需要反复迭代，通过一次图割就可以求得全局最优解。并且通过改进网络图的结构，提升求解效率的同时，提高了分割准确率[18]。在部分图像分割应用场景中，One-Cut分割算法非常有效地替代了基于块坐标下降的近似迭代优化算法。

因此，本文针对GrabCut算法出现NP-hard问题、图像分割效率低的问题，以经典的One-Cut的算法为基础，改进表观重叠惩罚项，并结合直方图加速技术[24]，优化网络图的结构，对One-Cut算法进行改进，提高图像分割的效率及精度。

2 One-Cut算法

当表观模型θ1和θ0由颜色直方图来表示时，式(3)的最小解等价于仅含S的能量项E(S)的最小解。能量项E(S)如式(4)所示：

(4)

(5)

2.1 交互式分割中的One-Cut算法

(6)

|∂S|=∑ωpq|sp-sq|

(7)

(8)

其中,ΔI2表示像素点p和q的颜色欧氏距离，δ2取所有像素点的ΔI2的平均值，而E(S)的最优解则利用graph cut算法一次迭代即可求出。

2.2 表观重叠惩罚项

One-Cut算法中表观重叠惩罚项如式(9)所示。

(9)

为阐述表观重叠惩罚项和网络图的对应关系，将式(9)中表观重叠惩罚项缩小一半，从而改写为式(10)。如式(6)所示，能量函数中表观重叠项存在可调整系数β，故式(10)与原表观重叠惩罚项等价。

(10)

现有的One-Cut网络图是以原GrabCut网络图为基础，再添加k个辅助节点，且每个辅助节点与它相应的区间中所有像素相连接。以此方式将每个像素点与它相应的辅助节点连接在一起。式(10)的详细网络图结构如图1所示。

Figure 1 Network structure of the One-Cut appearance overlap penalty term图1 One-Cut的表观重叠惩罚项的网络图结构

图1中顶点v1,v2,…,vnk分别代表区间k中的所有像素，顶点Ak为额外添加的辅助节点。它们之间用无向边连接，每条边的最大流量即为表观重叠惩罚项系数β>0。

3 One-Cut算法的改进

大数据时代已经到来，云计算、物联网、大量社交网络的兴起使我们社会的图像数据种类和数量极速增长，显著增加了图像处理的任务量，因此提高图像分割的效率也越来越重要。

One-Cut算法已经取得了显著的成就，甚至在一些公开的数据集上的分割精度已经达到了国际上最先进的水平，但它仍然面临颜色信息利用不合理、网络图结构不合理、存在冗余计算、网络图中过多权重单一的边和网络图中节点过多等问题，这些问题导致图像分割效率和精度低。因此，优化该算法的求解过程，即优化网络图的构建，对提高该算法的分割效率有着重要的意义。

针对于图像分割效率低的问题，利用改进表观重叠惩罚项方法，结合颜色直方图加速技术，实现对表观重叠惩罚项的优化和网络图的构建的改进，从而达到提高分割效率及分割精度的目的。

3.1 表观重叠惩罚项的改进

网络图的优化和表观重叠惩罚项的改进是相互对应的。令K表示颜色区间的总数。同时，由于R⊆S，表观重叠项的改进的理论推导过程如式(11)所示。

(11)

3.2 网络图的结构的改进

Figure 2 Network structure of the improved appearance overlap penalty term图2 改进后的表观重叠惩罚项的网络图结构

3.3 最大流最小割算法求解能量函数

最大流最小割算法是一种经典组合优化技术。在现实或抽象领域中都可使用最大流最小割算法。在现实中，可利用最大流最小割算法计算通信网络中任意两点间的最大流量。在抽象领域中，可利用最大流最小割算法快速地求解最优化问题。如可以使用最大流最小割算法求解图割算法中网络图的最小割。

由式(6)和式(11)，可得最大流最小割算法求解的能量函数，如式(12)所示。

(12)

Figure 3 Segmentataion of the network图3 网络图分割

图3中，源点M和汇点T分别位于图中顶端和低端。中间椭圆代表包围盒内像素点。图3a为构建完成的网络图，可使用最大流最小割算法计算该网络图中最小割。图3b中加粗曲线为该网络图的最小割。根据该最小割，可将图像中所有像素分为前景或背景。

4 实验结果及分析

4.1 实验条件及流程

为验证改进后的One-Cut算法的分割精度及其效率，实验选取One-Cut[9]实验所用数据集为原始图像，分别用GrabCut算法、One-Cut算法和本文算法进行分割。本实验在Windows 10操作系统和Visual Studio 2015平台下，结合OpenCV 3.1库，在i5-4200u处理器、4 GB内存的笔记本PC上完成。

实验流程如图4所示。

Figure 4 Flow chart of the experiment图4 实验流程图

4.2 实验结果

图5为利用GrabCut算法、One-Cut算法和改进后的One-Cut算法进行分割的部分结果。部分示例图像如图5所示。图5a列为原始图像，白色矩形框为用户交互包围盒。图像中包围盒内的区域为区域R。图5b～图5d列分别为GrabCut算法、One-Cut算法和本文算法的最终分割结果。

Figure 5 Segmenttation results of the three algorithms图5 三种算法的分割结果

为评价分割结果，采用分割误差(Error)、准确率(Precision)、召回率(Recall)[26]三个客观评价指标和平均主观质量分数[27]对比GrabCut算法、One-Cut算法和本文算法。主观评价法采用平均主观评价法。由选自不同背景的30名观察者为图像分割的质量打分，最低为1分，最高为7分。部分实验数据(共列出14幅图像)及其平均值，如表1所示。

由表1可以得到，本文算法的最小分割误差、最高准确率、最高召回率和最高平均主观质量分数为0.64%、99.33%、99.98%和6.567，平均分割误差、平均准确率、平均召回率和平均主观质量分数的均值分别为6.88%、94.51%、94.54%和5.712。

GrabCut算法的平均分割误差、平均准确率、平均召回率和平均主观质量分数的均值分别为8.88%、92.40%、92.99%和5.376。One-Cut算法的平均分割误差、平均准确率、平均召回率和平均主观质量分数的均值分别为8.04%、93.16%、94.06%和5.659 5。

本文算法的平均误差比GrabCut算法的平均误差低2%，比One-Cut算法的平均误差低1.16%。本文算法的平均准确率比GrabCut算法的平均准确率提升2.11%，比One-Cut算法的平均准确率提升1.35%。本文算法的平均召回率比GrabCut算法的平均召回率提升1.55%，比One-Cut算法的平均召回率提升0.48%。本文算法的平均主观质量分数均值比GrabCut算法的平均主观质量分数均值高0.366，比One-Cut算法的平均主观质量分数均值高0.052 5。实验结果说明，降低网络图的复杂度有利于提高图像分割的精度。

Table 1 Segmentation experiment results表1 分割实验结果

三种算法的分割效率如表2所示。由表2可以看出，利用本文算法进行图像分割的最短运行时间为275.21 ms。本文算法、GrabCut算法和One-Cut算法的平均运行时间分别为569.73 ms、11 539.98 ms和1 308.13 ms。本文算法的运行效率分别为One-Cut算法和GrabCut算法运行效率的2.3倍和20.26倍。本文算法在部分图像上的运行效率最高达到了One-Cut算法的运行效率的3.52倍。实验数据表明，通过使用One-Cut算法的L1相似度、改进表观重叠惩罚项目和直方图加速技术，能够显著增加图像分割的效率。

Table 2 Segmentation efficiency表2 分割效率

4.3 实验结果分析

假定所有网络图中每条边的长度都为1，相对于One-Cut算法的网络图结构，本文算法网络图结构中源点M到汇点T的路径长度短，节点和边较少,即网络图的复杂度较低。另外，由于最大流最小割算法属于近似求解算法，因此最大流最小割算法对本文算法的网络图求解更加精确。

由表1和表2可以看出，在相同的数据集和实验条件下，One-Cut算法的分割精度及分割效率明显优于GrabCut算法。且由于One-Cut算法采用了L1距离项，避免了NP-hard问题，One-Cut算法运行效率较GrabCut算法高出了7.82倍。

本文算法在One-Cut算法的基础上，进一步改进了表观重叠惩罚项的求解，优化了网络图结构。在图像处理的过程中，其运行时间均小于GrabCut算法和One-Cut算法，节省时间的最高比例超过了70%。依据经验，包围盒占图像的比例越小，本文算法优化的节点越多，削减的冗余计算也就越多，即分割效率越高。

对于图5中的第四幅图像，无论GrabCut算法、One-Cut算法，还是本文算法，其分割结果均不理想。主要原因是图中像素颜色集中于墨绿色，前景目标与背景的颜色区域重叠较为严重，导致欠分割和召回率低的现象。因此，对于此类前景目标与背景的颜色区域重叠较为严重的图像，仅靠颜色和边缘信息会难以准确实现前景目标的分割。准确分割该类图像还需要借助于纹理、结构特性等信息。

5 结束语

为克服GrabCut算法分割效率和精度低的问题，本文以One-Cut算法为基础，通过改进表观重叠惩罚项，结合直方图加速技术，对One-Cut算法进行了改进，避免了GrabCut中的NP-hard问题，优化了表观重叠惩罚项，改进了网络图的构建。实验结果表明，改进后的One-Cut算法在分割效率、精度上均优于GrabCut算法和One-Cut算法。

GrabCut算法、One-Cut算法以及本文算法都仅利用相邻像素间的边缘信息和颜色信息，若能充分挖掘图像像素间的距离信息，并合理地结合超像素分割，将会进一步提升本算法的分割效率或精度。

[1] Li Xiao-hong,Wu Jing-fei,Zhang Guo-fu,et al.New color image segmentation based on watershed and region merging[J].Journal of Electronic Measurement and Instrument,2013,27(3):247-252.(in Chinese)

[2] Zhao Rong-chun,Zhao Zhong-ming,Zhao Xin-bo.Digital image processing and analysis[M].Beijing:Tsinghua University Press,2013.(in Chinese)

[3] Wang Dan-dan,Xu Yue,Song Huai-bo,et al.Fusion ofK-means and Ncut algorithm to realize segmentation and reconstruction of two overlapped apples without blocking by branches and leaves[J].Transactions of the Chinese Society of Agricultural Engineering,2015,31(10):227-234.(in Chinese)

[4] Xia Yong,Ji Ze-xuan,Zhang Yan-ning.Brain MRI image segmentation based on learning local variational Gaussian mixture models[J].Neurocomputing,2016,204:189-197.

[5] Lin Qiang, Dong Ping,Lin Jia-yu.A survey on graph cut techniques [J].Microprocessors,2015,36(1):35-39.(in Chinese)

[6] Liu Xian-tao.The image processing technology based on energy minimization model[D].Nanchang:Jiangxi University of Science and Technology,2014.(in Chinese)

[7] Yan Zi-heng.Research and applications for the problem of minimum cut/maximum flow algorithms[D].Nanjing:Nanjing University of Posts and Telecommunications,2016.(in Chinese)

[8] Zhang Shao-juan,Zou Jian-cheng.Summary of graph cut [J].Journal of North China University of Technology,2010,22(3):10-15.(in Chinese)

[9] Tang Meng,Gorelick L,Veksler O,et al.Grabcut in one cut[C]∥Proc of the IEEE International Conference on Computer Vision,2013:1769-1776.

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

[11] Unger M,Pock T,Trobin W,et al.TVSeg-interactive total variation based image segmentation[C]∥Proc of British Machine Vision Association Conference,2008:44-46.

[12] Boykov Y,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.

[13] Chan T F,Esedoglu S,Nikolova M.Algorithms for finding global minimizers of image segmentation and denoising models[J].SIAM Journal on Applied Mathematics,2006,66(5):1632-1648.

[14] Pock T,Cremers D,Bischof H,et al.Global solutions of variational models with convex regularization[J].SIAM Journal on Imaging Sciences,2010,3(4):1122-1145.

[15] Chan T F,Vese L A.Active contours without edges[J].IEEE Transactions on Image Processing,2001,10(2):266-277.

[16] Zhu Song-chun, Yuille A.Region competition:Unifying snakes,region growing,and Bayes/MDL for multiband image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(9):884-900.

[17] Rother C, Kolmogorov V,Blake A.Grabcut:Interactive foreground extraction using iterated graph cuts[J].ACM Transactions on Graphics (TOG),2004,23(3):309-314.

[18] Sun Wei.Research on interactive image segmentation based on graph cut[D].Xi’an:Shaanxi Normal University,2015.(in Chinese)

[19] Vicente S, Kolmogorov V,Rother C.Joint optimization of segmentation and appearance models[C]∥Proc of International Conference on Computer Vision,2009:755-762.

[20] Xin Yue-lan.Superpixel based grabcut color image segmentation [J].Computer Technology and Development,2013,23(7):48-56.(in Chinese)

[21] Hu Zhi-li,Guo Min.Fast segmentation in color image based on quadtree decomposition and graph cuts[J].Computer Engineering & Science,2015,37(2):390-396.(in Chinese)

[22] Shi Yong-gang,Tan Ji-shuang,Liu Zhi-wen.Renal cortex segmentation using graph cuts and level sets[J].Computer Science,2016,43(7):290-293.(in Chinese)

[23] Dai Qing-yan,Zhu Zhong-jie,Duan Zhi-yong,et al.Image segmentation based on super-pixel and improved iterated graph cut algorithm[J].Computer Engineering,2016,42(7):220-226．(in Chinese)

[24] Cheng Ming-ming,Mitra N J,Huang Xiao-lei,et al.Global contrast based salient region detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2015,37(3):569-582.

[25] Meng Rui，Tang Hao-xuan.Clothing target matting for algorithm based on OneCut and shared matting [J].Intelligent Computer and Application,2015,5(5):84-88.(in Chinese)

[26] Chang H H,Zhuang A H,Valentino D J,et al.Performance measure characterization for evaluating neuroimage segmentation algorithms[J].Neuroimage,2009,47(1):122-135.

[27] Lin Jian.A learning-based co-evaluation framework for image segmentation evaluation[D].Chengdu：Southwest Jiaotong University,2014.(in Chinese)

附中文参考文献：

[1] 李小红,武敬飞,张国富,等.结合分水岭和区域合并的彩色图像分割[J].电子测量与仪器学报,2013,27(3):247-252.

[2] 赵荣椿,赵忠明,赵歆波.数字图像处理与分析[M].北京:清华大学出版社,2013.

[3] 王丹丹,徐越,宋怀波,等.融合K-means与Ncut算法的无遮挡双重叠苹果目标分割与重建[J].农业工程学报,2015,31(10):227-234.

[5] 林强,董平,林嘉宇.图割方法综述[J].微处理机,2015,36(1):35-39.

[6] 柳显涛.基于能量最小化模型的图像处理技术研究[D].南昌:江西理工大学,2014.

[7] 严子恒.最小割最大流算法的研究与应用[D].南京：南京邮电大学,2016.

[8] 张少娟,邹建成.图割综述[J].北方工业大学学报,2010,22(3):10-15.

[18] 孙巍.基于图割的交互式图像分割技术研究[D].西安:陕西师范大学,2015.

[20] 辛月兰.基于超像素的Grabcut彩色图像分割[J].计算机技术与发展,2013,23(7):48-56.

[21] 胡志立,郭敏.基于四叉树分解与图割的彩色图像快速分割[J].计算机工程与科学,2015,37(2):390-396.