混合量子粒子群图像分割算法IS-MQPS*

2015-03-27高颖慧曲智国

计算机工程与科学 2015年1期

关键词：量子像素粒子

高颖慧,曲智国,卢凯

(1.国防科学技术大学ATR国家重点实验室，湖南长沙 410073；2.国防科学技术大学计算机学院，湖南长沙 410073)

混合量子粒子群图像分割算法IS-MQPS*

高颖慧1,曲智国1,卢凯2

(1.国防科学技术大学ATR国家重点实验室，湖南长沙 410073；2.国防科学技术大学计算机学院，湖南长沙 410073)

基于群智能的图像分割技术因其与人类视觉机理相符合，受到人们重视。但是，现有群体模型存在的对参数取值敏感和易收敛于局部极值等问题，制约了群智能技术在复杂图像分割中的应用。首先定义了基于群智能图像分割的抽象模型，然后将通用量子粒子模型GQPM引进图像分割，提出了混合量子粒子群图像分割算法IS-MQPS。IS-MQPS算法以量子粒子携带灰度和坐标信息，以纠缠量子态定义群体行为规则，以混合量子粒子群的自组织聚类实现图像分割。实验表明，IS-MQPS算法具有对噪声不敏感、分割区域意义明确等优点，可应用于复杂图像分割。

图像分割；群智能；通用量子粒子模型；混合量子粒子群

1 引言

神经心理学对人类视觉机理的研究表明，人类视觉行为需要先后经过直觉和专注两个阶段。以行为科学观点，直觉阶段视觉行为是下意识过程，过程本身没受到任何集中控制也没有任何协调者，因此直觉阶段视觉行为是一种分布式处理行为。直觉阶段视觉行为所要达到的目的是对场景进行区域分割并初步提取出关注点，这与图像分割目的一致，图像分割过程可与直觉阶段视觉行为相类比。因此，以分布式方案进行图像分割是一种恰当合理的选择。

群智能为寻找复杂分布式问题求解方案提供了基础[1,2]，以群智能技术进行图像分割成为当前图像分割领域的一个重要研究方向。如：MacGill J[3]提出一个基于人工鸟模型Boid的图像分割算法;Ramos V和Almeida F[4]基于Chialvo D R和Millonas M M[5]提出的蚁群模型，设计实现了一个图像分割算法;何浩和陈艳秋[6]提出一个基于人工细胞模型的图像分割算法;徐小慧和张安[7]基于一般粒子群模型实现了图像分割;梁建慧和马苗[8]基于人工蜂群实现了图像分割;楚晓丽[9]基于人工鱼群实现了图像分割，等等。

这些算法采用自下而上的建模策略，通过对最小个体间及个体与环境间的简单作用规则的调整，达到所需的全局演化行为，最终使整个群体“涌现”出某些与图像本身相联系的特征，进而实现图像分割。虽然现有的这些基于群智能的图像分割算法具有传统图像分割算法所不具有的全局性和分布性，但也存在图像分割效果受群体模型本身性能影响较大的不足。例如，由于粒子群模型存在易发散和易陷入局部最优的不足，蚁群模型存在受参数取值影响较大和对个体初始放置位置敏感的不足，人工细胞模型存在受参数取值影响较大的不足，所以现有的这些基于群智能的图像分割算法在分割复杂图像时效果不很理想。

随着量子理论的发展，研究人员发现量子系统和具有社会性的生物群体间有许多可类比的地方，且以量子系统模拟具有社会性的生物群体拥有许多非量子系统不具有的优点[10]。于是，出现了以量子态定义个体、基于量子纠缠机理和冯·诺依曼(Von Neumann)熵理论设计群体进化规则的新型群体模型-通用量子粒子模型GQPM(Generalized Quantum Particle Model)[10]。GQPM具有对噪声不敏感、适用于高维和大数据集聚类等优点。

为提高复杂图像分割性能，本文将GQPM引进图像分割，提出了混合量子粒子群图像分割算法IS-MQPS(Image Segmentation Algorithm based on Mixed Quantum Particle Swarm)。实验结果表明，IS-MQPS算法具有良好的分割效果和抗噪声能力，可用于复杂图像的分割。

2 基于群智能图像分割算法的抽象模型

群智能是人工生命研究的重要内容，是解决分布式问题的重要手段，群智能应用最广泛的领域之一就是数字图像处理。通过深入研究文献[1～9]可知，一个基于群智能的图像分割算法ISA_SI(Image Segmentation Algorithm based on Swarm Intelligence)，可以表达为一个三元问题：

(1)

