基于小波变换的数据压缩算法的研究与实现
Posted by 天际的荒草 | Posted in Docs | 文档 | Posted on 18-09-2009
标签：EZW算法, 图像压缩, 小波, 离散小波变换
0
目录
摘要 III
ABSTRACT IV
第一章 绪论 1
1.1 课题研究的背景 1
1.2 课题研究的任务和目标 1
1.3 内容安排 2
第二章 小波变换图像压缩技术基础 3
2.1 小波变换简介 3
2.2 小波变换基本理论 4
2.2.1 连续小波变换 4
2.2.2 离散小波变换 7
2.3 多分辨率分析 12
2.4 几种常见的小波 13
2.5 小波变换与图像压缩 15
2.6 从能量角度看小波变换 16
第三章 基于小波变换的图像压缩算法的研究 18
3.1 几种小波图像压缩算法的介绍 18
3.1.1 几种小波图像压缩算法的介绍 18
3.1.2 关于JPEG2000 20
3.2 各种小波图像压缩算法的共性 20
3.3 对各种小波压缩算法的比较及本课题所选方案 21
3.3.1 对各种小波压缩算法的比较 21
3.3.2 本课题所选方案 21
3.4 所选方案的实现 21
3.4.1 EZW算法概述 21
3.4.2 零树的构造 22
3.4.3 扫描方法 23
3.4.4 EZW算法的实现 23
3.5 EZW算法举例 24
3.5.1 树结构 24
3.5.2 编码 25
3.5.3 解码过程 27
3.6 关于编码 28
第四章 基于小波变换的图像压缩算法的软件实现 29
4.1 软件总体功能设计 29
4.2 软件各个模块的实现 30
4.3 软件应用举例 35
4.4 软件评价 37
4.5 本软件系统的优点和不足 38
4.6 值得改进的地方 38
第五章 总结 39
5.1 所做工作的总结 39
5.2展望 39
参考文献 41
致谢 43
附录 44
摘要
信息时代的到来使人们极易获得大量的信息，数字图像就是一种重要的信息载体。如何存储和传输这些图像一直是人们关注的焦点，对此，人们也提出了许多方法和制定了许多标准。小波变换作为一门较新的数学分支，被引入图像处理以后，很快引起了人们的极大兴趣。随着研究的开展，相继出现了许多基于小波变换的图像压缩方式，如嵌入式零树算法（EZW，the Embedded Zerotree Wavelet algorithm ）、分层树集合分割算法（SPIHT，Set Partitioning In Hierarchical Trees）、最佳截断嵌入码块算法 ( EBCOT ，Embedded Block Coding with Optimized Truncation)等等，在此基础上，人们还制定了基于小波变换的国际化图像压缩标准JPEG2000。
本文首先介绍了小波变换理论的发展情况和一些基本的小波理论，然后又介绍了几种基于小波变换的图像压缩技术并对它们做了简单的比较，紧接着重点论述了EZW算法的原理和实现，这也是本文的重点。最后，实现了基于EZW算法的一个软件系统。
关键词： 图像压缩,小波,离散小波变换,EZW算法
ABSTRACT
People can easily obtain a large amount of information with the arrival of the information age, digital image is an important information carrier. How to store and transmit these digital images has been the focus of people’s attention, thus, many methods were proposed and a number of standards were shaped. As a relatively new branch of mathematics, wavelet transform has been introduced into image processing, and quickly caught the great interest. Following this study, many image compression methods which based on wavelet transform have been launched, for example, the Embedded Zerotree Wavelet algorithm (EZW), Set Partitioning In Hierarchical Trees (SPIHT), Embedded Block Coding with Optimized Truncation (EBCOT), and so on. On these basses, it has developed international image compression standard JPEG2000 based on wavelet transform.
Firstly, this paper introduces the basic wavelet transform theory and the development of the wavelet theory, then introduces several image compression technology based on wavelet transform , compares them Simply, and treatises the EZW algorithm and its implementation, which is the focus of this paper. Finally, it’s realized a software system based on the EZW algorithm.
KEY WORDS: Image compressing, Wavelets, Discrete Wavelet Transform, EZW algorithm
第一章 绪论
1.1 课题研究的背景
人类社会已经进入信息时代了。在这个时代，人们每天都可以通过各种手段（如PDA、网络、电视、广播等等）获得大量的信息，而这些信息在我们的日常生活中是不可或缺的。图像信源由于其具有丰富的信息量而成为传递信息地重要媒介。我们日常所获取地信息有百分之七十以上来自于眼睛，可以说数字图像正成为信息高速公路上一种重要的媒体。数据量大是数字图像地一个显著特点，例如，按CCIR601 标准对常规电视信号进行每秒25帧，每帧分辨率为720×576，Y：U：V 为4：2：2 每个分量8bit 的格式进行数字化，则其总数编码率可达166Mb/s[1]。这给数字图像的存储、传输带来了极大的困难，因此必须进行压缩以减少数据量。由于数字图像存在着大量的冗余，故图像数据可以进行压缩处理。数字图像压缩可追溯到上世纪四十年代所提出的线性PCM 编码方法，迄今为止已有六十多年的历史。目前数字图像压缩技术已成为信息高速公路、高清晰电视（HDTV）、可视电话、会议电视、多媒体通信等技术的关键，在航空遥感、生物医学工程等领域也起着重要的作用。
图像数据压缩是指以较少的比特率有损或无损地（指信息）表示原来的象素矩阵的技术，也称图像编码。由于图像数据中通常存在这种信息的冗余，如空间冗余、时间冗余、信息熵冗余、结构冗余、知识冗余和视觉冗余等冗余信息。减少或消除信源的各种冗余度是实际图像数据压缩的基本依据。图像压缩研究的就是寻找高压缩比的方法且压缩后的图像要有合适的信噪比，在压缩传输后恢复原信号且在压缩、传输、恢复过程中，还要求图像的失真度小。
图像压缩过程常称为编码，图像恢复过程常称为解码。根据解码后的数据与原始数据是否完全一致来分类，图像压缩方法一般划分为无失真编码和失真编码两大类。本文的侧重点将放在失真编码部分。
1.2 课题研究的任务和目标
本课题的选题是《基于小波变换的数据压缩的算法研究和应用》，鉴于小波分析理论在图像压缩方面的突出表现和图像数据在人们生活中的重要性，本课题将只研究小波变换在图像数据处理方面的应用。
基于小波变换的图像压缩技术都有其共性，即对图像都要首先进行小波变换，然后再量化编码，各种技术的不同主要体现在量化和编码阶段。本文将对小波变换理论进行系统的论述，然后介绍几种典型的基于小波变换的图像压缩算法，并对它们做简要的分析，接着，本文将选择其中一种算法进行详细的探讨，最后，将用VC++开发工具对此算法进行实现，设计出一个软件系统，这也是本研究的目标。
1.3 内容安排
本文对小波变换图像压缩技术做了比较深入的研究，共分五章，各章的内容安排如下：
第一章简要介绍了本课题的研究背景、研究任务和目标，以及本文的内容安排。
第二章详细介绍了小波变换图像压缩的技术基础。首先详细论述了小波变换理论，然后介绍了几种常用的小波，最后举例将小波变换引入图像压缩，并从能量角度进行了说明。
第三章是本文的重点。本章首先介绍了几种典型的基于小波变换的图像压缩算法，并对它们进行了简单的比较及说明了本课题的所选算法，然后详细的论述了此算法的原理及实现，最后用举例的方式进一步阐述了此算法。
第四章是本课题所选算法的软件实现。首先介绍了软件的总体功能，然后对软件设计中各个模块进行了说明，并对一副图像的进行了压缩，最后对软件做了评价，并讨论了它的优缺点，提出了值得改进的地方。
第五章对本研究做了总结，并对新技术做了展望。
第二章 小波变换图像压缩技术基础
2.1 小波变换简介
小波变换是近十几年才发展起来并迅速应用到图像处理等众多领域的一种数学工具，是继110 多年前的傅立叶(Joseph Fourier)分析之后的一个重大突破，无论是对古老的自然学科还是对新兴的高新技术应用学科都产生了强烈冲击。
傅立叶理论指出，一个信号可表示成一系列正弦和余弦函数之和，叫做傅立叶展开式。用傅立叶表示一个信号时，只有频率分辨率而没有时间分辨率，这就意味我们可以确定信号中包含的所有频率，但不能确定具有这些频率的信号出现在什么时候。为了继承傅立叶分析的优点，同时又克服它的缺点，人们一直在寻找新的方法。20 世纪初，哈尔(Alfred Haar)对在函数空间中寻找一个与傅立叶类似的基非常感兴趣。1909 年，Haar发现了最简单，我们现称之为Haar小波基的标准基，同时打开了通向小波的道路。
1936 年 Littleword 和 Paley 对傅立叶级数建立了二进制频率分量分组理论，即L-P 理论，分组后的傅立叶变换序列相当于带通滤波器作用于原序列，使得L-P 理论具备了频率域内以任意尺度分析函数的能力，这是最早的多尺度分析的思想。1952 年至1962 年 Calderon、Zygmund、Stern 和 Weiss 等人将L-P 理论推广到高维情况，建立了数学研究领域中的奇异积分算子理论。1965 年 Calderon 给出了再生公式[2]，对任意函数f(x)：
(2.1)
式中 且 满足一定的条件。Calderon 再生公式将函数f(x)表示成伸缩与平移 线性组合，其离散形式非常接近于我们现在说的小波展开；1974 年 Coiffman 对一维 空间和高维 空间给出了原子分解，原子分解的意义即使函数空间中的函数可以由该空间的原子按一定的规则完全表示：1975 年Calderon 利用他自己前面提出的再生公式给出了H空间的原子分解，现已成为许多函数分解的出发点；1976 年 Peetre 引入了 Besov空间的一组基，其展开的系数的大小刻画刻 Besov 空间本身；1981 年 Stromberg 在对 Haar标准正交基改进的基础上，引入了 Sobolev空间的H s 正交基，所有这些工作维小波分析奠定了基础。1984 年法国科学家 Molet 在分析地震波的局部特性时首先使用了小波变换对信号进行分析并提出了小波这一术语。什么是小波？所谓小波就是小的波形，“小”指其具有衰减性，“波”指其波动性，具有振幅正负相间的振荡形式。Molet 与理论物理学家 Grossman 共同提出了连续小波变换的几何体系其基础是平移和伸缩的不变性：1985 年法国马赛大学的数学家 Mayer 将 Molet 的思想与数学研究中已经存在的奇异积分算子理论联系起来，构造了具有一定衰减性的光滑函数，其二进制尺度位移体系构成了L2 (R) 空间的标准正交基，同时 Meyer 与 Grossman 及比利时籍科学家 Daubechies 合作，通过构造了L2 (R) 上的一个准正交完备集的方法选取了小波空间的离散子集，即框架，并证明了一维小波函数的存在性。随后 Lemarie 将这一结果推广到n 维情况，并和 Battle 分别给出了具有指数衰减性的小波函数；1988 年Daubechies 发表了他的论文，证明了具有有限紧支集的正交小波的存在性，这就是人们熟 Daubechies小波基；1989 年数字图像处理的专家 S.Malla t将小波变换用于信号处理，提出了对小波分析理论具有突破性意义的多分辨分析的概念，统一了在此之前提出的这种小波构造方法，将小波正交基纳入统一的框架之中。Mallat 还在这一框架下给出了二进小波变换的快速算法——Mallat 算法（FWT）[3，4]。
90 年代，Sweldens 等人提出了用提升方案来构造小波的方法[5,6]，这种以
新的方法构造的小波可以称为第二代小波，以便同以前的小波相区别。第二代小
波构造方法的继承了第一代小波变换的多分辨率特性，同时不依赖于傅立叶变换，因此利于构造非线形的小波，在图像处理等领域有广阔的应用前景。
在这以后，人们又构造了许多小波基。当前小波理论的研究方兴未艾，一是继续研究满足各种不同要求的小波基，一是研究小波分析在信号分析、语音与图像处理、地震勘探、数值算法、CT 成像、天体识别、机器视觉、分形及数字电视、系统故障检测和量子力学等多学科领域的应用。
在信号分析领域，小波分析是一种强有力的数学分析工具。事实上，小波分
析理论将一些各自独立发展的信号处理技术，如计算机视觉中的多尺度信号处理、语音与图像压缩中的子带编码等纳入到一个统一的框架中去。由于小波分析在时域和频域都有很好的局部化性质，所以较好地解决了时间和频率分辨的矛盾。对信号的低频成分用窄时窗使得时域分辨率低而频率分辨率高，对信号的高频成分，用宽时窗使得时域分辨率高而频域分辨率低。这一体现了自适应分辨分析思想的性质就是小波变换的“变焦性”，使得小波分析在信号处理领域的很多方面如地震信号处理、语音的合成与分析、信号的奇异性检测与谱估计、图像处理等都取得了成功的应用。本文主要用小波分解以后将能量集中在低频部分，这样就可以形成零树结构，这样就可以用零树编码对图像进行压缩。
2.2 小波变换基本理论
2.2.1 连续小波变换
1. 一维连续小波变换
定义：设 ，其傅立叶变换为 ，当 满足允许条件(完全重构条件或恒等分辨条件)
< (2.2)
时，我们称 为一个基本小波或母小波[7]。将母函数 经伸缩和平移后得
(2.3)
称其为一个小波序列。其中a为伸缩因子，b为平移因子。对于任意的函数 的连续小波变换[7]为
(2.4)
其重构公式[7](逆变换)为
(2.5)
由于基小波 生成的小波 在小波变换中对被分析的信号起着观测窗的作用，所以 还应该满足一般函数的约束条件
(2.6)
故 是一个连续函数。这意味着，为了满足完全重构条件式， 在原点必须等于0，即
(2.7)
为了使信号重构的实现在数值上是稳定的，处理完全重构条件外，还要求小波 的傅立叶变化满足下面的稳定性条件：
(2.8)
式中 。
从稳定性条件(2.8)可以引出一个重要的概念[7]：
定义(对偶小波) 若小波 满足稳定性条件(2.8)式，则定义一个对偶小波 ，其傅立叶变换 由下式给出：
(2.9)
注意，稳定性条件(2.8)式实际上是对(2.9)式分母的约束条件，它的作用是保证对偶小波的傅立叶变换存在的稳定性。值得指出的是，一个小波的对偶小波一般不是唯一的，然而，在实际应用中，我们又总是希望它们是唯一对应的。因此，寻找具有唯一对偶小波的合适小波也就成为小波分析中最基本的问题。连续小波变换具有以下重要性质：
(1)线性：一个多分量信号的小波变换等于各个分量的小波变换之和。
(2)平移不变性：若f(t)的小波变换为 ，则 的小波变换为 。
(3)伸缩共变性：若f(t)的小波变换为 ，则f(ct)的小波变换为 。
(4)自相似性：对应不同尺度参数a和不同平移参数b的连续小波变换之间是自相似的。
(5)冗余性：连续小波变换中存在信息表述的冗余度。
小波变换的冗余性事实上也是自相似性的直接反映，它主要表现在以下两个方面：
(1)由连续小波变换恢复原信号的重构分式不是唯一的。也就是说，信号f(t)的小波变换与小波重构不存在一一对应关系，而傅立叶变换与傅立叶反变换是一一对应的。
(2)小波变换的核函数即小波函数 存在许多可能的选择(例如，它们可以是非正交小波、正交小波、双正交小波，甚至允许是彼此线性相关的)。
小波变换在不同的(a，b)之间的相关性增加了分析和解释小波变换结果的困难，因此，小波变换的冗余度应尽可能减小，它是小波分析中的主要问题之一[8]。
2. 高维连续小波变换
对 ，公式
(2.10)
存在几种扩展的可能性[7]，一种可能性是选择小波 使其为球对称，其傅立叶变换也同样球对称，
(2.11)
并且其相容性条件变为
(2.12)
对所有的 。
(2.13)
这里， =〈 〉， ，其中 且 ，公式(2.10)也可以写为
(2.14)
如果选择的小波 不是球对称的，但可以用旋转进行同样的扩展与平移。例如，在二维时，可定义
(2.15)
这里， ， ，相容条件变为
(2.16)
该等式对应的重构公式[7]为
(2.17)
对于高于二维的情况，可以给出类似的结论[4]。
2.2.2 离散小波变换
将连续小波变换的缩放因子a离散化，得到二进小波变换；再将其平移因子b也离散化，就得到离散小波变换[7]。
1. 二进小波变换与滤波器
为了适应数字信号处理，需要将小波变换离散化。可以先进行缩放因子的离散：若小波函数 满足
， (2.18)
则称 为基本二进小波。
在连续小波变换中，若 为基本二进小波，则令a = 2k ，得到二进小波变换：
(2.19)
为了构造基本二进小波，可设φ满足：
(2.20)
可推出 ，则φ大体上相当于一个低通滤波器，因此，φ(2x)的通道比φ(x)的宽，可设φ满足如下的双尺度方程：
(2.21)
其Fourier变换为：
，其中
为低通滤波器。由 ，可得H(0) = 1 即∑hn = 1。
若设
，其中
则G为高通滤波器，有
(2.22)
其Fourier变换为：
(2.23)
因 且 ，得G(0) = 0 即∑gn = 0。
2. 离散小波变换
下面再将二进小波变换中的平移因子也离散化：令b = n2k，则可得离散小波变换[7]：
(2.24)
可以用前面所讲的滤波器系数改写成如下循环形式：
(2.25)
其中， ，D= 为差——高频部分，A = 为剩余——低频部分， 与 为上面讲过的滤波器 之系数。
可以写出正反离散小波变换的具体算法如下：
正变换（分解）（保存 和所有 ）
j = 0; ;
while ( j < J ) {
j++;
}
逆变换（重构）（利用正变换所保存下来的 和所有 ）
j = J;
while ( j > 0 ) {
j–;
}
说明：
图形的横纵坐标分别表示时间（平移因子）和变换结果S f与W f的值。
小波分解可以无限进行下去，J是自己指定的最大分解次数，一般为8~10。
求和符号中k∈Z，无上下限，但具体计算时，由于只有有限个hk、gk不为0，所以实际上是有限的。
逆变换中h与g上的一杠表示复数的共轭，对于实h与g，则共轭与不共轭相同。
求S f与W f都涉及到对所有的样本求和，不可能只处理一个样本。
3. 小波分解
执行离散小波变换的有效方法是使用滤波器。该方法是Mallat在1988年开发的，叫做Mallat算法[9]。这种方法实际上是一种信号的分解方法，在数字信号处理中称为双通道子带编码。用滤波器执行离散小波变换的概念如图2.1所示。
其中： 为低通滤波器
为高通滤波器
图2.1 双通道滤波过程
图中，S表示原始的输入信号，通过两个互补的滤波器产生A和D两个信号，A表示信号的近似值(approximations)，D表示信号的细节值(detail)。在许多应用中，信号的低频部分是最重要的，而高频部分起一个“添加剂”的作用。犹如声音那样，把高频分量去掉之后，听起来声音确实是变了，但还能够听清楚说的是什么内容。相反，如果把低频部分去掉，听起来就莫名其妙。在小波分析中，近似值是大的缩放因子产生的系数，表示信号的低频分量。而细节值是小的缩放因子产生的系数，表示信号的高频分量。
由此可见，离散小波变换可以被表示成由低通滤波器和高通滤波器组成的一棵树。原始信号通过这样的一对滤波器进行的分解叫做一级分解。信号的分解过程可以叠代，也就是说可进行多级分解。如果对信号的高频分量不再分解，而对低频分量连续进行分解，就得到许多分辨率较低的低频分量，形成如图2.2所示的一棵比较大的树。这种树叫做小波分解树(wavelet decomposition tree)。分解级数的多少取决于要被分析的数据和用户的需要。小波分解树表示只对信号的低频分量进行连续分解。
为低通滤波器
为高通滤波器
图2.2 小波分解树
在使用滤波器对真实的数字信号进行变换时，得到的数据将是原始数据的两倍。例如， 如果原始信号的数据样本为1000个，通过滤波之后每一个通道的数据均为1000个，总共为2000个。于是,根据尼奎斯特(Nyquist)采样定理就提出了降采样(downsampling)的方法，即在每个通道中每两个样本数据取一个，得到的离散小波变换的系数(coefficient)分别用cD和cA表示，如图2.3所示。图中的符号 表示降采样。
图中 分别表示低通、高通滤波器。
图2.3降采样过程
4. 小波重构
离散小波变换可以用来分析或者叫做分解信号，这个过程叫做分解或者叫做分析。把分解的系数还原成原始信号的过程叫做小波重构(wavelet reconstruction)或者叫做合成(synthesis)，数学上叫做逆离散小波变换(inverse discrete wavelet transform，IDWT)。
在使用滤波器做小波变换时包含滤波和降采样两个过程，在小波重构时要包含升采样(upsampling)和滤波过程。小波重构的方法如图2.4所示，图中的符号 表示升采样。
图中：
为高通滤波器
为低通滤波器
图2.4 小波重构方法
升采样是在两个样本数据之间插入“0”，目的是把信号的分量加长。升采样的过程如图2.5所示。
（a）降采样信号 （b）升采样信号
图2.5 升采样的方法
2.3 多分辨率分析
多分辨率分析MRA(Multi-resolution Analysis)是S. Mallat与Y. Meyer于1986年左右共同引入的。这一程序是构造小波基的一种有效的方法。从函数分析的角度给出了正交小波的数学解释，在空间的概念上形象的说明了小波的多分辨率特性，给出了通用的构造正交小波的方法，并将之前所有的正交小波构造方法统一起来，并类似傅立叶分析中的快速傅立叶算法，给出了小波变换的快速算法—— Mallat算法[9]。这样，在计算上变得可行以后，小波变换在各个领域才发挥它独特的优势，解决了各类问题，为人们提供了更多的关于时域分析的信息。
多分辨分析就是要构造一组函数空间，每组空间的构成都有一个统一的形式，而所有空间的闭包则逼近 。在每个空间中，所有的函数都构成该空间的标准化正交基，而所有函数空间的闭包中的函数则构成 的标准化正交基，那么，如果对信号在这类空间上进行分解，就可以得到相互正交的时频特性。而且由于空间数目是无限可数的，可以很方便地分析我们所关心的信号的某些特性。
下面简要介绍一下多分辨分析的数学理论[8]。
定义：空间 中的多分辨分析是指 满足如下性质的一个空间序列 ：
(1)调一致性： ，对任意
(2)渐进完全性： ，
(3)伸缩完全性：
(4)平移不变性：
(5)Riesz基存在性：存在 ，使得 构成 的Risez基。关于Riesz的具体说明如下：
若 是 的Risez基，则存在常数A，B，且，使得：
(2.26)
对所有双无限可平方和序列 ，即
(2.27)
成立。
满足上述条件的函数空间集合成为一个多分辨分析，如果 生成一个多分辨分析，那么称 为一个尺度函数。
可以用数学方法证明，若 是 的Riesz基，那么存在一种方法可以把 转化为 的标准化正交基。这样，我们只要能找到构成多分辨分析的尺度函数，就可以构造出一组正交小波。
多分辨分析构造了一组函数空间，这组空间是相互嵌套的，即
那么相邻的两个函数空间的差就定义了一个由小波函数构成的空间，即
并且在数学上可以证明 且 ， ，为了说明这些性质，我们首先来介绍一下双尺度差分方程，由于对 ，所以对 ，都有 ，也就是说可以展开成 上的标准化正交基，由于 ，那么 就可以展开成
(2.28)
这就是著名的双尺度差分方程，双尺度差分方程奠定了正交小波变换的理论基础，从数学上可证明，对于任何尺度的 ，它在j+1尺度正交基 上的展开系数 是一定的，这就为我们提供了一个很好的构造多分辨分析的方法。
在频域中，双尺度差分方程的表现形式为：
(2.29)
如果 在 =0连续的话，则有
(2.30)
说明 的性质完全由 决定。
2.4 几种常见的小波
同傅立叶分析不同，小波分析的基（小波函数）不是唯一存在的，所有满足小波条件的函数都可以作为小波函数，那么小波函数选取就成了十分重要的问题[10],一下对几种常见小波[11]做一个简单介绍。
Haar小波
A.Haar于1990年提出一种正交函数系,定义如下：
(2.31)
这是一种最简单的正交小波，即
… (2.32)
Daubechies(dbN)小波系
该小波是Daubechies从两尺度方程系数 出发设计出来的离散正交小波。一般简写为dbN，N是小波的阶数。小波 和尺度函数吁中的支撑区为2N-1。 的消失矩为N。除N＝1外(Haar小波)，dbN不具对称性〔即非线性相位〕；dbN没有显式表达式(除N＝1外)。但 的传递函数的模的平方有显式表达式。假设 ，其中， 为二项式的系数，则有
(2.33)
其中
在本研究的实现中，本文采用的小波就是db9/7小波。
Mexican Hat(mexh)小波
Mexican Hat函数为
(2.34)
它是Gauss函数的二阶导数，因为它像墨西哥帽的截面，所以有时称这个函数为墨西哥帽函数。墨西哥帽函数在时间域与频率域都有很好的局部化，并且满足
(2.35)
由于它的尺度函数不存在，所以不具有正交性。
Meyer函数
Meyer小波函数 和尺度函数 都是在频率域中进行定义的，是具有紧支撑的正交小波。
(2.36)
其中， 为构造Meyer小波的辅助函数，且有
(2.37)
2.5 小波变换与图像压缩
对信号与图像来说，如果要传输和存储，这就需要快速传输。在同等的通道容量下，如果信号与图像数据可以压缩后在传输，就可以使传输的数据量变的很小，也就增加了通信能力。对图像压缩来说，首要的认为就是对图像数据进行压缩，这就要寻找高压缩比的方法且压缩后的图像要有合适的信噪比，在传输后的恢复图像中，要保持图像的原始特征不改变。图像最终是依靠于人眼的观察而感知的，所以某些图像的压缩编码就要考虑人类的视觉特性。这类方法思想在于将原始图像在频域内作多层分解，然后对分解后得到的信息表示灵活的有选择的编码。
小波变换主要是对原有的图像进行离散小波变换（discrete wavelet transform ,DWT）,将原有的图像在时间－频率域上分解。这里给出一个例子[12]:
图 2.6.a
图2.6.b Lena三级分解图像
图2.6.a是图像名字叫“Lena”。“Lena”不仅是图像压缩界，也是整个图像处理领域最常用到的一幅测试图像。该图是1972年10月“花花公子”杂志的中间插页的一部分，是瑞典人Lena Soderberg的特写，被南加利福尼亚大学一位不知名的学者发现后加以剪裁和扫描，用来作为其图像压缩研究的测试图像。从此“Lena”在图像处理研究领域广为使用，成为最重要、知名和常用的测试图像。而Lena本人一直生活在瑞典，直到1988 年她才知道自己的“名声”，1997年5月她还应邀参加了波士顿第50届图像科学与技术协会年会[13]。但为什么会选用这些图像作为检验图像压缩算法的测试图像呢？因为这些测试图像都是很有特点和代表性的。“Lena”图像多为纯连续色调，特别是墙和露出的皮肤区域；图像中帽子是好的连续色调，而头发和帽子上的羽毛却是差的连续色调；墙上的直线和镜子的曲线部分则是离散色调图像的特征。因此用该图作为图像压缩的测试图是很具有代表性的。
图2.6.b表示Lena图像使用三级滤波器组做小波变换输出的子图像(sub- image)，所选用的小波为Daub 9/7。图中的数字1, 2和3表示分解的级数编号，LL3表示第3级的低频子图像，在这个例子中，它是分辨率最低的子图像，HL3表示第3级分解在水平方向上的子图像，LH3表示第3级分解在垂直方向上的子图像，HH3表示第3级分解在对角线方向上的子图像，其他的组合符号依此类推。
2.6 从能量角度看小波变换
图像经过小波变换后，它的能量并不会发生损失，而是会将能量重新分配，这样，各子图像包含的能量差别很大[14]。以某细胞图像为例[15]，对其进行小波分解，其能量分布特征如表3.1所示。表3.1中数据为各子图像能量占整幅图像能量的百分比。
表2.1 某细胞4级分解后各子图像的能量百分
子图像名称 能量特征
98.51
0.36
0.38
0.08
0.16
0.20
0.03
0.09
0.09
0.01
0.03
由表2.1可见,图像分解后的能量主要集中在 子图像,占全部能量的98%以上,其它子图像的能量较少,且层次越低,能量越少.
目前，对于小波变换图像压缩的研究主要集中在两个方面：一是小波基的选
择，一是小波系数的编码。因为小波变换本身并不能压缩图像，只是提供了减少
比特率的一种可能，必须结合其它编码技术对小波系数编码才能实现压缩目的。
所以，基于小波变换的图像压缩方法通常分为3个步骤 :小波变换、量化和编码。此类方法首先对图像进行多级小波分解，然后对每层的小波系数进行量化， 如零树编码进行量化，矢量量化等，再对量化后的系数进行编码，如算术编码、哈夫曼编码等无失真编码。对于基于小波变换的图像压缩编码方法，对小波变换后系数的量化和编码是实现数据压缩的关键，也是本文的研究重点。
第三章 基于小波变换的图像压缩算法的研究
3.1 几种小波图像压缩算法的介绍
3.1.1 几种小波图像压缩算法的介绍
自从小波变换用运到图像处理领域以后，发展相当的快，出现了许多新的技术，例如向嵌入零数小波编码（EZW）技术，它是运用较早的基于离散小波变换的图像压缩技术，在 EZW图像压缩技术的基础上，又出现了SPIHT图像压缩算法和EBCOT图像压缩算法，她们的基础都是EZW算法。下面，分别对它们作一介绍：
EZW算法
在1992年，Lewis，A. S.和Knowles, G.首先介绍了一种树形数据结构来表示小波变换的系数[16]。在1993年，Shapiro, J. M.把这种树形数据结构叫做“零树(zerotree)”，并且开发了一个效率很高的算法用于熵编码，他的这种算法叫做嵌入(式)零树小波(Embedded Zerotree Wavelet，EZW)算法[17]。EZW主要用于与小波变换有关的二维信号的编码，但不局限于二维信号。
SPIHT算法
受 EZW算法和 Amir Said 本人开发的 IEZW(Improved Embedded Zerotree Wavelet)算法的启发，Amir Said 和 William Pearlman 在1996年发表了他们对EZW的改进算法[18]，叫做 SPIHT(set partitioning in hierarchical trees)算法，可考虑译成“层树分集”算法。图像经过小波变换之后，大部分能量都集中在低频子带。SPIHT算法就是从这个事实出发，最先传送幅度大的系数，这样解码器即使在低速率应用环境下也可得到图像的大部分信息。编码树的结构与EZW算法的结构类似，每一个节点要么没有子节点，要么有4个子节点。在编码过程中，使用三个列表变量存储重要系数和不重要系数。
小波图像编码方法的开发与渐进图像(progressive image)如何传输有着密切的关系。传输渐进图像的方法很多，SPIHT算法采用的方法是幅度大的系数先传送，理由是这样的：假设原始图像由一组像素 组成，用 表示 经过小波变换之后产生的系数，其中(i, j) 为像素的坐标，也是小波图像系数的坐标。为简化符号，使用字母p表示二维图像，
用c 表示小波变换之后的系数，因此一幅图像的小波变换可表示成，
(3.1)
W(g) 表示单式(unitary)分层子带变换，经过小波变换之后的二维阵列c 具有与p 相同的维数。每一个元素 可用二进制数的格式表示在渐进图像传送中，解码器开始设置的重构矢量 通常为零，然后按照接收到的编码信息进行修改。在接收到系数的近似值或者精确值之后，解码器可以得到重构的图像 ，
(3.2)
其中， 表示小波变换的逆变换。为使接收端能够尽快看到图像的主要内容，就需要对图像的内容进行选择。选择的原则是解码器重构的图像与原始图像最接近。如果用均方差(MSE)指标来衡量，则失真程度 可表示为，
(3.3)
其中N 为图像的像素数目， 是由系数, 重构的像素值。由于欧几里得范数(Euclidean norm)即向量的长度相对于单式变换 是不变的。该式表明，解码器开始使用的系数近似值 为零时，最大的系数 对减少均方差最重要，因此幅度比较大的系数需要先传送。根据幅度大的系数先传送的原则，就需要对系数进行排序。如何排序就是SPIHT算法想解决的问题。假设传送的系数已经按要求排了序，当系数 用二进制的形式表示时，同样根据幅度大的系数先传送的原则，自然而然地会按照最高有效位最先传送的原则进行传输。在渐进图像传输中，这个方法叫做位平面(bit plane)方法。这个原则也体现在SPIHT算法中。
SPIHT算法的一个特点是不单独传输系数的排序信息。这样做的基本依据是任何排序算法的执行路径都是使用分支点的比较结果进行定义的，如果编码器和解码器使用相同的排序算法，解码器就可重复编码器的执行路径，因此排序信息可从执行路径中重新获得。
EBCOT算法
最佳截断嵌入码块编码 (Embedded Block Coding with Optimized Truncation，EBCOT)是 David Taubman 在1999年发表的一种压缩算法[19]，现正处在进一步开发之中。该方法与早期的EZW，SPIHT以及Taubman和Zakhor开发的LZC(layered zero coding)等算法有着不同程度的联系。
EBCOT算法是一种对小波变换产生的子带系数进行量化和编码的方法。它的基本思想是把每一个子带的小波变换系数分成独立编码的码块(code-block)，并且对所有的码块使用完全相同的压缩算法。
对每一个码块进行编码时，编码器不用其他码块的任何信息，只是用码块自身的信息产生单独的嵌入位流(bitstream)。每一码块的嵌入位流可以被截断成长度不等的位流，生成不同的位速率，这就是EBCOT算法中“截断”的含义。
每一码块的嵌入位流应该截断到什么程度才符合特定的目标位速率、失真限度或者其他衡量图像质量的指标，也就是在给定一个目标位速率的情况下，使重构图像的失真程度最小，David Taubman提出了一种认为是“最佳”的方法来截断每一个独立码块的位流，这就是EBCOT算法中“最佳”的含义。
概括地说，EBCOT算法的主要想法是把嵌入码块编码方法与码块位流的最佳截断方法结合在一起，使重构图像的失真最小，它的主要特性包括分辨率可变(resolution, scalability)、信噪比可变(SNR scalability)和随机访问(random access)。
3.1.2 关于JPEG2000
JPEG2000[20]是由ISO/IEC JTC1 SC29标准化小组负责并正在制定的新的静态图像压缩国际标准。JPEG全名为Joint Photographic Experts Group（联合摄影专家组），它是一个在国际标准组织(ISO)下从事静态图像压缩标准制定的委员会。它制定出了第一套国标静态图像压缩标准：ISO10918-1;就是我们所说的JPEG了。由于JPEG优良的品质，使得它在短短的几年内就获得极大的成功，目前网站上百分之八十的图像都是采用JPEG的压缩标准。然而，随著多媒体应用领域的激增，传统JPEG压缩技术已无法满足人们对多媒体图像资料的要求。因此，更高压缩率以及更多新功能的新一代静态图像压缩技术JPEG2000就诞生了。JPEG2000正式名称为:ISO15444，同样是由JPEG组织负责制定。该标准是由联合摄影专家组于1997年开始征集提案，把它作为JPEG标准的一个更新换代标准。它的目标是进一步改进目前压缩算法的性能，以适应低带宽、高噪声的环境，以及医疗图像、电子图书馆、传真、Internet网上服务和保安等方面的应用。国际标准化组织的WG1小组已于2000年8月制定了最终的国际标准化草案（The Final Draft International Standard，简称FDIS）。JPEG2000与传统JPEG;最大的不同，在于它放弃了JPEG。所采用的以离散余弦变换(Discrete Cosine Transform)为主的区块编码方式，而采用以小波转换(Wavelet Transform)为主的多解析编码方式。离散子波变换算法是现代谱分析工具，在包括压缩在内的图像处理与图像分析领域正得到越来越广泛的应用。此外JPEG2000还将彩色静态画面采用的JPEG编码方式与2值图像采用的JBIG编码方式统一起来，成为对应各种图像的通用编码方式。
3.2 各种小波图像压缩算法的共性
在3.1.1小节中提到了三种基于小波变换的图像压缩技术( EZW算法、SPIHT算法、EBCOT算法)，它们都是基于小波变换的压缩算法，因此之间都存在着某种共性。以下的图3.1.a和图3.1.b中分别说明了小波压缩和解压缩的五个步骤。
图 3.1.a 图像压缩
图 3.1.b 图像解压
从以上两个图中可以看到各种小波算法压缩图像和解压缩图像的流程是一样的。此外，压缩中的五个步骤除了量化都是可逆的。量化的过程是为了降低小波变换后产生的浮点数的精度。
量化和编码阶段是小波变换图像压缩的重要方面，小波变换的目的是为了产生大量零值或者近视于零值的幅度值。各种小波变换的图像处理方法的不同点主要就体现在量化和编码阶段。
3.3 对各种小波压缩算法的比较及本课题所选方案
3.3.1 对各种小波压缩算法的比较
小波图像处理的方法是非常之多的，在前面只是介绍了比较经典的三种算法，这三种算法之间存在着不同的联系，它们之间的区别主要体现在对图像进行完小波变换后的量化和编码阶段。这三个经典的算法中，EZW算法是最为基本的算法，也是首先被提出的，后面介绍的SPIHT算法和EBCOT算法都是以EZW算法为基础的、经过改进的更为优秀的算法，当然，比起EZW算法的实现，后两种算法也将会更加的复杂。
3.3.2 本课题所选方案
本课题中将选用EZW算法作为小波变换图像压缩的方案，原因有二：第一，虽然这种算法提出的较早，也在它的基础上衍生了别的算法，但是它是较基础的算法，对于它的理解和应用会有助于对别的算法的理解；第二，EZW算法相对于SPIHT、EBCOT等许多算法实现起来更为容易，而且在压缩效果上还是比较理想的。因此，本课题选用了EZW算法来实现基于小波变换的图像压缩。
3.4 所选方案的实现
3.4.1 EZW算法概述
嵌入式零树小波中的“嵌入(Embedded)”是渐进编码技术(Progressive Encoding) 的另一种说法,其含义是指一幅图像可以分解成一幅低分辨率图像和分辨率由低到高的表示图像细节的许多子图像,图像合成的过程与分解的过程相反,使用子图像生成许多分辨率不同的图像。
“零树(ZeroTree)”是指小波变换系数之间的一种数据结构,因为离散小波变换是一种多分辨率的分解方法,每一级分解都会产生表示图像比较粗糙的低频图像和比较精细的高频图像的小波系数,在同一方向和相同空间位置上的所有小波系数之间的关系可用一棵树的形式表示,如果树根和它的子孙的小波系数的绝对值小于某个给定的阈值T(Threshold) ,那么这棵树就叫做零树。
“小波(wavelet)”是指该算法以离散小波变换为基础,以大的小波变换系数比小的小波变换系数更重要,以及高频子带中的小系数可以被抛弃的事实为背景。
EZW算法是多分辨率图像的一种编码方法。对整幅图像编码一次，生成一种分辨率图像，编码一次叫做一遍扫描。每一遍扫描大致包含三个步骤：设置阈值、每个小波系数与阈值进行比较、量化系数和重新排序。在扫描过程中需要维护两种表，一种是小波系数的符号表，另一种是量化表[12]。
3.4.2 零树的构造
回顾二维小波变换的计算过程，不难想象各级子图像中的系数是相关的。由于低频子图像的系数要比高频子图像的系数大，零树编码技术就是利用这个事实来设计编码/解码过程中每一级使用的量化器。各级子图像中的系数之间的关系可以用树的形式描述。如图3.2(a)所示，最低频率的子图像在左上角，最高频率的子图像在右下角，由同一方向和相同空间位置上的所有小波系数组成一棵树。例如，从第三级子图像HH3、第二级子图像HH2到第一级子图像HH1的相应位置上的所有系数构成一棵下降树。按箭头所指的方向，各级系数的名称分别用祖系数、父系数、子系数和孙系数来称呼。举例来说，LL3的系数为{63}, HH2和HH1中的系数分别为{3}和{4, 6, 3, -2}, 由这些系数构成的树如图3.2(b)所示。如果把{63}指定为父系数，{3}就称为子系数，而{4, 6, 3, -2}中的4个系数就称为孙系数。
（a）构造方法 （b）小波系数举例
图3.2 EZW编码树的构造
为便于比较，把图3.2(b)所示的两棵树用图3.3(a)和(b)表示。假设编码时开始的阈值 =32，由于63比32大，这样的树叫做非零树，图3.3(a)所示。假设下一次编码时的阈值 =16，把-13当作父系数，它的幅度16小，而它的所有4个子系数的幅度都比16小，这样的树叫做零树，系数-13叫做零树根，如图3.3(b)所示。根据以上的分析，零树的定义可概括为一句话：子孙系数都为零的树。定义零树的重要意义在于，如果一棵树是零树，那么这棵树就可以用一个预先定义的符号来代表整棵树，从而提高了压缩比。
(a) 非零树例子 (b) 零树例子
图3.3 非零树与零树的概念
3.4.3 扫描方法
EZW算法对小波系数的进行编码的次序叫做扫描[12]。扫描子图像系数的方法有两种，一种叫做光栅扫描(raster scan)，如图3.4(a)所示，另一种叫做迂回扫描(morton scan)，如图3.4(b)所示。
(a) 光栅扫描 (b) 迂回扫描
图3.4 小波变换系数扫描方法
3.4.4 EZW算法的实现
EZW算法可粗略地归纳为下面几个主要步骤。
⑴阈值T 的选择
开始时的阈值 通常按下式估算，
＝ (3.4)
其中， 表示最大的系数值， 表示小波变换分解到第i 级时的系数。以后每扫描一次，阈值减少一半。
⑵给系数分配符号
使用EZW算法编码图像时每一次扫描需要执行两种扫描，并产生两种输出的符号。第一种扫描叫做主扫描(dominant pass)，它的任务是把小波系数X 与阈值T 进行比较，然后指定POS（positive significant）、NEG(negative significant)、ZTR(zerotree root)、IZ(isolated zero)中4个系数符号之一，其余的用T,0表示,其中T表示该系数没有子孙系数且它本身为0。对整幅图像扫描之后产生系数符号序列。第二种扫描叫做辅扫描(subordinate pass)，其任务是对主扫描取出的带有符号POS或者NEG的系数进行量化，产生代表对应量化值的量化符号“0”和“1”。
即：
主扫描： 扫描每一个系数以产生系数符号
如果系数幅度大于阈值(T )且为正数，输出符号POS，如果系数幅度小于阈值(T )且为负数，输出符号NEG，如果系数是零树根，输出ZTR，如果系数幅度小于阈值但树中有大于阈值的子孙系数，输出孤立零符号IZ。
辅扫描： 量化带符号POS和NEG的系数
在量化系数之前要构造量化器。量化器的输入间隔为[ ， ) ，该间隔被1.5 分成两个部分：[ ,1.5 ]和[ ,2 ]，量化间隔为0.5 , 其中i 为第i 次编码。量化器的输出为量化符号“0”和“1”，“0”对应量化值为(1.5-0.25) ，“1”对应量化值为(1.5+0.25) 。
3.5 EZW算法举例
为进一步理解EZW算法，举一个例子。假设有一幅8×8的图像P ，离散小波变换矩阵为W ，经过小波变换之后的图像为X＝WP ，小波图像系数X 和扫描方式分别如图3.5(a)和(b)所示。另外还假设，图3.5(a)所示的数据是经过3级分解的小波图像系数。
(a) 小波图像数据 (b) 迂回扫描
图3.5 8×8小波变换图像
3.5.1 树结构
图3.6(a)中的系数用坐标（行号，列号）表示。最低分辨率子图像(即第3级)中的(0,0)系数和其他三个系数在高一级分辨率子图像(即第2级)中有3个子系数与它有关，构成的树如图3.6(b)所示。说明如下：
(0,0) 表示子带LL3的系数，它与第3级子图像中相关的子系数有3个：(0,1),(1,0),(1,1)。
(0,1) 表示子带HL3的系数，它与第2级子图像中相关的子系数有3个：(0,2),(0,3),(1,2),(1,3)。
(1,0)表示子带LH3的系数，它与第2级子图像中相关的子系数有3个：(2,0),(2,1),(3,0),(3,1)。
(1,1) 表示子带HH3的系数，它与第2级子图像中相关的子系数有3个：(2,2),(2,3),(3,2),(3,3)。
(a) 8×8子图像小波变换系数 (b) 最低频带小波变换系数树
图3.6 编码树的结构
在其他子图像中，任何一个系数在高一级分辨率子图像中都有4个子系数与它有关，它们之间构成的树如图3.7(b)所示，图中只表示了两个的树。从图中可以看到，
(0,2)表示子带HL2 的系数，它与第1级子图像中相关的子系数有4个：(0,4),(0,5),(1,4),(1,5)。
(0,3) 表示子带HL2 的系数，它与第1级子图像中相关的子系数有4个：(0,6),(0,7),(1,6),(1,7)。
(1,2)表示子带HL2 的系数，它与第1级子图像中相关的子系数有4个：(2,4),(2,5),(3,4)(3,5)。
(1,3)表示子带HL2 的系数，它与第1级子图像中相关的子系数有4个：(2,6),(2,7),(3,6)(3,7)。
(a) 8×8子图像小波变换系数 (b) 2级子图像小波变换两个系数树
图3.7 编码树的结构
3.5.2 编码
根据对图像分辨率的要求，编码时可对小波图像系数进行多次扫描。每一次扫描包括主扫描和辅扫描 。
第一次扫描：
步骤1: 选择初始阈值。最大的系数为63，因此选择 。
步骤2: 指定系数的符号。设DL为主扫描表，SL为辅扫描表，从(0,0)点开始扫描，扫描的每一个系数与阈值32比较，在此过程中将比较符号放在DL中。当一个系数被指定为符号ZTR时，它的所用子孙系数不在扫描,标记它的子孙系数为x。当一个系数被标识为Z时表示此系数小于阈值且没有子孙系数。如图3.8所示为第一次扫描的结果。
第一次主扫描之后， DL中的系数符号为：
DL={ POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z POS,Z, Z} 。POS,NEG在此次扫描中它为一个重要系数，不在被扫描。
(a) 系数符号和标记 (b)系数量化
图3.8 第一次主扫描
步骤3: 量化系数。对带符号POS/NEG的系数进行量化。在第一次主扫描期间的阈值是32，幅度大于32的有4个系数{63，34，49，47}。用48把间隔[32, 64) 分成两个部分,如图3.8(b)所示。幅度在间隔[32,48) 中的系数指定为符号“0”, 幅度在间隔[48, 64) 中的系数指定为符号“1”，于是这4个系数被编码成如表3.1所示的量化符号。
在第一次辅扫描之后，4个系数{63-POS, 34-NEG, 49-POS, 47-POS}的量化符号所组成的位流为：
S1: 1 0 1
表3.1 第一次辅扫描量化表
系数幅度 量化符号 重构幅度
63 1 56
34 0 40
49 1 56
47 0 40
步骤4:把系数集{63-POS, 34-NEG,49-POS, 47-POS}排列成{63-POS, 49-POS, 34-NEG, 47-POS}。
步骤5： 输出编码信息。编码器输出两类信息，一类给解码器的系数符号系列等信息，另一类用于下一次扫描的阈值和大于阈值的系数值等信息。
① 给解码器的信息包含下面三种：
HEADER (即 ), D1: POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z, POS, Z, Z
S1: 1 0 1 0.
② 给下一次扫描用的信息包含下面三种：
,{63-POS, 49-POS, 34-NEG, 47-POS}和子带图像。
同第一编码一样，可以继续进行第二次扫描以及更多次。这可以根据对图像的压缩率或者数据的传送率等应用要求可决定是否继续编码。
3.5.3 解码过程
EZW的解码过程是EZW编码的逆过程，编码时扫描多少次，解码时也可以解多少次，这要取决于对图像分辨率或者传输环境的要求。解码过程大致分为三个步骤：在接收到编码器发送的信息之后，解码器首先设置阈值，构造逆量化器，然后开始解读位流中包含的位置和小波系数值。
第一次解码
解码器开始时的阈值 ，它接收到来自编码器第一次扫描输出的系数符号是，POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z, POS, Z, Z /1 0 1 0。这个信息相当于量化符号所组成的位流与系数符号之间有如下的对应关系，
D1 POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR, ZTR, IZ, ZTR, ZTR, Z, Z, Z, Z, Z POS, Z, Z
S1 1 0 1 0
解码器要按照编码时的扫描和量化方法进行解码。输入位流的第1个系数符号是POS，对应的量化符号位是“1”，因此第1个系数是56；第2个系数符号是NEG，对应的量化符号位是“0"，因此第2个系数是-40；第3个系数符号是IZ，在相应的图像系数位置上用“0”表示它的系数,第4个系数是ZTR，对应为“0”并且它的所有子孙系数也为“0”。第一次解码的结果如图3.9所示。用“0”表示的系数表示已经扫描过，它们对应符号IZ或者ZTR，用“×”表示的系数表示不需要扫描的系数，因为它们是零树根的子孙。
图3.9 第一次解码
在第一次解码之后，解码器需要判断是否要进一步重构比较精细的图像。如果不需要，则退出解码，如果需要则进入第二次解码甚至更多次。
3.6 关于编码
在以上给出的编码器输出中并没有用到熵编码，在实际的许多软件设计中都会用到熵编码，例如可以用运EZW算法和算术编码来共同完成图像数据的处理。
另外，由于EZW算法先将待编码的比特流按重要性排序，再依据所排顺序从最重要位到最不重要位依次发送。该算法在发送过程中，可根据目标码率或失真度要求随时结束编码；在解码过程中，也能根据要求随时结束解码，并可得到相应码流截断处的目标码率的恢复图像，从而有效地控制计算量，满足网络传输中实时处理的要求。这也是本课题所采用的方法，即用户可以根据自己的需要，自行的设置压缩率和解压率，来随时停止编码和解码过程。
第四章 基于小波变换的图像压缩算法的
软件实现
4.1 软件总体功能设计
本软件主要实现基于小波变换的EZW算法对图像（位图）的压缩和解压缩，也就是将第三章的研究和小波变换技术相结合，用具体的开发工具——VC++[21]进行实现。
图4.1 软件界面
该软件完整的工作过程是：
图像压缩过程：图像读入后显示在软件的界面，然后可以根据需要设定图像小波变换的级数对图像进行变换，变换完之后还可以进行图像的重构。对经小波变换的图像可以进行EZW编码，编码中没有使用熵编码，而是采用直接设定压缩率的方法来得到压缩图像（后缀名为ezw）。
对于压缩后的文件（.ezw文件），可以按照原压缩率将其读入界面并显示，然后用户可以设定解压缩率实现图像的解压，将.ezw文件解压为.bmp文件。
注：本章中的压缩率和解压缩率只是一种笼统的说法，并不遵循严格的公式定义。
4.2 软件各个模块的实现
按照软件应该实现的功能，本软件可以分为一下四个模块，分别为图像的读入模块、图像小波变换模块、EZW算法实现模块、解码模块。各个模块之间的联系如图4.2所示。图4.2所示的过程实际上也就是一次完整的图像处理过程。
图4.2 软件模块设计流程图
各个模块的分别实现：
位图读入显示模块
本软件实现的是BMP文件格式的图像压缩，BMP位图文件可以看成由四个部分组成：位图文件头(bitmap-file header)、位图信息头(bitmap-information header)、彩色表( color table) 和定义位图的字节(BYTE)阵列，可以调用基本类对图像信息进行存取。
实现位图的读入，由于本软件是基于MFC(Microsoft Foundation Class Library)框架的，但MFC中没有处理设备无关位图(DIB)位图的类，可以定义一个处理DIB位图的专用类CDib类，在其中封装必要而有效的DIB数据成员和处理函数[22]。该类具有的功能如下：
Void LoadFIle(CString m_fileName); //装载BMP位图文件
BOOL SaveFile(const char* paszFilename); //存储BMP位图文件
Char* GetFileName(); //返回位图文件名
DWORD GetSize(); //返回位图文件的大小
UINT GetWidth(); //返回位图文件的宽度
UINT GetHeight(); //返回位图文件的高度
UINT GetNumberofCorlors(); //返回位图颜色数目
RGBQUAD* GetRGB();//返回颜色表首地址
BITMAPINFO* GetInfo(); //返回图像信息结构首地址
BYTE *GetData(); //返回图像数据首地址
位图的读取流程图如图4.3所示。
图4.3 位图的读取流程图
图4.4为位图的显示流程图。
图4.4 位图的显示流程图
图像的小波变换模块
对图像进行小波变换，它是小波变换图像压缩的基础，后面的EZW算法就是以此为前提和基础。这个过程中将弹出一个对话框，要求用户输入一个1～6之间的整数，用来指定小波变化的级数。
此模块对图像进行离散小波变换，这里选用的小波是db9/7小波，用db9/7小波的滤波器系数可以构成小波变换矩阵 。当然，由于这个矩阵是非常规则的[23]，所以只需构造出它的一行就行了。对图像进行二维小波变换时采用标准分解方法，即对每一行的像素值先进行变换，产生每一行像素的平均值和细节系数，再对经过变换的图像的所有列进行变换，形成最终小波变换图像。
此过程的流程图4.5所示：
图4.5 图像小波变换模块流程图
编码模块
对经过小波变换的图像进行量化编码。这个模块就是EZW算法的实现过程，这里又会有一个对话框弹出，让用户输入一个0～1之间的小数，来设定压缩率，实际就是何时终止编码。用户输入的数字越小，则压缩率越大。
该模块就是第三章的具体实现，完成对小波变换后的图像编码。它首先判断一个系数的符号情况，是 POS、NEG、ZTR、IZ 和 Z 中的哪一个，然后再对符号为POS和NEG两种符号进行量化编码。此模块的流程图如下：
图4.6 EZW编码模块
解码模块
这个模块按压缩时的压缩率来显示图像，用户可以设定解码率，并在此解码率下解码图像。
此模块为EZW算法的解码过程，主要是对获得的码流进行定位和量化。这个过程中设定的解码率实际就是用来说明什么时候停止解码。
小波重构模块
此模块为一次完整压缩/解压缩的最后一步，是对解码中得到的系数进行小波重构，也就是小波变换的逆过程。
至此，一次完整的图像压缩/解压过程完成。
4.3 软件应用举例
以下，将对该软件的应用做一个小的演示，来看一下它的工作情况。
图4.7 载入24位Lena图
图4.8 Lena图的三级小波变换图
图4.9(a) 压缩前的Lena文件 图4.9(b) 压缩后的ezw文件
图4.10(a) 解压后Lena图 图4.10(b) 解压后bmp文件
说明：图4.7为软件载入24位Lena图，它的大小为720K；
图 4.8 为图4.5的三级小波变换；
图4.9为压缩后生成的ezw文件，编码长度占总码的比重为0.6，大小为403K；
图4.10为解压后的Lena图，解码长度占总码的比重为0.7，大小为719K。
从以上的应用中可以看出，对比压缩前和解压后的图像，本软件的性能还是比较好的。
4.4 软件评价
在图像编码系统中，评估编码系统性能的一种方法是失真度量法，用峰值信号噪声比(peak signal to noise ratio, PSNR)[23]来衡量, 定义为最大像素值(Peak Signal Value, PSV)与均方差(mean square error，MSE)[23]之比，
(5.1)
对8位二进制图像，
(5.2)
其中，
(5.3)
其中，x(m,n)为原始图像的像素值， 为解压缩之后的像素值。
评估编码系统性能还使用其他方法，这些方法包括使用规格化均方差
(normalized mean square error，NMSE)、信号噪声比(signal to noise ratio，SNR) 和平均绝对误差(mean absolute error，MAE)来度量，分别定义为
(5.4)
(5.5)
(5.6)
其中，x(m,n)为原始图像的像素值， 为解压缩之后的像素值。
表5.1 Lena图像七级小波分解EZW压缩算法整体性能
压缩比 CR 峰值信噪比 PSNR(db) 压缩时间 T（s）
16:1 27.54 0.54
8:1 23.23 0.61
4:1 33.17 0.68
2:1 36.28 0.77
1:1 39.55 0.91
4.5 本软件系统的优点和不足
本软件系统实现了EZW算法，能够对图像实现压缩和解压缩功能，用户可以根据自己的需要设定压缩率和解压缩率，压缩效果较好，压缩图像解压缩后主观上没有区别。
虽然本软件实现了图像压缩/解压处理功能，但EZW算法毕竟是一种较为基础的算法，相对于SPIHT算法和EBCOT算法在压缩率等方面就存在着差距，另外，在本课题的实现中并没有采用熵编码，这在某种程度上也会造成系统的性能下降。
4.6 值得改进的地方
本软件实现了EZW算法，但还可以进行一些改进，用于提升性能：
本系统的编码过程中没有进行熵编码，可以进一步用运EZW算法和熵编码(如算术编码)相结合的算法来提供系统的性能；
如果要取得好的压缩率，可以在EZW算法基础上采用改进的编码方法(如SPIHT算法和EBCOT算法)， JPEG 2000 编码规范就是一个很好的改进；
本系统只实现了对位图（.bmp）的处理，没有考虑到其他图像格式，因此，可以对其功能进行改进。
第五章 总结
5.1 所做工作的总结
在本研究中，首先详细的介绍了小波变换的产生背景和小波变换的基本理论知识，重点谈到了连续小波变换和离散小波变换，其中的离散小波变换最为重要，它是图像小波变换的理论基础。接着，介绍了几种常见的小波并将小波变换引入了图像处理中，在这里，为了直观，举出了一个对图像进行小波变换的例子，随后还从能量的角度对图像小波变换进行了说明。所有这些都是基于小波变换处理图像的前提和基础，是每种小波变换算法都要用到的。
随后，对基于小波变换的图像压缩算法进行研究。这里，首先介绍了几种比较经典的基于小波变换的图像压缩算法和JPEG2000这个国际化图像处理标准，并对几种算法进行了简单的分析，阐述了它们之间的共性，并对它们做了比较。接着，确定了本课题中所要采用的基于小波变换的图像压缩算法——EZW算法。随后，重点论述了EZW算法，包括它的由来、算法概述及如何实现，还提及到了与算法相关的内容，如零树的构造、扫描等等。最后，举出了一个EZW算法实现的具体例子，详细阐述了EZW算法的思想和实现。这一部分是全文的重点，也是基于小波变换图像压缩的精髓所在，还是各种基于小波变换处理图像的区别点。
最后，论述了小波变换图像压缩的软件实现。在此，具体阐述了基于小波变换的EZW图像压缩算法的VC++实现。首先，讲到了软件的总体设计思路，要实现的功能，接着对软件各个模块进行了介绍，并说明了实现流程，然后对软件进行了应用举例，说明软件的工作情况。最后，对软件及EZW算法的性能进行了评价，并讨论了软件系统的优点和不足以及值得改进的地方。
从整个工作来看，基本上到达了前期的目标，在对基于小波变换的图像压缩的算法进行研究的基础上实现了软件系统，对软件系统的性能也是比较满意的。但也留下了些遗憾，主要有一些几点：
研究的基于小波变换的图像压缩算法不是最先进的、性能最良好的算法（如EBCOT算法），而是一种较为基础的算法。
在实现了EZW算法之后，并没有实现熵编码，而是直接进行了编码，导致了压缩性能的下降。
5.2展望
由于小波变换在图像处理方面的突出表现，引起了人们的极大关注和兴趣。随之而来，许多新技术也不断出现，这其中，有的是对原有技术的改进，有的是将小波图像处理技术和别的编码技术相结合，以取得最佳效果，有的是原创型的新算法。第三章中所介绍的JPEG2000也是许多技术的结合产物，它就综合应用了图像分块技术、小波变换技术、EBCOT压缩技术。在功能上，它的压缩比要比原来的JPEG技术提高20％以上，还实现了渐进传输(progressive transmission)，这是JPEG2000的一个重要特性，它可先传输低分辨率的图像或者是图像的轮廓，然后逐步传输其他数据，不断提高图像质量，以满足用户的需要。这个特性在多媒体网络应用中有重要的意义。例如，当下载一幅图像时，可比较快地看到这幅图像的概貌，根据对图像质量的要求和可用的网络带宽控制下载图像的数据量。支持兴趣区(region of interest, ROI)的编码是其另一个重要功能。用户利用这个特性可指定感兴趣的图像区域，在压缩时对这些图像区指定特定的压缩质量，或在恢复时指定特定的解压缩要求，这给用户带来了极大的方便。例如，在有些情况下图像中只有一小块区域对用户是有用的，对这些区域采用低压缩比，而其他区域采用高压缩比，在保证不丢失重要信息的同时能有效地压缩数据量。
创新无界，可以相信，随着人们研究的不断深入，小波变换技术在图像处理方面将不断会有新的成果产生。
参考文献
[1] 鲁宏伟.多媒体计算机原理与应用[M]. 北京：清华大学出版社，1998.
90～93.
[2] Han Y. A version of Calderon-Zygmund decomposition and its applications[C]. Sci Sinica, 1985, 28:134～146
[3]李建平 主编. 小波分析与信号处理——理论、应用及软件实现[M]. 重庆：重庆出版社，1997.12.
[4] 张贤达. 现代信号处理[M].北京：清华大学出版社. 2001. 485～573.
[5] Wim Sweldens. The Lifting Scheme：A New Philosophy in Biorthogonal Wavelet Constructions [J]. In Proc. Of SPIE，San Diego，CA，USA. Vol.2569. Sept.1995：68～79.
[6] Wim Sweldens. The Lifting Scheme：A Construction of Second Generation Wavelets [J]. SIAM J.Math. Appl. to appear 1997.
[7] 张贤达. 小波与离散变换理论及工程实践[M].北京：清华大学出版社. 2005.
[8]胡昌华，张军波，夏军，张伟．基于MATLAB的系统分析与设计——小波分析[M]．西安：西安电子科技大学出版社，2000.
[9]Mallat, S. G.，A Theory for Multiresolution Signal Decomposition: The Wavelet
Representation [J], IEEE Trans. PAMI, vol. 11, no. 7, July 1989：674～693.
[10]董长虹，高志，余啸海．Matlab小波分析工具箱原理与应用[M]．北京:国防工业出版社，2004.
[11] 谭建豪，章兢，蔡立军，张新国. 现代信息处理及其应用[M].北京：清华大学出版社，2006.70～80.
[12]林福宗，多媒体技术基础(第二版)[M].北京：清华大学出版社，2002.
169～194.
[13]David Salomon 著. 吴乐南 等译. 数据压缩原理与应用(第二版)[M].
北京： 电子工业出版社，2003.
[14]李萍，许录平．整数小波图像变换及统计分析[J]．计算机工程与应用，2004，40(11) ：90～92．
[15]黄雪菊，王秀梅，郝常明．基于小波变换的图像分级压缩算法[J] ．重庆邮电学院学报（自然科学版），Vol.18，No.4，Aug.2006：1～3.
[16]Lewis, A. S. and Knowles, G. Image Compression Using the 2-D Wavelet Transform [J], IEEE Trans. IP, vol. 1, no. 2, April 1992：244～250.
[17]Shapiro, J. M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients [J], IEEE Trans. SP, vol. 41, no. 12, Dec. 1993：3445～3462.
[18] A. Said and W. Pearlman, A new, fast and efficient image codec based on set partitioning in hierarchical trees [J], IEEE Trans. Circuits System, Video Technology, vol. 6，June 1996：243–250.
[19]David Taubman, High performance scalable image compression with EBCOT [J], Image Processing, IEEE Transactions on , Volume: 9 Issue: 7 , July 2000: 1158 ～1170.
[20] 张晓娣 等.新一代的静止图像压缩标准JPEG2000 [J]. 电信科学，2001(5).
[21] 靳济芳. Visual C++小波变换技术与工程实践[M]. 北京：人民邮电出版社，2004.
[22] 杨淑莹. VC++图像处理程序设计（第二版）[M].北京：清华大学出版社，北京交通大学出版社，2005.4～16.
[23] 吴乐南.数据压缩（第二版）[M].北京：电子工业出版社，2005.
150，19～22.
附录
主要程序：
