基于差分免疫克隆聚类的图像分割方法

摘要

本发明公开了一种基于差分免疫克隆聚类的图像分割方法，它属于图像处理领域，主要解决已有聚类技术收敛速度慢、稳定性差、易陷入局部极值问题。其实现步骤为：1)对待分割图像提取灰度共生矩阵和小波变换特征；2)对待分割图像进行分水岭预分割，将属于同一块内的像素特征取均值，得到聚类数据；3)进行种群1初始化和个体编码；4)计算种群1中个体适应度值，得到种群2中抗体并更新精英种群；5)对种群1和种群2分别设计不同的操作算子，对种群1依次进行差分变异、正交重组、二项式交叉及选择操作，对种群2依次进行比例克隆、超变异及克隆选择操作；6)输出图像分割结果。本发明具有收敛速度快，稳定性高、分割结果区域一致性好和保留信息完整的优点，能够有效地对纹理图像和SAR图像进行分割，可用于SAR图像目标识别。

说明书

技术领域

本发明属于图像处理领域，是一种涉及纹理图像及SAR图像分割的方法，可应用于目标识别。

背景技术

图像分割是图像处理中的基本技术.是按照图像的某些特性(例如灰度级、频谱、纹理等)将图像空间划分为一些区域。图像分割技术在实际中的应用非常广泛，对图像目标的提取、测量都离不开图像分割，分割的准确性直接影响后续任务的有效性，因此具有十分重要的意义。目前常用的图像分割技术主要采用阈值分割技术、边缘分割技术、区域增长分割技术等。

聚类，即无监督分类，是一种重要的数据分析方法，也是统计模式识别中非监督模式分类的一个重要分支，属于数据挖掘领域。数据挖掘是从大量的数据中抽取出潜在的、不为人知的有用信息、模式和趋势，是一个利用各种分析工具在海量数据中发现模型和数据间关系的过程，这些模型和关系可以用来做出预测。图像分割的目的在于将图像划分成互不交叠的若干个区域，要求每个区域的内部具有一致的纹理，而不同区域之间的纹理不同。图像分割的过程就是给每个像素分配一个标号，该标号反映像素在分割结果中所属的类别，对于基于图像特征的图像分割方法，图像分割的实质是一个按照像素属性(灰度、纹理、颜色等)进行聚类的过程，因此将数据挖掘中的聚类算法用于图像分割，利用对图像上的像素点进行聚类处理，可以达到图像分割的目的。其优点为：可以解决图像边缘不清晰的问题，同时聚类方法具有可发现性，可以对图像的处理力度进行控制。但由于图像数据的特殊性，并不是所有的聚类算法都能直接应用于图像分割，有的算法需要改进，有的算法根本不适合这个领域的分类；而且有的分割算法中分类思想体现的比较明显，一些则不明显，也就是说聚类算法应用于图像分割领域是有其特点的。

由于聚类分析可以解决图像分割任务中训练样本匮乏和要求无监督处理等条件的要求，于是人们很自然地想到可以讲聚类分析用于图像分割中。早在1979年Coleman和Anderews就提出用聚类算法进行图像分割。基于聚类分析的图像分割方法是图像分割领域中一类及其重要和应用相当广泛的算法，无论是灰度图像、彩色图像还是纹理图像或者SAR图像，都可以应用聚类分析方法完成分割。目前聚类分析已经成为图像分割领域中的一个强大的研究分析工具。采用聚类方法进行图像分割是将图像空间中的像素用对应的特征空间点表示，根据它们在特征空间的聚集性对特征空间进行分割，然后将它们映射回原图像空间，得到分割结果。其中，K均值、模糊C均值聚类(FCM)等都是最常用于图像分割的聚类技术。

针对传统聚类技术本身存在的一些缺陷，例如对初始值敏感，导致分割结果不稳定等，近年来将智能信息处理技术结合聚类用于图像分割成为一个热点研究方向，主要包括遗传聚类、免疫克隆选择聚类、差分进化聚类等。在这类方法中，图像分割被表示为组合优化问题，而这些智能信息处理技术作为一种优化算法来寻找最优的图像分割结果。上述聚类技术虽然能够克服传统聚类技术对初始值和噪声敏感等缺陷，但是它们采用单一的种群进化方式及传统的更新种群操作，很容易减少种群多样性，从而陷入局部极值，严重影响图像分割结果。尽管也存在一些改进技术，例如改变交叉变异方式，增大种群规模等，但都没能从根本上解决以上问题。

