结合闭合解抠图及最小生成树的图论分割算法

王卫星，石红玉

（1.福州大学物理与信息工程学院，350000福州；2.皇家工学院，斯德哥尔摩，瑞典）

结合闭合解抠图及最小生成树的图论分割算法

王卫星1，2，石红玉1

（1.福州大学物理与信息工程学院，350000福州；2.皇家工学院，斯德哥尔摩，瑞典）

针对图像目标物体与背景边界交错在一起或两者之间边界不明晰以及背景与目标纹理相似的情况，进行图像分割非常困难.为此，提出了一种基于图论（graph theory）及闭合解抠图思想的图像分割算法.首先，利用闭合解抠图算法对图像进行预分割，粗糙地将图像分为前景和背景两部分；其次，提取目标及背景的细节，再分别用改进的图论分割算法细分割目标物体及背景，从而得到最终图像分割结果.实验结果表明，抠图算法避免了前景和背景的混叠，改进的图论算法可有效提高6%～12%的分割精度.与传统的区域合并、通常的图论及阈值算法相比，该算法精度高、效果好，具有显著优越性.

闭合解抠图；图论；最小生成树；图像分割

自1971年Zahn［1］最早将图论应用于图像分割和数据聚类以来，由于图论方法良好的数学基础及应用的扩展，基于图论的图像分割成为国内外研究的热点，并产生了多种基于图论的图像分割算法.主要包括:图切割相关算法［2-7］，活动线（live wire）方法［8］，随机游走与等周算法［9-11］，最小生成树算法［12］.

值得一提的是2006年Sharon等［4］在《Nature》上提出的一种基于图方法的至上而下的分层分割方法，分割结果精准且效率高.另外，Felzenszwalb等［12］提出了“小而并之”的最小生成树分割算法，即当区域的内部差异大于区域之间的像素差异时，就认定两区域属于同质区域而将它们合并.该分割方法能够部分地根据不同的图像特性进行不同分割且效率较快，本文就以此方法为基础进行改进.

上述最小生成树方法不足之处在于随着设置参数的增大，丢失了图像的很多细节，而参数设置过小容易产生过分割，无法正确把握分割尺度.为了解决这一问题，可以考虑结合预（粗）分割算法来进行补充，可能的预分割算法之一是抠图算法［13］.抠图算法虽然不能检测出图像中目标物体的详细细节，但可以将整体目标物体从复杂背景图像中分割出来，弥补了图论方法在此方面的不足.Levin等［14］所提出来的closed-form solution算法通过用户的交互输入计算全局最优值，得到高质量的抠图结果.因此，本文方法结合图论和此算法，各取其长，在闭合解抠图算法粗分割的基础上用改进的图论方法对图像进行细分割，得到较为理想分割效果.

1 基于闭合解抠图算法的预分割

抠图是从图像背景中提取出前景目标的技术.对于输入图像I，存在以下颜色组合方程

式中:F、B分别为前景色和背景色；α为不透明度，表征前景色所占的比重，0≤α≤1．关于α，本文进行四舍五入，即其取值非0即1，因为对于图论方法，为了进一步将对前景分割与背景分割得到的结果相加，本文设定对图像黑色像素点不进行处理．若α在0～1之间，则无论是前景还是背景都会对此部分像素进行基于图论的分割，最后相加时会产生前景和背景的重复叠加．

根据闭合解抠图理论对本文研究图像进行处理，选取了两幅各具特色的自然景象（非人造目标）图像，图像中目标物体及背景的组合及纹理均复杂.如图1所示为闭合解抠图的结果与高效随机游走算法［15］分割结果的比较.由图1可以明显看出本文方法可以准确地将前景目标从背景图像中分割出来，包括前景和背景交错的部分，比如小鹿的身体与草丛、帆船的倒影等；而随机游走算法虽然能大致将前景与背景之间的边界描绘出来，但是对于边界点较为模糊或者前景与背景之间灰度值较为接近的情况，找到的边界并不准确.

图1 闭合解抠图结果与高效随机游走算法比较

2 基于改进分割准则的图论算法的细分割

在以上闭合解抠图结果的基础上，对图像前景进行基于图论的细分割.即将图像映射成一个加权图G（V，E），采用基于合并策略的Krusal算法进行分割，主要涉及3个参数:1）高斯滤波参σ；2）阈值函数参k，用来控制分割程度；3）再合并参数min-size.若两邻域其中一个的区域大小小于min-size，则将两区域合并.此方法分割效果好、算法结构简单且计算效率高，但它仍然有许多缺点，本文针对以上3个参数分别加以改进.

2.1 图论算法的具体改进

2.1.1 最小生成树中区域内部和区域间差异函数的改进

如果仅仅用区域内的最大边权代表区域的差异程度，对某些图像而言，容易受噪声和孤立点的影响，分割效果也会变差，因此可以重新定义区域内部差异和区域间差异为

式中N为最小生成树的边数，即N=｜C｜-1．此举虽然在一定程度上降低了敏感度，原方法中可以合并的两区域可能因此将不能合并，但可以通过调节参数k控制分割尺度．

