（计算数学专业论文）零树编码在图像压缩中的应用.pdf

华中科技大学硕士学位论文 摘要 小波分析和小波变换是八十年代后期发展起来的一种信号处理手段，由于其 在时间( 空州) 频率域良好的局部化性能，特别有利于非平稳信号分析，近年来 在信号处理的各个领域得到了广泛的应用。本文主要研究将零树编码应用于静止 图像压缩编码。 尽管小波变换对图像处理非常有效，但不同的小波基对图像编码的效果是不 同的。我们研究了几种常用的正交小波基和双正交小波基，实验表明在图像处理 中，具有线性相位，正则性的，完全重构的双正交小波基比正交小波基更利于图 像压缩。 零树编码在图像压缩中有重要地位，本文重点讨论了零树编码在无失真图像 压缩中的应用，本文理论上讨论了影响零树编码效率，并给出了影响编码效率的3 个主要参数，即小波基的选取、剩余矩阵编码、零树编码层数。小波分解形成了 图像能量的聚集，这种聚集可以形成更多的零树，而m s r 作为对对偶小波波形集 中度的度量参数同样也可以作为衡量零树编码效率的度量。对于零树编码的层 数通过最少零树编码所需要的比特数来确定。对于剩余矩阵r 的编码，通过统计 的方法，采用了算术编码。 关键词：图像压缩小波变换零树编码剩余矩阵 华中科技大学硕士学位论文 a b s t r a c t t h ew a v e l e ta n a l y s i sa n dt h ew a v e l e tt r a n s f o r ma r en e wt o o l so f s i g n a lp r o c e s s i n g d e v e l o p e di nl a t e rp e r i o db f 8 0 s b e c a u s eo ft h e i rg o o dl o c a l p e r f o r m a n c e si nb o t ht i m e ( s p a c e ) a n df r e q u e n c y , t h e ya r ep a r t i c u l a rf o rt h ea n a l y s i so fn o n s t a t i o n a r ys i g n a l sa n d h a v eb e e nu s e di nv a r i o u sf i e l d so fs i g n a lp r o c e s s i n gr e c e n t l y i nt h i sd i s s e r t a t i o n ，t h e s t i l li m a g e c o m p r e s s i o n b a s e do nw a v e l e tt r a n s f o r mi ss t u d i e d a l t h o u g hw a v e l e tt r a n s f o r mi s e f f i c i e n tf o ri m a g ep r o c e s s i n g ，d i f f e r e n tw a v e l e t b a s e sh a v ed i f f e r e n te f f i c i e n c yf o ri m a g e c o d i n g o u rr e s e a r c hs h o w st h a tl i n e a rp h a s e ， p r e f e c tr e c o n s t r u c t i o na n dr e g u l a r i t yb i o r t h o g o n a lw a v e l e tf i l t e rb a n k sa r eb e t t e rt h a n o r t h o n o r m a lw a v e l e tf i l t e rb a n k sf o ri m a g e c o m p r e s s i o n z e r o t r e e sc o d i n gi so n eo ft h em o s te f f i c i e n ts t i l li m a g e c o m p r e s s i o n ，t h i sp a p e r f o c u s e do nt h ed i s c u s s i o na b o u tz e r o - t r e e si nt h el o s s l e s s i m a g ec o m p r e s s i o n ，a n d a n a l y s i st h et h r e ep a r a m e t e r s - - t h ec h o o s eo fw a v e l e tb a s e d ，t h er e s tm a t r i xc o d i n ga n d t h el a y e ro fz e r o - t r e e s - - w h i c he f f e c t e dt h ee f f i c i e n c yo fz e r o t r e e sc o d i n ga n d g a v et h e m e a n so fh o wt oc h o o s et h ep a r a m e t e r s w a v e l e td e c o m p o s ec a nm a d et h ee n e r g yo f i m a g eg e tt o g e t h e rt ot h el o wf r e q u e n c y , t h u si tt a nf o r mm o r ez e r o f l e e sa n dm s r a s t h em e a s u r eo ft h ee f f i c i e n c yo fz e r o - t r e e sc o d i n g t h el a y e ro ft h ez e r o f l e e sc o d i n g c a nb eg o tb yt h em i n i m u mb i t so fz e r o t r e e sc o d i n g t h er e s tm a t r i x e sr c o d i n ga d o p t s t h em a t hc o d i n g t h o u g h s t a t i s t i c sm e t h o d s k e yw o r d s ：i m a g ec o m p r e s s w a v e l e tt r a n s f o r mz e r o t r e e sc o d i n g t h er e s tm a t r i x 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表域撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确0 式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期：年月日 学位论文版权使用授权书 本学位论文作，尚完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华】科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于1 i 保密口。 ( 请在以上方柏讷打“4 ”) 学位论文作者签名： 日期：年月| 二f 指导教师签名： 日期：年月曰 华中科技大学硕士学位论文 1 1 引言 1 绪论 人类社会已经进入了信息时代，建立在计算机技术和通讯技术上的信息高速 公路使我们能更新、更快、更准确地掌握这种信息。图像信源由于其具有丰富的 信息量而成为传递信息地重要媒介。我们日常所获取地信息有百分之七十以上来 自于眼睛，可以说数字图像正成为信息高速公路上种重要的媒体。数据量大是 数字图像地一个显著特点，例如，按c c i r 6 0 1 标准对常规电视信号进行每秒2 5 帧，每帧分辨率为7 2 0 5 7 6 ，y ：u ：v 为4 ：2 ：2 每个分量8 b i t 的格式进行数字 化，则其总数编码率可达1 6 6 m b s 。这给数字图像的存储、传输带来了极大的困难， 因此必须进行压缩以减少数据量。由于数字图像存在着大量的冗余，故图像数据 可以进行压缩处理。数字图像压缩可追溯到上世纪四十年代所提出的线性p c m 编 码方法，迄今为止已有六十多年的历史。目前数字图像压缩技术已成为信息高速 公路、高清晰电视( h d t v ) 、可视电话、会议电视、多媒体通信等技术的关键， 在航空遥感、生物医学工程等领域也起着重要的作用。 对于一个数字通讯系统而言，数据编码有两方面的含义，它包括信源编码和 信道编码。信源编码主要解决有效性问题，其主要目的是：通过去除信源中各符 号间的相关性或信源中各符号出现的概率尽可能相等的方法，在不丢失信息量的 前提下尽量减少信源输出符号序列的冗余度，提高符号的平均信息量( 信源熵) 。 此外，数据的加密等处理也可在信源编码中进行。由于信息需要物理媒质进行传 送，所以信道编码主要解决可靠性问题，并通过信道编码使编码后的数据在信道 中能传送最大的信息率，提高信道的利用率和信息的传输质量。本文将主要针对 信源中灰度图像的压缩编码进行研究，尤其是零树编码在静止图像中的压缩。 1 2 图像数据压缩简介 图像数据压缩是指以较少的比特率有损或无损地( 指信息) 表示原来的象素 华中科技大学硕士学位论文 矩阵的技术，也称图像编码。由于图像数据中通常存在这种信息的冗余，如空间 冗余、时间冗余、信息嫡冗余、结构冗余、知识冗余和视觉冗余等冗余信息。减 少或消除信源的各种冗余度是实际图像数据压缩的基本依据。图像压缩研究的就 是寻找高压缩比的方法且压缩后的图像要有合适的信噪比，在压缩传输后恢复原 信号，且在压缩、传输、恢复过程中，还要求图像的失真度小。 图像压缩过程常称为编码，图像恢复过程常称为解码。根据解码后的数据与 原始数据是否完全一致来分类，图像压缩方法一般划分为无失真编码和失真编码 两大类。 1 2 1 无失真编码 无失真编码又称为熵编码( e n t r o p yc o d i n g ) ，要求在解码后得到的图像与原图 像严格相同。 ( 1 ) h u f f m a n 编码：是无失真离散信源变长编码的最佳方法。在变字长编码 中，对出现概率大的信息符号编以短字长的码字，对于出现概率小的信息符号编 以长字长的码字，则平均码长一定小于其他任何符号顺序排列方式，以达到缩短 平均码长，实现压缩数据的目的。 ( 2 ) 游程编码：是将图像特定方向上具有相同灰度值的连续串用一代表值和 串长度来表示，实现数据压缩。 ( 3 ) 算术编码：用单个的浮点输出数值代替一输入信号流，对较长的复杂的 信息，输出就需要更多的位数，具有自适应功能，能自动调整对输出符号的概率 估值。 ( 4 ) l z w 编码：l z w 算法基于一转换表，将可变长度的符号串变成定长的 码字，如果码字小于它们替代的符号串，就产生了压缩。 1 2 2 率失真编码 率失真编码的解码图像较之原始图像存在一定的误差，但视觉效果一般是可 以接受的，即人眼决不出失真或是即使有失真但在可接受的范围。 ( 1 ) 预测编码：是一毒孛针对统计冗余进行压缩的方法，它反映图像内相邻两 华中科技大学硕士学位论文 象素之间的相关性，因而一个象素可以由与它相邻的并且已被编码的象素来进行 预测统计。预测是根据某一个模型进行的，理论上讲，只要模型选取的足够好， 则只需存储或传输起始象素与模型参数就就可以代替一副图像。如差分脉冲调制 法d p c m ，其理论是基于图像中相邻象素间存在相关性。 ( 2 ) 分频带编码：将图像数据变换到频域后，按频率分频带，然后用不同的 量化器进行量化，从而达到最优的组合。 ( 3 ) 变换编码：不是直接对时域图像信号进行编码，而是将时域信号( 空间) 变换到系数域( 频域) 上进行处理，对产生的变换系数进行量化、编码。在变换 后，由于在频域上信息是按照频谱的能量与频率分布排列的，只要对频域平面量 化器进行合理的比特分配，就能得到较高的压缩比。 ( 4 ) 结构编码：编码时首先将图像中的边界、轮廓和纹理等结构特征求出来， 然后保存这些信息参数，解码时根据结构和参数信息进行反合成，从而恢复图像。 1 3 图像编码标准 随着通信技术的迅速发展，人们对于图像数据传输的需求也越来越大，为了 适于图像压缩编码技术的商品化和工业化，在上世纪八十年代末九十年代初终于 产生了针对不同应用场合的一系列图像编码国际标准( 草案) 。这些标准是四十多 年来这一领域研究成果的集中体现。这些压缩标准本身都是开发的标准系统，它 也推动着新的压缩编码技术发展，“全屏幕、全运动、离质量”将是今后图像压缩 标准发展的方向。 1 3 1 静止图像的编码标准 静止图像的编码标准有两个，它们是用于二值传真图像压缩的j p i g 标准和适 用于各种分辨率与格式的彩色和灰度图像压缩的j p e g 标准。 ( 1 )二值图像的编码标准一一j p i g1 9 8 8 年i s o i e c j t c i s c 2 w g 9 和 c c i t t 第1 3 研究组成立了“联合二值图像专家组”( j o i n tb i 1 e v e li m a g ee x p e l s g r o u p ) ，该小组的任务是研究制定用于二值图像的累进编码( p r o g r e s s i v e e n c o d i n g ) 华中科技大学硕士学位论文 标准。1 9 9 2 年1 0 月，该小组提出了一个正式建议( i s o i e c c d 一1 1 5 4 4 或c c i t t 8 2 建议草案) ，该建议就是j p i g 标准，它包括了累进编码、兼容的累进川顷序编码和 单层编码三种编码模式。该标准的第一个特点是编码效率高，与c c i t tt 4 ( g 3 ) 芹d t 6 ( g 4 ) 所建议的m h 、m r 、m m r 编码方法相比，对于典型的文本和线条文件， 压缩比是g 4 中m m r 的1 ，l 1 5 倍。第二个特点是可以通过参数定义，利用 p r e s ( p r o g r e s s i v er e d u c t i o ns t a n d a r d ) 算法生成原始图像的半分辨率，实现二值图像 的累进编码。第三个特点是该建议可以用于灰度和彩色图像的信息保持型压缩编 码。 ( 2 ) 静止图像压缩标准- - j p e gj p e g 标准是由国际标准化组织( i s o ) 和 c c i t t 第1 5 专家组( s g - - x v ) 组成的“联合图片专家组”( j o i n t p h o t o g r a p h i c e x p e r t s g r o u p ) 在1 9 9 1 年正式制定的，该标准建议的压缩算法包括三部分：基本系统 ( b a s e l i n es y s t e m ) 、扩展系统( e x t e n d e ds y s t e m ) 和独立的信息保持型压缩。标 准规定所有基于j p e g 标准的编解码器都必须含有一个基本系统。基本系统提供 顺序扫描重建( s e q u e n t i a lb u i l d - u p ) 图像，实现图像的有关失真压缩编码。具体 的编码方法为采用8 8 分块d c t 变换以消除快中象素间的相关性，通过结合人 眼视觉特征和白适应技术设计的量化器对变换系数进行量化，而对量化后的结果 通过z i g - - z i g 法将二维矩阵系数展开成一维数列并采用h u f f m a n 码进行熵编码。 概括的说，j p e g 采用d c t + q + v l c 算术进行图像编码。 1 3 2 运动图像的编码标准 运动图像编码标准包括h 2 6 1 、m p e g 一1 、m p e g 2 和h 2 6 3 等，这些标准可 适用于这种不同码率、质量要求的应用场合。 ( 1 ) h 2 6 1 标准建议h 2 6 1 标准建议是由c c i t t 的s g x v 成立的“可视电 话编码专家组”于1 9 9 0 年底前提出的，它是为电视电话会议制定的有失真压缩编 码算法。为t * u 用序列图像在时间上的相关性，该建议采用运动估计、运动补偿 的帧间预测的方式，并对帧间预测误差和帧间图像进行d c t 变换以利用图像在空 间域上的相关性，对于d c t 变换系数则采用符合人眼视觉特征的量化器进行量化， 量化后的系数采用h u f f r n a n 变长编码实现熵编码。该建议确立了序列图像压缩的 华中科技大学硕士学位论文 m c + d c t + q + v l c 编码方案。此外，h 2 6 1 对图像格式作了统一的规定：“公用中 i 副格式”( c i f ：c o m m o ni n t e r m e d i a t ef o r m a t ) 和q c i t ( q u a r t e rc i f ) 两种。 ( 2 ) m p e g l 标准m p e g 1 标准的任务是将视频信号及其伴音以可接受的重 建质量压缩到1 5 m b s 的码率，并符号成一个单一的m p e g 位流，同时保证视频 和音频的同步，对于视频信号的压缩编码，m p e g 1 所用编码算法与h 2 6 1 建议基 本相同，但在传输码率上，h 2 6 1 算法随p 取值不同码率可变，而m p e g l 固定 1 5 m b s 的传输码率，此外，h 2 6 1 中未对声音的编码方法作出规定。 在m p e g l 算法中，为了更多的去除序列图像的时间冗余度同时满足多媒体 等应用所必须的随机存取的要求，浚标准将图像序列划分为帧间图像( i n t r a p i c t u r e s ) 、预测图像( p r e d i c t e dp i c t u r e s ) 和双向图像( b i d i r e c t i o n a lp i c t u r e s ) 三 种类型。对于帧内图像( i - 帧) 采用类似j p e g 算法进行编码。对于预测图像( p 一 帧) ，通过i - 帧或p 帧进行预测，然后对预测误差作有条件的传送。对于双向图像 ( b - 帧) ，通过前、后帧图像作为参考进行双向预测，由于b 帧图像不会被用作其 他图像的预测基准，因此预测误差不会被传播，双向预测技术是m p e g 一1 标准的 一个特色。 ( 3 ) m p e g 2 标准m p e g 一2 标准是在m p e g 1 基础上作了重要扩展和改进后 提出的，其工作始于1 9 9 0 年7 月，在1 9 9 3 年1 1 月汉城会议上正式通过m p e g 一2 标准的建议草案。 在m p e g 一2 标准中，针对常规电视图像隔行扫描方式设置了按帧( f r a m e ) 编 码和按场( f i e l d ) 编码两种模式，并相应地对运动补偿作了扩展。对于图像不同 分辨率的要求，m p e g 2 制定了4 级( l e v e l ) 5 类( p r o f i l e ) 共1 1 种单独的技术 规范集( s p e c i f i c a t i o ns e t s ) ，其中最重要地4 种技术规范为：基本级的基本型 ( m p m l ) 、基本级地简单型( s p m l ) 、高级型的基本型( m p m l ) ：g l n 1 4 4 0 缴的空间可调型( s s p 1 4 4 0 ) 。在1 9 9 3 年下半年，美国“大联盟”( o a ：g r a n d a l l i a n c e ) 和欧洲的数字视频广播d v b 计划( d i g i t a l v i d e ob r o a d c a s t p r o j e c t ) 已先 后决定将m p e g 2 建议用于自己的h d t v ( h i g h d e f i n i t i o nt v ) 。 ( 4 ) h2 6 3 标准h 2 6 3 标准着重于低码率序列图像压缩，其编码算法与h 2 6 l 华中科技大学硕士学位论文 类似但有所改进和扩展。在图像格式上，h 2 6 3 标准规定了五种图像格式：亚 q c i f ( s u b q c i f ) 、q c i f 、c i f 、4c i f 和1 6q c i f 。此外采用了半象素精度的运动 补偿技术，在h 2 6 1 中只采用整象素精度的运动补偿。为改进算法性能，采用了 无限制运动矢量( u n r e s t r i c t e dm o t i o nv e c t o r s ) 、基于语法的算术编码( s y n t a x b a s e d a r i t h m e t i cc o d i n g ) 、高级预测( a d v a n c e dp r e d i c t i o n ) 和p b 帧( p bf r a m e ) 四个 协议编码方案。 1 4 小波理论的发展概况 小波理论是近年来兴起的一个崭新的信号分析理论。它的出现吸引了许多领 域的学者对之进行深入的研究，目前正受到数学界和工程界的极大重视。虽然真 正的小波研究高潮起始于上世纪8 0 年代后期，但它的基本数学思想却要追溯到上 世纪初。我们知道信号分为平稳信号和非平稳信号，研究稳定信号的理想工具是 f o u r i e r 变换，而非稳定信号可以利用小波变换进行分析。 1 9 0 9 年，h a a r 发现了最简单，我们现称之为h a a r 小波基的标准基，同时打开 了通向小波的道路。h a a r 小波函数y ( d 是一个在 o ，i n 上取值为1 ，而在 1 2 ， 1 1 上取值为一l 的阶梯函数，即： i i v z ( x ) = 一1 1 0 ， x 0 , 1 2 ) x t 2 ，o ) 其他 19 3 6 年l i t t l e w o r d 和p a l e y 对傅立叶级数建立了二进制频率分量分组理论，即 l p 理论，分组后的傅立叶变换序列相当于带通滤波器作用于原序列，使得l p 理 论具备了频率域内以任意尺度分析函数的能力，这是最早的多尺度分析的思想。 19 5 2 年至1 9 6 2 年c a l d e r o n 、z y g m u n d 、s t e m 和w e i s s 等人将l - p 理论推广到高维 情况，建立了数学研究领域中的奇异积分算子理论：1 9 6 5 年c a l d e r o n 给出了再生 公式，对任意函数f ( x ) ： f ( x ) ：j f 仍( x 刊( 纵矿f ( y ) ) 咖譬 6 华中科技大学硕士学位论文 式中c p , ( x ) ：一i 妒( 一x ) 且伊( x ) 满足一定的条件。c a l d e r o n 再生公式将函数f ( x ) 表 -f 示成伸缩与平移仍( z y ) 线性组合，其离散形式非常接近于我们现在说的小波展 r 丌；1 9 7 4 年c o i f f m a n 对一维h 一空间和高维日一空间给出了原子分解，原子分解的 意义即使函数空间中的函数可以由该空间的原予按一定的规则完全表示：1 9 7 5 年 c a l d e r o n 利用他自己前面提出的再生公式给出了日，空间的原子分解，现已成为许 多函数分解的出发点；1 9 7 6 年p e e t r e 引入了b e s o v 空间的一组基，其展开的系数 的大小刻画刻b e s o v 空间本身；1 9 8 1 年s t r o m b e r g 在对h a a r 标准正交基改进的基 础上，引入了s o b o l e v 空间的h “正交基，所有这些工作维小波分析奠定了基础。 1 9 8 4 年法国科学家m o l e t 在分析地震波的局部特性时首先使用了小波变换对 信号进行分析并提出了小波这一术语。什么是小波? 所谓小波就是小的波形，“小” 指其具有衰减性，“波”指其波动性，具有振幅正负相间的振荡形式。数学上的小 波定义如下： 设| ，f ，r ( 只) n l j ( r ) 且妒( o ) = 0 ，则按如下方式生成的函数簇 | l f ，。 ： ( r ) ： d i “2 妒( 上兰) ，口，b r ，d 0 ( 1 1 ) 盘 称为“基本母小波”或“小波基”。定义f ( x ) 的小波变换为： ( p 吃 厂) ( 口，b ) = ( 1 - - 2 ) 式中 表示内积。m o l e t 与理论物理学家g r o s s m a n 共同提出了连续小波变 换的几何体系其基础是平移和伸缩的不变性：1 9 8 5 年法国马赛大学的数学家m a y e r 将m o l e t 的思想与数学研究中已经存在的奇异积分算子理论联系起来，构造了具有 一定衰减性的光滑函数，其二进制尺度位移体系构成了r ( 月) 空阳j 的标准正交基， 同时m e y e r 与g r o s s m a n 及比利时籍科学家d a u b e c h i e s 合作，通过构造了三2 ( 月) 上 的一个准正交完备集的方法选取了小波空间的离散子集，即框架，并证明了一维 小波函数的存在性。随后l e m a r i e 将这一结果推广到n 维情况，并和b a t t l e 分别给 出了具有指数衰减性的小波函数：1 9 8 8 年d a u b e c h i e s 发表了他的著名长篇论文， 华中科技大学硕士学位论文 证明了具有有限紧支集的正交小波的存在性，这就是人们熟知的d a u b e c h i e s 小波 基；1 9 8 9 年数字图像处理的专家s 。m a l l a t 将小波变换用于信号处理，提出了对小 波分析理论具有突破性意义的多分辨分析的概念，统一了在此之前提出的这种小 波构造方法，将小波正交基纳入统一的框架之中。m a l l a t 还在这一框架下给出了二 进小波变换的快速算法。在这以后，人们又构造了许多小波基。当前小波理论的 研究方兴未艾，一是继续研究满足各种不同要求的小波基，一是研究小波分析在 信号分析、语音与图像处理、地震勘探、数值算法、c t 成像、天体识别、机器视 觉、分形及数字电视、系统故障检测和量子力学等多学科领域的应用。 在信号分析领域，小波分析是一种强有力的数学分析工具。事实上，小波分 析理论将一些各自独立发展的信号处理技术，如计算机视觉中的多尺度信号处理、 语音与图像压缩中的子带编码等纳入到一个统一的框架中去。由于小波分析在时 域和频域都有很好的局部化性质，所以较好地解决了时间和频率分辨的矛盾。对 信号的低频成分用窄时窗使得时域分辨率低而频率分辨率高，对信号的高频成分， 用宽时窗使得时域分辨率高而频域分辨率低。这一体现了自适应分辨分析思想的 性质就是小波变换的“变焦性”，使得小波分析在信号处理领域的很多方面如地震 信号处理、语音的合成与分析、信号的奇异性检测与谱估计、图像处理等都取得 了成功的应用。本文主要用小波分解以后将能量集中在低频部分，这样就可以形 成零树结构，这样就可以用零树编码对图像进行压缩。 1 5 小波变换与图像压缩 对信号与图像来说，如果要传输和存储，这就需要快速传输。在同等的通道 容量下，如果信号与图像数据可以压缩后在传输，就可以使传输的数据量变的很 小，也就增加了通信能力。对图像压缩来说，首要的认为就是对图像数据进行压 缩，这就要寻找高压缩比的方法且压缩后的图像要有合适的信噪比，在传输后的 恢复图像中，要保持图像的原始特征不改变。图像最终是依靠于人眼的观察而感 知的，所以某些图像的压缩编码就要考虑人类的视觉特性。这类方法思想在于将 原始图像在频域内作多层分解，然后对分解后得到的信息表示灵活的有选择的编 华中科技大学硕士学位论文 自马。 基于小波变换的图像压缩编码思想是利用二维离散小波变换将原图像分解为 不同分辨率上的子图像：即图像每次变换后分为一个低频子图像和三个高频子图 像：水平高频分量、垂直高频分量和斜线高频分量，在多次变换后可以得到各细 节子图像和一个原图像在该分辨率下的近似子图像。对分解后得到的各子图像， 根据小波系数的特点和人眼的视觉特征分别做不同的量化和编码处理，经过传输 后在对编码过程进行解码，然后利用小波变换的逆变换由各子图像重构出原图像， 以下是小波低频分量的编码和解码流程图，如图1 1 和1 2 所示： 二维 l 原始离散变抉。l 图像小渡系数 | 变换 小渡 重现 变换 窝挠 隧像 盼逆 系数 变换 圈1 i 小波变换低频分蠡的犏福流程圈 二馈i 亲篓卜慧 变换| 龠 化 墓郴b = = =l 信道 刮囊怿囊 重垦_ j 变换i 耋燕i 葚l _ 誊璺 鄹像i 的避i系数i 茬il 册逆 i 变挺ll = jl 整凝 l i 比特律 群h 一 码l 图1 2 小波变换低频分嚣的解码滴程圉 9 华中科技大学硕士学位论文 1 6 本文的研究内容 本文介绍小波理论及其在图像压缩编码应用方面的主要工作，具体工作内容 是： ( 1 ) 首先回顾了图像压缩的发展及图像编码的标准，对小波理论的发展概况 进行了总结。探讨了连续小波和离散小波变换的原理、性质及其特点，分析了小 波变换的时间一频率窗特性，以及一维小波变换与多分辨率离散小波变换技术。 ( 2 ) 分析了正交小波基和双正交小波基，在一般的图像中，双正交小波基的 压缩效果优于正交小波。 ( 3 ) 系统分析了零树小波的编码效率，本文主要从小波基的选取，零树编码 的层数和剩余矩阵的编码三个方面来讨论的。 1 0 华中科技大学硕士学位论文 2 1 小波变换 2 图像的小波变换编码 有关小波理论思想在上世纪初已经形成，但直到八十年代初才发展为统一的 理论框架，它将独立发展起来的各种信号处理技术统一起来，如应用于计算机视 觉的多分辨信号处理、应用于语音和图像压缩的子带编码、应用于数学的小波序 列展开等，都被认为是同一理论的不同研究方面，使小波分析成为传统傅里叶分 析发展史上的一个新旱程碑。小波分析优于傅里叶的地方是，它在时域或空间域 同时具有良好的局部化性能，而且由于对高频成分采用逐步精细的时域或空间域 取样步长，从而可以聚焦到对象的任意细节。小波分析的这一特点，使得它特别 适合非平稳信号的分析，被誉为数学显微镜。 信号的傅立叶变换定义为 + 号 ，( c o ) = i f ( t ) e - j q t d t ( 2 - 1 ) 一 傅立叶变换( 傅立叶分析系数) 用无穷区间上的复正弦基函数和信号的内积 描述了信号中总的频率分布，它将原时域信号的研究转化为在频域上的傅立叶分 析系数的研究，傅立叶分析是纯频域分析。从信号处理的角度讲，傅立叶分析认 为信号f ( t ) 在每个时刻t 的值是频率各个复正弦分量的迭加。傅立叶变换有它本身 固有的缺点，它只适合于确定住的平稳信号，在时空域上傅立叶变换没有任何分 辨率，傅立叶变换在有限频域上的信息都不足以确定在任意小范围内的函数，特 别是非平稳信号在时间轴上的任何突变，其频谱将散布在整个频率轴上。 为了克服这一缺点，g a b o r 于1 9 4 6 年引入了窗口或短时傅立叶变换，即引入 局部( 时域上的局部) 频率参数使局部傅立叶变换在一个时窗内分折时域信号。 假定信号在时窗内近似平稳。设有信号f ( t ) 以及在时间轴以f 为中心有限时窗 华中科技大学硕士学位论文 w ( t ) 是平稳的，则短时信号f ( t ) w ( t f ) 具有以下的傅立叶变换 6 7 ( c o ，f ) = j f ( t ) w ( t r ) e - j “d t ( 2 2 ) 短时傅立叶变换是将信号映射到时频平面中的一个二维函数。从滤波器的角度看 在给定的频率曲，( 2 2 ) 式意味着在整个时域以一个带通滤波器对f ( t ) 滤波，带通 滤波器的冲激响应就是调制在该频率的窗函数。如( f ) 的傅立叶变换为w ( c o ) ， 定义滤波器带宽a f 为 弘需 协， 其中分母为时窗的能量，两个正弦波只有当频率差大于时才能被分辨开来， 因此，短时傅立叶变换的频率分辨率为a f 。同理，时域上的间隔出为 舻：丝型竺( 2 _ 4 ) 0 矿( f ) 1 2 d t 则这两个时域上的脉冲只有当时间差大于血时- a 能被分辨出来。h e i s e n b e r g 不等式指出时域和频域的分辨率不能任意小，时间带宽积的下限为 ，f 石1 ( 2 - 5 ) 所以只能用时间分辨率换取频率分辨率或者相反地用频率分辨率换取时间分辨 率，虽然短时傅立叶变换实现了时一频分析，但仍存在着局限性。一但为短时傅立 叶变换去了一个窗口，且在所有频率上使用了时间的窗函数，则由( 2 3 ) 式和( 2 4 ) 式给出的时频分辨率将在整个平面上固定不变。 为了克服短时傅立叶变换固定频率分辨率的局限性，希望时域分辨率f 和频 率分辨率v 在时一频平面上变化，频率分辨率随着滤波器中心频率的增大而增大， 即，与f 成正比。 华中科技大学硕士学位论文 笪：c( 2 6 ) 1 c 是一常数，分析滤波器则由一系列具有恒定相对带宽的带通滤波器组成。换言之， 分析滤波器的频率响应并不是在频率轴上均匀分布，而是在对数尺度上分布的。 当( 2 - 6 ) 式满足时，a f 和出随着分析滤波器中心频率的变化而变化。当然 他们仍然满足h e i s e n b e r g 不等式，但此时时间分辨率在高频时变得非常细，而频 率分辨率在低频时变得非常好。这种分析对于短时高频成分和长时低频成分组成 的信号非常适宜。这就是小波分析的思想。 从信号分析的角度来看，要求基函数在不同要求有不同的波形，例如为了孤 立信号的不连续性，希望基函数非常短，而在求得细分析时又要求基函数非常长， 因此把这种基函数称为小波基，它是在原型小波妒( f ) f ( r ) 的基础上通过平移伸 缩得到的 一 嘣归击y e ) 沼，) 式中b 为平移因子，口r + 为尺度因子，对大的a 基函数变为伸张型的宽型小 波的低频函数，当d 很小时，基函数变为压缩型的窄小波的高频函数，就有恒定相 对带宽垒；：c ，用 来进行能量归一化。 吖a 定义连续小波变换为信号f ( t ) 与小波基的内积 舻( 口，6 ) = 厂( f ) y 和( t ) d t ( 2 8 ) 由于原型v 4 t ) 用于所有的滤波器冲激响应，因此没有一个尺度是特别重要的，即 小波分析在所有尺度上是自相似的。对于给定频率兀，局部频率( 又称分析频率) ，= j o 随n n n q ：口而变化，它不再和调制频率相联系，而是和时间尺度相联 系。由( 2 7 ) 式可知小波窗函数的窗口形状是变化的。对于高频信号，时窗变窄， 华中科技大学硕士学位论文 频窗变宽，有利于插述信号的细节；对于低频信号，时窗变宽，频窗变窄，有利 于描述信号的整体行为。正是由于小波函数的这种变窗特性，使它能够表示各种 不同频率分量的信号，特别是具有突变性质的信号。 在( 2 8 ) 式中，如将d 离散化，取d = 2 ，j 为倍频程次数，连续小波转化为 小波级数( 相当于傅立叶级数) w ( 2 j , b ) = i 厂( f ) 。( o a t ( 2 9 ) 再对平移因子b 离散化，取b = n a ( n z ) ，得到离散化小波系数( 对应于离散傅 立叶级数) w ( 2 j ，2 j n ) = 2 - ff ( t ) g t + ( 2 一j t n ) a t ( 2 1 0 ) j 如果信号也是离散的，为厂( i ) ，则得到离散小波变换 吲= w ( 2 j , 2 7 n ) = 2 - j 2 y ( 2 一k - n ) f ( k ) ( 2 - 1 1 ) k 在实际应用中运算总是离散的和有限长度的，因此要求小波基函数也是有限长度 的，在数学上称为紧支集( c o m p a c ts u p p o r t ) ，所谓紧支集即在有限的区间外函数为 零。d a u b e c h i e s 基于离散滤波器迭代方法构造了紧支集正交小波基和紧支集双正交 小波基，将所有正交小波的构造统一起来，并为以后的构造设定了框架。 2 2 多分辨分析与m a l l a t 塔式算法 多分辨分析的思想来自于计算机视觉理论。从机器视觉的角度而言，单纯从 灰度信息理解- - n 图像中的物体是很困难的，更重要的是图像中灰度的局部变化， 为了能够较好地理解一个物体，刻画这种局部变换的尺度应该与物体的大小适配。 然而在一般的图像中。需要理解的各种结构拥有不同的大小，因此不可能预先定 一个最佳的分辨率来描述它们。为了解决这一难题，在计算机视觉中采用了不同 的分辨率下处理图像中不同信息的方法，将图像在这种分辨率下的细节提取出来， 得到一个拥有不同分辨率f ，( ，z ) 的图像细节序列。其中f ，分辨率是图像细节定 4 华中科技大学硕士学位论文 义为：在分辨率f ，下对图像的逼近和在分辨率7 川下对图像的逼近之差。这种多分 辨的表示提供了一种图像信息简单的分层描述，在不同的分辨率下，图像的细节 刻画了不同尺度的物理结构。在粗分辨率时，这些细节表示了大的结构信息，提 供了图像的“上下文”描述，因此，很自然地应该分析这些信息，然后，逐渐增 加分析精度。这种由粗到细的分析过程已经广泛应用在立体视觉匹配和模板匹配 中，并且表明与人眼的低级视觉处理是十分相似的。关于分辨率的层次划分，考 虑到计算和推导的方便阱及人眼的视觉特性，一般采用倍频程划分，即分辨率取 值为2 ，。 设4 为分辨率2 上对信号分析的算子，是可测矢量空间r ( r ) 中一系列闭子 空间的投影算子，( z ) 为能量有限的可测信号，即，( x ) l 2 ( r ) ，一可看成空 间上2 ( 月) 中函数在分辨率2 ，上所有可能的分析( 逼近) 集合，则多分辨率分析具有 如下性质： ( 1 ) 正交投影性 在分辨率27 上所有已分析函数中爿，( x ) 是最相似于，( x ) ，即对所有的g ( x ) | | g ( x ) 一f ( x ) j i 到ia 厂( x ) 一f ( x ) | | ( 2 - 1 2 ) 因此算子爿。是矢量空间矿的f 交投影。 ( 2 ) 因果性或单调性 在分辨率2 ”上对f ( x ) 的分析包含所有分辨率2 ，上对原有函数的分析的信息，即 对所有的，z _ 亡+ 1 ( 2 1 3 ) ( 3 ) 线性 a j 厂( x ) 是在分辨率27 上对信号厂( z ) 的分析( 逼近) ，如果再在分辨率厂( x ) 上进行 一次分析，显然a 。( x ) 没有改变，因此 华中科技大学硕士学位论文 a7 a7 = a ( 2 一1 4 ) ( 4 ) 伸缩不变性 被分析的函数厂( x ) 在分辨率27 上的分析和被分析函数f ( 2 x ) 在分辨率2 ”1 上的分 析是完全相同的。或者说被分析函数的空间可以从另一个对分辨率值进行尺度变 化的被分析函数的空问推导出来。矿是分辨率2 。的闭子区间，对所有的z f ( x ) 铮( 2 均矿，+ ( 2 15 ) ( 5 ) 平移不变性 信号f ( x ) 的多分辨分析a f ( x ) 可用单位长度内2 。个抽样值来表征。当f ( x ) 平移 正比于2 7 的长度，则a 。f ( x ) 也同样平移相同的数量，即可用平移相同数量抽样值 来表征。对所有的，z ( 6 ) 逼近性 f ( x ) 铮f ( x 一2 七) 巧 ( 2 1 6 ) u _ = 上2 ( r ) ，n = ( o ) ( 2 1 7 ) ，一 j ( 7 ) r e i s e 基 存在着g ，使得 g ( x t ) i 女z ) ( 即g ( x ) 的整数平移系) 构成的r e i s e 基，基v 妒，存在着唯一的序列和。 l 2 ( z ) ，使得 ( x ) = c ( k ) g ( x 一七) ( 2 1 8 ) t 中的一个函数是由上2 ( z ) 中的唯序列通过中的g ( x ) 的整数平移组成的滤波 器组成，反之任意序列扣。) l 2 ( z ) 确定唯一函数，且存在着正常数a ，b ， 彳b ，使得 刮卯h l2 - b i i4 5 | i 2 ( 2 - 1 9 ) k e z 1 6 华中科技大学硕士学位论文 对所有的矽e 7 0 成立。 满足上述性质的任何矢量空涮集 一) 脚称为r ( r ) 多分辨率分析( 逼近) ，与 之相关联的爿，算子给出了任一上2 ( r ) 在分辨率2 上的分析( 逼近) 。 当j = o 时，闭子区间为时，存在函数( x ) v o ，使得( x ) 的整数平移系 o = t ) ) 。构成的规范正交基，那么函数系 庐 = 女) ) 。：构成规范正交系，即 满足 ( ( x 一，) ，( x t ) ) = 6 1 k ( 2 2 0 ) 式中民是k n o r e c k e r d 函数。设中( 缈) 是庐( x ) 的傅立叶变换，则( 2 - 2 0 ) 式在频 率域表现为： 善j m ( 础石) 2 = 磊1 ( 2 2 1 ) 利用对分辨分析的因果性( 单调性) 性质扩展到z ，若c 三2 ( r ) 是 上2 ( r ) 的多分辨分析，则存在唯一的尺度函数办( x ) 三2 ( r ) ，其伸缩系为 ，( x ) = 2 j 庐( 2 。x )z(