发明内容

本发明的目的在于克服上述已有技术的不足，提出一种基于差分免疫克隆聚类的图像分割方法，将免疫克隆选择理论与差分进化理论相结合，充分利用二者的优点，通过交叉变异方式，加入正交重组机制，避免陷入局部极值情况，有效地对纹理图像和SAR图像进行分割。

实现本发明目的的技术方案是用图像的灰度共生矩阵及小波特征，反映图像信息，对这两者构成的多维特征向量进行聚类。其具体实现步骤如下：

(1)对待分割的纹理图像和SAR图像分别提取灰度共生矩阵和小波变换特征，得到N个D维的特征向量，其中N为图像的像素个数，D为灰度共生矩阵与小波特征的维数之和；

(2)对待分割图像进行分水岭预分割，将属于同一块内的像素特征取均值，得到N1个D维的特征向量，作为聚类的输入数据样本，N1为分水岭分割块数；

(3)从N1个数据样本中随机选取k个样本作为种群1的初始种群，k为图像分割的类别数；

(4)对初始种群1中个体进行编码，得到NP个D*k维的向量，NP为种群1规模，种群1中每个个体记为i＝1...NP，G＝0，为当前进化代数；

(5)对编码后的种群1中个体按照如下步骤计算适应度值；

5a)将每个个体表示为一个划分的k个聚类中心{c_i，i＝1，...k}；

5b)根据样本点与各个聚类中心欧式距离最近原则获得各个聚类中心的划分集合O_i，对每个集合O_i中的所有样本点求平均值，得到新的聚类中心为：i＝1，...，K j＝1，...，n，n_i为O_i中样本点的个数，

5c)根据计算出的新的聚类中心，得到适应度函数为：

$f=1/(1+\underset{i=1}{\overset{K}{\Sigma }}\underset{x_j\in C_i}{\Sigma }||x_j-c_i^{*}|\left|\right)$

其中，||·||为求取欧氏距离的运算符；

(6)计算出种群1中所有个体的适应度值后，将它们由高到低排序，将适应度值最高的个体保存到精英种群中，并取前面的d个个体作为种群2中抗体，将其对应的适应度值作为种群2中抗体的亲和度值，d为设定的种群2规模，当前进化代数G＝0；

(7)将种群1中个体i＝1...NP作为目标向量，对其执行差分变异操作，得到每个目标向量对应的变异向量i＝1...NP；

(8)从种群1中随机选择一个目标向量对其执行正交重组操作，得到一个新个体取代个体X_m，G；

(9)对种群1中的其他目标向量i＝1...NP∩i≠m执行二项式交叉操作，得到对应的试验向量i＝1...NP∩i≠m；

(10)对种群2中的抗体按照与亲和度值成正比的克隆规模以此进行比例克隆操作和超变异操作；

(11)对种群1和种群2分别进行选择操作，用种群2中抗体取代种群1中适应度值最低的d个个体，返回步骤(6)重新进行迭代优化，重复进行N_max次，得到的精英种群，N_max为设定的最大迭代次数；

(12)从精英种群中选择适应度值最大的个体代表最终的聚类中心，并根据该聚类中心将N1个数据划分到不同的类别中，结合步骤(2)中的分水岭预分割结果，对图像的每个像素点进行类别划分，得到图像最终分割结果。

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

1、本发明的聚类方法结合了免疫克隆选择理论与差分进化理论的不同特性，采用两种不同的方式进化种群，有效地保持了种群多样性，避免陷入局部极值；

2、本发明相对已有的进化聚类技术，引入了自适应交叉变异操作，能够加快图像分割速度，并引入了正交重组机制，有效地避免了早熟收敛，并获得较好的分割结果；

仿真结果表明，本发明方法较现有的K均值聚类算法与遗传聚类算法GAC能更有效地进行纹理图像和SAR图像分割。

附图说明

图1是本发明的流程示意图；

图2是本发明对一幅2类纹理图像的分割结果；

图3是本发明对一幅3类纹理图像的分割结果；

图4是本发明对一幅2类SAR图像的分割结果；

图5是本发明对一幅3类SAR图像的分割结果；

具体实施方式

参照图1，本发明的具体实现步骤如下：

步骤1、对待分割图像提取灰度共生矩阵和小波特征。

