1、最新小波变换与JPEG编码小波变换与JPEG编码第10章 小波变换与JPEG 2000编码虽然基于DCT的JPEG标准的压缩效果已经很不错，但在较高压缩比时会出现明显的马赛克现象，且不能渐进传输。为了适应网络发展的需要，JPEG于2000年底推出了采用DWT (Discrete Wavelet Transform离散小波变换)的JPEG 2000标准。小波变换是1980年代中期发展起来的一种时频分析方法，比DCT这样的傅立叶变换的性能更优越，被广泛应用于调和分析、语音处理、图像分割、石油勘探和雷达探测等等方面，也被应用于音频、图像和视频的压缩编码。本章先介绍小波变换的来龙去脉，然后分别介绍连续
2、小波变换、离散小波变换、Haar小波变换和整数小波变换，最后介绍JPEG 2000的编码算法和标准。10.1 小波变换小波变换(wavelet transform)是傅立叶变换的发展，中间经历了窗口傅立叶变换。原始数据一般是时间或空间信号，在时空上有最大分辨率。时空信号经傅立叶变换后得到频率信号，在频域上有最大分辨率，但其本身并不包含时空定位信息。窗口傅立叶变换通过对时空信号进行分段或分块进行时空-频谱分析，但由于其窗口的大小是固定的，不适用于频率波动大的非平稳信号。而小波变换可以根据频率的高低自动调节窗口大小，是一种自适应的时频分析方法，具有多分辨分析功能。本节先讨论小波变换与（窗口）傅立叶
3、变换的关系，然后依次介绍连续小波变换、离散小波变换、Haar小波变换和第二代小波变换（整数小波变换）。10.1.1 傅立叶变换与小波变换傅立叶变换(Fourier transform)是法国科学家Joseph Fourier发表于1822年的他在用无穷三角级数求解热传导偏微分方程时所提出的一种数学方法，它可将时空信号变换成频率信号。Joseph Fourier鉴于傅立叶变换不含时空定位信息，（1971年的诺贝尔物理学奖获得者）匈牙利人Dennis Gabor于1946年提出窗口傅立叶变换（window Fourier transform）。可以用于时频分析，但是窗口大小是固定的。1984年法国
4、的物理学家Jean Morlet和A. Grossman，在进行石油勘探的地震数据处理分析时，又提出了具有可变窗口的自适应时频分析方法小波变换（wavelet transform）。傅立叶变换傅立叶变换(Fourier transform)是1807年法国科学家Joseph Fourier在研究热力学问题时所提出来的一种全新的数学方法，当时曾受到数学界的嘲笑与抵制，后来却得到工程技术领域的广泛应用，并成为分析数学的一个分支傅立叶分析。原始的多媒体数据一般为时空信号，在时空上有最大分辨率，并可利用时空上的相关性进行数据压缩。Fourier变换可将时空域中的多媒体信号映射到频率域来研究，即更符合人
5、类感觉特征，也可以利用信号在频率域中的冗余进行数据压缩。Fourier变换所得的频率信号，在频率域上有最大分辨率，但其本身并不包含时空定位信息。时空信号：f (t), t(-, ) （一维时间信号，参见图10-1）f (x, y), x, y(-, ) （二维空间信号）图10-1 音频信号的时间波形图Fourier变换，F(w)为频率信号：Skip Record If. （参见图10-2）Skip Record If.图10-2 音频信号的频率图窗口傅立叶变换虽然基于Fourier变换的频谱分析，在需要信号分析及数据处理的物理、电子、化学、生物、医学、军事、语音、图像、视频等众多科学研究与工程
6、技术的广阔领域得到了非常广泛和深入应用，但对既需要频谱分析又要求时空定位的应用，如雷达探测、语音识别、图像处理、地震数据分析等等，Fourier分析技术就显得力不从心了。为了弥补Fourier变换不能时空定位的不足，工程技术领域长期以来一直采用D.Gabor开发的窗口Fourier变换（短时Fourier变换），来对时空信号进行分段或分块的时空-频谱分析（时频分析）。窗口Fourier变换：（参见图10-4）Skip Record If.其中，g为窗口函数（参见图10-3）。图10-3 音频处理中常用的几种窗口函数图10-4 音频信号的三维频谱图虽然窗口Fourier变换能部分解决Fourie
7、r变换时空定位问题，但由于窗口的大小是固定的，对频率波动不大的平稳信号还可以，但对音频、图像等突变定信号就成问题了。本来对高频信号应该用较小窗口，以提高分析精度；而对低频信号应该用较大窗口，以避免丢失低频信息；而窗口Fourier变换则不论频率的高低，都统一用同样宽度的窗口来进行变换，所以分析结果的精度不够或效果不好。迫切需要一种更好的时频分析方法。小波变换近二十年来发展起来的小波(wavelet)分析正是这样一种时频分析方法，具有多分辨分析功能，被誉为数学显微镜。它是继一百多年前发明傅立叶分析之后的又一个重大突破，对许多古老的自然学科和新兴的高新技术应用学科都产生了强烈冲击，并迅速应用到图像
8、处理和语音分析等众多领域。1）函数展开与积分变换小波分析是傅立叶分析的发展，是分析数学的一个新分枝，高等数学中的微积分（数学分析）就是分析数学的基础。与幂级数、三角级数或傅立叶级数等一样，小波分析研究用一组简单函数，如xn、sin nx, cos nx等，来表示任意函数，如Skip Record If.（幂级数）Skip Record If.（三角级数/傅立叶级数）其中Skip Record If.被表示的函数的全体构成一个函数空间（一种函数的集合），而表示这些函数的函数族xn与sin nx, cos nx等则为函数空间的基底。函数展开式中的系数为该函数在函数空间中相对于此基底的坐标，对应于函
9、数空间的一个点。这相当于将函数从原来的域变到新的域，如三角级数将时空域的函数变换到频率域。为了求得展开式的系数，需要对原函数求微积分，如幂级数中的Skip Record If.三角级数中的Skip Record If.和傅立叶级数中的Skip Record If.若f (x)不是以2 l为周期的函数，在上式中改记x为t、Skip Record If.，并让Skip Record If.，则得Fourier变换：Skip Record If.这是一种复变函数的广义积分，也是一种积分变换。2）小波的发展自从近两百年前Joseph Fourier在研究热力学问题提出Fourier分析以后，长期以来许
10、多数学家一直在寻找更广泛函数空间的性能更好的基底函数族，工程技术领域也一直在寻找更好的时频分析方法，但收获甚微。1984年法国的年轻的地球物理学家Jean Morlet在进行石油勘探的地震数据处理分析时与法国理论物理学家A.Grossman一起提出了小波变换(wavelet transform, WT)的概念并定义了小波函数的伸缩平移系：Skip Record If.，但并没有受到学术界的重视。直到1986年法国大数学家Yves Meyer构造出平方可积空间L2的规范正交基二进制伸缩平移系：Skip Record If.小波才得到数学界的认可。1987年正在读硕士的Stephane Malla
11、t将自己熟悉的图像处理的塔式算法引入小波分析，提出多分辨分析的概念和构造正交小波的快速算法Mallat算法。1988年法国女科学家Inrid Daubechies构造出具有紧支集的正交小波基Daubechies小波。1990年美籍华裔数学家崔锦泰和武汉大学的数学教授王建忠又构造出基于样条函数的单正交小波函数样条小波。1992年Daubechies在美国费城举行的CBMS-NFN应用数学大会上作了著名的小波十讲Ten Lectures on Wavelets报告，掀起了学习与应用小波的高潮。1994年Wim Swelden提出了一种不依赖于Fourier变换的新的小波构造方法提升模式(lifti
12、ng scheme)，也叫第二代小波或整数小波变换。3）连续小波变换连续小波变换(CWT = Continuous wavelet transform)的定义为：Skip Record If.其中，a为缩放因子（对应于频率信息），b为平移因子（对应于时空信息），Skip Record If.为小波函数（又叫基本小波或母小波），Skip Record If.表示Skip Record If.的复共轭。连续小波变换的过程可参见图10-5。图10-5 连续小波变换的过程小波变换的特点有：（参见图10-6）时频局域性、多分辨分析、数学显微镜自适应窗口滤波：低频宽、高频窄适用于去噪、滤波、边缘检测等图1
13、0-6 窗口傅立叶变换与小波变换的时频特征如同三角函数sin x和cos x及e-jx可以缩放构成函数空间的基底sin nx, cos nx及 e-jwx 一样，母小波也可以缩放和平移而构成函数空间的基底：Skip Record If.及Skip Record If.与傅立叶变换不同，小波变换的结果有两个参数，多了一个可以表示时空位置信息的平移因子，所以其图示为一个二维曲面。图10-7/8是Mallat构造的一组典型数据的曲线及其连续小波变换曲面的二维与三维图示：图10-7 Mallat数据及其连续小波变换的二维图示图10-8 Mallat数据及其连续小波变换的三维图示4）小波函数小波变换与傅
14、立叶变换比较，它们的变换核不同：傅立叶变换的变换核为固定的虚指数函数（复三角函数）e-jwx,而小波变换的变换核为任意的母小波Skip Record If.。前者是固定的，而后者是可选的，实际上母小波有无穷多种，只要Skip Record If.满足下列条件即可。小波函数需满足的条件：绝对可积且平方可积，即Skip Record If.正负部分相抵，即Skip Record If.（即Skip Record If.）满足允许条件(admissible condition)，即Skip Record If.（广义积分收敛）其中Skip Record If.为Skip Record If.的傅立叶
15、变换常见的小波函数有：Haar小波(Alfred Haar，1910年)：Skip Record If.，参见图10-9。图10-9 Haar小波函数及其Fourier变换墨西哥草帽(Mexican hat)小波：Skip Record If.，参见图10-10。图10-10 墨西哥草帽小波函数及其Fourier变换Morlet小波(Jean Morlet，1984年)：Skip Record If.，参见图10-11。图10-11 Morlet小波函数(C=5)及其Fourier变换除了Haar小波外，其他紧支集小波都不是初等函数，有的小波函数是用导数/积分或微分方程/积分方程来定义，有的小
16、波用其傅立叶变换定义，有的小波甚至没有解析表达式，而只是一些数字解，很多小波为复函数，所以不太直观。可以把小波与三角函数中正弦波加以比较（参见图10-12）。图10-12 小波与正弦波离散小波变换将连续小波变换的缩放因子a离散化，得到二进小波变换；再将其平移因子b也离散化，就得到离散小波变换。1) 二进小波变换与滤波器为了适应数字信号处理，需要将小波变换离散化。可以先进行缩放因子的离散：若小波函数Skip Record If.满足Skip Record If.，则称Skip Record If.为基本二进小波。在连续小波变换中，若Skip Record If.为基本二进小波，则令a = 2k
17、，得到二进小波变换：Skip Record If.为了构造基本二进小波，可设满足：Skip Record If.可推出Skip Record If.，则大体上相当于一个低通滤波器，因此，(2x)的通道比(x)的宽，可设满足如下的双尺度方程：Skip Record If.其Fourier变换为：Skip Record If.，其中Skip Record If.为低通滤波器。由Skip Record If.，可得H(0) = 1 即hn = 1。若设Skip Record If.，其中Skip Record If.则G为高通滤波器，有Skip Record If.其Fourier变换为：Skip
18、Record If.因Skip Record If.且Skip Record If.，得G(0) = 0 即gn = 0。例如（B2滤波器），若取为二次B样条，则Skip Record If.可得hn = h1- n，h0 = h1 = 3/8 = 0.375，h -1 = h2= 1/8 = 0.125，其余hn = 0；因G不唯一，可令Skip Record If.，gn = -g1- n，解得-g0 = g1 = 0.5798，-g-1 = g2 = 0.0869，-g-2 = g3 = 0.0061，其余gn=0。又例如（B3滤波器），若取为中心三次B样条，则Skip Record I
19、f.可得hn = h- n，h0 = 3/8 = 0.375，h -1 = h1= 1/4 = 0.25，h -2 = h2= 1/16 = 0.0625，其余hn = 0；似上例可得gn = -g- n，-g-1 = g1 = 0.59261，-g-2 = g2 = 0.10872，-g-3 = g3 = 0.00008，其余gn为0。2) 离散小波变换下面再将二进小波变换中的平移因子也离散化：令b = n2k，则可得离散小波变换：Skip Record If.可以用前面所讲的滤波器系数改写成如下循环形式：Skip Record If.其中，Skip Record If.，D = Wf为差高
20、频部分，A = Sf为剩余低频部分，hk与gk为上面讲过的滤波器Skip Record If.之系数。可以写出正反离散小波变换的具体算法如下：正变换（分解）（保存Skip Record If.和所有Skip Record If.）j = 0; Skip Record If.;while ( j 0 ) Skip Record If.j-;Skip Record If. 图10-13 Mallat数据的离散小波变换说明：图形的横纵坐标分别表示时间（平移因子）和变换结果S f与W f的值。小波分解可以无限进行下去，J是自己指定的最大分解次数，一般为810。求和符号中kZ，无上下限，但具体计算时，由
21、于只有有限个hk、gk不为0，所以实际上是有限的。逆变换中h与g上的一杠表示复数的共轭，对于实h与g，则共轭与不共轭相同。求S f与W f都涉及到对所有的样本求和，不可能只处理一个样本。3) 小波分解执行离散小波变换的有效方法是使用滤波器。该方法是Mallat在1988年开发的，叫做Mallat算法。这种方法实际上是一种信号的分解方法，在数字信号处理中称为双通道子带编码。用滤波器执行离散小波变换的概念如图10-14所示。图10-14 双通道滤波过程图中，S表示原始的输入信号，通过两个互补的滤波器产生A和D两个信号，A表示信号的近似值(approximations)，D表示信号的细节值(deta
22、il)。在许多应用中，信号的低频部分是最重要的，而高频部分起一个“添加剂”的作用。犹如声音那样，把高频分量去掉之后，听起来声音确实是变了，但还能够听清楚说的是什么内容。相反，如果把低频部分去掉，听起来就莫名其妙。在小波分析中，近似值是大的缩放因子产生的系数，表示信号的低频分量。而细节值是小的缩放因子产生的系数，表示信号的高频分量。由此可见，离散小波变换可以被表示成由低通滤波器和高通滤波器组成的一棵树。原始信号通过这样的一对滤波器进行的分解叫做一级分解。信号的分解过程可以叠代，也就是说可进行多级分解。如果对信号的高频分量不再分解，而对低频分量连续进行分解，就得到许多分辨率较低的低频分量，形成如图
23、10-15所示的一棵比较大的树。这种树叫做小波分解树(wavelet decomposition tree)。分解级数的多少取决于要被分析的数据和用户的需要。小波分解树表示只对信号的低频分量进行连续分解。图10-15 小波分解树随便要提及的是，在使用滤波器对真实的数字信号进行变换时，得到的数据将是原始数据的两倍。例如， 如果原始信号的数据样本为1000个，通过滤波之后每一个通道的数据均为1000个，总共为2000个。于是,根据尼奎斯特(Nyquist)采样定理就提出了降采样(downsampling)的方法，即在每个通道中每两个样本数据取一个，得到的离散小波变换的系数(coefficient)
24、分别用cD和cA表示，如图10-16所示。图中的符号表示降采样。图10-16 降采样过程4) 小波重构离散小波变换可以用来分析或者叫做分解信号，这个过程叫做分解或者叫做分析。把分解的系数还原成原始信号的过程叫做小波重构(wavelet reconstruction)或者叫做合成(synthesis)，数学上叫做逆离散小波变换(inverse discrete wavelet transform，IDWT)。在使用滤波器做小波变换时包含滤波和降采样两个过程，在小波重构时要包含升采样(upsampling)和滤波过程。小波重构的方法如图10-17所示，图中的符号表示升采样。图10-17 小波重构方
25、法升采样是在两个样本数据之间插入“0”，目的是把信号的分量加长。升采样的过程如图10-18所示。图10-18 升采样的方法图10-19是对某数据进行离散小波变换后结果。图10-19 某数据的离散小波变换10.1.2 哈尔小波变换哈尔（Haar）小波是最简单的一种小波，本节首先介绍用来构造任意给定信号的哈尔基函数，然后介绍表示任意给定信号的哈尔小波函数，最后介绍函数的规范化和哈尔基的构造。哈尔基函数与哈尔小波函数函数空间的基底是一组线性无关的函数，称之为函数基，如xn和sinwx, coswx或ejwx，可以用来构造任意给定的信号f (x)，如用基函数的加权和表示：Skip Record If.
26、（幂级数）Skip Record If.（三角级数/傅立叶级数）其中，构成函数基的基本函数(n=w=1) x1和sinx, cosx或ejx称为基函数(basis function)。前面曾介绍过的（对小波的发展起了重要作用的）二进制伸缩平移系：Skip Record If.就是1986年Meyer构造出的平方可积函数空间L2的规范正交函数基，其中的Skip Record If.为基函数，2 j为伸缩因子，k为平移因子。若固定j，则函数基中所有函数Skip Record If.的形状大小都相同，仅有平移，只能表示固定尺度的函数空间V j，所以也称j为尺度因子，称Skip Record If.为
27、尺度函数(scaling function)。1）哈尔基函数最简单的基函数是匈牙利数学家Alfrd Haar（哈尔）在1909年提出的哈尔基函数框函数(box function)：Skip Record If.其对应的尺度函数为Skip Record If.，k = 0, 1, 2, ., 2 j-1可见，原始的哈尔基函数Skip Record If.相比，由于尺度因子2 j的作用，非0区间的长度为1/2 j会随着j的增加而成倍缩少，面积也以同样的速度缩小；由于平移因子k的作用，非0区间会随着k平移k/2 j。图10-20是j=0, 1和2时尺度函数的部分波形图。 Skip Record If
28、.的波形 Skip Record If.和Skip Record If.的波形Skip Record If.、Skip Record If.、Skip Record If.和Skip Record If.的波形图10-20 哈尔基函数所对应尺度函数的波形矢量空间V j定义为由尺度函数Skip Record If.的线性组合生成的函数空间（显然是分段的等间隔台阶函数，每段的长不小于1/2 j）：Skip Record If.因为j越大，尺度函数越窄（分段1/2 j越细），能表示的函数就越多，所以有Skip Record If.，即矢量空间V j是嵌套的：Skip Record If.。2）哈尔小
29、波函数由框函数所构成的函数基虽然能生成函数空间，但框函数本身并不是小波函数，因为它不满足无穷积分为0的条件。与框函数相对应的小波函数为前面已经介绍过的哈尔小波函数(Haar wavelet functions)：Skip Record If.其对应的尺度函数为Skip Record If.，k = 0, 1, 2, ., 2 j-1类似于哈尔基函数，与原始的哈尔小波函数Skip Record If.相比，由于尺度因子2 j的作用，非0区间的长度为1/2 j也会随着j的增加而成倍缩少，面积也以同样的速度缩小；由于平移因子k的作用，非0区间也会随着k平移k/2 j。图10-21是j=0, 1和2时尺度函数的部分波形图。Skip Record If.的波形 Skip Record If.和Skip Record If.的波形Skip Record If.、Skip Record If.、Skip Record If.和Skip Record If.的波形图10-21 哈尔小波函数所对应尺度函数的波形由哈尔小波的尺度函数所构成的矢量空间为Skip Record If.因为Skip Record If. (1)即Skip Record If.可用Skip Record If.表示，所以有Skip Rec
