基于改进多目标粒子群优化聚类的图像分割方法

摘要

本发明公开了基于改进多目标粒子群优化聚类的图像分割方法，主要解决现有聚类图像分割技术评价指标单一和区域杂点多，分割不理想等问题。其实现步骤为：(1)输入原始图像，提取像素特征，并进行分水岭分割，产生聚类数据；(2)利用聚类数据初始化种群(3)升级种群中各粒子的速度和位置(4)评价各新粒子，计算聚合值并升级理想点(5)升级各粒子的最优位置，升级leader粒子库和外部粒子库(6)更新迭代次数，若达到预先设定的最大迭代次数，则输出外部粒子库，否则继续执行步骤(3)(7)在输出的外部粒子库中，根据聚合值的大小选择最优个体，根据最优个体进行标记，得到分割结果。本发明与现有技术相比，边缘保持较好，分割正确率高，可用于SAR图像的目标识别。

说明书

技术领域

本发明属于图像处理领域，特别是涉及基于改进多目标粒子群优化聚类的图像分割方法，可应用于目标识别。 

背景技术

图像分割作为一种重要的图像处理技术，在理论研究和实际应用中都得到了人们的广泛重视。为后续工作有效进行而将图像划分为若干个有意义的区域的技术称为图像分割。图像分割是后续工作有效进行的关键，从图像处理到图像分析的关键步骤。目前,从分割操作策略上讲,可以分为基于边界的方法，基于区域生成的分割方法，基于聚类的分割方法等。目前，人们更多采用基于进化聚类的方法来进行图像分割。进化聚类图像分割算法主要是进化计算与聚类技术相结合应用到图像分割上的算法，主要的核心是进化聚类算法的研究。在现有的聚类方法中,通常把基于目标函数的聚类问题归结为一个优化问题，再结合进化计算对聚类问题进行智能优化。随着多目标技术的发展，出现了多目标进化聚类技术，基于多目标进化聚类方法的优点在于它可以获得在多个目标函数间权衡的聚类结果。 

现有的多目标进化算法中，多目标粒子群算法是一种崭新的随机优化方法，具有程序实现简单、控制参数少的特点，所以得到了广泛应用。在现有的进化聚类图像分割算法中，单目标聚类图像分割算法存在评价单一，细节保持不好等缺点，而在现有的多目标进化聚类图像分割技术中，缺乏种群的多样性，造成分割不理想，分割正确率低，计算复杂度高等缺点。 

发明内容

本发明的目的在于克服上述已有技术的不足，提出一种基于改进多目标粒子群优化聚类的图像分割方法，本发明选取了两个互补的目标函数，将分解的理论融入到多目标粒子群优化算法中，改善现有方法的目标函数单一性和边缘细节保持不理想等缺点。 

基于改进多目标粒子群优化聚类的图像分割方法，包括如下步骤： 

（1）输入待分割图像，提取待分割图像的特征，并计算该待分割图像的梯度，得到梯度 

图像，对梯度图像进行分水岭分割，得到N个互不重叠的区域，N≥1000； 

（2）对每个区域中所有像素点特征取均值，获得每一个区域的特征向量，作为初始聚类数据点集合W＝{w₁,w₂…w_N}； 

（3）利用初始聚类数据点集合，随机初始化大小为M的种群: 

（3a）随机初始化各粒子的位置X＝{x₁,x₂…x_M}、速度V＝{v1_,v₂…v_M}，每个粒子 的位置x_m代表一种分割结果，m＝1,2,…M，M＝50； 

（3b）将各粒子的当前位置作为各粒子的最优位置； 

（4）根据每个粒子的位置计算每个粒子的目标函数值F，F＝[f₁ f₂]，其中，f₁为类内方差，f₂为类间连接； 

（5）根据各粒子的位置和目标函数值初始化leader粒子库和外部粒子库； 

（6）根据目标函数值初始化理想点Z^*，Z^*＝[Z₁ Z₂]，其中Z₁为第一个目标函数f₁到目前为止找到的最小值，其中Z₂为第二个目标函数f₂到目前为止找到的最小值； 

（7）根据各粒子的目标函数值标准化各粒子的目标函数值，并计算各粒子的聚合值； 

（8）升级各个粒子的速度和位置；升级公式按如下进行： 

$v_i^{t+1}=v_i^t+(p_i^t-x_i^t)+(p_g^t-x_i^t)$

$x_i^{t+1}=x_i^t+v_i^{t+1}$

