CN108921853B - 基于超像素和免疫稀疏谱聚类的图像分割方法 - Google Patents

Abstract

本发明公开了一种基于超像素和免疫稀疏谱聚类的图像分割方法，主要解决现有图像分割方法的分割精确低和鲁棒性差的问题。其方法步骤是：首先，对纹理图像进行超像素划分，提取其纹理特征，作为特征数据集；然后，在谱聚类过程中结合免疫克隆算法和稀疏表示寻找最佳的特征数据集的相似度矩阵；最后，根据聚类标签结合超像素标记原始图像，实现对纹理图像的分割。本发明提取图像的超像素块作为特征数据集，用基于免疫稀疏谱聚类的图像分割方法对特征数据集进行划分，获得了更准确的分割结果。

Description

基于超像素和免疫稀疏谱聚类的图像分割方法

技术领域

本发明属于图像处理技术领域，特别涉及一种图像分割技术，可用于目标识别。

背景技术

图像分割常用的方法有基于阈值的分割方法、基于边缘的分割方法和基于区域的分割方法等，随着模式识别和人工智能的理论发展，结合特定理论的分割方法也得到广泛的应用，例如基于聚类的分割技术、基于人工神经网络的分割技术、基于遗传算法的分割技术等。在现有的聚类方法中，谱聚类是一种具有实现简单、与维数无关以及全局寻优的良好特征性的聚类方法。将谱聚类应用于图像分割是近年来在图像分割领域的一个热门研究方向。图像分割的过程就是把每个像素作为一个数据点，分割的结果是为这些数据点赋予一个类标。具有同样类标的像素分成一类，从而实现对图像的分割。

谱聚类的关键是计算N×N的相似度矩阵，N是样本个数，对于大规模数据，计算量太大。

Juanjuan Luo,Licheng Jiao,and Jose A.Lozano.在论文“A Sparse SpectralClustering Framework via Multiobjective Evolutionary Algorithm”(IEEETransactions on Evolutionary Computation20.3(2016):418-433.)中提出了一种基于多目标优化的稀疏谱聚类框架。该方法将稀疏表示与非支配排序的遗传算法 NSGA2结合，对谱聚类的相似度矩阵进行优化。该方法改进了相似度矩阵的生成，提高了谱聚类的聚类准确率，但是该方法在收敛速度和解的多样性上不够好，并且采用RC测度作为最终解选取的指标，没有NC测度准确。

西安电子科技大学在其申请的专利“基于免疫稀疏谱聚类图像分割方法”(专利申请号200910024374.6，公开号CN101673398A)中公开了一种基于免疫稀疏谱聚类的图像分割方法。该方法采用了免疫克隆算法和谱聚类算法相结合对图像进行聚类，实现图像的分割。该方法虽说不需要先验知识，计算复杂度低，但却仍然存在分割精度不高的缺点。

发明内容

本发明的目的在于克服上述已有技术的不足，提出一种基于超像素和免疫稀疏谱聚类的图像分割方法，以提取更简洁有效的特征，提高分割精度。

本发明的基本思路是：通过对纹理图像进行超像素划分，提取其纹理特征，得到聚类数据集；通过在谱聚类过程中使用免疫克隆算法和稀疏表示，寻找出最佳的聚类数据集相似度矩阵；通过聚类标签结合超像素标记原始图像，对纹理图像进行分割。

根据上述思路，本发明的实现步骤包括如下：

(1)输入一幅大小为256*256的待分割图像；

(2)使用简单线性迭代聚类SLIC方法对待分割图像划分超像素；

(3)使用灰度共生矩阵和gabor小波变换提取超像素的特征；

(4)将所有超像素特征数据归一化到[0,1]之间，以除去数据间量级的影响，得到归一化后的超像素特征数据集I；

(5)对归一化后的超像素特征数据集I，使用免疫克隆选择方法得到非支配抗体集P；

(6)将非支配抗体集P的每个非支配抗体依次作为谱聚类过程的相似度矩阵，对超像素特征数据集I进行谱聚类，得到一系列关于超像素特征数据集I的聚类结果；