其中，PIA(Particle Inhabiting Array)是粒子栖息阵列，用来放置群体;SM(Swarm Model)是群体模型，指放置在粒子栖息阵列上的群体的具体形式；CR(Conjunction Rule)是关联准则，用于建立群体与图像数据间联系的规则。

从图1可知，群体模型SM包含三个元素：

(1)个体模型IM(Individual Model)：指群体中各个粒子的具体形式，它决定群体的一般性特征。

(2)行为规则AR(Action Rule)：指群体中个体运动、变换或繁殖，进而实现自组织聚类所依据的准则。行为规则是实现群体进化、最终“涌现”出种群特征的关键。

(3)协调方程HE(Harmony Equation)：指衡量群体进化程度的方程，可通过它来控制进化。

基于群智能图像分割的基本思想：将构成群体的个体随机放置于群体栖息阵列上，基于某种关联准则建立群体与图像数据间的联系。个体依据某种行为规则在群体栖息阵列上运动、变换或繁殖，进而实现自组织聚类。该进程不断进行，群体逐渐分化成一系列小种群，同一小种群内的粒子具有某种相似特征。

由于建立了群体与图像数据间的联系，故由种群特征可凸显出图像各区域的特征，达到分割目的。

Figure 1 Composition of SM

群体模型SM是决定基于群智能图像分割效果的关键元素，为了获得良好的分割效果，需要选择性能良好的群体模型。

3 通用量子粒子模型GQPM

不断从不同领域涌现的新思想，启发群智能研究者定义更多性能更优的群体模型，以拓展群智能应用范围和改进群智能应用效果。由群智能理论可知，具有社会性的生物群体中大量个体的随机行为将导致群体的一个确定行为。若将群体看作一个复合系统，群体中的个体看成复合系统的子系统时，以上现象意味着系统联合熵小于其各子系统的熵，且具有负的条件熵。经典信息论中，Shannon联合熵大于或等于其任意子系统的Shannon熵，Shannon条件熵不可能为负，所以Shannon熵不满足以上要求。对量子理论的研究发现：(1)量子系统中大量微观粒子的随机微观行为将导致系统的一个确定性宏观行为，这可与群智能中个体和群体间关系相类比，因此可以用量子态纠缠方法来刻画群体行为和个体行为之间的关系；(2)量子纠缠态的冯·诺依曼熵满足系统联合熵小于其各子系统熵及条件熵为负的要求，因此量子态纠缠方法较其它非量子化方法更加适用于基于群智能的聚类。Shuai Dian-xun等人[10]将量子态概率幅表示、量子态纠缠机理和冯·诺依曼熵理论引进群体模型，定义了通用量子粒子模型GQPM。

4 混合量子粒子群图像分割算法IS-MQPS

IS-MQPS基本思路如下：根据像素灰度信息定义粒子量子态及量子态纠缠原则，再令量子粒子携带灰度和坐标信息，以量子粒子群在量子粒子栖息阵列上的纠缠进化实现灰度相近且位置接近的像素的聚类，实现分割。IS-MQPS算法基本流程如图2所示。

Figure 2 Flow of IS-MQPS

一个好的图像分割算法应该满足以下三点：(1)不需选取阈值；(2)轮廓连续；(3)区域分割适量。IS-MQPS算法对以上三点都有较好体现。

4.1 图像粗分割和过渡区提取

过渡区是环绕目标边界兼具边界和区域特征的带状区，通过细化过渡区可得到边界线。过渡区提取是通过图像粗分割实现的。图像粗分割就是利用边缘检测和区域生长确定待分割图像大概划分成多少个区域，并将区域间分隔带标记出来的过程。

根据图像特点选择足够灵敏的边缘检测算子，检出图像中所有可能的边缘点，即过渡区的点，图像上所有点就被分成了非过渡区和过渡区两部分。将进行了过渡区标记的图像记作TR(x,y)，当(x,y)为过渡区点时，TR(x,y)=1，否则TR(x,y)=0。记TR0为所有非过渡区点的集合，TR1为所有过渡区点的集合。

区域生长的基本思想是将具有相似性质的像素集合起来构成区域。具体如下：首先在需要分割的区域找一个种子像素作为生长起点，然后将种子像素邻域中与其性质相近的像素，根据事先确定的相似准则合并到种子像素所在的区域中。再将这些新像素当作新的种子像素重复以上过程，直到再没有满足相似准则的像素可以被包括进来为止，这样就形成了一个区域。对于整幅图像的分割，一个区域生长完成后，还必须检查是否还有尚未涉及到的像素。如果还有，那么在剩下的像素中，再选择一些种子像素进行生长，形成新的区域。如此继续下去，直到图像中所有的像素都归属到相应的区域中，整个图像的分割才算完成。

