基于形态学分水岭的Normalized Cut图像分割方法

刘贺鹏，吕建平

(西安邮电大学 计算机学院，陕西 西安 710121)



基于形态学分水岭的Normalized Cut图像分割方法

刘贺鹏，吕建平

(西安邮电大学 计算机学院，陕西 西安 710121)

针对传统分水岭分割后所产生的过分割问题，提出了一种基于形态学分水岭算法和NormalizedCut算法相结合的图像分割方法。在传统分水岭分割的基础上，融合形态学算法进行初步分割，并将分割后各个子区域的形心和平均灰度值作为NormalizedCut算法的输入参数，完成图像分割。结果表明，组合算法既避免了过分割现象，也达到了NormalizedCut算法的分割精度，是一种有效的图像分割算法。

图像分割；分水岭；形态学；NormalizedCut

图像分割是图像处理领域以及计算机视觉中一个经典问题，图像分割的主要目的是将一幅图像分解成互不交叠的若干灰度一致性区域，并将人们感兴趣的部分凸显出来，为后续的图像分析、理解、目标跟踪、分类与识别等处理提供理论支撑。由于应用场景的不同，人们所感兴趣的目标也各不相同。因此，图像分割始终是图像处理中的一个难点，如何使分割算法充分地适应不同的场景且具有较快的运算速度一直是图像分割研究的热点。

近年来，众多成功应用于其他领域的理论方法被引入到图像分割的研究中，这使得图像分割的研究取得了很大进展。其中，较成功的包括分水岭算法与种子生长结合的算法[1]、主动轮廓模型、阈值分割方法[2]、基于图论的方法等。基于图论的方法是近年来国内外学者竟相追逐的研究热点。图论中较为经典的分割算法是Leahy 和 Wu[3]提出的最小割算法(Cut)，但该算法只考虑了两个子图之间的割最小，偏向于分离单个或小簇顶点，易划分出极小子图，对噪音敏感，分割效果不理想。1997年，Shi 和 Malik 在最小割的基础上得到了一种更好的分割方法：归一化图割 (Nomalized Cut, Ncut)[4]，其同时度量了不同分割区域的差异以及同一分割区域的相似性，对图像的全局信息进行提取，解决了最小割准则的固有缺陷。然而，Ncut算法会随着图中结点数的递增，计算量呈几何级数增加，导致在分割较大的图像时会非常耗时。因此，如何减少Ncut方法计算量成为众多学者关注的焦点。

Vincent[5]等人提出的分水岭分割算法因具有计算量小、分割精度高的优点在图像分割领域引起了广泛关注。但原始分水岭算法更多地局限于图像的局部信息，过度分割现象[6-7]严重，较少直接用于实际。为充分结合分水岭和Ncut方法的优点，本文采用基于数学形态学分水岭的Ncut算法，其初步分割区域个数得到了很好的控制，有效降低了运算量，同时组合算法也继承了Ncut算法分割精度高、对噪声鲁棒性强的优点。

1　形态学分水岭算法

分水岭算法是一种传统的分割技术，该算法最初是在20世纪70年代末，由C.Digabel和H.Lantuejoul引入到二值黑白图像的分析过程中，再经过Beucher、Vincent等人的深入研究，建立了比较完善的分水岭理论体系，并在20世纪80年代用于灰度图像的分割[8]。1991年，Vincent等人又深入改进了算法，提出了浸没算法，大幅缩短了算法时间。

由于图像在成像的过程中存在噪声、光照等复杂因素的影响，组成目标的这些极值区域、噪声区域以及中间区域在梯度图像中都会变成极小区域被分割出来，这是造成分水岭算法过分割的主要原因。为了有效减少过分割现象，可通过对原始待分割图像进行平滑滤波的方式减少脊线的产生。然后，结合形态学开运算和闭运算对平滑后的边缘图像做进一步的噪声和边缘抑制，从而获得形态学分水岭变换。图1显示了传统的分水岭变换和形态学分水岭变换对经典的Cameraman图像进行初步分割的结果。从图像中可看出，形态学滤波变换保留了图像中主要的边缘细节信息，同时有效减少了脊线的产生。

图1　经典Cameraman图像分水岭及形态学分水岭初分割结果

2　Normalized Cut方法

对于一个给定的带权图G={V,E}，其中V是结点的集合，E是连接结点的边的集合，顶点之间边的连接权值 表示两点之间的相似程度，通常使用高斯核函数来计算结点间的权值。移去结点A与B之间的边可将其拆分为两个不相交的部分A与B，A∪B=V，A∩B=∅。该图定义一个割如式(1)[9-10]

(1)

即A与B之间所有边的权值之和，NormalizedCut方法定义其不相似度量为

(2)

将元素向量记为y，每个分量对应图的一个结点，其值是l或-1，用于区分图的不同部分。将相似性矩阵记为W，W为对称阵，第i行第j列元素为w(i,j)。次数矩阵记为D，D为对角矩阵，其对角线上的元素记为d(i),等于相应结点的权值之和，即

(3)

该标记下准则为

(4)

为找出最小的Ncut值对应的y，可转换成如式(5)的特征向量求解问题

(D-W)y=λDy

(5)

在问题求解上用y作为指示向量，NormalizedCut方法使用的是特征方程的第二个最小特征值所对应的特征向量作为该问题的解。在向量y中选择一个分割数值，使y中大于该数的部分所对应的结点在A中，其余的在B中，这样就将图G中的结点分成两个部分。若所分割的部分需要再细分，可递归地调用该算法。

