（信号与信息处理专业论文）基于方向提升小波变换的图像编码技术研究.pdf

j l 作 英文题目：工h 星b 星墨星垦 堡hq 旦i 盟垒g 星g q 鱼i 堕g 坠垒墨星鱼q b 旦i ! 星曼! i q n 垦! ! yl i 鱼i n 堡垒墨曼亟 肋v e l e tt r a n s f o i m 主题词：图像压缩编码、s p i h t 、方向小波变换、提升算法、无链表编码 k e y w o r d s ：i m a g ec o m p r e s s i o nc o d i n g ，s p i h t , d i r e c t i o n a lw a v e l e tt r a n s f o r m ，l i f t i n gw a v l e t t r a n s f o r m ，l i s t l e s sz e r o t r e ec o d i n g 南京邮电大学硕士研究生论文 摘要 摘要 近年来，随着计算机和因特网的普及，多媒体已经渗透到人们的生活当中，也成为当 前计算机行业最热门的技术之一。多媒体技术和通讯技术的日益发展，使得多媒体娱乐、 多媒体通信、数字音频广播和高清晰度电视等各类实际应用对信息数据存储和传输的要求 不断提高，因此，多媒体技术和i n t e m e t 的应用发展所面临的主要问题之一就是解决对庞 大图像数据信息的表示、传输和存储。为了达到令人满意的视觉和传输效果，对图像数据 进行有效的压缩编码，是需要解决的关键技术之一。 本文首先对视频压缩技术的发展、基于小波变换图像压缩编码算法的现状以及本课题 研究的意义进行了介绍，并对小波变换原理进行了比较全面的阐述，在此基础上研究了两 种经典的基于小波变换的图像压缩编码算法e z w 、s p i h t 。为了达到硬件应用的目标， 本文在深入分析研究小波变换、s p i h t 实现方法以及现有各种改进算法性能的基础上，从 改进小波变换和s p i h t 实现方法两个方面，分别提出了两种相应的改进算法。首先通过引 入了方向提升小波变换，改进变换的性能和实现速度，其次通过采用无链表l s p i h t 图像 压缩编码算法，降低对存储空间的需求。并将这两种算法相结合，得到一种新的综合算法 基于方向提升小波变换的无链表l dl s p i h t 图像压缩编码算法。最后，为了验证本 文算法的性能与实用性，本文分别基于软件仿真、d s p 硬件平台对算法进行了实验测试， 并详细分析说明了算法性能。实验结果表明，本文提出的这种新的算法，降低了对存储空 间的需求，提高了编码性能。本文最后对全文工作进行了总结和回顾，并重点指出了今后 需要继续进行的相关研究工作及方向。 关键字：图像压缩编码、s p i h t 、方向小波变换、提升算法、无链表编码 南京邮l 【l 火学硕士研究生论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，a l o n gw i t ht h ep o p u l a r i z a t i o no fc o m p u t e ra n di n t e m e t ，m u l t i m e d i ah a s b e c o m ea ni n d i s p e n s a b l ep a r to fh u m a no r d i n a r yl i f e a st h er a p i dd e v e l o p m e n to fm u l t i m e d i a t e c h n o l o g y , m u l t i m e d i ae n t e r t a i n m e n t ，m u l t i m e d i ac o m m u n i c a t i o n ，d i g i t a la u d i of r e q u e n c y b r o a d c a s ta n dh i g hd e f in i t i o nt e l e v i s i o ne t c ，t h e s ep r a c t i c a la p p l i c a t i o n se n h a n c et h er e q u i r e m e n t o fi n f o r m a t i o nd a t as t o r a g ea n dt r a n s m i s s i o n o n eo ft h em a i np r o b l e m s ，w h i c hc o n f r o n t e dw i t h l m u l t i m e d i at e c h n o l o g y , t h ea p p l i c a t i o n sa n dd e v e l o p m e n t so fi n t e r n e t ，i st os o l v et h ed e n o t a t i o n ， t r a n s m i s s i o na n ds t o r a g eo ft h ei m a g ed a t ai n f o r m a t i o n i no r d e rt oo b t a i ns a t i s f y i n gv i s i o na n d t r a n s m i s s i o ne f f e c t ，e f f e c t i v ei m a g ed a t ac o m p r e s sc o d i n g ，i st h ek e yt e c h n o l o g yt os o l v e i nt h i st h e s i s ，d e v e l o p m e n to fv i d e oc o m p r e s s i o nt e c h n o l o g y , t h ec u r r e n ts i t u a t i o no fi m a g e c o m p r e s s i o na l g o r i t h m sb a s e do nw a v e l e tt r a n s f o r m ，a sw e l la st h es i g n i f i c a n c eo ft h i st h e s i sa r e i n t r o d u c e d t h en a t u r ea n dt h e o r yo fw a v e l e tt r a n s f o r ma r ea l s od e s c r i b e dc o m p r e h e n s i v e l y a f t e rt h i s ，t w oc l a s s i ci m a g ec o m p r e s s i o na l g o r i t h m su s i n gw a v e l e tt r a n s f o r ma r es t u d i e dw h i c h a r ee z wa n ds p i h t o nt h eb a s i so far e s e a r c ho nw a v e l e tt r a n s f o r m ，s p i h tm e t h o da n dt h e i r i m p r o v e da l g o r i t h m se x i s t i n g ，t h et h e s i sp r o p o s e dt w oi m p r o v e da l g o r i t h m sr e s p e c t i v e l yf o rt h e p u r p o s eo fi m p r o v i n gp e r f o r m a n c ef o rw a v e l e tt r a n s f o r ma n ds p i h tt om e e tt h ed e m a n do f h a r d w a r ea p p l i c a t i o n s f i r s t l y , p e r f o r m a n c ei s i m p r o v e da n di m p l e m e n t a t i o ni ss p e e du pb y i n t r o d u c i n gt h et e c h n o l o g yo fd i r e c t i o n a ll i f t i n g b a s e dw a v e l e tt r a n s f o r m s e c o n d l y , t h i st h e s i s i n t r o d u c e sl i s t l e s ss p i h ta l g o r i t h mf o ri m a g ec o m p r e s s i o nt or e d u c et h es i z eo fs t o r a g es p a c e n e e d e d t h e n ，d i r e c t i o n a ll i f t i n g b a s e dw a v e l e tt r a n s f o r ma n dl s p i h ta l g o r i t h ma r ec o m b i n e d t o g e t h e r , w h i c hl e a dt o an e wc o m p r e h e n s i v em e t h o d - - l i s t l e s ssp i h tb a s e do nd i r e c t i o n a l l i f t i n g b a s e dw a v e l e tt r a n s f o r mf o ri m a g ec o m p r e s s i o n t h i r d l y , s i m u l a t i o n sa r ec o n d u c t e do n t h ep l a t f o r mo fd s pa n ds o f t w a r et o v e r i f yt h ep e r f o r m a n c ea n dp r a c t i c a la p p l i c a t i o no ft h e a l g o r i t h m sp r o p o s e di nt h i st h e s i s a n a l y s i si sa l s og i v e n s i m u l a t i o nr e s u l t ss h o wt h a tt h en e w a l g o r i t h mn o to n l yr e d u c e ss t o r a g es p a c e ，b u ta l s oi m p r o v e sc o d i n gp e r f o r m a n c e a tt h ee n do f t h i st h e s i s ，s u m m a r i z a t i o n sa r eg i v e na n dd i r e c t i o no fo u rf u r t h e rr e s e a r c hi sp o i n t e do u t k e y w o r d s ：i m a g ec o m p r e s s i o nc o d i n g ，s p i r i t , d i r e c t i o n a lw a v e l e tt r a n s f o r m ，l i f t i n gw a v e l e t t r a n s f o r m ，l i s t l e s sz e r o t r e ec o d i n g 南京邮电入学硕二j ：研究生论文 目录 目录 摘要i a b s t r a c t i i 目录i i i 第一章绪论1 1 1 引言。l 1 2 视频压缩技术的发展1 1 3 基于小波变换图像压缩编码算法的现状2 1 4 本课题研究的意义3 1 5 本文的工作内容与结构安排。4 第二章小波基本理论及基于小波变换的图像编码6 2 1 小波变换原理7 2 1 1 连续小波变换7 2 1 2 离散小波变换8 2 1 3 提升小波变换第二代小波变换一8 2 2 基于小波变换的图像编码l l 2 2 1 嵌入式零树小波编码算法e z w 1 1 2 2 2 分层小波树集合分割算法s p i h t 。1 4 2 3 本章小结1 6 第三章基于方向提升小波变换的m l ds p i h t 算法研究1 7 3 1 方向小波的提出与发展1 7 3 1 1 图像方向信息的重要性1 7 3 1 2 方向小波研究与发展1 7 3 2 方向提升小波变换算法的研究与实现1 8 3 2 1 方向提升小波变换的算法研究l8 3 2 2 改进方向提升小波变换算法的实现1 9 3 3 基于方向提升小波变换的m l d s p i h t 算法实现：2 6 3 4 本章小结2 7 第四章基于方向提升小波变换的l d l s p i h t 算法研究2 8 i i i 南京邮电大学颀士研究生论文 目录 4 1 传统s p i f i t 算法编码结构的缺陷2 8 4 2 无链表l s p i t l t 编码算法的研究与实现2 9 4 2 1 无链表压缩编码的算法研究2 9 4 2 2 改进无链表l s p i h t 编码算法的实现31 4 3 基于方向提升小波交换的l d l s p i h t 算法实现3 3 4 4 本章小结3 4 第五章l d l s p i h t 算法的d s p 实现研究3 5 5 1 算法d s p 实现的硬件系统平台介绍3 5 5 2 基于d s p 嵌入式平台算法l d l s p i h t 的代码优化3 6 5 2 1 嵌入式程序优化遵循的原则3 6 5 2 2 算法和数据结构的优化3 6 5 2 3 代码优化3 7 5 3 算法l d l s p i h t 的移植实现。4 0 5 4 本章小结4 2 第六章实验结果与分析4 3 6 1 实验平台、参数设定4 3 6 2 改进的方向提升小波变换算法l ds p i h t 实验结果与分析4 3 6 3 基于无链表的改进l s p i h t 实验结果与分析4 8 6 4 基于方向提升小波变换的l d l s p i h t 实验结果与分析5 3 6 5 算法l d l s p i h t 的d s p 实现实验结果与分析5 8 6 6 本章小结6 0 第七章总结与展望6 2 7 1 全文总结6 2 7 2 未来工作展望6 3 参考文献6 4 致谢j 6 7 i v 南京邮电火学硕士研究生论文 1 1 引言 第一章绪论 近年来，随着计算机和因特网的普及，多媒体作为先进计算机技术和视频 通信等技术集成的产物，已经渗透到人们的生活当中，也成为当前计算机行业 术之一。目前，多媒体计算机信息的数据来源主要包括：文字、语音、静止图 像、电影、动画、图形等等。而图像信息能给人以直观而具体的物体形象，是 界重要信息的来源，因此图像也己成为最为重要的数据类型，图像的处理与分 发展成为现代信号处理技术中专门的分支学科。由于图像信息丰富、数据量大 5 1 2 5 1 2 大小的真彩色图像，如果每像素占三个字节，其数据量就接近1 m b ， 电视( h d t v ) 的码率在1 2 g b s 以上，即使传输媒质是光纤，也会被迅速淹没。 人们对视觉效果的要求越来越高，使图片的信息数据量也越来越大，单纯靠增加存储器容 量、提高信道带宽以及计算机处理速度等方法来解决，显然是不现实的。一幅图像，虽然 含有大量的信息数据，但同时也存在大量的冗余信息。因此，冗余数据的消除或减少便成 为图像数据压缩的理论基础和依据。如何有效的组织、存储、传输和恢复图像数据，探索 更有效、更高压缩比的图像编码技术，成为现代信息处理技术中的关键任务之一。 1 2 视频压缩技术的发展 自1 9 4 8 年提出电视信号数字化以来，视频压缩技术发展至今已有5 0 多年的历史。1 9 6 6 年j b on e a l 对比分析了d p c m 和p c m 算法并公布了用于电视信号的实验数据，1 9 6 9 年 进行了线性预测编码的实际试验。7 0 年代开始进行帧间预测编码的研究。8 0 年代初开始 对做运动补偿( m c ) 所用的运动估计( m e ) 算法进行研究。h c a n d r e w s 等人于1 9 6 8 年 提出了变换编码，采用的是二维离散傅立叶变换，此后相继出现了采用其它变换方法的编 码技术，其中包括二维d c t 等。 于1 9 8 8 年形成草案、1 9 9 0 年通过的i t u th 2 6 1 1 】建议是视频编码技术走向实用化的 重要里程碑，它是视频编码4 0 年研究成果的结晶。之后于9 0 年代初相继提出的m p e g 1 、 m p e g 2 、h 2 6 3 、m p e g 4 i - 3 1 等标准和建议都是在h 2 6 1 的基础上发展和改进的。这些国 际标准普遍采用的混合编码技术是当今最实用的高效编码技术，已经成为当今视频编码算 南京邮电大学硕研究生论文第一章绪论 法的主流，得到了广泛的应用。其中，m p e g 1 制定于1 9 9 2 年，可适用于不同带宽的设备， 如c d r o m ，v i d e o c d ，c d i ，最高可达1 1 5 m b p s ；m p e g 2 制定于1 9 9 4 年，设计目标 是提供高级工业标准的图像质量以及更大范围的传输码率，范围从低清晰度的会议电视、 v c d 等1 - 2 m b p s ，标准电视的3 1 0 m b p s ，到高清晰度电视的1 0 1 5 m b p s ，在地面广播、有 线电视网、电缆网络以及直播卫星( d i r e c tb r o a d c a s ts a t e l l i t e ) 提供广播级的数字视频。1 9 9 5 年i t u t 为甚低码率视频编码制订了h 2 6 3e 2 】建议；1 9 9 8 年m p e g 专家组制定了基于内容 的视频编码方案m p e g 4 【3j ，它不仅获得高效的视频、音频编码，更加注重多媒体系统的 交互性和灵活性，同时针对网络视频传输，提供了可分级视频编码和多项抗误码措施，取 得了更广泛的应用。 视频编码标准的制定推动了视频编码技术的实用化和产业化，同时随着技术的不断进 步，新的视频编码标准h 2 6 4 t 3 1 也于2 0 0 3 年5 月公布。h 2 6 4 标准是i t u t 的v c u g ( 视 频编码专家组) 和i s o i e c 下属的m p e g 联合开发的一个新的数字视频编码标准，侧重于 i p 和无线网络上的应用，通过采用帧内预测，去方块效应滤波器，整数变换等新技术，进 一步提高了压缩效率，及抗误码性能和交互性等。 1 3 基于小波变换图像压缩编码算法的现状 图像压缩编码长期以来利用离散余弦变换( d c t ) 1 4 1 作为变换编码的主要技术，并已有 各种标准如j p e g 等问世。然而利用d c t 作为主要技术的变换编码方法存在着明显的方块 效应。这是因为在d c t 编码中图像被分成8 8 的方块，每块一般独立进行变换和量化编 码，编码过程中存在两种误差：1 、低频端的量化误差；2 、对高频信息的舍弃造成高频数 据的量化误差，而各相继块的量化误差未必相同，因此在这些边界处就可能产生很大的幅 度差异，人眼对此非常敏感，这就是令人头痛的“方块效应”。此外，基于d c t 变换的编 码方法是靠丢掉一部分信息( 如某些高频分量) 来求得较高的压缩比，它是一种各向同性 的变换编码方法。这种由于其没有考虑人的视觉系统的特性，如人眼对边缘轮廓的敏感性， 人眼对不同方向的图像信息有不同的敏感性的特点，因此，在保证较高图像质量的前提下， 利用离散余弦变换进行图像编码进一步提高图像压缩比较困难。 8 0 年代末，小波理论 5 1 被引入到图像编码领域，为图像编码技术的发展注入了巨大的 活力。由于具有描述非平稳信号【6 l 的独特优点，小波变换可将图像信号分解成不同空间分 辨率、不同频率特征和方向特征的子图像信号，便于在失真编码中综合考虑人的视觉特性， 也利于图像的逐渐浮现传输。另外，它作用于图像的整体，在有效去除图像的全局相关性 塑塞唑! 垒查堂堡! ：堕塑圭丝苎 笙二望堕堡 的同时，使量化误差分散到整个图像中，避免了d c i 变换编码带来的方块效应【7 1 。小波变 换编码能有效的解决方块效应，从而使得小波变换图像编码成为当前图像编码研究的主要 方向。 迄今为止，国内外学者已经提出了多种结合不同量化和编码措施的基于小波的编码算 法，普遍获得在相同性能下较传统的d c t 变换编码更高的压缩比，但是各种算法各有优缺 点，适合于一切图像分解的最优的小波基和编码方法是不存在的，面向问题选择满足实际 需要的方法才是明智之举。 最常用的小波基是d a u b e c h i e s 8 】紧支集规范正交小波基，这一类小波基及其对应的滤 波器组具有两两正交、精确重构、有限支集和具有一定正则性等优良数学特性，有利于图 像处理，但是，此类小波基是非对称的，在有损编码中会引起重构信号的相位失真。于是 c o h e n 和d a u b e c h i e s 等人引入了双正交小波基。对称的双正交小波基可以满足图像处理中 比较严格的线形相位特性要求，不仅可以减少或消除重建图像的边缘失真，而且在级联的 塔型结构中无需相位补偿，同时支集较短，便于快速实现和进行边界处理，适合用于图像 编码叽 变换编码的另一关键步骤是对小波系数的压缩，即量化编码( 1 0 】。目前用于小波系数的 压缩方法基本上有三类：标量量化、矢量量化、小波系数的零树方法。标量量化技术是一 种简单实用的数据压缩技术，具有对信号的适应性及实现的简单性。从信息论的角度，矢 量量化总能获得优于标量量化的率失真性能，但是训练码本、矢量的搜索需要花费很多时 间，如果不能充分利用小波变换系数的特殊性，并结合新的数字信号处理技术，即使能够 获得很高的压缩比，也很难形成高性能的压缩编码方案。零树是一种新型的数据结构，零 树方法利用了相应子带间的相关性，是基于小波图像压缩编码的一个有意义的突破，具有 代表性的是1 9 9 3 年s h a p i r o 提出的嵌入式零树编码l 】( e z w ：e m b e d d e di m a g ec o d i n gu s i n g z e r o t r e eo fw a v e l e t sc o e f f i c i e n t s ) 和1 9 9 6 年s a i d 、p e a r l m a n 提出的多级树集合分裂 算法【1 2 】( s p i h t ：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 ) 。零树方法压缩性能较好，不 需要训练码书，编码算法较矢量量化简单，支持逐次浮现式传输，适于实时处理。 1 4 本课题研究的意义 作为迄今为止小波压缩编码效果最好的算法之一，s p i h t 在继承e z w 算法优异特性的 基础上，构造了两种不同类型的空间树d ( i ，) 和l ( i ，j ) ，对小波系数进行更紧凑的划分， 将尽可能多的非重要系数汇集在一个子集中，用一个符号表示，实现有效压缩。但s p i h t 南京邮电火学顺士研究生论文 第一苹绪论 编码过程中使用了l i p 、l s p 、l i s 三个列表来记录小波系数、划分集合的重要性信息，过 多的占用了存储空间，也同时增加了计算量，限制了s p i h t 算法的具体推广应用，尤其是 在手持、移动、嵌入式等终端设备中的应用。另外，作为的s p i h t 编码的第一阶段小 波变换的效果也将直接影n 晌j - ns p i h t 的压缩编码效果，而传统的小波变换、提升变换都忽 略了图像的方向性信息，仅仅考虑了图像的垂直、水平信息，图像的方向性信息一般表现 为图像的边缘、细节。这样，一方面就不利于将图像能量的有效集中以方便后续s p i h t 压 缩编码；另一方面，在具体的应用中，尤其是在高压缩低比特率的应用中，必将损失过多 的高频细节能量，严重影响图像的客观质量。 为此，本文在综合分析了前人研究的基础上，提出了一种基于小波变换的新算法 基于方向提升小波变换的无链表算法，即l d l s p i h t 算法。该算法首先改进了s p i h t 压缩 编码算法的第一阶段小波变换，本文在分别研究了方向小波、提升变换的基础上，引 入了简化的方向提升小波变换，既考虑了图像的方向信息，也降低了对计算和存储空间的 需求，以方便以后的实际应用；其次，该算法还改进了s p i h t 本身的编码结构，使用两个 副表露、r 替代l i p 、l s p 、l i s 三个列表来记录小波系数、划分集合的重要性信息，不 但降低了对存储空间的需求，还减小了计算量。总的来说，本文提出的基于方向提升小波 变换的l dl s p i h t 压缩编码算法，不但提高了编码性能，而且降低了对存储空间的需求， 便于该算法的具体推广与应用。论文最后还进行了基于d s p 平台的移植和应用的初步研究。 1 5 本文的工作内容与结构安排 图像压缩在多媒体技术中具有重要地位，传统图像编码压缩方法和标准虽得到广泛应 用，但仍有不少问题，小波用于图像编码压缩具有压缩率高、很好地渐进传输、可伸缩的 质量等诸多优点，因而得到广泛关注。 本文首先简单介绍了小波的基础知识、小波变换的原理以及常见的两种基于小波变换 的图像压缩编码经典算法e z w 、s p i h t ：之后在分析传统小波变换的缺陷、研究已有方向 提升小波变换不足的基础之上，提出了改进方向提升小波变换：接着又充分研究了无链表 算法，基于现有的无链表l z c 算法的不足，提出了新的改进无链表l s p i h t 编码算法，其 在降低对存储需求的同时，也保持住了原有的图像性能，并将方向提升小波变换与无链表 l s p i h t 编码算法相结合得到新算法l dl s p i h t 。最后，为了验证本文提出算法的实用性， 先后基于硬件、软件分别实验说明。 本文共分七章，具体结构安排如下： 4 塑塞堕坐查兰堡二! ：型! 塑竺笙塞笙二兰笙堡 第一章：首先介绍了视频压缩编码技术的发展，随后又分别介绍了基于小波变换图像 压缩编码的现状以及本课题的研究意义，最后指出了本文所要研究的主要内容与结构安 排： 第二章：首先介绍了各种小波变换原理，之后又详细介绍了两种传统经典的小波图像 压缩编码算法e z w 、s p i h t ； 第三章，对传统的小波变换以及现有的方向小波变换进行充分的分析研究，在此基础 上，提出一种新的方向提升小波变换算法，并将其与s p i h t 相结合得到新算法l ds p i h t ， 进行了简单的性能分析： 第四章，对原始的s p i h t 和已有的无链表图像压缩编码算法进行充分的分析研究，在 这些算法的基础上提出一种将新的无链表l s p i h t 算法，并将方向提升小波变换与此无链 表l s p i h t 算法相结合得到新算法l dl s p i h t ，进行了简单的性能分析； 第五章，为了充分说明本文所研究算法的实用性，将其移植到嵌入式硬件平台，基于 d s p 硬件平台实现图像压缩编码； 第六章，对前两章所提出的两种算法进行了软件实验仿真、硬件移植工作，对实验结 果做了分析，实验证明，本文所提出的两种改进算法都能有效的提高图像压缩编码性能和 d s p 硬件平台的可移植性： 第七章，对全文内容进行总结，并对今后可能的研究方向进行了展望。 南京邮电大学硕：j 二研究生论文 第二章 小波雉本理论及基于d 、波变换的图像编码 第二章小波基本理论及基于小波变换的图像编码 作为多个学科共同研究的成果，小波分析理论正日益受到学术界和工程界的密切关 注，成为近代多门学科和多种领域的研究热点。小波分析在信号分析方面所表现出来的优 良特性，使小波成为在这一领域中强有力的研究工具。 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 变换的应用领域均可通过小波变换 来加以应用。小波的发展可以追溯到2 0 世纪初，1 9 1 0 年，h a a r 提出了的规范正交基，尽 管当时没有出现“小波”这个词，但它是最早的小波基。1 9 3 6 年l i t t l e o e d 和p a l e y 对f o u r i e r 级数建立的l p ( 二进制频率分量) 理论：对频率按2 。进行划分，其f o u r i e r 变换的相位变 化并不影响函数大小，这是多尺度分析思想的最初来源。其后，c a l d e r o n 于1 9 7 5 年给出了 抛物型空间上的原子分解，它的离散形式已接近小波展开，只是无法得到组成正交基的结 论。1 9 8 1 年s t r o m b e r g 对h a a r 系数进行了改进，证明了小波函数的存在性。1 9 8 2 年b a t t l e 在构造量子场论时使用了类似c a l d e r o n 再生公式的展开，值得注意的是，1 9 8 4 年法国地球 物理学家m o r l e t 在分析地震波的局部性质时，发现传统的f o u r i e r 变换难以达到要求。因 此，他把小波概念引入了信号分析中对信号进行了分解。随后，理论物理学家g r o s s n l a n 对m o r l e t 的这种信号按一个确定的函数的伸缩、平移展开的可能性进行了研究，为小波分 析开了先河。小波分析于1 9 8 8 年有了突破性的进展，数学家d a u b e c h i e s 提出构造具有紧 支撑的光滑小波，后来m a l l a t 提出了多分辨率分析的概念及快速小波变换【l 4 , l 5 】，其发展 历史不过十几年。但在这段时间内，有关小波的研究不断取得重大突破，小波分析己经成 为目前发展最快和最引人注目的学科之一，几乎涉及或应用于信息领域的所有学科。 s w e l d e n s 和d a u b e c h i e s 等学者于九十年代中期提出了一种新的小波的构造方法提升小 波( 又称为第二代小波) 1 6 , 1 7 , 1 8 1 。 本章将首先简要介绍各种小波变换的定义及特点：之后介绍静止图像小波编码的传统 经典算法嵌入式小波零树e z w 算法、分层小波树集合分割s p i h t 算法，为本文的后 续算法研究打下理论分析基础。 6 南京邮电大学顺。l - ：t i j l ：究生论文 第二章小波丛本理论及基于小波变换的图像编码 2 1 小波变换原理 2 1 1 连续小波变换 ( 1 ) 定义 设( f ) r ( r ) ，f ( 尺) 为( f ) 的矢量空间，r 为实数集。其傅立叶变换为( 甜) 满足容 许条件( 完全重构条件或恒等分辨条件) ： q ：吲 1 ，。b o 1 ，则根据式( 2 7 ) ，可得离散小波 的函数族： 少肚( r ) = c t o j 2 v ( a 0 7 卜慨) ( 2 6 ) 则离散的小波变换为： d w t ( j ，七) = e 厂( f ) ，( ，灿 ( 2 7 ) 其逆变换为： 厂( ，) = f d 嵋。( ，) ( 2 8 ) c 是一个与信号无关的常量，重构小波一般不是唯一的。当= 2 时，似( f ) 即为二 进小波( d y a d i cw a v e l e t ) 。 从理论上可以证明将连续小波变换离散成离散小波变换，信号的基本信息并不会丢 失，相反由于小波基函数的正交性，使得小波空间中两点之间因冗余度造成的关联得以消 除：同时，因为正交性，使得计算的误差更小，使得变换结果时一频函数更能反映信号本 身的性质。 2 1 3 提升小波变换第二代小波变换 l9 9 6 年，s w e l d e n s 与d a u b e e h i e s 等学者在d o n o h o 与l o u n s b e r y 等人的工作基础上建立了 一种新的实现小波变换的结构一提升框架【嗡l 。该方法最初是用来改进某一已有的小波，后 来称为“第二代小波”。在第二代小波中，小波不一定是由某一母小波通过膨胀和平移得 到的，它们的定义非常灵活，也许是在某一区间，也许是定义在不规则的网格上。而在二 维空间中，则可能定义在曲面上【2 0 也3 1 。 提升框架的实质就是将第代小波变换的滤波器多相矩阵( p o l y p h a s e m a t r i x ) 通过 e u c l i d e a n 算法分解为若干个交替的上三角阵、下三角阵与常数对角阵的乘积形式，滤波器 的多相矩阵通常l a u r e n t 多项式( l a u r e n t p o l y n o m i a l ) 构成。 8 塑塞塑生盔兰堡! ：型! 壅竺笙兰 笙三至尘丝苎尘型堡丝苎主尘鲨些垫塑望堡堡坚 ( 1 ) 提升方案的基本原理和提升步骤 小波函数。( f ) 通常定义为一个属于l 2 ( r ) 空间的母小波的二进伸缩( d i l a t e s ) 和平移 ( t r a n s l a t e ) ： 妙似( ，) = 2 j 2 y ( 2 7 f 一七) ( 2 9 ) 这样的小波称为第一代小波。然而，在更一般的情况下，小波并不必须是彼此的伸缩 和平移，但仍然具有第一代小波的特点，这样的小波称为第二代小波，利用提升方案可以 构造它们。第- 4 - d , 波具有如下性质： l 、l 2 ( r ) 空间的r i e s z 基，还有l e b e s g u e ，l i p s e h i t z ，s o b o l e v 和b e s o v 空间无条件基； 2 、小波及其对偶在空间和频域是局部化的，有些小波还是紧支撑的； 3 、小波分析可纳入多分辨分析的框架，这导致了快速小波变换算法： 在研究中又常需要如下性质： 4 、第一代小波提供了定义在r ”上函数的基。但在图像数据分割、在一般定义域上的 微分和积分方程的求解，需要定义在任意的、可能不光滑的域上的小波： 5 、第一代小波典型的只具有不变测度的空间的基，而微分方程的对角化、在曲线或 表面上的分析等需要可适应加权测度的基； 6 、第一代小波隐含对数据进行规则采样，而实际问题经常要处理不规则采样的数据。 具备小波性质l 3 ，有满足和6 性质的第一代小波推广称为第二代小波。这里的关键 问题是平移与伸缩并不是属于1 3 所必须的，放弃平移和伸缩，隐含着f o u r i e r 变换不能 再作为构造工具。提升格式保留了第一代小波的特点，同时有克服了其平移和伸缩的不变 性。 w i ns w e l d e n s 确定提升格式由分裂( s p l i t ) 、预测( p r e d i c t ) 和更新( u p d a t e ) 三部分 组成，如图2 1 、2 2 所示： 9 南京邮电大学颂：i ：f j f 究生论文第二章小波基奉理论及基于小波变换的图像编码 图2 - 2 一次提升小波逆变换示意图 下面详细介绍这三部分： 第一步：分裂，将输入信号：分成相互关联的t 和艺两组信号。并且t 、的相关性 越强，分割效果越好。在实现中，最常用的分解方法是惰性小波( l a z y w a v e l e t ) 作为第一级 小波分解，即：x d n = x 2 n ，x o n = 虹2 ，z + 1 】。也就是将奇数点定义为奇序列吒，偶数点 定义为偶序列t 。惰性分割充分利用了信号x 的局部相关性，为预测和更新过程提供了数 据基础。 第二步：预测，是针对数据间的相关性，用将分裂后得到到的偶信号兑与预测算子尸 去预测奇预测值吒，然后用预测值与毛的差值来代替，即d = x o 一尸( t ) ，该信号的预测 误差d 就是图像的高频( h ) 细节信息。这种预测是可逆过程，我们可以利用x e 和d 来恢复， 如式：吒= d + 尸( t ) ，再进而恢复x 。 第三步：更新，为了使原信号集的某些全局特性在其子集t 中继续保持，必须进行更 新。更新的思想就是要找一个更好的子集t ，使得它保持原图的某一标量特性q ( x ) ( 例如 均值、消失矩等) 不变。将该信号的预测误差d 通过滤波器u ，得到t 的更新值，即： s = 吒+ u ( d ) 。其中，预测和更新可以重复多次，最后得到输入信号的近似分量s 。和细节 分量以。 ( 2 ) 提升方案的优点 与第一代小波变换相比，提升小波变换具有更多优良的性质： 1 、提升小波变换过程简单，运算量低，避免了传统小波变换过程中复杂的卷积操作， 易于硬件实现； 2 、提升小波变换与逆变换过程的输入输出结果都是整数，完成了真正意义上的可逆 小波变换，保证了图像的无损编码，提高了编码性能； i n 南京邮电大学硕士硼f 究生论文第二章小波基本理论及基于小波变换的幽像编码 3 、提升方案不需要傅立叶分析的背景知识，与第一代小波变换方法相比，其计算复 杂度大大降低，理解起来较容易。 2 2 基于小波变换的图像编码 小波图像压缩是一种很重要的图像压缩方法，它利用小波变换同时具有好的空间分辨 率和好的频率分辨率的特性，使变换系数的质量同时在频率上和空间上集中，达到去除冗 余的作用。小波编码研究主要从三方面进行：一是对小波系数的合理组织，研究表明在图 像的低比特率编码中，用来表明非零系数所在位置的开销往往大于用来表示非零系数数值 的开销，因此小波算法中排序算法的优劣和排序信息的处理决定了整个编码算法的效率； 二是从重要系数的量化方法上进行研究，进一步提高数据的压缩率；三是从小波滤波器的 构造出发，找出适合具体应用的可逆小波变换，以实现图像的压缩。 随着小波图像压缩应用研究的深入，出现了许多的基于小波变换的编码算法，其中嵌 入式零树小波编码e z w 算法、分层小波树集合分割s p i h t 算法和比特流优化截取的内嵌 块编码e b c o t 算法三种算法是最典型的算法。由于本文研究对象是s p i h t 压缩编码算法， 所以在本节中，将对嵌入式零树小波编码e z w 算法、分层小波树集合分割s p i h t 算法做 详细的介绍和分析。 2 2 1 嵌入式零树小波编码算法e z w 1 9 9 3 年，s h a p i r o 根据小波系数的统计分布规律，提出了嵌入式零树