其中，表示t+1代第i个粒子的速度，表示t代第i个粒子的速度，表示t代第i个粒子的位置；表示t+1代第i个粒子的位置，表示t代第i个粒子的最好位置，表示t代leader粒子库中的粒子； 

（9）对每个新粒子进行评价，即对新粒子计算每个目标函数的值； 

（10）根据每个目标函数的值，升级种群的理想点； 

（11）根据每个粒子的目标函数值计算每个粒子的聚合函数值； 

（12）根据每个粒子的聚合函数的值的大小升级每个粒子的最优位置：如果新粒子的聚合函数值比粒子最优位置的聚合值小，则用新粒子的位置代替粒子的最优位置，否则粒子最优位置不变； 

（13）升级leaders粒子库和外部粒子库； 

（14）更新迭代次数t，直到迭代次数达到预先设定的最大值maxgen，则输出外部种群，否则返回到步骤（6）进行下一代迭代； 

（15）在输出的外部种群中选择最优解；利用分解过程中得到的聚合值来进行最优解的选取；具体实现是先选择使用者设定的类别数的非支配解作为候选解；然后分别将每个候选解在聚合函数上聚合值最小的个体作为最优个体；最后将最优个体所对应的类别标号作为像素的灰度值，得到图像分割结果。 

所述步骤（1）所述的对每个区域中所有像素点特征取均值，获得每一个区域的特征向量，按照以下步骤进行： 

（1a）对于任意像素点i，利用小波分解，提取图像的10维小波特征； 

（1b）对于任意像素点i，计算0°,45°,90°,135°四个方向上的灰度共生矩阵，选取该四个矩阵上的三个统计量，分别为对比度、同质性和角二阶，获得像素点i的12维纹理特征； 

（1c）将上述10维小波特征向量和12维纹理特征向量合并成22维纹理特征向量，作为第i个像素点的特征； 

（1d）对原始图像中的所有像素点重复步骤（1a）-（1c），得到原始图像所有像素点的纹理特征。 

所述步骤（4）中f₁代表聚类紧凑性，聚类紧凑性是计算所有数据点到其聚类中心的类内距离和，f₁(x)，通过如下公式进行计算： 

$f_1\left(x\right)=\underset{x_k\in x}{\Sigma }\underset{i\in x_k}{\Sigma }\delta (i,{\mu }_k)$

其中，f₁(x)为待聚类数据集的类内距离和；x为待聚类数据集；Σ为算术运算中的累加符号；x_k为待聚类数据集的第k类；∈为集合中的属于符号；i为一个类别中的一个数据点；δ(i,μ_k)为欧式距离函数；μ_k为待聚类数据的第k类的聚类中心。 

所述步骤（4）中第二个目标函数值f₂代表聚类连通性，聚类连通性用于评估相邻数据点被划分到同一个类别的相邻度，f₂(x)通过如下公式计算： 

$f_2\left(x\right)=\underset{i=1}{\overset{m}{\Sigma }}\left(\underset{j=1}{\overset{L}{\Sigma }}{x}_{i,j}\right)$

$x_{i,j}=\left(\begin{array}{c}\frac{1}{j},\mathrm{if}\exists x_k:i\in x_k^j\in x_k\\ 0,\mathrm{else}\end{array}\right)$

其中，f₂(x)为类间距离和；x为待聚类数据集；m为待聚类数据点的个数；Σ为算术运算中的累加符号；i为一个数据点；L是最近邻的个数，L＝10；j为近邻点；x_i,j为第i个数据点与其第j个最近邻的关系值，当第i个数据点和第j个数据点属于同一类，则x_i,j取 0，否则取1/j。 

所述步骤（7）所标准化目标函数值，按如下公式进行： 

$S\left(f_i\left(x\right)\right)=1/(1+e^{-f_i\left(x\right)})$

其中，f_i(x)为第i个目标,i＝1,2。 

所述步骤（7）中所述的各粒子的聚合函数值，任意粒子j的聚合函数值g_j(x|λ^j,z^*)，按如下公式进行： 

minimize  g_j(x|λ^j,z^*)＝d₁+θd₂

其中，d₁＝||(F_j(x)-z^*)^Tλ^j||/||λ^j||,d₂＝||(F_j(x)-z^*)-d₁λ^j/||λ^j||||，${\lambda }^j=\left(\begin{array}{cc}{\lambda }_1^j& {\lambda }_2^j\end{array}\right)$是第j个粒子的权值，x表示一个粒子，F_j(x)表示第j个粒子的目标函数值，z^*表示理想点，|是算术运算中的条件符号，||·||表示2范数，(·)^T为矩阵转置运算，θ取为0.5。 

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

