基于改进量子粒子群优化的多阈值图像分割算法

Foundation item: Supported by the National Natural Science Foundation of China(61372140)

基于改进量子粒子群优化的多阈值图像分割算法*

杨震伦闵华清罗荣华

(华南理工大学 计算机科学与工程学院, 广东 广州 510006)

摘要：为提升工程应用中图像分割的质量,在变异量子粒子群算法的基础上进行改进,并结合最大类间方差法提出了一种基于改进量子粒子群优化(QPSO)的多阈值图像分割算法.该算法结合贝叶斯定理与粒子搜索过程中的历史信息构建了一个记忆向量,然后根据记忆向量对每个粒子的行为进行预测,并以此自动设置各粒子的变异概率,使算法在保持一定局部开发能力的同时提升全局搜索能力.在Berkeley数据集上的仿真实验结果表明,与两种基于粒子群的图像分割算法相比,文中算法能获得更为稳定且清晰的图像分割结果.

关键词：量子粒子群优化;记忆信息挖掘;多阈值;图像分割

收稿日期：2014-07-06

基金项目：* 国家自然科学基金资助项目(61372140)

作者简介：杨震伦(1978-),男,博士生,主要从事进化算法和图像处理研究.E-mail: wugdone@yeah.net

文章编号：1000-565X(2015)05-0126-06

中图分类号：TP391.41

doi:10.3969/j.issn.1000-565X.2015.05.020

收稿日期：2014-12-08

图像的多阈值分割可以归为一个典型的优化问题,常用的方法是结合一些最优化算法来确定合适的阈值.粒子群算法是一种高效的优化算法,其结构简单、运算复杂度低等优点正好适用于解决多阈值图像分割中所遇到的难题.而量子粒子群优化(QPSO)算法是粒子群改进算法中较有影响力的一种,其主要贡献是结合量子物理的思想修改了粒子群的位置更新方程,使得粒子群能模拟量子空间中的粒子进行搜索.与标准粒子群优化算法相比,QPSO算法主要具有收敛速度快、全局收敛性优及参数易于调整等优点.近些年,有学者研究了基于QPSO的多阈值分割算法,高浩等[1]将QPSO算法和最小误差法相结合,提出了一种图像多阈值分割方法.冯斌等[2]将QPSO算法应用到二维最大类间方差(OTSU)法的最优二维阈值搜索上.Gao等[3]提出了一种基于合作学习方法的改进QPSO算法并应用到基于OTSU方法的多阈值图像分割上.目前大多数基于QPSO的图像分割算法都是将最优阈值的获取问题模型化成一个目标准则函数的优化问题,以提高搜索最优阈值的效率且在阈值个数增大时并不增加太多的运算量.各类应用对于图像分割算法的需求虽然不尽相同,但对于算法的效率、智能化程度及处理速度等性能的要求是不断增长的.

虽然QPSO算法的全局收敛能力较强,但仍然存在一定程度的早熟收敛问题.一些改进算法在近年来被提出以解决这个问题,其中最典型的一种改进思路是引入变异因子.Coelho[4]为QPSO引入了混沌变异因子,主要对粒子位置更新公式中的ln(1/randu)进行变异.石锦风等[5]提出了一种基于变异的QPSO算法,其主要做法是利用符合柯西分布的随机值对全局最优gbest或平均最优mbest进行扰动以增强粒子的全局搜索能力.林星等[6]提出了一种边界变异的QPSO算法,当粒子到达搜索域的边界时,引入随机变异以避免越界的粒子聚集在边界处.这类基于变异的改进QPSO算法存在两个问题:①对于不同的粒子,变异概率是相同的,缺乏针对性；②变异概率需要事先确定,对于不同问题需要设置不同的变异概率.为此,文中针对变异QPSO算法面临的问题,提出了一种改进的变异QPSO算法,并根据多阈值图像分割应用的特点,将所提出的算法结合OTSU方法实现了一种灰度图像的多阈值分割算法.

1算法设计

