利用超图图割的图像共分割算法

袁飞，朱利，张磊

（1.西安交通大学电子与信息工程学院，710049，西安；2.西安交通大学软件学院，710049，西安；3.北京理工大学计算机学院，100081，北京）

单幅图像分割是计算机视觉领域的一个难题。 完全非监督的图像分割算法依赖于图像的局部特征而缺少图像内或图像间的邻域域信息，使得图像分割的结果不佳；监督或半监督的图像分割算法虽然能获得较好的结果，但是通常依赖于大量的人为标注训练数据，且图像分割的速度通常很慢［1］。因此，近年来解决单幅图像分割的图像共分割就成为新的研究热点。图像共分割是指从具有相同或者相似目标的2幅或者多幅图像中通过聚类算法［2-6］来分割出目标。相对于单幅图像的分割，共分割对多幅相似图像同时进行处理，引入了更多的先验信息（例如多个目标的相似性等），所以能更准确有效地完成图像内容的分割任务。

在图像分割算法中，基于图割的图像分割技术是研究广泛的热点问题之一。其基本思想是将图像映射为图，通过对所构造的图的聚类，完成对图像的分割。同其他图像分割技术一样，基于图割的图像分割技术也可以应用于图像共分割问题上，且相比传统方法具有更好的分割结果。文献［2］采用对输入图像潜在前景直方图的L1距离来衡量前景差异，并作为全局约束加入基于马尔科夫随机场（MRF）的能量函数，通过优化能量函数的方法来实现图像共同前景的分割，但能量函数的优化求解过程的计算复杂度相对较高，使得算法耗费时间较长，同时其分割效果并不理想。文献［3］同样采用输入图像潜在前景直方图距离作为前景差异，利用最大流最小割的算法对优化问题求解，提高了分割的效率，但其算法基于图像像素计算，计算复杂度仍然很高。文献 ［6］首先通过对图像的归一化分割和基于核的方法进行分割，然后根据分块相似性建立优化问题能量函数，通过降低节点数目来提高算法效率，但预处理所耗费的时间较长。Huang等借助图像共分割的思想实现高效的重复前景物体分割［7］和视频分割［8］，但构造的图比较复杂，无法有效表示图像和视频场景中的共性对象，从而不利于高效求解。目前基于图割的图像共分割算法都是在传统简单图的基础上对图像进行表示，需要引入更多的特征信息，从而增加了优化过程的计算复杂度。本文引入超图模型替代传统简单图，可以更好地对图像内和图像间的相关关系进行表达，同时通过降低图构造的复杂度和维度来降低算法计算的复杂度，从而达到提高分割算法效率的目的。

1 超图模型介绍

Berge于1970年第一次提出超图并对其进行系统的阐述［9］，其初衷是表示多端子网络所联成的超网络的拓扑结构。超图理论已经在计算机科学和人工智能领域得到长足发展。

设G=｛V，E｝为超图，其中V=｛v1，v2，…，vn｝为超图节点集，vj∈V 为超图节点，E=｛e1，e2，…，em｝为超边集，ei∈E为超边，且满足

超图可由一个m×n的矩阵H表示，称H为超图的关联矩阵。h（i，j）表示矩阵H中第i行第j列的元素，定义为

若给第i条超边赋予权值ω（ei），则对角矩阵W表示超边权值矩阵，且对角线上第i个元素为w（ei）。令Dv表示节点度的对角阵，对角线上第i个元素表示节点vj∈V的度定义为

令De表示超边度的对角阵，对角线上第i个元素表示超边ei∈E的度定义为

超图克服了简单图只能表示2个顶点之间的双向关系的缺点，可以表示多个顶点之间的局部聚合信息，这样就能完整地描述客观世界中数据间的复杂多重的相关关系。图像作为一种数据形式，其中包含了大量的特征，可以提取高维特征来代表图像。对于图像分割来说，用简单图映射图像，只能保留每2个像素或分块间的相关关系，而实际上它们间的相关关系是十分复杂的，这势必导致信息的丢失；超图可以同时表示像素或分块在局部邻域与多个像素或分块间的多重相关关系，从而保留了更多的特征信息。超图表示示例如图1所示。

从图1b可以看出，超图能表示任意数目的节点间的相关关系，即包含在同一超边内的节点相互关联。超图能更好地表示多个数据之间的相关性，同时使得数据的表达更加简单。因此，利用超图对图像进行映射，可以对图像中局部或者全局信息进行更简单完备的进行表达，从而提高图像分割的效率。

2 算法介绍

图1 超图表示示例

