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

张 健，李宏升

(黄淮学院 信息工程学院，河南 驻马店 463000)

1 引 言

图像分割是按照某种算法把它分成多个区域并将感兴趣的目标提取出来[1]，在图像处理领域中属于重要组成部分，对于分析目标特征具有重要意义。

基于图论的图像分割国内研究为：常见的方法有图论最小生成树方法、图论主集等[2]，它们的一个共同特点是将图像中的像素以聚类或者分组的方法进行划分，进而完成对图像的分割，但是不会将渐变区域与常数区域合并，使图像出现误分割；随后图论最优分割模型[3]，可以得到图的全局性质，但是需要构造的度量函数并非最佳，算法的时间复杂度较高，对复杂的图像进行分割时，会导致图像分割速度较慢，从而在很多实时视觉处理场合无法采用。国外研究为：Wu和Leahy提出用图论最小割进行图像分割[4]，利用分割的像素之间相似性最小化作为分割标准，但该方法易出现较小的分割；Shi和Malik提出了一种改进的归一化割的分割方法[5]，通过计算所有连接边的权值在整个图的边集权值中所占的分量，消除Wu和Leahy方法的较小分割偏向，但是受图像大小限制，难以实用；Grady和Schwartz针对Shi和Malik的问题，提出了图论等周分割的方法[6]，这种方法不需要相似矩阵的重构操作，复杂图像出现误分割；Felzenszwalb提出采用图论全局信息进行分割[7]，采用近邻函数和灰度函数作为权值和相似度函数，但分割精度上受到一定影响。

本文采取基于图论阈值对图像分割，首先构造图论和图像的映射函数关系，每个顶点通过点来映射，每条边通过线来映射；然后用基于区域属性的图像边缘决策表，不同像素点或不同组像素点之间的灰度特征差作为权重系数，通过基于决策属性权重来构造像素联系图；接着采用聚类计算像素到目标类和背景类的相似程度，最小生成树策略解决伪割集问题；最后给出图像阈值设定以及算法流程。实验仿真显示分割图像边缘信息的效果明显清晰，消除了图像分割中存在的过合并和欠合并现象，且信息熵大。

2 算法描述

2.1 图像像素属性

2.1.1 基于关联函数的图像像素空间连接

将一幅图像视为一个带权的无向图G，G为有序三元组[V(G)，E(G)，χG]，其中V(G)是非空的顶点集，E(G)是不与V(G)相交的边集，而χG是关联函数，把欲分割图像中每一个像素作为图论数据集合中的顶点，则:

χG(e)=uv,

(1)

其中：u、v以像素为端点的分割线段表示，使图G的每条边对应图G的无序顶点对[8]。这样每个顶点通过点来映射，每条边通过线来映射，线连接着映射该边端点的点，连接同一条边的两顶点。图1给出了4个像素点的连接图，其中V(G)=(v1,v2,v3,v4)为顶点集，E(G)=(v1v2,v1v3,v1v4,v2v3,v2v4,v3v4)为无向边集。

图1 4个像素点的连接Fig.1 Connection of four pixels

2.1.2 基于区域属性的图像边缘决策表

据像素灰度的不同把原始图像分为若干不连通的区域[9]，w(vi,vj)为e(vi,vj)∈χG(e)对应的 2 个区域之间的边缘权重，设图像分割边缘决策表为:

S={U,C∪D,V,F},

(2)

其中：U={x1,x2,…,xn}为图像分割边缘论域，C={a1,a2,…,am}和D分别称为图像边缘条件属性集和分割决策属性集，∀a∈C，Va=[la,ra]⊂R是实值区间。决策表里有多个属性，并且对每一个属性，任意两个像素区域间都有这个属性关系，因此，任意两个像素区域间都要连 |C∪D|条边，构成了以像素区域为属性关系的图像。表1给出了基于属性关系像素区域间决策表。

表1像素区域间的属性关系决策表

Tab.1 Relationship of decision table between regions of pixels

U12345678a0．911．31．31．41．41．64b20．5312133d10010111

不同像素点或不同组像素点之间的灰度特征差作为权重系数，通过基于决策属性权重来构造像素联系图[10]，结果如图2所示，其中标号1代表的权重是{a[0.8，0.9]，b[2，0.5]}；2代表的权重是{a[0.9，0.6]，b[0.9，0.5]}；3是{a[0.9，0.1]，b[0.9，0.5]}；4是{a[0.6，0.9]，b[3，0.5]}；5是{a[4，0.9]，b[3，0.5]}；6是{a[0.8，0.3]，b[2，3]}；7是{a[1.4，1.3]，b[0.9，3]}；8是{a[1.3，1.3]，b[0.9，3]}；9是{a[0.6，0.3]，b[3，3]}；10是{a[4，1.3]，b[3，3]}；11是{a[0.8，0.4]，b[2，2]}；12是{a[0.7，0.4]，b[0.9，2]}；13是{a[0.3，1.4]，b[0.9，2]}；14是{a[0.6，0.4]，b[3，2]}；15是{a[4，0.4]，b[3，2]}。

