复杂网络理论在彩色图像分割中的应用研究

，，，

(西安理工大学 自动化与信息工程学院，西安 710048)

0 引言

图像分割是一种根据纹理，颜色，灰度等视觉特征将图像划分成具有独特性质的目标区域的技术和过程[1]，在计算机视觉领域中一直发挥着非常重要的作用。近年来，基于图论的图像分割方法已成为国内外的一个研究热点。现有的基于图论的方法[2-3]很多，其中基于图论的最小生成树算法因其简单，高效且能获取全局信息，在图像分割中得到了广泛应用，但其使用自适应的全局阈值进行图像分割，分割效果并不理想尤其在图像细节方面。复杂网络理论与图像分割方法相结合，可以避免单一算法的不足，并为该领域提供了更多的选择性。2009年，Backes A R提出一种新的描述图像边缘特征的方法，利用复杂网络给图像边缘特征建模[4]，该方法不仅比传统图论法对图像边缘轮廓具有更好的表示结果而且它可以表示具有间隙或不完整信息的图像边缘轮廓；复杂网络可以很好的表示图像的纹理特征[5]，节点表示像素点，节点之间的连接表示像素点之间的相似性，提取场景中的全局纹理特征，不同类型的纹理呈现出不同的节点度分布。最近，Mourchid Y提出将图像用图形表示[6]，通过应用社区检测算法计算出单一模块化特征度量，该度量对于图像旋转和小失真是不变的。

基于复杂网络理论在图像处理应用中展现的优越性能，本文将彩色图像分割与复杂网络理论相结合，根据像素点之间的相似性，对大量的图像数据建模，从复杂网络的角度构造社团网络结构图，然后用社团检测算法进行社团划分，对图像相似像素聚类，进而实现彩色图像分割。社团检测一直是复杂网络学科中研究的热点，到目前为止，比较常用的算法有GN 算法[7]、Newman 快速算法[8]等。GN 算法是由Girvan 和 Newman 在2001年提出，该算法思想基础为分裂法，依次删除网络中边介数值最高的边，当算法结束时整个网络将被划分成不同的社团。但是GN算法有两个缺点：其中一个为该方法和其他传统方法一样都无法判断一个网络最终可以被划分成社团的个数。另外一个缺点就是速度较慢。Newman 快速算法以贪心算法思想为基础的凝聚算法。该算法可用于大型复杂网络，在社区划分过程中，经过计算比较得到最大的模块度值Q，所对应的社区结构就是该网络最好的社区结构组成，但是该算法准确度没有GN算法高。本文采用的是目前比较流行的社团检测算法即谱聚类算法，谱聚类算法能够广泛的应用于任意的数据空间上，尤其在运行高维数据如图像数据时，相比于传统的聚类算法，该算法更加完整、更加全面，且在得到社团划分结果的质量方面比其他算法要好。

在本文工作中，考虑了一种基于社团检测算法的特征，称为模块化[9]，这是目前使用最广泛的质量函数，当基础社团结构未知时，比较不同社团检测算法对真实数据的有效性。实验采用BSDS300图像库[10]，并且通过实验结果表明该方法在精度方面优于传统图论分割方法，可以获得更好的分割结果。

1 复杂网络的图像表示

Girvan和Newman在2002年最先提出网络社团结构的概念[11]，即网络中存在内部连接紧密的节点群而节点群之间连接稀疏。复杂网络的社团检测算法是这几年许多不同的科学领域研究的热点问题。本文从复杂网络的角度对彩色图像进行建模，图像中的像素点表示网络中的节点，像素之间的相似性表示网络之间的连接。将网络社团结构图表示为一个数学模型，即G=(V,E)，V表示由n个节点组成的点集，E是由m条连接边构成的边集。对于一副具有R、G、B三个颜色分量的彩色图像来说，每个像素点都可以表示为RGB颜色空间中的一个节点xi。利用下面的公式(1)，按照从左到右，从上到下的顺序计算每一个像素点4邻域的相似度，首先需构造n维零矩阵A，后需计算目标像素点与其邻域像素点之间的RGB欧式距离，具体公式如下：

