基于动态局部搜索和免疫克隆自动聚类的图像分割方法

摘要

本发明提出了一种基于动态局部搜索和免疫克隆自动聚类的图像分割方法，用于解决现有图像分割方法中存在的鲁棒性和精确度差、收敛速度慢的技术问题，实现步骤是：1.输入一幅待分割图像；2.初始化抗体种群，得到第一抗体种群；3.对第一抗体种群进行克隆选择操作，得到第二抗体种群；4.设置对第二抗体种群优化的当前优化代数t和最大优化代数tmax；5.对第二抗体种群进行优化，得到第六抗体种群；6.判断是否满足迭代停止条件；7.对第六抗体种群中的非支配解集进行选择；8.利用已得到的最优分割中心点对待分割图像进行分割。本发明提高了图像分割的精确度、鲁棒性和收敛速度，可用于对图像中特征目标的提取和对目标的识别与跟踪。

说明书

技术领域

本发明属于图像处理技术领域，涉及一种自动聚类图像分割方法，特别涉及一种 基于动态局部搜索和免疫克隆自动聚类的图像分割方法，可用于对图像中特征目标的提取 和对目标的识别跟踪。

背景技术

图像分割的过程就是把每个像素点作为一个数据点，分割的结果是为这些数据点 赋予一个类标，具有同样类标的像素点分成一类，从而实现对图像的分割。聚类分析是数据 挖掘的主要技术之一，将各种聚类方法应用于图像分割是近年来在图像分割领域的一个热 门研究方向。

从人工参与的程度来看，图像分割可分为人工、半自动、自动三种类型。其中人工 分割完全由操作者利用鼠标等工具勾画出分割区域的轮廓，容易受操作者主观因素的影 响，并且费时费力重复性差；半自动分割需要针对具体图像和任务确定参数的选取问题，包 括设定阈值、分割目标的数目等，实际上多数分割方法都属于半自动分割。自动分割就是利 用自动聚类分析实现图像的分割，其中自动聚类分析就是在自动搜索到数据集最优聚类个 数的同时找到其最合理的划分。

由于大多数自动聚类算法没有充分考虑待分割图像的全局信息，尤其是在针对多 区域的图像时，这类分割方法对噪声点比较敏感，导致图像分割的鲁棒性较差，算法的适应 范围较小。为解决这些问题，近些年来研究人员将一些进化算法引入到自动聚类方法中，但 由于这些进化算法本身在收敛性方面的不足且容易陷入局部最优分割方案，导致分割图像 过程中分割的精确度低，收敛速度比较慢。

例如，中国专利申请，授权公开号CN101477686B，名称为“基于克隆选择的无监 督图像分割方法”中，公开了一种基于克隆选择的无监督图像分割方法，该方法将克隆选择 用于对分割质量的优化，能够在无指定分割区域数目的情况下，有效地对图像进行自动分 割。该方法虽然解决了传统聚类方法中必须给出指定的分割类别数目的缺陷，减少了分割 过程对先验知识的依赖。但是，该方法仍然存在的不足之处是，其优化的目标函数中未包括 全局紧致性和模糊分离度，没有充分考虑图像的全局信息，导致该方法适应范围小，鲁棒性 差，从而不能正确的分割密度分布不均衡的图像。又如SahaS和BandyopadhyayS等人在 Appl.SoftComput.,2013,13:89-108上发表了“Ageneralizedautomaticclustering algorithminamulti-objectiveframework”的论文，文中提出一种基于模拟退火算法 的多目标自动聚类算法，该方法结合了模拟退火算法的框架对聚类的质量进行了优化，实 验结果表明该算法能够检测到适当的聚类个数，并且得到最合理的数据集划分。虽然该算 法的目标函数包含了很多聚类信息，但是由于模拟退火算法收敛速度慢并且算法性能与初 始参数敏感的特点，从而导致聚类质量的不高，收敛速度较慢。

发明内容

本发明的目的在于克服上述现有技术存在的不足，提出了一种基于动态局部搜索 和免疫克隆自动聚类的图像分割方法，用于解决现有图像分割方法中存在的分割精确度 低、鲁棒性差和收敛速度慢的技术问题。

为实现上述目的，本发明采取的技术方案为：

一种基于动态局部搜索和免疫克隆自动聚类的图像分割方法，包括如下步骤：

(1)输入一幅待分割图像；

(2)采用基于聚类中心的可变长实数编码方式编码抗体，并对该抗体进行初始化， 得到第一抗体种群A(t)；