2.1.2 边权函数设计的改进

原方法的权重函数仅仅是灰度值的绝对差异，而没有考虑到各像素的空间位置.若两像素空间位置较远，其相关性一般也会变弱，理应加大边权惩罚.因此可定义权重函数为

其中:I（vi）、I（vj）分别为像素vi和vj的灰度级；d（vi，vj）定义为vi和vj之间的空间欧式距离为

为一个自适应的二维高斯因子

式中:μi、μj分别为方向像素灰度级的期望；σi、σj分别为其标准差；r为其协方差．

2.1.3 图映射分割后再合并机制的改进

算法 1）从分割S开始，对每一条边（vi，vj）∈E，vi∈C1，vj∈C2，如果C1≠C2并且｜C1｜＜q且｜C2｜＜q，那么就将C1和C2合并，得到新的分割Snew．2）对Snew中的每一条边，（vi，vj）∈E，vi∈C1，vj∈C2，如果C1≠C2并且｜C1｜＜q或者｜C2｜＜q，那么就将C1和C2合并．

假设待分割图像的分辨率为3×3，分割S中每一顶点为一区域，p=4．由图2（a）可以看出，Step 1更容易得到大的区域，但一些小区域仍然存在.经过Step 2可以保证所有区域大小大于p．而原方法直接跳到第2步，使图像只得到一个分割区域，产生过合并现象．

图2 再合并机制比较

2.2 改进的图论分割算法与其他类似分割算法的比较分析

对图1中图像的抠图结果图（目标物体图和背景图），分别进行基于改进Graph-Based算法、基于mean-shift模型的区域合并算法［16］以及Canny边缘检测算法的图像分割，试验结果如图3所示.由于噪声太多，基于边界扫描（如Canny）的方法无法精确地勾画出各目标物体的轮廓及纹理等.区域合并算法有些地方过合并有些地方过分割，以下图像都不同程度地出现了这一问题.相较而言，基于改进图论的分割方法效果较好，小鹿身体中属于草丛部分完全被分离出去，第2排属于近处与远处的树木分割开来.该方法可以有效去除孤立点和其他噪声，并且将渐变区域合为同一区域.

图3 闭合解抠图基础上分割结果比较

以上3种方法的处理速度如表1所示，其中区域合并方法未将mean shift预处理的时间计算在内，可见基于图论的分割方法效率较高.

表1 3种方法处理速度比较

3 结果与分析

经过以上分析，本文的算法（包括粗分割和细分割）的总流程图如图4所示.其中:①为闭合解抠图部分；②为基于改进图论算法的图像分割部分.当①中交互选取种子点时，根据本文图像纹理特点，为得到好的抠图效果与效率，选取的种子点像素数目占整幅图像的比率大致为3%～8%.

按照图4对图像进行分割，图5演示了每一步的过程，此处种子点概率为4.53%.与原图论方法［12］以及文献［17］的改进图论方法进行比较（均在抠图基础上进行处理），调整各参数尤其是k以得到最优的分割效果.从图5可以看出，若没有预分割（闭合解抠图）步骤及图论算法的改进，原图论的分割算法很难分割这些边界模糊复杂的自然景象图像.

图4 算法流程图

图5 本文方法分割步骤

基于图1中的图像，图6（a）是用本文算法处理的结果，图6（b）、6（c）分别是在抠图基础上用原算法和文献［17］算法处理的结果.两幅图像的种子点比率分别为5.67%、3.26%.

从图1可以看出:第1幅图像中小鹿站在草丛中，身体与草丛混杂在一起，纵向看，小鹿身体上的花纹和身处的草丛均是垂直方向的纹理，只存在颜色的差异，是分割的难点所在，本文方法将小鹿和草丛准确分离，而原图论方法与文献［17］方法头部分割结果均不理想；第2幅图像中帆的颜色与水色灰度差异小，难以分辨，且近处树叶与远处树叶边界模糊，以及树叶缝隙与天空的交接等都给分割带来困难，本文方法较好的解决了以上难点，而原图论方法未将远处和近处树木合理分割，天空云彩欠分割，文献［17］方法除以上问题外，水中的帆船同样欠分割.针对以上两幅图像，根据人工绘制边界图7，分别比较，计算各方法的分割精度如表2所示.

图6 本文方法与其他方法比较

精度计算为

式中:Epixel、Upixel分别为3种方法分割结果中边界点的正确率与错误率；λ为惩罚系数，其值越大对多余边界像素点的惩罚越大，精度也越低．考虑到图像的复杂性，本文未能将所有边界点都准确描绘出，且主要考量方面为正确率，因此本文取λ= 0.3；WEpixel为期望分割结果的总边界像素点．

图7 期望分割结果

根据上述粗分割和细分割的结合方法，本文选取了40多幅具有不同代表性的边界模糊图像进行了试验，参照图6和表2的分析，本文提出方法可有效提高6%～12%的分割精度.

