自适应分级粒子群算法的阈值图像分割研究

鲁 俊，邬春学，高 华

(1.上海理工大学 光电信息与计算机工程学院；2.上海理工大学 教务处,上海 200093)

自适应分级粒子群算法的阈值图像分割研究

鲁 俊1，邬春学1，高 华2

(1.上海理工大学 光电信息与计算机工程学院；2.上海理工大学 教务处,上海 200093)

提出了一种改进型的粒子群算法,并与阈值法相结合应用于图像分割。该改进粒子群算法通过调节惯性权重而获得合理有效的收敛速度；采用分级思想对粒子进行分类并对普通粒子速度更新公式进行修改，从而有效避免了优化过程中粒子的早熟现象；结合遗传算法中的交叉思想增加种群的多样性，增强全局搜索能力从而避免算法陷入局部最优解。将其应用于的阈值图像分割，试验结果表明：相对于标准PSO算法，该自适应分级粒子群算法具有较强的全局寻优能力，且收敛速度快、鲁棒性好，能很好地应用于阈值图像分割。

图像分割；聚类分析；自适应分级；粒子群算法；阈值

0 引言

图像分割是自动图像模式识别和场景分析的重要预处理环节。随着模式识别、计算机视觉、虚拟现实与仿真、卫星遥感图像技术的发展，越来越多的学者开始研究图像分割技术，提出了很多具有代表性的图像分割方法。图像分割问题复杂，每种方法都有一定的局限性，还没有能适用于所有图像的通用算法[1-3]。阈值法是一种简单高效的图像分割方法，它通过若干个阈值将图像的灰度级划分为几部分，认为属于某一区间的像素就是同一物体。阈值法简单高效，但是很难确定最优阈值，分割效果不稳定。

目前已有诸多阈值选取方法，如P-tile法、最大类间方差法(也称Otsu法)、最小误差法等。其中，日本学者Otsu在1979年提出的Otsu方法，通过灰度值来分割图像，将图像分为目标和背景，通过求它们之间的最大类间方差得到最佳阈值，与目标和背景分布模型无关，适用于各类图像，有很好的分割效果[4]。但是Otsu对每一个灰度值都要计算方差，运算时间长，很难适应实时图像分割。

粒子群算法(Particle Swarm Optimization,简称PSO)是一种基于群体智能的启发式优化算法，具有广泛的通用性和适应性。它根据速度搜索，充分发挥其记忆功能，利用个体及群体最优信息并行搜索问题最优解，广泛应用于函数优化问题的求解。但由于PSO算法易陷入局部最优解且收敛速度慢[5-6]，加之图像分割问题本身的复杂性，使得PSO算法在阈值图像分割结果上不理想。

本文在对标准 PSO算法进行深入学习和研究的基础上，提出一种改进粒子群算法( AGPSO)，它运用线性自适应惯性权重，在速度更新的过程中采用分级思想，针对普通粒子提出一种修正速度公式，同时采用交叉思想来更新速度，并将该算法与阈值法相结合应用于图像分割问题。通过与Otsu算法及标准PSO算法进行比较，表明AGPSO算法具有较高的可行性和有效性。

1 Otsu算法

Otsu是在最小二乘法的原理上衍生的一种基于分类类别函数，通过选取图像灰度阈值t将图像分割为几部分。计算图像各个灰度值的概率Pi，并在此基础上计算图像最大类间方差值，通过最大类间方差值来确定图像分割的灰度最佳阈值t[7]，算法流程如下：

设待处理图像的灰度集：G={0,1,2,…,L-1}，灰度t∈(G)的个数ni，总的像素N为：

(1)

灰度值为t的像素点出现的Pi为：

(2)

显然，

(3)

通过选取阈值灰度值ts将图像划分为两部分，灰度级处于t∈[0,ts-1]的称为背景部分类(C0)；灰度级处于t∈[ts,L-1]的称为目标部分类(C1)，表示图像中的目标物。

背景部分类出现概率m0和灰度均值x0分别为：

(4)

目标部分类出现概率m1和灰度均值x1分别为：

(5)

图像总的灰度均值xS为：

(6)

则背景部分类C0和目标部分类C1的类间方差σ2可表示为：

(7)

由式(4)至式(7)可进一步推出：

(8)

由式(1)～式(8)可以得出类间方差σ2是关于阈值变量t的函数，Otsu算法就是以σ2为判别函数，选取t使σ2最大得到图像的最佳阈值。阈值的选择是基于灰度的统计，与具体图像没有关系，有较高的通用性，但是Otsu对每一个灰度都要计算其σ2，运算量大，很难进行实时图像分割。

2 AGPSO算法基本原理

2.1 基本PSO算法