采用滑窗法逐像素点地提取图像的几种统计量在[0°，45°，90°，135°]四个方向上的特征，对于纹理图像，提取图像的对比度、同质区、能量及相关性四个统计量在四个方向上的共16维特征；对于SAR图像，提取图像的对比度、同质区、能量三个统计量在四个方向上的共12维特征，滑窗大小为17*17。对纹理图像和SAR图像都进行三层离散小波分解，提取小波能量的10维特征，滑窗大小为16*16，因此，对于纹理图像，特征向量维数D为26，对于SAR图像，特征向量维数为D为23。

步骤2、对待分割图像进行分水岭预分割，分割块数为N1，得到待聚类数据。

这一部分的目标是对待分割图像进行预分割，减少聚类数据规模，降低方法时间复杂度，由于分水岭块数如果过多，会增加时间复杂度，若过少会导致区域内的纹理特征一致性较差，因此应合理控制分水岭分割块数，对于不同纹理特性的图像，N1的值是不固定的，本发明中N1值为1500左右。

步骤3、设定聚类方法参数，初始化种群。

(3.1)聚类方法参数主要包括：种群1规模NP为25，种群2规模d为5，种群2克隆规模nc为25，正交重组量化个数Q₁为3，因子个数F为4，最大迭代次数N_max为30；

(3.2)初始化种群1A(G)＝{X_1，G，X_2，G，...X_NP，G}，G＝0

其中，i＝1...NP，从输入数据集中随机选取，k为聚类类别数，D为提取的特征维数，G为当前进化代数。

步骤4、计算种群1中个体适应度值。

(4.1)将每个个体表示为一个划分的k个聚类中心{c_i，i＝1，...k}；

(4.2)根据样本点与各个聚类中心欧式距离最近原则获得各类的划分集合O_i，对每个集合O_i中的所有样本点求平均值，得到新的聚类中心为：i＝1，...，K j＝1，...，n，n_i为O_i中样本点的个数；

(4.3)根据计算出的新的聚类中心，得到适应度函数的计算公式为：

$f=1/(1+\underset{i=1}{\overset{K}{\Sigma }}\underset{x_j\in C_i}{\Sigma }||x_j-c_i^{*}|\left|\right)$

其中，||·||为求取欧氏距离的运算符。

步骤5、初始化种群2中抗体并更新精英种群。

(5.1)计算出种群1中所有个体的适应度值后，将它们由高到低排序；

(5.2)将适应度值最高的个体保存到精英种群中，取前面的d个个体作为种群2 A₂(G)＝{a_1，G，a_2，G，...a_d，G}，G＝0中抗体，其对应的适应度值作为抗体的亲和度值，种群2中每个抗体表示为i＝1，2...d，d为设定的种群2规模。

步骤6、设计两个种群的操作算子。

(6.1)差分变异操作

6.1.1)根据以下公式计算变异算子F_i：

F_i＝randcauchy_i(μ_F，0.1)

randcauchy_i(μ_F，0.1)表示服从位置参数μ_F，尺度参数为0.1的柯西分布随机数，μ_F初始化为0.5，每一代中μ_F按下式更新：

${\mu }_F=(1-c)*{\mu }_F+c*\frac{{\Sigma }_{F\in S_F}{F}^2}{{\Sigma }_{F\in S_F}F}$

c∈(0，1)，S_F是所有成功进入下一代的试验向量对应的变异算子集合；

6.1.2)根据以下公式进行差分变异操作，得到变异向量：

$V_{i,G}=X_{i,G}+F_i*(X_{\mathrm{best},G}-X_{i,G})+F_i*(X_{r_1^i,G}-X_{r_2^i,G})$

X_best，G为当前种群1中适应度值最高的个体；为从当前种群1中随机选取的两个个体。

(6.2)正交重组操作

6.2.1)从种群1中随机选择一个个体m，将个体m的目标向量及其对应的变异向量作为两个父代个体，分别记为和令i＝1，2，...D*k，按下式将每维空间量化为Q₁个数值：

$a_{i,j}=\left(\begin{array}{cc}{1}_{\min }^i& j=1\\ 1_{\min }^i+(j-1)*\left(\frac{1_{\max }^i-1_{\min }^i}{Q_1-1}\right)& 2\le j\le Q_1-1\\ 1_{\max }^i& j=Q_1\end{array}\right)$

Q₁＝3为正交重组时采用的量化个数；