4.2 混合量子粒子群

粒子群中包含两种量子粒子：一是像素量子粒子，二是质心量子粒子。以下分别进行介绍。

(1)像素量子粒子。

将过渡区TR1中每一个像素与一个量子粒子相关联，这种量子粒子携带以下信息：① 粒子量子态：通过量子化与粒子相关联像素的灰度值得到；② 两类数据信息：一类是与粒子相关联像素的灰度值，另一类是像素坐标值。将这种量子粒子称为像素量子粒子，记为pc。

(2)

pck携带的两类数据信息组成如下结构：

(3)

(2)质心量子粒子。

例如，第h个区域如图3所示。

Figure 3 Sketch map of region border and region centroid

(4)

cch携带的数据信息组成如下结构：

(s-1,{t-2,t+2}),(s,{t-3,t+3}),

(s+1,{t-3,t+3}),(s+2,{t-3,t+3}),

(s+3,{t-2,t-1,t+2}),(s+4,{t,t+1})}

(5)

4.3 纠缠聚类

为了进行纠缠聚类，首先需要将混合量子粒子群放置在量子粒子栖息阵列上。可选择待分割图像作为粒子栖息阵列，但由于一般有W×H≫(s+n)，W×H代表待分割图像尺寸，(s+n)为混合量子粒子群的粒子数，因此为减少计算量，可以以一个较小尺寸阵列作为粒子栖息阵列。选阵列尺寸为N×N，满足N×N>(k+n)及N×N≪W×H。

(1)碰撞规则。

(6)

Figure 4 Sketch map of pixel neighbourhood

③质心量子粒子间的碰撞。由于每一个质心量子粒子都与一个区域相关联，每一个区域代表一个类，所以，即使存在某一个质心量子粒子位于另一个质心量子粒子的坐标邻域中，它们之间也不发生纠缠。

(2)纠缠规则。

量子粒子间的纠缠是完成量子粒子自组织聚类的关键，以下考虑如何实现纠缠。设任意两个量子粒子(既可以是像素量子粒子，也可以是质心量子粒子)满足纠缠条件，它们基于以下规则实现纠缠：

(7)

公式(7)满足以下要求：

当多于两个量子粒子需要纠缠时，对纠缠规则进行如下改进：设量子粒子ch也在ck的坐标邻域内，它们也满足相互纠缠的条件，则根据纠缠态传递性，ch与cl也满足纠缠条件，ch、cl及ck将纠缠在一起。

(8)

(3)聚类后处理。

在粒子碰撞纠缠过程中，当某一个纠缠类中已经包含了一个质心量子粒子，此时，若再有一个质心量子粒子跟该类中的某一个量子粒子满足纠缠条件，后出现的质心量子粒子将不与该类纠缠。这是由于每个质心量子粒子都代表一个初始分割出来的区域，也就是代表一个类，而每一类中只能有一个质心量子粒子。后出现的质心量子粒子将等待其它满足纠缠条件的不含质心量子粒子的纠缠类进行纠缠。

阈值TH的取值由待分割图像的特点决定，最小取9。若待分割图像每一个区域都较大，则TH的值可以适当取大一些。

混合量子粒子群完成聚类后，根据量子粒子携带的像素坐标值，将各类量子粒子所携带像素映射回待分割图像，并将同类量子粒子携带的像素赋予相同灰度值，从而完成图像分割。

5 实验及结果分析

5.1 分割质量评价方法

图像分割算法的分割质量评价方法分为主观评价方法和客观评价方法两类。主观评价方法是最常用的方法，是通过人对图像本身的观察理解，主观地对比不同算法的分割结果。但是，主观评价方法存在一些局限，如需要有参照、图像类型对评价结果有影响等等。客观评价方法是通过一些已经建立的评价模型或评价标准来评价算法的优劣，但没有一种通用有效的客观评价标准。常见的评价标准和评价方法包括：

(1)区域内部均匀性：分割常常被定义为把一幅原始图像分成若干个内部性质相似的区域，因此可以用分割图中各个区域内部特性的均匀程度来描述分割图像的质量。

(2)轮廓连续性：轮廓连续可以保证分割出来的每一个区域有意义。若轮廓不连续，则本来不同的区域可能会连在一起，这样的分割就不好。

