（电路与系统专业论文）基于自适应提升小波的图像压缩[电路与系统专业优秀论文].pdf

摘要 目前，基于小波变换的图像压缩技术是当前图像压缩领域的主要研究方向。 提升方法能够方便的构造从整数到整数的小波，为图像的无损压缩研究提供了有 力的工具。 本文工作主要分为两部分：第一，研究了提升小波变换以及自适应方法，然 后针对一种改进的自适应方法，通过计算机仿真验证了算法的有效性。该自适应 方法是根据图像的具体特征，从一组具有不同小波基的预测器中，选取较好的预 测器，从而得到较好的无损压缩效果。该结构保持完全重构，需要较少的存储空 间，适合硬件实现。第二，研究了该自适应提升小波的f p g a 实现技术，给出了 实现的结构和电路，并通过仿真验证了其正确性。 关键词：自适应提升方法小波变换图像压缩 a b s t r a c t n o w ，w a v e l e tt r a n s f 0 皿f o ri m a g ec o m p f 船s i o ni st h ci m p o n a i l tm e t h o di i m a g e c o m p r c s s i o nf i e l d i j f t i gs c h e m ec 姐i m p l e m e n tt h ew a v e l e tt r 柚s f b m st h tm a p i n t e g e rt oi i l t c g c r ，w h i c hp v i d e sm ee 任b d i v e 啪lf o rs u d y j n gt l l e1 0 s s l e s si m a g e c o m p r c s s i o n 1 1 l i sp 印c ri sc o m p o s e do fm op a f t s ：f i r s t ，w es t u d yt h el i f t i n gw a v e l e t 岫s f o j _ i a i l d i t sa d 印t i v em c t h o d n 锄w ev a l i d a t e 髓i m p r 0 v e da d a p t i v em e t h o db ye x p e r i i i l e n t a l f c s 川t s b a s e d0 nt h ec h 缸矾钯稻o fi m 8 9 e s ，t h eb e s t 册ec a nb es e l e d e d 丘d ms o m e p r c d i c t o f s ，w h i c hh a v ed i 如f e n tw a v d e tb a s e s n eb e t t c fc o m p r c s s i o nc 柚b ey i e l d c d t h ea r c h i l e d l l r ek e e p sp e 血dr c c 0 璐t r u 胡o n ，n e e d sl e s sm e m o r ya i l di ss u i t e df o r h a f d w 盯ei i n p l 锄e n t s e c o n d ，w es t u d yt h ci l n p l e m e n tt e c l l i l o l o g yo fa d a p t i v el 讯i n g w a v e l e ta n dg i v eo u tl h e 删t e c l u r e 粕dt l l ed r c 洒t a c c o r d i n g 0t h es i m u l a t i 彻，l h e f e s u l ti sv a i i d a t e d 1 【e y w o r d s ：a d a p t i v eu m 嘴s c h e 眦w a v e i e tt m 瑚f o mi m a 咎m 唧i o n 独创性( 或刨新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：! 虱望立日期：哆 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布的全部或 部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解 密后遵守此规定) 本学位论文属于保密在年解密后适用本授权书。 本人签名： ! 墨 鱼i 日期：丛：篁 导师签名：刎日期：翌五：包：主 第一章绪论 第一章绪论 1 1 论文选题背景和研究意义 随着数字化进程的加速以及计算机、网络和通讯技术的迅速发展，人们对数 据、语音和多媒体业务的需求不断增加，需要传输的数据量不断增大，然而由于 存储空间和带宽资源等方面的限制，人们对图像压缩技术也提出了更高的要求。 如：一幅分辨率为6 4 0 们0 ，2 5 6 色的彩色图像，若每个像素占2 4 位，则需要 7 3 7 m b i t s 的存储窑问。如果是活动图像( 如可视电话、远程会议、数字电视) ， 以3 0 帧s 的速度播放，则视频信号的传输率要高达2 2 0 m b s 。而一张6 0 0 m b 的 光盘，仅能存放2 0 秒左右的画面信息。f b i 拥有2 5 0 0 多万个卡片，每个卡片有 1 0 幅指纹图像，如果不经过压缩，存储这些图像需要2 5 0 多万亿字节的存储空间， 那么对于图像的整理、存储和搜索几乎是不可能的。由此可见，图像压缩的必要 性及其社会效益、经济效益将越来越明显。 图像压缩所解决的问题是尽量减少表示数字图像所需要的数据量，同时又要 能保持恢复图像的质量，满足规定的要求。以数学的观点来看，这一过程实际上 就是将二维像素阵列变换为一个在统计上无关联的数据集合。这种变换在图像存 储或传输之前进行。在以后的某个时候，再对压缩图像进行解压缩来重构原图像 或原图像的近似图像。图像压缩技术节省了数据的存储空间，这样不论是在传输 数据还是在处理数据的时候都会绘我们带来很大的便利。 图像数据能够进行压缩，是因为图像数据是高度相关的1 1 1 。大多数图像内相邻 像素之间有较大的相关性，存在很大的冗余度，即空间冗余度。序列图像前后帧 之间有较大的相关性，即时间冗余度。若用相同码长表示不同出现概率的符号也 会造成比特数的浪费，即符号冗余度。由于大部分图像的最终接收者是人眼，而 人眼对图像中不同部分的敏感程度是不同的，去处其中对人眼不敏感或意义不大 的部分，对图像的主观质量不会有很大的影响，即视觉冗余。 1 2 图像压缩编码技术介绍 从通信系统的角度来划分，图像压缩属于信源编码的范畴，也称为图像编码。 图像压缩编码就是对图像数据采用不同的表达方法，以减少表示图像所需的数据 量。 图像压缩编码系统的基本原理如图1 1 所示： 2基于自适应提升小波的图像压缩 数据 数据 图1 1 图像压缩编码系统 首先对原始图像进行映射变换，然后进行量化和编码。映射变换对图像信息 进行恰当的分解与表征，改变图像数据的特性，去除图像空间域、时间域、频率 域冗余度，使之便于进行压缩编码。 量化器通过分层将映射变换后的连续的模拟量离散化，以利于数字处理。根 据样本取值范围分层的均匀与否，量化可分为均匀( 线性) 量化和非均匀( 非线 性) 量化。另外，如果对映射变化后的数据逐个进行量化，则称为标量量化；若 是成组进行量化，则称为矢量量化。量化引入误差，劳且在重建图像时不可恢复。 但由于人眼的视觉特性允许重建图像有一定的失真，从而使得能够保持一定重建 图像质量的量化成为可能。如何充分利用人眼的视觉特性，通过量化消除图像的 视觉冗余度，是量化器设计的关键问题。 编码器通常称为熵编码器，其目的在于寻找一种合适的编码方法，最大限度 地去处量化后数据的符号冗余度，输出最终的二进制码流。编码技术的基础理论 是s h a n n 的信息论。 解码器是编码器的逆过程，首先对码流进行熵解码，然后反量化和反映射变 换，最后得到复原图像。 图像压缩编码的方法有许多种，从不同角度出发有不同的分类方法，比如从 压缩的角度出发可分为两大类： ( 1 ) 无损压缩，是利用数据的统计冗余进行压缩，可完全恢复原始数据而不 引入任何失真。具体讲就是解码图像和原始图像严格相同，从数学上讲是一种可 逆运算。虽然无损压缩不存在信息的减少，但是同时也意味着压缩比不会太大。 这类方法广泛应用于文本数据、程序和特殊应用场合的图像数据( 如指纹图像、 医学图像、遥感图像等) 的压缩。由于压缩比的限制，仅使用无损压缩方法不可 能解决图像和数字视频的存储和传输问题。 ( 2 ) 有损压缩，是利用了人类视觉对图像中的某些频率成分不敏感的特性， 第一章绪论 允许压缩过程中损失一定的信息。也就是说解码图像和原始图像是有差别的，允 许有一定的失真。虽然不能完全恢复原始数据，但是所损失的部分对理解原始图 像的影响较小，却换来了大的多的压缩比。有损压缩广泛应用于语音、图像和视 频数据的压缩。 从信源编码的角度来分类，图像压缩编码可以分为匹配编码、变换编码和识 别编码。从目前已有的使用方案的角度来分类，可以分为预测编码、变换编码和 统计编码。 图像压缩编码技术可以追溯到1 9 4 8 年提出的电视信号数字化，到今天已经有 5 0 多年的历史，大致经历了以下三个阶段。 早期阶段 5 0 到7 0 年代，是图像医缩编码发展的早期阶段，主要是基于信息论的熵编码。 常用的熵编码有游程编码、霍夫曼编码与算术编码等。霍夫曼编码的理论依据是 变字长编码理论。编码器的编码输出码字是字长不等的码字，按编码输入信息符 号的出现统计概率，给输出码字分配以不同的字长。对编码输入中出现概率大的 信息符号，赋以短字长的输出码字；出现概率小的信息符号，赋以长字长的输出 码字。 人们又发现图像数据中相邻像素之间存在很强的空间冗余，提出了以差分脉冲 编码调制( d p c m ) 为代表的各种预测编码方法和内插编码方法。d p c m 方法就是首 先根据算法模型，用原有的样本值对新样本进行预测，得到新样本的预测值。然 后，取新样本的实际数值，和预测值进行比较，二者相减得到差值，最后对差值 进行编码。 中期阶段 1 9 8 5 年，m k l m t 提出“第二代图像编码技术”的概念f 2 】。其特点是不局限于 信息论的框架，充分利用人的视觉生理、心理和图像信源的各种特征，来获得高 压缩比。主要有子带图像编码、基于方向性分解的编码、基于区域分割和合并的 编码。 该阶段，还提出了一种重要的编码方法混合编码方法。经过多年的研究和 探索，人们逐渐认识至4 仅仅使用一种编码方法很难去除多种相关性，而将多种编 码方法结合起来能够得到更好的压缩效果。混合编码就是根据应用场合的不同， 选择几种熵编码和变换编码方法组合在一起，构成一种新的混合编码方法。例如 在j p e g 标准中【3 1 ，就采用了d c r 、霍夫曼编码和算术编码等多种编码方法。 目前阶段 8 0 年代末到9 0 年代中期，大量崭新的数学理论成果被引入图像编码领域，比 如：分形理论、神经网络理论和小波理论。 分形图像编码主要是以分形理论中的收缩仿射变换和迭代函数系统作为理论 d 基于自适应提升小波的图像压缩 基础的。它与经典的图像数据压缩方法相比，在思维方式上有很大的突破，其压 缩比在理论上可超过经典压缩方法的几个数量级，分形图像压缩的发明人之一 m b a m s l e v 在1 9 8 8 年发表的论文中宣称分形图像压缩可达到1 0 0 0 ：1 的压缩比。 分形图像压缩极高的压缩比、快速的解压缩速度颇引人关注。分形图像压缩是有 失真的。失真量大小与压缩比有密切的关系。但分形编码受到分形模型建立复杂、 编码时间长和难以与传统编码技术结合等多方面的限制，其压缩效果仍无法达到 预期目标，还有待于进一步的研究。 人工神经网络i 矗d a ln e u r a ln c t w o r k ) 的研究兴起于8 0 年代中期，其本质是 模仿人脑处理问题的方法，通过各种人工神经元网络模型对数据进行非线性压缩， 具有自学习性、大规模并行处理、非线性处理和分布式存储等许多优点。人工神 经网络是一种非线性动态网络，工作过程一般分为训练和工作两个阶段。训练阶 段就是使用一些训练图像和训练算法，调整网络的权重，使重建图像的误差最小。 目前直接用于图像压缩编码的神经网络主要有反向误差传输型和自组织映射型。 小波变换是一种变分辨率的分析方法。它对高频信号采用小时窑，对低频信 号采用大时窗进行分析。这正好与自然界中高频信号一般持续时问短，而低频信 号持续时问较长的时频分布特性相吻合，非常适合于图像处理。j p e g 2 0 0 0 标准【4 j 棚 的核心就是采用了小波变换。基于小波变换的图像压缩技术是当前图像压缩领域 的主要研究方向。 1 3 本文的主要工作 本文工作主要分为两部分：研究自适应提升小波变换在图像无损压缩方面的 应用，并提出了一种改进的方法；研究该自适应提升小波变换的硬件实现方法。 主要内容安排如下： 第一章为绪论，介绍论文的选题背景、研究意义，以及图像压缩编码技术的 发展状况。 第二章，首先回顾了小波理论的发展，然后介绍了小波变换的定义，阐述了 小波变换的基本思想，最后主要介绍了m a i j 玎算法和提升方法。 第三章，首先介绍了小波变换在图像压缩中的应用，然后介绍了自适应提升 小波变换的原理，并提出了一种改进的自适应方法。 第四章，主要介绍了基于即e 陡的e d a 设计方法以及该自适应提升小波的硬 件实现方法。 第五章，对本文工作进行总结，并指出进一步研究的方向。 第二章小波变换基本原理 第二章小波变换基本原理 2 1 小波理论发展回顾 小波分析是近年来兴起的一套非常热门的信号分析理论，被认为是继f o u i i e r 分析之后的一个新的突破性进展。它给许多相关领域带来了崭新的思想，提供了 强有力的工具，在科技界引起了广泛的关注和高度的重视。下面回顾一下小波理 论发展的各个阶段1 7 j 。 小波理论的研究始于上世纪初。1 9 1 0 年，h a r r 提出了规范正交小波基的思想， 构造了紧支撑的正交函数系h 町函数系1 8 】。1 9 3 6 年，【j t n c w o o d 和p a l e y 建立 了一组i j t e w d p a l e v 基，这为小波后来的发展奠定了理论基础。 小波的概念应该是1 9 8 2 年提出来的。法国地球物理学家j m o r e t 在分析地震 数据时提出地震波按照一个确定函数的伸缩、平移系 k 卜妒( 兰二勺；口，6 r ，口一o 【 4 j 展开。随后，他与a g r o s 锄锄共同研究，发展了连续小波变换的几何体系，由此 能将任意一个信号分解成对空间和尺度的贡献。1 9 8 5 年，法国数学家m e y 盯证明 了小波正交系的存在，并构造了具有一定衰减性质的光滑小波函数。1 9 8 9 年，m a l l a t 将计算机视觉领域内的多尺度分析思想引入到小波分析中，提出了多分辨分析概 念，统一了此前所有正交小波的构造，给出了构造正交小波基的一般方法和m a l l a t 塔式算法，并将其应用于图像分析和完全重构【9 1 0 ，1 1 】。m a l l a t 塔式算法是小波变换 的快速算法，它的地位相当于傅立叶变换中的f f t 。1 9 9 0 年，崔锦泰1 1 2 】和王建忠 构造了基于样条的双正交小波函数，并讨论了具有最好局部化性质的尺度函数和 小波函数【1 3 1 4 1 。1 9 9 1 年，w i c k c r h a 髑e r 和c o i 劬a i l 等人通过对母小波函数进行伸 缩、平移和调制运算，提出了小波包的概念【1 5 】，并将m a l l a t 算法进一步深化，得 到了小波包算法。这是在原有的小波理论基础上提出了最佳基的选择方法，这是 对小波理论的一个重大发展f 1 6 l 。小波包是小波理论的扩展。 1 9 9 4 年，s w d d s 提出了一种新的小波构造方法提升方法【1 7 2 。为了与 采用f o u r i c f 变换构造的传统小波相区别，有人将由该方法构造的小波称作第二代 小波，将传统小波称为第一代小波。在一维情形下，小波再也不需要通过一个函 数的伸缩和平移来得到，构造方法变得更加灵活。由s w e l d e n s 的提升方法，我们 很容易构造出整数到整数的小波变换【2 2 】，这样就可以避免第一代小波变换结果为 基于自适应提升小波的图像压缩 浮点数所带来的问题，使得小波变换更加实用。因此，基于提升方法的整数小波 变换广泛应用于图像处理方面【珏矧。 近年来，小波变换在各个领域的应用越来越广泛【2 7 3 1 l ，比如：在信号处理方 面，对于语音、雷达、地震等信号的检测、目标识别都使用了小波变换。小波变 换在数学其它分支中应用于求微分方程、积分方程，概率小波等。小波在通信领 域中也有应用，比如c d m a 、自适应均衡、扩频通信和分形调制等。在图像处理 中，图像数据的压缩、去噪，数字水印，指纹鉴别，模式识别等也广泛使用小波 变换。 2 。2 第一代小波变换原理 小波分析是一种信号与信息处理的工具，是继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 分 析只是考虑时域和频域之间的一对一映射，它以单个变量( 时问或频率) 的函数 表示信号；小波分析则利用联合时间一尺度函数分析非平稳信号，从根本上克服 了f o u r i e r 分析只能以单个变量描述信号的缺点。在小波分析中，利用小波基取 代传统的三角函数基，对函数进行分析和研究。由于小波基是小波函数妒( x ) 经过 平移和伸缩得到的，因此具有简单、灵活、随意的特性，又具有多分辨分析的功 能。它为诸多应用领域提供了新的更为优越、更为方便的分析工具。下面介绍小 波变换的基本原理p 2 。3 6 】。 2 2 1 连续小波变换 v ，( t ) r ( r ) ，( f ) 的连续小波变换定墨l 啊( 啪) 坩m c ，( f 炒( 学产， 内积形式为： 嘿( d ，6 ) - ( ，( r ) ，妒口，( r ) ) 露毒0 ( 2 - 1 ) 式帆，e o ) i i 。一( 半) ，口是胜因子，6 反映位移，其值可正可负。 要使逆变换存在，妒t ) 要满足容许条件： ( 2 2 ) 第二章小波变换基本原理 铲正肾 式中妒b ) 是妒( f ) 的傅里叶变换。 连续小波变换的逆变换为： ，( f ) 。g t e 喝( 咖) ( r ) 熹动 若要求妒是一个窗函数，那么妒还必须属于r 忸) ，即 陋o 枉c * 由容许条件可得曲在原点必定为零，即 妒( o ) - 妒。妞。o 连续小波变换具有如下性质： 性质1 叠加性：设，( f ) = a g ( t ) + 卢 ( f ) ，则 蚂( 口，6 ) = a 暇( 口，6 ) + 卢瞩( 口，6 ) ( 2 - 3 ) ( 2 - 5 ) 性质2 时移性质；若，( f ) 一暇( 口，6 ) ，则，( 卜- f ) 一喝( 盘，6 一f ) 。 性质3 尺度变换：若，( t ) 一暇( 口，6 ) ，则，( c f ) 一去喝( c 4 ，c 6 ) ，其中 性质4 冗余性：连续小波变换中存在信息表述的冗余度。其表现是由连续小 波变换恢复原信号的重构公式不是唯一的，小波变换的核函数妒。( f ) 存在许多可能 的选择。尽管冗余的存在可以提高信号重建时计算的稳定性，但增加了分析和解 释小波变换的结果的困难。 2 2 2 离散小波变换 在实际应用中，经常使用的是离散小波变换( d w t ) 。对连续的尺度参数口和 连续的平移参数6 采用离散化处理： 令以= 盘j ，6 - 脚j 其中，七z ，口0 ，1 ， o 是固定值，则离散小波变换为： 暇，t ( ，) = 扣肚( f ) ，) = 4 i 7 弘( 口i 一蛾) ，o ) 出 ( 2 7 ) 对应的离散小波函数为： 妒j ( f ) z 口i 7 v 0 i 一七6 0 )( 2 8 ) 基于自适应提升小波的图像压缩 特殊的，若口。一2 ，f = 1 ，则称其为二进离散小波变换。 2 2 3 多分辨分析 1 9 8 8 年，m a l l a t 与m e y e r 合作提出了多分辨分析( m u l t i r e s o l u t i o n a n a l y s i s ， 简称m r a ) 的框架，其主要思想是将r 俾) 分解为一串具有不同分辨率的子空间 序列。该子空间序列的极限就是r 俾) ，然后将r 俾) 中的，描述为具有一系列近 似函数的逼近极限，其中每一个近似函数都是，在不同分辨率子空间上的投影。 定义2 1 设e j 。是r 僻) 的一串闭子空间序列，如果满足以下五条性质，则 称杪， 。，为r ( r ) 的一个m r a 。 ( 1 ) 单调性( 包容性) ( 2 ) 遇近性 ( 3 ) 伸缩性： ( 4 ) 平移不变性： 一c k c k c k c t l c k 2 c 甚_ 4 工2 僻) ，q 一 o ) 妒( f ) 巧营( 2 f ) 一。 妒( f ) 巧尊( f 一2 h 七) ，v 七z ( 5 ) 砌e 配基的存在性： 存在妒o ) k ，使得 妒( 2 一卜- 七) ) 。构成巧的砧e s z 基。 令e k 是工2 伍) 空间的一个多分辨分析，则存在一个唯一的函数妒o ) 工2 伍) 使得 妒j - 2 一7 2 妒( 2 一j f 一七l 七z ( 2 9 必定是内的一个标准正交基，其中妒o ) 称为尺度函数。 若妒0 ) 生成一个多分辨分析，那么妒也属于_ 。，并且因为协哪：k z j 是f 。 的一个麟e s z 基，所以存在唯一的f 2 序列协( 七) ) ，它描述尺度函数妒( f ) 的两尺度关 系为： 庐( f ) 。螬任如( 2 f 一七) ( 2 _ 1 0 ) 由定义2 1 的性质( 1 ) 可知+ ，w z ，所以 第二章小波变换基本原理 一+ - o + - ( 2 - 1 1 ) 反复应用式( 2 1 1 ) ，得 r 伍) 一o ( 2 - 1 2 ) 口 同样，象妒o ) 生成一样，存在一个函数妒( f ) 生成闭子空间，且有与式( 2 1 0 ) 类似的双尺度方程 1 5 f o ) 一压g 忙伍一i ) ( 2 - 1 3 ) 式( 2 1 3 ) 称为小波函数双尺度方程。 2 2 4m a l l a t 算法 1 9 8 8 年，m a u a t 将计算机视觉领域内多尺度分析的思想引入到小波分析中， 提出了信号的塔式分解算法，常简称为m a l l a t 算法。m a l l a t 算法在小波分析中的 地位类似于f i 丌算法在傅里叶分析中的地位。 设，t ) r 僻) ，e j 。构成三2 陋) 的多分辨分析，已得到，扛) 在2 7 分辨率下 的粗糙象爿，从而有t + 。o + 1 ，即 爿，。一，+ l ，+ d + l ，( 2 1 4 ) 其中彳，。蝥，砷似o ) ，d ，4 p 雎( f ) 向 蝥瓶o ) 。蝥一妒m ( f ) + p 州- ( f ) 由尺度函数的双尺度方程可得： 蚧，0 ) i 忙锄k ( f ) 由尺度函数的正交性得： ( 妒+ ，。，妒，) 一j i l 伍一2 m ) 由小波函数的双尺度方程得 知m 。，妒似) t g ( 七一2 m ) 由式( 2 1 5 ) 、( 2 - 1 7 ) 和( 2 1 8 ) 得 c m 一2 蝥，t 忙一抽) ( 2 1 5 ) ( 2 1 6 ) ( 2 - 1 7 ) ( 2 1 8 ) ( 2 1 9 ) 1 0 基于自适应提升小波的图像压缩 d m 。蝥卅g 似一加) c 矿量 瞎勘k m + 圣忙一加k 。 ( 2 2 0 ) ( 2 2 1 ) 引入无穷矩阵日t 眠 ) ，g 一( q ) ，其中日。 一| i l + 忙一2 m l g 朋。一占忙一2 ，1 ) ， 则式( 2 - 1 9 ) 、( 2 - 2 0 ) 和( 2 2 1 ) 可写成 黔：嚣，刎h ， ) l q + ，一鹎。” 卜 和 c 一日q “+ g + d + l ，j ；j ，j 一1 ，l o( 2 2 3 ) 其中日，g 分别是h 和g 的共轭转置矩阵。 式( 2 - 2 2 ) 为m a l l a t 一维分解算法，式( 2 2 3 ) 为m a i l a t 一维重构算法，如图2 1 所 示： c o 堕_ + c l 旦。c 2 旦+ q 一一、 ( a ) 分解算法 c 0 j 一c 1 显二c 2 显二一g q 见 ( ”重构算法 图2 1 一维m a l l a t 小波分解和重构算法示意图 由于图像是二维信号，需要进行二维小波变换。利用二维小波变换的可分离 特性，分别对图像的行和列进行一维小波变换，在重构的时候，为了保证变换的 可逆性，一定要按照与分解算法相反的顺序进行变换。这样，就可以得到二维m a l l a t 分解和重构算法。 第二章小波变换基本原理 2 3 第二代小波变换原理 2 3 1 提升方法的基本原理 d a u b e c h i e s 和s w e l d e n s 提出了基于提升方法的小波变换，提升方法所构造的 小波被称为第二代小波【1 他1 1 。人们可以不依赖傅立叶变换，不必通过对一个函数 的伸缩和平移来构造小波，而是通过一种简单的提升方法构造小波。第一代小波 变换都可以找到等效的提升方法。提升方法一般分为三个步骤：分裂( s p l i t ) 、预 测( p r e d i d ) 和更新( u p d a t e ) 。正向变换如图2 2 所示。 x m 】 2 叫+ ， 下 ， s p l i t罔田 【r 一= 一r j 一一叫+ 卜一 d m 】 c m 】 图2 2 提升方法正向变换 ( 1 ) 分裂( s p k t ) 假设输入信号为x 【雅】，将其分解为偶数序列x 。印】和奇数序列艺【拄】，其中 t 【甩】一x 【2 玎】，【 卜x 【2 n + 1 】。 显然，t 陋】和吃】是两个高度相关的子集，分裂过程并不能改善信号的特性， 但是通过后面的提升步骤能够有效的去处两个子集的相关性。 ( 2 ) 预测( p t e d i c t ) 预测过程就是利用相邻的偶数序列t m 来预测奇数序列k 陋】，得到的预测之 差d 陋】为小波系数。如果信号子集之间有很强的相关性，就可以得到很好的效果。 预测过程相当于一个高通滤波器，输出的是输入信号x m 】的高频成分。 d m 】一m 卜罗p ，m + f 】 ( 2 2 4 ) ( 3 ) 更新( u p d a t e ) 更新过程就是由偶数序列t l n 】和细节成分d m 得到尺度系数c 【n 】。它相当于 一个低通滤波器，输出的是输入信号茁加】的低频成分。也就是说，经过分裂与预测 两个步骤产生的子集丢失了原始数据集中的某些整体性质，为了保持这些性质， 必须采用更新过程对其进行修正。 c 咖卜t 】+ 罗h d 坼+ f 】 ( 2 - 2 5 ) 基于自适应提升小波的图像压缩 由于提升方法在结构上保证了完全重构，所以我们只要改变预测器和更新器 的符号，就很容易得到提升方法的逆向变换。如图2 _ 3 所示。 艺加】d _ 】+ p f t n + 7 】 ( 2 - 2 6 ) c 【 卜弘d 【 + 7 】 ( 2 2 7 ) d 印】 c m - ( + 、卜兰+ 丫 厂 i 棚i p m e 够 十l t 。 史 一，、 图2 - 3 提升方法逆向变换 2 3 2l a u r e n t 多项式及e u c u d e 锄算法 假设 ) 是聊r 滤波器，则| i l ( 七) 的z 交换村0 ) 是一个h u r e n t 多项式： 唼懈。 则该l a u r c n t 多项式的阶数i h 0 ) l 定义为： i h 0 ) | 屯一七( 2 2 9 ) 可以看出，滤波器 他) 的长度，是相应的多项式的阶数加一，即： f - l h ( z ) l + 1 ( 2 - 3 0 ) h i l r c n t 多项式有以下性质： ( 1 ) 两个i 丑u r e n t 多项式之和或之差仍然是l a u r e n t 多项式。 ( 2 ) 阶数为，的b u 瑚t 多项式与阶数为f 的i 丑u 蜘t 多项式之积仍然是i 和r e n t 多项式，且阶数为“ 定理2 1 ( e u d i d c 姐分解算法) 取两个i j a u r c n t 多项式口( z ) 和6 ( z ) - 0 ，且 k 乜) j 皂f 6 ( z ) f 。令口。o ) 一口0 ) ，g ) - 6 0 ) ，从f o 开始迭代，则： q + 。0 ) ；6 f ( z ) 6 f + ，扛) 一8 ；q ) 4 q ) n 。0 ) 一g c d ( 口( z ) ，6 0 ) ) ，h 是使屯0 ) 一o 的最小整数。 第二章小波变换基本原理 设阻+ 。q ) i c 慨( z ) 卜则存在拼使得0 ) i o ，迭代在，l 。燃+ l 时结果。迭代次 数为邝s p o ) | + 1 。若令q l + ，0 ) 一q 0 ) 岛( z ) ，则有 【4 0 。】11 j ? 一0 ：， ：暑 c z - 。， 变换形式可以得到： 嘲刊掣计剥 p 3 动 233 根手卜方法的舅柏寿示 假设砷) 是一个因果的腿的滤波器，坼) = 耋z 一。 离散小波变换如图2 4 所示。正变换先分别经过分析低通滤波器石和高通滤波 器喜，然后分别作下采样，而逆变换先分别上采样，然后再经过合成低通滤波器，j l 和高通滤波器g ，其中的四个滤波器都是f m 滤波器。 圈2 4 离散小波变换不意图 完全重构条件可以表示为： p 鼍o 1 j + g ( z 培o 。1 ) ( 2 _ 3 3 ) 1 i l ( z 万( 吨1 ) + g ( z ) 喜( 一z 4 ) o 卜。叫 定义调制矩阵m ( z ) ： 一瞄描1 q 若定义对偶调制矩阵露q ) ，则完全重构条件可以写为： 肘0 1 ) 。m ( z ) 一2 ，( 2 3 5 ) 正交小波变换是一个特例。此时，矗一i ，g 一亭，调制矩阵m 0 ) ；厨( z ) 。西。 滤波器 的多相表示为： 基于自适应提升小波的图像压缩 ( z ) a 吃( z ) + z 。1 吃( z ) 吃表示偶数项系数，吃表示奇数项系数，则： 也( z ) 一k z 。 九g ) 4 ；4 或者为： 恕( z ：) ：型尝盟 啡2 ) = 学 将多相矩阵写成： p 仁，。 乏曷主芝；】 可得： 聊= 却矧 类似的可以定义声( z 、。小波变换可用多相矩阵表示。如图2s 所示。 ( 2 - 3 6 ) ( 2 - 3 7 ) ( 2 - 3 8 ) ( 2 3 9 ) ( 2 - 4 0 ) ( 2 - 4 1 ) ( 2 4 2 ) 图王5 小波变换的多相表示 完全重构条件又可以表示为： p ( z ) p 0 。) 一， ( 2 4 3 ) 假如矩阵p 是非奇异的，那么有： 吲茚。而蠹丽匕篇1 当多相矩阵p ( z ) 对应的行列式为1 时，即也( z ) 0 ) 一吃( z ) 0 ) = 1 ，可以 得到： 。0 ) 一g 。( z 。1 ) 。0 ) - 一g 。( z 一1 ) 邑( z ) t 山。( z 。1 ) ( 2 4 5 ) ( 2 4 6 ) ( 2 4 7 ) 第二章小波变换基本原理 这表明： 2 3 4 小波变换的提升分解 虿。( z ) 耳 。( 2 _ 1 ) 营( z ) 耳z 一1 l i l ( 一z 一2 ) i ( z ) 昌一z 一1 9 ( 一z 一1 ) ( 2 4 8 ) ( 2 4 9 ) ( 2 5 0 ) 定义2 2 如果滤波器对伪，g ) 相应的多相矩阵p 0 ) 满足d e t p ( z ) = 1 ，则称该滤波 器对是互补的。 显然，如果o ，g ) 是互补的，则萌，岳) 也是互补的 定理2 2 ( 提升) 设( 矗，g ) 是互补的，则任何与j l 互补的其它有限滤波器g 可以 表示为如下形式： g “( z ) 一g ( z ) + ( z ) s q 2 )( 2 5 1 ) 其中s 0 ) 是i 舢r c n t 多项式。相反，任何具有这种形式的滤波器都与i l 互补。 圈2 6 娘始提升不葸图 图2 6 是原始提升的表示。定理2 2 也可以写成关于低通滤波器 与后的形式，则 对偶多相矩阵声”为： 声一一声。) 【一。占。) 0 】 ( 2 5 2 ) 从而，新的石滤波器表示为： ( z ) 一i l o ) 一岳o 扣0 。2 )( 2 5 3 ) 定理2 3 ( 对偶提升) 设( ，g ) 是互补的，则任何与g 互补的其它有限滤波器 ” 形如 ”d ) 一1 1 0 ) + 9 0 弘0 2 ) ，其中f ( z ) 是一个i 丑u r e n t 多项式。相反，任何具有 这种形式的滤波器都与g 互补。 对偶提升之后新的多穗矩阵为蜘斗对偶提舻生新韵 岳滤波器：季0 ) ；季q ) 一i ( z ) f ( z 4 ) 。图2 7 是对偶提升的系统表示。 基于自适应提升小波的图像压缩 图2 7 对偶提升示意图 以上的提升步骤能重复进行，可以得到： 定理2 4 已知互补滤波器对( 矗，g ) ，总存在b u r e l l l 多项式岛0 ) ， 1 s is m ，和一个常数置一0 ，使得 荆。郦删。硼瞄。压】 则对偶多相矩阵为： 声c z ，。冉【一墨：一，0 墨一宇。1 1 竽三 图2 8 和2 9 分别表示了提升小波的正变换和逆变换。 ( z ) ， ( 2 5 4 ) ( 2 5 5 ) 图2 8 提升小波正变换 2 3 5 整数提升小波 图2 9 提升小波逆变换 c a l d e r b a n k 和d a u b c c h i 【越】提出了整数到整数的提升小波变换。从公式( 2 2 4 ) 和( 2 - 2 5 ) 可以看出，如果小波滤波器的系数是浮点数，那么其输出结果仍然是小数。 输出结果的小数部分是由其中的“预测”和“更新”滤波器引入的，所以只要对 其取整即可得到整数小波变换。 第二章小波变换基本原理 1 7 嘶叫2 m 卜l 萃a t 胁+ q i 口巧6 ) c 【雄】。t 【n 】+ i 军“，d 【n + 7 1j 2 - 5 7 ) 其中，1 i 表示取整操作。因为两个整数的和与差同时为偶数或奇数，所以取整操 作可以去除冗余。虽然取整操作相当于对原来的小波滤波器系数作了很小的改动， 但是仍然保留着小波的多尺度特性和区域相关性，更重要的是，取整操作不影响 重构特性，整数小波在结构上仍然保持完全重构，只要将“+ ”和“一”互换就 可以得到逆变换。整数小波变换得到的小波系数d i n 】和尺度系数c 砷】都是整数，且 完全重构，在对灰度图像进行无损压缩时是很有用处的。 s + p 变换是由s a i d 和p c a f h n a n 提出的一种整数小波变换，成功地应用于图像 的无损压缩，其性能优于基于线性预测的j p e g 标准。s + p 变换结构如图2 1 0 所 不o s 变换p 变换 c 陋】 d 陋】 图2 1 0s + p 变换示惹圈 假设有一个整数信号m 】，豇一o ，1 ，一1 。首先将z m l 分裂为奇偶两个序列 艺m 】、t 】，然后进行s + p 变换： 吐n 】一艺m 卜t 】c 2 - 5 8 ) 酬吲小l 掣i ( 2 5 9 ) l 厶 j d m 】一盔扣卜l 尸( c m l ) + 丑( 盔砷】) i( 2 - 删 其中式( 2 5 8 ) 与式( 2 - 5 9 ) 被称为s 变换，式( 2 觥称为p 变换。 s 变换的运算非常简单，并且有效地降低信号的一阶熵。但是，其变换后得到 的高通分量之间仍然存在一定的相关性。在s + p 算法中，利用c 陋】和引n 】某些值 基于自适应提升小波的图像压缩 来预测某个d 【n 】的值。 下面列举几种常用的整数提升小波【2 4 】： 5 3 整数提升小波： 9 ，7 m 整数提升小波： ：二篡二藩兰三：皂j c z - 6 - ， c 【n 卜t 研】+ i 丢( d 【h 一1 】+ d 【抖1 ) + 三j d 陋卜b ，+ 。l 毒t 。t _ + 2 ，+ t 陋：- ，一9 g e 研+ q + z e 防，+ 丢j q 6 c 【小帅】+ b 】+ d 【卜1 】) + 丢j s + p b 整数提升小波： d l 【n 】一茗。m 卜工。【行】 c 【n 】x 。【n 】+ l 丢d t 撕】j ( 2 - 6 3 ) 蛳，州+ 怯( 一3 c 体+ 1 】+ c ”雄一1 】捌加+ 1 】) + 丢j 5 1 1 c 整数提升小波： 啪】- 艺”怯瓴卟t m + 1 】) j c 【小咖】一怯斗州) + 割 ( 2 卿 m 川【小品( c 【】- c m - c f n + l 】+ 帕2 】) + 主j 提升小波的优点： 1 原位运算：使用提升方法的快速小波变换可以进行原位运算，类似于快速傅立 叶变换。原始信号可以被快速小波变换结果所覆盖，在整个计算过程中不需要 额外存储单元，节省了存储空问。 2 不必借助傅立叶交换来梅造小波。 3 速度更快：和传统的方法相比，提升小波将变换所需的运算量减少到一半。 4 重构方法简单：由于提升小波在结构上保持完全重构，所以，只需要简单地调 整计算顺序和运算符的正负号就可以得到逆变换。 5 ，利用提升方法很容易建立非线性小波变换，其中一个典型的例子就是整数小波 第二章小波变换基本原理 1 9 变换。这些变换有利于硬件实现和无损图像编码。 2 4 本章小结 本章首先对小波分析的发展进行了回顾，然后详细阐述了小波变换的基本理 论，从多分辨分析到小波交换的快速算法m a l l a t 算法，以及提升小波变换的基 本原理和整数提升小波变换。这一章为下一章的自适应提升小波变换打下了理论 基础。 基于自适应提升小波的图像压缩 第三章基于自适应提升小波的图像压缩 3 1 小波变换在图像压缩中的应用 小波分析是一种时频局部化分析方法，能以有效的信号表征方式来处理图像 中的非平稳信号，为多分辨分析与子带分解提供了个统一的理论框架。因此， 基于小波分解的图像压缩方法越来越引起人们的关注。 在小波理论的研究中，已经发现了许多小波基，在实际应用中，这为人们选 择合适的小波基提供了很大的自由度。小波变换是将图像分解成与人类视觉特性 相匹配的不同分辨率、不同方向性的子带，且变换后将能量集中在某些子带，这 更有利于图像的压缩。基于小波变换的图像压缩方法能有效地克服d c t 变换所造 成的“方块效应”和“蚊式噪声”。新一代的图像压缩标准j p e g 2 0 0 0 中所采用的 就是小波变换，并且支持图像的渐进传输，以及对感兴趣区域进行特别处理。所 以基于小波变换的图像压缩方法成为当前研究的一个重要方向。 3 ，1 1 图像的多分辨分析 一维小波交换将一维数据分解为高频和低频分量。应用于图像韵是二维小波 变换。如果该二维小波变换是可分离的，则可以分解为两个一维小波变换，分别 在水平方向和垂直方向上对图像进行分解，水平分解和垂直分解的先后顺序任意。 每一级变换都将图像数据分解为四个子带图像：l l 子带是垂直和水平方向的低频 分量，u 子带是水平方向的低频分量和垂直方向的高频分量，h l 子带是垂直方 向的低频分量和水平方向的高频分量，i i h 子带是垂直和水平方向的高频分量。 垂直和水平方向均为低频的子带u 。又被称为分析信号，h h 、h l 、l h 三个子带 被称为细节信号。分析信号又可以迸步分解为四个子带，因此，分解后的总的 子带数为3 k + l ，其中k 为分解的层数，如图3 1 所示。 l l ll h 列变换行变换 原始图像 h h lh h 图3 1 图像的多级小波变换 和直接对图像进行二维小波变换相比，可分离的二维小波变换方法简单，计 算量小，因此在基于小波变换的图像压缩研究中，被广泛采用。 第三章基于自适应提升小波的图像压缩 3 1 2 小波基的选择 在实际应用中，对小波基的选择主要考虑以下几个因素【7 ，1 7 ”，3 8 1 ： ( 1 ) 正交性 多尺度分解后的各个子带数据分别落在相互正交的子空间中，且各子带数据 相关性减小。但是除h a a r 小波之外，同时满足正交特性和线性相位特性的f i r 滤波器组是不存在的。因此，一般放宽条件而选用双正交滤波器组。 ( 2 ) 紧支性 一般