小波变换ppt课件[古柏书屋]

1、2002秋季学期网上课程 多媒体技术基础与应用 (Multimedia Fundamentals and Applications) (Face to Face 2 of 4) 林 福 宗 清华大学 计算机科学与技术系 智能技术与系统国家重点实验室 L 2002年10月9日 1向阳书苑 小波变换与应用小波变换与应用 n一、小波变换 u1.小波 u2.小波变换 u3. 离散小波变换 n二、Haar小波变换 u1.哈尔函数 u2.求均值和差值 u3. 哈尔变换的特性 u4.一维哈尔小波变换 u5. 二维哈尔小波变换 n三、阅读和练习作业 2向阳书苑 一、一、Wavelet Transform 小波

2、分析是近十几年才发展起来并迅速应用到 图像处理和语音分析等众多领域的一种数学工 具。它是继110多年前的傅立叶(Joseph Fourier) 分析之后的一个重大突破，无论是对古老的自 然学科还是对新兴的高新技术应用学科都产生 了强烈冲击。 小波理论是应用数学的一个新领 域。要深入理解小波理论需要用到比较多的数 学知识。本教学提纲企图从工程应用角度出发， 用比较直观的方法来介绍小波变换和它的应用， 为读者深入研究小波理论和应用提供一些背景 材料 3向阳书苑 1. What is wavelet n一种函数 u具有有限的持续时间、突变的频率和振幅 u波形可以是不规则的，也可以是不对称的 u在整个

3、时间范围里的幅度平均值为零 u比较正弦波 4向阳书苑 n部分小波波形 5向阳书苑 小波的定义小波的定义 n Wavelets are a class of a functions used to localize a given function in both space and scaling. A family of wavelets can be constructed from a function , sometimes known as a mother wavelet, which is confined in a finite interval. Daughter wavel

4、ets are then formed by translation (b) and contraction (a). Wavelets are especially useful for compressing image data, since a wavelet transform has properties which are in some ways superior to a conventional Fourier transform. ( ) x ( , ) ( ) a b x 6向阳书苑 nAn individual wavelet can be defined by an

5、d Calderns formula gives Then A common type of wavelet is defined using Haar functions. 7向阳书苑 2. Wavelet Transform n老课题 函数的表示方法 n新方法 Fourier Haar wavelet transform 8向阳书苑 (1) 1807: Joseph Fourier n傅立叶理论指出，一个信号可表示成一系列正 弦和余弦函数之和，叫做傅立叶展开式。 n用傅立叶表示一个信号时，只有频率分辨率而 没有时间分辨率，这就意味我们可以确定信号 中包含的所有频率，但不能确定具有这些频率

6、的信号出现在什么时候。 n为了继承傅立叶分析的优点，同时又克服它的 缺点，人们一直在寻找新的方法。 9向阳书苑 傅立叶变换的定义：A mathematical description of the relationship between functions of time and corresponding functions of frequency; a map for converting from one domain to the other. For example, if we have a signal that is a function of time-an impuls