(7)计算每个聚类结果的NC测度，选取最小的NC测度对应的聚类结果作为超像素特征数据集I的最终聚类结果；

(8)根据超像素特征数据集I的聚类结果，将每个像素点的类别标记为其所对应的超像素点的类别，作为待分割图像的聚类结果，完成图像分割。

本发明与现有技术相比具有以下优点：

第一，由于本发明在图像分割的聚类过程中，采用了超像素处理，得到具有代表性的超像素块，克服了用原始图像特征进行谱聚类时样本数目多的缺点，降低了计算量；

第二，由于本发明在图像分割的聚类过程中，采用了免疫克隆算法与稀疏谱聚类相结合，能够得到分布广泛、多样的候选解，提高了图像的分割精度；

第三，由于本发明在图像分割的聚类过程中，采用了NC测度选取最终解，克服了RC测度没有考虑类内相似度的缺陷，提高了图像分割的准确性。

附图说明

图1为本发明的实现流程图；

图2为用本发明和现有两种纹理图像分割方法对一幅2类纹理图像的分割对比图；

图3为用本发明和现有的两种纹理图像分割方法对一幅3类纹理图像的分割对比图。

具体实施方式

下面结合附图对本发明做进一步的详细描述。

步骤1,输入待分割图像。

从数据库中选取一幅大小为A＝256*256的纹理图像，作为输入的待分割图像。

步骤2,对待分割图像划分超像素。

现有的划分超像素的方法有基于图论的方法、基于熵率的方法、基于梯度下降的方法Meanshift、简单线性迭代聚类方法SLIC和基于几何流的水平集方法 Turbopixels等。本实例使用简单线性迭代聚类方法SLIC将待分割图像划分成n 个超像素点，其实现步骤如下：

(2a)在待分割图像中均匀选取n个像素点作为初始种子点，为每个初始种子点分配一个标签，每个种子点包含有A/n个像素点，种子点之间的距离为

(2b)在种子点的2S*2S邻域内重新选择种子点，即计算该邻域内所有像素点的梯度值，将种子点移到该邻域内梯度最小的地方，避免其落在图像边界的位置干扰聚类过程；

(2c)在每个种子点的2S*2S邻域内，计算邻域内的像素点与该种子点的距离D’，

其中，d_c表示颜色距离

l_j、a_j和b_j分别表示种子点的颜色信息，l_i、a_i和b_i分别表示像素点的颜色信息， d_s表示空间距离

x_j和y_j分别表示种子点的空间信息，x_i和y_i分别表示像素点的空间信息，m表示平衡参数，用来衡量颜色值与空间信息在相似度衡量中的比重，将每一个像素点的标签设为与其最相近的种子点的标签；

(2d)不断迭代过程(2b)和(2c)，直到收敛，获得n个种子点，用这些种子点作为超像素点，获得超像素点的集合V＝{v₁,v₂,…,v_i,…,v_n}，v_i表示第i个超像素点。

步骤3，提取超像素的特征数据集。

提取纹理图像的特征的方法有灰度共生矩阵、小波变换和非下采样小波变换等，本实例采用的方法是灰度共生矩阵和gabor小波变换，其实现如下：

(3a)通过灰度共生矩阵获取待分割图像的所有像素点的8个特征：

(3a1)将待分割图像矢量化为16个灰度级；

(3a2)对待分割图像的每个像素点在5*5的窗口内生成在距离d＝1，方向为θ＝0°，θ＝45°，θ＝90°，θ＝135°四个方向的灰度共生矩阵p(i,j)，i和j分别为灰度共生矩阵横向和纵向上的索引值；

(3a3)计算灰度共生矩阵的对比度、能量、熵、相关性这四个统计量：

对比度：

能量：

熵：

相关性：

其中p’(i,j)为归一化后的灰度共生矩阵，μ_x、σ_x分别表示p’(i,j)沿x轴方向的均值和方差，μ_y、σ_y表分别示p’(i,j)沿y轴方向的均值和方差；

(3a4)分别计算四个灰度共生矩阵的对比度、能量、熵、相关性的均值和方差，一共得到待分割图像所有像素点的8个特征向量；