6.2.2)随机产生F-1个整数t₁，t₂，...t_F-1，满足1＜t₁＜t₂＜...＜t_F-1＜D*k，F＝4为正交重组时采用的因子个数，将D*k维空间按下式分为F个因子：

$\left(\begin{array}{c}{H}_1=(a_1,...,a_{t_1})\\ H_2=(a_{t_1+1},...,a_{t_2})\\ ...\\ H_F=(a_{t_{F-1}+1},...,a_{D*k})\end{array}\right);$

6.2.3)将每个因子H_i，i＝1，2，...F按下式量化为Q₁个数值：

$\left(\begin{array}{c}{H}_i\left(1\right)=(a_{t_{i-1}+\mathrm{1,1}},a_{t_{i-1}+\mathrm{2,1}},...,a_{t_i,1})\\ H_i\left(2\right)=(a_{t_{i-1}+\mathrm{1,2}},a_{t_{i-1}+\mathrm{2,2}},...,a_{t_i,2})\\ ...\\ H_i\left(Q_1\right)=(a_{t_{i-1}+1,Q_1},a_{t_{i-1}+2,Q_1},...,a_{t_i,Q_1})\end{array}\right);$

6.2.4)构造一个正交矩阵结合上述量化结果产生M₁＝9个子代个体，按照适应度值从中选择值最大的个体取代个体m。

(6.3)二项式交叉操作

6.3.1)根据以下公式计算交叉概率：

CR_i＝randnormal(μ_CR，0.1)

randnormal(μ_CR，0.1)表示服从均值为μ_CR，方差为0.1的正态分布随机数，μ_CR初始化为0.5，每一代中μ_CR按下式更新：

μ_CR＝(1-c)*μ_CR+c*mean(S_CR)

c∈(0，1)，S_CR是所有成功进入下一代的试验向量对应的交叉概率集合，mean(S_CR)表示该集合的算术均值；

6.3.2)对种群1中的目标向量i＝1，...NP∩i≠m和变异向量i＝1，...NP∩i≠m，执行二项式交叉操作，得到对应的试验向量：

$u_{i,G}^j=\left(\begin{array}{cc}{v}_{i,G}^j,& \mathrm{if}\left({\mathrm{rand}}_j\right[\mathrm{0,1}]\le {\mathrm{CR}}_i)\mathrm{or}(j=j_{\mathrm{rand}})\\ x_{i,G}^j,& \left(\begin{array}{cc}\mathrm{otherwise}& j=\mathrm{1,2},...D*k\end{array}\right)\end{array}\right)$

rand_j[0，1]是服从[0，1]之间均匀分布的随机数，j_rand表示[1，D*k]之间均匀分布的随机整数。

(6.4)比例克隆及超变异操作

6.4.1)对种群2A₂(G)＝{a_i，G，a_2，G，...a_d，G}中每个抗体a_i，G，依据亲和度值计算其克隆规模q_i：

nc为克隆种群大小的期望值，aff(a_i，A)为抗体种群A中抗体a_i的亲和度值；

6.4.2)对抗体种群2的克隆操作定义为：

$T_c^c\left(A_2\left(G\right)\right)=T_c^c(a_{1,G}+a_{2,G}+...+a_{d,G})=T_c^c\left(a_{1,G}\right)+T_c^c\left(a_{2,G}\right)+...+T_c^c\left(a_{d,G}\right)$

其中：$T_c^c\left(a_{i,G}\right)=\{a_{i,G}^1+a_{i,G}^2+...+a_{i,G}^{q_i}\},a_{i,G}^j=a_{i,G},j=\mathrm{1,2}...q_i;$

6.4.3)对克隆种群执行超变异操作

对于待变异的抗体如果满足变异概率，从1～k中随机选择一个类别j，用输入样本数据中的一个随机样本作为类j变异后的聚类中心，得到变异后的抗体种群

(6.5)种群更新操作

6.5.1)对种群1中个体i＝1，...NP∩i≠m执行选择操作，得到下一代进化种群A(G+1)，对于种群1中每个目标向量i＝1，...NP∩i≠m，及其对应的变异向量i＝1，...NP∩i≠m，按照适应度值进行比较，如果试验向量适应度值高于目标向量，用试验向量取代其对应的目标向量进行下一次迭代；

