基于图论的Normalized Cut图像分割算法

摘 要：基于图论的图像分割算法是近年来图像分割领域研究的的热点问题，该文就其Normalized Cut算法进行了简要的介绍，并利用其对图像进行了仿真分割。

关键词：图论 图像 分割算法

中图分类号：TP391 文献标识码：A 文章编号：1674-098X（2014）06（c）-0049-01

1 图论相关背景知识

图论（Graph Theory），起源于18世纪欧拉研究和解决的柯尼斯堡七桥问题（Konigsberg），是研究顶点与边所组成的图形的理论与方法，20世纪50年代初刚刚开始发展，以图（Graph）作为研究对象，是离散数学的分支。近年来，计算机技术在各个领域的被广泛应用，使得图论其在电子、信息论等学科中的应用也取得了很大的进展。

2 基于图论的图像分割准则

基于图论的图像分割方法主要是利用分割准则实现的，到目前为止，基于图论的图像分割准则主要被分为基于特征向量分割准则、基于区域合并分割准则、与基于归一化割分割准则三类。

（3）利用步骤（2）中求出的第二小特征向量将图像分割为两部分。

（4）判断图像是否还需要做进一步的分割，若需要继续分割，则递归调用该算法完成图像的分割。通常，作者设定的最大允许SNcut值或分割区域所包含的最小像素数SArea作为是否需要继续分割判断依据，作为Ncut算法最终迭代停止条件。

3.2 具体分割实例

（1）本文涉及到测试用颅脑MR图像均为灰度图像，为了实现肿瘤图像的分割，衡量像素间相似度矩阵W选择如公式（4）所示：

（4）

在公式（4）中，F（i）用于表示图像像素灰度值，x（i）为图像像素按列元素从上至下重新排列后位置，在引入像素灰度信息的同时也引入像素坐标信息。、为控制像素点间值域差异与空域差异的敏感程度参数，r为两个像素点之间设定的有效距离。

（2）算法中设置迭代次数为1000，两个算法停止条件，sNcut表示Ncut所允许的最小值，sArea则表示Ncut分割区域允许包括的最小像素数，以先达到者为算法停止条件。

4 结语

本章内容首先对经典Normalized Cut所涉及到的理论及相关知识做了简要介绍，并利用matlabR2010a对Normalized Cut进行算法仿真，并将其应用到相关图像分割中，该算法基本可以将目标从背景图像中分割出来，但分割的精度有待于进一步提高，这与分割中相关参数的设定、权重矩阵的选取有关，将在以后做进一步的研究。

参考文献

[1] 孙惠泉.图论及其应用[M].科学出版社，2004：1-2.

[2] 刘建龙.基于图论的图像分割算法研究[D].哈尔滨工业大学，2006.

[3] 孙亮.基于图论的文档图像分割应用研究[D].山东师范大学，2009.

[4] 陶文兵，金海.一种新的基于图谱理论的图像阈值分割方法[J].计算机学报，2007（1）：110-119.

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