(3)采用包含全局紧致性和模糊分离度的目标函数，对已得到的第一抗体种群A (t)进行克隆选择操作，得到由非支配抗体组成的第二抗体种群A⁽¹⁾(t)；

(4)设置对第二抗体种群A⁽¹⁾(t)进行优化的当前代数t为0，最大优化代数为t_max；

(5)采用人工免疫算法对第二抗体种群A⁽¹⁾(t)进行优化，实现的步骤为：

(5a)采用等比例克隆方式对第二抗体种群A⁽¹⁾(t)中的抗体进行克隆增殖操作，得 到第三抗体种群A⁽²⁾(t)；

(5b)采用单点交叉方式对第三抗体种群A⁽²⁾(t)中的抗体进行交叉操作，得到第四 抗体种群A⁽³⁾(t)；

(5c)采用非一致性变异方式对第四抗体种群A⁽³⁾(t)中的抗体进行变异操作，得到 第五抗体种群A⁽⁴⁾(t)；

(5d)采用动态局部搜索算子对第五抗体种群A⁽⁴⁾(t)中的抗体进行局部搜索操作， 得到第六抗体种群A⁽⁵⁾(t)；

(6)判断当前代数t是否小于最大优化代数t_max，若是，则将当前代数t加一，用第六 抗体种群A⁽⁵⁾(t)替换第二抗体种群A⁽¹⁾(t)，执行步骤(5)，否则，执行步骤(7)；

(7)采用半监督方式对第六抗体种群A⁽⁵⁾(t)中的非支配解集进行选择操作，得到 最优分割中心点；

(8)利用已得到的最优分割中心点对待分割图像进行分割，实现步骤如下：

(8a)计算待分割图像中每一个像素点属于最优分割中心点中每个类的隶属度，获 得待分割图像像素点的隶属度矩阵；

(8b)从待分割图像像素点的隶属度矩阵中找出待分割图像中每个像素点所在列 中的最大隶属度，将这些最大隶属度在隶属度矩阵中位置的行标号，作为这些最大隶属度 所对应的像素点的类标号；

(8c)显示待分割图像中所有的类，完成图像分割。

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

1.本发明由于采用了包含全局紧致性和模糊分离度的目标函数作为优化目标，与 现有技术中采用单一目标进行图像分割相比，考虑了待分割图像的全局信息，减小了分割 过程对噪声的敏感度，从而提高了图像分割的鲁棒性。

2.本发明由于对图像的最优分割中心点进行优化采用了人工免疫算法，将全局搜 索和动态局部搜索相结合，在编码阶段，采用基于聚类中心的可变长实数编码方式编码染 色体，简单高效；在交叉操作中，采用单点交叉方式，保证了交叉后抗体的有效性；在变异操 作中采用非一致性变异方式，有效避免了由于变异操作导致的退化现象；在克隆选择操作 中，同时考虑解的亲和度大小和拥挤度，在保持种群多样性的同时保证了解的均匀性；与现 有技术中采用的仅包括全局搜索进行优化相比，有效的提高了图像分割过程中最优分割中 心点的收敛速度和图像分割的精确度。

附图说明

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

图2是本发明和现有图像分割方法的分割结果对比图。

具体实施方式

下面结合附图和具体实施例，对本发明作进一步描述。

参照图1，本发明的分割方法包括如下步骤：

步骤1，输入一幅待分割图像；

输入一幅大小为244×244人工合成图像。

步骤2，采用基于聚类中心的可变长实数编码方式编码抗体，并对该抗体进行初始 化，得到第一抗体种群A(t)；

步骤2a)设置当前循环次数x为0，设置第一抗体种群A(t)的规模为n，待分割图像 的最大聚类数目为k_max；

本实施例中n的取值为100，k_max的取值为25。

步骤2b)根据设定的图像聚类个数k(2≤k≤k_max)，从图像像素点集中随机选取k个 数据对象作为k个聚类中心，记为v＝[v₁，v₂，...，v_k]，其中v_i＝[v_i1，v_i2，…，v_id](i＝1, 2,…,k)表示v中第i个聚类中心，d为数据对象的维数；

步骤2c)将矩阵v转化为行向量，作为一个抗体，即h_l(t)＝[v₁,v₂,...,v_k](l＝1, 2,...,n)；

步骤2d)判断当前循环次数x是否小于第一抗体种群A(t)的规模n，若是，则执行步 骤2b)，否则，执行步骤2e)；

步骤2e)将初始化得到的所有抗体组成第一抗体种群A(t)。