记忆在人们的日常行为中扮演了重要的角色,通常在做决定前,人们会根据之前的记忆来试图进行相应事件的预测.记忆包含“记”和“忆”,实际上是事件发生时对某些内容的记录及在需要使用这些信息时进行回顾的过程.记忆的影响能用多种模型进行描述,其中贝叶斯定理阐述了某个事件的先验概率与该事件的证据被观察到之后的后验概率之间的关系,是对记忆的影响进行描述的较为通用的模型.在贝叶斯定理中,通过先验分布和所采集的数据来构建相应的后验分布,而后验分布表征了获取相应数据之后的知识状态.根据这个知识状态可对后续数据结果进行推断,能实现在获得不完全信息的情况下对随机事件进行一定的预测,如果有一个较为适当的先验分布,基于贝叶斯定理进行的推断则较为准确[7].

由于QPSO算法中粒子的行为相对独立且具有并行搜索特性,笔者在前期研究中提出了一种方法[8]:首先根据贝叶斯定理及粒子搜索过程中的历史信息来构建一个记忆向量,并利用该向量来对粒子的行为进行预测,然后基于这种预测对不同的粒子施以差异化的影响,从而使粒子的搜索更有效率.基于上述记忆信息挖掘方法,文中采用了一种在记忆向量的利用上更为合理和有效的策略.

1.1记忆向量

QPSO算法中粒子i的位置更新公式为

Xi(t+1)=Qi(t)±

(1)

式中:randu为[0,1]范围内均匀分布的随机数;β为收缩扩张因子,用来控制收敛速度的参数;mbest为主流思想或者平均最优位置的虚拟点,该虚拟点并不与一个实际的粒子所在的位置对应,而是通过计算所有粒子的自身最优位置pbest的均值来得到;Qi为粒子i的局部吸引子,根据Clerc[9]的轨道分析,无论采用什么模型,为了保证粒子群算法的收敛性,每个粒子必须收敛到自身局部吸引子上.

根据QPSO算法的更新公式可知,粒子每次出现在以局部吸引子为中心的区域的某个位置上,文中利用记忆向量来预测粒子在下一代中出现在远离其局部吸引子的概率.由于在算法运行初期没有任何先验信息,故记忆向量的每个元素可初始化为1/N,其中N为粒子数.根据贝叶斯定理,记忆向量Mems可用迭代式计算:

(2)

式中:Mems(t+1,i)是后验概率,表示粒子i在下一代中出现在远离其局部吸引子的位置的概率;在迭代搜索中,上一代的后验概率Mems(t,i)可作为当前代的先验概率;fitdis(t,i)表示根据上一代的记忆向量,粒子i在本次更新中应该出现的位置到粒子群主流趋势的距离的建议,此处的主流趋势可以与mbest或gbest对应,也可以与这些全局点及相应的局部吸引子组合而成的虚拟点对应.因此,在不同的情况下fitdis(t,i)可以用不同的方法来计算,文中采用的计算方法为

(3)

式中，f(·)为适应度函数.从式(3)可见,记忆向量包含的是粒子与mbest点的适应度距离的累积历史信息,而这些信息在原始QPSO算法中是不被保存和利用的.由于很久以前的记忆对当前的决策价值较小且如果包含所有前代的信息,则记忆向量Mems随着迭代次数的增加会变得很小,故Mems被设计成只包含最近K代的信息,而K为记忆影响代数,是一个预先设定的参数,通常可设为10.完成记忆向量的构建后,关键在于如何应用到算法中以对粒子的行为施加有效的引导.

1.2算法实现

由文献[8]可知,可将记忆向量直接引入QPSO的位置更新公式中,即利用记忆向量对粒子的行为进行直接的干预.然而,这种方法存在两个方面的问题:①如果记忆向量对粒子的行为影响较大,则会减弱QPSO算法固有结构的优势,如果记忆向量对粒子的行为影响较小,则改进效果不明显;②该方法引入了新的参数,不利于算法在不同问题上的快速应用.因此,文中对记忆向量的利用采用间接影响粒子行为的方式,即以QPSO-Mu算法[5]为基线算法,引入记忆向量来实现变异概率的自适应设定,从而实现对不同粒子的差异化处理,文中所提出的算法称为基于记忆信息挖掘的变异QPSO算法(QPSO-MuM).在基线算法中分别采用了对gbest和mbest进行变异的方法,文中主要采用对mbest进行变异的方法.QPSO-MuM算法的伪代码如下:

Procedure QPSO-MuM

