（应用数学专业论文）使用进化算法的矢量量化.pdf

摘要 使用进化算法的矢量量化 曹凯 摘要矢量量化是一种有效的有损压缩技术，广泛应用于图像和语音压缩领域， 其最突出的优点在于解码算法简单。矢量量化的基本问题是码书设计和码字搜索， 码书设计决定了压缩性能，是矢量量化的关键。传统的l b g 和树结构等码书设计 算法，因依赖初始码书或聚类种子，以及码书的自适应能力不强等原因，不易逼 近全局最优解。遗传算法作为一种新的全局优化搜索算法，具有群体多样性、简 单通用、鲁棒性强、适于并行处理等显著特点，得到了广泛应用。它能够在搜索 过程中自动获取和积累有关搜索空间的知识，并自适应控制搜索过程以接近全局 最优解，可以弥补传统码书设计算法的不足。人工蚁群优化是一种全新的智能搜 索算法，人工蚂蚁通过概率选择和信息素更新来模拟自然界中真实蚂蚁的觅食行 为。目前蚁群算法在旅行商问题和车辆路径问题等组合优化问题中的应用较为成 熟，在矢量量化图像压缩编码中的应用才刚刚起步，其应用于码书设计值得进一 步深入研究。 本文首先根据遗传算法中染色体的不同选取方案，提出了基于训练矢量划分 和基于码书的码书设计算法，实验证明这两种算法都优于传统码书设计算法。接 着介绍了蚁群算法的原理以及基于人工蚁群算法的矢量量化图像压缩编码码书设 计建模。针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优，本 文提出了一种新的信息素更新方法和局部调整算法，即对属于不同性能聚类中心 的训练矢量之间增加不同的信息素增量以及采用模拟退火策略调整最不相似训练 矢量，实验结果表明改进的蚁群算法使峰值信噪比( p s n r ) 提高t o 1 1d b 。将蚁 群算法和遗传算法相结合，提出了遗传蚂蚁码书设计算法，即在蚁群算法中嵌套 遗传算子，首先通过概率选择产生的划分作为遗传算法的初始种群，通过选择、 交叉及变异算子产生新的划分以后进行排序，舍弃后面的一半，并用前面的一半 更新信息素。实验表明，对于2 5 6 x 2 5 6 8 b i t 的标准l e n a 图，码书大小为2 5 6 时，遗 传蚂蚁码书设计算法所获得的p s n r 为2 9 8 2 d b l ： ：单纯的蚁群算法码书算法提高了 0 2 3 d b 。 关键词：图像压缩，矢量量化，码书设计，遗传算法，蚁群算法 a b s l r a e t v e c t o rq u a n t i z a t i o nu s i n ge v o l u t i o n a r ya l g o r i t h m c a o k a i a b s t r a c ta sa l le f f i c i e n tl o s sc o m p r e s s i o nt e c h n i q u e ，v e c t o rq u a n t i z a t i o ni sk n o w nf o r i t ss i m p l ed e c o d i n g , a n dh a sb e e nw i d e l ya p p l i e dt oi m a g ea n ds p e e c hc o m p r e s s i o n t h ef u n d a m e n t a lp r o b l e mo fv e c t o rq u a n t i z a t i o ni sd e s i g n i n gc o d e b o o ka n ds e a r c h i n g f u rc o d e w o r d d e s i g n i n gc o d e b o o kw h i c hd e t e r m i n e sc o m p r e s s i v ep e r f o r m a n c ei sv i t a l t 0v e c t o rq u a n t i z a t i o n t h et r a d i t i o n a la l g o r i t h m sf o rd e s i g n i n gc o d e b o o ks u c ha sl b g a l g o r i t h ma n dt r e e s t r u c t u r ea p p r o a c hd e p e n d so nt h ei n i t i a lc o d e b o o ko ra g g r e g a t e d c l a s ss e e d s ，i na d d i t i o n ，t h es e l f - a d a p t i v ea b i l i t yo fc o d e b o o ki sv e r yw e a k , t h e r e f o r e ，i t i sh a r dt oa p p r o a c ht h eg l o b a lo p t i m a ls o l u t i o n a sag l o b a lo p t i m i z a t i o ns e a r c h i n g a l g o r i t h m ，f e a t u r i n gc o l o n yd i v e r s i t y ，s i m p l eu n i v e r s a l i t y ，s t r o n gr o b u s t n e s s ，b e i n gf i t f o rp a r a l l e lp r o c e s s i n g , a n dw i d eu s a g e ，g e n e t i ca l g o r i t h mc a na c q u i r ea c c u m u l a t e a u t o m a t i c a l l yk n o w l e d g er e l a t e dt os e a r c h i n gs p a c ed u r i n gt h es e a r c h i n gp r o c e s s , a n d c o n t r o ls e l f - a d a p t i v e l yt h es e a r c h i n gp r o c e s st oa p p r o a c ht h eg l o b a lo p t i m a ls o l u t i o n , w h i c hm a k eu pt h ed e f i c i e n c yo ft h et r a d i t i o n a la p p r o a c ho fv e c t o rq u a n t i z a t i o n a n t c o l o n yo p t i m i z a t i o n ( a c of o rs h o r t ) w a sf i r s tp r o p o s e db yd o r i g o , i ta d o p t sr a n d o m s e l e c t i o na n dp h e r o m o n er e n e wa st h er e a la n t sf o r a g et os o l v et h ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s n o wa c ow a ss u c c e s s f u l l ya p p l i e di nt s p ，j s p ，a n dt h e r e s e a r c hi nc o d e b o o kd e s i g nh a sb e e ns t a r t e dr e c e n t l y ，i ti sw o r t ht ok e e po n a c c o r d i n gt ot h ed i f f e r e n tc o d i n gd e s i g no nc h r o m o s o m ei nt h eg e n e t i ci g o r i t h m ， w ep u tf o r w a r dt h ec o d e b o o kd e s i g no fg e n e t i cv e c t o rq u a n t i z a t i o nb a s e do nt r a i n i n gl i s t a n dv e c t o rq u a n t i z a t i o nb a s e do nc o d e b o o k , f u r t h e r m o r e ，i t sv a l i d i t yi sp r o v e d t h e n i n t r o d u c e st h et h e o r ya n dm o d e lo fa c oa n dt h ea p p l i c a t i o no fa c oi ni m a g ev e c t o r q u a n t i z a t i o n a sf o rt h em a i nd e f e c to fa c o ，s u c ha ss l o wc o n v e r g e n c es p e e da n df a l l i nl o c a lo p t i m i z a t i o n ，t h i sp a p e rm e n d st h ea c oa l g o r i t h mw h i c hu s e di ni m a g ev e c t o r q u a n t i z a t i o n ：t h i sp a p e ra d o p t san o vp h e r o m o n e up d a t em o d e l t r a i nv e c t o r s ，w h i c h b e l o n gt od i f e r e n tc l u s t e r i n gc e n t e r s ，h a v ed i f f e r e n tp h e r o m o n ei n c r e m e n t ，a n du s e s s i m u l a t e da n n e a l i n gs t r a t e g yt oa d j u s tt h et r a i n i n gv e c t o r sw h i c hh a st h em a x i m u m d i s t a n c eb e w t e e nt h et r a n i n gv e c t o ra n di t sr e p r e s e n t a t i v e ，e x p e r i m e n ts h o w st h a tt h e m o d i f i e dm e t h o dh a si m p r o v e dt h ec o d e b o o kq u a l i t y0 1 6 d b ；c o m b i n eg e n e t i c a l g o r i t h ma n da c oa l g o r i t h m ，ag e n e t i ca c oa l g o r i t h mi sp r o p o s e d ，g e n e t i co p e r a t o r s i si n t e g r a t e di n t oa c o se v e r yi t e r a t i v e ，t h ec o d e b o o k sw h i c hg e n e r a t e df r o ma c oa r e o p t i m i z e db yg e n e t i co p e r a t o r , e x p e r i m e n ts h o w st h a tt h ep s n ro fc o d e b o o k ，w h i c h a b s t r a c t g e n e r a t ef r o mg e n e t i ca c o , i s2 9 8 2 ，t h e r ei s0 2 3 d bi n c r e a s et h a nt h ec o d e b o o k g e n e r a t e do n l yb ya c o t h r o i _ l g ht h ew o r ko ft h i sp a p e r , w ec a r ls e et h es e a r c ha b i l i t yo fa c o , t h e c o m b i n a t i o no fg e n e t i ca n da c oc o n t a i n st h ea d v a n t a g e so fg e n e t i ca n da c o i m p r o v e sc o d e b o o k sp e r f o r m a n c eg r e a t l y k e y w o r d s ：i m a g ec o m p r e s s ，v e c t o rq u a n t i z a t i o n ，c o d e b o o kd e s i g n ，g e n e t i ca l g o r i t h m ， a n tc o l o n yo p t i m i z a t i o n i l l 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 作者签名：盐纽 日期：乏丑垒纽，臼 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索 有权将学位论文的标题和摘要汇编出版。 作者签名：曾灿 日期：型 垒丛1 2 j 第1 章前言 第1 章前言 当前，随着人类科学技术的飞速发展，信息时代已经到来，与此紧密相关的 数据压缩技术一直得到广泛的重视。在经过长期的世界范围内的研究与探索之后， 很多有效的数据压缩技术已经成功应用于实际的数据存储与数据传输系统中。图 像矢量量化具有解码算法简单，压缩比高等特点，已经成为图像压缩编码的重要 技术之。 本章主要介绍图像压缩中的矢量量化技术的研究背景、研究现状、研究目的 和意义。并介绍本文所研究的主要内容、创新，及章节安排。 1 1 研究背景 人类社会已经进入了信息时代，建立在计算机技术和通信技术上的信息高速 公路使我们能更新、更快、更准确地掌握各种信息。 图像信源由于其具有非常丰富的信息量而成为传递信息的重要媒介。我们日 常所获取的信息有百分之七十以上来自于视觉，可以说图像正成为信息高速公路 上一种重要的媒体。数据量大是数据图像的一个显著特点，例如：按c c i r6 0 1 标准 对常规电视信号进行每秒2 5 帧，每帧分辨率为7 2 0 x 5 7 6 y ：u ：v 为4 ：2 ：2 每个分量8 b i t 的格式进行数字化，则其总数码率可达1 6 6 m b s 。这给数字图像的存储、传输带来 了极大的困难，因此必须进行压缩以减少数据量。日前数据图像压缩技术已成为 信息高速公路、高清晰度电视( h d t v ) 、可视电话、会议电视、多媒体通信等技术 的关键，在航空遥感、生物医学工程等领域也起着非常重要的作用。 在近几十年，数字系统由于其实现的低费用，易于规划以及较小的失真的优 点，已经广泛得到应用。在现实世界中，因为大多数信号均是连续的波形( 时间和 幅值下均连续) ，所以需要把这些信号转化为适合数字处理的离散信号( 时间和幅值 上均离散) 。n y q u i s t 采样定理证明了在满足一定条件下，连续时间信号转化为离散 时间信号不会产生失真。但是连续幅值转化为离散幅值的量化操作必将产生失真【1 】 因此有损量化问题，广义上说是信源编码，几乎出现在每个使用数字系统的场合。 为了在通信通道进行传输或便于存储，需要采用相对低的码率表示模拟样本序列 的数据压缩系统。根据香农率失真理论【2 】，矢量量化( v q ) 能获得比其它基于标量 量化的编码力法更好的压缩性能，因此它作为一种高效的数据压缩方法，近年来 己经厂泛地用于语音、图像压缩和模式识别等领域。 在二十世纪六十年代初期和中期，出现了最早的矢量量化思想，h u a n g 和 s c h u l t h e i s s 提出最早的分组量化的基本实现方法【3 】。直到1 9 8 0 年由l i n d e ，b u z o 和 第1 章前言 g r a y 将聚类算法弓 入到矢量量化器设计中，提出来一种著名的矢量量化码书设计 算法，即l b g 算法【4 】( 又称g l a 算法) ，其文献已经成为矢量量化的经典文献，是矢 量量化技术发展的鉴石。随后，现代的矢量量化研究得到了日益广泛的关注。各 国学者以l b g 算法为基础，钊对矢量量化器的特点，将神经网络、最优化理论、 模糊数学、演化算法等各种方法与新思想引入到矢量量化中来，以期得到快速、 高效、性能好的矢量量化器，矢量量化研究进入了一个飞速的发展时期并且取得 了很多成果。 本课题就是在这种背景下确立的。这一课题既要求对图像压缩编码的理论有 一个清晰的了解。又涉及到图像压缩编码中的一些新技术和算法，具体有矢量量 化编码理论、遗传算法、蚁群算法和神经网络等。而且这一课题跨度很大，涉及 计算机软件与理论、信息与计算科学、信号与信息处理等专业知识。通过这一课 题的实施，对图像压缩编码的一些经典算法进行分析，提出了一些改进算法及新 算法，并进行了实验。本课题的确立和完成对图像压缩编码领域做出了一些有益 的探索。 1 2 矢量量化技术的研究现状 矢量量化的基本理论早在二十世纪六七十年代已有人关注，而在二十世纪八 十年代开始逐步完善起来。矢量量化是分组量化的一种，受到广泛注意和使用的 分组量化方法【8 1 是由j y h u a n g 和p m s e h u l t h e i s s 于1 9 6 3 年首先提出来的，他们指出 分组量化的实现方法。1 9 7 9 年，格尔肖在他在论文【5 】中详细阐述了分组量化的一 般性理论。而数据压缩中的多径搜索编码的三种方法，即码书编码、树型编码和 格型编码，于1 9 8 2 年在文献中f 6 1 进行了详细地评述。 1 9 8 0 年，f l ：l l i n d e ，b u z o 和g r a y 将标量量化的l l o y d m a x 算法1 6 】推广，发表了第 一个可行的矢量量化码书设计算法1 4 ：l b g 算法，将矢量量化技术推向研究高潮， 并推广应用，该文献已经成为矢量量化的经典文献，是矢量量化发展的基石。从 此，矢量量化技术的研究进入了一个全面高速的发展时期而国外一直处于领先地 位。在2 0 多年历程中，学者们在以下五方面对矢量量化技术展开研究： ( 1 ) 矢量量化器的研究：对基本矢量量化器复杂度大和比特率固定的缺点，开 发其它类型的矢量量化器； ( 2 ) 矢量量化码书设计算法研究：针对基本矢量量化器的l b g 码书设计算法容 易陷入局部极小、初始码书影响优化结果和计算量大的缺点。学者们引入 了神经网络、优化理论、模糊集合等技术，提出了各种各样的码书设计算 法： 第1 章前言 ( 3 ) 矢量量化码字搜索算法研究：在矢量量化编码场合中，针对基本矢量量化 器的穷尽搜索编码算法的计算量大和比特率固定的缺点提出各种各样的 快速码字搜索算法和变比特率码字搜索算法； “) 矢量量化码字索引分配算法研究：考虑到信道噪声将会在矢量量化解码端 引入额外失真，学者们开始研究码字索引分配算法以减少由于信道噪声引 起的失真； ( 5 ) 矢量量化技术的应用研究。 由于本论文的需要，下面分别详细阐述矢量量化器的研究现状及码书设计算 法研究现状。 1 2 1 矢量量化器研究现状 经过研究人员二十年多的努力，已经在最基本的矢量量化基础上演变出各种 各样的矢量量化的变种，以下阐述矢量量化器的变种的研究现状： ( 1 ) 约束矢量量化( c o n s t r a i n e dv q ) 基本的矢量量化器是无约束的矢量量化器，其主要缺点是复杂度大，在一些 码书大维数高的实际应用中无法发挥矢量量化的优越性。基于此，以下所提及的 文献对基本的矢量量化器附加了各种各样的约束条件，提出了各种各样以降低复 杂度为目标的约束矢量量化器。目前提出的主要算法有贪婪树生成算法【7 ，8 】、变长 的变速率树型矢量量化器【9 ，1 0 、分类分裂矢量量化( c l a s s i f i e ds p l i tv q ) 算法【1 1 ， 1 2 ，1 3 、差分矢量量化 1 4 ( d i f e r e n t i a lv q ) 、采用二维分裂法合并法的差分图像矢 量量化1 1 5 】、基于小波变换的矢量量化图像编码算法【1 6 ，1 7 ，18 】和球形矢量量化 ( s p h 甜c a lv q ) 的格型矢量量化1 1 9 ，2 0 ，2 1 1 的方法。 ( 2 ) 预测矢量量化( p r e d i c t i v ev q ) 它是有记忆的矢量量化器，其原理是先将量化电平通过预测滤波器，然后对 预测误差进行编码而不是对原信号直接编码，研究成果有成功地将一维预测v q 应 用于语音信号的压缩 2 2 1 、和两种二维预测v q 2 3 】( 即滑动块预测v q 和块树预测 v q ) ，并将它们应用于二维图像压缩。 ( 3 ) 有限状态矢量量化 2 4 ( f i n i t e s t a t ev q ) 它是一个开关矢量量化器，由编码器选择的量化器序列可以被译码器跟踪， 所以它可以看作带反馈计算的自适应矢量量化器，也是有记忆的矢量量化器。文 献 2 5 ，2 6 ，2 7 1 中对f s v q 作了改进、应用和深入的探讨。 ( 4 ) 自适应矢量量化 2 8 1 ( a d a p t i v ev q ) 此矢量量化器是目前各国学者的研究热门，它的码书不是固定的而是自适应 第1 章前言 于输入矢量，这类量化器主要应用于视频图像序列的压缩。文献1 2 9 提出了一种基 于内容可寻址记忆( c o n t e n ta d d r e s s a b l em e m o r y 。c a m ) 结构的自适应实时矢量量 化图像编码算法，文献【3 2 】提出基于记忆和预测机制的自适应矢量量化，最近文献 1 3 0 ，3 1 齐j 自适应矢量量化的码书设计和应用进行了详尽描述。 1 2 2 矢量量化码书设计算法研究现状 种有效和直观的矢量量化码书设计算法l b g 算法( 也叫g l a 算法) 【4 1 是由 l i n d e ，b u z o 和g r a y 于1 9 8 0 年首先提出来的。其特点为物理概论清晰、算法理论严 密及算法实现容易。但该算法有二个主要的缺点：( a ) 在每次迭代的最佳的划分阶 段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计算：( b ) 初 始码书的选择影响码书训练的收敛速度和最终码书的性能；( c ) 码书的自适应能力 不强。针对这些问题，学者们开始提出各种改进的算法，主要有以下方面： ( 1 ) l b g 改进算法 为了获得更好的初始码书，如文献 3 3 1 提出了一种改进的的初始化技术。除了 初始化技术的改进，对l b g 算法的其它改进方法有两大类：一是将快速码字搜索引 入到l b g 算法中以提高设计速度，此方法归入到码字搜索算法中加以叙述。二是 采用其它技术提高码书性能或加快设计速度，如文献1 3 4 1 6 f l e q u i t s 提出名叫成对最 近邻算法( p a i r w i s en e a r e s t n e i g h b o r ，p n m 的码书算法，明显减少了计算复杂性，但 最终得到的码书性能l e l b g 算法差；文献f 3 5 1 提出一种最大下降算法( m a x i m u m d e s c e n t ，m d ) ，同l b g 算法比较，提高了码书性能，减少了计算时间：文献1 3 6 1 提 出基于快速胞腔划分的改进分裂法矢量量化码书设计算法，减少了分裂法码书设 计中庞大的运算量；文献【3 7 】提出一种称为部分g l a 的码书设计算法。 ( 2 ) 基于神经网络的码书设计算法 近年来，神经网络己经成功地应用到矢量量化码书设计算法中。文献【3 8 】提出 了一种简单的学习矢量量化( l e a r n i n gv o ，l v q ) 。该算法得到的码书不如l b g 算法。 为了解决l v q 算法的码字欠利用问题，提出了各种改进竞争学习算：利用自组织 特征映射神经网络【6 4 1 ；频域敏感竞争学习算法【6 , 3 9 】f r e q u e n c y s e n s i t i v e c o m p e t i t i v el e a f i n g ，f s c l ) ；基于随机松弛思想的软竞争学习算法【4 0 l ( s o f t c o m p e t i t i v el e a m i n g , s c l ) ：失真均衡竞争学习算法f 4 1 1 ( o i s t o r t i o ne q u a l i z e d c o m p e t i t i v el e a r n i n g ，d e c l ) 及部分失真均衡竞争学习算法 4 2 ( p a r t i a ld i s t o r t i o n u n i f o r mc o m p e t i t i v el e a r n i n g ，p d u c l ) 。此外，文献【4 3 ，4 4 1 提出基于n e u r a l g a s 的码书设计算法。 ( 3 ) 基于全局优化技术的码书设计算法 第1 章前言 码书设计的目标是找n i ) l l 练矢量的最佳分类。学者们采用了各种各样的全局 优化技术f 4 5 ，4 6 ，4 7 ，4 8 ，4 9 ，5 0 1 进行码书设计以改善码书性能，但是这些算法的普遍缺 点是增加了计算时间。文献【5 1 】，1 5 2 1 ，【5 3 ，5 4 1 分别将模拟退火算法、随机松弛算法和 演化算法应用到矢量量化码书设计中，同时首先将禁止搜索( t a b us e a r c h ) 算法1 5 5 】 应用到码书设计，所有这些全局优化算法性能l l l b g 算法高。 ( 4 ) 基于模糊聚类理论的设计算法 上面各种矢量量化码书设计算法都是将每个训练矢量根据一定的准则分配给 单个聚类，而忽略了训练矢量属于其它聚类的可能性，导致算法局部最优或强烈 依赖于初始码书的选择。因此，学者们将模糊聚类理论 5 6 ，5 7 1 应用到码书设计算法 中。文献 5 8 1 提出模糊c 一均值( f u z z yc - m e a n s ，f c m ) 算法，性能比l b g 算法好， 计算量比l b g 大得多。近几年研究较多的模糊矢最量化( f u z z yv e c t o rq u a n t i z a t i o n , f v 算法1 5 9 1 将模糊逻辑引入到矢量量化的码书设计中，对初始码书依赖性小。 性能和f c m 相当，运算量小于f c m ，但相对于l b g 还是比较大。为此文献 6 0 1 1 6 1 】 提出了模糊k 一邻域算法( f f l ( n ) 及其改进算法，设计速度快码书性能高。除了上述 这四类算法外，还有其它码书设计方法，如路径跟踪算法1 6 2 1 和偏差缩减算法 6 3 l 等等 同时二十世纪九十年代。半导体技术和微电子工艺日臻成熟，d s p 技术已经广 泛地应用于各种领域，d s p 芯片的高速运行和并行处理能力为各种数据压缩算法提 供了理想的实现环境，各国学者也针对d s p 的结构特点对传统的矢量量化技术改 进，研究各种适合于硬件实现的矢量量化算法。 1 3 本课题的目的与意义 2 l 世纪，人类社会已进入信息时代。“信息爆炸”的结果要求人们解决如何对浩 如烟海的数据进行有效的压缩，以便以最少的代码表示信源所发出的信号，减少 数据占用的存储空间( 如数据库、多媒体影音文件、数字电视系统等等) 、传输时间 ( 如数据通信、遥测) 或占用带宽，也就是说要设法尽可能地压缩给定消息集合所占 用的空间域、时域和频域资源。 数据压缩是信源编码的目的和手段。从广义上讲，数据压缩就是减少分配给指 定消息集合或数据采样集合的信号空间大小。该信号空间可以是物理容积，也可 以是时间间隔或带宽。数据压缩的主要目的是为了降低码速率或减少存储空间。 矢量量化( v e c t o rq u a n t i z a t i o n ，v o ) 在量化时用输出给集合( 码书) 中最匹配的一 组输出值( 码字) 来代替一组输入采样值( 输入矢量) 。矢量量化的突出优点是解码算 法简单，压缩比高，因此它已经成为图像压缩编码的重要技术之一。矢量量化图 第1 章前言 像压缩技术的推广应用领域非常广，首先，矢量量化图像压缩技术可以用于卫星 遥感照片、航天飞机遥感图像的压缩编码，甚至可以应用到外星图像资料实时传 输系统和气象部门和图像传输系统中，从而推动航天事业的发展。其次，矢量量 化压缩技术在雷达图像处理、军用地图的存储与自动检索以及未来信息战争的图 像传输等方面的应用将提高军事信息处理效率从而推动军事科技现代化。此外， 数字电视技术和d v d 的视频压缩技术己经在世界范围内展开研究，矢量量化技术 高压缩比的特点将使它成为首选的编解码技术之一，从而推动多媒休产业的迅速 发展。 矢量量化技术的研究涉及多学科领域的理沦和技术，如信息论、编码理论、 通信原理、保密技术、信号处理、优化理论、模糊集合论、矩陈分析、神经网络、 小波变换、视觉模型拓扑学、随机概率理论、预测技术、模式识别等等。矢量量 化技术的研究将给这些理论和技术注入新鲜血液。因此。无论从理论角度还是从 应用角度来石，开展对矢量量化技术的研究，不但具有重要的学术意义，还有极 为重要的国防意义和经济意义 1 4 主要内容及创新 本课题对矢量量化码书设计算法进行了研究和探索，为了解决经典算法存在 的缺点和提高运行效率方面，本文引入了遗传算法、蚁群算法等算法对矢量量化 码书设计进行研究。本文的主要工作和创新在以下几个方面： ( 1 ) 在矢量量化压缩编码方面，提出了基于码书和基于训练序列的两种遗传矢量量 化算法，实验验证了这两种算法的合理性和有效性，同时比较了两种方法的实 验效果。 ( 2 ) 针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优，提出了一 种新的信息素更新方法和局部调整算法，即对属于不同性能聚类中心的训练矢 量之间增加不同的信息素增量以及采用模拟退火策略调整最不相似训练矢量， 实验结果表明改进的蚁群算法使峰值信噪比( p s n r ) 提高了0 1 1d b 。 ( 3 ) 综合考虑遗传算法和蚁群算法的优缺点，提出了一种基于遗传蚂蚁矢量量化图 像压缩编码方案，实验证明了该方案的合理性和有效性。 1 5 本文章节安排 第1 章，主要介绍了图像压缩中的矢量量化技术的研究背景、研究目的和意义、 国内外研究现状、本文的主要内容、创新和整篇文章的章节安排。 第2 章，主要对矢量量化编码技术进行了比较系统的介绍，包括基本原理、评价 第1 章前言 标准和矢量量化中的典型算法即l b g 算法。在对l b g 算法进行描述的同时，还对 该算法的优缺点进行了分析，并在此基础上提出了改进的设想。 第3 章，主要介绍了遗传算法的定义、特点及基本遗传算法的实现，在介绍了遗 传算法的相关知识的基础上根据遗传算法中染色体的不同选取方案，提出了基于 训练序列和基于码书的的码书设计算法。 第4 章，针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优，提 出了一种新的信息素更新方法和局部调整算法。综合考虑遗传算法和蚁群算法的 优缺点，提出了一种基于遗传蚂蚁矢量量化图像压缩编码方案。 第5 章，对本题研究的成果进行了总结，并对今后研究方向进行了展望。 第2 章矢量量化编码技术 第2 章矢量量化编码技术 本章对矢量量化技术进行了比较详细的介绍，重点描述了矢量量化的l b g 算 法，为本文提出的算法奠定基础。同时介绍了矢量量化技术的性能衡量指标。 2 1 矢量量化的基本原理 2 ，1 1 矢量量化的理论基础 矢量量化的理论基础是香农的速率一失真理论。1 9 4 8 年，香农定义了信道容 量，并证明只有码速率不超过信道容量，符号就能以任意小的差错概率在该信道 中传输。1 9 5 9 年，香农定义了速率一失真函数r ( d ) 并证明只有尺( d ) 不超过信道 容量就能保证接收端的失真不超过给定阀值d 的，在数学上，尺( d ) 定义为在给定 失真d 的条件下，系统所能够达到的最小码速率。对于幅值离散的信源，r ( d ) 定 义如下： r ( d ) - m i n p ( x ) p o x ) i o g ：( p ( y x ) q c o ) ( 2 1 ) jy 其中 q ( y ) - p ( x ) p ( y x )( 2 。2 ) 平均失真满足条件： p ( x ) p ( y x ) d ( x ，y ) d ( 2 3 ) 其中d ( x ，n 是失真测度，它表示输出采样值】，再现原始信源采样值x 所引入的 失真，p c r x ) 表示在已经发送x 的情况下接收到y 的概率。r ( d ) 的单位为比特 采样。同样，可以计算速率失真函数的逆函数d 假) ，称为失真一速率函数，其 含义为：在给定速率不超过r 的条件下，系统所能达到的最小失真。d 俾) 和尺( d ) 所给出的编码性能极限，适用于所有信源编码方法。d ( r ) 是在维数随k 趋向无穷 大时d ( r ) 的极限，即 d ( 月) 。 i r a q 僻) ( 2 4 ) 根据香农的这一理论，可以找到一个最小的信源速率使得系统发送端到接收 端的平均失真不超过给定的失真阀值，这正是数据压缩系统所要做的事情，因此 内格尔- t 1 9 7 1 年称香农的这理论为啮据压缩的数学基础”。从式( 2 4 ) 可知，利用 矢量量化，编码性能可能任意接近速率一失真函数，其方法是增加矢量维数k 。在 第2 章矢量量化编码技术 实际应用中速率一失真函数常常作为一个理论下界与实际编码速率相比较，分析 系统还有多大的改进余地。总之，速率一失真理论指出了矢量量化的优越性。不 过，速率一矢真理论是一个存在性定理而非构造性定理，因为它并没指明如何构 造矢量量化器。 2 1 2 矢量量化定义 基本矢量量化器【5 6 】可以定义为从k 维欧几里德空间r 到其一个有限子集c 的一个映射，即q ：r 一c ，其中c - y ，) ，2 ：，) ，l y i e r 称为码书，m 为码书 大小，该映射满足：q ( x l x r ) 一y ，其中z 一“，x 2 ，屯) 为r 中的七维矢量， y ，一0 ，。y 。，y 。) 为码书c 中的码字并满足 d o ，y ，) - m i n d ( x ，y j )( 2 - 5 ) 其中，a ( x ，y ，) 为输入矢量z 与码字_ ) ，之间的失真测度。每一个矢量z 都能在 码书c - y ，) ，2 ，y 。i y 。) 中找到其最近码字) ，- q ( x l x r ) 。输入矢量空间 通过量化器q 量化后，可以用划分s - s ，s ：，s 。) 来描述，其中s 是所有映射成 码字y 。的矢量的集合，即s 。- 仁i q o ) - y i 。这个空间墨，s ：，满足： 譬s s ( 2 6 ) 基本的矢量量化编码和解码过程如图2 1 所示。矢量量化编码器根据一定的失 真测度在码书中搜索出与输入矢量之间失真最小的码字，传输时仅传输该码字的 索引。矢量量化解码过程很简单，只要根据接收的码字索引在码书中查找该码宇， 并将它作为输入矢量的重构矢量。 图2 - 1 矢量量化编码和解码示意图 2 1 3 矢量量化的特点 矢量量化之所以能够压缩数据，是由于它能够去掉冗余度，而且它能有效地 第2 章矢量量化编码技术 利用矢量中各分量间的4 种相力关联的性质：线性依赖性、非线性依赖性、概率密 度函数的形状以及矢量维数。而标量量化只能够用线性依赖性和概率密度函数的 形状来消除冗余度。所以，一个k 维最佳矢量量化器的性能总是优于七个最佳标量 量化器。 基本的矢量量化编码器需要使用由个七维矢量组成的码书。对某个输入矢 量进行编码时，在码书搜索与该输入矢量之问失真最小的码字，将其对应的标号( 需 要l o g ，n 比特) 发送到接收端。接收端也具备相同的码书，解码时根据接收的标号 在码书中找到对应的码字。如果每个采样有肘个电平，则七维输入矢量空间大小 为肘k ，但码书中仅有个码字，所以最大压缩比可达，- m 。采用标量量化 时，每个采样需要l o g ，m 比特，而用矢量量化时，每个采样只需要( 1 0 9 ，) k 比 特。 在相同的速率下，矢量量化的失真明显比标量量化的失真小：而在相同的失 真条件下，矢量量化所需要的码速率比标量量化所需要码速率低得多。但是，由 于矢量量化的复杂度随矢量维数据成指数式增加，所以矢量量化的复杂度比标量 量化的复杂度高。 2 1 4 矢量量化的相关概念 1 失真测度( d i s t o r t i o nm e a s u r e ) 失真测度用来衡量一个矢量用其它矢量重构而造成的失真，它是一个非负量。 下面介绍文献中最常见的几种失真测度。这里设工，y 是 维矢量。 ( i ) 平方误差测度：矢量量化最常用的失真测度，其定义如下： d ( 圳) - ：o 咄) 2 ( 2 ) l 。失真测度：比较常用的失真测度，满足三角不等式，其定义如下： a ( x ，y ) - ( ：“- y i ) 9 ) “ ( 3 ) 工。失真测度： d ( x ，y ) 。m a x ( 1 一) ，。d ( 4 ) 加权平方误差测度：如果w ，是非负的加权值，则该测度定义如下： d ( x ，) ，) ：= ：m “一y 。) 2 ( 5 ) i t a k u r a s a i t o 失真测度：由i t a k u r a 和s a i t o 针对语音压缩系统提出的，若对于每一 个输入矢量r ，r o ) 是t x t 正定对称矩阵，则该测度可表示为： 第2 章矢量量化编码技术 a ( x ，y ) l ( 工一_ ) ) 7 r ( 工x 工一y ) 2 编码速率( e n c o d i n gr a t e ) 矢量量化器的编码速率定义为每个输入采样所需要的平均比特数。设码书大 小为j v ，矢量维数为k 。对于基本的矢量量化器，由于每个码字索引所占的比特 数为l o g ：n ，则每一维分量( 采样) 所占的比特数即编码速率为，。o o g ：n ) k 。 3 复杂度( c o m p l e x i t y ) 与标量量化相比，矢量量化的主要缺点是复杂度大，而且复杂度随维数的增 大成指数式增加，这是实现高维矢量量化器的主要障碍。无论从硬件考虑还是从 软件考虑，复杂度有两种：时间复杂度和空间复杂度。时间复杂度定义为量化每个 输入矢量所需要的计算量，包括加减法、乘除法和比较等等。空间复杂度定义为 量化器所需的存储容量。 4 编码失真( e n c o d i n gd i s t o r t i o n ) 均方误差( m e a ns q u a r e de r r o r , m s e ) 常常用来描述矢量量化编码失真。此外， 信噪比( s i g n a ln o i s er a t i o ，s n r ) 和峰值信噪比( p e a ks i g n a ln o i s er a t i o ，p s n r ) 也常 用来描述矢量量化编码失真。假如一幅j 】l f 的l 灰度图像，原始图像像素为白， 而重构图像像素为y d ，0 s i m l o ，n 一1 ，则m s e ，s n r 和p s n r 可分别定 兰!m竺-1垒n型-i!垒二生12mse ( 2 乃 鱼竺兰型! _ 兰二 ( 2 乃 snr=10logjo磊n-1 n - i 2 ， p s n r - 1 0 1 0 9 l 。二m s e ( 2 - 9 ) 上述概念经常作为矢量量化器设计和评价的客观依据，在本文中主要考虑平 均信息率，和峰值信噪比p s n r 。 2 2 性能衡量指标 矢量量化应用于图像压缩所采用的性能衡量指标般来说包括客观失真测度和 主观度指标两类。在客观性能指标里经常用均方误差( m s ex 参照公式2 7 ) 来描述 矢量量化编码失真。信噪比s n r ( 参照公式2 8 ) 作为信号处中最通用的性能指标也 常用来描述矢量量化器的编码失真，另外，在图像编码中由于图像像索的幅度的 均值一般都大于零，因此我们用以在计算信噪比时用最大值来代替均方根值，得 第2 章矢量量化编码技术 到另一种常用的信号质量衡量指标峰值信嗓比( p s n r x 参照公式2 9 ) 一般来说，一个理想的度量一应是某个单一数值，它应该通用、可靠、易求 并利于判断分析。但没有一种度量方法