（计算机应用技术专业论文）图像矢量量化编码技术研究.pdf

嶷州人学颤 学位论文l 笙| 像矢量量化编码技术研究 摘要 本文主要研究和探索遗传算法和并行算法在图象矢量量化编码中的应用。遗 传算法的引入解决了l b g 等经典算法所存在的缺点，同时提高了运行效率。在 小波变换和矢量量化编码相结合的图象压缩编码中，采用遗传算法和并行计算提 高了图象的压缩比和质量，以及运行效率。主要研究内容包括以下三个方面： ( 1 ) 提出了两种基于遗传算法的图象矢量量化编码算法 矢量量化的基本问题是码书设计和码字搜索。码书设计决定了压缩性能，是 矢量量化的关键。传统的l b g 和树结构等码书设计算法，因依赖初始码书或聚类 种子，以及码书的自适应能力不强等原因，不易逼近全局最优解。遗传算法作为 一种新的全局优化搜索算法，具有群体多样性、简单通用、鲁棒性强、适于并行 处理等显著特点，得到了广泛应用。它能够在搜索过程中自动获取和积累有关搜 索空间的知识，并自适应控制搜索过程以达到全局最优解，可以弥补传统码书设 计算法的不足。本文根据遗传算法中染色体的不同选取方案，提出了基于训练序 列和基于码书的码书设计算法，实验证明这两种算法都优于传统码书设计算法。 ( 2 ) 提出了基于d w t 和遗传算法的图象矢量量化编码算法 图像小波多分辨率分解很好地模仿了人类视觉系统( h u m a nv i s u a ls y s t e m ) 处理图像信号的过程。小波图像系数在空问位置和内容上均存在相关性，采f t j 矢 帚量化编码技术叫以充分利用小波图像系数之问的相关性，因而可在较小的失真 下得到较高的压缩比。根据不同图像在小波变换后欠量树的相似性特点，码书 h 形成，备种情况的分布数据都可以使用此码书，极大地节省了每次i j l i 练码。讳的 设i f 时间。小波变换与矢量量化技术年只结合已成为。种有效的图象压缩编码方 案。本文将遗传算法应用于小波变换与矢量量化技术相结合| 勺图象压缩编码算 法，在相同握缩比下改善了图象的质量。 ( 3 ) 基于d w t 和遗传算法的矢量量化编码算法的爿：行计算方砥研究 对17 通用的压缩方法，可以采j j 扩大训练集的范围柬获得缆讨意义j ：的码 书。但随着训练图像数的增j | l ，计算量也必然增加。我们可以采用并行算法来提 高计算速度。另外，小波变换后在h 【，l h 和h h 三个不同了带进行独立的矢量 量化，以及矢量量化中遗传算法的并行性，都有利于采| j 并行计算。本文设计了 。种并行算法并在基j p v m 的帆群环境下实现了该算法。实验证实了算汪、的 介删，陛和钉效性。 关键词：矢量量化；图像编码；遗传算法：小波变欹；并行算法 q ，吲法分类号：t p 3 9 1文献标以码：a 图像矢量厦化编码技术倒f 究 a b s t r a c t i nt h i st h e s i s ，w em a k es o m er e s e a r c h e so ng e n e t i ca n dp a r a l l e la l g o r i t h m si n a p p l i c a t i o no fi m a g ev e c t o rq u a n t i z a t i o nc o d i n g b yi n t r o d u c i n gg e n e t i ca l g o r i t h m ，w e s o l v et h ed e f i c i e n c ye x i s t i n gi nl b gc l a s s i c a la l g o r i t h m sa n di m p r o v ee f f i c i e n c yo f t h ea l g o r i t h m s i nt h ep r o c e s so fi m a g ec o m p r e s s i o nc o d i n gw h i c hi sc o m b i n e db y w a v e l e tt r a n s f o r mt e c h n i q u ea n dv e c t o rq u a n t i z a t i o n ，g e n e t i ca l g o r i t h ma n dp a r a l l e l c o m p u t i n ga r ea d o p t e dt oi n c r e a s e t h ec o m p r e s s i o nr a t i oa n dq u a l i t yo fi m a g e s ，a s w e l la st h er u n n i n ge f f i c e n c y t h i st h e s i sc o n s i s t so f t h r e ep a r t sm e n t i o n e db e l o w ( 1 ) w ep r e s e n tt w ok i n d so fc o d i n ga l g o r i t h m so nv e c t o rq u a n t i z a t i o nb a s e do n g e n e t i ca l g o r i t h m 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 eb o o ka n d s e a r c h i n g f o r c o d e w o r d d e s i g n i n g c o d e b o o kw h i c hd e t e r m i n e s c o m p r e s s i v e p e r f o r m a n c ei sv i t a lt ov 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 g c o d e b o o ks u c ha sl b ga l g o r i t h mm i 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 l c o d e b o o ko r a g g r e g a t e d c l a s s s 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 f c o d c b o o ki sv e r yw e a k ，t h e r e f o r e ，i ti 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 l o p t i m i z a t i o ns e a r c h i n ga 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 e u 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 tf 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 m c 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 d t o s e a r c h i n gs p a c ed u r i n g t h es e a r c h i n gp r o c e s s ，a n dc o n t r o l s e l f - a d a p t i v e l y t h e s f l a r c h i n gp r o c e s st og e tt 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 y o 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 na c c o r d i n gt ot h ed i f f e r e n tc o d i n g d e s i g no nc h r o m o s o m ei nt h eg e n e t i ca l 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 n o 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 ta n dv e c t o rq u a n t i z a t i o nb a s e do n c o 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 ( 2 ) w ep r e s e n tac o d i n ga l g o r i t h mo ni m a g ev e c t o rq u a n t i z a t i o nb a s e do l ld w t a n dg e n e t i ca l g o r i t h m t h ed e c o m p o s i t i o no fm a g ew a v e l e t sm u l t i r e s o l u t i o ns i m u l a t ew e l lt i l ep r o c e s s w h e nh u m a nv i s u a ls y t e mp r o c e s si m a g es i g n a l t h ec o e 衔c i e n t so fw a v e l e ti m a g e c o r r e l a t et ot h e i r s p a c i a lp o s i t i o n s a n d c o n t e n t s ，a c c o r d i n g l ya d o p t i n g v e c t or q u a n t i z a t i o nc o d i n gt e c h n i q u ec a nn o to n l ym a k el u l lu s eo ft h ec o r r e l a t i o no l + c o c t f i c i e n t so fw a v e l e ti m a g e 、b u ta l s og e th i g hc o m p r e s s i b i l i t yw i t hl i t t l ed i s t o r t i o n a c c o r d i n gt ot h et r a i t so f 、t h es i m i l a r i t yo fv e c t o rt r e e sa f t e rw a v e l e tt r a n s f o r mo f d i f t e r e n ti m a g e s ，o n c et h ec o d e b n o kc o l l i e si n t ob e i n g ，d i s t r i b u t i n gd a t ai ne a c hc a s e c a l l 1 1 s ct h i sb o o k w h i c hg r e a t l y s a v et h ed e s i g nt i m eo fc a c ht r a i n i n go f c o d e b o o k a p p a r e n t l y ，w a v e l e tt r a n s f o r mc o m b i n e dw i t hv e c t o rq u a n t i z a t i o nw i l lb ct i l l 譬i 州 学硕l 学位论文蹦像矢量量化编码技术研究 e f f e c t i v ec o d i n gm e t h o d t h i st h e s i sa d o p t san e ws t r a t e g yb yg e n e t i ca l g o r i t h mw i t h t h ea b o v em e n t i o n e da l g o r i t h mw h i c hi m p r o v e st h e q u a l i t yo fi m a g e i ns a m e c o m p r e s s i o nr m i o n ， ( 3 ) w em a k er e s e a r c ho np a r a l l e lc o m p u t i n go fv e c t o rq u a n t i z a t i o nb a s e do n d w ta n dg e n e t i ca l g o r i t h m a sf o ru n i v e r s a lc o m p r e s s i n gm e t h o d ，s ow ec a ne n l a r g et h es e e 。p eo ft r a i n i n g l i s t s ，a c c o r d i n g l yc o d e b o o kf o rs t a t i s t i c a lp u r p o s ei sa c q u i r e d w i t ht h ei n c r e a s eo f t r a i n i n gi m a g e s ，t h ec o m p u t i n gw o r kw i l lb eb o u n dt oi n c r e a s e w ea d o p tt h ep a r a l l e l a l g o r i t h m t oi n c r e a s et h e c o m p u t e rs p e e d w h i l ea f t e rw a v e l e t t r a n s f o r m ， i n d e p e n d e n tv e c t o rq u a n t i z a t i o np r o c e s s i n gi nt h r e ed i f f e r e n tf i l i a l ez o n eh l l ha n d h t i ，a n dp a r a l l e l i t yo fg e n e t i ca l g o r i t h mi nv e c t o rq u a n t i z a t i o nw i l lb eb e n e f i c i a lt o p a r a l l e lc o m p u t i n g ，a c c o r d i n g l y g o o dc o d e b o o kq u a l i t ya n de f f i c i e n c yw i l l b e a c q u i r e d w ed e s i g nt h ep a r a l l e la l g o r i t h mi nt h i sp a p e ra n dm a k ee x p e r i m e n t su n d e r c o m p u t e rc l u s t e r t h ee n v i r o n m e n tb a s e do i l p v m ，t h ee x p e r i m e n t sp r o v et h e r a t i o n a l i t ya n dv a l i d i t yo ft h ea l g o r i t h m k e y w o r d s ：v e c t o rq u a n t i z a t i o n ，i m a g ec o d i n g ，g e n e t i ca l g o d t h m ，w a v e l e t t r a n s f o m ，p a r a l l e la l g o r i t h m 直州人学坝i 学位论文 i 警l 像矢量量化编码技术研究 v o d w t g a h v s l b g d s p p v m m p i p s n r m s e s n r d p c m s t f t e z w s a q s i m d m i m d 简写符号对照间与付丐期照 v e c t o rq u a n t i z a t i o n d i s c r e t ew a v e l e tt r a n s f o r i l l g e n e t i ca l g o r i t h m s l l u m a nv i s u a ls y s t e m l i n d eb u z og r a y d i g i t a ls i g n a lp r o c e s s i n g p a r a l l e lv i r t u a lm a c h i n e m e s s a g ep a s s i n gi n t e r p a c e p e a ks i g n a lt on o i s er a t i o m e a ns q u a r e de r r o r s i g n a ln o i s er a t i o d i f k r e n t i a lp u l s ec o d em o d u l a t i o n s h o r t i i m ef o u r i e rt r a n s f o r n q e m b e d d e dz e r o t r e e sw a v e l e t s u c c e s s i v ea p p r o x i m a t i o nq u a n t i z a t i o n s i n g l ei n s t r u c t i o nm u l t i p l ed a t a m u l t i p l ei n s t r u c t i o nm u l t i p l ed a t a v 表 盘州大学颂f 。学位论文 第1 章前言 当前，随着人类科学技术的乜速发展，信息时代已经到来，与此紧密相关的 数据压缩技术一直得到广泛的重视。在经过长期的世界范围内的研究与探索之 后，很多有效的数据压缩技术已经成功应用于实际的数据存储与数据传输系统 中。图象矢量量化具有解码算法简单，压缩比高等特点，已经成为图像压缩编码 的重要技术之。 本章主要介绍图像压缩中的矢量量化技术的研究背景、研究现状、研究f | 的 和意义。并介绍本文所研究的主要内容、创新，及章节安排。 1 1 研究背景 人类社会已经进入了信息时代，建立在计算机技术和通信技术卜的信息高速 公路使我们能更新、更快、更准确地掌握各种信息。 图像信源由于其具有非常丰富的信息量丽成为传递信息的重要媒介。我们“ 常所获取的信息有百分之七十以上来自于视觉，可以说图像正成为信息高速公路 上一种重要的媒体。数据量大是数据图像的一个显著特点，例如：按c c t r6 0 l 标准对常规电视信号进行每秒2 5 帧，每帧分辨率为7 2 0 5 7 6 ，l ，：u ：v 为4 ：2 ：2 每个分量8 b i t 的格式进行数字化，则其总数码率可达1 6 6 m b s 。这给数字图像的 存储、传输带来了极大的困难，因此必须进行压缩以减少数据量。 ；= = l 前数据图像 压缩技术已成为信息高速公路、高清晰度电视( h d t v ) 、可视电话、会议 也视、 多媒体通信等技术的关键，住航字遥感、生物医学工程等领域也超着 常重要的 作用。 在近几十年，数字系统由于其实现的低费用，易于规划以及较小的失真的优 点，已经广泛得到应用。存现实世界中，因为大多数信号均是连续的波形( 时问 和幅值f ：均连续) ，所以需要把这些信号转化为适合数字处理的离散信号( 时问 和幅值上均离散) 。n y q u i s t 采样定理证明了在满足一定条件下连续时洲信号转 化为离散时删信号不会产生失真。但是连续幅值转化为离散幅值的量化操作必将 产：生失真j 。凶此有损量化| 、u j 题，广义| - 说是信源编码，儿乎出现在每个使刖数 字系统的场合。为了在通信通道进行传输或便于存储，需要采用相对低的码率表 示模拟样本序列的数据压缩系统。根据香农率失真理论1 27 i ，欠嚣量化( v q ) 能 获得比其它基】：标景旨化的编码力法更好的压缩性能，矧此它作为一种高效的数 据址缩方法，近年来已经广泛地用f i 吾音、图像雎缩和模式识别等领域。 在二：f - 世纪六h 代初期乖】中期，出现了最早的欠量量化思想， i u a n g 年u s c h u l t h e i s s 提m 最早的分组量化的基本j 史现方法【4 8 l 。直到1 9 8 0 年由i , i n d e ，b u z o 和( r a y 将聚类算法引入到矢量量化器没计中，提出来一种著名的矢量量化码f i 砹训算法，即l b g 兑法| ) 州( 义称( j i a 算法) ，其文献已经成为欠最量化的经典 文献，足久鞋鞋化技术发腱的基石。鼬后，现代的久肇：量化研究得到了fl 箍泛 幽像矢壁量化编码技术研究 的关注。各国学者以l b g 算法为基础，针对矢量量化器的特点，将神经网络、 最优化理论、模糊数学、演化算法等各种方法与新思想引入到矢量量化中来，以 期得到快速、高效、性能好的矢量量化器，矢量量化研究进入了一个飞速的发展 时期并且取得了很多成果。 本课题就是在这种背景f 确立的。这一课题既要求对图像压缩编码的理论 有一个清晰的了解，又涉及到图像压缩编码中的一些新技术和算法，具体有矢量 量化编码理论、遗传算法、小波变换和子带压缩编码理论、并行计算及程序设计 等。而且这一课题跨度很大，涉及计算机软件与理论、信息与计算科学、信号与 信息处理等专业知识。通过这一课题的实施，对图像压缩编码的一些经典算法进 行分析，提出了一些改进算法及新算法，并进行了实验。本课题的确立和完成对 图像压缩编码领域做出了一些有益的探索。 1 2 矢量量化技术的研究现状 矢量量化的基本理论早在二十雌纪六七十年代已有人关注，而在二十世纪八 十年代开始逐步完善起来。矢量量化是分组量化的一种，受到广泛注意和使用的 分组量化方法【4 8 1 是由j y h u a n g 和p m s c h u l t h e i s s 于1 9 6 3 年首先提出来的，他 们指出分组量化的实现方法。1 9 7 9 年，格尔肖在他在论文r ”j 中详细阐述了分组 量化的一般性理论。而数据压缩的一崭新的分组量化方法多径搜索编鸱的三 种方法，即码口编码、树型编码和格型编码。于1 9 8 2 年在文献中p7 j 进行了详细 地评述。 1 9 8 0 年，由l i n d e ，b u z o 和g r a y 将标量量化的l l o y d m a x 算法1 6 6 】推广，发 表r 第一个可行的矢量量化码书设计算法1 5 叫：l b g 算法将矢量量化技术摊向研 究高潮，并推广应用，该文献已经成为矢量量化的经典文献，是矢量量化发展的 基石。从此，矢量量化技术的研究进入了一个全面高速的发展时期，而国外一直 处于领先地位。在2 0 多年历程中，学者们在以下五方面对矢量量化技术展开研 究： ( 1 ) 矢量量化器的研究：对基本矢量量化器复杂度大和比特牢固定的缺点 丌发其它类型的矢量量化器： ( 2 ) 矢量量化码书设计算法研究：针对基本矢量量化器的【，b g 码书设计算 法容易陷入局部极小、初始码书影响优化结果和计算量大的缺点，学者 们引入j ，神经网络、优化理论、模糊集合等技术，提出了各种各样的码 眵蹬计算法； ( 3 ) 矢最餐化码字搜索算法研究：在矢量量化编码场合中，针对基本矢量 量化器的穷尽搜索编码算法的计算量大和比特率蹦定的缺点，提出备种 各样的快速码字搜索算法利变化特率码字搜索算法： ( 4 ) 矢量量化码宁索引分配算法研究：考虑到信道噪声将会在欠肇肇化解 码端引入额外失真，学者们”始研究码字索引分配算法以减少l “_ ) 二信道 嗓声0 i 起的失真。 贵州人孝碗l j 学似论文 ( 5 ) 矢量量化技术的应用研究。 山于本论文的需要，下面分别详细阐述矢量量化器的研究现状及码- 棒设计算 法研究现状。 1 2 1矢量量化器研究现状 经过研究人员二十年多的努力，已经侄最基本的矢量量化基础上演变出各种 各样的矢量量化的变种，以下阐述矢量量化器的变种的研究现状： ( 1 ) 约束矢量量化( c o n s t r a i n e dv q ) 基本的矢量量化器是无约束的矢量量化器，其主要缺点是复杂度大，在一砦 码书大维数高的实际应用中无法发挥矢量量化的优越性。摹于此，以下所提及的 文献对基本的矢量量化器附加了各种各样的约束条件，提出了各种各样以降低复 杂度为目标的约束矢量量化器。目前提出的主要算法有贪婪树生成算法【2 0 1 ”l 、变 长的变速率树型矢量量化器阿”l 、分类分裂矢量量化( c l a s s i f i e ds p l i tv q ) 算法 6 t , 2 - 8 邡1 、差分矢量量化【5 4 1 ( d i f f e r e n t i a lv q ) 、采用二维分裂法合并法的差分图像 矢量量化 7 9 l 、基于小波变换的矢量量化图像编码算法 8 2 , 8 3 , 7 4 1 和球形欠量量化 ( s p h e r i c a lv q ) 的格型矢量量化1 2 4 j ”j 的方法。 ( 2 ) 预测矢量量化( p r e d i c t i v ev q ) 它是有记忆的矢量量化器，其原理是先将量化电平通过预测滤波器，然后对 预测误差进行编码而不是对原信号直接编码，研究成果有成功地将维预测v q 膨用于语音信号的压缩f ”1 、和两种二维预测v q f ”t ( 印滑动块预测v q 和块树预 测v q ) ，并将它们应用于二维图像压缩。 ( 3 ) 有限状态矢量量化剐( f i n i t e s t a t ev q ) 它是一个开关矢量量化器，由编码器选择的量化器序列可以被译码器跟踪， 所以它可以看作带反馈计算的自适应矢量量化器，也是有记忆的矢量量化器。文 献阻6 0 8 4 1 中对f s v q 作了改进、应用和深入的探讨。 ( 4 ) t h 适应矢量量化m m ( a d a p t i v e v q ) 此矢量量化器是目前各国学者的研究热门，它的码书不是固定的而是自适应 十输入欠景，这类量化器主要应用于视频图像序列的压缩。文献1 7 2 1 提出了种基 于内容可寻址也 乙( 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 ) 结构的自适应突时矢 量量化图像编码算法，文献【1 6 1 提出基于记忆和预测机制的臼适应矢量量化，最近 文献l _ ”川对自适应矢量量化的码书设汁和应用进彳亍了详尽描述。 1 2 2 矢量量化码书设计算法研究现状 种有效和直观的矢量量化码书砹算法一l b g 算法( 也l i t ig l a 算法) 是由i , i n d e 、b u z o 和g r a y 于1 9 8 0 年苗。先提出来的。其特点为物l 警概论清晰、 算法i 哩论严密及算法实现容易。但陔算法有二个主要的缺点：( a ) 在每次迭代的 最佳的划分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空f l , l _ 卡t 繁琐 的刊算：( h ) 幸j j 始码书的选择影响码忙洲练的收敛速度和最终码书的性能：c ) 码 i 笙| 像矢量量化编码技术研究 书的自适应能力f ：强。针对这些问题，学者们丌始提出各种改进的算法，主要有 以下方面： ( 1 ) l b g 改进算法 为了获得更好的初始码书，如文献p o l 提出了一种改进的的初始化技术。除了 初始化技术的改进，对l b g 算法的其它改进方法有两大类：是将快速码字搜 索引入到l b g 算法中以提高设讨速度，此方法归入到码字搜索算法中加以叙述。 二是采用其它技术提高码书性能或加快设计速度，如文献”u j 中e q u i t s 提出名l i t f 成对最近邻算法( p a i r w i s e n e a r e s t n e i g h b o r ，p n n ) 的码书算法，明显减少r 计算 复杂性，但最终得到的码书性能比l b g 算法差；文献p l 提出一种最大卜降算法 ( m a x i m u md e s c e n t ，m d ) ，同l b g 算法比较，提高了码书性能，减少了计算时 问：文献1 5 1 提出基于快速胞腔划分的改进分裂法矢量量化码书设计算法，减少了 分裂法码书设计中庞大的运算量：文献提出一种称为部分g i a 的码书设计算 法。 ( 2 ) 基f 神经网络的码书设计算法 近年来，神经网络已经成功地应用到矢量量化码书设计算法中。文献1 5 叫提出 厂一种简单的学习矢量量化( l e a r n i n gv e ，l v q ) 。该算法得到的码书 i 如l b g 算法。为了解决l v q 算法的码字欠利用问题，提出了各种改进竞争学习算法： 利用自组织特征映射神经网络1 58 】；频域敏感竞争学习算法i ”0 l ( f r e q u e n c y s e n s i t i v ec o m p e t i t i v el e a r i n g ，f s c l ) ；基于随机松弛思想的软竞争学 刊算法恻( s o f tc o m p e t i t i v el e a r n i n g 、s c i ) ；失真均衡竞争学习算法( d i s t o r t i o n e q u a l i z e dc o m p e t i t i v el e a r n i n g ，d e c l ) 及部分失真均衡竞争学习算法p l ( p a r t i a l d i s t o r t i o nu n i t b r mc o m p e t i t i v el e a r n i n g ，p d u c ) ：此外，文献i ，、 “提出基于 n e u r a l 一( j a s 的码书设计算法。 ( 3 ) 基于全局优化技术的码书设计算法 妈书设汁的目标是找到训练矢量的最佳分类。学者们采用了各种各样的全局 优化技术1 4 4 1 4 2 a 4 , 6 7 , 6 9 1 进行码书设计以改善码书性能，但是这些算法的普遍缺点 足增加了引算时问。文献i ”j s c , i1 4 5 , 3 5 1 分别将模拟退火算法、随机松弛算u a t i i , 7 4 化 算法应用到矢量量化码书设计中，i 司时首先将禁止搜索( t a b us e a r c h ) 算法 应用到码书改计，所有这些全局优化算法性能比l b g 算法高。 ( 4 ) 基于模糊聚类理论的设计算法 f 面各种矢量量化码书设计算法都是将每个训练矢量根据定的准则分配 给单个聚类，而忽略j i ) i i 练欠最属于其它聚类的可能性，导致算法崩郎最优或强 烈依赖于初始码书的选择。凶此，学者们将模糊聚类理论 4 2 3 l 应f h 到码书设计算 法k 义献f 3 0 lc l 提出模糊f 一均值( 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 r q u a n t i z a t i o n ，l ：v q ) 算法1 2 纠将模糊逻辑引入到矢量量化的码书设计中，对初始鹳 书依赖性小，性能干【if c m 相当，运算量小于f c m ，但相对于l b g 还是比较大。 为此艾献j 提模糊女一领域算法( f f k n ) 及其改进算法，设i t 迷度快，码二话 凌州人掌硕f j 学位论文 性能扁。 除了上述这四类算法外，还有其它码书设计方法，如路径跟踪算法i ”峙h 偏差 缩减算法 6 2 j 等等。 同时二十世纪九十年代，半导体技术和微电子工艺同臻成熟，d s p 技术已经 广泛地应用于各种领域，d s p 芯片的高速运行和并行处理能力为各种数据压缩算 法提供了理想的实现环境，各国学者也针对d s p 的结构特点对传统的矢量量化 技术改进，研究各种适合于硬件实现的矢量量化算法。 1 3 本课题的目的与意义 2 i 世纪，人类社会已进入信息时代。“信息爆炸”的结果要求人们解决如何 埘浩如烟海的数据进行有效的压缩，以便以最少的代码表示信源所发出的信号， 减少数据占用的存储空刚( 如数据库、多媒体影音文件、数字电视系统等等) 、 传输时间( 如数据通信、遥测) 或占用带宽，也就是说要设法尽可能地压缩给定 消息集合所占用的卒j 可域、时域和频域资源。 数据压缩是信源编码的目的和手段。从广义上讲，数据压缩就是减少分配给 指定消息集合或数据采样集合的信号空间大小。该信号空间可以是物理容积，也 - i j 以是时阊问隔或带宽。数据压缩的主要目的是为了降低码速率或减少存储空 州。 矢量量化( v e c t o rq u a n t i z a t i o n ，v q ) 在量化时用输出给集合( 码书) 中最匹 配的组输出值( 码字) 来代替一组输入采样值( 输入矢量) 。矢量量化的突出 优点是解码算法简单，压缩比高，因此它已经成为图像压缩编码的重要技术之。 吞量量化图像压缩技术的推广应用领域非常广，首先，矢量量化图像压缩技术可 以用j 二卫星遥感照片、航天飞机遥感图像的压缩编码，甚至可以应用到外星图像 资料实时传输系统和气象部门和图像传输系统中，从而推动航天事业的发展。其 次，矢量量化压缩技术在雷达图像处理、军用地图的1 竽储与自动检索以及末来信 息战争的图像传输等方面的应川将提高军事信息处理效率从而推动军事科技现 代化。此外，数字电视技术# f i i ) v d 的视频压缩技术已经在世界范围内展丌- 研究， 矢量量化技术高压缩比的特点将使它成为首选的编解码技术之一，从而推动多 媒体产业的迅速发展。 矢量量化技术的研究涉及多学科领域的理论和技术，如信息论、编码理论、 通信原理、保密技术、信号处理、优化理论、模糊集合论、矩陈分析、神经恻络、 小波变换、视觉模型拓扑学、随机概率理论、预测技术、模式谚l 别等等。矢量量 化技术的研究将给这些理论和技术注入新鲜血液。因此，无论从理论角度还是从 应用角度来看，丌展对矢量量化技术的研究，不但具有重要的学术意义，还有极 为蓖要的围防意义和经济意义。 幽像失量量化编码技术研究 1 4 主要内容及创新 本课题对矢量量化码书设计算法进行了研究和探索，为了解决经典算法存在 的缺点和提高运行效率方面，本文引入了遗传算法、小波变换和并行程序设计等 技术对矢量量化编码技术进行研究。本文的主要工作和创新在以= 几个方面： ( 1 ) 在矢量量化压缩编码方面，提出了基于码书和基于目t l 练序列的两种遗 传矢量量化算法，实验验证了这两种算法的合理性和有效性，同时比较了两种方 法的实验效果。 ( 2 ) 在矢量量化和小波变换压缩编码相结合方面，提出了一种基于小波变 换的遗传矢量量化图象压缩编码方案，实验证明了该方案的合理性和有效性。 ( 3 ) 并行化方面，对于通用的压缩方法，可以采用扩大训练集的范围来获 得统计意义上的码书。但随着训练图像数的增加，计算量也必然增加。我们可以 采用并行算法来提高计算速度。另外，小波变换后在h i 。，l h 和h h 三个不同子带 进行独立的矢量量化，以及矢最量化中遗传算法的并行性，都有利于采用并行计 算。本文设计了一种并行算法，并在基于p v m 的机群环境下实现了该算法。实 验证实了算法的合理性和有效性。 1 5 本文章节安排 第l 章，主要介绍了图像压缩中的矢量量化技术的研究背景、研究目的和意 义、周内外研究现状、本文的主要内容、刨新和整篇文章的章节安排。 第2 章，主要对矢量量化编码技术进行了比较系统的介绍，包括基本原理、 评价标准和矢量量化中的典型算法即l b g 算法。在对l b g 算法进行描述的同时， 还对陔算法的优缺点进行了分析，并在此基础上提出j ，改进的没想。 第3 章，主要介绍了遗传算法的定义、特点及基木遗传算法的实现，在介绍 了遗传算法的相关知识的基础l 二，根据遗传算法中染色体的不同选取方案，提出 了基于训练序列和基于码书的的码书设计算法。 第4 章，对矢量量化和小波变换相结合的图象压缩编码技术进行了研究。提 出了，一种基于小波变换和遗传算法的矢量量化编码算法。 第5 章本章在介绍了并行计算的相关知识的基础上，对欠最量化和小波变 换相结合的图象压缩编码技术，设计了一种并行算泫。并存基于p v m 的机群环 境卜实现了该算法。实验证实了算法的合珲性和有效性。 第6 章，对本课题研究的成果进行了总结，并埘今后研究方向进行了展望： 贵州 学坝i ：学位论文 第2 章矢量量化编码技术 本章对矢量量化技术进行了比较详细的介绍，重点描述r 矢量量化的l b g 算法，为本文提出的算法奠定基础。同时介绍了矢量量化技术的性能衡量指标。 2 1矢量量化的基本原理 2 1 1 矢量量化的理论基础 矢量量化的理论基础是香农的速率一失真理论。1 9 4 8 年，香农定义了信道容 量，并证明只有码速率不超过信道容量，符号就能以任意小的差错概率在该信道 中传输。1 9 5 9 年，香农定义了速率一失真函数r ( d ) 。并证明只有r ( d ) 不超过信道 容量就能保证接收端的失真不超过给定阀值d 的，在数学上，r ( d ) 定义为在给 定失真d 的条件下，系统所能够达到的最小码速率。对于幅值离敞的信源，r ( d ) 定义如下： 尺( d ) = r a i n p ( x ) p ( y x ) l o g z ( p ( y x ) q ( y ) ) ( 2 1 ) r 其中 q ( ，) = p ( x ) p ( y x ) f ( 2 2 ) 平均失真满足条件：p ( x ) p ( y x ) d ( x ，y ) 蔓d ( 2 3 ) y 其中d ( x ，y ) 是失真测度，它表示输出采样值，再现原始信源采样值所 引入的失真，p ( y ) 表示存已经发送x 的情况下接收到y 的概率。r ( d 1 的单 位为比特采样。同样，可以计算速率一失真函数的逆函数d ( r ) ，称为失真速率 函数，其含义为：在给定速率不超过r 的条件f ，系统所能达到的最小失真。d ( r 1 和r ( d ) 所给出的编码性能极限，适用于所有信源编码方法。d ( r ) 是在维数据k 趋向无穷大时d 。( 月) 的极限，即 d ( r ) ，i i r a 眈( 尺) ( 2 4 ) 根掘香农的这一理论，可以找到一个最小的信源速率使得系统发送端到接收 端的! ，_ 均失真不超过给定的失真阀值，这正是数据压缩系统所要做的事情，吲此 内格尔f1 9 7 1 年称香农的这一理论为“数掘压缩的数学丛础”。从式( 2 - 4 ) 可 知，利用欠量量化，编码性能可能任意接近速率失真函数，其方法是增加矢嚣 维数女。舀实际应f j f ，速二钲失真甬数常常作为一个理沦f 释t 爻际编码速牢 幽像矢量量化编码技术研宄 相比较，分析系统还有多大的改进余地。总之，速率一失真理论指出了矢量量化 的优越性。不过，速率一矢真理论是一个存在性定理而非构造性定理，凼为它并 没指明如何构造矢量量化器。 2 1 2 矢量量化定义 基本矢量量化器【5 6 1 可以定义为从k 维欧几里德空间r 到其一个有限子集c 的一个映射，即q ：r 斗c ，其中c ： y 。，y l , - - - , y 1 只r 称为码书，n 为 码书大小，该映射满足：q ( x i x r k ) = y ，其中x = ( 知，_ ，一x k ，) 为r 中的k 维 矢量，y ，= ( y 妒，y p ( ki ) ) 为码书c 中的码字并满足 d ( x ，y p ) _ 。r a i n d ( x ，y j ) ( 2 5 ) 其中，d ( x ，y j ) 为输入矢量r 与码字”之问的失真测度。每一个矢量 f = ( ，_ ，_ 一。) 都能在码书c = y o , y ，y 。) 中找到其最近码字 y 。= q ( x i r r ) 。输入矢量空问通过量化器q 量化后，可以用划分 s = s 0s ，s 。) 来描述，其中s 是所有映射成码字只的输入矢量的集合，即 s = 缸i q ( x ) = 只 。这个空问品，s ，s 。满足： u ：1 s ，= s 且丌= s = s ( 2 6 ) 基本的矢量量化编码和解码过程如图2 一l 所示。矢量量化编码