基于图论的图像分割算法分析研究

杨先花

(闽南理工学院，福建石狮 362700)

现代社会中，数字图像是人们获取信息的重要来源。图像分割是从图像预处理到图像识别和分析理解的关键步骤，是把图像分成各具特色的区域并提取出感兴趣的目标的技术和过程。图像分割的新方法不断出现，但每一种方法都有其侧重点，局限性较大，因此，不断融入新知识对现存图像分割算法整合优化成为研究的热点［1－2］。

基于图论的图像分割算法是目前图像处理领域的一个研究热点，它把数学中的图的理论应用到图像分割中，本文对基于图论的图像分割算法中归一化划分准则与阈值化的图像分割方法进行结合，将权值计算公式进行改进，较好的体现了像素点间的相似性，通过实验对比，得到较好地整合效果。

1 基于图论的图像分割算法介绍

1.1 基于图论的图像分割算法概述

基于图论的图像分割算法的基本思想:将图像映射为带权的无向图，从而把图像的结构与图的结构一一对应，将图像的像素点与图中的顶点对应，在图像分割中利用图的最佳划分理论，从而将复杂的图像分割问题简化为最优化分问题［3］。

图像分割中使用的图是无向加权图，这样的图G(V，E)由节点V(图像的像素)和节点间的连接边E组成的一种拓扑图形，不同节点间的连接有不同的权值W，权值反映了两个像素节点间的相似度，即属于同一区域的可能性。

把图G划分为A、B两部分，且A和B间满足:A∩B=φA∪B=Vex，A、B之间的差异程度即所有移走的边的权值总和。

1.2 基于图论的图像分割算法的发展

基于图论的图像分割算法的研究是近几年国内外图像分割领域的一个新研究热点，主要体现在:最优割集的设计，分割中图谱方法的应用，以及算法实现上的快速性［4］。目前较为代表性的方法见表1。

表1 基于图论的图像分割算法的发展Tab.1 Development of image segmentation algorithms based on graph theory

这3种代表算法都是通过对图的某种特性研究从而建立相应的能量函数，通过对能量函数取得极小值，即得到图理论对应图像的最佳分组。

1.3 常见典型图割集准则［5］

(1)Minimum Cut(最小割)

最小割集准则简单常见，适用于较小分割，定义为公式 (1)，通过树图缩减的方式来实现该割集的图像分割，优点是求解简单，缺点是易造成孤立点的分割。

(2)Average Cut(平均割)

平均割集准则定义为公式 (2)，该割集的实现方式是通过求解方程(D-W)Z=λZ标准特征系统来实现，该割集易出现过分割。

(3)Min－Max Cut(最大最小割)

(4)Normalize Cut(归一化割)

雨落先表示了歉意，说许姐，非常不好意思，请您来其实不是因为证书，而是想和您商量件事，一件非常重要的事。许沁略显诧异，笑道，什么事啊，搞得这么紧张兮兮的。玉敏刚要张口，雨落用手止住了，然后平静地说了。

归一化割集准则定义为公式 (4)，该准则是通过求解方程(D-W)Z=λZ标准特征系统来实现，特点是能有效克服划分孤立点的问题，但类间重叠较大时易出现歪斜划分。

2 阈值化改进分割算法

2.1 阈值化图像分割方法

阈值分割是一种简单、经典的图像分割技术，运算速度快，性能稳定，被应用于血液细胞图像的分割、产品质量检测等许多领域［6］。阈值分割的基本原理是通过对图像的灰度直方图进行数学统计，选择一个或多个阈值将像素划分成若干类。在实际应用中，图像受噪声和其他客观因素的影响较大，图像质量差，最佳阈值很难确定。因此，如何选取一个最佳阈值是阈值分割法的关键和难点。全局分割、局部分割和动态分割是常规三种最佳阈值的选择方法，但各有弊端，新的方法不断出现。

2.2 基于Normalized Cut准则的图像分割方法

Shi和Malik等人提出Ncut准则描述两类间的分离度，优点是通过对像素点位置和亮度信息的确定避免了划分孤立点的问题，取得较好的分割效果，缺点是忽略了像素点与其邻域的空间关系，对噪声敏感。

2.3 改进的归一化阈值图像分割算法

该方法采用Normalized Cut准则与图像的阈值分割联合起来区分目标和背景，得到了良好地分割效果。

改进一:将以往描述图像像素个数的权值矩阵用表示图像亮度的灰度值的权值矩阵代替，图像的灰度值更鲜明反映了像素间的亮度差异，图像的空间信息反映了像素点间相互关联的信息，大大节约了算法的时间和存储空间。权值公式定义为:

M(u)是节点u与其四个相邻点的灰度值的中值，体现像素点与其邻域的空间信息的值。

改进二:将像素点与其邻域的空间信息反映到权值计算中，降低了噪声。

对一幅M×N的数字图像f(x，y)，图像灰度级为L，像素点坐标为V，则图像信息用图理论描述如下:

图1 原噪声图片Fig.1 Original noise picture

通过分析，体现像素间的相关性的w(u，v)取值影响重大，它决定着图像分割的质量。Tmin就是阈值分割中的门限阈值，也是改进后基于归一化的图谱划分测度的图像阈值化分割准则，门限的选取取决于图顶点之间的边权值w(u，v)。

在MATLAB环境下，设置数据得到效果图如图1～图3所示，可以看出图3效果较好，有效减少了噪声。

图2 改进前分割图Fig.2 Segmentation map before improvement

图3 改进后分割图Fig.3 Segmentation map after improvement

3 结束语

本文主要介绍分析了基于图论的图像分割算法及其优缺点，并对改进的阈值化归一分割算法进行设计、实验对比，取得了较好地分割效果，实验证明，相对于普通图像阈值分割算法，阈值化归一分割算法在局部处理和噪声抑制上有较好的效果;较区域分割算法，不易产生过分割。但是算法也存在不足，比如算法在实现速度上，效果还不是很理想，如何找到快速的求解过程，找到通用性较好的权值计算公式是今后研究的方向。

【参 考 文 献】

［1］程 伟，梁 萍．数学形态学在施切单板缺陷图像分割中的研究［J］．林业机械与木工设备，2011，39(2):25 －27．

［2］邹丽晖，白雪冰．数学形态学在木材表面缺陷图像分割后处理中的应用［J］．林业机械与木工设备，2006(12):40－42．

［3］石 美．基于图论的阈值化图像分割方法研究［D］．合肥:合肥工业大学，2011．

［4］杨 帆，廖庆敏．基于图论的图像分割算法的分析与研究［J］．视频技术．2006(7):80－83．

［5］Jiang M．Digital image processing course［R］．Technical Report，Department of Information Science．School of Mathematics．Peking University，2001．

［6］胡 敏，石 美，汪荣贵．一种具有抗噪性的图像分割方法［J］．计算机工程．2011，37(8):231 －235．