小波变换压缩算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页 多媒体技术概述,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页 多媒体技术概述,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,6,章 小波变换压缩算法,主要内容,小波变换用于图像压缩的理由,傅里叶变换,窗口傅里叶变换,小波变换的原理,小波变换实例,小波变换与数据压缩,2,小波变换用于图像压缩的理由,基于,DCT (Discrete Cosine Transform),的压缩标准,JPEG,MPEG-1,MPEG-2, H.264,DCT,压缩的优点,简单、 便于硬件实现,3,小波变换用于图像压缩的理由,DCT,压缩的缺点,图像是分块处理，,沿块的边界方向相关性被破坏，,出现 “,blocking artifacts”,4,傅里叶变换,信号表示,多种方式信号的描述,:,例如一个函数表达式，这就是信号的时域表示，,傅里叶变换,1822,年,傅里叶提出频率的概念,:,通过傅里叶正变换将信号在频域分解，获得信号的频谱，再通过反变换重建原始信号。,频率仍然是傅里叶变换所定义 。,5,傅里叶变换,傅里叶变换的特点,具有频域准确定位，可分析信号能量在各个频域成分中的分布情况，,最常用的、最广泛的信号分析工具，,并且相关的理论研究已发展为一个重要的数学分支,调和分析。,6,傅里叶变换,傅里叶变换的不足,缺乏时间,-,频率的定位功能,不适于非平稳信号,无法根据信号的特点自动调节时域和频域的分辨率,7,傅里叶变换的不足成为了推动寻找新变换的动力,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,1946,年,Gabor,提出了短时傅里叶变换的概念 ，从而开始了非平稳信号的时频联合分析,8,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,9,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,Gabor,变换： 时窗函数,Gauss,函数时,时窗函数的,Fourier,变换仍然是,Gauss,函数，,保证了窗口傅立叶变换在频域内也有局域化的功能。,10,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,时窗（,Time Window,）,11,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,频窗（,Frequency Window,）,时窗函数,g(t),的傅立叶变换 ，,12,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,以上定义知，,g(t),和,G(),分别起着时窗和频窗的作用，在时间频率坐标系中，时窗和频窗共同作用的结果就构成了时,-,频窗，这样就从几何上直观地描述了时频局部化。,13,窗口傅里叶变换,窗口傅里叶变换（,short time Fourier transform,）,尽管窗式傅立叶变换能,解决变换函数的局域化问题,，但是，其窗口的大小和形状是固定的,即,窗口面积不变,，,窗口没有自适应性。,对于高频的信息，时间间隔要相对的小，更好地确定峰值和断点,，或者说需要用较窄的时域窗来反映信息的高频成分。,对于低频谱的信息，时间间隔要相对的宽才能给出完整的信号信息，,或者说必须用较宽的时域窗来反映信息的低频成分。,14,小波变换原理,小波变换的（,wavelet transform,）发展,20,世纪,80,年代后期发展起来的小波变换理论,它是继傅里叶,(Joseph Fourier),分析后信号处理与分析的强大工具,无论是对古老的自然学科还是对新兴的高新技术应用学科都产生了强烈冲击。,小波理论是应用数学的一个新领域。要深入理解小波理论需要用到比较多的数学知识。,从工程应用角度出发，直观的方法来介绍小波变换及其应用，为读者深入研究小波理论和应用提供一些背景材料,15,小波变换原理,小波变换的（,wavelet transform,）发展,哈尔,(Alfred Haar),对在函数空间中寻找一个与傅里叶类似的基非常感兴趣。,1909,年他发现了小波，,1910,年被命名为,Haar wavelets,最早发现和使用了小波的名称,16,小波变换原理,小波变换的（,wavelet transform,）发展,20,世纪,70,年代，当时在法国石油公司工作的年轻的地球物理学家,Jean Morlet,提出了小波变换,CWT (continuous wavelet transform),的概念。,法国科学家,Y.Meyer,创造性地构造出具有一定衰减性的光滑函数，用缩放,(dilations),与平移,(translations),均为,2,的,j,次幂的倍数构造了平方可积的实空间,L,2,(R),的规范正交基，使小波得到真正的发展,.,S.Mallat,于,1988,年在构造正交小波基时提出了多分辨率分析,(multiresolution analysis),的概念,从空间上形象地说明了小波的多分辨率的特性,提出了正交小波的构造方法和快速算法，叫做,Mallat,算法。,Mallat,算法地位相当于快速傅里叶变换在傅里叶分析中的地位。,17,小波变换原理,小波变换的（,wavelet transform,）发展,1988,年,Inrid Daubechies,最先揭示了小波变换和滤波器组,(filter banks),之间的内在关系,20,世纪,90,年代中期，,Sweldens,提出了小波变换提升方案,-,第二代小波变换， 用于,JPEG2000,小波在信号,(,如声音信号，图像信号等,),处理中得到极其广泛的应用。,18,小波变换原理,小波变换的（,wavelet transform,）发展,小波变换具有在不同尺度下保持时频分析窗口面积不变性质,自动调节对信号分析的时宽和带宽,被誉为信号分析的显微镜,19,小波变换原理,连续小波变换（,continuous wavelet transform,）,小波（,Wavelet (A small wave, a ripple),就是小的波形，所谓小，就是它具有衰减性，是存在于一个较小区域的波。,20,小波变换原理,连续小波变换变换（,continuous wavelet transform,）,小波基函数,21,小波变换原理,连续小波变换（,continuous wavelet transform,）,小波正变换,小波反变换,22,标注,:,a = scale variable,缩放因子,b= time shift,时间平移,在,CWT,中，缩放和平移是连续变化的,小波变换原理,连续小波变换（,continuous wavelet transform,）,函数的伸缩,23,小波变换原理,连续小波变换（,continuous wavelet transform,）,小波函数的伸缩,24,小波变换原理,连续小波变换（,continuous wavelet transform,）,25,时窗中心,：小波 的时窗中心是其母函数 的时窗中心乘 倍再平移 个单位,小波的 时窗宽度是其母函数 的时窗宽度的 倍。,小波变换原理,连续小波变换（,continuous wavelet transform,）,小波的 频窗中心是其母函数 的频窗中心的 倍,小波的 频窗宽度是其母函数 的频窗宽度的 倍,26,小波变换原理,连续小波变换（,continuous wavelet transform,）,用较小 对信号做高频分析时，实际是用高频小波对信号进行细致观察,用较大 对信号做低频分析时，实际是用低频小波对信号进行概貌观察,27,小波变换原理,连续小波变换（,continuous wavelet transform,）,部分小波波形,28,小波变换原理,子带编码,SBC,(subband coding),：,把信号的频率分成几个子带，然后对每个子带,分别进行编码，并根据每个子带的重要性分配,不同的位数来表示数据,20,世纪,70,年代，子带编码开始用于语音编码,20,世纪,80,年代中期开始在图像编码中使用,29,小波变换原理,离散小波变换,30,图中的符号 表示频带降低,1/2,，,HH,表示频率最高的子带，,LL,表示频率最低的子带。这个过程可以重复，直到符合应用要求为止。这样的滤波器组称为分解滤波器树,(decomposition filter trees),小波变换原理,离散小波变换,只有离散，小波变换才能应用,离散的方式有很多,离散小波变换的多分辨率分析,Mallat,创立了多分辨率分析理论,在多分辨率分析基础上，,Mallat,提出了基于,滤波器组,实现信号的小波正变换和反变换算法。执行离散小波变换的有效方法,31,小波变换原理,Mallat,算法,低通滤波器和高通滤波器构成双通道滤波,原始的输入信号,:S,两个互补的滤波器,A,表示信号的近似值,(approximations),D,表示信号的细节值,(detail),32,小波变换原理,Mallat,算法,低通滤波器和高通滤波器构成小波分解树,对低频分量连续分解,33,小波变换原理,Mallat,算法,小波包分解树,对低频分量和高频分量均连续分解,34,小波变换原理,Mallat,算法,下采样过程,原始信号的数据样本为,1000,个，通过滤波之后每一个通道的数据均为,1000,个，总共为,2000,个。,35,小波变换原理,Mallat,算法,下采样过程,原始信号的数据样本为,1000,个，通过滤波之后每一个通道的数据均为,1000,个，总共为,2000,个。,36,小波变换原理,Mallat,算法,下采样过程,原始信号的数据样本为,1000,个，通过滤波之后每一个通道的数据均为,1000,个，总共为,2000,个。,37,小波变换原理,Mallat,算法,下采样过程,原始信号的数据样本为,1000,个，通过滤波之后每一个通道的数据均为,1000,个，总共为,2000,个。,图中的符号 表示下采样,。,38,小波变换实例,一维哈尔小波变换,哈尔函数定义,39,小波变换实例,一维哈尔小波变换,哈尔函数定义,基函数,一组线性无关的函数，以用来构造任意给定的信号,40,小波变换实例,一维哈尔小波变换,哈尔基函数,最简单的基函数,41,小波变换实例,一维哈尔小波变换,哈尔基函数,42,小波变换实例,一维哈尔小波变换,尺度函数,：尺度函数,尺度函数张成的空间,V,j,V,j,的基的个数为,2,j,43,小波变换实例,一维哈尔小波变换,小波函数,：与尺度函数对应,哈尔小波函数,与哈尔函数相对应,44,小波变换实例,一维哈尔小波变换,小波函数,：与尺度函数对应,哈尔小波函数,与哈尔函数相对应,哈尔小波基函数,45,小波变换实例,一维哈尔小波变换,小波基函数构成的空间：,W,j,46,小波变换实例,一维哈尔小波变换,小波基函数构成的空间：,W,j,47,小波变换实例,一维哈尔小波变换,小波基函数构成的空间：,W,j,48,小波变换实例,一维哈尔小波变换,生成矢量空间,W,2,的哈尔小波基函数,49,小波变换实例,一维哈尔小波变换,生成矢量空间,W,2,的哈尔小波基函数,50,小波变换实例,一维哈尔小波变换,生成矢量空间,W,2,的哈尔小波基函数,51,小波变换实例,一维哈尔小波变换,实例,图像,9 7 3 5,像素个数：,2,j,=2,2,=4,V,2,中的哈尔基表示,52,小波变换实例,一维哈尔小波变换,实例,V,2,中的哈尔基表示的一般形式,其中的系数,53,小波变换实例,一维哈尔小波变换,实例,用,V,0,W,0,和,W,1,中的函数表示图像,生成空间,V,0,的哈尔基函数为,生成空间,W,0,的哈尔小波基函数为,生成矢量空间,W,1,的哈尔小波基函数为 和,I,(,x,),可表示成,54,小波变换实例,一维哈尔小波变换,实例,55,小波变换实例,一维哈尔小波变换,实例,56,小波变换实例,一维哈尔小波变换,实例,57,小波变换实例,一维哈尔小波变换,实例,58,小波变换实例,一维哈尔小波变换,实例,59,小波变换实例,一维哈尔小波变换,实例,生成其中，,4,个系数 ， ， 和 就是原始图像通过哈尔小波变换所得到的系数，用来表示整幅图像的平均值和不同分辨率下的细节系数。,4,个函数, ,和 就是构成空间,V,2,的基。,60,小波变换实例,一维哈尔小波变换,哈尔小波变换的快速算法,计算哈尔小波变换系数,步骤,1,：求均值,(averaging),。计算相邻像素对的平均值，得到一幅分辨率比较低的新图像，它的像素数目变成了,2,个，即新的图像的分辨率是原来的,1/2,，相应的像素值为：,8 4,步骤,2,：求差值,(differencing),用,2,个像素表示这幅图像时，图像的信息已经部分丢失。为了能够从由,2,个像素组成的图像重构出由,4,个像素组成的原始图像，就需要存储一些图像的细节系数,(detail coefficient),，以便在重构时找回丢失的信息。原始图像可用下面的两个平均值和两个细节系数表示，,8 4 1 -1,步骤,3,：重复步骤,1,和,2,把由第一步分解得到的图像进一步分解成分辨率更低的图像和细节系数。在这个例子中，分解到最后，就用一个像素的平均值,6,和三个细节系数,2,1,和,1,表示整幅图像：,6 2 1 -1,61,小波变换实例,一维哈尔小波变换,该算法可以推广到其他小波变换,分辨率,平均值,细节系数,4,9 7 3 5,2,8 4,1 -1,1,6,2,62,小波变换实例,二维哈尔小波变换,图像的二维变换,63,转置后继续对列实施变换相当于对行实施变换,小波变换实例,二维哈尔小波变换,例如,64,小波变换实例,二维哈尔小波变换,例如,65,小波变换实例,二维哈尔小波变换,例如,66,小波变换实例,二维哈尔小波变换,针对图像的小波变换的两种方法,标准分解,(standard decomposition),非标准分解,(nonstandard decomposition),67,小波变换实例,二维哈尔小波变换,标准分解,(standard decomposition),对图像的每一行进行小波变换，然后对这个经过行变换的图像的每一列进行小波变换,68,小波变换实例,二维哈尔小波变换,标准分解,(standard decomposition),69,小波变换实例,二维哈尔小波变换,标准分解,(standard decomposition),对图像每一行的像素值进行一维小波变换，再进行列变换，行变换与列变换交替进行,70,小波变换实例,二维哈尔小波变换,非标准分解,(nonstandard decomposition),交替地对图像的行和列进行小波变换,。,71,小波变换实例,二维哈尔小波变换,非标准分解,(nonstandard decomposition),72,小波变换实例,二维哈尔小波变换,非标准分解,(nonstandard decomposition),73,小波变换实例,二维哈尔小波变换,非标准分解,(nonstandard decomposition),74,小波变换实例,二维哈尔小波变换,非标准分解,(nonstandard decomposition),75,小波变换与数据压缩,76,原始图像,压缩图像,小波变换与数据压缩,压缩算法,1,（去除最小的系数）,77,小波变换与数据压缩,压缩算法,2,（全局）,78,小波变换与数据压缩,79,小波变换与数据压缩,小波变换可以用于图像、声音,(Sound),、视频压缩,小波的压缩过程通常分三部分：,小波变换部分，量化部分，熵编码部分,80,小波变换与数据压缩,81,Original,1 Level,2 Levels,3 Levels,小波变换与数据压缩,为了进一步说明高频中的信息的所含内容，我们将一个经过压缩后的图像，逐步还原出来，每多一次还原过程，也就是经过一次小波变换的逆变换，图像逐渐清晰起来，见下图,82,小波变换与数据压缩,83,Time 2 Decomp Bowl,Time 1 Decomp basic content,Time 4 Decomp Background,Time 3Decomp Figures,小波变换与数据压缩,84,小波变换与数据压缩,85,量化,