林福宗 清华大学 计算机科学与技术系 linfz@mail.tsinghua.edu.cn 2008年9月 多媒体技术教程 第7章 小波与小波变换 林福宗 清华大学 计算机科学与技术系 linfz@mail.tsinghua.edu.cn 2008年9月
第7章 小波与小波变换目录 7.1 小波介绍 7.2 哈尔函数 7.3 哈尔小波变换 7.4 规范化算法 7.5 二维哈尔小波变换 7.1.1 小波简史 7.1.2 小波概念 7.1.3 小波分析 7.1.4 小波定义 7.2 哈尔函数 7.2.1 哈尔基函数 7.2.2 哈尔小波函数 7.2.3 函数的规范化 7.2.4 哈尔基的结构 7.3 哈尔小波变换 7.4 规范化算法 7.5 二维哈尔小波变换 7.5.1 二维小波变换举例 7.5.2 二维小波变换方法 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍 小波(wavelet)是什么 在有限时间范围内变化且其平均值为零的数学函数 具有有限的持续时间和突变的频率和振幅 在有限的时间范围内，它的平均值等于零 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续1) 部分小波 许多数缩放函数和小波函数以开发者的名字命名，例如， 图7-1 正弦波与小波——部分小波 Moret小波函数是Grossmann和Morlet在1984年开发的 db6缩放函数和db6小波函数是Daubechies开发的 图7-1 正弦波与小波——部分小波 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续2) 小波简史 小波变换 (wavelet transform)是什么 1807: Joseph Fourier 老课题：函数的表示方法 新方法：Fourier－Haar－wavelet transform 1807: Joseph Fourier 傅立叶理论指出，一个信号可表示成一系列正弦和余弦函数之和，叫做傅立叶展开式 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续3) 只有频率分辨率而没有时间分辨率 可确定信号中包含哪些频率的信号，但不能确定具有这些频率的信号出现在什么时候 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续4) 1909: Alfred Haar Alfred Haar对在函数空间中寻找一个与傅立叶类似的基非常感兴趣。1909年他发现并使用了小波，后来被命名为哈尔小波(Haar wavelets) 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续5) 1945: Gabor 开发了STFT (short time Fourier transform) 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续6) 1980：Morlet 1986：Y.Meyer 20世纪70年代，在法国石油公司工作的年轻地球物理学家Jean Morlet提出小波变换 (wavelet transform，WT)的概念。 20世纪80年代, 开发了连续小波变换 (continuous wavelet transform， CWT) 1986：Y.Meyer 法国科学家Y.Meyer与其同事创造性地构造出具有一定衰减性的光滑函数，用于分析函数 用缩放(dilations)与平移(translations)均为2 j(j≥0的整数)的倍数构造了L2(R)空间的规范正交基，使小波分析得到发展 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续7) 1988：Mallat算法 法国科学家Stephane Mallat提出多分辨率概念，从空间上形象说明小波的多分辨率的特性，并提出了正交小波的构造方法和快速算法，称为Mallat算法[1] 该算法统一了在此之前构造正交小波基的所有方法，其地位相当于快速傅立叶变换在经典傅立叶分析中的地位 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍(续8) 小波理论与工程应用 Inrid Daubechies于1988年最先揭示了小波变换和滤波器组(filter banks)之间的内在关系[2]，使离散小波分析变成为现实 Ronald Coifman和Victor Wickerhauser等著名科学家在把小波理论引入到工程应用方面做出了极其重要贡献 在信号处理中，自从Stephane Mallat和Inrid Daubechies发现滤波器组与小波基函数有密切关系之后，小波分析在信号(如声音和图像)处理中得到极其广泛的应用 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析 小波分析/小波变换 变换目的是获得时间和频率域之间的相互关系 小波变换 小波分析中常用的三个基本概念 对一个函数在空间和时间上进行局部化的一种数学变换 通过平移母小波(mother wavelet)获得信号的时间信息 通过缩放母小波的宽度(或称尺度)获得信号的频率特性 对母小波的平移和缩放操作是为计算小波的系数，这些系数代表局部信号和小波之间的相互关系 对比傅立叶变换 提供了频率域的信息，但丢失了时间域的局部化信息 小波分析中常用的三个基本概念 连续小波变换 离散小波变换 小波重构 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续1) 连续小波变换(continuous wavelet transform，CWT) 傅立叶分析 小波分析 用一系列不同频率的正弦波表示一个信号 一系列不同频率的正弦波是傅立叶变换的基函数 小波分析 用母小波通过移位和缩放后得到的一系列小波表示一个信号 一系列小波可用作表示一些函数的基函数 凡能用傅立叶分析的函数都可用小波分析 小波变换可理解为用经过缩放和平移的一系列函数代替傅立叶变换用的正弦波 用不规则的小波分析变化激烈的信号比用平滑的正弦波更有效，或者说对信号的基本特性描述得更好 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续2) CWT的变换过程示例，见图7-3，可分如下5步 小波ψ (t)和原始信号f(t)的开始部分进行比较 计算系数C——该部分信号与小波的近似程度；C值越高表示信号与小波相似程度越高 小波右移k得到的小波函数为ψ (t-k) ，然后重复步骤1和2，……直到信号结束 扩展小波，如扩展一倍，得到的小波函数为ψ (t/2) 重复步骤1~4 图7-3 连续小波变换的过程 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续3) 离散小波变换(discrete wavelet transform，DWT) 连续小波变换用下式表示 该式含义：小波变换是信号f(t)与被缩放和平移的小波函数Ψ之积在信号存在的整个期间里求和 CWT变换的结果是许多小波系数C ，这些系数是缩放因子(scale)和位置(position)的函数 离散小波变换(discrete wavelet transform，DWT) 用小波的基函数(basis functions)表示一个函数的方法 小波的基函数序列或称子小波(baby wavelets)函数是由单个小波或称为母小波函数通过缩放和平移得到的 缩放因子和平移参数都选择2j (j >0的整数)的倍数，这种变换称为双尺度小波变换(dyadic wavelet transform) 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续4) DWT得到的小波系数、缩放因子和时间关系，见图7-5 图(a)是20世纪40年代使用Gabor开发的短时傅立叶变换(short time Fourier transform，STFT)得到的 图(b)是20世纪80年代使用Morlet开发的小波变换得到的 图7-5 离散小波变换分析图 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续5) 执行DWT的有效方法 用Mallat在1988年开发的滤波器，称为Mallat算法[1] DWT的概念见图7-6。S表示原始的输入信号；通过两个互补的滤波器产生A和D两个信号 A表示信号的近似值(approximations)，大的缩放因子产生的系数，表示信号的低频分量 D表示信号的细节值(detail)，小的缩放因子产生的系数，表示信号的高频分量 图7-6 双通道滤波过程 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续6) 小波分解树与小波包分解树 由低通滤波器和高通滤波器组成的树 原始信号通过一对滤波器进行的分解叫做一级分解。信号的分解过程可以迭代，即可进行多级分解。 小波分解树(wavelet decomposition tree) 用下述方法分解形成的树：对信号的高频分量不再继续分解，而对低频分量连续进行分解，得到许多分辨率较低的低频分量，见图7-7 小波包分解树(wavelet packet decomposition tree) 用下述方法分解形成的树：不仅对信号的低频分量连续进行分解，而且对高频分量也进行连续分解，这样不仅可得到许多分辨率较低的低频分量，而且也可得到许多分辨率较低的高频分量，见图7-8 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续7) 图7-7 小波分解树 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续8) 图7-8 三级小波包分解树 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续9) 注意：在使用滤波器对真实的数字信号进行变换时，得到的数据将是原始数据的两倍 例如，如果原始信号的数据样本为1000个，通过滤波之后每一个通道的数据均为1000个，总共为2000个。于是,根据尼奎斯特(Nyquist)采样定理就提出了采用降采样(downsampling)的方法，即在每个通道中每两个样本数据中取一个，得到的离散小波变换的系数(coefficient)分别用cD和cA表示，见图7-9 图7-9 降采样过程 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续10) 小波重构 重构概念 两个过程 把分解的系数还原成原始信号的过程叫做小波重构(wavelet reconstruction)或合成(synthesis)，数学上叫做逆离散小波变换(inverse discrete wavelet transform，IDWT) 两个过程 在使用滤波器做小波变换时包含滤波和降采样(downsampling)两个过程，在小波重构时也包含升采样(upsampling)和滤波两个过程，见图7-10 升采样是在两个样本数据之间插入“0”，目的是把信号的分量加长，其过程见图7-11 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续11) 图7-10 小波重构方法 图7-11 升采样的方法 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续12) 重构滤波器 滤波器关系到能否重构出满意的原始信号。在信号的分解期间，降采样会引进畸变，这种畸变叫做混叠(aliasing)。这就需要在分解和重构阶段精心选择关系紧密但不一定一致的滤波器才有可能取消这种混叠 低通分解滤波器(L)和高通分解滤波器(H)以及重构滤波器(L'和H')构成一个系统，这个系统叫做正交镜像滤波器(quadrature mirror filters，QMF)系统，如图7-12所示 图7-12 正交镜像滤波器系统 2019年1月1日 第7章 小波与小波变换
7.1 小波介绍——小波分析(续13) 小波变换演示 网址：http://galaxy.uci.agh.edu.pl/~maziarz/Wavelets/ 要安装下面的插件 Macromedia Shockwave plug-in 该演示有声音解说 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数 7.2.1 哈尔基函数 基函数是一组线性无关的函数，可以用来构造任意给定的信号，如用基函数的加权和表示 哈尔基函数(Haar basis function) 定义在半开区间[0，1)上的一组分段常值函数(piecewise-constant function)集 生成矢量空间V0的常值函数 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续1) 生成矢量空间V1的常值函数 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续2) 生成矢量空间V2的常值函数 可按照以上方法继续定义哈尔基函数和由它生成的矢量空间Vj，…… 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续3) 为了表示矢量空间中的矢量，每一个矢量空间都需要定义一个基(basis)，哈尔基定义为 为生成矢量空间而定义的基函数也叫做尺度函数(scaling function)。哈尔基尺度函数定义为 其中，j为尺度因子，使函数图形缩小或放大 i为平移参数，使函数沿x轴方向平移 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续4) 7.2.2 哈尔小波(函数) 最古老和最简单的小波，定义为 生成矢量空间W0的哈尔小波 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续5) 生成矢量空间W1的哈尔小波 2019年1月1日 第7章 小波与小波变换
7.2 哈尔函数(续6) 生成矢量空间W2的哈尔小波 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换 求有限信号的均值和差值 [例7. 1] 假设有一幅分辨率只有4个像素P0、P1、P2、P3的一维图像，对应的像素值或称图像位置的系数分别为 [9 7 3 5] 计算该图像的哈尔小波变换系数 步骤1：求均值(averaging)。计算相邻像素对的平均值，得到一幅分辨率比较低的新图像，它的像素数目变成了2个，即新的图像的分辨率是原来的1/2，相应的像素值为 [8 4] 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换(续1) 步骤2：求差值(differencing)。为能从2个像素组成的图像重构由4个像素组成的原始图像，就需要存储一些图像的细节系数(detail coefficient) 方法是把像素对的第一个像素值减去这个像素对的平均值，或者使用这个像素对的差值除以2 原始图像用两个均值和两个细节系数表示为 [8 4 1 -1] 步骤3：重复步骤1和2，把由第一步分解得到的图像进一步分解成分辨率更低的图像和细节系数。其结果，整幅图像表示为 [6 2 1 -1] 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换(续2) 表7-1 哈尔变换过程 分辨率 平均值 细节系数 4 [9 7 3 5] 2 [8 4] [1 -1] 1 [9 7 3 5] 2 [8 4] [1 -1] 1 [6] [2] 把由4个像素组成的一幅图像用一个平均像素值和三个细节系数表示，这个过程称为哈尔小波变换(Haar wavelet transform)，也称哈尔小波分解(Haar wavelet decomposition)。这个概念可以推广到使用其他小波基的变换 特点：(1) 变换过程中没有丢失信息，因为能够从所记录的数据中重构出原始图像。(2) 对这个给定的变换，可从所记录的数据中重构出各种分辨率的图像。(3) 通过变换之后产生的细节系数的幅度值比较小，为图像压缩提供了一种途径，如去掉微不足道的系数 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换(续3) 哈尔小波变换 在例7.1中的求均值和差值的过程实际上就是一维小波变换的过程，现在用数学方法重新描述哈尔小波变换 I(x)图像用V2中的哈尔基表示 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换(续4) I(x)图像用V1和W1中的函数表示 生成V1矢量空间的基函数为 和 ，生成矢量空间W1的小波函数为 和 ，I(x)可表示为 2019年1月1日 第7章 小波与小波变换
7.3 哈尔小波变换(续5) I(x)图像用V0、W0和 W1中的函数表示 生成矢量空间V0的基函数为 ，生成矢量空间W0的小波函数为 ，生成矢量空间W1的小波函数为 和 ， I(x)可表示为 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换 用小波对图像进行变换的两种方法 标准分解(standard decomposition) 首先使用一维小波对图像每一行的像素值进行变换，产生每一行像素的平均值和细节系数，然后使用一维小波对这个经过行变换的图像的列进行变换，产生这个图像的平均值和细节系数 分解的过程如下： 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换(续1) 图7-28 图像的标准分解方法 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换(续2) 非标准分解(nonstandard decomposition) 用一维小波交替地对每一行和每一列像素值进行变换。 对每一行计算像素对的均值和差值，然后对每一列计算像素对的均值和差值 对包含均值的1/4像素计算行和列的均值和差值，依此类推 过程如下： 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换(续3) 图7-29 图像的非标准分解方法 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换(续4) 图7-26 使用小波分解产生多种分辨率图像 (a) 原始图像 (b) 1/4分辨率图像 (d) 1/64分辨率图像 (c) 1/16分辨率图像 图7-26 使用小波分解产生多种分辨率图像 2019年1月1日 第7章 小波与小波变换
7.5 二维哈尔小波变换(续5) 灰度图 (c) 1/16分辨率图像 (d) 1/64分辨率图像 2019年1月1日 第7章 小波与小波变换
第7章 小波与小波变换 参考文献和站点 Mallat, S. G.，A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Trans. PAMI, vol. 11, no. 7, July 1989, pp. 674-693 Daubechies, I. Orthonormal Bases of Compactly Supported Wavelets, Comm. Pure and Applied Math., vol. 41, Nov. 1988, pp. 909-996 http://www.mathworks.com/access/helpdesk/help/toolbox/wavelet/wavelet_tocframe.shtml Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin, Wavelets for Computer Graphics: A Primer. IEEE Computer Graphics and Applications, 15(3): 76-84, May 1995 (part 1), and 15(4): 75-85, July 1995 (part 2) Peggy Morton and Arne Petersen, Image Compression Using the Haar Wavelet Transform，Math 45，College of the Redwoods, Dev.19，1997 http://amath.colorado.edu/courses/4720/2000Spr/Labs/openingpage.html Sarkar, T.K., Su, C., Adve, R., Salazar-Palma, M., Garcia-Castillo, L., and BOIX, R.R., A Tutorial on Wavelets from an Electrical Engineering Perspective, IEEE Antennas & Propagation Magazine, Vol. 40, No. 5, pp. 49-70, Oct. 1998.(Part 1: Discrete Wavelet Techniques), and Vol. 40, No. 6, pp. 36-48, Dec. 1998. (Part 2: The Continuous Case) W.Maziarz & K.Mikolajczyk, A Course on Wavelets for beginners, http://galaxy.uci.agh.edu.pl/~maziarz/Wavelets/ 2019年1月1日 第7章 小波与小波变换
END 第7章 小波与小波变换