6.5.2)对种群2中抗体执行克隆选择操作，得到新一代种群A₂(G+1)，对经过变异操作的抗体种群的克隆选择操作定义如下：

$T_c^s\left(\right\{a_1+a_1^{1^{\prime }}+...+a_1^{{q_1}^{\prime }}\}+\{a_2+a_2^{1^{\prime }}+...+a_2^{{q_2}^{\prime }}\}+...+\{a_d+a_d^{1^{\prime }}+...+a_d^{{q_d}^{\prime }}\left\}\right)=a_1^{\prime }+a_2^{\prime }+...+a_d^{\prime }$

其中，抗体a′_i在子种群中具有最高的亲和度；

6.5.3)用种群2的抗体替代种群1中最差的d个个体，返回步骤5，重复迭代N_max次，得到最终的精英种群，N_max为设定的最大迭代次数。

步骤7、从精英种群中选择适应度值最大的个体代表最终的聚类中心，并根据该聚类中心将N1个数据划分到不同的类别中，结合步骤2中的分水岭预分割结果，对图像的每个像素点进行类别划分，得到图像最终分割结果并输出。

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

1仿真内容：应用本发明方法和现有的K均值聚类方法、遗传聚类方法分别对两幅纹理图像和两幅SAR图像进行分割实验，并从方向信息的准确性、同质区域的内部一致性、细节信息的完整性和边缘边界的清晰性评价这些方法的各自性能，对于纹理图像还可以通过分割正确率结果来评价各种方法的性能。

2仿真实验结果

A.两类纹理图像的实验结果

用本发明方法以及现有K均值聚类方法，遗传聚类方法对两类纹理图像进行分割，其分割正确率比较结果见表1。三种方法的分割结果如图2所示。其中图2(a)为两类纹理图像；图2(b)为该纹理图像分割的正确结果；图2(c)为K均值聚类方法对图2(a)进行分割得到的结果；图2(d)为遗传聚类方法对图2(a)进行分割结果，图2(e)为本发明方法的分割结果。由图2可见，K均值的分割结果在纹理上出现斑点，而遗传聚类与本发明方法都能有较好的区域一致性，本发明方法具有更清晰的边缘轮廓。

B.三类纹理图像的实验结果

用本发明方法以及现有K均值聚类方法，遗传聚类方法对三类纹理图像进行分割，其分割正确率比较结果见表1。三种方法的分割结果如图3所示。其中图3(a)为三类纹理图像；图3(b)为该纹理图像分割的正确结果；图3(c)为K均值聚类方法对图3(a)进行分割得到的结果；图3(d)为遗传聚类方法对图3(a)进行分割结果，图3(e)为本发明方法的分割结果。由图3可见，本发明方法的区域一致性最优，而且边缘比较清晰、光滑，而K均值与遗传聚类的分割结果边缘都比较模糊，且区域一致性较差。

C.两类地物背景SAR图像的实验结果

用本发明方法以及现有K均值聚类方法，遗传聚类方法对三类SAR图像进行分割，其效果比较如图4所示。其中图4(a)为两类SAR图像；图4(b)为K均值聚类方法对图4(a)进行分割得到的结果；图4(c)为遗传聚类方法对图4(a)进行分割结果，图4(d)为本发明方法的分割结果。由图4可见，本发明方法能够检测出部分边缘及细节信息，区域一致性较好，而K均值方法和遗传聚类方法检测到细节信息都少于本发明方法。

D.三类地物背景SAR图像的实验结果

用本发明方法以及现有K均值聚类方法，遗传聚类方法对三类SAR图像进行分割，其效果比较如图5所示。其中图5(a)为三类SAR图像，为新墨西哥州Albuquerque城附近的Rio Grande河的Ku-波段SAR图像，分辨率为1m，包括三类地物：植被，河流和农作物；图5(b)为K均值聚类方法对图5(a)进行分割得到的结果；图5(c)为遗传聚类方法对图5(a)进行分割结果，图5(d)为本发明方法的分割结果。由图5可见，本发明方法能够比较完整地检测出桥梁目标，而K均值与遗传聚类方法在桥梁附近的区域一致性较差。

表1三种方法对两幅纹理图像分割正确率结果

  本发明方法  遗传聚类方法  K均值聚类方法  两类纹理图像  0.9822  0.9730  0.9457  三类纹理图像  0.9725  0.9573  0.9530

从表1可见，本发明方法对两幅纹理图像能得到最高的分割正确率结果。