表2 本文方法与其他方法精度比较%

4 结 论

1）本文针对目标边界不清楚的图像难以用常规图像分割算法进行分割的问题，提出了一种结合闭合解抠图和改进图论的分割方法.对闭合解抠图得到的背景和前景图像分别用改进的图论方法进行处理，再将两个结果合并得到最终分割结果.

2）此方法不会产生前景与背景的错分割，亦可保留图像细节.

3）将前景和背景分开处理，在用基于改进的图论方法进行分割时，具有可以分别根据前景和背景纹理特点设置不同分割尺度的优点，这在一定程度上避免了欠分割和过分割.

4）从区域内部和区域间差异函数、边权函数和图映射分割后再合并机制3方面对图论方法进行改进，降低噪声对分割结果的影响，提高分割准确性.与原图论和区域合并方法相比，本文方法错分率小，具有良好的分割效果.

参考文献

［1］ZAHNC.Graph-theoreticalmethods for detecting and describing gestalt clusters［J］.IEEE Transactions on Computers，1971，C-20（1）:68-86.

［2］SHI J，MALIK J.Normalized cuts and image segmentation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（8）:888-905.

［3］BOYKOV Y，FUNKA-LEA G.Graph cuts and efficient ND image segmentation［J］.International Journal of Computer Vision，2006，70（2）:109-131.

［4］SHARON E，GALUN M，SHARON D，et al.Hierarchy and adaptivity in segmenting visual scenes［J］.Nature，2006，442（7104）:810-813.

［5］CHEN Yuke，WU Xiaoming，CAIKen，et al.CT image segmentation based in clustering and graph-cuts［J］. Procedia Engineering，2011，15:5179-5184.

［6］侯叶.基于图论的图像分割技术研究［D］.西安:西安电子科技大学，2011.

［7］EGGER J，FREISLEBEN B，NIMSKY C，etal.Templatecut:a pattern-based segmentation paradigm［J］.Nature Scientific Reports，2012，2:1-8.

［8］WIECLAWEKW，PIETKA E.Fuzzy clustering in Intelligent scissors［J］.Computerized Medical Imaging and Graphics，2012，36（5）:396-409.

［9］GOPALAKRISHNAN V，HU Y，RAJAN D.Random walks on graphs for salient object detection in images［J］.IEEE Transactions on Image Processing，2010，19（12）:3232-3242.

［10］依玉峰，高立群，郭丽.基于Mean shift随机游走图像分割算法［J］.计算机辅助设计与图形学学报，2011，23（11）:1875-1881.

［11］汪云飞，毕笃彦，黄飞.一种用于图像分割的等周算法改进［J］.西安电子科技大学学报，2012，39（2）: 87-94.

［12］FELZENSZWALB P F，HUTTENLOCHER D P.Efficient graph-based image segmentation［J］.International Journalof Computer Vision，2004，59（2）:167-181.

［13］WEXLER Y，FITZGIBBON A，ZISSERMAN A.Bayesian estimation of layers from multiple images［J］.Computer Vision，2002，2352:487-501.

［14］LEVIN A，LISCHINSKI D，WEISS Y.A Closed-form solution to natural image matting［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，30（2）:228-242.

［15］ANDREWSS，HAMAMEN G，SAAD A.Fast random walker with priors using precomputation for interactive medical image segmentation［J］.Medical Image Computing and Computer-Assisted Intervention，2010，6363:9-16.

［16］PENG Bo，ZHANG Lei，ZHANG D.Automatic image segmentation by dynamic region merging［J］.IEEE Transactions on Image Processing，2011，20（12）:3592-3605.

［17］ZHANG M，ALHAJJ R.Improving the graph-based image segmentation method［C］／／Proceeding of the 18thIEEE International Conference on Tools with Artificial Intelligence.Arlington:IEEE，2006:617-624.

（编辑张 红）

A minimum spanning tree based image segmentation algorithm w ith closed-form solution

WANGWeixing1，2，SHIHongyu1
（1.School of Physics and Information Engineering，Fuzhou University，350000 Fuzhou，China；2.Royal Institute of Technology，Stockholm，Sweden）

For the edges between objects and background in an image are intertwined or their common boundaries are vague as well as the textures of objects and background are similar，a new method based on graph theory and closed-form solution was proposed.First，it uses closed-form solution to initially separate the objects from background roughly，then，to extract the detailed information of inter objects，it applies an improved graph-based algorithm to obtain the final image segmentation results.The test results show that the algorithm ofmatting avoids aliasing of foreground and background and the improved graph-based algorithm increases segmentation accuracy by 6%～12%effectively.Compared to the traditional algorithms such as region merging，ordinary graph，and thresholding，the new algorithm has the better accuracy and effect，therefore it has the significant superiority.

closed-form solution；graph theory；minimum spanning tree；image segmentation

TP391

A

0367-6234（2014）09-0123-06

2013-10-12.

国家自然科学基金资助项目（61170147）.

王卫星（1959—），男，教授，博士生导师.

王卫星，znn525d＠qq.com.