(3b)通过gabor小波变换获取待分割图像的所有像素点的2个特征：

使用两个不同的gabor滤波器组将待分割图像变换到频域空间，提取待分割图像的两个不同尺度不同方向的纹理特征，两个不同的gabor滤波器组分别为 G₁和G₂，表示如下：

G₂＝G·cos[2·π·f·(x·cosθ+y·sinθ)]

其中，G(x,y)表示Gabor函数，

s_x、s_y分别表示沿x轴和y轴的方差，f为正弦函数的频率，θ表示gabor滤波器的方向，一共得到待分割图像所有像素点的2个特征向量；

(3c)将灰度共生矩阵获取所有像素点的8个特征和通过gabor小波变换获取的2个特征合并，每个像素点得到10个特征，对每一个超像素点包含的若干个像素点的纹理特征数据取平均值，作为该超像素点的特征数据值，一共得到大小为n*10的超像素特征数据集H，n表示超像素点的个数，10表示特征的数目。

步骤4，将超像素特征数据集H归一化到[0,1]之间，以除去数据间量级的影响，得到归一化后的超像素特征数据集I。

(4a)选取超像素特征数据集H中的任一元素；

(4b)计算所取元素与该元素所在列中最小元素的差值；

(4c)计算该元素所在列中最大元素与该元素所在列中最小元素的差值；

(4d)将(4b)得到的差值除以(4c)得到的差值，得到所取元素的归一化结果；

(4e)判断超像素特征数据集H中的元素是否已经取完，若是，则将所有元素的归一化结果合并成归一化后的超像素特征数据集I，否则，返回(4a)。

步骤5,使用免疫克隆算法得到非支配抗体群。

(5a)初始化抗体群：

设置最大迭代次数T＝20，抗体群规模N＝30，随机生成初始抗体群POP(t)＝(X₁，X₂，…，X_l，…，X_N)，其中t表示迭代次数，初始化为0，X_l表示第l个抗体l＝1，…， N，N表示抗体群规模，

x_ij表示第i个超像素点和第j个超像素点的相似性，i＝1，…，n，j＝1，…，n，n表示超像素点的个数，

rand为一个0到1之间的随机数；

(5b)计算每个抗体的目标函数：

其中f₁(X_l)表示抗体X_l的误差项目标函数，f₂(X_l)表示抗体X_l的稀疏项目标函数，I表示超像素的特征数据，||·||² ₂表示2范数的平方，||·||₀表示0范数；

(5c)选择操作

从抗体群POP中选择两个抗体X_l和X_m，判断第一抗体X_l和第二抗体X_m之间是否满足(f₁(X_l)≤f₁(X_m)&f₂(X_l)<f₂(X_m))或(f₁(X_l)<f₁(X_m)&f₂(X_l)≤f₂(X_m))：

如果是，则抗体X_l为非支配抗体，它能够支配抗体X_m；

否则，抗体X_l不是非支配抗体，它不能支配抗体X_m；

其中，f₁(X_l)和f₂(X_l)分别表示第一个抗体X_l的误差项目标函数和稀疏项目标函数的值，f₁(X_m)和f₂(X_m)分别表示第二个抗体X_m的误差项目标函数和稀疏项目标函数的值；

从抗体群POP中选择出所有的非支配抗体，组成非支配抗体群POP₁；

(5d)克隆操作

对非支配抗体群POP₁进行4次克隆操作生成的抗体群，表示为：

POP₂＝{POP₁，POP₁，POP₁，POP₁}。

(5e)交叉操作

(5e1)设置两个0到1的随机数，即第一随机数α、第二随机数β和第三随机数η；

(5e2)将第一随机数与设定阈值0.5进行比较：

如果α>0.5，则从克隆后的抗体群POP₂中随机选取两个抗体X_r1和X_r2进行均匀交叉，产生新的抗体：X_r3，X_r3中的元素

如果α≤0.5，则从克隆后的抗体群POP₂中随机选取两个抗体X_r1和X_r2进行算术交叉，产生新的抗体：X_r4＝ηX_r1+(1-η)X_r2；