1、本发明由于选取了两个互补的目标函数，增加了评价的多样性，保证了图像信息的完整性； 

2、本发明将分解理论融入到多目标粒子群中，不仅提高了非支配解集的多样性而且增加了非支配解集的数量，从而获得更优秀的解，进一步提高了分割精确度； 

附图说明

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

图2(a)为三类合成纹理图像image1； 

图2(b)为图像image1的理想分割结果； 

图2(c)为用现有多目标进化聚类方法对图2(a)进行分割得到的结果； 

图2(d)为用现有多目标粒子群优化聚类方法对图2(a)进行分割得到的结果； 

图2(e)为用本发明方法对图2(a)进行分割得到的结果。 

图3(a)为四类合成纹理图像image2； 

图3(b)为对图像image2的理想分割结果； 

图3(c)为用现有多目标进化聚类方法对图3(a)进行分割得到的结果； 

图3(d)为用现有多目标粒子群优化聚类方法对图3(a)进行分割得到的结果； 

图3(e)为用本发明方法对图3(a)进行分割得到的结果； 

图4(a)为两类机载SAR原图像，分为田地和森林； 

图4(b)为用现有多目标进化聚类方法对图4(a)进行分割得到的结果； 

图4(c)为用现有多目标粒子群优化聚类方法对图4(a)进行分割得到的结果； 

图4(d)为用本发明方法对图4(a)进行分割得到的结果； 

图5(a)为三类SAR图像，分为植被、农作物和河流； 

图5(b)为用现有多目标进化聚类方法对图5(a)进行分割得到的结果； 

图5(c)为用现有多目标粒子群优化聚类方法对图5(a)进行分割得到的结果； 

图5(d)为用本发明方法对图5(a)进行分割得到的结果。 

具体实施方式

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

步骤一、输入待分割图像，提取该图像的特征。 

(1a)对于任意像素点i，利用小波分解，提取图像的10维小波特征向量； 

(1b)对于任意像素点i，计算0°,45°,90°,135°四个方向上的灰度共生矩阵，选取该四个矩阵上的三个统计量，即对比度、同质性和角二阶，获得像素点i的12维纹理特征向量； 

(1c)将上述10维小波特征向量和12维纹理特征向量合并成22维特征向量，作为第i个像素点的纹理特征； 

(1d)对图像中的所有像素点重复步骤(1a)-(1c),得到原始图像所有像素点的特征。 

步骤二、计算待分割图像的梯度。 

对待分割图像分别进行膨胀变换和腐蚀变换，再用膨胀变换后的结果减去其腐蚀变换后的结果，由此得到待分割图像形态梯度图像。 

步骤三、对形态梯度图像进行分水岭分割，得到N个互不重叠的区域，N≥1000，对每个区域中所有像素点特征取均值，获得每一个区域的特征向量，作为初始聚类数据点集合：Z＝{z₁,z₂…z_N}。 

步骤四、根据待聚类数据初始化大小为M的种群: 

（4a）初始种群各粒子的位置X＝{x₁,x₂,....xM}利用Prim算法最小生成树，数的权值是两个数据点之间的欧式距离，根据最小生成树原理和权值矩阵，可得到N个数据点之间的连接图，随机断开K处并通过解码得到个体，每个个体代表一种分割结果。随机初始化种群中各粒子的速度V＝{v₁,v₂…v_M}。 

（4b）将各粒子的当前位置作为各粒子的最优位置，并为每个粒子j分配权重向量λ^j， 是第j个粒子的权值；${\lambda }_1^j=j/M,{\lambda }_2^j=(M-j)/M,j=\mathrm{1,2},...,M.$

步骤五、根据每个粒子的位置计算每个粒子的目标函数值F，F＝[f₁ f₂]，其中，f₁为类内方差，f₂为类间连接。 

（5a）第一个目标函数值f₁代表聚类紧凑性，聚类紧凑性是计算所有数据点到其聚类中心的类内距离和，f₁(x)，通过如下公式进行计算： 

$f_1\left(x\right)=\underset{x_k\in x}{\Sigma }\underset{i\in x_k}{\Sigma }\delta (i,{\mu }_k)$