(3)抗噪声能力：噪声在图像中是普遍存在的。当噪声严重时，需要采用专门的去噪算法进行处理。但是，对于轻度噪声，好的分割算法应该不受其影响，所以抗噪声能力也是衡量分割算法性能的一个方面。

5.2 分割实验及结果分析

本文提出的IS-MQPS算法，需要基于边缘检测和区域生长对图像进行粗分割。实验中，我们统一采用Krisch算子来检测边缘，Krisch算子定义如下：

K1～K8是八个卷积模板。在每一个像素位置分别用这八个模板计算卷积值，然后将这八个卷积值中的最大值输出，作为检测到的边缘值。模板在图像上移动，计算出每一个像素位置的边缘值，就完成了对整幅图像的边缘检测。

(1)分割效果对比实验。

通过分析图5和图6两组分割效果对比图，总结本文算法特点如下：

① 由于本文算法的粗分割过程可以将图像中明显区域的边缘提取出来，从而保证了图像中的明显区域在分割过程中不会被割裂，使得分割后区域意义比较明确，提高了分割质量。同时本文算法对混合量子粒子群的初始放置位置不敏感，所以本文算法的分割质量比较稳定。蚁群分割算法的分割质量受粒子数量、迭代次数及原图像质量的影响较大，当粒子数量不够多、迭代次数较少或原图像比较复杂时，该算法的分割质量就不很理想。人工细胞群分割算法的分割质量受迭代次数及原图像质量的影响也较大，当迭代次数较少或原图像比较复杂时，该算法的分割质量也不理想。

②本文算法的时间性能较好，尤其当图像中各区域内部灰度较均匀，过渡区像素个数较少时，如图6a所示。人工细胞群分割算法的时间性能最差，这主要是由于该算法粒子数量多，且在每一轮迭代中对每一个粒子进行更新的计算量较大。蚁群分割算法的时间性能受粒子数量和迭代次数的影响较大。

Figure 5 Comparison of segmentation effect (Part 1)

Figure 6 Comparison of segmentation effect (Part 2)

(2)抗噪声能力测试。

本实验的目的是测试本文算法的抗噪声能力。图7是一幅人工合成的简单图像，通过在该图像中加入椒盐噪声和高斯噪声得到所需的含噪图像，具体如图8a和图9a所示。

Figure 7 Source image used to test anti-noise ability

Figure 8 Segmentation result of salt and pepper noise image

Figure 9 Segmentation result of Gaussian noise image

从图8和图9的含噪图像分割结果可以看出：

①图8a是含椒盐噪声(噪声强度为0.02)的图像。图8d是本文算法的分割结果，可以看出分割结果与原图像间差异较小，噪声仅仅在边缘部分对分割结果有所影响。

②图9a是含高斯噪声的图像，噪声均值为0，方差为0.004。图9d是本文算法的分割结果，可以看出分割结果比较准确，区域连续性和边缘完整性都较好，没有受到噪声影响。

本文算法具有一定的抗噪声能力，从算法本身来分析，有三个方面可以减小噪声对分割的影响：(1)群智能技术本身就具有一定的抗噪声能力，量子粒子群作为一种群智能实现模式，也具有一定的抗噪声能力。(2)每一个量子粒子所携带的数据信息，除了灰度以外，还有像素坐标信息。粒子间的纠缠前提是所携带的数据信息要相似，不但灰度值要接近，坐标位置也需相距不远，才能进行粒子纠缠。这在一定程度上抑制了相对孤立的小区域的存在。(3)当进化过程终止之后，虽然仍可能存在一些由噪声引起的相对孤立的部分，但分割后处理会重新调整和优化分割结果，这样可以很大程度上抑制噪声对分割结果的影响。

6 结束语

基于群智能的图像分割因其与人类视觉机制相符合，成为一种重要的图像分割算法。由于现有群智能实现模式存在对参数取值敏感、易收敛于局部极值等问题，所以利用现有群智能实现模式对复杂图像进行分割，分割效果往往不很理想。针对该问题，本文将基于量子纠缠机理和VonNeumann熵理论定义的通用量子粒子模型GQPM引进图像分割，设计基于GQPM的高性能图像分割算法，提出了混合量子粒子群图像分割算法IS-MQPS，以满足复杂图像的分割需求。实验表明，IS-MQPS分割算法具有良好的分割效果和较强的抗噪声能力，可应用于复杂图像的分割。

[1]LeiXiu-juan.Swarmintelligentoptimizationalgorithmsandtheirapplications[M].Beijing:SciencePress, 2012.(inChinese)

[2]LiBi,HaoZhi-feng.Cooperativecoevolutionaryalgorithmanditsapplications[M].Beijing:SciencePress,2013.(inChinese)

