（计算机软件与理论专业论文）微粒群算法在图像处理中的应用研究.pdf

摘要 微粒群算法( p s o ，p a r t i c l es w a r mo p t i m i z a t i o n ) 是一种新近出现的启发式全局 优化算法，由于算法的易实现性和高效性，因此受到了人们的广泛关注。它已成 为与遗传算法、禁忌搜索算法以及模拟退火算法并行发展的一种全局优化算法。 这种算法的基本思想是源于鸟类的群体行为。其特点是在较为简单的规则指导下， 可以保证微粒迅速降落在最优解处。因此，这种方法具有一定的智能性和社会性。 基于p s o 的基本思想，本文对p s o 算法进行了详细的论述，讨论了算法的优 缺点，并对p s o 的基本原理进行了详细分析。为了进一步改进算法的性能，本文 提出了两种新算法。一种是基于p s o 的核模糊聚类算法( k e r n e lf u z z yc m e a l l s c l u s t e r i n g ) 。通常，传统聚类算法只在数据特征差异较大时才有效，当数据特征差 异较小时，传统聚类算法很难取得较好的聚类效果。新算法先用高斯核函数，把 输入空间的样本映射到高维特征空间后，再利用微粒群算法的全局搜索、快速收 敛的特点，在特征空间中进行聚类，克服了k f c m 对初始值和噪声数据敏感、易 陷入局部最优的缺点。通过对医学图像的分割，结果表明，新算法在性能上比 k f c m 聚类算法有较大的改进，具有更好的聚类效果，且算法能够很快地收敛。 另一种是基于p s o 与d c t 域的鲁棒图像水印算法。数字水印技术是保护多媒 体数据版权和图像可靠性认证的一种新技术，本文比较系统地研究了数字水印在 图像中的应用问题，提出了一种新的基于p s o 与d c t 域的鲁棒图像水印方案。实 验仿真表明，针对不同的水印图像和不同的载体图像存在不同的优化频带，在优 化频带中嵌入水印明显地平衡了鲁棒性和隐蔽性的冲突。攻击实验表明，该算法 对压缩、噪声等一般信息处理是鲁棒的。本文还讨论了置乱技术在数字水印中的 应用，置乱技术能分散错误比特的分布，提高了数字水印的鲁棒性。 最后，简述了p s o 算法在未来在图像处理领域的发展前景及相关应用，据此 指出了未来的主要研究工作和方向。 关键词：微粒群算法，图像分割，核模糊c 均值聚类，数字水印，离散余弦变换 摘要 t h ea p p l i c a t i o na n dr e s e a r c ho fi m a g ep r o c e s s i n g b a s e do i lp a r t i c l es w a r mo p t i m i z a t i o n h up i n g p i n g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db ya s s o c i a t ep r o f p e iz h e n k u i a b s t r a c t p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mi sah e u r i s t i cg l o b a lo p t i m i z a t i o na l g o r i t h m w h i c ha p p e a r e dr e c e n t l y i th a sb e e nw i d e l yc o n c e m e db yp e o p l eb e c a u s eo fi t s f e a s i b i l i t ya n de f f e c t i v e n e s s i th a sb e e np r o v e nt ob eap o w e r f u lc o m p e t i t o rt oo t h e r h e u r i s t i ca l g o r i t h m s ，s u c ha sg e n e t i ca l g o r i t h m ，t a b o os e a l c ha n ds i m u l a t e da n n e a l i n g a l g o r i t h mf o rg l o b a lo p t i m i z a t i o np r o b l e m s t h eb a s ei d e ao ft h i st h e o r yi sf r o mt h e c o l o n yb e h a v i o r so fb i r d s t h em e r i to fp s o i st h a ti tc a l la s s u r et h ep a r t i c l e sl a n dt h e b e s tp l a c ew i t hs o m es i m p l er u l e s s ot h i sm e t h o dh a st h ea t t r i b u t eo fi n t e l l i g e n c ea n d s o c i e t yp a r t l y b a s e do nt h ep s o si d e a ，t h ep s oh a sb e e ni n t r o d u c e da n dd i s c u s s e di nd e t a i li n t h i sp a p e r 。t h em e r i t sa n dd i s a d v a n t a g e so ft h ep s oa l ea n a l y z e da n dt h e ni t sb a s a l p r i n c i p l ei sa n a l y z e da n dr e s e a r c h e di n t h i sp a p e r i no r d e r t op r o v ea l g o r i t h m s p e r f o r m a n c e ，t w on o v e la l g o r i t h m sa r ei m p r o v e d o n ei sf u z z yc l u s t e r i n ga l g o r i t h m w h i c hu s e st h em e r i t so ft h eg l o b a lo p t i m i z i n ga n dh i g h e rc o n v e r g e n ts p e e do fp a r t i c l e s w a r mo p t i m i z a t i o n ( p s o ) a l g o r i t h ma n dc o m b i n e sw i t hk e r n e lf u z z yc - m e a n s ( k f c m ) i sp r o p o s e d i ng e n e r a l ，t r a d i t i o n a lc l u s t e r i n ga l g o r i t h m s a r es u i t a b l et o i m p l e m e n tc l u s t e r i n go n l yi ft h ef e a t u r ed i f f e r e n c e so fd a t aa r el a r g e 。i ft h ef e a t u r e d i f f e r e n c e sa r es m a l la n de v e nc r o s si nt h eo r i g i n a ls p a c e ，i ti sd i f f i c u l tf o rt r a d i t i o n a l a l g o r i t h m st oc l u s t e rc o r r e c t l y ，b yu s i n gg a u s sk e r n e lf u n c t i o n s ，w ec a l lm a pt h ed a t ai n t h eo r i g i n a ls p a c et oah i g hd i m e n s i o n a lf e a t u r es p a c ei nw h i c hw ec a l lp e r f o r m c l u s t e r i n ge f f i c i e n t l y t h ea l g o r i t h me l i m i n a t e sk f c mt r a p p e dl o c a lo p t i m u m ，b e i n g s e n s i t i v et oi n i t i a ld a t aa n dt h en o i s ed a t a t h ep e r f o r m a n c eo ft h i sm o d i f i e d p s o - k f c mi sc o m p a r e dw i t hk f c m t h er e s u l t so fs i m u l a t i o ne x p e r i m e n t so n m e d i c a li m a g es h o wt h ef e a s i b i l i t ya n de f f e c t i v e n e s so ft h en e wc l u s t e r i n ga l g o r i t h m 1 1 a n o t h e ri s w a t e r m a r k i n gs c h e m eo np s oi nt h ed c td o m a i n d i g i t a l w a t e r m a r k i n gh a sr e c e n t l yb e e np r o p o s e da san e wm e a n st op r o v i d ec o p y r i g h t p r o t e c t i o no fm u l t i m e d i ad a t aa n di m a g ea u t h e n t i c a t i o n a l o n gw i t hp e n e t r a t e da n a l y z e o ft h et h e o r yo fp s o ，a ni n n o v a t i v ew a t e r m a r k i n gs c h e m eo np s oi nt h ed c t d o m a i n i s p r o p o s e d c o m p u t e rs i m u l m i o ni n d i c a t e st h i ss c h e m ec a nf i n da no p t i m i z e dd c t d o m a i nf r e q u e n c yb a n d sw h e nw ee m b e da nw a t e r m a r k i n gi m a g ei n t oa nd i g i t a li m a g e s i m u l a t i o nr e s u l t sp r o v et h eb a l a n c eo fc o n f l i c t i n gb e t w e e nt h e i n v i s i b i l i t ya n d r o b u s t n e s s a t t a c k i n ge x p e r i m e n tr e s u l t sr e v e a lt h ef a c tt h a tt h es c h e m ei sr o b u s tt o j p e gc o m p r e s s i o n ，n o i s e ，e ta 1 f i n a l l y ，t h ed e v e l o p i n g f o r e g r o u n da n dc o r r e l a t i v e a p p l i c a t i o ne n g i n e e r i n g t e c h n o l o g ya r ei n t r o d u c e d t h er e s e a r c ht r e n da n dp s oi nt h ef u t u r ea r ep o i n t e do u ti n s o m ea r e a s k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ，i m a g es e g m e n t a t i o n , k e m e lf u z z yc m e a n s c l u s t e r i n g ，d i g i t a lw a t e r m a r k i n g ，d i s c r e t ec o s i n et r a n s f o r m 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名： 塑聋聋同期：砂o g 年岁月2 b 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 日期：扣1 7 孑年 日期：伽专万年 箩月2 易日 4 ，通常取缈为4 1 ，取z = 0 7 2 9 。 1 2 一一2 4 l 实验结果表明，与使用惯性权重的微粒群算法相比，使用收敛因子的微粒群算法有 更快的收敛速度。其实只要恰当地选取0 9 、c j 和c 2 的值，两种算法结果是一样的，因此 带收敛因子的微粒群算法可被看作带惯性权重的算法的一个特例。同时这也说明，恰当 1 0 中国石油大学( 华东) 硕上学位论文 地选择算法的参数值可以改善算法的性能。 2 2 4 具有空间特性的微粒群寻优模式 如果将微粒赋予一定的半径，则微粒便具有了一定的空间特性。将该空间特性作为 算法的参数扩展，因此，此类算法可归结为参数的选择与控制研究。 t h i e m o 等【1 6 1 提出一种空问扩展微粒群算 法( s e p s o ) ，算法中假设微粒是具有一定体 积的球体，并且在聚集时会发生碰撞现象。为每个微粒赋半径值，并用于检测两个微粒 是否会碰撞，如果会，则采用弹离策略使它们分离。算法给出三种弹离策略：随机弹离、 实际物理弹离和速度直线弹离，在实验中采用了直线弹离策略，即碰撞发生后，微粒沿 原速度方向做直线运动，并将速度值乘以弹跳因子。弹跳因子可为正也可为负，表明弹 离速度可与原速度同向也可反向：弹跳因子可小于1 也可大于或等于1 ，表明微粒在弹 离后可以加速也可减速。对于高维多峰函数，速度直线弹离显著改善了算法的性能。它 维持了群体的多样性，使得微粒群可以持续进化。另外，在算法运行初期不经常使用弹 离，这样可以避免微粒的碰撞聚集而引起的停滞现象。 2 3 混合微粒群算法 到目前为止，在原始微粒群算法的基础上提出的改进算法已有很多，它们都从不同 角度改善了微粒群算法的性能。但是我们还应该清楚，这些算法并不是在求解所有问题 时性能都是最优的。这就给予该领域的研究者更多的研究前景。 2 3 1 带选择的微粒群算法 a n g e l i n e 利用微粒群机理和通常为进化计算所用的自然选择机理如g a ，最早提出 了一种杂交p s o h s ( h y b r i ds w a r m ) 1 7 】。其原理采用了进化计算中锦标赛选择方法：每个 微粒将其当前位置上的适应度与其它k 个微粒的适应度比较，记下最差的一个得分，然 后整个微粒群以分值高低排队。在此过程中，不考虑微粒的个体极值p b e s t 。群体排序完 成后，用群体中当前位置和速度最好的一半替换群体中差的另一半，而不修改微粒的个 体极值。这样，每一次迭代后，一半微粒将移动到搜索空间中相对较优的位置，这 些移动的微粒仍保留它们的个体极值，以便用于下一代位置更新。此h s 方法加入选择 后具有更强的搜索能力。 2 3 2 基于繁殖和子群的微粒群算法 l o v b j e r g 等进一步提出了基于繁殖和子群的微粒群算法。他们在繁殖过程中引入 1 1 第二章微粒群算法的概述 了繁殖概率来代替适应度。每次迭代时，依据繁殖概率在微粒群中选取一定数量的微粒 放入一个池中，池中微粒随机两两进行繁殖，产生数目相同的后代微粒，用后代微粒代 替父母微粒，使种群数目保持不变。后代微粒的位置由父母位置的算术“交叉 得： c h i l d l ( x 。) - - p * p a r e n t l ( x , ) + ( 1 - p ) * p a r e n t 2 ( x , ) ( 2 6 ) c h i l d 2 ( x ，) = p * p a r e n t 2 ( x , ) + ( 1 一p ) * p a r e n t l ( 置) ( 2 7 ) 其中p 是均匀分布在0 1 之间的随机数。后代的速度向量由父母速度向量之和归一 一化后得到： c h i i d l ( v ，) = c h i l d 2 ( v , ) = 竺p a r e n t 器l ( v i 篇p a r e 端n t 2 ( v , 伽槲i) +) r 川 型器勰l parent2parentl(vi+parent2(v， 1 ) f 川 ( 2 - 8 ) ( 2 - 9 ) 搜索空间中位置的算术交叉操作是标准g a 中最常用的交叉方法之一，这里使用交 叉操作的原因是后代微粒可受益于父母双方，增强搜索能力。例如，父母微粒分别处于 不同局部最优峰值，则其后代能跳出局部最优，更快寻找到全局最优。基于子群的p s o 将微粒群划分成一组子粒群，每一个子粒群有自己的最优解。繁殖操作可在同一子群内 部进行，也可在不同子群之间进行。 2 3 - 3 带高斯变异的微粒群算法 最近，h i g a s h i 和i b a 提出了用进化计算中高斯变异算子与p s o 杂交的思想1 1 9 1 。该 方法在传统的速度与位置更新规则中融入高斯变异，以避免陷入局部极小。在g a 中常 用的变异操作被应用到p s o 中：微粒群中的每个微粒在搜索区域内移动到另一位置时， 不像原来只依据一个先验概率，而不受其它微粒的影响，而是由于高斯变异具有一定的 模糊性。变异的计算公式为： m u t ( ) = 砀+ ( 1 + g a s s i a n ( a ) ) ( 2 1 0 ) 根据实验经验，其中盯取值为搜索空间中一维长度的十分之一。搜索中，微粒依先 验概率选择，它们的位置由具有高斯分布的概率决定。搜索开始时，搜索范围较宽，后 来随着高斯变异率的逐渐减小，搜索效率得到改善。 2 ，3 4 基于邻域算子的微粒群算法 对p s o 中邻域算子的研究发现：邻域算子能改进p s o 性能，因为它能保持微粒群 1 2 中国石油大学( 华东) 硕十学位论文 的多样性，避免过早收敛。 s u g a n t h a n 2 0 1 引入一个可变的邻域算子来改进标准p s o 的性能。在优化的初始阶段， 一个微粒的邻域就是它本身。随着迭代次数增多，邻域逐渐变大，直至包括所有微粒。 换句话说，p s o 算法中的全局极值g b e s t 被一个局部邻域逐渐增加的局部极值k 所代替。 与此同时，p s o 算法中随机漫步和惯性权重的大小也逐渐调整，以使在优化的最后阶段 进行更好的搜索。 2 3 5 多阶段的微粒群算法 a i k a z e m i 等【2 1 1 提出一种多阶段微粒群算法( m p s o ，m u l t i p h a s ep a r t i c l es w a r m o p t i m i z a t i o n ) 。其主要思想是：将微粒群分组，并让群体在算法不同阶段有不同的暂态 搜索目标，这些目标使微粒移离或移向迄今为止自身或全局的最好位置，可防止微粒陷 入局部最优解。m p s o 与p s o 的区别在于每个微粒的位置和速度更新规则。在m p s o 中，速度更新等式为： 2q 串+ 咚水鼬+ q 木嘞( 2 1 1 ) 该更新过程依赖于系数孙c g 和以的设置。对处于不同组和不同阶段的微粒，这些 系数取不同的值。其中咚和氏应该有不同的符号，它们的符号表示微粒将移向还是移 离全局最优值。m p s o 的位置更新等式与基本p s o 一样，但是除非新的位置改善了微 粒的性能，否则微粒不移动，因此微粒的当前位置就是它迄今找到的最好位置。 2 4 小结 本章介绍了微粒群算法的基本思想和算法流程。基于算法思想，本文论述了微粒群 算法的信息交换方式、参数的选择等，然后，详细介绍了微粒群算法的一些改进算法模 型和混合算法模型，其中主要包括离散微粒群算法、带收敛因子的微粒群算法、具有空 间特性的微粒群算法、带选择的微粒群算法、基于繁殖和子群的微粒群算法等。 1 3 第三章基于微粒群算法的核模糊聚类算法 第三章基于微粒群算法的核模糊聚类算法 聚类分析已被广泛应用于数据分析、模式识别、图像处理等方面。常用的聚类方法 可分为如下几类：划分方法，层次聚类方法，基于密度的方法，基于网格的方法和基于 模型的方法。最著名与最常用的划分聚类方法是c 均值及其推广模糊c 均值( f u z z y c m e a n s ，简称为f c m ) 算法。c 均值算法首先由j m a cq u e e n 提出，其原理是：首先 定义一个准则函数，并随机选择c 个初始聚类中心，然后根据样本与聚类中心的距离， 将该样本划分到该类中；再重新计算每个类的聚类中心。此过程不断重复，直到准则函 数最小。 目前p s o 算法在聚类分析领域已经得到成功应用，已被提出的p s o 算法的聚类算 法，如文1 2 2 1 在k m e a n 聚类的基础上提出两种应用p s o 算法的聚类方法，文【2 3 1 应用p s o 算法进行了图像聚类。 3 1 模糊c 均值聚类算法 传统的聚类分析是一种硬划分，它把每个待辨识的对象严格地划分到某个类中，具 有非此即彼的性质。因此这种分类的类别界限是分明的，而实际上大多数对象并没有严 格的属性，它们在性态和类属方面存在着中介性，适合进行软划分。如在人为管理系统、 医疗诊断、心理学、生物学等领域中，许多过程难用精确的数学模型来刻画，而只能用 自然语言来描述，判断方法是建立在直观和经验的基础上，即操作人员是凭借自己的实 践经验来采取对策完成判断任务的。因此自l a z a d e h 教授1 9 6 5 年创立模糊集理论以 来，取得了很多有意义的成果，z a d e h 提出的模糊集理论为这种软划分提供了有力的分 析工具，人们开始用模糊的方法来处理聚类问题，并称之为模糊聚类分析。由于模糊聚 类得到了样本属于各个类别的不确定性程度，表达了样本类属的中介性，即建立起了样 本对于类别的不确定性的描述能更客观地反映现实世界，从而成为聚类分析研究的主 流。 设有限集x = “，x 2 ，矗 属于尸维欧几里德空间r 尸，即t r p ，j - - 1 ，z ，刀。 f c m 算法采用误差平方和函数作为聚类准备函数，见式( 3 1 ) ，= 甜钏一一w 犷( 3 - 1 ) 1 4 中国石油大学( 华东) 硕上学位论文 其中胛为样本数：c 为给定的类别数目，并且1 c mm 称为加权幂指数它影响隶 属度矩阵的模糊度；l 为第f 类的聚类中心；蜥表示样本属于第f 类的程度，满足式( 3 2 ) ： = l ，= 1 ，2 ，玎 ( 3 2 ) f c m 算法就是要求使j 达到最小值的聚类结果，因此将分别为u j ，叻求导，令它 们的导数为0 ，并代入条件得= l 。得： ，j2 封南r ( ) “_ 字1 q 2 f 一 ( ) 册 ( 3 - 3 ) ( 3 4 ) f c m 算法是通过对以上两式进行迭代完成的。当收敛到极小值时，就得到了最终 的聚类结果，即模糊c 划分矩阵u 和聚类中心矩阵c o ，见式( 3 5 ) 、( 3 - 6 ) ： u = “， f = l ，2 ，c ；21，2，z(3-5) w = 【w 】 i = i ，2 ，f ( 3 6 ) 基于上面的思想，下面给出实现模糊c 均值算法的具体步骤： 1 ) 给定类别数c 和允许误差己雠，卜l ； 2 ) 初始化聚类中心c o f ( 力，- - 1 ，2 ，”c ； 3 ) 按式( 3 3 ) 计算隶属度蜥( 0 ，i = 1 ，2 ，c ；产1 ，2 ，力 4 ) 按式( 3 - 4 ) 修正所有聚类中心t o i ( t + 1 ) ，i = 1 ，2 ，c c 2 5 ) 计算误差：p = l i a r , ( t + o - c o , ( t ) i 。如果e = 0 ) ，胪( 巧，圪， 圪) ，聊1 为常数，其约束，见式( 3 8 ) ： = 1 ，其中七= 1 2 ，2 ( 3 8 ) 将核函数代入式( 3 7 ) ，可得式( 3 9 ) ： 0 矽( 稚) 一矽( 杉) 1 1 2 = k ( x k ，砟) + k ( k ，v , ) - 2 k ( x k ，) ( 3 9 ) 由此可以定义式( 3 7 ) ： d ( x ，y ) 垒i i 矽( x ) 一矽( y ) 0 ( 3 一lo ) 撖力为特征空间中的欧氏距离，核代入使之在原输入空间中诱导出了一类核依赖 的新的距离度量，由此将f c m 在欧氏距离下