步骤3，采用包含全局紧致性和模糊分离度的目标函数，对已得到的第一抗体种群 A(t)进行克隆选择操作，得到由非支配抗体组成的第二抗体种群A⁽¹⁾(t)；

目标函数可表示为：

minf(h(t))＝[f₁(h(t)),f₂(h(t))]

其中，

$f_1\left(h\right(t\left)\right)=J=\underset{i=1}{\overset{K}{\Sigma }}\frac{\underset{k=1}{\overset{N}{\Sigma }}{u}_{ik}^{m}d(v_i,x_k)}{\underset{k=1}{\overset{N}{\Sigma }}{u}_{ik}}$

$f_2\left(h\right(t\left)\right)=\frac{1}{S}=\frac{1}{\underset{i=1}{\overset{K}{\Sigma }}\underset{j=1,j\ne i}{\overset{K}{\Sigma }}{u}_{ij}^{m}d(v_i,v_j)}$

$u_{ik}=\frac{1}{\underset{j=1}{\overset{K}{\Sigma }}{\left(d\right(v_i,x_k)/d(v_j,x_k\left)\right)}^{2/(m-1)}}$

$\left(\begin{array}{cc}{u}_{ij}=\frac{1}{\underset{s=1,s\ne j}{\overset{K}{\Sigma }}{\left(d\right(v_i,v_j)/d(v_j,v_s\left)\right)}^{2/(m-1)}}& i\ne j\end{array}\right)$

其中，f₁(h(t))表示抗体h(t)对应的第1个目标函数的值，J表示全局紧致性，K表 示抗体h(t)所对应的聚类个数，N表示待分割图像中像素点集的大小，u_ik表示第k个像素点 属于第i个聚类中心的隶属度，m表示模糊指数，且m＝2，d(v_i,x_k)表示聚类中心v_i和x_k之间 的距离，v_i＝[v_i1，v_i2，...，v_id](i＝1，2，...，K)表示抗体h(t)解码后对应的第i个聚类中心 点，x_k＝[x_k1，x_k2，…，x_kd]表示图像像素点集中第k个像素点；f₂(h(t))表示抗体h(t)对应的 第2个目标函数的值，S表示模糊分离度，u_ij表示第j个聚类中心点属于第i个聚类中心点的 隶属度，d(v_i,v_j)表示聚类中心点v_i和聚类中心点v_j之间的距离。

对于上述公式描述的多目标自动聚类问题，当且仅当(f₁(h'(t))≤f₁(h(t))&f₂(h'(t))＜f₂(h(t)))||时，称抗体h'(t)相比于抗体h(t)是Pareto占优的，也称为抗体h' (t)支配抗体h(t)，基于这个定义，克隆选择的操作过程可以描述如下：

步骤3a)设置非支配抗体数目的上界Q；

本实施例中Q取值为50；

步骤3b)选择A⁽⁰⁾(t)所有的非支配抗体组成第二抗体种群并 统计其中非支配抗体的个数s；

步骤3c)判断s是否大于Q，若是，则对第二抗体种群A⁽¹⁾(t)进行拥挤度分析，根据 拥挤度大小删除A⁽¹⁾(t)中拥挤度高的抗体，直到A⁽¹⁾(t)中抗体个数为Q；否则，执行步骤4。

步骤4，设置对第二抗体种群A⁽¹⁾(t)进行优化的当前代数t为0，最大优化代数为 t_max；

本实施例中最大优化代数t_max设置为50。

步骤5，采用人工免疫算法对第二抗体种群A⁽¹⁾(t)进行优化，实现的步骤为；

步骤5a)采用等比例克隆方式对第二抗体种群A⁽¹⁾(t)中的抗体进行克隆增殖操 作，得到第三抗体种群A⁽²⁾(t)。

为扩大种群规模，本实施例采用整体等比例克隆方式对A⁽¹⁾(t)进行克隆增殖操 作，第二抗体种群A⁽¹⁾(t)经克隆增殖操作后变为第三抗体种群A⁽²⁾(t)：

A⁽²⁾(t)＝{{h₁⁽¹⁾¹(t),h₁⁽¹⁾²(t),…,h₁^(1)q(t)},{h₂⁽¹⁾¹(t),h₂⁽¹⁾²(t),…,h₂^(1)q(t)},…,

{h_s⁽¹⁾¹(t),h_s⁽¹⁾²(t),…,h_s^(1)q(t)}}