粒子群算法将每个个体Xi=(xi1，xi2，…，xiD)认为是在D维空间中的一个无体积和重量的收索粒子，并以特定的速度Vi=(vi1，vi2，…，viD)飞行在搜索空间，将Xi带入目标函数即可求出其适应度，粒子的飞行速度由个体的最佳坐标Pi=(pi1，pi2，…，piD)和群体的最佳坐标Pg=(pg1，pg2，…，pgD)进行动态调整。粒子速度位置更新公式如下：

(9)

(10)

其中，g为迭代次数，i=1，2，……G，为种群数目；d=1，2，…，D为搜索空间维数；w为惯性权重，代表父代的粒子速度对子代的速度作用；c1、c2为学习因子，用来确定粒子最优位置和全局最优位置对粒子速度更新的影响。

2.2 改进粒子群算法AGPSO

基本PSO算法不足之处是容易陷入局部最优。每个粒子参照Pid和Pgd来优化速度和位置，一旦Pgd陷入局部最优，则整个种群会陷入局部极值。本文通过3个方面的改进来保证种群的多样性以及收敛速度：①惯性权重的线性调整；②分级思想的引入并对普通粒子采用改进的速度更新公式；③仿照遗传算法对粒子速度进行交叉操作。

2.2.1 惯性权重的自适应调整

惯性权重w代表了粒子父代的速度对子代速度的作用。通过设置其取值大小可改变PSO 算法的全局与局部寻优能力。对于全局优化问题，通常的做法是在算法前期采用较大的惯性权重以提高粒子的探索(exploration)能力。在算法的后期，为加快收敛速度而使粒子拥有较高的开发(exploitation)能力，采用较小的惯性权重[8-10]。本文采用自适应的线性递减权重(linearly decreasing weight)策略，随着迭代次数的增多，线性减少w值的大小，公式如下：

(11)

式(11)中，w0为惯性权重的初始值，wG为进化到最大代数时的惯性权重，G为迭代次数的最大值，g为当前代数。参数设定：w0=0.9，wG=0.4。

2.2.2 基于分级思想的普通粒子速度更新修正公式

采用分级思想优化粒子群的信息交互模型，将原全局寻优算法变为局部信息交换算法。分级原理是将适应值相近的个体划分在同一级，各级之间相似性依据适应值之间的欧氏距离来确定[11-12]。先将适应值从大到小排序，以最好适应值和最差适应度之差将粒子动态分级，按照粒子的适应度值将粒子评定为优秀、一般、较差3类，它们所占比例分别为40%、40%、20% 。

针对一般粒子提出修正的更新公式：

(12)

其中Pbd为优秀粒子的个体最优位置，一般粒子随机选取优秀粒子作为进化方向，表现越好的粒子被选中的概率越高，从而确保了越优秀的粒子被选中的机会越大。具体计算方法如下：

(13)

(14)

i=1,2，…,bp为优秀粒子按照适应度大小排列而来的序列数,则p1+p2+…+pbp=1,对于优秀粒子的选中概率，可以以[0,1]区间内的随机数r来表示，如果Pi

2.2.3 采用交叉的速度更新

通过学习生物进化思想，粒子群中的每个粒子都有一个杂交概率，这个杂交概率的大小是随机的，与粒子个体无关。在没代迭代中，依据杂交概率选取相应数目粒子。这些粒子随机两两杂交，生成等数目的子代粒子，杂交过的个体不能再次杂交，保证每个个体都有变异机会，同时只保留杂交后的子代，以保持种群数目的稳定[13-14]。经过杂交操作后，由亲代个体随机生成两个新的速度，因此子代速度只有方向上的改变，数量上没有改变。

(15)

(16)

式中r的取值为均匀分布在[0，1]之间的随机数，杂交变异的经验值此处选0.2。

2.2.4 AGPSO阈值图像分割

Otsu算法本质就是找到一个最佳的灰度阈值t，使得式(8)达到最大值。但是传统的Otsu算法有计算量大、时间复杂度高的不足。本文将AGPSO算法与Otsu结合，以类间方差σ2作为AGPSO的适应度函数；使用灰度阈值t作为粒子位置，根据公式(10)更新粒子位置；采用分级和生物进化杂交变异思想，根据公式(9)来更新优秀粒子和普通粒子速度，同时对普通粒子采用公式(12)来更新速度。然后选取粒子按照公式(15)、(16)进行交叉变异操作；使用公式(11)自动调整惯性权重值，在一维灰度空间中迭代搜索使σ2最大的灰度值，算法步骤如下：①令t=Rand(0,255)，初始化每个粒子的速度和位置，随机生成一个规模为POP的种群，随机生成粒子初始速度Vi在[-Vdmax,Vdmax]范围内；②输入图像，根据式(3)计算图像中各灰度出现的概率。设图像总像素数为N，根据式(1)至式(6)计算其大小；③根据式(8)计算每个粒子的适应度；④将适应度与它经过的最好位置Pid比较，若优于Pid，则将其替换最好位置Pid；⑤计算每个粒子的适应度并与群体所经过的最好位置Pgd比较，若优于Pgd，则将其替换全局最好位置Pgd； ⑥按照粒子适应度大小排序，使用分级思想对粒子进行分类；⑦根据公式(9)来更新优秀粒子和一般粒子的速度，对一般粒子采用公式(12)来更新速度，完毕后选取粒子按照公式(15)、(16)进行交叉变异操作；⑧按照公式(10)更新粒子位置；⑨判断是否满足终止条件，若满足则终止；否则，转向步骤③继续执行；⑩根据得到的阈值Pgd对图像进行分割。

