（信号与信息处理专业论文）提升小波二叉树编码算法研究.pdf

中文摘要 图像编码是数字图像处理的重要分支，广泛应用在各种图像视频编码的传 输、存储和检索系统中。自2 0 世纪8 0 年代以来，小波变换因其特有的多分辨率 分析能力而被广泛应用于图像和视频编码领域，取得了很好的效果。小波编码是 变换编码新的、重要的发展方向，随着j p e g 2 0 0 0 的推出，可以预见，小波编码 将成为图像视频编码的主流技术。 本论文主要研究了针对不可分离二维小波变换用于图像压缩的二叉树小波 编解码算法。文中首先简要地介绍了一维小波变换、多分辨分析和m a l l a t 算法， 讨论了m a l l a t 算法实现中的边界延拓问题，并以周期延拓方式为例给出了m a l l a t 算法实例。接着研究了可分离的二维小波变换和二维m a l l a t 算法，编写c 语言 程序对图像做可分离的二维小波变换，使用m a t l a b 6 5 将得到的小波系数进行统 计分析与能量分布分析，分析了可用于图像编码的小波系数特性。结合小波变换 图像编码的基本思想，介绍了三种典型的小波图像编码算法。 在研究二维离散信号采样和小波提升格式的基础上，基于全相位列率滤波理 论，设计了全相位内插滤波器组，将全相位内插滤波器用做小波变换提升格式中 的预测和更新滤波器，详细介绍了不可分离二维小波变换提升结构的实现过程。 与可分离的情况相类似，同样对图像经不可分离二维小波变换后的小波系数进行 了统计分析。在此基础上，结合各分解子带小波系数金字塔排列的特点，借鉴经 典的s p i h t 小波编码算法的思想，提出了二叉树小波编解码算法，并详细给出 了二叉树编解码实例。 最后在v c 6 0 环境下，编写c 语言程序，实现了图像的不可分离的二维提 升小波变换和二叉树编码算法，并进行相应的二叉树解码和小波反变换重建图 像。对经典的测试图像做压缩，将得到的实验结果与传统的小波编码算法s p i h t 做比较，在低比特率情况下，得到了较好的压缩效果，重建图像的峰值信噪比平 均提高约0 4 d b 。 关键词：二叉树小波编码；图像编码；图像压缩；小波变换；提升格式；s p i h t 编码算法 a b s t r a c t t h ei m a g e c o d i n g ，w h i c hi sas i g n i f i c a n tb r a n c ho fd i g i t a li m a g ep r o c e s s i n g ，i s e x t e n s i v e l ya p p l i e di nv a r i o u st r a n s m i t t i n g s t o r a g ea n dr e t r i e v a ls y s t e m so fi m a g e & v i d e o s i n c e19 8 0 s ，t h ew a v e l e tt r a n s f o r mh a sb e e nw e l la p p l i e di ni m a g ea n dv i d e o c o d i n gf o ri t ss p e c i a lc a p a b i l i t yo fm u l t i r e s o l u t i o na n a l y s i s w a v e l e tc o d i n gi sa n e wa n dv i t a ld e v e l o p m e n td i r e c t i o ni nt r a n s f o r mc o d i n g w i t ht h ep r o c l a m a t i o no f j p e g 2 0 0 0s t a n d a r d ，w a v e l e tc o d i n gw i l lb et h em a i n s t r e a mt e c h n o l o g yi ni m a g e v i d e oc o d i n gf i e l d s i nt h i s p a p e r , b i n a r yt r e ew a v e l e te n c o d i n g & d e c o d i n ga l g o r i t h mt oi m a g e c o m p r e s s i o ni sm a i n l ys t u d i e db a s e do nn o n s e p a r a b l et w o d i m e n s i o n a lw a v e l e t t r a n s f o r mo nl i f t i n gs c h e m e f i r s to fa l l ，o n e - d i m e n s i o n a lw a v e l e tt r a n s f o r m ， m u l t i r e s o l u t i o na n a l y s i sa n dm a l l a ta l g o r i t h ma r eb r i e f l yi n t r o d u c e d ，a n dt h e nt h e b o u n d a r ye x t e n s i o np r o b l e mi nm a l l a ta l g o r i t h m sr e a l i z a t i o ni sa l s od i s c u s s e d ， m o r e o v e r ，a ni l l u s t r a t i o no f m a l l a ta l g o r i t h mi sg i v e nw i t hp e r i o d i ce x t e n s i o nm e t h o d s s e c o n d l y , s e p a r a b l et w o d i m e n s i o n a lw a v e l e tt r a n s f o r ma n dt w o d i m e n s i o n a lm a l l a t a l g o r i t h ma r es t u d i e d s e p a r a b l et w o d i m e n s i o n a lw a v e l e tt r a n s f o r mo ft h ei m a g ei s i m p l e m e n t e dw i t hcp r o g r a m ；a n dt h es t a t i s t i c a la n a l y s i sa n de n e r g yd i s t r i b u t i n g a n a l y s i so ft h ec o r r e s p o n d i n gw a v e l e tc o e f f i c i e n t sa l ed e a l tw i t hu s i n gm a t l a b 6 5 ，t h u s t h ec h a r a c t e r i s t i co fw a v e l e tc o e f f i c i e n t sa p p l i e dt oi m a g ec o d i n ga r ea l s oa n a l y z e d w i t ht h eb a s i ci d e ao fw a v e l e tt r a n s f o r mi m a g ec o d i n g ，t h r e et y p i c a lw a v e l e ti m a g e c o d i n ga l g o r i t h m sa l ei n t r o d u c e d i nt h ef o l l o w i n g ，t h es a m p l i n go ft w o d i m e n s i o n a ld i s c r e t es i g n a la n dw a v e l e t l i f t i n gs c h e m ea r ed i s c u s s e d 。a n da l lp h a s ei n t e r p o l a t i n gf i l t e rb a n k si sd e s i g n e d b a s e do nt h et h e o r yo ft h ea l lp h a s es e q u e n c yf i l t e r i n g u s i n gt h ea l lp h a s e i n t e r p o l a t i n gf i l t e r sa st h ep r e d i c t i o na n du p d a t ef i l t e ri nw a v e l e tl i f t i n gs c h e m e ，h o w t or e a l i z et h en o n s e p a l a b l et w o d i m e n s i o n a lw a v e l e tt r a n s f o r mw i t hl i f t i n gs c h e m ei s i n t r o d u c e di n d e t a i l s i m i l a r l y t ot h e s e p a r a b l ei n s t a n c e ，t h ei m a g ew a v e l e t c o e f f i c i e n t s ，w i t hn o n s e p a r a b l et w o d i m e n s i o n a lw a v e l e tt r a n s f o r m a r ep r o c e s s e d w j t hs t a t i s t i c a la n a l y s i s c o n s i d e r i n gt h ec h a r a c t e r i s t i c so fw a v e l e tc o e f f i c i e n t si na l l d e c o m p o s i t i o ns u b b a n d sa n dt h eb a s i ci d e ao fc l a s s i c a ls p i h tw a v e l e tc o d i n g a l g o r i t h m ，b i n a r yt r e ew a v e l e tc o d i n ga l g o r i t h mi sp r o p o s e dw i t hd e t a i l e di n s t a n c e f i n a l l y , t h en o n s e p a r a b l et w o d i m e n s i o n a lw a v e l e tt r a n s f o r mo fi m a g e sw i t h l i f t i n gs c h e m ea n db i n a r yt r e ee n c o d i n ga l g o r i t h ma r er e a l i z e dw i t hcp r o g r a mi n t h ec o n s o l eo fv c 6 0 c o r r e s p o n d i n g l y , b i n a r yt r e ed e c o d i n ga n dw a v e l e ti n v e r s e t r a n s f o r ma r ec a r d e do u tt or e c o n s t r u c tt h ei m a g e s v h e nc o m p r e s s i n gt h ec l a s s i c a l t e s ti m a g e s ，t h er e s u l t si n d i c a t et h a tt h ec o m p r e s s i o ne f f i c i e n c yi sb e t t e rt h a nt h e t r a d i t i o n a lw a v e l e tc o d i n ga l g o r i t h ms p i h ta tl o wb i tr a t e sa n dt h ep e a k s i g n a l t o - n o i s er a t i o ( p s n r ) o ft h er e c o n s t r u c t e di m a g e sa r eh i g h e rt h a nt h a to f s p i h ta b o u t0 4 d b 。 k e yw o r d s ：b i n a r yt r e ew a v e l e tc o d i n g ；i m a g ec o d i n g ；i 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 m ；l i f t i n gs c h e m e ；s p i h t c o d i n ga l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：成1 矗 签字日期： 2 。口7 年f 月2 f 日 学位论文版权使用授权书 本学位论文作者完全了解叁盗盘鲎有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：立盛和云 导师签名： 1 毛叭乏 签字日期：20 0 7 年f 月2 f 日 签字日期：w 叼年f 月巧7 日 第一章绪论 1 1 小波分析概述 第一章绪论 小波分析是近2 0 年来迅猛发展起来的一门新兴学科，已被广泛应用于数值 分析、信号处理、图像处理、量子理论、地震勘探、语音识别、计算机视觉、 c t 成像、机械故障诊断等领域。 小波分析的发展历史最早可追溯到1 9 1 0 年h a a r 提出的小波规范正交基【l j ， 不过当时还没有“小波”这一概念。1 9 3 6 年，l i t t l e w o o d 和p a l e y 对傅里叶( f o u r i e r ) 级数建立了二进制频率分量分组理论( l p 分解理论) f 2 j ，这是多分辨率分析思 想的最早来源。1 9 8 3 年法国地球物理学家m o r l e t 在分析地震波的局部性质时， 发现传统的傅里叶变换难以达到实际要求，首次提出了小波分析( w a v e l e t a n a l y s i s ) 这一概念，并把它用于信号分解中【3 】。 真正的“小波热”始于1 9 8 6 年，当时m e y e r 、l e m a r i 6 和b a t t l e 先后创造性 地构造出了具有一定衰减性的小波函数【4 矧。1 9 8 7 年，m a l l a ts 巧妙地将计算机 视觉领域内的多分辨率分析【7 s l ( m u l t i r e s o l u t i o n a n a l y s i s ) 思想引入到小波分析中， 成功地统一了在此之前由s t r 6 m b e r g 、m e y e r 、l e m a r i 6 和b a t t l e 提出的具体小波 函数的构造方法，在此基础上给出了构造正交小波基的一般方法，实现信号的小 波分解和重构；并且在金字塔算法的启发下，以多分辨率分析为基础，提出了著 名的快速小波变换算法( f w t ：f a s tw a v e l e tt r a n s f o r m 卜刊a l l a t 算法【7 弗】，从而引 出了离散小波变换的概念并将其有效地应用于图像分解和重构。 与9 0 年代初期的快速发展相比，最近几年小波理论的研究进入了相对平缓 的阶段。这个阶段主要研究小波滤波器组的构造f 9 1 、多小波理论 1 0 - 1 2 1 及非线性小 波变换 1 3 , 14 】和自适应小波变换理论【1 5 】等。其中最重要的成果之一是s w e l d e n s 等 人提出的第二代小波即基于提升格式( l i f f i n gs c h e m e ) 的小波构造框架 1 6 - 1 9 ，以及 在此基础上提出的基于提升格式的小波变换。并且基于提升格式的小波变换为非 线性小波变换和自适应小波变换的实现提供了新的方法 2 0 , 2 1 l 。 1 2 图像压缩编码发展现状 图像压缩的基本理论起源于2 0 世纪4 0 年代末香农( s h a n n o n ) 的信息论。在 第一章绪论 这个理论框架下，出现了几种不同的无失真信源编码方法，如h u f f m a n 编码、算 术编码、词典编码等，这些编码方法的压缩率是很有限的，对较复杂的自然图像， 压缩率一般不超过2 。由于压缩率的这一限制，使其难以满足大多数图像存储和 传输的需要。根据应用的需求，人们对有失真压缩进行了广泛的研究。有失真的 图像视频编码的一个主要目的就是在保证一定重构质量的前提下，以尽量少的 比特数来表征图像和视频信息【2 引。 近年来，图像和视频压缩领域出现了多种压缩算法和以i s o 的j p e g 、 m p e g 1 2 ，i t u t 的h 2 6 1 2 6 3 2 6 4 等为代表的国际压缩标准。这些传统的图像 编码方法以信息论为基础，主要采用基于块的离散余弦变换( d c t ：d i s c r e t e c o s i n et r a n s f o r m ) 消除图像的空间冗余；通过块运动估计运动补偿技术消除时间 冗余；最后通过变字长编码消除统计冗余【2 3 1 。然而，随着研究和应用的不断深入， 基于分块余弦变换编码的缺点逐渐暴露出来，尤其在低比特率环境下，容易导致 方块效应、飞蚊噪声等失真现象。这是因为一般情况下，图像信号是高度非平稳 的，而且图像中的一些突变结构比如边缘信息远比图像的平稳信息重要，用余弦 变换基作为非平稳信号的逼近其结果不是最优的 2 4 , 2 5 】。并且，2 0 世纪9 0 年代以 后出现了以i n t e m e t 为代表的新的传输媒体，i n t e r n e t 上的图像浏览和传输有了许 多新的要求，例如嵌入式码流和多分辨码流等。这就要求在图像压缩算法实现中， 能灵活地提供关于质量、分辨率等的分级结构，这些灵活性要求同d c t 变换编 码的结构也很难有机地结合【2 2 】。 2 0 世纪8 0 年代后期发展起来的小波变换由于其具有良好的空间频率局部 化等特性，成为信号处理中分析非平稳信号的有力工具。由于小波基的无条件基 特性，使它成为一大类信号非线性逼近的最优基，许多信号在小波基的表示下， 都可以获得稀疏的表示。小波变换理论中一个关键的思想是多分辨率分解，这个 思想很好地利用在小波图像编码中，使得图像压缩是小波变换最成功的应用领域 之一。小波图像压缩的研究表明，现代应用中需要的许多特征如多分辨率编码、 多层质量控制、嵌入式码流等，均能与小波图像编码结构非常自然地融合在一起， 在较大的压缩比下，小波图像压缩的重构质量也明显好于d c t 变换方法f 2 6 】。 随着小波理论研究的不断深入，基于小波的图像和视频压缩应用研究取得了 许多成果。1 9 8 6 年，w b o d s 【2 7 】构造了第一个真正意义上的小波图像编码器。1 9 9 2 年d a u b e c h i ei 构造了9 7 小波滤波器【28 i ，在小波压缩领域中得到了广泛的应用。 1 9 9 3 年s h a p i r o 提出了嵌入式零树小波编码算法( e z 、聊口9 1 ，初步揭示了小波变换 后各子图之间的关系，在m p e g 4 【3 0 】中，e z w 算法已经成为静止图像压缩编码 的模块之一。p e a r l m a n 于1 9 9 6 年提出了分层小波树集合分割算法( s p i h t ) 3 1 , n j ， 这是迄今为止效果最好的小波压缩算法之一。2 0 0 0 年t a u b m a n 提出了具有优化 2 第一章绪论 截断的嵌入式块编码算法( e b c o t ) t 3 3 1 ，它的压缩效率更高，但复杂度也有所增加， 鉴于这种算法的优异性能，已被采纳为j p e g 2 0 0 0 t 3 4 】的核心算法。目前，基于小 波变换的图像和视频压缩已经成为当前的研究热点，并且可以预见，基于小波的 视频压缩技术将是未来视频压缩标准的一项核心技术2 5 1 。 1 3 图像质量的评价准则 目前常用的图像质量评价方法主要有客观评价准则和主观评价准则两种【2 6 1 。 客观评价准则是对压缩还原后的图像与原始图像的误差进行定量计算，一般是对 整个图像或图像中的指定区域进行某种平均计算，比较常用的有均方误差( m s e ： m e a ns q u a r e de r r o r ) 和峰值信噪比伊s n r ：p e a ks i g n a l t o - n o i s er a t i o ) 等【2 2 1 。 设一幅原始图像的像素值为扛( f ，_ ，) ，0 i m l ，0 j n 一1 ，相应的压缩 后的还原图像像素值为 ；( f ，) ，0 f m 一1 ，0 歹n 1 ) ，则误差图像为 e ( f ，) = x ( i ，j ) 一x ( i ，) ，0 i m 一1 ，0 j 一1 ) ，那么均方误差表示为 ， m s e = 面1m 缶- 1 n 缶- i e 2 ( f ，护去篓融“廊棚 2 ( 1 - - ) 设k 。，= 2 x 一1 ，其中k 表示一个像素点所用的二进制位数，则峰值信噪比定义 为 p 0 1 9 志= 1 0 l g i 脚一丽 ( d b )( 1 2 ) 在许多采集的视频序列和商用图像的应用中，常取k = 8 。所以，对8 位二 进制图像，= 2 5 5 ，代入上式得 ps10lg篙iokfmn2552 ( d b ) ( 1 - 3 ) 评估编码性能还使用其它一些指标，比如信号噪声匕g ( s n r ：s i g n a lt on o i s e r a t i o ) 和平均绝对误差( m a e ：m e a n a b s o l u t ee r r o r ) 1 3 5 等，它们的定义分别为： 眦删刊藉嘉x ( i 丽x ( il i l，) 一，州l f = 0j = 0 一 一 i m a e ：上窆孰渺奶) j m n ：二一y y i z f f ，) 一；( i ，) l 智鲁i 。 ( d b )( 1 - 4 ) ( 1 - 5 ) 第一章绪论 式( 1 1 ) 式( 1 5 ) 看起来直观、严格，但用它们所求得的结果常常与人们的主 观视觉效果不一致。这是因为均方误差、峰值信噪比和信号噪声比等都是从总体 上反映原始图像和恢复图像的差别，并不能反映一幅图像中少数像素点有较大灰 度差别和较多像素点有较小差别等各种情况。显然，客观质量评价采用以上各式 是对图像中所有的像素点同样对待的，不能全面反映人眼的视觉特性。 对压缩图像质量的第二种评价准则是主观准则，它是选择一组评价者给待评 图像进行打分，对这些主观打分进行平均获得一个主观评价分。表1 1 t 2 2 1 所列是 两种典型的评分标准。设每一种得分记为c j ，每一种得分的评分人数为n ，则一 个被称为平均感觉分m o s ( m e a no p i n i o ns c o r e ) 的主观评价得分为： 七 ”，c m o s = ( 1 6 ) ”， i = i 例如，一段视频节目的评分为4 5 ，这说明图像质量相当好。 表1 1 对图像质量评价的两种主观评分标准 得分第一种主观评价标准第二种主观评价标准 5 非常好 感觉不到失真 4好感觉到失真，但没有不舒服的感觉 3 一般稍微感慌到有些不舒服 2较差不舒服 1 差有非常不舒服的感觉 评价图像压缩效果的另外一个重要指标是压缩比c ，它指的是表示原始图像 每像素的比特数同压缩后平均每像素的比特数的比值，也常用每像素比特值( b p p ： b i tp e rp i x e l ) 来代表压缩效果。在视频图像序列传输应用中，由于信道的限制， 目标传输速率是确定的，例如3 8 4 k b s 表示每秒3 8 4 千比特，这时的压缩比则要 根据传输的视频帧率和分辨率来确定。 对以上各种评价指标，文献中最常用的是峰值信噪比，因为其在大多数情况 下可提供很有价值的信息，并且在数学上也比较容易计算。本论文中主要采用客 观评价准则，通过考察重建图像的p s n r 对整个编码算法性能进行评价。具体来 说，就是在给定的码率下，计算解码图像的p s n r 值，如果该数值越大，则认为 算法性能越好。 4 第一章绪论 1 4 本论文的研究内容及组织结构 本论文选题来自于国家自然科学基金“二维提升小波变换和可变块运动补偿 视频压缩编码技术( n o 6 0 3 0 2 0 1 8 ) ”的一部分，主要研究基于提升格式的不可分 离的二维小波变换及其二叉树编码方法，进一步提高图像压缩质量。 论文首先介绍小波分析和图像压缩编码的发展现状，接着介绍了一维和可分 离的二维小波变换及目前几种常用的小波编码算法；在此基础上了讨论了不可分 离的二维小波变换，构造了具有五株形的全相位内插滤波器和提升格式的不可分 离的二维小波滤波器；并将其用于图像的多分辨率分解，对小波变换后的系数特 点进行研究，在借鉴s p i h t 编码算法的基础上提出了二叉树小波编码算法，并 详细给出了二叉树编解码实例；接着用c 语言设计程序实现了不可分离的二维 提升小波变换和二叉树小波图像编解码，给出了典型图像的实验结果，并与可分 离二维小波变换的s p i h t 编码算法做了分析比较。本论文具体的章节安排如下： 第一章是绪论部分，主要讲述了小波分析的发展历史和现状及图像压缩编码 的发展概况，并简要介绍了图像编码质量的评价准则。 第二章对基于小波变换的图像压缩编码进行了详细讨论。首先研究了一维和 可分离的二维小波变换以及小波变换的快速算法m a l l a t 算法，并在v c 6 0 环 境下，编写c 语言程序给出了一维m a l l a t 算法实例；选择常用的9 7 双正交小波， 编写c 语言程序对图像做可分离的二维小波变换，使用m a t l a b 6 5 将得到的小波 系数进行统计分析与能量分布分析，分析了可用于图像编码的小波系数特性。最 后结合小波图像编码的基本思想，重点介绍了三种典型的小波图像编码算法。 第三章重点介绍不可分离的二维小波变换以及如何将其用于图像分解。首先 由二维离散信号的采样和不可分离的二维小波变换谈起，设计了全相位内插滤波 器。将全相位内插滤波器用于小波变换提升格式中的预测和更新滤波器，设计了 不可分离的二维小波滤波器，并编写c 语言程序将其用于图像分解。使用 m a t l a b 6 5 对分解得到的小波系数进行统计分析与能量分布分析，得到了类似于 可分离二维小波变换时的分析结果。 第四章和第五章的内容是本论文所做的主要工作。第四章在第三章图像分解 及对小波系数分析所得结果的基础上，借鉴第二章中经典的s p i h t 小波编码算 法的思想，提出了二叉树编解码算法，并详细给出了二叉树编解码实例。 第五章在v c 6 0 环境下，编写c 语言程序，实现了图像的不可分离的二维 提升小波变换和二叉树编码算法，并进行相应的二叉树解码和小波反变换重建图 像。对经典的测试图像做压缩，将得到的实验结果与经典的s p i h t 小波编码算 法做比较并得出结论。 5 第二章基于小波交换的图像压缩编码 第二章基于小波变换的图像压缩编码 小波分析作为一种时频局部化分析方法，其基本思想是寻求一个满足一定条 件的基本小波函数少( f ) ，通过对基本小波函数的伸缩和平移构成小波函数族 ，。( 叫，然后利用这个函数族来逼近或表示所要研究的信号，并作出相应的分 析和处理f 3 6 】。 2 1 一维小波变换 2 1 1 连续小波变换 设沙( f ) 为一平方司积函数，即y ( f ) p ( r ) ，若冥傅里叶夏换沙( 妫满足答讦 性条件： 。= e 肾 ( 2 - ，) 则称沙( f ) 为基本小波或母小波( m o t h e r w a v e l e t ) 函数。 对母小波函数进行伸缩和平移，设其伸缩因子( 又称尺度因子) 为a ，平移 因子为b ，便可得到如下小波函数族： 圳呲，= 忑1 沙( 等) p 2 ， 这里，a o ，b 酞。虬。( f ) 称为小波函数，简称小波。变量口反映函数的尺度( 或 宽度) ，变量b 指明函数沿f 轴的平移位置。 定义2 1 由小波函数族虬。( f ) 可以定义函数厂( d 亡( 尺) 的连续小波变换 ( c w t ：c o n t i n u o u sw a v e l a tt r a n s f o r m ) ( 既厂) ( 口，b ) ： ( 厂) ( a ，6 ) = ( 厂( r ) ，虬，。( ，) ) = 万1e 厂( r ) y ( 半户口 啪酞( 2 - 3 ) 其逆变换为 巾) = 百2f e ( 硝啪) 虬“z 肋亨 = 专re ( 硝咖) 去杪( 等弘睾 ( 2 - 4 ) 由式( 2 3 ) 可见，连n d , n 变换( 既厂) ( 口，b ) 是厂( f ) 在函数炸6 ( f ) 上的投影，它 6 第二章基于小波变换的图像压缩编码 将一个一维函数厂( f ) 变换为一个二维函数。 假定y ( f ) ，矿( 国) 的窗函数中心与半径分别为( f ，a y ) 和( 方，矿) ，对于一组确 定的参数( 口，6 ) 而言，小波变换( 呒厂) ( a ，b ) 的值可解释为通过一个中心位于 厂、 i6 + 口f ，竺l ，边长分别为2 a a 。，和2 垃的矩形时间一频率窗 la 口 广 1 b + a t 一口y ，b + a t + a a 妒 f 一0 ) - 一竺，竺+ 全生l 对信号进行的观察，即它提取的 一 一l 口 aaaj 是信号厂( f ) 在上述指定时间段及频率段内的局部信息。小波变换本质上是对信号 的时一频联合分析。尺度口能自动改变时频分辨率：当a 增大时，频宽减小，时 宽增大，而且虬。( f ) 的窗口向低频方向移动；当a 减小时，则变化正好相反，如 图2 1 所示。这就是小波变换具有的逐渐局部化特性，即“变焦距特性”，因此 可视为“数学显微镜”。这一重要性质正是分析非平稳信号所需要的。 岛+ a l t *包+ a z t 。t 图2 - 1 c w t 的时间一频率窗( 图中，a l a 2 ，6 l 1 驴。 离散小波定义为： c ，j ( f ) = a o j 2 9 ( a o 。卜k b o ) ，k z 定义2 2 对任意f ( t ) r ( 尺) ，其离散小波变换( d w t ：d i s c r e t ew a v e l e t t r a n s f o r m ) 下式给出： y i ( a d , n b o a o 忙 = a o j n i i i ti ( , 丽面江，k z ( 2 6 ) 为计算需要，选取= 2 ，b o = l 的二进制离散小波变换，即有： h ( f ) = 2 , 2 y ( 2 t - k ) ，k z ( 2 7 ) 定理2 1 若 y 肚( f ) 是r ( r ) 的框架，即满足稳定性条件，则v f r ( r ) 都能 由 ，k z 重构，其重构公式为： 几) = 巾) ，吩，。( f ) 碱，( f ) 歹，k z ( 2 - 8 ) j = - - k = - - 式中的 哆乒( f ) 称为框架 吩，。( 叫的对偶。 定义2 3 若y r ( 尺) ， y 膳) 是r ( r ) 的一组r i e s z 基，则称少为r 函数； 若还存在一个函数沙r ( r ) ，妒似( f ) = 2 m 痧( 2 t - k ) ，_ ，k z ，使 竹乒 与 仍j ) 是 r ( 尺) 的对偶基，则称l f ，为尺小波，称痧为相应于y 的对偶小波。并且一对( 沙，妒) 满足双正交性质 = 艿，。瓯一，k ，m ，”z ( 2 - 9 ) 则称 y ，痧) 为一对双正交小波， 乒，呒，。 ， 朋，。e z 为一对双正交小波基。 ( i ) 若 y 肪 满足正交条件 = 4 。瓯，k ，m ，玎z ( 2 - l o ) 则称少为正交小波， ，tl 。z 为正交小波基； ( i i ) 若满足条件 = 0 ，j m ，k ，m ，”z ( 2 - l1 ) 则称为半正交小波， ) ， 。z 为半正交小波基。 一般情况下，重构公式( 2 8 ) 中的 痧坩( 叫是很难求得的，除非具有某些对偶 的先验知识。所以，往往要对小波给出很多的限制，以确定其对偶。例如，它们 是半正交小波或正交小波时，就比较容易确定它们的对偶，因为正交小波少= 驴， 是自对偶的；半正交小波y r ( r ) 的对偶旷，通过它的f o u r i e r 变换定义 第二章基于小波变换的图像压缩编码 痧：i 丝l 一 ( 2 一1 2 )y 2 i 、一二一 【：z 一 l 痧( 缈+ 2 尼万) 1 2 j = 而考虑其它小波时，如何确定它们的对偶小波( 即重构小波) 是信号重构的 一个关键问题【3 7 1 。 2 2 多分辨分析和一维m a l l a t 算法 1 9 8 9 年，m a l l a ts 受图像编码技术中塔形分解和多速率信号分解思想的启 发，提出了多分辨分析( m u l t i r e s o l u t i o na n a l y s i s ) 7 ，8 1 的概念及小波分解与重构的 快速算法m a l l a t 算法 7 , 8 1 ，使小波理论与经典的滤波方法建立了联系，从而 促进了小波理论的实际应用。 2 2 1 多分辨分析 多分辨分析又称为多尺度分析，它是建立在函数空l 司概念上的理论。多分辨 分析的基本思想就是用一簇具有不同分辨率的近似函数来对给定函数 八f ) 叠俾) 进行逼近，而这些近似函数可以通过对f ( t ) 使用选择的滤波函数进 行平滑滤波而得到。 定义2 4 r ( r ) 空间中的一闭子空间 巧) 腔，若满足： ( i ) 单调性：c 形一1c 巧c 巧oc ，w z ； ( i i ) 完备性：n 一= o ) ，u 一r ( r ) ； ( i i i ) 伸缩性：f ( t ) 一f ( 2 t ) l 小w z ； ( i v ) 石k 平移不变性：( f ) 巧营厂( h 告) 巧，v k z ； ( v ) r i e s z 基存在性：存在( f ) k ，使得 ( f 一七) ik z ) 是的一个r i e s z 基。则称矽( f ) 生成一个r ( r ) 的多分辨分析( m r a ：m u l t i r e s o l u t i o n a n a l y s l s ) 巧) e z ，且称矽( f ) 为尺度函数( s c a l i n gf u n c t i o n ) 。 由c 巧一，c 匕c 一+ 。c ，v j z 的包含关系，知( f ) = 唬，。( f ) kck 可以 用k 空间的基函数识。( f ) = , f 2 矽( 2 t - k ) ，k z 展开，令其展开系数为 见 ，k z ， 则有 ( ) = 2 a 矽( 2 ，一七) ( 2 一1 3 ) z 另一方面，引入闭子空间 ) 越，且杉是巧在巧+ - 空间中的补空间，即： i + l = 一+ 哆，j z ( 2 - 1 4 ) 9 第二章基于小波变换的图像压缩编码 显然，r ( 尺) 空间可表示为子空间序列 形 ，的直和，即 o ，“ r 俅) = 形= + 矽。+ + 彬+ ( 2 1 5 ) 设 吩，。( f ) = 2 m 沙( 2 f 一七) ，j ，k z 构成的r i e s z 基，其中少( r ) 是尺度函数( f ) 对应的小波。 由于k = v o + ，故y ( f ) = o ( f ) w oc 巧，这意味着小波基函数y ( f ) 可以 用k 子空间的r i e s z 基破。( f ) = , j 2 b ( 2 t - k ) ，k z 展开，令其展开系数为 h ) ，k z ，则有 y ( f ) = 2 吼( 2 f 一七) ( 2 1 6 ) k c j , 式( 2 1 3 ) 和式( 2 - 1 6 ) 分别称为尺度函数和小波函数的两尺度关系( t w o s c a l e r e l a t i o n ) ，其中 a ， 吼 女e z 1 2 称为两尺度序列( 研。一s c a l es e q u e n c e ) 。 2 2 2 一维m a l l a t 算法 在上述多分辨分析的理论框架下，信号与图像处理专家m a l l a ts 提出了基于 滤波器组的小波分解和重构算法一m a l l a t 算法，该算法也被称为快速小波变换 算法。该算法的提出，使得小波分析从理论研究真正走向实用。 考虑2 2 1 节讨论的多分辨分析和小波的一般结构，其中 矿， 由某个尺度函 数驴l 2 ( r ) 生成，而 由某个小波y l 2 ( r ) 生成，根据u 巧= l 2 ( r ) ，任一 。7 j e z f 矽( r ) ，能够对某个n z ，用厶非常接近地逼近，其中厶为厂在空间 上的投影。因为巧= 匕一。+ 一。对任何j z 成立，厶具有唯一的分解 = 厶一。+ g _ l ，其中，厶一，- p g _ 1 一。因为对于正整数m ，有 = 阡k i + 一l = = 阿0 一】+ 陟0 _ 2 + + 乃0 一厨+ 一| i ， ( 2 1 7 ) 重复上述过程，厶( f ) 有唯一分解 厶( f ) = g ，一l ( f ) + g 一2 ( f ) + + g u - u ( f ) + 厶一 ，( f ) ( 2 1 8 ) 上式中的唯一分解称为小波分解。其中，g ( f ) 形，= n m ，n 一1 ， 一材( f ) 一肘；m 代表小波分解的级，一般根据实际分辨率要求而确定。 下面，我们讨论把厶表示为它的分量g ，g 一肘与厶村，并由这些分量 重构名的m a l l a t 算法。 再次写出( f ) 与 f ，( f ) 的两尺度关系，存在两个序列 n ) ， 吼) ，2 ，使 l 矽( f ) = 2 二p 女痧( 2 f 一尼) 三( 2 一1 9 ) y ( f ) = 吼b ( 2 t 一尼) l 对于所有的，r 成立。其中，为了讨论方便，我们省掉了不必要的倍数互。 1 0 第二章基于小波变换的图像压缩编码 另一方面，因为( 2 f ) ，( 2 t - 1 ) k ，且k = k + ，所以存在两个序列 吒) ， 圾) 1 2 , k z 使 b ( 2 t - 1 ) = a t _ 2 k ( b ( t 一七) + 6 ，| | f ，( 卜砒z z ( 2 - 2 0 ) 式( 2 - 2 0 ) 称为矽( f ) 与吵( f ) 的分解关系。 。现在我们有两对序列( q ) ， ) ) 与( p 。) ， 吼) ) ，它们全部是唯一的。这些序 列常用来表示下列分解和重构算法，其中， a 。) 与 b k ) 称为分解序列， 既) 与 吼) 称为重构序列。 ( 1 ) 分解算法 f j ( t ) l 和g j ( t ) 都具有唯一的级数表示 ff j c t ) = 巳，。( 2 7 t 一尼) ) ：圭屯昨扯妁 q 。2 d 其中， c j , k ) ， 嘭 ) 严。，_ 代表小波分解的级。并且我们有意识地隐藏了规范化 系数2 ，坨，用矽( 2 7 t - k ) ，y ( 2 7 t - c ) 代替，女( f ) ，| ；c ，i ( f ) 。 乃“( o - - e c 川，“t - 1 ) = l k ：。( 2 7 f 一七) + 沙( 2 7 t - k ) ) l = i 口，一：。c 。，l ( 2 f 一尼) + l 岛一：。c j + ，1 5 f ，( 2