其中，f₁(x)为待聚类数据集的类内距离和；x为待聚类数据集；Σ为算术运算中的累加符号；x_k为待聚类数据集的第k类；∈为集合中的属于符号；i为一个类别中的一个数据点；δ(i,μ_k)为欧式距离函数；μ_k为待聚类数据的第k类的聚类中心。 

（5b）第二个目标函数值f₂代表聚类连通性，聚类连通性用于评估相邻数据点被划分到同一个类别的相邻度，f₂(x)通过如下公式计算： 

$f_2\left(x\right)=\underset{i=1}{\overset{m}{\Sigma }}\left(\underset{j=1}{\overset{L}{\Sigma }}{x}_{i,j}\right)$

$x_{i,j}=\left(\begin{array}{c}\frac{1}{j},\mathrm{if}\exists x_k:i\in x_k^j\in x_k\\ 0,\mathrm{else}\end{array}\right)$

其中，f₂(x)为类间距离和；x为待聚类数据集；m为待聚类数据点的个数；Σ为算术运算中的累加符号；i为一个数据点；L是最近邻的个数，L＝10；j为近邻点；x_i,j为第i个数据点与其第j个最近邻的关系值，当第i个数据点和第j个数据点属于同一类，则x_i,j取0，否则取1/j。 

步骤六：根据各粒子的位置和目标函数值选择非支配粒子，将非支配粒子存入leader粒子库和外部粒子库，即初始化leader粒子库和外部粒子库。 

步骤七、根据各粒子的目标函数值标准化各粒子的目标函数值，并计算各粒子的聚合值。（7a）为了对每一个粒子达到公平的原则，对目标函数进行标准化，按如下公式计算： 

$S\left(f_i\left(x\right)\right)=1/(1+e^{-f_i\left(x\right)})$

其中，f_i(x)为第i个目标,i＝1,2。 

（7b）第j个粒子的聚合函数值g_j(x|λ^j,z^*)，按如下公式进行： 

minimize  g_j(x|λ^j,z^*)＝d₁+θd₂

其中，d₁＝||(F_j(x)-z^*)^Tλ^j||/||λ^j||,d₂＝||(F_j(x)-z^*)-d₁λ^j/||λ^j||||，${\lambda }^j=\left(\begin{array}{cc}{\lambda }_1^j& {\lambda }_2^j\end{array}\right)$是第j个粒子的权值，x表示一个粒子，F_j(x)表示第j个粒子的目标函数值，z^*表示理想点，|是算术运算中的条件符号，||·||表示2范数，(·)^T为矩阵转置运算，θ取为0.5。 

步骤八、根据目标函数值初始化理想点Z^*，Z^*＝[Z₁ Z₂]，其中Z₁为第一个目标函数f₁到目前为止找到的最小值，其中Z₂为第二个目标函数f₂到目前为止找到的最小值。 

步骤九、升级各个粒子的速度和位置。粒子的速度和位置更新公式，按如下进行， 

$v_i^{t+1}=v_i^t+(p_i^t-x_i^t)+(p_g^t-x_i^t)$

$x_i^{t+1}=x_i^t+v_i^{t+1}$

其中，表示t+1代第i个粒子的速度，表示t代第i个粒子的速度，表示t代第i个粒子的位置；表示t+1代第i个粒子的位置，表示t代第i个粒子的最好位置，表示t代leader粒子库中的粒子，该粒子的选取的规则是选择leader粒子库中聚合值最小的粒子，即leader库中最优的粒子。 

步骤十、对每个新粒子进行评价，即对新粒子计算每个目标函数的值。 

步骤十一、根据各个新粒子每个目标函数的值，升级种群的理想点：如果所有新粒子的第一个目标函数值的最小值f₁^min小于Z₁则用f₁^min代替Z₁，否则Z₁不变；如果所有新粒子的第二个目标函数值的最小值f₂^min小于Z₂则用f₂^min代替Z₂，否则Z₂不变。 

步骤十二、根据各粒子的目标函数值标准化各粒子的目标函数值并计算其聚合函数值。 

步骤十三、根据聚合函数的值的大小升级各粒子的最优位置：如果新粒子的聚合函数值比粒子最优位置的聚合值小，则用新粒子的位置代替粒子的最优位置，否则粒子最优位置不变。由此根据支配关系升级leader粒子库。 

步骤十四、根据各个新粒子和它们之间的支配关系升级外部粒子库。 

步骤十五、更新迭代次数t，直到迭代次数达到预先设定的最大值maxgen，则输出外部种群，否则返回到步骤九进行下一代迭代； 