{For i=1 to swarm size N

randomize X[i];

pbest[i]=X[i];

Mems[i]=1/N;

EndFor

While(true)

calculate mbest;

find gbest;

For i=1 to swarm size N

If fitness(X[i])>fitness(pbest[i]) then pbest[i]=X[i];

calculate Q[i];

calculate Mems [i] with Eq.(2) and Eq.(3);

If rand(0,1)

update the position of particle i with Eq.(1);

EndFor

If (termination criterion is met) then break the loop;

EndWhile

output gbest;

Function Cauchy(mbest,mems[i])

For d=1 to D

If rand(0,1)<(Pmd*mems[i]*N)

mbestd=mbestd+rid;

EndIf

EndFor

output mbest;}

其中:Pm是每个粒子的变异概率;D是粒子维数;Pmd是粒子每一维的变异概率,通常取值为D-1;rid是一个符合柯西分布的随机变量,其概率密度函数为

(4)

式中，a为尺度参数.

与基线算法相比,QPSO-MuM算法主要增加了记忆向量的迭代计算及利用,即QPSO-MuM算法在QPSO-Mu算法的基础上添加了基于记忆信息的处理.而该处理主要通过在每个粒子的每一维变异概率的设置上考虑记忆向量所蕴含的信息,即在已经接近收敛的粒子上减小变异的概率,使算法的收敛能力和收敛速度都能保持在一定的水平上,而对尚未收敛的粒子增大变异概率以提高粒子的活性,使之能找到更有价值的搜索区域.通过基于记忆信息的处理,算法在保持一定局部开发能力的同时提升全局搜索能力.

1.3算法测试

由于文中算法是在基线算法的基础上进行改进,故有必要与基线算法进行比较以验证文中算法的性能,同时为了比较文中提出的记忆信息利用方法与文献[8]中记忆信息利用方法的优势,对比算法还包括了QPSOM算法[8].文中选择了3个有代表性且被广泛使用的测试函数来验证文中算法的性能.这些函数包括Rosenbrock、Rastrigin和Griewank函数,相应变量的取值范围分别为(-100,100)、(-10,10)和(-600,600),全局最优解都为0.

由于仿真实验中3种算法都属于随机算法,文中采用统计分析方法[12]来进一步验证3种算法比较结果的可信度.算法之间的统计差异显著性基于95%的置信水平.如果文中算法的某项结果均明显优于两种对比算法,则在文中算法的中位数结果右边显示“++”;如果结果仅明显优于两种对比算法中的任意一种,则显示“+”;如果结果均不优于任意一种比较算法,则不显示任何符号.而如果任意一种对比算法的某项结果明显优于文中算法,则在该算法相应的中位数结果右边显示“+”.从表1可以看出,文中QPSO-MuM算法的性能整体上优于基线算法,与QPSOM算法相比具有较为明显的优势,四分位距的比较结果表明文中算法具有较高的稳定性,这充分说明了记忆信息挖掘策略的有效性及文中改进QPSO算法的优越性.

2多阈值图像分割

2.1图像分割算法的实现

文中将QPSO-MuM算法和OTSU方法结合起来,实现了一种灰度图像多阈值分割算法,其实现要

表1　测试函数上的模拟结果

点如下:

(1)粒子的适应度计算基于OTSU法.OTSU法是一种简单的图像分割方法,又叫大津法[13].该方法根据图像的灰度值将图像分割为不同的类别,其目标是找到相应的最优阈值,使这不同类别之间的方差为最大值.OTSU法的实现方法简单,获得的阈值相对较优且较为稳定.

(2)算法的分割对象是256级灰度图,粒子的维数与分割阈值的个数M一致,粒子的每一维对应一个阈值,其数值是位于[0,255]上的整数,每次迭代中粒子的适应度计算基于OTSU法,即分别根据每个粒子的M个阈值,将图像分割成M+1个部分,分别计算任意两个部分的类间方差并累加,进而分别获得每个粒子的pbest以及整个粒子群的gbest并对粒子位置进行更新,最后按照gbest所包含的阈值对图像进行分割.

(3)由于算法求得的多个阈值必须按相应灰度值顺序进行排列,故在初始化策略上,文中采用文献[14]方法将灰度值按分割阈值数平均分为M个区间,每个粒子的初始值在相应的区间内随机生成得到.

2.2实验结果与讨论

为验证文中所提多阈值图像分割算法的性能,对文中算法、基于标准粒子群优化的图像分割算法[15]和基于贝叶斯粒子群优化(BPSO)的图像分割算法[14]进行了实验比较.

