（电路与系统专业论文）粒子群优化算法在信息隐藏技术中的应用研究[电路与系统专业优秀论文].pdf

论文独刨性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特剐栩以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名；耋照整日期，出3 论文使用授权声明 本人完全了解复虽大学有关保留、使用学位论文的规定，即；学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。傈密的论文在解密后遵守此 规定。 作者签名；扭 导师签名：日期，! 址f 呼 弘 摘要 摘要 隐写术作为信息隐藏技术的一个主要分支，由于其崭新的应用前景，已经受 到学术界和工业界的广泛关注，成为了信息安全技术的前沿方向。 隐写术的研究中要解决以下几个主要问题：( 1 ) 提高信息嵌入量，( 2 ) 保持隐 写结果的质量，( 3 ) 改善隐写算法抵抗隐写分析的性能。本文重点研究了如何应 用粒子群优化算法解决上述三个问题，主要完成了以下几个方面的工作。 ( 1 ) 针对隐藏图像信息隐藏的大容量隐写技术，提出了一种基于粒子群优化 技术的空间域信息隐藏算法。该算法运用粒子群优化算法搜索的最优置换矩阵置 换待隐藏的秘密信息，置换结果通过l s b 替换算法嵌入到掩体图像灰度值中。实 验中将该算法与另外两种基于遗传算法的信息隐藏方法做了比较，结果表明该算 法花费较少时间，且嵌入信息后的图像质量好。 c 2 1 提出了一种基于j p e g 和粒子群优化的变换域隐写算法。该方法首先利用 粒子群优化算法搜索到的最优置换矩阵将秘密信息进行置换；接着修改了j p e g 标准量化表以便能够嵌入较多的信息；将置换结果嵌入到量化后的d c t 系数的 d c 和中低频a c 区域中；最后利用j p i g 熵编码得到隐藏了信息的j p e g 格式文件。 与j q t m 方法的比较实验结果表明，该方法能隐藏的信息量更大，且嵌入信息后 的图像质量更好。 c 3 ) 为了提高空间域l s b 替换算法的安全性，提出了一种能有效抗击r s 隐写 分析的信息隐藏方法。该算法针对r s 隐写分析原理，利用离散二进制粒子群优 化技术，对采用l s b 随机替换算法嵌入信息的s t e g o l 酮像进行灰度值调整，使r s 算法检测不到秘密信息的存在。实验结果表明该方法能有效抵抗r s 隐写分析， 且与同类隐写算法相比，性能更加稳定。 关键字：信息隐藏，隐写术，粒子群优化算法，最低有效位替换，r s 隐写分析， j p e g 图书分类号：t n 9 1 1 7 3 a b s t r a c t s t e g a n o g r a p h y , t h em a i nb r a n c ho fi n f o r m a t i o nh i d m gt e c h n o l o g y , h a v ea r o u s e d b o a r da t t e n t i o ni na c a d e m ya n di n d u s t r y , b e a t , a u s eo ft h e i rb r a n da p p l i c a t i o n s ，a n dh a v e b e e na na d v a n c e dd i r e c t i o no fi n f o r m a t i o ns e c u r i t y t h e r ea r et h r e ei m p o r t a n tp r o b l e m si ns t e g a n o g r a p h y ：( 1 ) h o wt oe m b e dl a r g e s i z eo fs e c r e tm e s s a g e ；( 2 ) h o wt om a k et h ee m b e d d e dm e s s a g eu n p e r c e i v a b l e ；( 3 ) h o wt om a k et h es t e g a n o g r a p h i ca l g o r i t h mb ea b l et oa g a i n s ts o m es t e g a n a l y s i s a l g o r i t h m o u rr a s e a r c hm a i n l yf o c u s e do nh o w t oi m p r o v et h ep e r f o r m a n c eo ft h e s t e g a n o g r a p h i ca l g o r i t h m sb yu s i n gp a r t i c l es w a r mo p t i m i z a t i o no s a l g o r i t h m s o m ew o r k sh a v eb e e nc o m p l e t e da sf 0 h o w s ( 1 ) f o rt h ei m a g eh i d i n gs t e g e n o g r a p h y , an e ws p a t i a ld o m a i ni n f o r m a t i o nh i d i n g m e t h o db a s e do np 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 sp r o p o s e d t h i sm e t h o df w s t e m p l o y st h ep s oa l g o r i t h mt og e tt h eo p t i m a ls u b s t i t u t i o nm a t r i xf o rt r a n s f o r m i n gt h e s e c r e tm e s s a g e s t h et r a n s f o r m e dr e s u l ti st h e nh i d d e n 抽t ot h ec o v e ri m a g e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e p r o p o s e dp s o - b a s e dm e t h o dc o s t s l e s s c o m p u t a t i o nt i m e a n da c h i e v e sab e t t e rs t e g oi m a g e q u a l i t yt h a nt h eg e n e t i c a l g o r i t h m - b a s e di n f o r m a t i o nh i d i n gm e t h o d ( 2 ) an o v e ls t e g a n o g r a p h i cm e t h o d ，b a s e d o nj p e ga n dp a r t i c l es w a n l l o p t i m i z a t i o na l g o r i t h m ，i sp r o p o s e d t h ep r o p o s e dm e t h o df i r s td e r i v e sa no p t i m a l s u b s t i t u t i o nm a t r i xb yp s o a l g o r i t h mf o rt r a n s f o r m i n g t h es e c r e tm e s s a g e s b ym e a n s o ft h es u b s t i t u t i o ns t r a t e g y , t h eq u a l i t yo fs i e g e - i m a g e si si m p r o v e d n e x t , i tm o d i f i e s t h es t a n d a r dj p e gq u a n t i z a t i o nt a b l ef o rt h ep u r p o s eo fa c c o m m o d a t i n gm o r es e c r e t m e s s a g e s t h et r a n s f o r m e dm e s s a g e sa r et h e nh i d d e ni nt h ec o v e r - i m a g ew i t hi t s d e - t o - m i d d ef r e q u e n c yc o m p o n e n t so ft h eq u a n t i z e dd c tc o e f f i c i e n t sm o d i f i e d f i n a l l y , aj p e gf i l e i sg e n e r a t e dt h r o u g hj p e ge n t r o p yc o d i n g w ec o m p a r eo u r m e t h o dw i t hc h a n ge ta 1 sj p e g - b a s e ds t e g a n o g r a p h i cm e t h o d t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tt h ep r o p o s e dm e t h o dh a sb o t hal a r g e rm e s s a g ec a p a c i t ya n dab e t t e r i m a g eq u a l i t yt h a nc h a n g e ta 1 ，s i na d d i t i o n ，o u rm e t h o dh a sah i 班s e c u r i t yl e v e l ( 3 ) t oi m p r o v et h er o b u s t n e s so ft h el e a s t - s i g n i f i c a n t - b i t ( is b ) s u b s t i t u t i o n m e t h o d ，an e wi n f o r m a t i o nh i d i n ga l g o r i t h mr o b u s tt or ss t e g a n a l y s i s ，i sp r o p o s e d t h i sm e t h o df u s te m b e d ss e c r e tm e s s a g e si n t ot h ec o v e r - i m a g e st h r o u g ht h es i m p l e l s bs u b s t i t u t i o nm e t h o da n do b t a i n st h eo r i g i n a ls t e g o i m a g e s 。a n dt h e ni te m p l o y s t h ed i s c r e t eb i n a r yv e r s i o no fp s oa l g o r i t h mt oa d j u s tt h eg r a ys c a l eo ft h eo r i g i n a l 2 s t e g o - i m a g e s b yd o i n gs o , t h er ss t e g a n a l y s i sm e t h o dc a nn o td e t e c tt h ee x i s t e n c eo f s e c r e tm e s s a g ei nt h er e v i s e ds t e g o - i m a g e s t h ee x p e r i m e n t ss h o wt h a to u rm e t h o di s r o b u s tt or ss t e g a n a l y s i sa n dc o m p a r e dt 0o t h e rs t e g a n o g r a p h i ca l g o r i t h m 。i t p e r f o r m sm o r es t e a d i l y k e y w o r d s ：i n f o r m a t i o nh i d i n g , s t e g a n o g r a p h y , p a r t i c l es w a 曲o p t i m i z a t i o n , l e a s ts i g n i f i c a n tb i t s u b s t i t u t i o n , r ss t e g a n a l y s i s , j p e g 绪论 1 1 信息隐藏技术概述 第一章绪论 多媒体数据的数字化为多媒体信息的存储提供了极大便利，同时也极大地提 高了信息表达的效率和准确性。随着计算机网络技术的发展，多媒体信息的交流 已经达到了前所未有的广度和深度，但信息的安全问题日益突出。安全信道和加 密技术两种方式可以用于实现信息保护。但是它们都存在一定的局限性。其中， 安全信道是一种专为发送者和接收者建立的信息通道，除了通信双方，其他人无 法访问。虽然安全性好，但实现复杂，代价昂贵。加密技术【1 】通过加密密钥， 重要信息被加密成密文传输，没有密钥无法解读信息。但加密技术存在如下缺点： 在网络传输中，加密后的密文通常无法通过某些网络节点，造成信息传输的失败； 密文以公开形式进行传输，不隐蔽秘密信息本身的存在，即明确提示攻击者哪些 是重要信息，容易引起攻击者的关注。目前，信息隐藏技术以其特有的优势解决 了加密技术的缺陷，引起了人们的重视。信息隐藏是一门新兴的交叉学科，在计 算机、通信、保密学等领域有着广阔的应用前景，其研究涉及密码学，图像处理、 模式识别、数学和计算机科学等领域。 信息隐藏( i n f o r m a t i o nh i d i n g ) f 2 1 ，有时又被称为数据隐藏( d a t ah i d i n g ) ， 是在不对载体信号产生过分影响的条件下将额外的信息嵌入数字媒体中，以实现 版权保护、隐蔽通信等功能，接收者获得隐藏对象后按照约定的规则读取秘密信 息。信息隐藏技术与加密技术的最大区别在于信息隐藏技术的载体在外观上与普 通载体一样，没有表明重要信息的存在，不易引起别人注意。信息之所以可以隐 藏在这些多媒体载体中是因为多媒体信号本身存在一定的冗余度，同时人的感知 也存在冗余度，人的视觉或听觉存在掩蔽效应，如：人眼对灰度的分辨率只有几 十灰度级。 一个信息隐藏系统模型可用图1 1 表示【3 】，主要有三部分组成：信息嵌入过 程，即利用嵌入密钥实现秘密信息的隐藏过程；信息提取过程，接收方即利用提 取密钥提取嵌入的秘密信息；密钥生成过程，根据一些安全参数生成嵌入密钥和 提取密钥。 这里的待隐藏消息可以是文字，图像，音频，视频，或者是其他任何可以用 比特流表示的数据。用来隐藏消息的载体通常又被称为掩体信号( c o v e rs i g n a l ) ， 通常可以是图像、音频、视频等数字媒体。待隐藏的消息和掩体信号可以不是同 一种结构。比如，我们可以在一幅莎士比皿的画像中隐藏他的声音。隐藏了秘密 4 绪论 信息的掩体信号被称为隐写信号( s t e g os i g n a l ) ，通过一般的观察和分析不应该 察觉它和掩体信号的差异。 图1 - 1 信息隐藏系统的一般模型 接收方收至l j s t e g o 信号和密钥( 如果使用了的话) 就可以恢复出隐藏的消息。一 些信息隐藏系统的提取过程需要掩体信号的参与，通常称为非盲提取，而不需要 掩体信号参与的提取称为盲提取。在绝大多数应用中，都要求不依靠掩体信号恢 复出隐藏的数据。 不可见水印 可见水印 w ( i m a t e m p e r c a r k e p t i b l e w 蕊蕊g ) 图1 - 2 信息隐藏技术的分类【2 1 按隐藏技术的应用目的和载体对象不同，信息隐藏可分为许多分支领域如图 1 - 2 所示【2 】：隐蔽信道，隐写术，匿名，版权标记术等。其中，研究最多的两大 分支为数字水印和隐写术。数字水印和隐写术由于应用领域不同，存在着一定的 区别。数字水印技术【4 - 7 】广泛应用于数字产品版权保护，侧重于鲁捧性，即要求 在信号遭到攻击( 如几何变换，有损压缩等) 后，隐藏的信息仍然能够可靠检测 5 1 一f 1 f 绪论 或提取；而隐写术【8 1 3 】的目的在于保证秘密信息进行安全、隐蔽的传输，因而 侧重于考虑隐写结果与掩体信号之间差别的不可感知性和信息韵嵌入量。本文的 研究重点是隐写术，因此下一节开始详细介绍隐写术的有关特性。 1 2 隐写术 隐写术( s t e g a n o g r a p h y ) 一词来源于希腊词汇s t e g n o s 和g r a p h i a ，意即“隐 藏”( c o v e r ) 和“书写”( w r i t i n g ) ，是一种保密通信技术，通常解释为把秘密消 息隐藏于其他信息当中，其中消息的存在形式较为隐秘。隐写术的目的是将秘密 消息嵌入到看上去普通的信息( 如：图像、音频等数字媒体) 中，以便不引起外 界注意的方式进行传递或存储。 1 工l 隐写术分类 隐写术大致可分为两种【2 】：一种是将秘密传递的信息记录下来，隐藏在特 定媒介中，然后再传送出去的一种技术，称为技术隐写术( t e c h n i c a l s t e g a n o g r a p h y ) ：另一种是将“记录”这个行为本身隐藏起来的技术，信息由隐 藏的“写”语言和语言形式所组成，称为语义隐写术( l i n g u i s t i cs t e g a n o g r a p h y ) 。 语义隐写术利用了语言文字自身及其修辞方面的知识和技巧，通过对原文进 行一定规刚下的重新排列或剪裁，从而隐藏和提取秘密信息。语义隐写术包括符 号码( s e m a g r a m ) 、隐语( o p e nc o d e ) 以及虚字密码( n u l lc i p h e r ) 等【3 l 。早在 1 6 至1 7 世纪，出现了大量的关于语义隐写术的著作，其中许多方法都依赖于信 息编码，即属于语义隐写术中的符号码。s c h o t t ( 1 6 0 8 - 1 6 6 6 ) 在他的著作( s c h o l a s t e g a n o g r a p h i c a ) 中阐述了如何将秘密信息嵌入乐谱中，即每个音符对应于一个 英文字母。隐语所利用的则是错觉或代码字，例如，在第一次世界大战期间，德 国间谍使用雪茄的假定单来代表不同类型的英国军舰，例如朴茨茅斯需要5 0 0 0 根雪茄就代表着朴茨茅斯有5 艘巡洋舰等。在虚字密码中，使用每个单词的相同 位置的字母来拼出一条消息。k a h n 在皿ec o d e b r e a k e r s ) 一书中阐述了一个僧 侣是如何撰写本书，且该书每个章节标题的第一个字母拼接起来组成了他爱人 的名字。另外，中国古代的藏头诗也属于一种虚字密码。 早在公元前4 4 0 年前，就已经有了把奴隶的头剃光将信息纹在头皮上、待头 发长出来后令其去传递信息情报的方法，这就是早期比较典型的技术隐写术。采 用技术隐写术方法的实例还很多，比如：将信息隐藏在信使的鞋底或妇女的耳饰 中，改变字母笔划的高度或在正文的字母上( 下) 面挖出非常小的洞来隐藏信息 等。现代社会的技术隐写术都采用图像，文本或视频等多媒体数字产品作为掩体 信号来隐藏信息。据外刊报道，美国“9 - 1 1 ”事件后。恐怖大亨拉登向世界公布 6 绪论 的录像带就一直被美英怀疑图像中隐藏了某种指令。 1 2 2 隐写术的性能要求 我们可以从以下三个方面来评估一个隐写方法的优点和缺点。各个方面的相 对重要性取决于不同的应用。 隐写容量( m e s s a g ec a p a c i t y ) ：隐写容量是指相对于掩体信号的大小能够 隐藏的信息量的多少。对于给定大小的消息，大的隐写容量意味着可以使用小的 掩体信号来隐藏信息，从而可以减少传送隐写后图像的带宽。 不可见性( i n v i s i b i l i t y ，t r a n s p a r e n c y ，i m p e r c e p t i b i l i t y ) ；嵌入数据的同时 不引起掩体图像视觉效果上的损失或图像质量的显著下降在大多数应用中是非 常重要的。在隐秘通信应用中，如果一个攻击者注意到了图像视觉上的变化，就 会让他怀疑其中隐藏了数据，即使攻击者不能从嵌入数据后的图像中恢复出数 据，这个隐写过程也是失败的。对信息不可见性的测试可分为主观测试和客观测 试两种。主观测试采用一定数量的没有经过训练的旁观者，根据他们是否能够区 分出未嵌入信息和已嵌入信息的图像来进行评判的测试。客观测试则使用差别失 真评测准则来评价嵌入信息所引起的掩体图像的扭曲程度。常用的差别失真评测 准则是峰值信噪比( p s n r ：p e a ks i g n a lt on o i s er a t i o ) ，单位为分贝( d b ) 。 抗隐写分析性能( a n t i - s t e g a n a l y s i s ) 隐写分析技术( s t e g a n a l y s i s ) 是对隐写 术的攻击，目的是为了检测秘密消息的存在以至破坏隐秘通信。因此，对隐写术 算法评价的另一个重要指标之一就是考察抵抗已有隐写分析方法的能力。 对于某一特定的隐写算法，隐写容量、不可见性以及抗隐写分析能力三者是 相互矛盾的。增加任何一个的性能，其余两者都会有不同程度的下降。 1 2 3 隐写分析技术 随着隐写技术的发展产生了隐写分析技术( s t e g a n a l y s i s ) 【1 4 1 9 i 。隐写分析 是对隐写术的攻击，它利用隐写术的弱点，即秘密信息的嵌入会导致掩体信号数 据分布特性或某些统计特性发生变化，来检测信号中是否隐藏了秘密信息，或者 破坏甚至提取出载体信号中隐藏的信息。在实际应用中，如果可以检测到载体信 号中存在秘密信息，那么隐写分析就是成功的。隐写分析是解决非法使用隐写术 问题的关键技术。隐写分析技术的提高有利于防止隐写术的非法应用，可以起到 防止机密资料流失、揭示非法信息、打击恐怖主义、预防灾难发生的作用，从而 保证国家的安全和社会的稳定。隐写分析不仅具有重要的应用价值，更具有重要 的学术意义。隐写分析研究可以揭示当前隐写术的缺陷，对隐写术的安全性进行 测试与评价，这是信息隐藏技术发展与完善的一条有效途径。 7 绪论 隐写分析专家根据获得信息的不同将攻击分为以下几种情况【1 4 】：已知s t e g o 信号的攻击( s t e g o - o n l y ) ：只可获得s t e g o 信号进行分析；己知掩体信号的攻击 ( k n o w n 岍) ：可以获得原始的载体和s t e g o 信号：已知消息攻击( 跏 m e s s a g e ) ：在某种意义上，攻击者可以获得隐藏的消息，针对系统分析秘密消息 相应隐藏信息的模式有利于将来的攻击；已知隐写算法的攻击( c h o s e ns t e g o ) ： 知道隐写工具( 算法) 和s t e 9 0 1 j 言号；已知恢复方法的攻击( c h o s e nm e s s a g e ) ：隐 写分析专家用某个隐写工具或算法对选择的消息生成s t e g o 信号，这个攻击的目 标是确定s t e g o 信号中相应的模式特征，它可以用来指出具体使用的隐写工具和 算法。 1 3 信息隐藏技术的研究现状 1 3 l 信息隐藏技术的发展 关于信息隐藏技术最早的记录是在公元前4 4 0 年，在旧约圣经中提到， 它的作者是古希腊的著名的历史学家希罗多德( h e r o d o t u s ) 。希罗多德在他的著 作中曾经讲述这样一个故事，波斯宫廷里有一个1 1 q d e m e r a t u s 的希腊人想发信息 给他的朋友( s p a r t a ) ，告诉他波斯国王_ x e r x e s - - 世将要发动入侵希腊战争。于是， 他将这条消息隐藏在写字板下面。当时的写字板是由两片木头像书一样装上合页 组成的，木头的每一面都覆盖着蜡。发送方在蜡上写字，接收者将蜡熔化之后又 可以重新使用写字板。d e m e r a t u s 的办法是将蜡除去后在木头上写上消息，然后 用蜡将其重新覆盖住，之后将表面上空白的写字板送往希腊。 从1 5 世纪到1 6 世纪，许多作家有关于文字的译码技术、隐形墨水以及隐秘信 息和音乐的组合的论文发表，如j o h a n n e st r i t h e m i u s 撰写的( s t e g a n o g r a p h i a ) 和 g a s p a r s c h o t t i 的 s t e g a n o g r a p h i c a ) 。在1 8 8 3 到1 9 0 7 之间，a u g u s t ek e r c k h o f f 发 表著作 c r y p t o g r a p h i cm i l i t a i r e ) ) ，c h a r l e sb r q u e t 发表 l e sf i l i g r a n 髂) ，虽然两 本书更多的是关于密码学的内容，但是为隐写技术的发展奠定了理论基础。在第 一次世界大战和第二次世界大战中，隐写技术得到很大的发展。 现在，随着网络和多媒体技术的飞速发展，人们可以充分利用多媒体中存在 的冗余信息作为隐藏消息的掩体信号，并将隐写结果通过计算机互联网络发送出 去。每年i e e e 、s p l e 等国际重要期刊上都发表了大量隐写术算法的文章，而且 许多研究机构也都投入入力、物力进行研究和开发。互联网上也出现了很多信息 隐藏软件，如：e z s t e g o 2 0 ，j p e g - j s t e g 2 1 】，s t e g a n o s 2 2 ，s - t o o l s 2 3 等。使用 的最多的隐写技术是l s b 嵌入法，或是直接把信息嵌入在图像的像素里，或者 是嵌入在带调色板图像的索引里( e zs t e g o ) ，或是嵌入在j p e g 格式图像的经量 8 绪论 化的d c t 系数里( j p e g - j s t e g ) 。 1 3 2 基于图像和优化算法的信息隐藏算法 目前，以图像为掩体信号的信息隐藏算法大体可以分为两类：空间域信息隐 藏【8 i o ，变换域信息隐藏【1 1 1 3 ，2 4 - 2 6 。其中，空间域信息隐藏算法多采用l s b 替换法，即用秘密消息位替换掩体图像中最不重要的位置，接收方只要知道秘密 信息嵌入的位置就能提取信息。变换域的方法把将秘密信息嵌入到掩体图像的某 些交换系数中，如d c t 系数和小波系数等。近几年，国内外有部分学者开始致 力于基于进化的优化技术和信息隐藏算法的相结合，利用这类优化算法进一步优 化信息隐藏算法性能。 ( 1 ) 空间域信息隐藏算法 2 0 0 1 年，w a n g 等人f 8 】首次将遗传算法用于信息隐藏技术中，改进了空间域 的l s b 替换算法，提出一种能隐藏大量信息的隐写方法，通过遗传算法的优化 使得隐写结果更接近掩体图像，不易被人察觉。2 0 0 4 年，w u 等人f 9 】在w a n g 等 人工作的基础上，利用遗传算法把秘密信息进行分子块置换，进一步提高了s t e g o 图像的质量。2 0 0 6 年，j j 等人p 0 也提出了一种基于遗传算法的全局最优块映射 的l s b 替换方法，利用遗传算法搜索到一种最优的映射方式，把秘密信息分块 位置重新映射后再嵌入掩体图像，提高了s t e g o 图像的质量。 ( 2 ) 变换域信息隐藏算法 2 0 0 4 年，k u m s a w a t 等人f 矧利用遗传算法搜索到最优的阈值和信息嵌入强 度，从而改进了一般的小波域的信息隐藏算法，提高了s t e g o 图像质量和算法的 鲁棒性。2 0 0 5 年，s h i l l 等人【2 5 】针对医学图像提出了一种基于遗传算法的变换域 水印算法，利用遗传算法分子块调整掩体图像灰度，使得调整后的图像d c t 系 数的特定位置能够被提取出秘密信息。2 0 0 6 年，l e e 等人1 2 6 提出了基于遗传算 法的离散小波变换域水印，利用遗传算法盲提取嵌入的水印信息，能够有效抵抗 几何攻击。随后，w u 等人1 2 7 分别针对几种经典的变换域和空间域隐写分析算 法，将遗传算法用于改进现有的几种隐写方法以使其能够抵抗隐写分析算法，极 大地提高了隐写术的安全性。 但是我们通过研究发现，目前信息隐藏技术中通常采用的都只是基于进化的 优化算法中的遗传算法。2 0 0 5 年，e 1 b e l t a g i 等人【2 8 】研究比较了五种基于进化的 优化算法( 粒子群优化算法，遗传算法，m c m e t i c 算法，蛙跳算法和蚁群算法) ， 指出粒子群优化算法性能最为突出。因此，本文的研究重点是以灰度图像作为掩 体信号，将粒子群优化算法应用于空间域和变换域的隐写术算法研究中，希望通 过粒子群优化算法能够改善隐写术的性能，达到在保证隐写结果的不可感知性的 9 绪论 前提下，能够嵌入尽可能多的秘密信息，同时研究如何采用粒子群优化算法来增 强隐写术的安全性。 1 4 粒子群优化算法 1 4 1 五种基于进化的优化算法 基于进化的优化算法( e v o l u t i o n a r y - b a s e do p t i m i z a t i o na l g o r i t h m ) 由于其性 能优异在数学和实际工程领域中得到了广泛的应用。因此本节就来研究一下五种 基于进化的优化算法，特别着重介绍其中的一种粒子群优化技术。 自然界中，很多生物行为具有一些特性，比如，蚂蚁能够找到最短的途径到 达食物所在地，鸟类在迁徙途中可以准确找到它们的目的地等。这类生物行为的 形成是通过学习，自适应和进化。很多学者都通过模拟这些高效的生物行为研究 出有效的计算系统来求解那些复杂的优化问题。进化算法就是一类通过模拟自然 界的生物进化或生物群体行为的优化搜索算法。过去的十几年中，研究人员通过 模拟不同的生物活动陆续提出了五种不同的基于进化的优化算法：遗传算法( g a ： g e n e t i c a l g o r i t h m ) 【2 9 ，m e m e t i c 算法【3 0 1 ，粒子群优化算法( p s o ：p a r t i c l es w a r m o p t i m i z a t i o n ) 【3 1 】，蚁群优化算法( a c o ：a n t 。c o l o n yo p t i m i z a t i o n ) 【3 2 】以及蛙跳 算法侣f l ：s h u f f l e df r o gl e a p i n g ) j 3 3 a 最早出现的基于进化的优化算法是遗传算法( g a ：g e n e t i c a l g o r i t h m ) 。遗传 算法是依照达尔文关于自然界中“物竞天择，适者生存”的选择与进化观点形成 的搜索策略。遗传算法经过遗传，交叉和变异运算模拟生物界的进化过程，能比 较有效的搜索出复杂问题的近似最优解，因而被广泛应用到科学计算和工程领域 3 4 3 6 1 。但是遗传算法的缺点在于需要花费大量的时间去搜索到一个近似最优 解，同时有些问题用遗传算法无法求解。 m e m c t i c 算法结合了遗传算法和局部优化策略的特点，有时也被称为混合遗 传算法( h y b 珊g e n e t i ca l g o r i t h m ) 或遗传局部搜索( g e n e t i cl o c a ls e a r c h ) 算 法。遗传算法对构成解种群的解施加交叉、组合、变异等操作，这一过程不断迭 代，达到提高解质量的效果，具有全局寻优的能力，但是往往运行时间比较长， 运行时占用比较多的计算机资源：局部搜索也是组合优化中常见的寻优算法，属 于一种启发式算法，局部搜索能有效探索解空间中的某个特定的区域，但是无 法跳出局部最优的“陷阱”。m e m e t i c 算法结合这两种算法，克服他们的不足， 算法采用遗传算法的整体框架，利用局部搜索技术在算法运行过程中提高解的质 量。 粒子群优化算法是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种新型的群体 1 0 绪论 智能( s w a r mi n t e l l i g e n c e ) 进化计算技术。粒子群优化算法源于对鸟群飞行行为的 研究，通过对“鸟群”简单社会系统的模拟，在多维解空间中构造“粒子群”， 并通过粒子之间的相互作用发现复杂搜索空间中的最优区域。粒子群优化算法是 一类随机全局优化技术，其简单易于操作、依赖的经验参数较少、收敛速度快。 1 9 9 6 年，d o r i g o 等人通过研究蚂蚁觅食行为提出了蚁群优化算法，与粒子 群算法类似，这也是一种基于群体智能的进化算法。自然界中蚂蚁在觅食过程中 沿途散播一种化学物质，称为信息素( p h e r o m o n e ) ，信息素中记录了食物源的远 近与食物量的多少，而其它蚂蚁通过触角能够检测识别到这种信息素并跟踪，从 而找到食物源。当大量蚂蚁不断地从蚁穴通往食物源，并在识别原有信息素的同 时沿途不断地散播新的信息素时，使得越短路线上的信息素浓度越来越高，从而 最终找到一条最短的路线，此后所有的蚂蚁都将沿这条路线到达食物源。 蛙跳算法本质上是遗传算法和粒子群优化技术的结合。在蛙跳算法中，一组 “青蛙”( 代表问题的一个潜在解) 构成了一个大群体，这个大群体又被随机分 成不同的子群，不同的子群具有不同的特点，每个子群都进行局部搜索。每个子 群就类似一个粒子群，进行更新迭代。每个子群进行有限次的迭代后，整个大群 体再重新进行随机的分组，每个新的子群继续进行新的迭代计算。 1 4 2 粒子群优化技术起源 自然界中，鸟群运动的主体是离散的，其排列看起来是随机的，但整体的运 动却保持着惊人的同步性。这些呈分布状态的群体表现出的似乎是有意识的集中 控制，一直是许多学者感兴趣的问题。例如。1 9 8 6 年r e y n o l d s 提出了b o l d 模型 用于模拟鸟类聚集飞行。r e y n o l d s 对鸟群飞行的研究发现，鸟仅仅是追踪它有限 数量的邻居，但最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂 的全局行为是由简单规则的相互作用引起的。通常单个自然生物并不是智能的， 但是整个生物群体却表现出处理复杂问题的能力，群体智能就是这些团体行为在 人工智能问题中的应用。 生物社会学家w i l s o n 认为 3 7 1 “至少从理论上，在搜索食物的过程中群体中 的个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测的 零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣 势。”也就是说，群体中的个体之间信息的社会共享有助于进化。 受上述鸟群运动模型的启发，1 9 9 5 年，社会心理学博士k e n n e d y 和电子工 程学博士e b e r h a r t 提出了一种新型的群体智能( s w a r mi n t e l l i g e n c e ) 进化计算技术 粒子群优化算法 3 1 1 。粒子群优化算法通过研究鸟类飞行觅食行为，模拟鸟 群的集体协作便群体以最快的速度找到最优解。粒子群优化算法源于对鸟群捕食 1 1 绪论 行为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到 食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。另外，人们 通常是以自己及他人的经验来作为决策的依据，这就构成了粒子群优化算法的一 个基本概念。 粒子群优化算法由于其具有较强的优越性，自问世以来短短十年的时间里， 己被应用于约束优化、函数优化、多目标优化、最大最小优化问题以及旅行商等 典型优化问题的求解之中，在工程设计与优化、航空、金融、通讯、机器人控制、 交通运输、工业生产优化和生物医学等诸多领域得到应用 3 8 - 4 0 。在处理大规模 复杂非线性优化问题方面，相比较其他优化算法，粒子群优化技术由于没有中心 控制约束，个别个体的故障不会影响到整个问题的求解，鲁棒性好；引入并行随 机搜索策略，能更有效地找到全局最优解，结果更符合实际情况。 i a 3 粒子群优化算法原理 粒子群优化同遗传算法类似，也是一种基于“群体”和“进化”的优化算法， 其基本思想是，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子0 所有的粒子都有一个被优化问题的目标函数所决定的适应值( f i t n e s sv a l u e ) ，以 此来评价粒子的优劣。每个粒子还有一个速度向量决定它们的搜索方向和搜索范 围。在搜索过程中，粒子将通过跟踪两个极值，一是粒子本身找到过的个体最优 解( 即个体极值，代表该粒子自身对寻优方向的认知水平) ，另一个是当前整个 群体找到的最优解( 即全局极值，代表粒子社会认知水平) ，来调节自身速度， 在解空间中搜索。 通过数学模型描述为：假设粒子群在一个d 维空间中进行搜索，群中的每个 粒子所处的位置表示为x 一o i 0 x a l ，一。) ( f - 1 , 2 ，h u m ) ，其c i a n u m 是群中粒 子总数，每个粒子的速度表示为k 一“。，v j 。，。) 。每个粒子通过不断调整自 己的位置来搜索新解，并用目标函数来评价每个粒子的优劣。各个粒子追随当前 的最优粒子，在解空间中进行搜索。每次迭代的过程既有确定性，又有随机的因 素。每一次迭代中，粒子通过跟踪两个“最优解”来更新自己：一个就是粒子本 身所找到的最好解( 表示成t 4 7 b e s t ) ；另一个“最优解”是整个粒子群经历过的最 好位置( 表示成曲耐) 。在找到这两个最好解后，通过个体粒子当前位置与个体 极值和全局极值间的距离来调整自身的速度；然后，以此速度飞行，更新该粒子 的位置。粒子移动原理图如图1 - 4 1 所示。从图中可以看出，粒子每次的迭代都 是朝着更接近的耐和妒耐的方向。 绪论 图1 4 - 1 粒子移动原理图 粒子的速度和位置更新表达式如下所示： ，右“- 培+ c 。n 翩订：( p 妇占一) + c ：，翮矗：( 如一丐：) ， x k _ + l x k q + v 矗。 ( 1 4 - 1 ) ( 1 4 2 ) 其中，屹是粒子f 在第k 次迭代中的第d 维的速度，工占是粒子f 在第k 次迭 代中的第d 维的位置；c t ，c 2 是学习因子，通常令c l - c 2 2 ；r a n d 2 是【o ，l 】之 间的随机数。为防止粒子远离搜索空间，粒子的速度的每一维都会被限制在 f 呻一，】之间。通常粒子群优化算法都会预先设定一个最大迭代次数，当达 到这个最大迭代次数时，则终止迭代，输出最优结果。 基本粒子群优化算法包含以下参数：种群规模一啪，粒子维数d ，最大迭代 次数i l e r _ m a x ，学习因子c ，和c ：。粒子群优化算法的流程如下： s t e p l 初始化。设置种群规模胆啪，最大迭代次数i t e r _ r n a x 和学习因子c l 和c 2 。 在允许范围内随机设置每个粒子的初始位置x ? 和速度k o ，每个粒子的个 体极p b e s t ；取其初始化为x 。，全局极值g b e s t 初始化为所有粒子中适应 值评价最好的粒子位置。 s t e p2 用式( 1 - 2 ) 对每一个粒子的速度和位置进行更新。 s t e p3 评价每一个粒子的适应度值。 s t e p4 更新个体最优值p b e s t ；。对每个粒子，将其适应值和个体极值比较，如果 优于砷耐；，则替换p b e s t ；为该粒子的位置。 s t e p5 更新全局最优值妒耐。如果所有粒子的个体极值中最好的好于当前的全 局极值，则将该个体极值设置为的g b e s t 。 s t e p6 检验是否符合结束条件。如果当前的迭代次数达到了预先设定的最大次数 ( 或达到最小错误要求) ，则停止迭代，输出最优解，否则转到s t e p 2 。 1 4 4 粒子群优化技术的改进 粒子群优化算法是通过粒子间的相互作用发现复杂搜索空间中的最优区域， 绪论 是一类随机全局优化技术。粒子群优化算法没有遗传操作，如交3 ( c r o s s o v e r ) 和 变异( m u t a t i o n ) ，而是利用个体在解空问中的随机速度来改变个体，其解群相对 进化代数而言，表现出更强的随机性，其计算复杂度比遗传算法低。遗传算法中 染色体共享信息，故整个种群较均匀地向最优区域移动。在粒子群优化算法中 g b e s t 将信息传给其他粒子，是单向的信息流动，多数情况下，所有的粒子可能 更快地收敛于最优解。 但是，粒子群优化算法同样也存在着陷入局部最优的可能，而且局部搜索精 度较低，易发散。若学习因子、最大速度等参数太大，粒子群可能错过最优解， 算法不收敛；而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以 粒子趋向同一化( 失去了多样性) ，使得后期收敛速度明显变慢，同时算法收敛 到一定精度时，无法继续优化，因此很多学者都致力于提高粒子群优化算法的性 能，尤其是收敛速