＝{h₁⁽²⁾(t),h₂⁽²⁾(t),…,h_m⁽²⁾(t)}

其中，h_i^(1)k(t)＝h_i⁽¹⁾(t)(i＝1,2,…,s)，k＝1,2,…,q，s表示第二抗体种群A⁽¹⁾(t)的大小，q表示克隆比例，且q＝5，h_i⁽²⁾(t)(i＝1,2,...,m)表示克隆后的抗体，m＝s×q 表示克隆后抗体种群的大小。

步骤5b)采用单点交叉方式对第三抗体种群A⁽²⁾(t)中的抗体进行交叉操作，得到 第四抗体种群A⁽³⁾(t)。

步骤5b.1)从第三抗体种群A⁽²⁾(t)中随机选择两个抗体h_i(t)和h_j(t)；

步骤5b.2)判断h_i(t)和h_j(t)的长度是否相同，若是，则执行步骤5b.3)，否则，执行 步骤

5b.4)；

步骤5b.3)统计h_i(t)和h_j(t)的长度l，随机产生一个交叉位置pos(pos＝1,2,…, l)进行h_i(t)和h_j(t)的交叉操作，交叉完成后得到两个新的抗体：

h′_i(t)＝[h_i(t)(1:pos),h_j(t)(pos+1:l)]

h′_j(t)＝[h_j(t)(1:pos),h_i(t)(pos+1:l)]

步骤5b.4)对于长度分别为l₁，l₂的两个抗体h_i(t)和h_j(t)，首先获得抗体h_i(t)和 h_j(t)分别所对应的聚类个数k₁，k₂；

步骤5b.5)进行基于聚类中心的单点交叉操作，在产生交叉位置时以长度较小的 抗体为依据；

经过交叉操作后得到第四抗体种群A⁽³⁾(t)：

A⁽³⁾(t)＝{h₁⁽³⁾(t),h₂⁽³⁾(t),…,h_m⁽³⁾(t)}

其中，h_i⁽³⁾(t)(i＝1,2,…,m)表示交叉后的抗体，m表示第四抗体种群A⁽³⁾(t)的大 小。

步骤5c)采用非一致性变异方式对第四抗体种群A⁽³⁾(t)中的抗体进行变异操作， 得到第五抗体种群A⁽⁴⁾(t)。

非一致性变异方式结合变异范围与进化代数，在进化代数较小时，变异范围比较 大，保证在全局范围内进行搜索；当进化代数增加时，变异范围随之缩小，使得该方法在末 期能进行局部搜索，从而有效地避免变异的随机性，加快收敛速度，具体操作过程如下：

步骤5c.1)设h_i⁽³⁾(t)＝[h_i⁽³⁾(t)(1),h_i⁽³⁾(t)(2),…,h_i⁽³⁾(t)(l)](i＝1,2,…,m) 是第四抗体种群A⁽³⁾(t)中的一个抗体，其长度为l；

步骤5c.2)随机产生随机数p，并对抗体的第p个位置进行变异：

h_i⁽⁴⁾(t)＝[h_i⁽³⁾(t)(1),h_i⁽³⁾(t)(2),…,h_i⁽³⁾(t)(p-1),h_i^(3)'(t)(p),…,h_i⁽³⁾(t) (l)]

$\Delta h\left(t\right)=(1-h_i^{\left(3\right)}(t\left)\right(p\left)\right)·(1-u^{{(1-t/t_{max})}^{\alpha }}),\Delta h{\left(t\right)}^{\prime }=h_i^{\left(3\right)}\left(t\right)\left(p\right)·(1-u^{{(1-t/t_{max})}^{\alpha }})$

其中，t表示当前优化代数，mod(·)表示求余操作，u表示0到1之间的随机数，t_max表示最大优化代数，且t_max＝50，α表示非一致性参数，且α＝2，

变异操作后，第四抗体种群A⁽³⁾(t)变成第五抗体种群A⁽⁴⁾(t)：

A⁽⁴⁾(t)＝{h₁⁽⁴⁾(t),h₂⁽⁴⁾(t),…,h_m⁽⁴⁾(t)}

其中，h⁽⁴⁾(t)(i＝1,2,...,m)表示经过上述非一致变异操作后的抗体，m为第五抗 体种群A⁽⁴⁾(t)的大小。

步骤5d)采用动态局部搜索算子对第五抗体种群A⁽⁴⁾(t)中的抗体进行局部搜索操 作，得到第六抗体种群A⁽⁵⁾(t)。