(5e3)重复操作(5e2)N次，产生N个新抗体，组成交叉后的抗体群POP₃。

(5f)变异操作

(5f1)选取交叉后的抗体群POP₃中的任一个抗体X_l，设该抗体X_l中的第i 个超像素点和第j个超像素点的相似性x_ij的变异准则为：

其中rand和γ为0到1的随机数，h是第j个超像素点关于第i个超像素点的近邻次序；

(5f2)对交叉后的抗体群POP₃中的N个抗体按照变异准则依次进行变异操作，产生N个新抗体，组成变异后的抗体群POP₄。

(5g)判断迭代次数是否达到了最大迭代次数T，若是，则将抗体群POP₄中作为最终的抗体群P，执行步骤(6)，否则，返回步骤(5b)，进行下一次迭代。

步骤6，对免疫克隆算法得到的非支配抗体群P进行谱聚类。

(6a)对于非支配抗体群P中的抗体X_l，l＝1，…，N，计算度矩阵

其中

其中x_ij表示第i个超像素点和第j个超像素点之间的相似性，n表示超像素点的数目；

(6b)计算拉普拉斯矩阵:L＝D-X_l；

(6c)根据特征值分解公式Lu＝λu对拉普拉斯矩阵L进行特征值分解，得到n 个特征值组成的向量λ，λ＝[λ₁，λ₂，…，λ_i，…，λ_n]和n个特征向量组成的矩阵u，u＝[u₁， u₂，…，u_i，…，u_n]，其中特征值λ_i对应于特征向量u_i；

(6d)对向量λ的特征值进行从小到大排序，得到n个排序后的特征值组成的向量λ’，λ’＝[λ₁’，λ₂’，…，λ_n’]，选取前h个最小的特征值组成向量λ”，λ”＝[λ₁’，λ₂’，…，λ_h’]，其对应的特征向量组成矩阵u’，u’＝[u₁’，u₂’，…，u_h’]，对矩阵u’归一化得到矩阵u”；

(6e)利用kmeans方法对u”进行划分，得到超像素特征数据集I的聚类结果V， V＝(V₁，…，V_i，…，V_n)，V_i表示聚类结果中第i类的超像素点集合。

步骤7，计算每个聚类结果的NC测度，选取最小的NC测度对应的聚类结果作为超像素特征数据集I的聚类结果。

(7a)通过如下公式计算每个聚类结果的NC测度：

其中，c表示聚类的类别数目，

表示类间权重，

V_h表示聚类结果中第h类的超像素点集合，

表示聚类结果中不属于第h类的超像素点集合，w_ij表示第i个超像素点和第j个超像素点之间的标准相似性，

表示抗体X_l中第i个超像素点和第j个超像素点之间的相似性，l＝1，…，N，N表示非支配抗体生成的聚类结果的数目，vol(V_h)表示子集V_h的权重，

d_i表示度矩阵中的第i个元素；

(7b)计算完所有聚类结果的NC测度，选取最小的NC测度对应的聚类结果作为超像素数据集I的聚类结果。

步骤8，根据超像素特征数据集I的聚类结果，将每个像素点的类别标记为其所对应的超像素点的类别，作为待分割图像的聚类结果，完成图像分割。

本发明的效果可通过以下仿真进一步说明：

1.仿真环境：

本发明的仿真是在计算机配置为core i5 3.30GHZ，内存8G，WINDOWS 7 系统和计算机软件配置为Matlab R2014b环境下进行的。

2.仿真内容：

应用本发明方法以及现有技术的K均值方法、模糊C均值方法分别对两类和三类纹理图像进行分割的仿真实验，从分割精度和边缘保持、细节保留等方面评价这些图像分割方法的性能。

仿真1，采用本发明对所选取的一幅可分割成二类的纹理图像进行分割，结果如图2，其中

图2(a)是一幅可分割成二类的纹理图像；

图2(b)是采用本发明方法对图2(a)进行分割得到的仿真分割结果图；

图2(c)是采用K均值对图2(a)进行分割得到的仿真分割结果图；

图2(d)是采用模糊C均值聚类算法对图2(a)进行分割得到的仿真分割结果图；

