（信号与信息处理专业论文）基于小波变换的图像压缩改进算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 图像信号由于其数据量很大，在存储和传输的时候要对其进行压缩处理。小波变换是 一种有效的数学工具，基于小波的图像压缩技术正受到广泛的关注和研究。图像经过小波 变换以后，在时域和频域都具有良好的局部化特性，重建图像中可以克服采用离散余弦变 换编码所固有的方块效应，而且与人类视觉特性相一致。 本论文主要研究了基于小波变换的静态图像压缩算法，完成了以下一些工作：介绍了 传统图像编码和小波变换编码的原理和方法，在理论分析的基础上总结出小波变换的优 势。重点研究了小波编码算法中著名的嵌入式零树小波编码算法( e w z ) 及其改进形式分层 小波树集分割编码算法( s p i h t ) ，并在其基础上提出了本文的改进算法，包括采用提升方 案，降低了原始小波变换的复杂度；图像经过小波变换后，最低频子带包含了图像的大部 分信息，本文提出了频率优先编码概念，对低频子带单独编码；在量化时引入了符合人类 视觉特性的模板重新定义各子带系数幅值以提高重构图像的主观质量；对s p i h t 算法进一 步分析发现各高频子带小波系数的分布有一定的方向性和相关性，提出了一种新的系数扫 描方法，进一步改善了编码效率。 实验结果表明，虽然本文所提出的改进算法与其他的改进s p i h t 算法相比编码时间有 所增加，但在峰值信噪比上有比较好的表现，且使编码的方式更贴近人类视觉系统，重构 图像的效果较好，总体来说是一种比较有效的压缩算法。 关键词：图像压缩小波变换e z ws p i h t 南京邮电大学硕士研究生学位论文 a b s t r a c t a b s t r a c t i m a g ec o n t a i n sg r e a td e a lo fd a t a , t h u si m a g ec o m p r e s s i o ni sn e e d e df o ri t se f f e c t i v es t o r a g e a n dt r a n s m i s s i o n w a v e l e tt r a n s f o r mi sa ne f f e c t i v es i g n a la n a l y s i st o o l ；i m a g ec o m p r e s s i o n t e c h n o l o g i e sb a s e do nw a v e l e tt r a n s f o r mh a v ed r a w n w i d er e s e a r c ha t t e n t i o n s a f t e ra p p l i e dw i t h w a v e l e tt r a n s f o r m ，i m a g es i g n a ls h o w sg o o dl o c a l i z i n gc h a r a c t e r i s t i c si nb o t ht i m es p a c ea n d 丘e q u e n c ys p a c e ，w h i c hc o r r e s p o n d st oh u m a nv i s u a lc h a r a c t e r i s t i c s r e s t o r i n gi m a g e st h r o u g h w a v e l e tt r a n s f o r mc o u l dg e tr i do ft h eb l o c ke f f e c ti n h e r e n ti nd c tt r a n s f o r m t h i st h e s i sh a sd o n ef o l l o w i n gw o r k s ：i tf i r s ta n a l y z e st h et h e o r i e sa n dm e t h o d so f t r a d i t i o n a li m a g ec o d i n ga n dw a v e l e tc o d i n g ，p o i n t so u tt h ea d v a n t a g eo fw a v e l e tt r a n s f o r m t h r o u g ht h e o r e t i c a la n a l y s i s t h e nt h et h e s i sf o c u s e so nt h ef a m o u sw a v e l e tc o d i n ga l g o r i t h m s ： e m b e d d e dz e r o t r e ew a v e l e ta l g o r i t h m ( e w z ) a n ds e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s a l g o r i t h m ( s p i h t ) ，a n dp r o p o s e san e wi m p r o v e da l g o r i t h mw h i c he m p l o y sl i f t i n gs c h e m et o d e c r e a s et h ec o m p l e x i t yo fw a v e l e tt r a n s f o r m t h ei m p r o v e da l g o r i t h mi n t r o d u c e st h ec o n c e p to f f r e q u e n c yp r i o r i t yc o d i n gw h i c hc o d e st h el o wf r e q u e n c ys u b b a n d ss e p a r a t e l y , b e c a u s et h el o w f r e q u e n c ys u b b a n d sc o n t a i ni m a g e sm o s ti n f o r m a t i o n i nq u a n t i f i c a t i o np h r a s e ，an e we n h a n c e t e m p l a t ef i t t i n gh u m a nv i s u a lc h a r a c t e r i s t i c si su s e dt oe n h a n c er e s t o r e di m a g e ss u b j e c t i v e q u a l i t y a f t e rs t u d y i n gt h ed i s t r i b u t i o no fc o e f f i c i e n t so fh i g h 仔e q u e n c ys u b b a n d s ，an e w c o e f f i c i e n t ss c a nm e t h o di sp r o p o s e dt ol e v e r a g et h ed i r e c t i o n a l i t ya n dc o r r e l a t i o no fc o e f f i c i e n t s d i s t r i b u t i o nt oi m p r o v et h ec o d i n ge f f e c t i v e n e s s e x p e r i m e n t ss h o wt h a tc o m p a r e d 埘也o t h e ri m p r o v e ds p i h ta l g o r i t h m s ，t h ep r o p o s e d a l g o r i t h mr e n d e r sb e t t e rp s n rp e r f o r m a n c ea tt h ec o s to fl o n g e rc o d i n gt i m e t h ei m p r o v e d a l g o r i t h ms u i t sh u m a nv i s u a lc h a r a c t e r i s t i c s ，a n do f f e r sr e s t o r e di m a g e so fb e t t e rs u b j e c t i v e q u a l i t y i na l l ，t h ep r o p o s e da l g o r i t h ms e e m s t ob ea 1 1e f f e c t i v ei m a g ec o m p r e s s i o na l g o r i t h m k e y w o r d s ：i m a g ec o m p r e s s i o n ，w a v e l e t ，e z w , s p i h t i i 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得南京邮电大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意。 研究生虢荔塾蕴b 期：研究生签名：蟹塾纽圣，日期： 珥掣 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论文。本文电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南京邮电大学研 究生部办理。 研究生躲兹避新繇 日期：丝2 ：生：! 争 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 论文研究的背景及意义 第一章绪论 随着现代信息技术的飞速发展，需要存储和传输的信息量越来越多，数据的种类也是 层出不穷，如何高效存储和传输数据变得非常重要。图像是一种应用相当普遍的数据，几 乎每个领域都需要使用图像。在很多场合，图像可以比文字更直观的表达意思和说明情况， 因此图像是一种非常重要的数据。但图像与文字信息不同，图像信息需要大的存储容量和 宽的传输信道，尤其是在需要实现大规模图像数据或传输高分辨率实时图像序列的场合， 即使以现在较发达的计算机网络技术仍然难以满足原始数字图像存储和传输的需要。为了 减少图像存储容量和满足传输带宽的要求，必须对图像进行压缩，于是对图像数据的压缩 就成为技术进步的迫切需求，正是由于这种需求，使得图像压缩编码算法和技术成为近3 0 年来一个非常活跃的研究领域。 小波变换作为信号处理的一种手段，逐渐被越来越多领域的理论工作者和工程技术员 所重视和应用，尤其是在图像压缩技术的应用中取得了显著的效果。小波变换同传统的图 像压缩技术相比，产生了质的飞跃，具有十分巨大的生命力和广阔的前景。与此同时嵌入 式编码技术是新一代静态图像压缩技术标准j p e g 2 0 0 0 1 】的核心技术之一，在当今网络信息 时代它具有很大的研究价值和应用空间。同样，嵌入式零树小波编码是一个简单的算法， 可以直接产生嵌入式码流，不需要训练码本，且在所要求的精度下时可以在任意时刻结束 编码，因而有很好的发展和应用前景 2 1 。近几年来，国内外的学者们不断的研究发现这种 算法本身还存在着缺陷和不足，还有很多地方值得我们去改进和进一步研究，因此对其算 法的改进将是静态图像嵌入式编码算法领域的一个主要研究方向。 1 2 图像压缩的研究现状和发展 自1 9 4 8 年提出电视信号数字化后，就开始了对图像压缩编码的研究工作，至今已有 4 0 多年的历史了。上个世纪五十年代和六十年代的图像压缩技术由于受到电路技术等的制 约，仅仅停留在一些基础的技术研究上，对视觉特性也做了一些重要的工作。其中最基本 的霍夫曼( h u f f m a n ) 编码、预测编码和变换编码就产生于这个时期。1 9 6 9 年在美国召开的 第一届“图像编码会议标志着图像编码作为- - i - j 独立的科学领域诞生。 上个世纪的七十年代和八十年代，人们突破了s h a n n o n 理论的框架，重视对感知特性 1 南京邮电大学硕士研究生学位论文 第一苹绪论 的利用，使图像压缩技术取得了质的突破。这一阶段，图像压缩技术的主要成功集中在编 码技术上。变换编码以其压缩比高、误差影响小等明显优势成为了图像压缩编码的核心技 术之一。这一时期的代表静止彩色图像压缩编码国际标准( j p e g 标准) 就是以变换 编码为基础的。此外，图像压缩技术的发展与矢量量化技术有十分紧密的联系，矢量量化 方法在近十几年发展很快，为编码技术提供了灵活的应用空间。这些也为压缩技术的发展 提供了重要的因素。 近几年来，图像编码技术进入了一个新的时代，特别是二十世纪八十年代以后，随着 小波变换理论、分形理论、人工神经网络理论等的建立，人们开始突破传统的信源编码理 论。图像编码进入了一个崭新的时期。其中小波变换编码既保留了传统编码方法的优点， 能够消除图像数据的统计冗余，同时又提供了天然的多尺度、多分辨率的图像描述方法， 而且随着一些基于小波变换的高效率压缩经典算法 3 - s ) 的提出，使得基于小波变换的图像编 码成为人们研究的热点。 1 3 图像压缩的基本思想 图像压缩，是多媒体通信的核心技术。它设法去除原始图像中存在的冗余信息，从而 可用较少的数据来表征图像。从信息论的角度讲，图像作为一个信源，其数据是信息量和 信息冗余量之和。在静止图像和运动图像中，图像信息冗余量有多种不同形式，如空间冗 余、时间冗余、结构冗余、知识冗余和视觉冗余等，数据压缩的实质就是减少这些冗余量。 另外，在许多领域图像数据压缩允许有一定程度的失真，这就给提高压缩比提供了有利条 件。例如在一些应用领域，人眼常常是图像信息的最终接收者，如果在图像数据压缩上能 够充分利用入眼视觉特性，丢弃掉部分人眼不敏感信息，就可实现高压缩比，同时恢复图 像获得较高的主观质量。 总之，图像压缩的目的就是在给定畸变条件下使用尽量少的比特数来表征和重建原始 图像，以便更好地存储和传输图像。利用图像中存在的各种冗余，特别是利用图像数据中 存在的空域冗余、时域冗余和人类视觉特性，是可以做到这点的。 图像压缩系统的框图包括两部分：编码系统和解码系统。编码系统包括映射变换、量 化和熵编码三个步骤，如图1 1 所示。我们把映射变换、量化和熵编码统称为编码器，与 之相对应的熵解码、反量化、反映射变换称为解码器。 2 南京邮电大学硕士研究生学位论文 第一章绪论 码 流 ；l ： ； 解码系统 ； 图1 1 图像压缩系统框图 不管是编码系统还是解码系统，包含的三个步骤都是相互联系、相互制约的。在编码 系统中，映射变换是为了改变原始图像数据的特性，使其更有利于压缩；量化是用有限的 符号集来表示映射后的图像；熵编码是为量化后输出的每个符号分配二进制比特流。因此， 三个步骤是共同实现数据压缩的。解码系统就是编码的逆过程，它的熵解码、反量化及反 映射变换是和编码系统中的三个步骤相互对应，缺一不可的。所以编码系统和解码系统都 应该被看作一个整体。 1 4 图像压缩的基本方法 长期以来，基于像素的方法一直是图像编码的主流方法，它从消除图像数据的相关冗 余出发，编码实体是像素或像素块。这种基于数据统计特性的图像编码方法己经得到了广 泛的应用。下面就对一些基本的编码方法进行简要的介绍。 1 4 1 熵编码 常用的熵编袒- a j ( e n t r o p yc o d i n g ) 有游程编码( r c l ，r u nl e n g t hc o d i n g ) 、霍夫曼编码 ( h u f f m a nc o d i n g ) 和算术编码( a r i t h m e t i cc o d i n g ) - - 类。 游程编码的原理非常简单，将一行中颜色值相同的相邻像素用一个计数值和该颜色值 来代替。例如，a a a a b b e e e e e e d e e e e 可以用4 a 2 b 6 e l d 4 e 来表示。当一幅图像是由很多块颜色 相同的大面积区域组成的，那么采用游程编码的压缩比是惊人的。但是，如果图像中任何 两个相邻像素点的颜色都不同，用这种算法不但不能压缩，反而数据量增加一倍，所以游 程编码通常不单独使用。 3 南京邮电大学硕士研究生学位论文第一章绪论 霍夫曼编码是一种常用的编码方法，它的基本原理是频繁使用的数据用较短的码字来 代替，较少使用的数据用较长的码字来代替，每个数据的码字各不相同。这些码字都是二 进制码，且码长是可变的，所以霍夫曼编码是一种变长编码。更进一步的说，它是一种变 长最佳编码方法，这里的最佳指对相同概率分布的信源来说，它的平均码长比其它任何一 种编码方法都短。但是，霍夫曼编码必须知道信源的概率分布，这通常是无法做到的，只 能用统计的近似分布来代替，这就影响了编码性能。另外，由于计算霍夫曼码表时需要对 原始图像数据进行两次扫描，来进行概率统计和构造霍夫曼树编码，所以编解码速度都较 慢。但因该编码方法非常简单，所以应用很广泛。 算术编码是2 0 世纪8 0 年代发展起来的一种熵编码方法。理论上，算术编码方法与霍 夫曼编码方法都是最佳的，即已编码数据的长度都是最小的。算术编码的原理是任何一个 数据序列均可表示成0 和1 之间的一个间隔，该间隔的位置与输入数据的概率分布有关。 可以根据信源的统计特性来设计具体的编码器，也可以针对未知模型的信源设计能够自适 应其分布的算术编码器，并且这两种形式的编码器均可以用硬件实现。相关数据表明，算 术编码与霍夫曼编码方法的平均压缩效果是十分相似的，只是霍夫曼编码更快一些，但在 未知信源概率分布的大部分情况下，算术编码优于霍夫曼编码。应该指出的是，熵编码是 通过无损压缩来消除冗余信息，以达到据压缩的目的。 1 4 2 变换编码 变换编码( t r a n s f o r mc o d i n g ) 是通过信号变换来消除图像数据空间相关性的一种有效 方法。尽管图像变换本身不能对数据进行压缩，但由于变换后系数之间的相关性明显降低， 图像的大部分能量只集中在少数变换系数上，采用适当的量化和熵编码方法就可以有效地 压缩图像的数据量。而且图像经过某些变换后，系数的空间分布和频率分布特性与人眼的 视觉特性相符合，因此可以利用人类视觉系统的生理和心理特点来得到较好的编码系统。 变换编码通常是将空间域相关的像素点通过变换映射到另一个正交矢量空间( 变换域 或频域) ，使变换后系数之间的相关性降低。就数据压缩而言，所选择的变换方法最好能与 图像信号的特征匹配，此外还应从失真要求、实现的复杂度以及编码比特率等多方面来综 合考虑。k - l ( k a r h u n e n l o e v e ) 变换虽然是均方误差准则下的最佳变换，但其算法复杂度较 高，所以在实际编码工作中，人们常用离散余弦变换( d i s c r e t ec o s i n et r a n s f o r m ，简称为 d c t ) 。对大多数图像信源来说，d c t 变换是现行编码方法中最接近k - l 变换的方法。但 在低比特率条件下，基于d c t 变换的编码方法出现明显的方块效应，所以很难实现图像 4 南京邮电大学硕士研究生学位论文 第一章绪论 编码的高压缩比。小波分析由于在时域和频域同时具有良好的局部化特性，符合人眼的视 觉特性，近年来受到广泛的关注，且己经被采纳入新的图像编码国际标准中。 对变换后系数的编码，一般采用阈值编码加区域编码的形式。以d c t 为例，根据变 换系数的能量分布，可以将图像划分为不同的区域，其中变换后幅值较大的图像系数大多 集中在图像块的左上角。与其它系数相比，这些低频系数具有的能量最大，包括了图像的 大部分内容，在变换图像中的地位最重要，应使它们的量化误差最小。同样，对于图像块 的其它区域，也应采用与该区域相匹配的量化和编码形式。这种按能量分布不同对不同区 域采用不同量化编码的方法称为区域编码。另一方面，变换图像中有许多系数的幅值很小， 只具有原图像中很小比例的能量，对图像质量影响甚微，因此一般采用设定阈值的方法， 置小于阈值的变换系数为零，从而大大提高编码效率。经阈值编码和区域编码后，变换图 像的系数大部分为零，如何采用有效的方法将非零系数和零系数组织起来，在带有最少冗 余的同时保证最大的连零系数出现概率，是变换图像编码中的又一关键问题。在d c t 图 像编码中，对变换系数采用z 形( z i g z a g ) 排序非常巧妙的解决了这问题，但对有些图像 变换方法，这种方法并非最佳。应该强调的是，d c t 变换的优势在于能够减少大范围数据 的冗余，这也是变换编码的思想所在。 在一般图像中，对应于边缘轮廓的位置附近含有大量高频信息，它们相对于原始图像 是非常局部的，代表了图像数据的精细结构。按人眼的视觉特性，这些边缘轮廓信息对于 图像的主观质量影响很大，在编码时应给予特别考虑。然而，由于传统的正交变换时频局 部性很差，变换后的系数失去了对原始图像精细结构的描述，从变换图像得不到图像边缘 轮廓等信息，因此在量化编码时无法采用特殊的方法。而且在传统的变换图像编码方法中， 大多是靠丢弃高频系数来提高图像压缩比的，从而导致图像的边缘轮廓模糊，严重影响重 构图像的主观质量。另外，当提高编码压缩比时，图像会出现块效应，这是因为为了降低 变换算法的运算复杂度和提高编码效率，传统的图像变换采用了分块变换技术。图像块大， 相关性就高，压缩比就大，但块尺寸太大又会丢失数据的平稳性，从而引入误差，包括失 去高频细节、引入沿物体边界的噪声( r i n ge f f e c t ) 和可见的d c t 块边界效应( b l o c ke f f e c t ) 。 所以，传统的变换图像编码不适合高压缩比的应用场合，原因在于其变换方法不具有时频 局部性和全局变换特性。 1 4 3 预测编码 预测编码( p r e d i c t i v ec o d i n g ) 实际上是基于图像数据的空间冗余特性的，用相邻的己知 5 南京邮电大学硕士研究生学位论文第一章绪论 像素( 或像素块) 来预测当前像素( 或像素块) 的值，然后再对预测误差进行量化和编码，这些 相邻像素或像素块可以是同行的，也可以是前几行的，相应的预测编码分别称为一维和二 维预测。预测编码的关键在于预测算法的选取，这与图像信号的概率分布有很大关系。实 际中常根据大量的统计结果来设计最佳的预测器，有时还使用自适应预测器以刻画图像信 号的局部特性，从而提高编码效率。预测编码有线性预测和非线性预测两大类。线性预测 编码又称为差分脉冲预测编码调制，即d p c m ( d i f f e r e n t i a lp u l s ec o d em o d u l a t i o n ) 。一般采 用像素预测形式的d p c m ，其优点是算法简单，易于硬件实现。缺点是对信道噪声及误差 很敏感，会产生误码扩散，使图像质量大大下降，而且其压缩比很低，一般很少单独使用， 要结合其它编码方法。 1 4 4 矢量量化 矢量量化( v e c t o rq u a n t i z a t i o n ，简称为v q ) 是新发展起来的一种数据压缩技术，按照香 农的率失真理论 9 1 ( r a t ed i s t o r t i o nt h e o r y ) ，图像矢量量化的性能要优于标量量化的性能。 矢量量化性能有可能任意接近率失真函数的理论极限。 矢量量化是用k 个样本形成一个k 维空间砂中的一个矢量，然后对此矢量进行量化， 只传输或存储矢量地址，因而可以大大提高压缩效率。矢量量化总是优于标量量化，因为 矢量量化时有效利用了矢量中各分量间的四种相关性( 线性依赖性、非线性依赖性、概率密 度函数的形状和矢量维数) 来去除冗余度。矢量量化是标量量化的多维扩展。 基于v q 的图像编码方法是利用相邻像素数据之间的高度相关性，将输入的图像数据 序列分组，每一组m 个数据被描述成一个有m 个元素的矢量。例如，将二维图像分成若干 个m x n 的矩阵块，每一个矩阵块内的数据排列成一个m = m n 个元素的一维矢量。实 际的矢量量化图像系统中编码器和解码器内置有相同的码本( c o d e b o o k ) ，码本由所有可能 的矢量值集合的有序子集组成。v q 的码本是根据训练矢量集合来设计的，常用的是l b g 算法【10 1 。编码器根据特定的距离准则( 或称代价函数) 在码本中对输入图像进行矢量匹配， 然后对匹配码的码字序号进行编码，从而实现了由一个矢量所需要的比特数到一个码字序 号所需要比特数的压缩。显然矢量量化是一种信息有损的压缩编码方法，但它可以获得较 高的压缩比。其解码方法比较简单，只是根据接收到的序号，从与编码器一致的码本中找 到与该序列对应的码字，实现对原始数据的近似重现，但编码端计算量很大。为了减小失 真，码本的体积自然增大，必然使得矢量匹配的搜索时间增长。另外，由于对原始数据分 块，在高压缩比下，会出现方块效应和边缘突出。 6 南京邮电大学硕士研究生学位论文 第一章绪论 1 5 主要研究工作和论文安排 本文的主要贡献包括针对原始小波变换存在大量卷积，计算复杂的问题，采用提升方 案构造小波基，降低变换复杂度；图像经过小波变换后，最低频子带包含了图像的大部分 信息，本文提出了频率优先性编码概念，对低频子带单独编码；根据人类视觉系统( h u m a n v i s u a ls y s t e m ，简称为h v s ) 的特点，采用视觉加权系数来重新设定各个子带的系数的大小， 使得对图像的量化编码方式更贴近人类视觉系统；对s p i h t 算法进一步分析发现各高频子 带小波系数的分布有一定的方向性和相关性，提出了一种新的系数扫描方法，进一步提高 了编码效率。 通过用最近的文献中提出的改进s p i h t 算法和本文算法分别对标准测试图像l e n a 和 b a r b a r a 图像进行压缩比较，对不同码率下重构图像的分析得出以下结论：在相同码率下， 本文算法虽然比较耗时，但p s n r 略有增加，且在编码的量化过程中更贴近人类视觉系统， 重构图像的效果更好，总体来说是一种比较有效的算法。 本文的章节安排如下： 第一章是绪论部分。介绍了论文的研究背景和意义，回顾了图像压缩技术的研究历史 和现状。并介绍了图像压缩编码的基本知识，概述了本论文的主要研究工作。 第二章介绍了小波变换的基本知识。包括对小波变换的发展历史的回顾，连续小波和 离散小波变换的基本原理的介绍，然后介绍多分辨率分析和小波分解与重构的快速算法一 m a l l a t 算法，最后介绍了把小波变化用于图像压缩时应该考虑的几个问题。 第三章进一步介绍了小波变换在图像压缩上的应用。详细介绍了基于小波变换的图像 压缩的经典算法：嵌入式零树小波编码( e m b e d d e dz e r o - t r e ew a v e l e t ，简称为e z w ) 算法及 其改进形式分层树集分割编码( s e tp a r t i t i o n i n gi nh i e r a r c h i c a lt r e e s ，简称为s p h i t ) 算法。 包括这两种算法的提出背景、原理、编码步骤和各自的特点。 第四章根据前面的理论基础，进一步对e z w 和s p i h t 算法进行分析，发现了其自身 所存在的一些不足，并针对这些不足提出了一种改进算法，并给出了实验结果和分析。 最后是对全文的总结和展望，提出了需要进一步解决的问题和新的研究方向。 7 南京邮电大学硕士研究生学位论文第二章小波变换理论简介 第二章小波变换理论简介 小波变换理论是不同领域的科学家们共同努力和探索的结果，如今已经具有坚实的数 学理论基础和广泛的应用背景，目前正在日新月异的蓬勃发展。在数学界，小波分析被看 作是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 分析的地方，现在都可以 用小波分析取代。目前，小波变换已被应用于信号处理、图像处理、模式识别、语音识别、 量子物理、地震勘测、流体力学、电磁场、c t 成像、机械故障诊断与监控和数值计算等 方面，成为了科学研究和实际应用中的强有力的数学工具i l 。 本章将通过分析f o u r i e r 变换、短时f o u r i e r 变换及其缺陷来研究连续小波变换和离散 小波变换。并从多分辨率分析入手推导一维m a l l a t 算法和用于图像处理的二维m a l l a t 算法。 2 1 傅里叶变换及其局限性 在传统的信号分析中f o u r i e r 变换占据了举足轻重的地位。f o u r i e r 变换定义了“频率” 的概念，用它可分析信号能量在各个频率成分中的分布情况。 对信号妁，其f o u r i e r 变换定义为： f ( w ) = i f ( t ) e - 少 d t ( 2 1 ) f o u r i e r 逆变换定义为： f ( t ) = 亡if ( c o ) e m d o ) ( 2 2 ) z 7 一 一个波形的f o u r i e r 变换的实质是：把这个波形分解成许多不同频率的正弦波之和，如 果这些正弦波加起来成为原来的波形，那么我们就确定了这个波形( 即信号) 的f o u r i e r 变换。 如果信号不是周期函数，那么它的f o u r i e r 变换将是频率的一个连续函数，即f ( t ) 可以用全 部频率的正弦波之和来表示。所以f o u r i e r 变换可以看作是时间函数在频率域上的表示。事 实上f o u r i e r 变换频率域包含的信息和原来函数所包含的信息完全相同，不同的仅是信息的 表示方法。 虽然傅立叶变换能够将信号的时域特征和频域特征联系起来，能分别从信号的时域和 塑室墅皇奎堂堡主婴窒竺兰垡笙奎翌三里尘鎏銮垫里笙笪坌 频域观察，但不能把二者有机的结合起来。这是因为信号的时域波形中不包含任何频域信 息。而其傅立叶谱是信号的统计特性，从其表达式也可以看出，它是整个时间域内的积分， 没有局部化分析信号的功能，完全不具备时域信息。也就是说，对于傅立叶谱中的某一频 率，不知道这个频率是在什么时候产生的。这样在信号分析中就面临一对最基本的矛盾： 时域和频域的局部化矛盾。 2 2 短时傅里叶变换 短时f o u r i e r 变换由g a b o r 首先系统地使用，其基本思想如下：把信号划分成许多小的 时间间隔，用傅里叶变换分析每一个时间间隔，以便确定该时间间隔存在的频率。为了达 到时间域上的局部化，f o u r i e r 变换的基本变换函数之前需要乘上一个时间上有限的时限函 数w ( t b ) ，然后用它们作分析工具，这样，p 一刖起频限作用，w ( t 一6 ) 起时限作用，它们 合在一起就起到了时频双限制作用。其基本变换方式为： g ，( 6 ) = i p 删f ( t ) g ( t - b ) d t ( 2 3 ) 当窗口函数取为g a u s s 函数时短时f o u r i e r 变换又称为g a b o r 变换。 虽然短时傅立叶变换在一定程度上克服了标准傅立叶变换不具有局部分析能力的缺 陷，但是不能改变窗口的形状，时间分辨率是固定的。因此，它不能敏感地反映信号的变 化，只是一种单一分辨率的分析。用它分析平稳信号还可以，但对非平稳信号，它不能兼 顾。 2 3 小波变换 2 3 1 小波变换的提出 小波理论是上世纪8 0 年代迅速发展起来的应用数学分支，是对f o u r i e r 分析的重要补 充和改善，是传统傅里叶分析发展史上的里程碑。 1 9 8 0 年法国地球物理学家m o r l e t 仔细研究了g a b o r 变换，对f o u r i e r 变换和短时f o u r i e r 变换做了深入研究，创造性地提出“小波 的概念，并建立了以其名字命名的m o r l e t 小波， 该方法在地质数据处理中取得了巨大的成功。小波的基本思想是通过一个母函数在时间上 的平移和尺度上的伸缩，获得一种能自动适应各种频率成分的有效的信号分析手段。小波 变换与f o u r i e r 变换非常相似，其基本的数学思想来源于经典的调和分析，都是将信号与一 9 南京邮电大学硕士研究生学位论文第二章小波变换理论简介 个具有两个参数的函数族作内积运算。不同的是f o u r i e r 变换以三角函数作为基底对信号进 行展开，小波变换则以局部化函数所形成的相似函数作为基底对信号进行展开。小波变换 发展了短时f o u r i e r 变换的局部化思想，其窗i z l 可随频率增大而缩小，随频率减小而放大。 在分析非平稳时变信号时，既能用持续时间很短的高频基函数去分析信号的高频成分，又 能用持续时间相对较长的低频基函数去分析信号的低频成分。小波变换在时域、频域内具 有良好的局部分析特性，在信号分析、图像处理、数据压缩、计算机视觉等很多领域得到 了广泛的应用。 小波变换是一种新的分析方法，它的产生、发展、完善和应用始终受惠于计算机科学、 信号处理、图像处理、应用数学、物理学、地球科学等众多科学领域和工程技术应用领域 的专家、学者和工程师们的共同努力。正因为如此，小波变换现在已成为科学研究和工程 技术应用中涉及而且及其广泛的一个热门话题。小波变换的定义应满足这样的条件：小波 基尽可能由少数的几个函数生成；理想的小波基应是紧支的。类似于f o u r i e r 分析，小波分 析分为两种变换，即连续小波变换和离散小波变换【1 2 】。 2 3 2 连续小波变换 连续的小波变换的形式化定义最早由m o r l e t 和g r o s s m a n 提出，其定义如下： 设汐l 2n l , 且；( o ) = o ，则按如下方式生成的函数族 仡，。) ： 9 口，。( f ) = i 口i 一号伊( t - 口b ) 口，6 足口。( 2 4 ) 叫连续小波，驴是基本小波， 纪，。 是按( 2 4 ) 式给出的连续小波，对于缈r ( r ) ，i - 言号f 的 连续小波变换哆( 6 ，口) 定义为： v e ，( b 秘= ( 触6 ) ：| a l 饨) 9 洋矽 ( 2 5 ) 在( 2 5 ) 式中，口 0 是尺度因子，b 是位移因子，b r ；其中伊r ( r ) 且满足条件： q = 肾认o o ( 2 6 ) 上式中汐 ) 是缈( f ) 的傅氏变换，该条件称为允许条件。小波变换的变换基的选择必须 满足( 2 6 ) 。傅氏变换中，变换基是固定的，而小波变换基是多变可选的，根据不同的需要 选择适当的小波基。在具体应用中，根据原函数厂( f ) 的特点来选择小波变换基9 0 ) ，使得 1 0 南京邮电大学硕士研究生学位论文 第二章小波变换理论简介 小波变换能更好的反映，( f ) 的特征。 2 3 3 离散小波变换 信号经过连续小波变换后，是存在冗余的。在实际应用中，我们不能用计算机来实现 连续小波变换。因此，需要将其离散化。离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m ，简称 为d w t ) 采用对数函数量化尺度参数，而时间参数则依赖于尺度函数，对于不同的应用， 对数的底可以取不同的数，最常用的是取2 。如果采用以2 为底的对数变化，则在时间轴 上的采样速率也以2 为因子进行变化。 将连续小波的尺度和平移参数离散化，即令 口= 矿，6 = 慨旷，a o l , b o o , m , n e z ( 2 7 ) 即可得到离散小波 ，2 赤甲学 ( 2 - 8 ) 则信号珩) 的离散小波变换定义如下： 。眄2 赤弘尸华舻( 矾) ( 2 9 ) 由于我们处理的数字图像是一种离散的二维信号，因此要对其进行二维离散小波变 换。二维离散小波变换和我们熟悉的二维离散傅立叶变换类似，只需要对数字图像在行和 列方向上分别做一维的离散小波变换即可完成。 2 4 多分辨率分析 小波既然被称为“数学显微镜 ，那么小波变换必须具备如下特点： ( 1 ) 当尺度因子a 较大时，视野宽而分辨率低，只能观察概貌； ( 2 ) 当尺度因子a 较小时，视野窄而分辨率高，便于观察细节部分； ( 3 ) 不同a 值下分析的品质因数( 中心频率与带宽的比值) 保持不变。 这种由粗到精对事物逐级分析的方法就称为多分辨率分析。多分辨分析又称为多尺度 分析，它是建立在函数空间概念上的理论，但其思想的形成来源于工程。其创始者s m a l l a t 是在研究图像处理问题时建立这套理论的。当时人们研究图像的一种很普通的方法是将图 像在不同尺度下分解，并将结果进行比较，以取得有用信息。m e y e r 正交小波基的提出， 南京邮电大学硕士研究生学位论文 第二覃小坡燹抉理论简介 使得m a i i a t 想到是否能用正交小波基的多尺度特性将图像展开，以得到图像不同尺度间的 “信息增量1 3 1 ”。这种想法导致了多分辨率分析理论的建立。多分辨率分析不仅为正交小 波基的构造提供了一种简单的方法，而且为正交小波变换的快速算法提供了理论依据。其 思想又同多采样率滤波器不谋而和，使我们又可将小波变换同数字滤波器的理论结合起 来。因此多分辨率分析在正交小波变换理论中具有非常重要的地位。 下面给出小波变换的多分辨率分析定义，它为图像压缩提供了理论基础。 首先定义空间p ( r ) 中的一系列闭子空间 巧) 越称为r ( r ) 的一个多分辨率分析或逼 近，并且这些空间必须满足如下条件： ( 1 ) 上完整性 0 圪= 厶( r ) ； ( 2 ) 下完整性 n 圪= o ； 埘e z ( 3 ) 尺度不变性x ( t ) 圪x ( 2 ”f ) ； ( 4 ) 位移不变性x ( t ) z ojx ( t - n ) z o ，nez ； ( 5 ) r e i s e 基存在一个基缈，使得 甲( f 一船) ，z z 是的r e i s e 基； ( 6 ) 函数空间的逐级剖分性匕c c c 眨，c ckc c c 圪。 2 5m a l l a t 快速算法 m a l l a t 算法是一种快速离散小波变换算法，它将滤波与亚采样结合在一起，用于计算 离散小波变换系数。 设k 是由函数系 2 一趁r p ( 2 。卜七) ，k e z 生成的，k = k + 。o 彬+ l ，对做j 级分解得： = w 1 0 形2 0 形3 0 0 - ，0 y ，( 2 1 0 ) 设有函数x ( t ) ，它在空间投影得 x o ( f ) = p o x ( t ) = 口。缈。( f ) ( 2 11 ) 可将其分解到嘶，暖，巧空间，即将x o ( t ) 的一组系数( o 分解为系数集 碰n ，掣，i = 1 ，2 ，kez ，分解方程为： 1 2 堕塞塑皇奎堂堡主翌垄竺堂篁笙茎 f 口) - h ( n - 2k ) 口：” j 疗 id ) = g ( n - 2 k ) 口： 第二章小波变换理论简介 ( 2 1 2 ) 一般合成公式为 口= h ( n - 2 k ) 口+ g ( n - 2 k ) d ( 2 1 3 ) kk 分解公式( 2 1 2 ) 相当于先对输入序列同滤波器的冲击相应卷积，再进行一次亚采样，只 保留偶数样点。合成公式( 2 1 3 ) 相当于先对输入序列进行一次插值，再通过滤波器。这组计 算离散小波变换和反变换的分解和合成公式即( 2 1 2 ) 和( 2 1 3 ) 就称为m a l l a t 快速算法。 图2 1 中所示的是一维小波变换的m a l l a t 算法的分解和重构过程；图2 2 中所示的是 二维小波变换的分解和重构示意图。 图2 1 一维小波变换的分解和重构 图2 2 二维小波变换的分解和重构 因此，我们可以看到进行一次小波变换的结果便是将图像分解为一个低频子带( 水平方 向和垂直方向均经过低通滤波) l l 和三个高频子带分别为：水平高通垂直低通子带，用l h 表示；水平低通垂直高通子带，用h l 表示：水平高通垂直高通子带，用h h 表示。分辨 率为原来的1 2 ，频率范围各不相同。第二次小波变换时只对l l 子带进行，进一步将l l 子带分解为l l 2 、l h 2 、h l 2 和h h 2 ，分辨率为原来的1 4 ，频率范围进一步减半，以此 类推。所以，进行一次小波变换得到4 个子带，进行m 次分解就得到3 m + 1 个子带，如图 2 3 所示。 1 3 南京邮电大学硕士研究生学位论文第二章小波变换理论简介 其中处于同一分解层的子带称为同尺度( 不同方向) 子带，处于不同分解层，但频率范 围成比例变化的子带称为同方向( 不同尺度) 子带，对应着原图像中不同方向的纹理和边缘 信息。当图像实现了小波的多分辨率分解后，并不意味着图像已实现了压缩。事实上，小 波变换只给图像压缩提供了一个好的图像表示形式，而数据总量并未减少。为了达到高压 缩比的目的，还应对变换后的系数进行分析处理，并进行适当的取舍、量化和编码。 l lh l l h h h l l 2h l 2 h l l l h 2h h 2 l h l h h l ( a ) 原图( b ) 一级小波分解( c ) 二级小波分解 图2