基于归一化割的图像分割

徐齐高

摘 要 本文研究了基于归一化割（Ncut）的图像分割方法的原理及算法实现过程，并进行仿真实验来验证算法的可行性。实验表明，Ncut图像分割方法能在一定条件下取得较好的分割效果，但分类数目的设定以及权值矩阵的计算需进一步的探讨和分析。

关键词 图像分割 归一化割 权值矩阵

中图分类号：TP391.4 文献标识码：A

0引言

基于图论进行图像分割是一种较新的图像分割方法。由于其可获得良好的结果，近年来引起人们的兴趣，是国际上图像分割领域的一个研究热点，尤其是图切割技术因它的全局能量最优化而格外引人注目。基于图论进行图像分割其基本思想是将图像看作一个带权图，其每个节点对应图像的一个像素或区域，连接每两个节点的边的权值表示该两节点属于同一区域的可能性，权值的大小与两节点的相似性、邻近性以及连续性等相关。根据图的某种特定划分建立相应的能量函数，该能量函数的最小值即对应图像的一个最佳分组。依据此思想， 研究者提出了其各自的图论分割准则， 其中比较有代表性的为最小割、平均划分、归一化割及比例划分等[1-3]。

其中最小割和归一化割由于其计算较为简便使用较广泛。Wu和Leahy[4]的研究发现，最小割准则很容易分割出图像中的孤立点集合。而归一化割（NCut）则可以避免分割出孤立点情况。因此，本文采用归一化割进行图像分割。

1基于归一化割的图像分割方法

一副图像可以采用一个无向图来G=（V，E）表达，其中V 是节点的集合，是E 连接节点的边的集合，V的基为N=|V|。连接每两个节点的边均赋予权值w（u，n），该权值衡量节点u 和v的相似程度。图像G=（V，E）通过简单的移除两部分之间相连接的边，就可以分割为两个不相交的集合A和B，并且满足A∪B=V，A∩B= 。这两部分的不相似的程度可以用移除的边的权重之和来计算，通常将他定义为割[5-6]：

cut（A，B）=w（u，v） （1）

最小割准则就是通过计算割式（1）的最小值来得到图像的分割方法。

Wu和Leahy提出了基于最小割准则的聚类方法，而且他们还试图将一幅图像分割为k个子区域，这可以通过递归调用最小割的方法实现。实验证明，在一些图像中，这种全局优化准则可以产生比较好的分割结果。然而，Wu和Leahy在他们的工作中发现了一个问题，最小割准则很容易分割出图像中的孤立点集合。通过最小割的定义式（1）可以分析出现这种现象的原因：最小割的值会随着连接两区域的边的数量的增加而变大。假设边的权值与两个节点之间的距离成反比，那么将节点n1单独分割出来的情况下，所得割的值会非常的小。可以看出，任何一个将右边的孤立点分割出来的情况都比将图分割为左右两个几乎相等的部分的情况时得到的割的值要小。

為了避免分割出孤立点情况的出现，归一化分割准则被提出来。归一化分割在最小割的基础上加入了每个区域的节点与所有节点的权值之和的比，来平衡分割。归一化分割的公式通常可以写为：

Ncut（A，B）=+ （2）

其中assoc（A，V）=∑u∈A，t∈Vw（u，t）是A中所有的节点到图像中所有节点的边的权值之和，assoc（B，V）是B中所有的节点到图像中所有节点的边的权值之和。通过式（2）可以看出，分割孤立点的情况，在归一化分割中的值是比较大的。

同样地，可以有如下的定义：

Nassoc（A，B） =+ （3）

其中，assoc（A，A）和assoc（B，B）分别表示A和B中节点之间相互连接的边的权值之和。式（3）反映了定义的平衡性，他表示每个分组内节点的关联度。

通过式（2）和式（3），可以得到：

（4）

从式（4）可以看出，想要求得的归一化分割的最小值，也就是求分组内的

最大关联度的过程。

采用Ncut 准则就可以克服划分孤立点的问题，最小的Ncut 值对应的划分即为图G 的最优划分。在这种情况下，最小化Ncut 可以转化为如下的标准特征系统

（5）

其中D是N€譔的对角矩阵，其对角线上的元素为=w（i，j），W是对称矩阵，其元素为w（i，j）， 和z分别为相应的特征值和特征矢量。

特征系统（5）的第二个最小的特征值对应的特征矢量可以用来完成全图的最优划分，从而得到对应图像的一个分割结果。可以采用递归算法以相同的方式进一步对分割得到的子图进行划分，直至满足终止条件为止。

2实验结果及分析

本文实验所用计算机CPU主频为2.5GHz，内存为1GB，软件为MATLAB2014a。下图中从左至右依次为原图，采用Ncut分割为3类的结果图以及分割为5类的结果图。本实验的权志矩阵w（u，v）是基于像素（i，j）的相似程度计算的。权值wij与像素i与j之间的距离及灰度差值成反比。

对比原图和分割结果图可以看出，Ncut分割方法基本可以将前景（小孩）和背景比较好的分离出来。而且设定的分割类别数目不同，分割的精细程度也不同。

3结论

本文分析了Ncut图像分割方法的原理及算法求解过程，并利用Ncut进行图像分割。实验表明，Ncut图像分割方法能在一定条件下取得较好的分割结果。但分割种类的设定、权值矩阵的计算方法需根据分割的目的以及特定图像进行分析。

参考文献

[1] 刘松涛，殷福亮.基于图割的图像分割方法及其新进展 自动化学报，2012.38（6）：911-922.

[2] 侯叶.基于图论的图像分割技术研究.西安电子科技大学.博士论文，2011.

[3] J.Shi and J.Malik， “Normalized cuts and image segmentation，” IEEE Trans.Pattern Anal.Mach.Intell.，vol.22，no.8，pp.888–905，Aug.2000.

[4] Wu Z Y， Leahy R. An optimal graph theoretic approach to data clu-stering：Theory and its application to image segmentation.IEEE Transactions on Pattern Analysis Machine Intelligence，1993，15（11）：1101-1113.

[5] 徐俊明.图论.合肥：中国科学技术大学出版社，2010.3.

[6] 胡晓雷.图论支持下的图像分割理论与方法研究.武汉大学遥感信息工程学院，2007.

[7] 刘嘉，王宏琦.一种基于图割的交互式图像分割方法.电子与信息学报，2008.30（8）：1973-1976.

[8] 韩守东，赵勇，陶文兵，桑农.基于高斯超像素的快速Graph Cuts图像分割方法.自动化学报，2011.37（1）：11-20.