利用超图图割的共分割算法将图像以超图的形式来表达，首先对具有相似前景的2幅图像分别进行Mean-shift过分割，并将得到的过分割区域分块作为超图的节点；然后利用分块的颜色直方图计算所有分块间的相似性，并将相似的分块对应的相似节点集合和单幅图像中相邻节点集合作为超边并计算其权值，构造超图；最后利用基于谱分析的近似算法求解超图归一化分割问题，获得图像对的共分割结果。

2.1 Mean-shift过分割处理

在图像至超图的映射过程中，一般选用图像的单像素、超像素或者区域分块作为节点。本文采用Mean-shift算法［10］先对图像进行过分割的预处理，将得到的分割分块作为超图节点，如对图2a、2b分别进行过分割，得到的结果如图2c、2d所示。Mean-shift算法先在特征空间中算出当前点的偏移均值，将该点移动到其偏移均值处，然后以此为新的起始点，重复上述移动，直到满足一定的收敛条件结束。采用Mean-shift算法对图像进行预处理，能很好的保持目标局部的一致性，从而提高共分割结果的质量；同时，能降低超图的节点数目，从而降低超图分割的计算复杂度，提高分割的效率。

2.2 超图构造

将2幅图像分别做预分割处理，得到每个分块作为超图的节点，通过节点的某种相邻关系，例如欧式空间的相邻、特征相似等，将这些节点划为一个集合作为超边，如图3所示。具体构造过程如下。

图2 图像过分割实例

图3 图像对超图构造

在同一幅图像中，将空间相邻的2个分块划为一个超边。分块相邻也就是在2个分块中存在像素点4相邻。这样就将2幅图像分别构造了2个独立的超图。由于在不同的图像中，相似区域的空间位置一般不会保持不变，故不能采用上面的分块空间相邻的方法将不同图像的分块联系起来，而超边可以理解为具有某种一致性的节点的集合，这样就可以将分块的特征将相似度较高的分块划为一个超边集合，利用分块的R、G、B颜色直方图判断其相似性。H1、H2分别为2幅图中的某一分块的归一化R、G、B 颜色直方图，Hl=［Hl，1，Hl，2，Hl，3］，l=1，2，其中 Hl，k，k=1，2，3表示分块l颜色直方图的k分量，计算（H1、H2）的 Chi距离d（H1，H2）作为分块的相关系数，即

由式（5）可知，分块相似度越高，相关系数越小。故将相关系数小于0.1的分块作为相似分块，否则为非相似分块。然后将2幅图中相似的分块集合划为一个集合，该集合则可以作为联系2幅图的一条超边，从而构造超图。

由于分块相似性判断方法是基于分块的颜色直方图，则计算超边权值的时候也采用分块的颜色信息进行计算。Cm、Cn分别代表分块m、n的R、G、B颜色均值，则定义Cm、Cn的相似度为

式中：α为0到1的系数。

在超图中，对相关性越强的节点，其所属的超边具有更大的权值。选择超边中图像分块间相似度的最大值作为超边的权值。由于通过直方图相关性判断得到的超边中的图像分块具有更强的相关性，故对其权值乘上权值系数λ（λ＞1）后作为该超边的权值。权值系数越大，表示通过直方图相关性判断得到的超边中的图像分块的相似性在超图中得到了强调，尤其减小了由前景背景分块过于相似造成的对共分割结果的影响，得到更好的共分割结果。

2.3 超图分割

根据上述方法将图像对构造为对应的超图，本文采用超图归一化分割算法［9］对其进行分割。假设节点子集S⊂V，Sc表示S的补集。Ω表示超图边界包含的被分割的超边集合，将超图分割为S、Sc两部分

式中：e为任意超边，超图的分割可以定义为

式中：vol表示图的分割。

超图G的归一化分割则可以定义为

这是一个NP-hard的优化问题，根据文献［11］可以被松弛为一个实值优化问题。根据文献［9］求解，可以采用谱分析的近似算法，定义超图的拉普拉斯矩阵为

由文献［9］可以知道超图拉普拉斯矩阵最小非零特征值对应的特征向量即为该实值优化问题的最优解，即该特征向量对应一个超图的二值划分，其第N列的数大于0时，则对应标号为N的分块为前景分块，反之，则属于背景分块，从而通过对超图的归一化分割，得到对图像对的前景背景共分割的结果。

3 实验结果分析

为了验证本文分割提出算法的有效性，对MSCR数据集［4］和 FlickrMFC数据集［12］中的部分图像进行了共分割实验。作为对比，将本文算法的实验结果与单幅图像的归一化分割算法［11］以及共分割算法［6］进行了比较。

实验中所用的机器配置如下：AMD速龙双核CPU，2GHz主频，2GB内存，32位操作系统。Mean-shift算法中2个参数的选择为：位置空间带宽5，颜色空间带宽5。图像间超边相似度计算系数α=0.1，超边的权值系数λ，在实验中取λ=2。