图2(e)是可分割成二类的纹理图像图的分割模板。

仿真2，采用本发明对所选取的一幅可分割成三类的纹理图像进行分割，结果如图3，其中：

图3(a)是一幅可分割成三类的纹理图像图；

图3(b)是采用本发明方法对图3(a)进行分割得到的仿真分割结果图；

图3(c)是采用K均值对图3(a)进行分割得到的仿真分割结果图；

图3(d)是采用模糊C均值聚类算法对图3(a)进行分割得到的仿真分割结果图；

图3(e)是可分割成三类的纹理图像图的分割模板。

将三种方法对上述这两种纹理图像的分割准确度结果进行计算统计，结果如表1所示。

表1三种方法对这两种纹理图像的分割准确度

	本发明	K均值	模糊C均值
				两类纹理图像	0.9804	0.9629	0.9485
三类纹理图像	0.8964	0.8026	0.7655

3.仿真结果分析：

从图2和表1中可以看出，图2(b)比图2(c)和图2(d)中的分割结果好，图2(c)和图2(d)中的杂点比图2(b)中的多，但图2(c)的边缘没有图2(b)清晰，表明本发明与现有K均值和模糊C均值聚类算法相比具有较强的鲁棒性且能够获得更准确的图像分割结果。

从图3和表1中可以看出，图3(b)比图3(c)和图3(d)中的分割结果好，图3(c)和图3(d)中的杂点比图3(b)中的多，但图3(c)的边缘没有图3(b)清晰，表明本发明与现有K均值和模糊C均值聚类算法相比在对三类纹理图像的分割上也有较强的鲁棒性且能够获得更准确的图像分割结果。

综上，本发明方法与现有K均值和模糊C均值聚类算法相比，准确率有大幅度提升。

Claims (6)

1.一种基于超像素和免疫稀疏谱聚类的图像分割方法，包括如下：

(1)输入一幅大小为256*256的待分割图像；

(2)使用简单线性迭代聚类SLIC方法对待分割图像划分超像素；

(3)使用灰度共生矩阵和gabor小波变换提取超像素的特征；

(4)将所有超像素特征数据归一化到[0,1]之间，以除去数据间量级的影响，得到归一化后的超像素特征数据集I；

(5)对归一化后的超像素特征数据集I，使用免疫克隆选择方法得到非支配抗体集P；按如下步骤进行：

(5a)初始化抗体群：

随机生成初始抗体群POP(t)＝(X₁，X₂，…，X_l，…，X_N)，其中t表示迭代次数，初始化为0，X_l表示第l个抗体l＝1，…，N，N表示抗体群规模，

x_ij表示第i个超像素点和第j个超像素点的相似性，i＝1，…，n，j＝1，…，n，n表示超像素点的个数，

rand为一个0到1之间的随机数；

(5b)计算每个抗体的目标函数：

其中f₁(X_l)表示抗体X_l的误差项目标函数，f₂(X_l)表示抗体X_l的稀疏项目标函数，I表示超像素的特征数据，

表示2范数的平方，||·||₀表示0范数；

(5c)选择操作

从抗体群POP中选择两个抗体X_l和X_m，判断抗体X_l和抗体X_m之间是否满足f₁(X_l)≤f₁(X_m)&f₂(X_l)<f₂(X_m)，或满足f₁(X_l)<f₁(X_m)&f₂(X_l)≤f₂(X_m)：

如果是，则抗体X_l为非支配抗体，它能够支配抗体X_m；

否则，抗体X_l不是非支配抗体，它不能支配抗体X_m；

其中，f₁(X_l)和f₂(X_l)分别表示第一个抗体X_l的误差项目标函数和稀疏项目标函数的值，f₁(X_m)和f₂(X_m)分别表示第二个抗体X_m的误差项目标函数和稀疏项目标函数的值；

从抗体群POP中选择出所有的非支配抗体，组成非支配抗体群POP₁；

(5d)免疫操作

对非支配抗体群POP₁进行克隆操作，生成克隆后的抗体群POP₂；

对抗体群POP₂进行交叉操作，生成交叉后的抗体群POP₃；