7、e response- then the Fourier Transform will convert that time domain data into frequency data, for example, a frequency response. (http:/ 10向阳书苑 (2) 1910: Alfred Haar发现发现Haar小波小波 n哈尔(Alfred Haar)对在函数空间中寻找一个与 傅立叶类似的基非常感兴趣。 n1909年他发现了小波，1910年被命名为Haar wavelets n他最早发现和使用了小波。 11向阳书苑 (3) 1945: Gabor提出提出ST

8、FT n20世纪40年代Gabor开发了STFT (short time Fourier transform) nSTFT的时间-频率关系图 12向阳书苑 (4) 1980: Morlet提出了提出了CWT nCWT (continuous wavelet transform) n20世纪70年代，当时在法国石油公司工 作的年轻的地球物理学家Jean Morlet提出 了小波变换WT(wavelet transform)的概念。 n 20世纪80年代,从STFT开发了CWT： 13向阳书苑 nDefinition - Basis Functions: a set of linearly ind

9、ependent functions that can be used (e.g., as a weighted sum) to construct any given signal. nwhere: ua = scale variable 缩放因子 uk = time shift 时间平移 uh* = wavelet function 小波函数 u用y = scaled (dilated) and shifted (translated) Mother wavelet function, n在CWT中，scale和position是连续变化的 14向阳书苑 缩放缩放(scaled)的概念的概

10、念 n例1：正弦波的算法 15向阳书苑 缩放缩放(scaled)的概念的概念(续续) n例2：小波的缩放 16向阳书苑 平移平移(translation)的概念的概念 17向阳书苑 (5) CWT的变换过程的变换过程 可分成如下可分成如下5个步骤个步骤 n步骤步骤1: 把小波把小波 和原始信号和原始信号 的开始部分进行比较的开始部分进行比较 n步骤步骤2: 计算系数计算系数c 。该系数表示该部分信号与小波的。该系数表示该部分信号与小波的 近似程度。系数近似程度。系数 c 的值越高表示信号与小波越相似，的值越高表示信号与小波越相似， 因此系数因此系数c 可以反映这种波形的相关程度可以反映这种波形

11、的相关程度 n步骤步骤3: 把小波向右移，距离为把小波向右移，距离为 ，得到的小波函数为，得到的小波函数为 ， 然后重复步骤然后重复步骤1和和2。再把小波向右移，得到小波。再把小波向右移，得到小波 ，重，重 复步骤复步骤1和和2。按上述步骤一直进行下去，直到信号。按上述步骤一直进行下去，直到信号 结结 束束 n步骤步骤4: 扩展小波扩展小波 ，例如扩展一倍，得到的小波函数为，例如扩展一倍，得到的小波函数为 n步骤步骤5: 重复步骤重复步骤14 18向阳书苑 (a) 二维图 19向阳书苑 (b) 三维图 连续小波变换分析图 20向阳书苑 (6) 三种变换的比较三种变换的比较 21向阳书苑 (7)

12、 1984: subband coding (Burt and Adelson) nSBC (subband coding)的基本概念： 把信号的频率分成几个子带，然后对每个子带 分别进行编码，并根据每个子带的重要性分配 不同的位数来表示数据 n20世纪70年代，子带编码开始用在语音编码上 n20世纪80年代中期开始在图像编码中使用 n1986年Woods, J. W.等人曾经使用一维正交镜 像滤波器组(quadrature mirror filterbanks，QMF) 把信号的频带分解成4个相等的子带 22向阳书苑 图(a) 正交镜像滤波器(QMF) 23向阳书苑 图中的符号 表示频带降低

13、1/2，HH表示频率最 高的子带，LL表示频率最低的子带。这个过程 可以重复，直到符合应用要求为止。这样的滤 波器组称为分解滤波器树(decomposition filter trees) 图(b) 表示其相应的频谱 24向阳书苑 (8) 20世纪世纪80年代年代 Mallat, Meyer等人提出multiresolution theory n法国科学家Y.Meyer创造性地构造出具有一定衰减性 的光滑函数，他用缩放(dilations)与平移(translations) 均为 2的j次幂的倍数构造了平方可积的实空间L2(R) 的规范正交基，使小波得到真正的发展 n小波变换的主要算法由法国的

14、科学家Stephane Mallat 提出 uS.Mallat于1988年在构造正交小波基时提出了多分 辨率分析(multiresolution analysis)的概念, 从空间上 形象地说明了小波的多分辨率的特性 u提出了正交小波的构造方法和快速算法，叫做 Mallat算法。该算法统一了在此之前构造正交小波 基的所有方法，它的地位相当于快速傅立叶变换 在经典傅立叶分析中的地位。 25向阳书苑 n小波分解得到的图像 26向阳书苑 (9)著名科学家著名科学家 Inrid Daubechies，Ronald Coifman和 Victor Wickerhauser等著名科学家 n把这个小波理论引

15、入到工程应用方面做出了极 其重要的贡献 nInrid Daubechies于1988年最先揭示了小波变换 和滤波器组(filter banks)之间的内在关系，使离 散小波分析变成为现实 n在信号处理中，自从S.Mallat和Inrid Daubechies 发现滤波器组与小波基函数有密切关系之后， 小波在信号(如声音信号，图像信号等)处理中 得到极其广泛的应用。 n 27向阳书苑 经过十几年的努力，这门学科的理论基 础已经基本建立，并成为应用数学的一 个新领域。这门新兴学科的出现引起了 许多数学家和工程技术人员的极大关注， 是国际科技界和众多学术团体高度关注 的前沿领域。 小波变换小波变换

16、28向阳书苑 3. 离散小波变换离散小波变换 n在计算连续小波变换时，实际上也是用 离散的数据进行计算的，只是所用的缩 放因子和平移参数比较小而已。不难想 象，连续小波变换的计算量是惊人的。 n为了解决计算量的问题，缩放因子和平 移参数都选择 ( j.0的整数)的倍数。使用 这样的缩放因子和平移参数的小波变换 叫做双尺度小波变换(dyadic wavelet transform)，它是离散小波变换(discrete wavelet transform，DWT)的一种形式。 29向阳书苑 n使用离散小波分析得到的小波系数、缩 放因子和时间关系如图所示。 u图(a)是20世纪40年代使用Gabor

17、开发的 短时傅立叶变换(short time Fourier transform，STFT)得到的时间-频率关 系图 u图(b)是20世纪80年代使用Morlet开发 的小波变换得到的时间-缩放因子(反映 频率)关系图。 3. 离散小波变换离散小波变换(续续) 30向阳书苑 离散小波变换分析图 31向阳书苑 DWT变换方法变换方法 n执行离散小波变换的有效方法是使用滤波器 u该方法是Mallat在1988年开发的，叫做Mallat算法 u这种方法实际上是一种信号的分解方法，在数字信 号处理中称为双通道子带编码 n用滤波器执行离散小波变换的概念如图所示 uS表示原始的输入信号，通过两个互补的滤波

18、器产 生A和D两个信号 uA表示信号的近似值(approximations) uD表示信号的细节值(detail) 32向阳书苑 在许多应用中，信号的低频部分是最重要的，而高频 部分起一个“添加剂”的作用。犹如声音那样，把高 频分量去掉之后，听起来声音确实是变了，但还能够 听清楚说的是什么内容。相反，如果把低频部分去掉， 听起来就莫名其妙。在小波分析中，近似值是大的缩 放因子产生的系数，表示信号的低频分量。而细节值 是小的缩放因子产生的系数，表示信号的高频分量。 双通道滤波过程 33向阳书苑 n离散小波变换可以被表示成由低通滤波器和高 通滤波器组成的一棵树 u原始信号通过这样的一对滤波器进行的

19、分解叫做一 级分解 u信号的分解过程可以叠代，也就是说可进行多级分 解。 u如果对信号的高频分量不再分解，而对低频分量连 续进行分解，就得到许多分辨率较低的低频分量， 形成如图所示的一棵比较大的树。这种树叫做小波 分解树(wavelet decomposition tree) u分解级数的多少取决于要被分析的数据和用户的需 要 小波分解树小波分解树 34向阳书苑 (a)信号分解 (b)系数结构 (c)小波分解树 小波分解树 35向阳书苑 小波包分解树小波包分解树 n小波分解树表示只对信号的低频分量进 行连续分解。如果不仅对信号的低频分 量连续进行分解，而且对高频分量也进 行连续分解，这样不仅可

20、得到许多分辨 率较低的低频分量，而且也可得到许多 分辨率较低的高频分量。这样分解得到 的树叫做小波包分解树(wavelet packet decomposition tree)，这种树是一个完整 的二进制树。 36向阳书苑 三级小波包分解树 n图表示的是一棵三级小波包分解树。小波包分 解方法是小波分解的一般化，可为信号分析提 供更丰富和更详细的信息。例如，小波包分解 树允许信号S表示为 1 3 3 2SAAADDADDD 37向阳书苑 降采样过程降采样过程 n在使用滤波器对真实的数字信号进行变换时，得 到的数据将是原始数据的两倍。例如，如果原始 信号的数据样本为1000个，通过滤波之后每一个

21、通道的数据均为1000个，总共为2000个。 n根据尼奎斯特(Nyquist)采样定理就提出了降采样 (downsampling)的方法，即在每个通道中每两个 样本数据取一个，得到的离散小波变换的系数 (coefficient)分别用cD和cA表示 38向阳书苑 降采样过程 n如图所示。图中的符号 表示降采样。 39向阳书苑 小波变换的定义小波变换的定义 nA transform which localizes a function both in space and scaling and has some desirable properties compared to the Fouri

22、er transform. The transform is based on a wavelet matrix, which can be computed more quickly than the analogous Fourier matrix. nAn alternative to the discrete cosine transform (DCT), the wavelet transform changes data, such as video data, into the sum of varying frequency wavelets. Wavelets are som

23、etimes used instead of the DCT because they are more versatile and dont slow down as much with larger images as the DCT does. Intels Indeo technology makes use of wavelets. http:/ 40向阳书苑 nHaar Transform A one-dimensional transform which makes use of the Haar functions. H- Transform, Haar Function Re

24、ferences Haar, A. 1999-2003 Wolfram Research, Inc. header. nH-Transform A two-dimensional generalization of the Haar transform which is used for the compression of astronomical images. The algorithm consists of dividing the image into blocks of pixels, calling the pixels in the block , , , and . For

25、 each block, compute the four coefficients Construct. 二、二、Haar小波变换小波变换 41向阳书苑 1.哈尔函数哈尔函数 n哈尔基函数 基函数是生成矢量空间V j 而定义的一组线性 无关的函数，可以用来构造任意给定的信号。 也称尺度函数(scaling function)，用符号V j 表示。 n哈尔小波函数 哈尔小波函数是生成矢量 的一组线性无关的函 数 ，用符号W j表示。矢量空间W j中的小波可 用来表示一个函数在矢量空间 中不能表示的部 分。 n见多媒体技术基础第2版，8.2 j V 42向阳书苑 2. 哈尔变换原理哈尔变换原理

26、n假设两个信号的数值分别为a和b，计算 它们的和与差， n从s和d重新获得a和b， 43向阳书苑 哈尔变换举例哈尔变换举例 【例】假设有一幅分辨率只有4个像素 的一维图 像，对应的像素值或者叫做图像位置的系数分 别为： 9 7 3 5 计算它的哈尔小波变换系数 n步骤1：求均值(averaging)。计算相邻像素对 的平均值，得到一幅分辨率比较低的新图像， 它的像素数目变成了2个，即新的图像的分辨 率是原来的1/2，相应的像素值为：8 4 44向阳书苑 哈尔变换举例哈尔变换举例(续续) n步骤2：求差值(differencing) 用2个像素表示这幅图像时，图像的信息已经部分丢 失。为了能够从

27、由2个像素组成的图像重构出由4个像 素组成的原始图像，就需要存储一些图像的细节系数 (detail coefficient)，以便在重构时找回丢失的信 息。原始图像可用下面的两个平均值和两个细节系数 表示，8 4 1 -1 n步骤3：重复步骤1和2 把由第一步分解得到的图像进一步分解成分辨率更低 的图像和细节系数。在这个例子中，分解到最后，就 用一个像素的平均值6和三个细节系数2,1和1表示 整幅图像：6 2 1 -1 45向阳书苑 哈尔变换过程 分辨率 平均值 细节系数 4 9 7 3 5 28 4 1 -1 1 6 2 n把由4像素组成的一幅图像用一个平均像素值 和三个细节系数表示 n这个

28、过程就叫做哈尔小波变换(Haar wavelet transform)，也称哈尔小波分解(Haar wavelet decomposition) n这个概念可以推广到使用其他小波基的变换 46向阳书苑 3. 哈尔变换的特性哈尔变换的特性 n从这个例子中我们可以看到： u变换过程中没有丢失信息，因为能够从所记录的数 据中重构出原始图像。 u对这个给定的变换，我们可以从所记录的数据中重 构出各种分辨率的图像。例如，在分辨率为1的图 像基础上重构出分辨率为2的图像，在分辨率为2的 图像基础上重构出分辨率为4的图像 u通过变换之后产生的细节系数的幅度值比较小，这 就为图像压缩提供了一种途径。例如，去掉

29、一些微 不足道的细节系数并不影响对重构图像的理解 47向阳书苑 4. 一维哈尔小波变换一维哈尔小波变换 n求均值和差值的过程实际上就是一维小 波变换的过程，现在用数学方法重新描 述小波变换的过程 48向阳书苑 (1) 哈尔基函数哈尔基函数 n基函数是一组线性无关的函数，可以用来构造 任意给定的信号, 如用基函数的加权和表示。 定义了基和矢量空间，就可以把由2j 个像素组 成的一维图像看成为矢量空间 中的一个矢量。 n最简单的基函数是哈尔基函数(Haar basis function)。哈尔基函数在1909年提出，它是由 一组分段常值函数(piecewise-constant function)

30、 组成的函数集。这个函数集定义在半开区间 上， 每一个分段常值函数的数值在一个小范围里是 “1”，其他地方为“0” n以图像为例并使用线性代数中的矢量空间来说 明哈尔基函数。 49向阳书苑 n这4个常值函数就是构成矢量空间V 2的基 2 0( ) x2 1 ( ) x2 2( ) x 2 3( ) x2 0( ) x2 1 ( ) x2 2( ) x 2 3( ) x 01 23 22 22 1,01/41,1/41/2 ( )( ) 0,0, 1,1/23/41,3/41 ( )( ) 0,0, xx xx xx xx 其他其他 其他其他 2 0 ( )x 2 1 ( )x 2 2 ( )x

31、 2 3 ( )x 哈尔基函数哈尔基函数(续续1) 50向阳书苑 哈尔基函数哈尔基函数(续续2) n为了表示矢量空间中的矢量，每一个矢 量空间V j 都需要定义一个基(basis) n为生成矢量空间 而定义的基函数也叫做 尺度函数(scaling function)，这种函数通 常用符号 表示。 n哈尔基函数定义为 ( ) j i x 101 ( ) 0 x x 其他 51向阳书苑 哈尔基函数哈尔基函数(续续3) n哈尔基尺度函数 定义为 ( ) j i x ( )(2),0,1,(21) jjj i xxii 其中，j 为尺度因子，改变j 使函数图形缩小 或者放大；i为平移参数，改变i使函数

32、沿轴 方向平移。 n空间矢量V j定义为 ( )0,21 jjj i Vspxi 其中，表示线性生成(linear span) 52向阳书苑 (2) 哈尔小波函数哈尔小波函数 n小波函数通常用 表示。与框函数相 对应的小波称为基本哈尔小波函数(Haar wavelet functions)，并由下式定义， n哈尔小波尺度函数 定义为， ( ) i j x 101/2 ( )11/21 0 x xx 当 当 其他 ( ) i j x ( )(2),0,(21) i jjj xxii 53向阳书苑 哈尔小波函数哈尔小波函数(续续1) n用小波函数构成的矢量空间用W j表示为， n根据哈尔小波函数的

33、定义，可以写出生 成，W 0,W 1和W 2 等矢量空间的小波函 数 ( )0,1,21 jjj i Wspxi 其中，SP表示线性生成；j为尺度因子，改变j 使函数图形缩小或者放大；i为平移参数，改变 i 使函数沿轴方向平移 54向阳书苑 哈尔小波函数哈尔小波函数(续续2) n生成矢量空间W 2 的哈尔小波： 22 01 22 23 101/812/83/8 ( )1 1/82/8( )13/84/8 00 14/85/816/87/8 ( )15/86/8( )17/81 00 xx xxxx xx xxxx 其他其他 其他其他 55向阳书苑 哈尔小波函数哈尔小波函数(续续3) n生成矢量

34、空间W 2 的哈尔小波 56向阳书苑 (3) 哈尔小波变换过程哈尔小波变换过程 n(1) 用V2 中的哈尔基表示 n图像9 7 3 5有2j =22=4个像素，因此可 以用生成矢量空间中的框基函数的线性 组合表示， 22222222 00112233 ( )( )( )( )( )I xcxcxcxcx 其中的系数 是4个正交的像素值9 7 3 5，因此， 2222 0123 ,c c cc和 2222 0123 ( )9( )7( )3( )5( ) I xxxxx 57向阳书苑 哈尔小波变换过程哈尔小波变换过程(续续1) 图I(x)用V2中的哈尔基表示 58向阳书苑 n用V 0, W 0和

35、W1中的函数表示图像 u生成矢量空间V 0的基函数为 ，生成 矢量空间W 0的小波函数为 ，生成矢 量空间W1的小波函数为 和 ，根 据 哈尔小波变换过程哈尔小波变换过程(续续2) uI(x)可表示成 0 0 ( ) x 0 0 ( )x 1 0( ) x 1 1( ) x 2001 VVWW 00001111 00000011 ( )( )( )( )( )I xcxdxdxdx 59向阳书苑 n其中，4个系数 ， ， 和 就是原始图像通 过哈尔小波变换所得到的系数，用来表示整幅 图像的平均值和不同分辨率下的细节系数。4 个函数 , , 和 就是构成空间 V2的基。 哈尔小波变换过程哈尔小波

36、变换过程(续续3) n用图表示为 0 0 c 0 0 d 1 0 d 1 1 d 0 0 ( )x 0 0 ( )x 1 0( ) x 1 1( ) x 60向阳书苑 n一幅图像是一个二维的数据阵列，进行小波变 换时可以对阵列的每一行进行变换，然后对行 变换之后的阵列的每一列进行变换，最后对经 过变换之后的图像数据阵列进行编码 u1. 求均值与求差值 使用求均值和求差值的方法，对矩阵的每一 行进行计算 u3. 使用线性代数 由于图像可用矩阵表示，使用N个矩阵M1, M2，和MN 同样可以对图像矩阵进行求平均 值和求差值。这N个矩阵分别是第一、第二 和第N次分解图像时所构成的矩阵 5. 二维哈尔小波变换二维哈尔小波变换 61向阳书苑 二维哈尔小波变换二维哈尔小波变换(续续1) n用小波对图像进行变换有两种方法，一 种叫做标准分解(standard decomposition)， 另一种叫做非标准分解(nonstandard decomposition)。标准分解方法是指首先 使用一维小波对图像每一行的像素值进 行变换，产生每一行像素的平均值和细 节系数，然后使用一维小波对这个经过 行变换的图像的