3　Normalized Cut方法

由于分水岭算法对噪声敏感，易造成过分割的问题，并不能将图像中有意义的区域表示出来，所以必须对分割结果进行2次合并。同时，分水岭脊线用于区分不同子区域的边界，并不属于任何子类。因此，文中采用局部最近邻规则，首先将分水岭脊线上的像素点划分为局部子区域内包含某一个子区域最多像素点所在区域。然后再计算各子区域形心和灰度均值。将形心当作图的各个结点，每个结点与其他结点连接建立一个浓缩的带权图G={V,E}，权值的计算融合了结点之间的距离和各子区域灰度均值信息。由于结点的个数远小于图像像素点的个数，因此基于形态学分水岭NormalizedCut方法所产生的权值矩阵较小，有利于数值求解。

基于形态学分水岭的NormalizedCut方法主要流程：(1)使用形态学分水岭算法对输入图像做初步分割；(2)提取分水岭分割图像各子区域的形心与区域灰度均值；(3)使用如下方式构造相似性矩阵即权值矩阵w。

(6)

式(6)中，G(i)、G(j)分别为结点i、j所在区域的灰度均值；σs表示结点i、j像素值标准差；P(i)、P(j)分别为结点i、j空间位置坐标；σt表示结点i、j空间位置标准差。显然，结点之间的距离越小、灰度差异越小，其之间的连接权值就越大；(4)求解特征方程(D,W)y=λDy，利用与第2个最小特征值相应的特征向量,对图中的结点进行划分,进而完成对图像的分割。

4　实验结果

为验证所提出的组合算法的有效性，本文比较了传统的分水岭算法、Normalized Cut方法以及形态学分水岭-Normalized Cut组合方法在分割精度、运行时间上的差异。

图2和图3为分别使用传统的分水岭方法、Normalized Cut方法以及基于形态学分水岭的Normalized Cut方法对不同的两组图像进行分割的结果。3种算法对应的时间如表1所示。使用传统的Normalized Cut方法和形态学分水岭-Normalized Cut方法分别将图2分割成5类、图3分割成9类。如图2(b)和图3(b)所示，传统的分水岭方法出现了严重的过分割现象。

对比图2(c)～图2(d)及图3(c)～图3(d)可发现，Normalized Cut方法和形态学分水岭-Normalized Cut方法分割结果视觉效果上总体趋于一致，但Normalized Cut方法在图像的边缘区域过渡更为平滑，具有更好的分割精度。从表1可看出，3种分割方法中，分水岭方法占用的时间最少，但分割效果最差；形态学分水岭-Normalized Cut方法本质上等同于Normalized Cut方法，但其运行速度较Normalized Cut方法具有较大的优势，更适用于对算法时间要求严格的场景。

表1　3种分割算法运行时间表　/s

图2　3种不同的方法Cameraman分割结果

图3　3种不同的方法Car分割结果

5　结束语

提出了一种形态学分水岭算法与Normalized Cut算法相结合的组合分割方法，该方法能以接近5～10倍的运行效率获得近似Normalized Cut方法的分割精度，有效消除了传统分水岭方法中的过分割问题，并具有较好的实用性。

[1]吕建平,司维.基于分水岭和种子生长的彩色图像分割[J].西安邮电大学学报,2014,19(2):52-55.

[2]谢勰,王辉,张雪锋.图像阈值分割技术中的部分和算法综述[J].西安邮电大学学报,2011,16(3):1-5.

[3]Wu Z,Leahy R.Anoptimal graph theoretic approach to data clustering:theory and its applicationto image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(11):1101-1113.

[4]Shi J,Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[5]Vincent L,Soille P.Watershed in digitalspaces:anefficientalgorithmbased on immersion simulation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1991,13(6):583-598.

[6]Gonzalez R C,Woods R E.Digitalimage processing[M].阮秋琦,阮宇智,译.北京:电子工业出社,2004.

[7]姚敏.数字图像处理[M].北京:机械工业出版社,2006.

[8]Rafael C Gonzalez,Richard E Woods.数字图像处理[M].阮秋琦,阮宇智,译.2版.北京:电子工业出版社,2003.

[9]黄一岑,沈一帆.基于Normalized Cut 的图像分割改进算法[J].计算机工程与应用,2008,44(34):179-181.

[10]任爱红,白婷婷.结合图论Normalized Cut方法的彩色图像分割研究[J].甘肃科学学报,2012,24(3):147-150.

A Normalized Cut Image Segmentation Method Based on Morphological Watersheds

LIU Hepeng, LÜ Jianping

(School of Computer Science and Technology, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In view of the over-segmentation caused by traditional watershed segmentation, a normalized cut image segmentation method combined on morphological watershed transformation is proposed in this paper. On the basis of traditional watershed segmentation, the morphology algorithm is adopted for initial segmentation, and the average grey value of each segmented area is used as input parameters for the normalized cut algorithm to complete the image segmentation. The results show that combined algorithm not only avoids over-segmentation, but also achieves as good accuracy as the normalized cut algorithm segmentation.

simage segmentation; watershed segmentation; morphology; Normalized Cut

2015- 12- 18

刘贺鹏(1988-)，男，硕士研究生。研究方向：数字图像处理。吕建平(1957-)，男，教授。研究方向：数字图像处理。

10.16180/j.cnki.issn1007-7820.2016.09.004

TP391.41

A

1007-7820(2016)09-012-03