(1)

其中：xi(k)表示节点i在第k个颜色分量上的取值，k=1,2,3分别表示R,G,B分量。

若d(xi,xj)小于等于阈值T，则认为两个像素点足够相似，用一条边将其连接并在矩阵A相应元素aij记为1，否则认为两像素点之间不相似，aij记为0。其中A为相似度矩阵同时也是稀疏的邻接矩阵，在存储时可以节省很大的空间。本文可根据A构造无向网络拓扑图。如公式(2)所述：

(2)

从上式中显然可以看出，阈值T对网络拓扑结构的影响产生着决定性作用。如果选取阈值T过小将导致网络连接过于稀疏，但阈值T也不能过大，因为阈值T越大丢失的图像信息就越多，这会影响最终的图像分割结果的质量。目前，还只能依靠经验或者通过实验来确定阈值T。本文根据实验所得的距离d的数据，设置一个阈值T的取值范围[dmin,dmax]，在这个范围内采用合适的步长，选取阈值，不同的阈值对应不同的网络社团结构图，之后选取结构较好的网络图进行社团检测。

2 谱聚类社团检测算法

谱聚类算法[12-13]能够广泛的应用于任意的数据空间上，理论基础是以拉普拉斯矩阵研究为主的谱图思想，而其核心的技术为通过对样本数据进行降维处理后进行聚类。

2.1 图的拉普拉斯矩阵

(1)对于任意的p∈Rn有：

(3)

(2)Lsym是半正定的矩阵并且有n个非负的实数特征值，0=λ1≤λ2≤…λn。

2.2 图划分准则

谱聚类算法的理论基础为谱图理论，用到的主要思想为图分割法。在图G中，对于给定数量K个子集，将每个子集可以分别表示为A1,A2,…Ak，且它们之间没有交集，图的割[14]可以适当的定义为：

(4)

K的指标向量可以定义为hj=(h1,j,...,hn,j)，其中:

(5)

(6)

其中:Tr表示矩阵的迹。

(7)

其中:TT′=1，Lsym的前k个特征向量构成矩阵T的列，每个特征向量与该函数的值相对应。由此，本文可以通过对T进行聚类得到k个子集。

2.3 k-means聚类算法

谱聚类算法最后一步经常利用k-means聚类算法[15]对降维后的数据进行聚类分析，k-means算法是一种基于聚类质心技术，具有算法简单，运行速度快等优点。输入参数k，可将数据样本聚集成k个不同的组，在同一个组内数据样本的相似度高，不同组之间数据样本不相似。

算法过程如下：首先从数据样本中选取k个对象作为初始均值，即作为初始的类的中心，之后对于数据样本中剩余的每个对象，按照它到每个组中心的距离，将它归入到距离最相近的组中，遍历完所有的对象后，再重新计算每个组的新均值作为该组的新中心。为了能达到全局最优，重复上述步骤至平方误差准则最小时结束。通过k-means算法对处理后图像数据进行聚类，将像素点划分成K个类别，相应的相似像素在一个归属类，最终实现图像分割。

3 本文算法模型

将基于谱聚类思想的复杂网络社团结构发现算法应用于彩色图像分割中主要分为三个阶段：

第一阶段将彩色图像利用复杂网络理论抽象为一个社团网络结构图，其中利用一定的相似性度量计算，将原图像矩阵转换为相似度矩阵；

第二阶段将转换后的相似度矩阵根据图划分准则进行聚类求精并取得相应的社团结构，利用质量函数对社团划分结果进行有效性评价；

第三阶段根据聚类后的相似像素数据得到图像分割结果。

在本实验中，预先不知道社团划分的数量,首先利用谱聚类的社团检测算法集中计算前k个最小特征值并找到相应的特征向量。其中k的选取根据归一化拉普拉斯矩阵的第二特性。之后，将k个特征向量构成矩阵的列，矩阵的每一行对应于具有k个特征的节点。最后，使用K-means的算法来计算节点之间的相似度并检测k个社团。

