小波变换科普性质的.ppt

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