步骤十六、在输出的外部种群中选择最优解。利用分解过程中得到的聚合值来进行最优解的选取。具体实现是先选择使用者设定的类别数的非支配解作为候选解；然后分别将每个候选解在聚合函数上聚合值最小的个体作为最优个体；最后将最优个体所对应的类别标号作为像素的灰度值，得到图像分割结果。 

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

1.仿真条件：本发明的仿真在windowsXP，SPI，CPUInterCore2Duo，基本频率2.33Ghz，软件平台为MatlabR2011a运行。 

2.仿真内容：应用本发明方法和多目标进化聚类方法，多目标粒子群优化聚类方法分别对两幅合成纹理图像和两幅SAR图像进行分割实验，并从细节信息的完整性、同质区域的内部一致性和边缘边界的清晰性评价这些方法的各自性能。合成纹理图像还可以用平均分割正确率结果来评价各种方法的性能。 

仿真1，用本发明方法以及多目标进化聚类方法，多目标粒子群优化聚类方法分别对两类合成纹理图像image1进行分割，其结果如图2所示。其中图2(a)为三类合成纹理图像image1；图2(b)为图像image1的理想分割结果；图2(c)为用现有多目标进化聚类方法对图2(a)进行分割得到的结果；图2(d)为用现有多目标粒子群优化聚类方法对图2(a)进行分割得到的结果；图2(e)为用本发明方法对图2(a)进行分割得到的结果。 

仿真2，用本发明方法以及多目标进化聚类方法，多目标粒子群优化聚类方法对四类合成纹理图像image2进行分割，其结果如图3所示。其中图3(a)为四类合成纹理图像image2；图3(b)为对图像image2的理想分割结果；图3(c)为用现有多目标进化聚类方法对图3(a)进行分割得到的结果；图3(d)为用现有多目标粒子群优化聚类方法对图3(a)进行分割得到的结果；图3(e)为用本发明方法对图3(a)进行分割得到的结果。 

仿真3，用本发明方法以及多目标进化聚类方法，多目标粒子群优化聚类方法分别对SAR图像分割，其结果如图4所示。其中图4(a)为两类机载SAR原图像，分为田地和森林；图4(b)为用现有多目标进化聚类方法对图4(a)进行分割得到的结果；图4(c)为用现有多目标粒子群优化聚类方法对图4(a)进行分割得到的结果；图4(d)为用本发明方法对图4(a)进行分割得到的结果。 

仿真4，用本发明方法以及多目标进化聚类方法，多目标粒子群优化聚类方法分别对Ku波段的SAR图像分割，其结果如图5所示。其中图5(a)为三类SAR图像，分为植被、农作物和河流；图5(b)为用现有多目标进化聚类方法对图5(a)进行分割得到的结果；图5(c)为用现有多目标粒子群优化聚类方法对图5(a)进行分割得到的结果；图5(d)为用本发明方法对图5(a)进行分割得到的结果。 

3.仿真结果分析： 

从图2(c)，2(d)和2(e)的分割结果中可以看出，本发明在边缘细节保持上都比其他两个现有方法好，且平均分割正确率也是最高的。 

从图3(c)，3(d)和3(e)的分割结果中可以看出，本发明在边缘细节保持上优于多目标进化聚类算法，区域一致性上优于多目标粒子群优化聚类算法且平均分割正确率也是最高的。 

从图4(c)和4(d)的分割结果中可以看出，本发明在区域一致性上优于多目标进化聚类算法和多目标粒子群优化聚类算法，本发明在森林得到了完整的分割，而其他两个方法均缺少了一小部分森林，本发明得到了最好的分割。 

从图5(c)和5(d)的分割结果中可以看出，本发明相比较多目标进化聚类算法，将一些小的植被区域分割出来，本发明相比较于多目标粒子群优化聚类算法，在农作物区域上保持了一致性，本发明得到了最好的分割。 

表1给出了不同的方法对Image1和Image2的独立分割运行20次后的平均分割正确率。多目标进化聚类算法用MOCK表示，多目标粒子群优化聚类算法用MPSO表示，本发明用DMPSO表示。 

表1  不同的方法对Image1和Image2的分割正确率 

图像 MOCK MPSO DMPSO Image1 0.8959 0.9203 0.9463 Image2 0.8943 0.9486 0.9719

从表1可见，本发明与其他两种算法的对比，得到了最高的平均正确率。