本文算法具体步骤如下：

输入：待分割彩色图像，阈值T，聚类数K

1)利用复杂网络理论将彩色图像表示为网络社团结构图。

2)利用像素之间的相似性度量计算求出相似度矩阵A。

3)计算归一化Laplacian矩阵Lsym。

4)计算k个特征值，并对它们进行排序0=λ1≤λ2≤...λk。

5)计算特征值λ1,λ2,...λk所对应的特征向量μ1,μ2,...μk。

6)构造矩阵U以μ1,μ2,...μk为列向量，且yi∈RK，i=1,...n表示矩阵U的行数。

7)利用K-means算法对(yi)i=1,...n进行聚类，并将相应像素点归属为C1,...Ck。聚类结果为网络社团结构图的划分结果，也是原图像中对应像素点所属的类别。

8)利用模块化质量函数评价社团结构的有效性。

输出：分割后的彩色图像。

4 结果与分析

为了检验本文算法的性能，对本文算法进行实验分析。算法实验环境为：windows 7系统、Intel i5处理器、4GB内存，实验平台为MATLAB R2014a。实验图像来自于BSDS300图像库。

4.1 不同阈值对图像分割效果的影响

对于同一副彩色图像在选取不同阈值时，实验分割结果图如图1所示，a(1)、a(2)和a(3)分别为阈值逐渐增大时的分割效果图，从图1中可以看出在各个阈值下的图像分割结果，阈值较小时，分割比较精细，能够得到完整的边缘信息，图像a(1)所示；阈值过大，分割结果非常粗糙，如图像a(3)所示，得到的分割结果没有意义。可以根据不同的实验要求选取合适的阈值。图1实验结果的相关数据如表1所示，其中模块度Q可以用来定量的评估网络社区划分的质量，其值越接近1，表示网络划分出的社区结构的强度越强，则划分质量越好。从表1中可以看出，在一定范围内，随着分割结果越细腻，模块度越高，说明网络社区划分质量也就越好，结构越强。

图1 各阈值下的实验分割结果

表1 图1中的实验数据

4.2 相关算法的分析比较

本文算法在BSDS300图像库中进行图像分割对比实验，实验结果如图2所示。第一列为原始图像，第二列为有效的自适应阈值分割算法[16]实验结果，其中k取值为230，min为30，第三列为本文算法实验结果。从图中可以看到自适应阈值分割算法在纹理区域容易产生很多细小的，离散的区域，受到纹理影响比较大；本文采用谱聚类社区划分算法，在区域合并时聚集效果要好于自适应阈值分割算法，极大的提高了区域合并的效果，且能够得到完整的物体边缘，区域轮廓清晰，同时也符合人眼的视觉直观感受，分割结果也较为成功。

图2 图像分割对比实验

表2 图2中precision-recall实验数据

本文采用precision-recall标准对图2中的分割结果进行定量评价，precision-recall广泛用于信息检索和统计学分类领域的两个度量值。两个参数取值在0和1之间，数值越接近1，查全率或查准率就越高，图像分割精度越高，F-Measure是Precision和Recall加权调和平均，当F值较高时说明实验方法比较有效。实验中每幅图ground truth来自于BSDS300图像库[15]的人工分割结果。表2中p表示precision，R表示recall，F表示F-measure。从表2数据中可以看出，本文图像分割算法的实验结果要优于自适应阈值分割算法，较符合人类的视觉感知，取得了更好的图像分割效果，验证了本文图像分割算法的有效性。

5 结语

从复杂网络的角度出发，根据图像的相似性度量对图像数据进行建模，并使用谱聚类算法划分网络社团结构图，进而得到图像的聚类结果，取得了较好的图像分割效果。实验表明利用网络社团结构图对图像数据中的复杂非线性结构进行建模是有效的，这为社团检测算法在图像处理方面开拓了一个有价值的研究领域。未来工作准备改进本文算法，提高算法运行效率，也尝试利用图像其它特征如纹理特征或者其它图像相似性检测方法对图像进行网络社团结构图建模，将其更好地应用在图像分割领域当中。