对抗体群POP₃进行变异操作，生成变异后的抗体群POP₄；

(5e)判断迭代次数是否达到了最大迭代次数T，若是，则将抗体群POP₄中作为最终的抗体群P，执行步骤(6)，否则，返回步骤(5b)，进行下一次迭代；

(6)将非支配抗体集P的每个非支配抗体依次作为谱聚类过程的相似度矩阵，对超像素特征数据集I进行谱聚类，得到一系列关于超像素特征数据集I的聚类结果；

(7)计算每个聚类结果的NC测度，选取最小的NC测度对应的聚类结果作为超像素特征数据集I的最终聚类结果；

(8)根据超像素特征数据集I的最终聚类结果，将每个像素点的类别标记为其所对应的超像素点的类别，作为待分割图像的聚类结果，完成图像分割。

2.根据权利要求1所述的方法，其中步骤(5d)中克隆后的抗体群POP₂，是对非支配抗体群POP₁进行4次克隆操作生成的抗体群，表示为：

POP₂＝{POP₁，POP₁，POP₁，POP₁}。

3.根据权利要求1所述的方法，其中步骤(5d)中生成交叉后的抗体群POP₃，其实现如下：

第一步，设置两个0到1的随机数，即第一随机数α、第二随机数β和第三随机数η；

第二步，将第一随机数与设定阈值0.5进行比较：

如果α>0.5，则从克隆后的抗体群POP₂中随机选取两个抗体X_r1和X_r2进行均匀交叉，产生新的抗体：X_r3，该抗体X_r3中的第i个超像素点和第j个超像素点的相似性可计算为

如果α≤0.5，则从克隆后的抗体群POP₂中随机选取两个抗体X_r1和X_r2进行算术交叉，产生新的抗体：X_r4＝ηX_r1+(1-η)X_r2；

第三步，重复操作第二步N次，产生N个新抗体，组成交叉后的抗体群POP₃。

4.根据权利要求1所述的方法，其中步骤(5d)中生成变异后的抗体群POP₄，其实现如下：

首先，选取交叉后的抗体群POP₃中的任一个抗体X_l，设该抗体X_l中的第i个超像素点和第j个超像素点的相似性x_ij的变异准则为：

其中rand和γ为0到1的随机数，h是第j个超像素点关于第i个超像素点的近邻次序；

然后，对交叉后的抗体群POP₃中的N个抗体按照变异准则依次进行变异操作，产生N个新抗体，组成变异后的抗体群POP₄。

5.根据权利要求1所述的方法，其中步骤(6)中对超像素特征数据集I进行谱聚类，按如下步骤进行：

(6a)对于非支配抗体群P中的抗体X_l，l＝1，…，N，计算度矩阵

其中

其中x_ij表示第i个超像素点和第j个超像素点之间的相似性，n表示超像素点的数目；

(6b)计算拉普拉斯矩阵L＝D-X_l；

(6c)根据公式Lu＝λu对拉普拉斯矩阵L进行特征值分解，得到特征值λ和特征向量u＝[u₁，u₂，…，u_n]；

(6d)选取前h个最小的特征值对应的特征向量组成u’＝[u₁’，u₂’，…，u_h’]，对u’归一化，得到归一化后的特征向量u”；

(6e)利用kmeans方法对u”进行划分，得到超像素特征数据集I的聚类结果：

V＝(V₁，…，V_i，…，V_c)，

其中V_i表示聚类结果中属于第i类的超像素点集合，c表示聚类的类别数目。

6.根据权利要求1所述的方法，其中步骤(7)计算每个聚类结果的NC测度，通过如下公式计算：

其中，c表示聚类的类别数目，

表示类间权重，

V_h表示聚类结果中第h类的超像素点集合，

表示聚类结果中不属于第h类的超像素点集合，w_ij表示第i个超像素点和第j个超像素点之间的标准相似性，

表示抗体X_l中第i个超像素点和第j个超像素点之间的相似性，l＝1，…，N，N表示非支配抗体生成的聚类结果的数目，vol(V_h)表示子集V_h的权重，

d_i表示度矩阵中的第i个元素。

Images