仿真实验主要基于Berkeley 图像数据集,在该数据集上采用这3种算法进行了大量仿真,实验结果良好,限于篇幅,文中仅给出图1所示的3幅原始图像的分割结果进行说明.

图1　原始图像

QPSO-MuM算法在本次实验中的参数设置与1.3节中设置一致,而对比算法的参数则依据所在文献来设置.为了保证公平的比较,实验中所有算法的种群数和最大运行代数统一设置为10和20.

为对算法的运行结果进行全面的评估和分析,文中给出了阈值为4时3种算法对3幅原始图像的分割结果,并比较分析了这3种算法的一致性度量、适应度及稳定性,最后分析QPSO-MuM算法克服维数灾难的能力.

实验环境如下:HP个人计算机,2GB RAM,Pentium Dual-Core E6600，3.07GHz CPU,Microsoft Windows 7,Matlab 2012a.

2.2.1图像分割结果比较

由于3种算法都是随机优化算法,故针对每幅图像以阈值4分别独立运行50次,选取最佳适应度值最接近这50次实验的中位值的分割结果,如图2所示.

图2　3种算法对3幅图像的分割结果

Fig.2Segmentation results of three algorithms for three images

很明显,文中算法能够准确地分割出图像中的主要目标,分割结果与对比算法相比更为清晰,包含更多的细节且从视觉上更接近原始图像.如图2(a)所示,文中算法的建筑物呈方格状而其他算法的相应区域均为丢失了部分细节的片状,图2(b)的分割结果中，文中算法的水面包含了更多细节而其他算法都缺失了相应的细节,这3种算法在其他图像上的实验结果都存在与此类似的差异.

2.2.2一致性度量、适应度及稳定性比较

文中采用一致性度量(U)[14]来评估图像分割质量.U的计算方法如下:

(5)

为测试算法的稳定性,文中还针对每幅图像以阈值2和3分别独立运行50次,记录每次实验最优适应度值,并对图像分割结果的U值进行计算,实验结果的中位值和四分位距如表2所示.对于文中算法,运用1.3节所述的方法分别与标准粒子群和贝叶斯粒子群算法进行了统计测试,适应度值表明,文中算法的寻优能力比标准粒子群和贝叶斯粒子群算法强;U值结果表明,文中算法分割图像的质量较高;适应度和U值的四分位距对比结果表明,文中算法具有优异的稳定性.

2.2.3克服维数灾难能力

为检验QPSO-MuM算法克服维数灾难的能力,即算法对高维空间的搜索能力,文中针对不同的高阈值数(M=5,9,12,16)分别对每幅图像进行实验,50次独立运行所需时间的中位值和四分位距如表3所示.从表中可知,随着阈值数的增加,QPSO-MuM算法的运算时间并没有显著的增加,这说明了QPSO-MuM算法具有较强的克服维数灾难的能力.

表2　3种算法的适应度及 U值统计结果

表3文中算法对3种图像的运行时间

Table 3Running time of the proposed algorithm for 3 imagess

M运行时间的中位值运行时间的四分位距/10-2图像1图像2图像3图像1图像2图像350.23620.22220.22399.4787.6778.10190.25900.25200.24776.2496.3907.957120.26140.25670.25896.2256.4566.695160.28020.26720.27098.4746.4347.430

3结论

基于记忆信息挖掘方法,文中对变异QPSO算法进行了改进并结合OTSU法提出了一种多阈值图像分割算法.该算法是在进化过程中依据每个粒子的搜索历史来构建一个包含对粒子在下一代出现位置的预测信息的记忆向量,并利用记忆向量分别自动设置变异QPSO算法中的每个粒子的变异概率.在Berkeley 图像数据集上的分割实验结果表明,文中算法能得到稳定而清晰的图像分割结果,且具有较强的克服维数灾难的能力.今后应结合医学图像辅助诊断等应用的具体需求,将文中提出的图像分割算法应用到实时图像处理上.

参考文献：

[1]高浩,须文波,孙俊.量子粒子群算法在图像分割中的应用 [J].计算机工程与应用,2007,43(33):24-25.

Gao Hao,Xu Wen-bo,Sun Jun.Image segmentation using quantum-behaved par tical swarm optimization algor ithm [J].Computer Engineering and Application,2007,43(33):24-25.

[2]冯斌,王璋,孙俊.基于量子粒子群算法的 Ostu 图像阈值分割 [J].计算机工程与设计,2008,29(13):3429-3431.

