（信号与信息处理专业论文）基于小波变换的分类矢量量化图像压缩编码方法研究.pdf

独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包括其他人已经发表或撰写过的研究成果；也不包括为获得西安电子科技大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 本人签名宣盘重 日期加，- ， 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或 部分内容，可以允许采用影印、缩印或其他复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本人签名宣盏垄 导师签名通曼聋 日期娜，f 日期0 蛐，s 摘要 摘要 本文主要研究了静止图像的压缩编码，给出了一种基于小波变换的利用了相 同方向不同分辨率级子图像之间相似性的分类矢量量化编码方法。论文介绍了小 波变换和矢量量化的基本概念，及小波变换中m a l l a t 算法在图像处理中的应用。 论文对图像经小波变换后小波系数的能量分布进行了讨论，研究了小波变换后相 同方向、不同分辨率级子图像之间的相似性，并把此研究结果应用到分类矢量量 化中。论文还讨论了小波零树的概念，把零树概念和零树数据结构的思想引入到 分类矢量量化方法中，给出了一种基于小波变换的分类矢量量化的方法。通过对 人头像和医学显微图像的计算机仿真，说明了此方法具有优于传统方法的压缩编 码效果。 关键词：图像编码、小波变换、分类矢量量化、相似性、小波零树 1 a 。b s t r a c t i nt h i sp a p e r ，s t i l li m a g ec o m p r e s s i o ni ss t u d i e d w h e nt h ei m a g ei sd e c o m p o s e db y d i s c r e t ew a v e l e tt r a n s f o i t l l ，t h es a m ed i r e c t i o ny e td i f f e r e n tr e s o l u t i o ns u b i m a g e sh a v ea s i m i l a r i t y b a s e do nt h i ss i m i l a r i t y , as t i l li m a g ec l a s s i f i e dv e c t o rq u a n t i z a t i o ns c h e m ei s p r e s e n t e d t h e m a i nc o n c e p t sa b o u tw a v e l e tt r a n s f o r ma n dv e c t o r q u a n t i z a t i o na r e i n t r o d u c e d h o wt ou s et h em a l l a ta l g o r i t h mi ni m a g ec o d i n gi si n t r o d u c e d t h ee n e r g y d i s t r i b u t i o no fs u b i m a g ec o e f f i c i e n t sa n dt h es i m i l a r i t yo fs u b i m a g e sa r ed i s c u s s e d i n t h i sp a p e r , t h ez e r o t r e eo fw a v e l e tt r a n s f o r mc o e f f i c i e n t si sd i s c u s s e dt o o b a s e do na l lo f a b o v e ，as t i l li m a g ec l a s s i f i e dv e c t o rq u a n t i z a t i o ns c h e m eb a s e do nw a v e l e tt r a n s f o r mi s p r o p o s e d t h r o u g ht h ec o m p u t es i m u l a t i o na b o u th e a di m a g e sa n dm i c r o s c o p e - m e d i c a l i m a g e s ，t h eb e t t e ri m a g ec o m p r e s s i o ne f f e c ti sp r o v e d k e y w o r d si m a g ec o m p r e s s i o n w a v e l e tt r a n s f o r mc l a s s i f i e dv e c t o rq u a n t i z a t i o n s i m i l a r i t y z e r o t r e e so f w a v e l e tc o e f f i c i e n t s 第一章绪论 第一章绪论 1 1 图像压缩编码的必要性和可能性 随着多媒体时代的到来，现代信息社会对通信业务的要求不断增长，而图像 作为信息含量最为丰富的载体，在现代通信技术中所承担的作用已远远超过其他 载体。有资料表明，人类通过视觉获得的信息量约占总信息量的7 5 。由于数 字通信一系列的优点，绝大多数图像通信系统采用数字的方式进行存储和传输。 但数字图像的特点之一就是数据量非常巨大，若不经过压缩，数字图像传输所需 的高传输速率和数字图像存储所需的巨大容量将成为推广应用数字图像通信的最 大障碍。 例如，一张6 0 0 m 字节的光盘，仅能存放2 0 秒左右的6 4 0 4 8 0 象索的图像 信息。而一路按c c i r 6 0 1 标准数字化后的电视信号，若不经过数据压缩，就要 占用2 5 9 2 个有效数字话路进行传输( 以6 4 k b p s 作为一个数字话路) 。这在实际 应用中是难以接受的。由此可以看出，进行图像压缩编码是非常必要的。可以说， 高效的数字图像压缩编码技术是解决图像数据存储与存储产品容量、图像通信与 通信网容量之间日益突出的矛盾的一个不可缺少的关键技术，是构造一个全新数 字化信息社会不可缺少的条件。 数字压缩技术始于信息论。从信息论观点看，描述图像信源的数据是由有效 信息量和冗余量两部分组成的，去除冗余量能够节省存储和传输中的开销，同时 又不损害图像信源的有效信息量。这种信息冗余是图像可以压缩的根本原因。我 们把图像内相邻像素之间的相关性，称为空间冗余：序列图像前后帧之间的相关 性，称为时间冗余：多光谱遥感图像各谱间的相关性，称为频率域冗余；相同码 长表示不同出现概率的符号造成的比特数浪费，称为符号冗余。 在有些场合，一定限度的失真是允许的。如人眼对图像灰度分辨的局限性， 监视器显示分辨率的限制，都可以对图像信源作一定程度有时甚至是很大程度的 压缩。这里分别利用了人眼的视觉冗余和显示器的分辨率冗余。 此外，在某些特定的应用场合，编码对象的某些特性可以预先知道。例如， 在可视电话中，编码对象为人的头肩像。利用对编码对象的先验知识为编码对象 建立模型。通过提取模型参数，对参数进行编码而不对图像直接进行编码，利用 了知识冗余，这是模型编码的思想，它可以达到非常高的压缩比。 图像编码技术就是把各种压缩的可能变为现实。 !基于小波变换的分类矢量量化图像压缩编码方法研究 i 2图像压缩编码分类和一般框图 1 2 1 图像压缩编码分类 以信息保真为出发点，图像压缩编码方法可以分为无损压缩和有损压缩两 类。无损压缩又称无失真压缩编码，其核心是基于统计模型，减少或完全去除原 数据流中的冗余，同时保持信息不变。哈夫曼编码、算术编码就属于这类。有损 编码又称限失真编码，它以牺牲部分信息量为代价来换取平均码长的缩短，其恢 复图像与压缩前图像不会完全一致。包含量化的编码就属于这类。 i 2 2图像压缩编码的一般框图 在多数应用中，人眼往往是图像的最终接受者( 信宿) ，考虑到视觉冗余， 为了提高压缩比，一般采用限失真编码。它的编码过程可以概括成图1 1 所示的 三个步骤，原始图像通过映射变换后，形成的系数经量化器量化和熵编码器编码， 形成码流输出。其解码为编码的逆过程。 图1 i图像编码的一股框图 1 映射变换 其目的是通过映射改变图像数据的特性，使之更有利于压缩编码。这一步 在图像编码中起到了核心作用。一个好的映射变换通过与合适的量化器相配合， 应能充分消除图像信源的各种冗余。 2 量化器 在限失真编码中要对映射后的数据进行量化。若量化是对映射后的数据逐 个进行，则称为标量量化。若量化是成组进行，则称为矢量量化。量化总会造成 某些信息丢失，形成失真，即量化失真或量化噪声。 3 熵编码器 第一章绪论 这一步是用来消除符号编码冗余的。它一般不产生失真。理想的情况是使 生成的码流的平均码长等于量化后数据的信息熵。 上述三个步骤在图像压缩编码中是相互联系相互制约的。 1 3图像压缩编码技术的发展历史与现状 1 9 4 8 年提出电视信号数字化后，就同时开始了对图像压缩编码的研究工作， 至今已有5 0 多年的历史。下面简要介绍这期间图像压缩编码技术的发展和现状。 1 3 1图像编码技术发展历史 最初的编码技术是基于s h a n n o n 信息论的熵编码技术。它纯粹基于信息的 统计模型，属无失真编码，其编码的平均码字长下限是图像的信源熵。此类技 术的代表有h u f f m a n 编码、游程编码、算术编码等。 随后，人们发现图像数据在数值上发生细微变化时，人眼并不会察觉。基 于这点，人们摆脱了无失真编码的限制开始寻求限失真编码的方案，出现了 允许有细微差异的量化方案。 后来，人们发现了图像中相邻像素之间存在着很强的相关性，去除这种冗 余可以大大简化图像的数据表示，在此基础上提出了以差分脉冲编码调制 ( d j p c 吖) 为代表的各种预测编码方法和各种内插编码方法。 由于正交变换具有熵保持、去相关、能量集中的特点，又出现了以d c t 变 换、k l t 变换、w a l s h h a d a m a r d 变换为代表的变换域编码。 7 0 年代，瑞士学者m k u n t 提出了“第二代图像编码技术”的概念。它区 别于前面去除图像统计冗余的早期编码方法而是以去除图像的视觉冗余为主要 目标，强调编码不仅应充分利用图像信源的局部和全局的统计相关性，而且要利 用图像内部的几何特征、自相关性和方向性等多种自然属性和规律，同时强调不 再简单地将图像作为客观信源来看待。而在充分考虑人类视觉系统特性的基础 上，针对图像视觉信息进行有效编码。在这个阶段，出现了基于方向性滤波的编 码、基于图像纹理轮廓的编码和区域基编码【l 。 这期间，人们逐渐认识到单纯通过一种编码技术很难去除图像存在的几种 相关性，而将多种编码技术有机地结合起来形成一种综合的压缩编码方法，以获 得更好的压缩性能。混合编码研究的一个直接成果就是j p e g 图像压缩国际标准 的诞生，它融d c t 、d p c m 、视觉加权标量量化和熵编码于一体，达到了良好 的性能指标。 一4 基于小波变换的分类矢量量化图像压缩编码方法研究 这阶段还出现了基于s h a n n o n 率失真理论的矢量量化( 叼) 技术。率失真理 论论述了矢量量化( v q ) 的性能总是优于标量量化( s q ) ，在编码长度趋于无穷 的情况下，比特率和失真之间的关系可以达到率一失真界。 另外还出现了以视觉的空间频率为出发点的子带图像编码技术，它对后期出 现的小波编码技术有着直接的影响。 1 3 2 图像压缩编码的现状 现阶段图像压缩编码的最大特点是引入了新的数学工具和理论。从8 0 年代 末到9 0 年代中期，大量崭新的数学理论成果被引入到图像编码领域，为图像编码 技术的发展注入了巨大的活力。当前阶段几种比较流行的编码技术是模型编码、 神经网络编码、分形编码和小波编码。这些技术分别利用了计算机视觉理论、神 经网络理论、分形几何理论和小波理论。 其中，基于小波变换的图像压缩编码已成为新一代图像压缩编码中最具生命 力的方法。小波变换可将图像分解成不同空间分辨率、不同频率特征和方向特征 的子图像信号。这样，对不同子图采取不同的量化方案，可以达到压缩的目的。 总之，当前阶段的编码基于更广泛的理论基础并注重各种算法的相互渗透和 补充，以获得更佳的编码性能。 1 4 本文的主要工作和内容安排 本文研究了小波变换、矢量量化和小波零树理论，分析和讨论了图像经小波 变换后，相同方向各高频子图像之间的相似性，在此基础上给出了一种基于小波 变换的分类矢量量化图像压缩编码新方法。该方法利用子图像之间相似性对高频 系数进行分类矢量量化。该方法的优点在于避免了传统的基于d c t 的图像压缩编 码算法在高压缩比情况下，出现明显的分块效应和振铃现象，在实现高压缩比的 情况下，保证了比较好的恢复图像质量。通过对人头像和医学显微图像的计算机 仿真，说明了该方法的优良性能。 本文在第一章讨论了图像压缩编码的必要性和可能性，介绍了图像压缩编码 的发展和现状。第二章主要阐述了小波变换的基本原理和数字图像的m a l l a t 算法。 第三章阐述了矢量量化的基本原理并简要介绍了矢量量化在图像编码中的应用。 第四章讨论和分析了图像经小波变换后的数据统计特性，介绍了小波零树的概念 和s h a p i o r 算法。第五章研究了分类矢量量化和小波变换后相同方向不同分辨率 级予图像之间的相似性，给出了一种处理小波变换后高频子图像的分类矢量量化 新方法。然后给出了这种方法的实验结果。最后，对全文做了总结。 第二章小波分析基本理论 第二章小波分析基本理论 作为多个学科共同研究的成果，小波分析理论正日益受到学术界和工程界的 密切关注，成为近代多门学科和多种领域的研究热点。 小波来源于f o u r i e r 分析的不足。在经典信号分析中，f o u r i e r 变换无法同时 得到信号的时域和频域特性，而小波采用可变的时一频窗口可以对信号进行局部 性分析，弥补了f o u r i e r 分析的不足。原则上讲，以往一切f o u r i e r 变换的应用领 域均可通过小波变换加以应用。由于小波变换在时域和频域同时具有良好的局部 化性质并且对高频成分采用逐渐精细的时域和空域取样步长，可以“聚焦”到对 象的任意细节，从而被人们誉为“数学显微镜”。 小波变换作为一种新的数学工具，具有十分优异的性能。不同学科的研究者 对小波有不同的看法。数学家认为小波可以作为表示函数空间的一种新方法；信 号处理专家认为小波是非平稳信号时间一频率分析的新技术：图像分析利处理专 家认为小波是时间一尺度分析和多分辨分析的一种有效工具。本章将以s m a l l a t 提出的多分辨率分析为主体，介绍小波变换的有关概念及m a l l a t 算法，并阐述小 波变换在图像处理中的应用。 2 1 小波变换 小波分析的基本思想是用一族函数去表示或逼近一信号或函数，这一族函数 称为基函数，它是通过基本小波函数的不同尺度的平移和伸缩构成，基函数表 示的特点是时频带宽乘积很小，且在时间和频率轴上都很集中。 2 1 1 小波函数 设少( t ) r ( r ) ，l 2 ( r ) 表示一维平方可积实函数集，妒( t ) 的f o u r i e r 变换为甲( f o ) 并且满足容许性条件( a d m i s s i b l ec o n d i t i o n ) c ，= 胖学咖 ( 2 - ) 则称矿( t ) 为基小波。 2 1 2连续小波变换 对于每一个基小波y 在l 2 ( r ) 上的连续小波变换定义为 町“a ，b ) 。击e ，( f ) 妒( 等瑚 ( 2 _ 2 ) 一6基于小波变换的分类矢量量化图像压缩编码方法研究 其中任意函数f ( t ) l 2 ( r ) ，a r + ，b r ，a 0 , a 称为伸缩因子，b 称为平移因 子，( 三二皇) 为( 三二鱼) 的复共轭函数，当为实函数时两者相等。 订日 令 妒( t ) = 缈( t ) ， 嘣t ) 2 忑1 妒( 丢) 则( 2 2 ) 式可改写成为 ，( a ，b ) 2 t ( t ) + ( t ) ( 2 3 ) 可见，小波变换可以看成是原始信号和一组不同尺度的带通滤波器的滤波运算， 从而可以把信号分解到一系列频带上进行分析处理。 ( 2 2 ) 式表示的容许性条件等价于 l ( ，) 馥2 0( 2 - 4 ) 从( 2 - 1 ) 式和( 2 - 3 ) 式可知基小波妒是个波动( 振荡) 的无直流函数。连续小波变换也 可以写成内积形式 吩，( a ，b ) 2 ( 2 - 5 ) 其中 州； y ( 上二鱼)t a ，b r , a o ( 2 - 6 ) v 日 称为分析小波( a n a l y z i n gw a v e l e t ) 或连续小波。它是由基小波( t ) 生成的小波。 j a l 1 “是为使变换结果归一化引入的。 子波p ( t ) 应具有以下三个特征：具有波动性的振荡，具有正负相间快速 衰减到零的特性，在整个肘阍域的均值为零。 连续子波变换具有如下性质： ( 1 ) 线性性质：一个多分量信号的小波变换等于各分量的小波变换之和； ( 2 ) 平移不变性性质：若f ( t ) + w r ( a ，b ) 则r ( t r ) h w r ( a ，b f ) ； 1 ( 3 ) 伸缩共变性质：若f ( t ) h w 矿f ( a b ) 则f ( c t ) + + w v “c a ，c b ) ； 吖c ( 4 ) 自相似性质：对应于不同尺度参数8 和不同平移参数b 的连续小波交换 之间是自相似的。这是由于小波族。( 啦黾同基小波妒( t ) 经过平移和伸缩 获得的，而连续小波变换又具平移不变性和伸缩共变性，所以在不同的( a ，b ) 点的连续小波变换具有自相似性： 假设y ( t ) l 2 ( r ) ，为了由连续小波变换式( 2 2 ) 重构f ( t ) ，矿( t ) 应满足容许性 第二章小波分析基本理论 条件式( 2 一1 ) 或式( 2 3 ) 。这时信号“t ) 可由它的小波变换。，( a ，b ) 重构。 重构公式如下： f ( 1 ) 。专儿 加渤6 ) 警 ( 2 _ 7 ) 2 1 3 小波变换的时频局部化性能 如果函数g ( t ) l 2 ( r ) ，且t g ( t ) l 2 ( r ) ，则g 被称为窗e l 函数。小波是窗1 2 1 函 数窗口函数的大小和形状是变化的，这一点不同于窗口f o u r i e r 变换中的窗口 函数。 若( “，w 0 ) 为子波函数妒( t ) 在时频平面上的中心点，显然y ( 尘旦) 的中心点位 “ 于( a l 。+ b ，w 0 a ) ，对应的时域及频域的宽度分另4 为a 盯，和盯。a ，其中q 与盯。为y ( t ) 对应的时域和频域宽度。因此，小波的时间频率窗特点是：对于小的中心频率 选，即低频信号，时窗变宽，频窗变窄，利于描述信号的整体形状；对于大的 a 中心频率堕，即高频信号，时窗变窄，频窗变宽。在很短暂的高频信号如信号 中的瞬变现象，小波变换能更好的“移近”观察，即数学显微镜的“变焦”特性。 ? 盆甾 w 圃圜矧 w 以 w 口 w n ，钔 w 图2 1 变换时频窗口的相空间表示 h e i s e n b e r g 测不准原理】排除了在时间和频率域均有任意高分辨率的可能 性。时间分辨率和频率分辨率是相互矛盾的，时间分辨率的提高意味着频率分辨 率的降低，反之亦然。但是子波变换还是较好的解决了时间和频率分辨率的矛盾， 它巧妙地利用了非均匀分布的分辨率，虽然时频窗的面积是固定的。正如图2 1 所示。 肌网图 !基于小波变换的分类矢量量化图像压缩编码方法研究 2 2 离散小波变换 在实际应用中，尤其是数字信号处理领域，为了计算上的方便，需要使用离 散小波变换进行分解，也就是将f i t ) 的积分形式展开为离散和形式。所谓离散小 波就是将y ( t ) 的参数a 和b 离散化。 对a 和b 按如下规律取样： a = 口? ，b = n 6 0 口：( 2 8 ) 其中，口。 1 ，b o r ，m ，n e z 。则由式( 2 - 6 ) 得离散小波： y 。( t ) 2 2y ( a o ”t - n b o )( 2 - 9 ) 特殊的，当d 。= 2 且b o l l 可以得到如下二进小波： y 。、。( t ) = 2 ”y ( 2 - m t - n )( 2 - 1 0 ) 离散小波变换为 d 。2if ( t ) v 。，( o a t 2 ( 2 - 1 1 ) 如果f ( t ) 也是离散的，记为f ( k ) ，则有 d ，。= ，( ) 瓦 ( 2 1 2 ) k 小波逆变换的离散形式为 f m ) = d 既，。，= 矿，。 ( 2 1 3 ) m nm 月 式( 2 1 2 ) 所示的小波称为离散二进小波，它对信号的分析具有变焦距的作用。 假设开始时选择一个放大倍数2 “，它对应为观察到信号的某部分内容。如想进 一步观看信号更细小的细节，就需要增大放大倍数即减小m 值。且可继续下去。 反之，可增大m 值，减小放大倍数，了解信号较粗的内容。 2 3 多分辨率分析与m a l l a t 算法 m a l l a t 提出的多分辨率分析( m u l t i - r e s o l u t i o na n a l y s i s ，m r a ) 的概念，及多分 辨率塔式分解与合成算法，使得信号在小波基函数上的内积运算转变为与相应小 波滤波器的卷积运算，因此。m a l l a t 快速算法在小波分析中的地位等同于快速傅 立叶算法( f f t ) 在付氏分析中的重要性，它极大地促进了小波变换在数字信号处理 中的工程应用。 第二章小波分析基本理论 2 3 1 多分辨分析 9 子波函数矿( t ) 经伸缩和平移构成了一个多分辨的函数空间，予波分解就是把 被研究信号在子波函数构造的多分辨空间上进行投影。这构成了对信号的多尺度 分析。 设矿，t - 1 ；2 ( r ) c j z ) 是r ( r ) 内一个嵌套子空间，且巧满足下列条件： ( 1 ) 一致单调性：c 矿f + l ，j e z ( 2 ) 渐进完全性：n = 0 1 ，u 巧2 r ( r ) t z，6 z ( 3 ) 伸缩不变性：f ( t ) f ( 2 t ) 一。，j e z ( 4 ) 平移不变性：f ( t ) en f ( t - k ) ，j ，k z ( 5 ) r e i s z 基存在性：存在庐( t ) ，使得 ( t - k ) ( 其中k e z ) 是的r e i s z 基。 则称平方可积空间l 2 ( r ) 0 0 一系列闭子空间批 埘构成了上2 ( r ) 上的一个多 分辨翠分j ir 。 多分辨率分析( m r a ) 定义了一个对r ( r ) 逐渐逼近的空间序列 ) ，即有 牌_ 。u 巧三2 ( r ) 。由上述定义可知，每个子空间_ 都对应着一组基 办* ) ， 它们都是由同一个函数妒( t ) 经过伸缩和平移构成的，生成公式如下： “( t ) = 2 1 ”庐( 2 t - k ) ， j ，k e z ( 2 - 1 4 ) 函数( t ) j c g 为该多分辨分析的尺度函数。 由m r a 的定义可以很自然地想到，对任意一个函数f ( t ) l 2 ( z ) ，都可以用 f ( t ) 在v j 上的投影p j ( t ) 来逼近f 。随着j 的增加，子空间v j 越来越逼近l 2 ( r ) ，p i ( t ) 也就越来越逼近f ( t ) ，即有坟t ) = l i mp j ( t ) 。对于相邻的两个子空间v j 和v j “来说， p 。( t ) 和p j + 。( t ) 之间存在着差异。为了表示这一差异，定义另外一个空间序列 矿， 懈，使得w j 是v j 在v j + - 中的正交补，即有 v j + 1 = v i w j ，v j 上w j ( 2 _ 1 5 ) 弋：i 弋：i 弋：弋三 图2 2l 2 ( r ) 的多分辨分解 基于小波变换的分类矢量量化图像压缩编码方法研究 这样就可以将l 2 ( r ) 分解为v ；，w 的直和。如图2 2 的形式。 l 2 ( r ) 2 o w j 1 0w j ow j + l o 2 v j o o 啊 ( 2 - 1 6 ) ，一j 显然，空间w ；包含了从j 层次逼近j 一1 层次时所需的“细节”信息。空间序 列( w j ) 同样是由一个函数y 的伸缩和平移来产生的，即子空间w i 的基是 妒。( t ) = 2 y ( 2 t - j ) j 。：，函数y 称为小波函数。 尺度函数( ，) 及予波函数妒( ，) 的特点是满足下列双尺度差分方程： 妒( f ) = f f 2 h ( n ) c j ( z t n ) 妒( ，) = 2 g ( n ) ( 2 ，一”) ，i e z = 2 ( ) 庐( 2 ，- h ) h e z y ( ，) = 2 g ( n ) 庐( 2 r - n ) ( 2 1 7 ) 其中妒( t ) ，矿( t ) 分别为，妒( r ) 的对偶函数，h ( n ) ，h ( n ) 称为尺度滤波器 g ( n ) ，g ( n ) 称为子波滤波器。对于实正交子波基有如下特点 庐( t ) = 庐o ) = b c t ) ，妒( r ) ；妒( t ) = ( r ) 至此，我们有了一系列子空间v j ，w j 及它们各自的基矿j ，妒，设( t ) 是信号 f ( t ) 在v j 空间内的分量：g j ( t ) 是信号f ( t ) 在w j 空l e r 的分量；则有 ( c ) = c 办。( ，) j e z ( 2 1 8 ) 岛( t ) = d 卅y 卅( ，) ( 2 1 9 ) 其中 c j ，k - ( ，( f ) ，以( f ) ) = c 们) 菇) 出 ( 2 - 2 0 ) 屯2 ( 邝厩) ) 2e ，( ，厩( f ) 讲 ( 2 2 1 ) r a ( 2 1 6 ) 知道l 2 ( r ) 可分解成v j ，w 的直和，对于任意f ( t ) l 2 ( r ) ，都有基于上述多 分辨空间的分解 第二章小波分析基本理论 1 1 j - i f ( t ) = ( c ) = 1 ( t ) + g j 1 ( t ) = f j a ( t ) + g j 2 ( t ) + g j 1 ( t ) = m ( t ) + g ，o ) ( 2 - 2 2 ) 产j - m 式2 2 2 可用图2 3 形象地表明。 “弋二弋二 图2 3 尺度空间对应的函数分解 对于时宽较小的基函数，它所张成的空间v ；被称为小尺度空间或高分辨率空 间，它包含了扩大后的基函数。所张成的大尺度空间或低分辨率空间v 。的全部 信息。信号在小尺度空间的分量反映了它的高分辨细节，在大尺度空间具有低分 辨分量。 多分辨分析的基本思想就是将信号所在的小尺度空间逐渐分解成一系列分辨 率逐渐降低的多尺度空间，使原始信号可表示为一系列不同分辨率下的信号的线 性组合，从而构成了对信号的多分辨( 多尺度) 分析。 2 3 2m a l l a t 算法 由于子波构造的多分辨空间有一些特殊的性质，如其尺度函数、子波函数满 足双尺度差分方程，进而使信号在各个子空间上的投影系数具有一定的递推关 系，于是就产生了子波分解的快速算法m a l l a t 算法。 由双差分尺度方程( 2 1 7 ) 可知： 卅( f ) = 2 j “9 i ( 2 j t l k ) ；2 0 + 1 m 庐( 2 “t 一2 k n ) ( 2 2 3 ) n e z 代入式( 2 2 0 ) 得： ， 1 、一 一 2 c j j ( k ) 。( 巾) ，“t ( r ) ) 。l 。邝) 庐j - , k ( t ) d t 2 i = 厂( r ) 2 。“善i ( ”) i ( 2 。r 一2 k 一一) - 击= 同理 = 州k ) = g ( h ) c 。 重构公式为： ( 月) c 坩 ( 2 - 2 4 ) n l z f 2 - 2 5 ) c j , k = c j ( k ) = h ( k - 2 n ) c 川( n ) + g ( t 一2 n ) dl ( h ) ( 2 - 2 6 ) n t z 旦基- t 4 , 波变换的分类矢量量化图像压缩编码方法研究 子波分解后的系数c j i k ，d j 是f m 在相应的子空间v j ，w j 上的各个基基址， 在分辨率j 下，空间位置k 处对原函数的贡献。h ( n ) 为一低通滤波器，g ( n ) 为一带通 滤波器， 基于以上各个子空间的系数的递推关系，可得下述的塔型分解与重构算法。 一个完整的塔型算法流程图如下： 图2 4 子波变换的m a l l a t 塔型算法 由上图可以看到，m a l l a t 算法通过一组分解滤波器h 和g 对信号进行滤波。 尺度滤波器h ，i 为一低通滤波器，起平滑作用，得到信号的缓变部分，子波滤 波器g ，g 为一带通滤波器，起差分作用，得到信号的细节变化成分。经一级子 波分解，对应的尺度函数、子波函数在时域尺度上增大一倍，频带上减小一半， 故后级系数可经下2 采样只保留一半而信息不损失。其中，子波系数d j 。反映了 在第j 个尺度下，以相应的分辨空间在空间位置k 处信号的起伏分量。 2 4 图像的二维小波变换 图像的最大特点是非平稳特性，即不能用一种确定的数学模型来描述，而小 波的多分辨率分析特性使之既可高效地描述图像的平坦区域，又可有效地表示图 像信号的局部突变( 即图像的边缘轮廓部分) ，它在空域和频域怠好的局部性，使 之可以聚焦到图像的任意细节。因此，小波非常适合于进行图像处理。 2 4 1 图像的m a l l a t 算法 针对图像信号处理，基于上述一维的数学表达，m a u a t 提出了二维的子波分 解与重构算法，其中采取了可分离的滤波器设计。图像子波分解算法为； 掣f ( m ，n ) - - 彤i f ( k ，o h ( k 一2 m ) h ( i 一2 竹) ( 2 - 2 7 ) ， 第二章小波分析基本理论 d j f ( m ，h ) = 嘭f ( k ，1 ) g ( k - 2 m ) h ( 1 - 2 n ) j d f ( m ，h ) = 以。f ( k ，1 ) h ( k 一2 m ) g ( 1 2 n ) 女t d j f ( m ，n ) = e 川df ( k ，1 ) g ( k 一2 m ) g ( 1 2 n ) ， 1 3 ( 2 - 2 8 ) ( 2 - 2 9 ) ( 2 - 3 0 ) 式中h ( n ) 和g ( n ) 分别为对应同一子波基的低通和高通滤波器。分解算法把 原始图象在同一级上分解成4 个子图象，分解后各级的子图象分别对应于不同 分辨率的频率段。p ? f ( m ， ) 为p 矗f ( m ， ) 在第j 级子波的低频成分，即在2 ，分 辨率下的模糊图象，称为亮度子图象；d _ ：f ( m ， ) 为以。f ( m ，”) 的竖直方向的高频 成分，相当于图象的水平边缘；d ；f ( m ，竹) 为p 盘f ( m ，”) 水平方向的高频成分，相当 于图象的竖直边缘；d ；f ( m ，h ) 表示尸盘f ( m ，h ) 水平，竖直两个方向上的高频成分， 即角点和4 5 0 边缘这三种高频成分均称为边缘子图象 子波分解是可逆的，图象子波重构算法为 e e lf ( m ，h ) = 4 掣f ( k ，1 ) h ( m - 2 k ) h ( n - 2 1 ) + 叫f ( k ，1 ) g ( m 一2 k ) h ( n - 2 1 ) + e 2 f e zi z t l z 珥f ( k ，1 ) h ( m 一2 k ) g ( n 一2 f ) + 巧f ( k ，1 ) g ( m - 2 k ) g ( n - 2 1 ) t e z k z目z l z ( 2 - 3 1 ) 图像数字信号经离散小波变换，即在水平和垂直方向上分别应用h 、g 滤波器 进行一维滤波来实现，如图2 5 所示。 对图像进行一级小波变换后，对低频子图像再进行小波变换，如此多次对 分解后的低频子图进行分解，得到的这种多级分解就是m a l l a t 塔式分解。如图 2 ，6 所示。 原始匿攮厂二二_三三三二】-一 ( a ) 二维离散小波分角翠 坐 基于小波变换的分类矢量量化图像压缩编码方法研究 列滤波 行滤波 ( b ) 二维离散小波重构 图2 s 二维离散小波变换的m a l l a t 实现 原 下面以一幅数字化图像l e n a 为例，对原图进行子波变换得到一组尺寸随 予波变换级数的增加而减半的子带。如图2 7 ( b ) 。这些子带代表了一定的频率信 息，将这些子带按左上方为低频，右下方为高频的次序排列起来。观察每个子带 内部的系数分布，可看出它还保持了原图的空间位置信息。可见，对图像进行予 波变换，频率信息表现在不同的子带上，而空间位置信息则体现在子带内部。对 图像进行一级小波分解。得到如图2 7 ( c ) 所示的分解数据。它由四块子图像组成， 分别代表了不同频率特性和方向特性的滤波。l l i 对应低频分量，l h l 代表水平 方向的高频分量，h l i 代表垂直方向的高频分量，h h i 代表对角线上的高频分量。 各部分都包含了原有图像的空间结构信息。其中，l l l 为原图像经过平滑的形式， 对低频子图l l l 可以继续分解，得到相应的多分辨率级层次。图( b ) 为图( a ) 做三 级小波变换后的结果，( c ) 为系数划分示意图。 第二章小波分析基车理论 ( a ) 原始嗍像 l l l l h l h l l h h l ( b ) 图像的f 激变换 l l 3 j l h 3 l h 2 h l 3 1 h h 3 l h l h l 2 h h 2 h l lh h l ( c )一级小波变换c d ) 系数之划分示意幽 圈2 7l 萼l 像的二级小渡变换 2 4 2 图像小渡变换的优点 l s 研究表明，大脑皮层单细胞接受的视觉信号具有方向性从视网膜进入大脑 皮层的信息处理具有方向滤波环节。小波变换从多个侧面体现了人匣感知特中# ， 其空b j 一尺度分层结构与人的视觉系统特性相似其多方向梯度提取的特点较为 符合视觉生理结构，因此，基于小波的编码方法可咀得到与人类视觉系统柏一致 的编码质量，为所谓的“感知压缩”提供了客观依据。 小城变换后的每个子带对应一定的频率，并傈待了定的原圈像的空阳j 特 性，随着分解层次的提高，不同分解级的子带具有一定的空间榍似性，这为编码 的有效实现提供了条件。 堑 基于小波变换的分类矢量量化图像压缩编码方法研究 而且，小波变换作用于图像的整体既能够去除图像的全局相关性，又可以 将量化误差分散到整个图像内，避免了一般离散余弦变换( d c t ) 产生的方块效应。 并且，多级分解后形成的不同分辨率和频率特性的子带信号，便于在失真编 码中综合考虑视觉特性，同时有利于图像的逐渐浮现传输。 多种优点结合起来，使得小波变换成为目前图像编码领域最有前途的编码方 法之一。 下面给出利用小波变换，实现高性能的图像编解码的一般框图。 编码系统解码系统 图2 8 基于小波变换的图像编解码系统框图 第三章矢量量化原理 第三章矢量量化原理 1 7 量化技术是信号数字化的关键步骤之一，并且在数据压缩上也起着重要的作 用。量化可以分为两大类：一类是标量量化( s c a l a rq u a n t i z a t i o n , s q ) ，一类是矢量 量化( v e c t o rq u a n t i z a t i o n , 砌。前者是把抽样后的信号逐个进行量化，后者是先将 k 个( k 至2 ) 抽样值形成k 维空间r 中的一个矢量，然后将此矢量进行量化。它 可以大大降低数码率，因此很受人们重视。 矢量量化总是优于标量量化的。这是因为矢量量化有效地应用了矢量中各分 量间的四种相互关联的性质( 线形依赖性、非线形依赖性、概率函数的形状、以及 矢量维数) 来消除冗余度。而标量量化只利用了线形依赖性和概率函数密度的形状 来去冗余。从理论上讲，正如s h m m o n 的率失真理论指出：当编码长度k o o 时， 速率与失真的关系可以达到率失真界。一般地说k 愈大，此关系离率失真界愈 近。因此，矢量量化优于标量量化，这也是率失真理论的结论。 1 9 7 8 年，b u z o 第一个提出实际的矢量量化器。即对语声作线形预测分析后， 将预测系数作矢量量化，得到压缩数据的语声编码器。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 算法推广，发表了第一个矢量量化器的设计算法，通常称为l b g 算法。因此，矢量量化研究开始进入高潮，尤其在失真测度、码书设计、码书的 快速搜索算法及各种类型的矢量量化系统等方面有了系统而广泛的研究。同时算 法由计算机模拟也转向硬件实现。目前，矢量量化已由探讨阶段转向实际应用阶 段。 本章将结合矢量量化在图像编码上的应用来简要阐述矢量量化的基本原理， 并对该领域的关键技术一码书生成算法进行详细讨论。 3 1 矢量量化基本原理 3 1 1 矢量量化的定义 首先我们以k = 2 为例，给出矢量量化的概念。 所有可能的2 维矢量( 囟，a ：) 组成一个二维平面，如图3 1 a 。矢量量化就是 先把这个平面划分成n 块( 相当于标量量化中的量化区问) s ，s 。，s 。；然后从 每一块中找一个代表值( 相当于标量量化中的量化值) r ( f _ ，z ) ，这就构成了一 个有n 个区间的2 维矢量量化器。选择最小的失真可能，将每个模拟矢量x ( a ， a ：) 确定在它对应的区间s 。，然后再用该区间的代表值z 代表它，r 就是模拟矢 量x 的重构矢量或称恢复矢量。通常把所有n 个量化矢量( 重构矢量或恢复矢量) 基于小波变换的分类矢量量化图像压缩编码方法研究 构成的集合 l 】；) 称为码书( c o d e b o o k ) 。把码书中的每个量化矢量r ( i = l 2 n ) 称为 码字或码矢。图3 1 b 所示的是一个7 区间的2 维矢量量化器，即k = 2 ，n = 7 ，f 称为量化矢量。 根据上面对矢量量化的描述，可以把矢量量化定义为： 矢量量化是把一个k 维模拟矢量x 映射为另一个k 维量化矢量 y y n2 y l ，y 2 ，y 。i y i r ) 其数学表示式为： y = q ( x )( 3 - 1 ) 式中x 输入矢量； a - 信源空间； 砧k 维欧氏空间； y 量化矢量( 码字或码矢) ； y 。一输出空间( 即码书) ； q ( ) 量化符号； n 码书的大小( 即码字的数目) 。 矢量量化用码书中n 个码字来替代信号矢量空间r 中的所有矢量，因而可 以大大简化信号的表示，达到压缩数据的目的。 湛 嗣 弋卜熬一 i 人k 一一 弋，彭 i 图3 1 矢量量化概念示意图 3 1 2 失真测度 失真测度d ( x ，y ) 是一个由乘积空间x y 。到非负实轴的映射。即 d ：x y n 斗【o ，)( 3 2 ) 可以这样说，失真测度是以某种方式来反映码字y 代替信源矢量x 时所付 出的代价。这种代价的统计平均值( 平均失真) 描述了矢量量化器的工作特性，即 d = e d ( x ，q ( x ) ) 】( 3 3 ) 式中e ( ) 表示求期望。 第三章矢量量化原理 常用的失真测度有以下几种： ( 1 ) 平方失真测度 d ( x ，y ) = | ix - y | | 2 = ( 一一) 2 式中n | j 表示范数。这是最常用的失真测度，因为它易于处理和计算， 在主观评价上有意义，i i p d , 的失真值对应好的主观评价质量。 ( 2 ) 绝对误差失真测度 f d ( x ，y ) = i x - y 户lx ，一t j 此失真值的主要优点是计算简单，硬件容易实现。 ( 3 ) 加权平方失真测度 d ( x ，y ) = ( x - y ) t w ( ) ( y ) 式中t _ 一矩阵转置符号； w 一正定加权矩阵。 失真测度是定义矢最间距离的概念。在矢量量化设计中，失真测度的选择是 非常重要的，选择的合适与否，直接影响系统的设计性能。而且，理想的失真测 度不仅能反映信号的主观质量，而且易于数学实现。 在图像的矢量量化中，最常用的失真测度是均方误差( m s e ) ，即式( 3 4 ) 。m s e 失真测度的几何意义对应于矢量在多维空间的欧氏距离，虽然它在一定程度上反 映了信号的主观质量，但与信号的实际主观接受效果并不吻合。尽管如此，m s e 由于计算简单仍得到了广泛的使用。 目前，线形预测失真测度、似然失真测度等等被相继提出，但完全反映图像 信号主观质量的失真测度还没有定论。 3 1 3 矢量量化器 有了失真测度，就可以根据矢量量化的定义来具体