[3]MacGillJ.Usingflockstodriveageographicalanalysisengine[C]∥ProcofArtificialLifeⅥ, 2000:453-466.

[4]RamosV,AlmeidaF.Artificialantcoloniesindigitalimagehabitats—Amassbehavioureffectstudyonpatternrecognition[C]∥Procofthe2ndInternationalWorkshoponAntAlgorithms(FromAntColoniestoArtificialAnts), 2000:113-116.

[5]ChialvoDR,MillonasMM.Howswarmsbuildcognitivemaps[C]∥ProcoftheBiologyandTechnologyofIntelligentAutonomousAgents, 1995:439-450.

[6]HeH,ChenYQ.Artificiallifeforimagesegmentation[J].InternationalJournalofPatternRecognitionandArtificialIntelligence, 2001, 15(6):989-1003.

[7]XuXiao-hui,ZhangAn.Entropicthresholdingmethodbasedonparticleswarmoptimizationforimagesegmentation[J].ComputerEngineeringandApplications, 2006,42(10):8-11.(inChinese)

[8]LiangJian-hui,MaMiao.Artificialbeecolonyalgorithmbasedresearchonimagesegmentation[J].ComputerEngineeringandApplications, 2012,48(8):194-196.(inChinese)

[9]ChuXiao-li. K-meansclusteringalgorithmandartificialfishswarmalgorithmappliedinimagesegmentationtechnology[J].ComputerSystems&Applications, 2013,22(4):92-94.(inChinese)

[10]ShuaiDian-xun,ShuaiQing,DongYu-min.Self-organizingdataclusteringbasedonquantumentanglementmodel[C]∥Procofthe1stInternationalMulti-SymposiumonComputerandComputationalSciences,2006:1.

附中文参考文献：

[1] 雷秀娟.群智能优化算法及其应用[M].北京：科学出版社，

2012.

[2] 李碧，郝志峰.协同进化算法及其应用[M].北京：科学出版社，2013.

[7] 徐小慧，张安.基于粒子群优化算法的最佳熵阈值图像分割[J].计算机工程与应用，2006，42(10)：8-11.

[8] 梁建慧，马苗.人工蜂群算法在图像分割中的应用研究[J].计算机工程与应用，2012，48(8)：194-196.

[9] 楚晓丽.K-Means聚类算法和人工鱼群算法应用于图像分割技术[J].计算机系统应用，2013，22(4):92-94.

GAO Ying-hui,born in 1975,PhD,associate professor,her research interests include image processing, quantum information processing, and pattern recognition.

曲智国(1982-),男,山东德州人，博士，研究方向为图像处理、量子信息处理和模式识别。E-mail:Green20001@sina.com

QU Zhi-guo,born in 1982,PhD,his research interests include image processing, quantum information processing, and pattern recognition.

卢凯(1973-),男，上海人，博士，教授，研究方向为并行计算机结构和高性能并行系统软件。E-mail:kailu@nudt.edu.cn

LU Kai,born in 1973,PhD,professor,his research interests include parallel computer architecture, and high performance parallel system software.

A novel image segmentation algorithm based on mixed quantum particle swarm

GAO Ying-hui1,QU Zhi-guo1,LU Kai2

(1.National Key Laboratory of Automatic Target Recognition,National University of Defense Technology,Changsha 410073；2.College of Computer,National University of Defense Technology,Changsha 410073,China)

Image segmentation technology based on swarm intelligence has been paid more and more attentions due to its consistency with human visual mechanism. However, many existing swarm models are sensitive to parameter values and easy to converge to the local minimum, which restricts the application of swarm intelligence in complex image segmentation. In the paper, we define the abstract model of image segmentation based on swarm intelligence firstly, and then propose a novel image segmentation algorithm based on mixed quantum particle swarm (IS-MQPS) by introducing the eneralized quantum particle model (GQPM) into image segmentation. IS-MQPS contains three key parts: defining the quantum particle by pixel's grey value and position value, defining the swarm action rule by entangled quantum state, and realizing image segmentation by self-organization clustering of mixed quantum particle swarm. Experiments show that IS-MQPS is insensitive to noise, has good segmentation effect, and can be used in complex image segmentation.

image segmentation;swarm intelligence;generalized quantum particle model;mixed quantum particle swarm

1007-130X(2015)01-0125-08

2013-04-01;

2014-11-07基金项目：国家自然科学基金资助项目(61103082)

TP18

10.3969/j.issn.1007-130X.2015.01.019