图2 基于决策属性权重的像素联系图Fig.2 Pixel connection diagram based on decision of weight

2.2 图像割集划分

2.2.1 图像割集区域相似度

假设目标像素的聚类集合为A，背景像素的聚类集合为B,像素灰度k到目标类的最小距离d1到背景类的最小距离d2，即:

(3)

则像素到目标类和背景类的相似程度大小为：

(4)

其中:η[χG(e)=1]标记像素与目标区域更相似，它能够保证与目标更相似的像素被划分到目标区域[11]，η[χG(e)=0]标记像素与背景区域更相似，它能够保证与背景更相似的像素被划分到背景区域。

2.2.2 图像割集最小决策树

计算像素与目标和背景区域相似度后，需要把虚假像素相似度进行区分，评价各个不同分类状态，使相似度聚类问题转化为数据优化问题[12]。设图G中分割区域边的权重和为：

(5)

式中：权重最小的w(T)为图G的最小生成树。

假设集合P用于存放G的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为P={v1}(假设构造最小生成树时，从顶点v1出发)，集合Q的初值为Q=Φ。从所有p∈P、v∈(V-P)选取具有最小权值的边pv，将顶点v加入集合P中，将边pv加入集合Q中，如此不断重复，直到P=V时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边[13]，从而有效地解决分割过程中出现的伪割集以为目标分割不完整的问题。

2.2.3 合并区域判定

图像割集最小决策树形成后，需要使区域内部差别尽可能小，区域之间差别尽可能大，使用判定函数判定2个区域是分割还是合并。设欲分割区域内部像素点间相似性的特征量φ1,φ1分割区域最小生成树中边缘权重的最大值：

(6)

欲分割2个相邻区域内之间相似性的特征量

(7)

区域间的差异值：

γi,j=min(φ2,φ3),

(8)

合并判决条件为：

(9)

当满足合并判决条件时,说明这两个区域内像素节点间的相似性较大,反之,则彼此之间的关联性较低[14-15]。

2.3 图像阈值分割

设阈值T用于控制分割的精度,其定义为:

T=ζγi,j,

(10)

当常数ζ较大时，分割效果较粗糙,较小时,分割效果较精细,不同ζ值会得到不同的分割效果，设定常数：

(11)

2.4 算法过程

①输入图像，采用基于关联函数的图像像素连通区域的计算权重；

②边缘决策表对连通区域划分；

③最小决策树计算区域相似度；

④判断合并条件,满足执行步骤5，否则执行步骤2；

⑤ζ精度控制；

⑥输出图像。

3 实验仿真

利用本文方法对不同图像进行分割实验,并与其他方法进行比较,同时对不同算法的分割结果采用定量实验准则进行相应的评价分析。

3.1 视觉分割效果

采用3种复杂图像,不同算法仿真结果如图3所示。

其中(a1)、(b1)、(c1)为待分割的原始图像，(a2)、(b2)、(c2)是图论主集法分割效果，(a3)、(b3)、(c3)是图论最优分割模型分割效果，(a4)、(b4)、(c4)是图论最小分割模型分割效果，(a5)、(b5)、(c5)是图论等周分割法分割效果，(a6)、(b6)、(c6)是本文分割效果，从分割效果上可以看出，本文提出的算法分割得到的图像边缘信息的效果明显清晰，一定程度上消除了图像分割中存在的过合并和欠合并现象。这是因为本文算法对分割区域生成最小决策树后还要计算相邻区域的差异性。

3.2 定性分析

熵值反映图像包含的平均信息量，采用熵值对分割效果进行评价，熵H定义为：

(12)

其中：pi为像素级为i∈[0，255]的出现的相对频率。H越大则图像的平均信息量越大，表2给出了分割后的图像信息熵对比。

表2 分割后的图像信息熵对比

本文算法分割后的图像信息熵比较大，说明分割图像得到的信息比其他算法大，这是因为当满足合并判决条件时,不需要分割，则保留了图像信息。

3.3 算法性能分析

为了比较不同算法的性能，表3给出了不同算法的错割率、处理时间。

由表3的结果证明，本文算法处理时间比其它算法处理时间至少要节约1 s时间,具有实时性，错割率较低，可以保证分割的效率，这是因为对合并区域判定后使区域内部差别尽可能小，区域之间差别尽可能大。