3 实验分析

为了检验AGPSO算法的有效性，在相同的硬件和软件条件下，选取图像分别对经典Otsu算法、基于标准PSO+Otsu分割算法和本文算法进行测试。参数设置为：P0P(种群)大小为30，G(最大迭代次数)为100次，惯性权重采用式(10)进行调整，加速因子c1=c2=2。Vdmax=256，实验结果如图1所示。

表1和表2分别列举了几种算法在不同图像中20次实验结果的平均数据。从表1和表2的结果容易得出，相较于传统Otsu算法，本文算法有迭代次数少、效率高的优点；相较于标准PSO+Otsu算法，本文算法得出的阈值t更好，且运算效率更高。

表1 Lena图像

表2 飞机图像

4 结语

本文针对传统粒子群算法收敛速度慢、易陷入局部最优的问题，提出了自适应分级的AGPSO算法，将其与阈值法结合应用于图像分割。AGPSO是一种高效且全局搜索能力强的优化算法，通过AGPSO算法实验并与其它算法对比，表明AGPSO算法在一定程度上有效避免了局部最优现象，收敛速度较快，精度较高，最终结果符合图像分割预期。将其应用于阈值图像分割，可提高阈值图像分割的准确率及分割速度，可很好地应用于实时图像分割。

[1] 卢振泰，陈武凡，吕庆文.基于互信息量的寄生虫卵图像自动优化分割[J].计算机应用研究,2007,24(11):301-302.

[2] GARC A-P REZ L,GARC A-ALEGRE M C,MARCHANT J,et al.Dy-namic threshold selection for image segmentation of natural struc -tures based upon a performance criterion[C].Proc of 3ECPA-3 European Conference on Precision Agriculture,2001.

[3] 黄港，李俊，潘金贵.基于粒子群优化方法的2维Otsu快速图像分割算法[J].中国图象图形学报，2011，16(3)：377-381.

[4] 张新娟.基于改进粒子群算法的阈值图像分割[J].中国图象图形学报,2013(6)：36-40.

[5] CHUN-AN LIU.New dynamic constrained optimzation PSO algorithm[C].Jinan(China),Proceedings 4th International Conference on Natural Computation(ICNC2008),2008.

[6] 刘申晓，王学春，常朝稳.基于改进粒子群优化算法的Otsu图像分割方法[J].计算机科学，2015(6)：125-129.

[7] 韦钢.电力系统分析基础[M].第1版.北京：中国电力出版社，2006.

[8] 林玉娥.粒子群优化算法的改进及其在管道保温优化设计中的应用[D].大庆：大庆石油学院，2006.

[9] 栗然，唐凡，刘英培，等.基于自适应变异粒子群算法的双馈风电机组等值建模[J].电力系统自动化，2012，36(4)：22-27.

[10] 张庭场，耿光飞.基于改进粒子群算法的中压配电网无功优化[J].电网技术，2012，36(2)：158-162.

[11] 刘世成，张建华，刘宗岐.并行自适应粒子群算法在电力系统无功优化中的应用[J].电网技术，2012，36(1)：108-112.

[12] 张磊.基于分级的粒子群优化算法研究[D].广州：广东工业大学，2011.

[13] 周双喜，杨彬刘.实现无功优化的新算法——遗传算法[J].电力系统自动化，1995，11(19)：19-21.

[14] 向铁元，周青山，李富鹏，等.小生境遗传算法在无功优化中的应用研究[J].中国电机工程学报，2005，25(17)：48-51.

(责任编辑：杜能钢)

国家自然科学基金项目(61202376) ; 上海市教育基金会晨光计划基金项目(10CG49)

鲁俊(1990-)，男，安徽芜湖人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为图像分割、人工智能；邬春学(1964-)，男，上海人，博士，上海理工大学光电信息与计算机工程学院教授、硕士生导师，研究方向为嵌入式系统及应用、计算机控制技术及工程、软件工程及软件开发技术；高华(1989-)，女，上海人，硕士，上海理工大学教务处助理工程师,研究方向为图像分割、机器学习。

10.11907/rjdk.162590

TP317.4

A

1672-7800(2017)003-0170-03