Feng Bin,Wang Zhang,Sun Jun.Image threshold segmentation with Ostu based on quantum-behaved particle swarm algorithm [J].Computer Engineering and Design,2008,29(13):3429-3431.

[3]Gao H,Xu W B,Sun J,et al.Multilevel thresholding for image segmentation through an improved quantum-behaved particle swarm algorithm [J].IEEE Transactions on Instrumentation and Measurement,2010,59(4):934-946.

[4]Coelho L S.A quantum particle swarm optimizer with chaotic mutation operator [J].Chaos,Solitons & Fractals,2008,37(5):1409-1418.

[5]石锦风,冯斌,孙俊.用带变异因子的 QPSO 算法解决 Job-Shop 调度问题 [J].计算机工程与应用,2008,44(8):49-52.

Shi Jin-feng,Feng Bin,Sun Jun.Solvingjob-shop scheduling problem with QPSO algorithm with mutation operator [J].Computer Engineering and Applications,2008,44(8):49-52.

[6]林星,冯斌,孙俊.基于边界变异的量子粒子群优化算法 [J].计算机工程,2008,34(12):187-188.

Lin Xing,Feng Bin,Sun Jun.Quantum-behaved particle swarm optimization algorithm based on bounded mutation [J].Computer Engineering,2008,34(12):187-188.

[7]史滋福.贝叶斯推理问题解决中的认知偏向研究 [D].重庆:西南大学心理学院,2007.

[8]Yang Z L,Min H Q,Jiang Y Z.Multilevel thresholding for image segmentation through quantum-behaved particle swarm optimisation with memory approach [J].Journal of Computational Information Systems,2013,9(2):703-711.

[9]Clerc M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization [C]∥Proceedings of 1999 IEEE Congress on Evolutionary Computation.Washington D C:IEEE,1999:1951-1957.

[10]Angeline P J.Evolutionary optimization versus particle swarm optimization:philosophy and performance diffe-rences [M]∥Porto V W,Saravanan N,Waagen D,et al.Evolutionary Programming VII.Berlin:Springer,1998:601-610.

[11]Liu J,Sun J,Xu W B.Quantum-behaved particle swarm optimization with adaptive mutation operator [M]∥Jiao Licheng,Wang Lipo,Gao Xin-bo,et al.Advances in Na-tural Computation.Berlin:Springer,2006:959-967.

[12]Li K,Kwong S,Wang R,et al.Learning paradigm based on jumping genes:a general framework for enhancing exploration in evolutionary multiobjective optimization [J].Information Sciences,2012,226:1-22.

[13]Otsu N.A threshold selection method from gray level histograms [J].IEEE Transactions on Systems,Man,and Cybernetics,1979,9(1):62-66.

[14]Jiang Y Z,Hao Z F,Yuan G Z,et al.Multilevel thresholding for image segmentation through Bayesian particle swarm optimisation [J].International Journal of Modelling,Identification and Control,2012,15(4):267-276.[15]周晓伟,葛永慧.基于粒子群优化算法的最大类间方差多阈值图像分割 [J].测绘科学,2010,35(2):88-89.

Zhou Xiao-wei,Ge Yong-hui.Multilevel threshold method for image segmentation based on particle swarm optimization and maximal variance [J].Science of Surveying andMapping,2010,35(2):88-89.

Multi-Threshold Image Segmentation Algorithm Based on Improved

Quantum-Behaved Particle Swarm Optimization

YangZhen-lunMinHua-qingLuoRong-hua

(School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China)

Abstract:In order to improve the quality of image segmentation in engineering applications, an improved quantum-behaved particle swarm optimization(QPSO) algorithm is proposed on the basis of mutated QPSO, which is then combined with the maximum between-cluster variance method to present a multi-threshold image segmentation algorithm. The algorithm is characterized by a memory vector constructed from memory information in the search procedure of particles using Bayesian theorem. The memory vector is used to predict the future behaviors of particles and to assign the mutation probability of each particle automatically. In this way, the global search ability is enhanced and the convergence ability is preserved for the algorithm. Experimental results on Berkeley datasets show that the proposed algorithm is superior to two existing PSO-based methods because it helps obtain more stable and clearer image segmentation results.

Key words: quantum-behaved particle swarm optimization; memory information exploration; multi-threshold;image segmentation