表3 不同算法的错割率、处理时间对此

4 结 论

采用图论阈值算法，构造图论和图像的映射函数关系，每个顶点通过点来映射，每条边通过线来映射；用基于区域属性的图像边缘决策表，不同像素点或不同组像素点之间的灰度特征差作为权重系数，通过基于决策属性权重来构造像素联系图；接着采用聚类计算像素到目标类和背景类的相似程度，最小生成树策略解决伪割集问题；最后给出图像阈值设定以及算法流程。得出分割图像边缘信息的效果明显清晰，消除了图像分割中存在的过合并和欠合并现象，且信息熵大，为以后研究图像分割提供一种新的思路。

[1] 张俊娜,冯云芝.基于量子最大熵多阈值算法的图像分割研究[J].激光与红外,2013,43(5):578-582.

Zhang J N, Feng Y Z. Image segmentation research based on quantum maximum entropy algorithm [J].LaserandInfrared,2013,43(5):578-582.(in Chinese)

[2] Cheng L J, Ding Y S, Hao K R,etal. An ensemble kernel classifier with immune clonal selection algorithm for automatic discriminant of primary open- angle glaucoma [J].NeuroComputing, 2012, 83(4):1-11.

[3] 张田.一种改进的基于图的图像分割方法[J].西华大学学报,2011,30(1):61-64.

Zhang T. An Improved graph-based image segmentation method [J].JournalofXihuaUniversity,2011,30(1):61-64.(in Chinese)

[4] Wu Z, Leahy R. An optimal graph theoretic approach to data clustering: theory and its application to image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 1993, 15(11):1101-1113.

[5] Shi J, Malik J. Normalized cuts and image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2000, 22(8):888-905.

[6] Grady L, Schwartz E L. Isoperimetric graph partitioning for image segmentation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2006, 28(3):469-475.

[7] Felzenszwalb P. Efficient graph-based image segmentation [J].InternationalJournalofComputerVision,2004, 59(2):167-181.

[8] 陈丽娟.矩阵论中的图论匹配法[J].南京信息工程大学学报,2011,3(6):571-573.

Chen L J . Matching method of graph theory in matrix theory [J].JournalofNanjingUniversityofInformationScienceandTechnology,2011,3(6):571-573.(in Chinese)

[9] 方富贵.图论的算法和应用研究[J].计算机与数字工程,2012,40(2):115-117.

Fang F G. Study on the Algorithm and applications in graph theory [J].ComputerandDigitalEngineering,2012,40(2):115-117. (in Chinese)

[10] 卢鹏,王锡淮,肖健梅.连续属性决策表离散化的图论方法[J].计算机工程与应用,2012,48(6):13-16.

Lu P, Wang X H, Xiao J M. Graph method of discretization of decision table with continuous attributes [J].ComputerEngineeringandApplications,2012,48(6):13-16. (in Chinese)

[11] 洪汉玉,颜露新,郭祥云,等.生产线复杂场景条件下的动目标提取方法[J].华中科技大学学报,2012,40(7):57-61.

Hong H Y,Yan L X,Guo X Y,etal. Approach to extract moving targets from production line under complex scenes [J].JournalofHuazhongUniversityofScienceAndTechnology,2012,40(7):57-61. (in Chinese)

[12] 段薇,马丽,路向阳.基于信息增益和最小距离分类的决策树改进算法[J].科学技术与工程,2013,13(6):1643-1646.

Duan W, Ma L, Lu X Y. An improved algorithm of decision tree based on information gain and minimum distance classification [J].ScienceTechnologyandEngineering,2013,13(6):1643-1646. (in Chinese)

[13] 熊小华,刘艳芳,宁爱兵.图的Steiner最小树的竞争决策算法[J].上海理工大学学报,2012,34(5):1643-1646.

Xiong X H, Liu Y F, Ning A B. Competitive decision algorithm for the steiner minimal tree problem in graphs[J].JournalofUniversityofShanghaiforScienceandTechnology,2012,34(5):1643-1646. (in Chinese)

[14] 李荪,李哲英,刘佳,等.图论分割算法算子消耗模型OCM的建立与分析[J].电子测量与仪器学报,2012,26(11):1011-1018.

Li S,Li Z Y, Liu J,etal. Operator cost model and analysis based on graph-based segmentation [J].JournalofElectronicMeasurementandInstrument,2012,26(11):1011-1018. (in Chinese)

[15] 张乾,冯夫健,林鑫,等.一种基于图论的图像分割算法[J].计算机工程,2012,38(18):194-197.

Zhang Q,Feng F J,lin X,etal. An image segmentation algorithm based on graph theory [J].ComputerEngineering,2012,38(18):194-197. (in Chinese)