基于标准割(Normalized cut)算法图像分割方法

安文波

(中国刑事警察学院，辽宁 沈阳 110854)

1 图像分割简介

图像分割是图像处理中的一项至关重要的技术。自20世纪70年代开始，图像分割技术一直备受人们的高度重视，到目前为止已经有很多的分割方法，从图像分割的依据出发，分割方法分为非连续性分割和相似性分割[1]。近年来有很多不同领域的学者们提出的新理论、新方法与图像分割相结合而形成多种新型分割技术，如聚类分析、图理论、小波变换、人工神经网络等分割方法，这些多领域、多类型的分割方法的提出对于图像分割技术的完善有着重要的作用。图1是一般的图像处理过程，从图中可以看出图像分割是介于图像预处理和图像识别之间，在图像处理当中起着承上启下的作用，一方面它是准确提取目标物的处理手段，使人们能够得到有意义的感兴趣对象，另一方面它能够做到目标准确的识别，特征准确的提取，参数准确的测量等使图像变得更为简明、抽象的形式展现在观察者面前，更容易进行视觉分析和模式识别，并且对后续的图像识别、分析和理解能够达到跟高的层次。

图1 图像处理过程

2 图论和阈值化分割方法

2.1 图论分割的原理

(1)

图论的图像划分领域应用到图像分割中来，形成了基于图论的图像分割方法该方法是将原图二值化形成一个带权值的映射图，首先给定几个基本定义如图2所示[2]，图中的点对应着像素点或区域，权值数的大小表示着两个点之间的相关性，通过权值的总和最小而形成的最小代价路线，这条线使得图像分割得以实现。

图2 图论分割原理

通过图2可以看出，图论方法是应用数学的一个计算方法，将待分割的图片映射成为一幅无向加权图，图中的点对应图像的像素点，且像素点构成图中的顶点集，每个点对应的数字表示图像的灰度值，通过权值公式计算两个像素的权值并寻找出一条权值和最小的路径完成图像分割。

图3 图像分割

图3在使用MATLAB软件进行的图论分割方法分割出来的图像，在MATLAB中通过计算灰度级强度差找到权值求和最小也就是代价最小的路径完成分割。

2.2 阈值分割的原理

阈值分割方法是图像分割的一项悠久而又关键的技术，所谓阈值就是事先设定一个值，阈值分割就是对图像的灰度分成不同的等级，然后设定一个阈值与图像中不同的灰度等级进行比较，根据比较将图像灰度像素分成两个区域，分别是目标区域和背景区域，从而达到分割的目的。假定图像的设定的阈值为n，那么图像中的像素等级也就被阈值分成两部分，输入图像f(x,y)，输出图像f′(x,y)，则：

这就是阈值化分割方法。图4是使用单个阈值方法将图像分割为目标物和背景图两部分

图4 单个阈值分割方法

由于实际需要的图像目标与背景图之间存在许多灰度等级，那么就需要两个或两个以上阈值对图像进行分割提取目标物。如(n1,n2)作为图像分割的阈值，那么就需要两个公式对图像进行二值化处理。

图5 双阈值图像分割

如图5就是使用两个阈值将图像分割为三个级别。

目前，由于图像中往往有各种噪声，最佳阈值的选择仍然是一项难题，在寻找最短路径是非常耗费时间的，如果提高速度那么就会使得精度会降低，如果提高选择精度那么又会很耗费时间，急需找到以一种合适的算法处理最佳阈值的选择问题。到目前为止，阈值分割方法有很多，较为经典的方法有：基于直方图的Ramesh阈值分割方法；基于空间信息的Pal阈值图像分割方法；基于属性相似度Pikaz阈值图像分割方法；基于熵的Kapur阈值图像分割方法；基于聚类分割的Kittler阈值图像分割方法；以及基于局部信息的Yanowitz阈值图像分割方法；这些方法有自己独特的优点，也有解决不了的缺点，仍然有很多学者在这个方面进行深刻的研究，尝试者解决这一难题。

2.3 改进的图像分割算法

虽然基于图论的分割方法在图像处理上有很好的发展空间和应用效果，但是单纯的使用这种方法仍然存在一些不足和缺陷，在区间数据很接近的情况下使用这种方法的弊端体现的很明显。因此，针对其不足的地方进行改进，使这种方法在图像分割领域能有更好的应用前景。阈值化图像分割是一种区域分割技术，通过设置一个合理的阈值，然后将图像中所有的灰度值与之进行比较，大于或等于阈值的像素被划分为分离出的物体，小于阈值的部分就是物体之外的。因此，只要能够选择到最佳阈值图像的分割就很容易实现。这种简单易行的方法和基于图论的图像分割方法相结合，能够很好的弥补图论方法在图像分割当中的不足之处。针对以上问题，采用 标准割Normalized Cut 割集方法[3]与阈值结合来实现目标和背景的精确分离，一种典型的分割图像分割方法。

3 标准割(Normalized cut)算法

如前文中所提到的，将一幅图表示成空间点集的无向加权图G=(A,B)其中V是定点集合，E是两点连接的边集合，w(u,v)是对两个节点连接成的边赋予权值 ，将图像分割成A和B两个部分的点集，其中V是A和B的集合V=A+B，A和B之间的差异程度可表示为移去两区间所有节点连接的边的权值之和所付出的代价，称为割cut，表示为：

(4)

Shi和Malik为了获得较好的分离效果，提出了提 Normalized Cut 标准割算法，其公式为：

(5)

近些年来，图像分割方法中谱聚类方法一直是大家研究的热门，诸如此类方法有很多种，如标准分割(Normalized cut，Ncut)算法、比例分割(Ratio cut，Rcut)方法[4]、以及最小最大割(Min-max cut，Mcut)算法[5]等。该类方法是将图构造一个带带顶点集的加权图，然后通过求矩阵的特征值和特征向量来获得谱聚类的结果。本文针对标准割算法进行了进一步的研究，该方法可以很好的克服被划分出来的图像中的孤立点，但是由于计算量较大且类间重叠较大时易出现弯斜划分。 图6是采用核磁拍摄的PDWI图(质子密度加权图)，并通过MATLAB进行了图像分割。采用改进后的标准割算法对图像进行分割，能够有效的克服前文中所产生的图像孤立点问题。

图6 真实图像分割

图中边缘部分为脑袋颅骨，中间部分为脑组织，从可以看出才用此方法可以很容易的对颅骨和脑组织进行图像分割。

4 结论

基于当今时代的信息发展的迅速性和有效性，数字图像在人们当中越来越受到重视，它是人们获取信息的主要方式和手段，数字图像已经渗透生活当中各个领域、各个技术行业，有些时候人们为了突出图像当中比较重要的部分或者需要图像当中的某些信息，这就需要对数字图像处理技术的要求也在不断的提高，对于把图像当中感兴趣的部分提取出来所需要的方法，各行业的人员都在进行不断的创新，对于其中的疑点和难点也一直在不断的解决，因此对于新的理论、新的技术应用在图像分割领域是非常重要的，本文针介绍的图像分割方法