图4为本文算法及对比算法的图像分割实验结果。从实验结果来看，本文算法在实验中能更好地对图像进行共分割。由于本文算法首先基于Meanshift算法进行预分割处理，所以最后的分割结果对于目标的完整性保持得较好。文献［11］算法为单图归一化分割，对2幅图像分别进行分割，没有引入图像间分块的相关关系作为相似性约束，因此分割误差较大。文献［6］算法基于像素进行共分割处理，没有预先对图像中局部连通的区域进行聚类，最终共分割结果中产生了相应误差。

图4 共分割实验结果对比

超边权值系数λ对分割结果有较大的影响。图5所示为图像对中的一幅图像以及在不同权值系数下的分割结果。从实验结果来看，随着权值系数的增大，图像分割的结果能更好地将较为相似的前景与背景分块分割开来，得到更好的分割结果。

图5 超边权值系数λ对实验结果的影响

实验的时间对比如表1所示。算法均选择采用颜色特征实现分割。本文算法与文献［6］算法相比，求解优化问题的计算复杂度降低，分割所需时间减少。文献［11］算法对每一幅图像单独进行归一化分割，本文算法与文献［11］算法相比，由于是对2幅图像同时进行分割，因而分割所需的时间减少了。从实验结果来看，本文算法相较于对比算法，其共分割的效率明显提高，分别为文献［6］和［11］算法所需时间的4%～10%、32%～55%。本文算法所耗的时间主要在Mean-shift预处理过程。

表1 采用3种算法对4组图像对进行共分割所需时间比较

4 总 结

本文针对基于传统简单图割算法的图像共分割方法效率低的问题，提出了一种基于超图模型的图像共分割算法。利用Mean-shift预分割所得到的分块作为节点，将相似的分块和相邻的分块划为一个超边子集，从而构造超图。然后，利用超图的归一化分割算法对所构造的超图进行划分，从而得到最终的图像共分割结果。实验结果表明，本文方法在分割质量和计算效率上均有很大的提高。然而，本文算法仍然存在一些需要进一步完善的地方，例如共分割结果对Mean-shift初始分割结果的要求较高，分块数不能过多，同时为了保证共分割的质量，分块必须保持良好的独立性等。此外，如何简单高效地判断并计算分块间的相似性是算法的关键，还有待进一步研究。

［1］ 林开颜，吴军辉，徐立鸿等.彩色图像分割方法综述［J］.中国图象图形学报，2005，10（1）：1-10.LIN Kaiyan，WU Junhui，XU Lihong.A survey on color image segmentation techniques ［J］.Journal of Image and Graphics，2005，10（1）：1-10.

［2］ ROTHER C，MINKA T，BLAKE A，et al.Cosegmentation of image pairs by histogram matching-incorporating aglobal constraint into MRFs［C］∥Proceedings of 2006IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2006：993-1000.

［3］ HOCHBAUM D S，SINGH V.An efficient algorithm for co-segmentation ［C］∥Proceedings of 2009IEEE 12th International Conference on Computer Vision.Piscataway，NJ，USA：IEEE，2009：269-276.

［4］ CHANG K Y，LIU T L，LAI S H.From co-saliency to co-segmentation：an efficient and fully unsupervised energy minimization model［C］∥Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2011：2129-2136.

［5］ VICENTE S，ROTHER C，KOLMOGOROV V.Object cosegmentation ［C］∥Proceedings of 2011IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2011：2217-2224.

［6］ JOULIN A，BACH F，PONCE J.Discriminative clustering for image co-segmentation ［C］∥Proceedings of 2010IEEE Conference on Computer Vision and Pattern Recognition.Piscataway，NJ，USA：IEEE，2010：1943-1950.

［7］ HUANG Hua，ZHANG Lei， ZHANG Hongchao.RepSnapping：efficient image cutout for repeated scene elements［J］.Computer Graphics Forum，2011，30（7）：2059-2066.

［8］ 张洪超，张磊，黄华.基于跨时空域相似邻接图的视频分割方法 ［J］.图学学报，2012，33（2）：83-88.ZHANG Hongchao，ZHANG Lei，HUANG Hua.Video cutout method based on spatio-temporal similarity neighboring graph［J］.Journal of Graphics，2012，33（2）：83-88.

［9］ BERGE C.Graph and hypergraph［M］.Amsterdam，Holland：North-Holland Publishing Company，1973.

［10］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.

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

［12］汪粼波，郭延文，夏天辰，等.样本驱动的半自动图像集前背景分割 ［J］.计算机辅助设计与图形学学报，2013，25（6）：794-801.WANG Linbo，GUO Yanwen，XIA Tianchen，et al.Example-driven semi-automatic image collection segmentation［J］.Journal of Computer-Aided Design &Computer Graphics，2013，25（6）：794-801.