动态局部搜索过程包括增加聚类中心、减少聚类中心，FCM算法修正3个部分，操作 过程按如下步骤进行：

步骤5d.1)设置阈值w，并产生一个(0,1)之间的随机数r；

本实施例中w设置为0.5。

步骤5d.2)判断该随机数r是否小于阈值w：

若是，则从待分割图像的像素点集中随机选一个对象作为新的聚类中心，并将该 聚类中心增加到第一抗体h_i⁽⁴⁾(t)中；否则，判断第一抗体h_i⁽⁴⁾(t)所对应的聚类中心个数是 否大于2，若是，则从第一抗体h_i⁽⁴⁾(t)中随机选取一个聚类中心进行删除操作；否则，执行 步骤5d.3)；

步骤5d.3)将第一抗体h_i⁽⁴⁾(t)解码，得到对应的聚类中心，并将已得到的聚类中 心作为FCM算法的初始聚类中心，进行聚类中心的修正操作，得到第二抗体h_i^(4)’(t)；

步骤5d.4)判断第二抗体h_i^(4)’(t)是否支配第一抗体h_i⁽⁴⁾(t)，若是，则用第二抗体 h_i^(4)’(t)代替第一抗体h_i⁽⁴⁾(t)，否则，继续执行步骤5d.1)。

步骤6，判断当前代数t是否小于最大优化代数t_max，若是，则将当前代数t加一，用 第六抗体种群A⁽⁵⁾(t)替换第二抗体种群A⁽¹⁾(t)，执行步骤5，否则，执行步骤7。

步骤7，采用半监督方式对第六抗体种群A⁽⁵⁾(t)中的非支配解集进行选择操作，得 到最优分割中心点。

$MS(G,S)=\sqrt{\frac{N_{01}+N_{10}}{N_{11}+N_{10}}},$

其中，MS(·)∈[0,1]，MS(·)值越小表示聚类质量越高，G表示待分割图像中像素 点集的真实类标集合，S表示聚类算法得到的待分割图像中像素点集的类标集合，N₀₁表示在 G中属于不同类而在S中属于同一类的像素点对的数目，N₁₀表示在S中属于不同类而在G中属 于同一类的像素点对的数目，N₁₁为在集合G和S中都属于同一类的像素点对的数目。

步骤8，利用已得到的最优分割中心点对待分割图像进行分割，实现步骤如下；

(8a)计算待分割图像中每一个像素点属于最优分割中心点中每个类的隶属度，获 得待分割图像像素点的隶属度矩阵；

(8b)从待分割图像像素点的隶属度矩阵中找出待分割图像中每个像素点所在列 中的最大隶属度，将这些最大隶属度在隶属度矩阵中位置的行标号，作为这些最大隶属度 所对应的像素点的类标号；

(8c)显示待分割图像中所有的类，完成图像分割。

以下结合附图和仿真结果，对本发明的技术效果作进一步详细描述：

1.仿真条件：

本发明采用MatlabR2009a软件在配置为corei32.30GHZ，内存2G，WINDOWS7系 统的计算机上进行。

2.仿真内容：

对一幅输入的人工合成图像进行图像分割，其结果如图2所示。

参照图2，图2(a)为输入的待分割图像原图，图2(b)为对输入的待分割图像加入高 斯0.01的噪声后的图像，图2(c)为DLSIAL方法的分割结果图，图2(d)为FCM-NSGA方法的分 割结果图，图2(e)为本发明方法的分割结果图。

由图2可以看出：本发明的图像分割结果中，白色斑点噪声和误检区域明显减少， 同时分割的准确率得到了有效的提高。

为了进一步分析分割结果，表1给出了图2分割结果图中精确的数据。

分割后的图像数据如表1所示，实施例中图像分割结果的性能采用准确率ACC、调 整后的兰德指数ARI，闵可夫斯基得分MS以及自动聚类得到的聚类个数K作为评价指标。其 中，mean表示三种方法独立运行20次的平均分割指标，best表示这20次中最好的分割指标。

表1不同方法在加噪图像上的分割结果

表1是本发明方法、DLSIAC方法以及FCM-NSGA方法对加入高斯0.01噪声的人工合 成图像进行分割的具体数据，由表中数据可以看出，本发明方法的分割图像能得到与图像 实际类别数最接近的类别数，而且分割准确率明显高于DLSIAL方法和FCM-NSGA方法，其MS 和ARI评价指标同样好于DLSIAC以及FCM-NSGA方法，这说明本发明方法在图像分割的准确 性和鲁棒性上得到有效的提高。