基于归一化割的图像分割

《基于归一化割的图像分割》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于归一化割的图像分割摘要本文研宄了基于归一化割(Ncut)的图像分割方法的原理及算法实现过程，并进行仿真实验来验证算法的可行性。实验表明，Ncut图像分割方法能在一定条件下取得较好的分割效果，但分类数目的设定以及权值矩阵的计算需进一步的探讨和分析。本文采集自网络，本站发布的论文均是优质论文，版权和著作权归原作者所有。关键词图像分割归一化割权值矩阵中图分类号：TP391.4文献标识码：A0引言基于图论进行图像分割是一种较新的图像分割方法。由于其可获得良好的结果，近年来引起人们的兴趣，是国际上图像分割领域的一个研究热点，尤其是图切割技术因它的全局能量最优化而格外引人注目。基于图论

2、进行图像分割其基本思想是将图像看作一个带权图，其每个节点对应图像的一个像素或区域，连接每两个节点的边的权值表示该两节点属于同一区域的可能性，权值的大小与两节点的相似性、邻近性以及连续性等相关。根据图的某种特定划分建立相应的能量函数，该能量函数的最小值即对应图像的一个最佳分组。依据此思想，研究者提出了其各自的图论分割准则，其中比较有代表性的为最小割、平均划分、归一化割及比例划分等［1-3］。其中最小割和归一化割由于其计算较为简便使用较广泛。Wu和Leahy［4］的研究发现，最小割准则很容易分割出图像中的孤立点集合。而归一化割(NCut)则可以避免分割出孤立点情况。因此，本文采用归

3、一化割进行图像分割。1基于归一化割的图像分割方法一副图像可以采用一个无向图来G=(V,E)表达，其中V是节点的集合，是E连接节点的边的集合，V的基为N=

4、V

5、。连接每两个节点的边均赋予权值w(u，n)，该权值衡量节点u和v的相似程度。图像G=(V，E)通过简单的移除两部分之间相连接的边，就可以分割为两个不相交的集合A和B，并且满足AUB=V，AnB=。这两部分的不相似的程度可以用移除的边的权重之和来计算，通常将他定义为割[5-6]:cut(A,B)=w(u,v)(1)最小割准则就是通过计算割式(1)的最小值来得到图像的分割方法。Wu和Leahy提出了基于最小割准则的聚类方法，而

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

7、化分割准则被提出来。归一化分割在最小割的基础上加入了每个区域的节点与所有节点的权值之和的比，来平衡分割。归一化分割的公式通常可以写为：Ncut(A，B)二+(2)其中assoc(A,V)=EuEA，t^Vw(u,t)是A中所右的节点到图像中所有节点的边的权值之和，assoc(B,V)是B中所有的节点到图像中所有节点的边的权值之和。通过式(2)可以看出，分割孤立点的情况，在归一化分割中的值是比较大的。同样地，可以有如下的定义：Nassoc(A,B)=+(3)其中，assoc(A,A)和assoc(B，B)分别表示A和B中节点之间相互连接的边的权值之和。式(3)反映了定义的平衡性，

8、他表示每个分组内节点的关联度。通过式(2)和式(3)，可以得到：(4)从式(4)可以看出，想要求得的归一化分割的最小值，也就是求分组内的最大关联度的过程。采用Ncut准则就可以克服划分孤立点的问题，最小的Ncut值对成的划分即力图G的最优划分。在这种情况下，最小化Ncut可以转化为如下的标准特征系统其中D是N??N的对角矩阵，其对角线上的元素为=w（i,j）,W是对称矩阵，其元素为w（i，j），和z分别为相应的特征值和特征矢量。特征系统（5）的第二个最小的特征值对应的特征矢量可以用来完成全图的最优划分，从而得到对应图像的一个分割结果。可以采用递归算法以相同的方式进一步对分割得到

9、的子图进行划分，直至满足终止条件为止。2实验结果及分析本文实验所用计算机CPU主频为2.5GHz，内存为1GB，软件为MATLAB2014a。下图中从左至右依次为原图，采用Ncut分割为3类的结果图以及分割为5类的结果图。本实验的权志矩阵w（11，v）是基于像素（i，j）的相似程度计算的。权值wij与像素i与j之间的距离及灰度差值成反比。对比原图和分割结果图可以看出，Ncut分割方法基本可以将前景（小孩）和背景比较好的分离出来。而且设定的分割类别数H不同，分割的精细程度也不同。3结论本文分析