小波分析完美教程经典

1 第 3章 小波与小波变换 (征求意见稿) 清华大学计算机科学与技术系 智能技术与系统国家重点实验室 林福宗，2001-9-25 小波是近十几年才发展起来并迅速应用到图像处理和语音等众多领域的一种 工具，是继 110多年前的傅立叶(Joseph Fourier)分析之后的一个重大突破，无论是对古老的 自然学科还是对新兴的高新技术应用学科都产生了强烈冲击。 小波理论是应用数学的一个新领域。要深入理解小波理论需要用到比较多的数学知识。 本章企图从工程应用角度出发，用比较直观的方法来介绍小波变换和它的应用，为读者深入 研究小波理论和应用提供一些背景。 3.1 小波介绍 3.1.1 小波简史 傅立叶理论指出，一个信号可表示成一系列正弦和余弦函数之和，叫做傅立叶展开式。 用傅立叶表示一个信号时，只有频率分辨率而没有时间分辨率，这就意味我们可以确定信号 中包含的所有频率，但不能确定具有这些频率的信号出现在什么时候。为了继承傅立叶分析 的优点，同时又克服它的缺点，人们一直在寻找新的方法。 20世纪初，哈尔(Alfred Haar)对在函数空间中寻找一个与傅立叶类似的基非常感兴趣。 1909年他发现了小波，并被命名为哈尔小波(Haar wavelets)，他最早发现和使用了小波。 20世纪 70年代，当时在法国石油公司工作的年轻的地球物理学家 Jean Morlet提出了小 波变换 WT(wavelet transform)的概念。 进入 20世纪 80年代，法国的科学家 Y.Meyer 和他的同事开始为此开发系统的小波分 析方法。Meyer 于 1986年创造性地构造出具有一定衰减性的光滑函数，他用缩放(dilations) 与平移(translations)均为 j2 ( j ³ 0的整数)的倍数构造了 2L (R)空间的规范正交基，使小波得 到真正的发展。 小波变换的主要算法则是由法国的科学家 Stephane Mallat在 1988年提出[1]。他在构造 正交小波基时提出了多分辨率的概念，从空间上形象地说明了小波的多分辨率的特性，提出 了正交小波的构造方法和快速算法，叫做 Mallat算法[1]。该算法统一了在此之前构造正交 小波基的所有方法，它的地位相当于快速傅立叶变换在经典傅立叶分析中的地位。 Inrid Daubechies，Ronald Coifman和 Victor Wickerhauser 等著名科学家把这个小波理论 引入到工程应用方面做出了极其重要的贡献。例如，Inrid Daubechies 于 1988 年最先揭示了 小波变换和滤波器组(filter banks)之间的内在关系[2]，使离散小波分析变成为现实。在信号 处理中，自从 S.Mallat和 Inrid Daubechies 发现滤波器组与小波基函数有密切关系之后，小 波在信号(如声音信号，图像信号等)处理中得到极其广泛的应用。 经过十几年的努力，这门学科的理论基础已经基本建立，并成为应用数学的一个新领域。 这门新兴学科的出现引起了许多数学家和工程技术人员的极大关注，是国际科技界和众多学 术团体高度关注的前沿领域。 2 3.1.2 小波概念 小波是定义在有限间隔而且其平均值为零的一种函数，它的波形如图 3-01(b)所示。图 (a)是大家所熟悉的正弦波，图(b)是从许多使用比较广泛的小波中挑选出的几种一维小波。 在图(b)所示的小波中，缩放函数和小波函数的名称大多数是以开发者的名字命名的， 例如 Moret小波函数是 Grossmann和 Morlet在 1984年开发的，db6缩放函数和 db6小波函 数是 Daubechies 开发的开发几种小波之一，Meyer 缩放函数和 Meyer 小波函数是 Meyer 开 发的。但也有不少例外，例如 Sym6缩放函数和 sym6小波函数则是 symlets的简写，是 Daubechies 提议开发的几种对称小波之一， coif2缩放函数和 coif2小波函数是 Daubechies 应 R. Coifman的请求而开发的几种小波之一。 与图(a)相比，图(b)所示的小波具有有限的持续时间和突变的频率和振幅，波形可以是 不规则的，也可以是不对称的，在整个时间范围里的幅度平均值为零。而正弦波和余弦波具 有无限的持续时间，它可从负无穷扩展到正无穷，波形是平滑的，它的振幅和频率也是恒定 的。 (b) 部分小波 图 3-01 小波与正弦波 在众多的小波中，选择什么样的小波对信号进行分析是一个至关重要的问题。使用的小 波不同，分析得到数据也不同，这是关系到能否达到使用小波分析的目的问题。如果没有现 成的小波可用，那么还需要自己开发合用的小波。 Owner 铅笔 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2007，版权所有， 仅供试用。ഀ 3 3.1.3 小波分析 信号分析一般是为了获得时间和频率域之间的相互关系。傅立叶变换提供了有关频率域 的信息，但时间方面的局部化信息却基本丢失。与傅立叶变换不同，小波变换通过平移母小 波(mother wavelet)可获得信号的时间信息，而通过缩放小波的宽度(或者叫做尺度)可获得信 号的频率特性。对母小波的缩放和平移操作是为了计算小波的系数，这些系数代表小波和局 部信号之间的相互关系。本节将介绍小波分析中常用的三个基本概念：连续小波变换、离散 小波变换和小波重构。 1. 连续小波变换 傅立叶分析是把一个信号分解成各种不同频率的正弦波，因此正弦波是傅立叶变换的基 函数。同样，小波分析是把一个信号分解成将原始小波经过移位和缩放之后的一系列小波， 因此小波同样可以用作表示一些函数的基函数。可以说，凡是能够用傅立叶分析的函数都可 以用小波分析，因此小波变换也可以理解为用经过缩放和平移的一系列函数代替傅立叶变换 的正弦波。 仔细观察图 3-02所示的正弦波和小波可以发现，用不规则的小波分析变化激烈的信号 也许比用平滑的正弦波更有效，或者说对信号的基本特性描述得更好。 图 3-02 傅立叶分析与小波分析使用的基函数 数学上傅立叶分析的过程实际上是用傅立叶变换表示， ( ) ( ) j tF f t e dtww +¥ - -¥ = ò 这个式子的含义就是，傅立叶变换是信号 ( )f t 与复数指数 j te w- ( cos sinj te t j tw w w- = + ) 之积在信号存在的整个期间里求和。傅立叶变换的结果是傅立叶系数 ( )F w ，它是频率w的 函数。 同样，连续小波变换(continuous wavelet transform，CWT )用下式表示， ( , ) ( ) ( , , )C scale position f t scale position t dty +¥ -¥ = ò 这个式子的含义就是，小波变换是信号 ( )f t 与被缩放和平移的小波函数y 之积在信号存在 的整个期间里求和。CWT 变换的结果是许多小波系数C，这些系数是缩放因子(scale)和位 置(position)的函数。 CWT 的变换过程可分成如下 5个步骤： 步骤 1: 把小波 ( )ty 和原始信号 ( )f t 的开始部分进行比较。 步骤 2: 计算系数C。该系数表示该部分信号与小波的近似程度。系数C的值越高表示 信号与小波越相似，因此系数C可以反映这种波形的相关程度。 Joshua Chen Highlight Joshua Chen Highlight Joshua Chen Squiggly Joshua Chen Squiggly Joshua Chen Squiggly Joshua Chen Highlight Joshua Chen Highlight Joshua Chen Underline Owner 铅笔 Owner 铅笔 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2007，版权所有， 仅供试用。ഀ 4 步骤 3: 把小波向右移，距离为k，得到的小波函数为 ( )t ky - ，然后重复步骤 1和 2。 再把小波向右移，得到小波 ( )t ky - 2 ，重复步骤 1和 2。按上述步骤一直进行下去，直到 信号 ( )f t 结束。 步骤 4: 扩展小波 ( )ty ，例如开展一倍，得到的小波函数为 ( / )ty 2 。 步骤 5: 重复步骤 1~4。 CWT 的整个变换过程如图 3-03所示。 图 3-03 连续小波变换的过程 小波变换完成之后得到的系数是在不同的缩放因子下由信号的不同部分产生的。这些小 波系数、缩放因子和时间之间的关系和它们的含义可以用图 3-04(a)表示，该图是用MATLAB 软件绘制的。图 (a)是用二维图像表示的小波变换分析图，x轴表示沿信号的时间方向上的位 置， y轴表示缩放因子，每个 -x y点的颜色表示小波系数C的幅度大小。图(b)是用三维图 像表示的小波变换分析图， z轴表示小波变换之后的系数。 5 (a) 二维图 (b) 三维图 图 3-04 连续小波变换分析图[4] 小波的缩放因子与信号频率之间的关系可以这样来理解。缩放因子小，表示小波比较窄， 度量的是信号细节，表示频率w比较高；相反，缩放因子大，表示小波比较宽，度量的是 信号的粗糙程度，表示频率w比较低。 2. 离散小波变换 在计算连续小波变换时，实际上也是用离散的数据进行计算的，只是所用的缩放因子和 平移参数比较小而已。不难想象，连续小波变换的计算量是惊人的。为了解决计算量的问题， 缩放因子和平移参数都选择 j2 ( j .>0 的整数)的倍数。使用这样的缩放因子和平移参数的小 波变换叫做双尺度小波变换(dyadic wavelet transform)，它是离散小波变换(discrete wavelet transform，DWT)的一种形式。从文献看，离散小波变换通常指的就是双尺度小波变换。 使用离散小波分析得到的小波系数、缩放因子和时间关系如图 3-05所示。图 (a)是 20世 纪 40年代使用 Gabor 开发的短时傅立叶变换(short time Fourier transform，STFT)得到的时间 -频率关系图，图(b)是 20世纪 80年代使用 Morlet开发的小波变换得到的时间-缩放因子(反 映频率)关系图。 图 3-05 离散小波变换分析图 执行离散小波变换的有效方法是使用滤波器。该方法是 Mallat在 1988年开发的，叫做 Mallat算法[1]，这种方法实际上是一种信号的分解方法，在数字信号处理中称为双通道子带 编码。 用滤波器执行离散小波变换的概念如图 3-06所示。图中，S 表示原始的输入信号，通 过两个互补的滤波器产生 A和 D两个信号，A表示信号的近似值(approximations)，D表示 信号的细节值(detail)。在许多应用中，信号的低频部分是最重要的，而高频部分起一个“添 加剂”的作用。犹如声音那样，把高频分量去掉之后，听起来声音确实是变了，但还能够听 Joshua Chen Highlight Joshua Chen Highlight Joshua Chen Highlight Joshua Chen Highlight Joshua Chen Underline Joshua Chen Underline Joshua Chen Note 低频信号为信号的近似值,高频信号为信号的细节值 wavelet中,大的sacle产生的系数是近似值,代表信号的低频分量,小的scale产生的系数是细节值,又称"添加剂",是信号的高频率分量 6 清楚说的是什么内容。相反，如果把低频部分去掉，听起来就莫名其妙。在小波分析中，近 似值是大的缩放因子产生的系数，表示信号的低频分量。而细节值是小的缩放因子产生的系 数，表示信号的高频分量。 图 3-06 双通道滤波过程 由此可见，离散小波变换可以被表示成由低通滤波器和高通滤波器组成的一棵树。原始 信号通过这样的一对滤波器进行的分解叫做一级分解。信号的分解过程可以叠代，也就是说 可进行多级分解。如果对信号的高频分量不再分解，而对低频分量连续进行分解，就得到许 多分辨率较低的低频分量，形成如图 3-07所示的一棵比较大的树。这种树叫做小波分解树 (wavelet decomposition tree)。分解级数的多少取决于要被分析的数据和用户的需要。 图 3-07 小波分解树 小波分解树表示只对信号的低频分量进行连续分解。如果不仅对信号的低频分量连续进 行分解，而且对高频分量也进行连续分解，这样不仅可得到许多分辨率较低的低频分量，而 且也可得到许多分辨率较低的高频分量。这样分解得到的树叫做小波包分解树(wavelet packet decomposition tree)，这种树是一个完整的二进制树。图 3-08表示的是一棵三级小波 包分解树。小波包分解方法是小波分解的一般化，可为信号分析提供更丰富和更详细的信息。 例如，小波包分解树允许信号 S 表示为 S=A1 + AAD3 + DAD3 + DD2。 Joshua Chen Underline Joshua Chen Underline Joshua Chen Underline Joshua Chen Underline Joshua Chen Note wavelet packet decomposition tree:不仅仅对信号的高频分量分解,也对信号的低频分量分解,得到的不仅仅是分辨率较低的低频率分量,还有高频率分量 7 图 3-08 三级小波包分解树 随便要提及的是，在使用滤波器对真实的数字信号进行变换时，得到的数据将是原始数 据的两倍。例如，如果原始信号的数据样本为 1000个，通过滤波之后每一个通道的数据均 为 1000个，总共为 2000个。于是,根据尼奎斯特(Nyquist)采样定理就提出了降采样 (downsampling)的方法，即在每个通道中每两个样本数据取一个，得到的离散小波变换的系 数(coefficient)分别用 cD和 cA表示，如图 3-09所示。图中的符号 表示降采样。 图 3-09 降采样过程 3. 小波重构 离散小波变换可以用来分析或者叫做分解信号，这个过程叫做分解或者叫做分析。把分 解的系数还原成原始信号的过程叫做小波重构(wavelet reconstruction)或者叫做合成 (synthesis)，数学上叫做逆离散小波变换(inverse discrete wavelet transform，IDWT)。 在使用滤波器做小波变换时包含滤波和降采样两个过程，在小波重构时要包含升采样 (upsampling)和滤波过程。小波重构的方法如图 3-10所示，图中的符号 表示升采样。 图 3-10 小波重构方法 升采样是在两个样本数据之间插入“0”，目的是把信号的分量加长。升采样的过程如 图 3-11所示。 图 3-11 升采样的方法 Joshua Chen Highlight 8 重构过程中滤波器的选择也是一个重要的研究问题，这是关系到能否重构出满意的原始 信号的问题。在信号的分解期间，降采样会引进畸变，这种畸变叫做混叠(aliasing)。这就需 要在分解和重构阶段精心选择关系紧密但不一定一致的滤波器才有可能取消这种混叠。低通 分解滤波器(L)和高通分解滤波器(H)以及重构滤波器(L'和 H')构成一个系统，这个系统叫做 正交镜像滤波器(quadrature mirror filters，QMF)系统，如图 3-12所示。 图 3-12 正交镜像滤波器系统 3.1.4 小波定义 在数学上，小波定义为对给定函数局部化的函数。小波可由一个定义在有限区间的函数 ( )xy 来构造， ( )xy 称为母小波(mother wavelet)或者叫做基本小波。一组小波基函数， { }, ( )a b xy ，可通过缩放和平移基本小波 ( )xy 来生成， , ( )a b x b x aa y y -æ ö= ç ÷ è ø 1 其中，a为进行缩放的缩放参数，反映特定基函数的宽度(或者叫做尺度)；b为进行平移的 平移参数，指定沿 x轴平移的位置。 当 ja = 2 和b ia= 的情况下，一维小波基函数序列定义为 / 2 , ( ) 2 (2 ) j j i j x x iy y - -= - ，或者 / 2, ( ) 2 (2 ) j j i j x x iy y= - 本教材将采用下面的表示法， / 2( ) 2 (2 ) i j j jx x iy y= - 其中， i为平移参数， j为缩放因子。 函数 ( )f x 以小波 ( )xy 为基的连续小波变换定义为函数 ( )f x 和 , ( )a b xy 的内积， ,( , ) , ( )f a b x b W a b f f x dx aa y y +¥ -¥ -æ ö= = ç ÷ è øò 1 在 1984年，A.Grossman和 J.Morlet指出，连续小波的逆变换为， , ,( ) , ( )a b a bf x f x a dadbCy y y +¥ +¥ - -¥ -¥ = ò ò 2 2 其中，Cy 为母小波 ( )xy 的允许条件(admissible condition)， 9 (ˆ ) C dy y w w w +¥ -¥ = < ¥ò 其中， (ˆ )y w 为 ( )xy 的傅立叶变换，而 ( )xy 是在平方可积的实数空间 2L (R)。 3.2 一维哈尔小波变换 哈尔小波是小波系列中最简单的小波。因此本节将从哈尔小波入手，首先介绍如何使用 哈尔小波分解一维函数，然后描述实际的基函数，最后介绍使用哈尔小波分解来压缩数据的 技术。 3.2.1 哈尔基函数 基函数是一组线性无关的函数，可以用来构造任意给定的信号，例如用基函数的加权和 表示。最简单的基函数是哈尔基函数(Haar basis function)。哈尔基函数在 1909年提出，它是 由一组分段常值函数(piecewise-constant function)组成的函数集。这个函数集定义在半开区间 [0,1)上，每一个分段常值函数的数值在一个小范围里是“1”，其他地方为“0”，现以图 像为例并使用线性代数中的矢量空间来说明哈尔基函数。 如果一幅图像仅由 02 =1个像素组成，这幅图像在整个[0,1)区间中就是一个常值函数。 用 00 ( )xf 表示这个常值函数，用 0V 表示由这个常值函数生成的矢量空间，即 0V ： 00 1 0 1 ( ) 0 x xf £ <ì = í î 其他 它的波形如图 3-13所示。 图 3-13 00 ( )xf 的波形 这个常值函数也叫做框函数(box function),它是构成矢量空间 0V 的基。 如果一幅图像由 12 =2个像素组成，这幅图像在[0,1)区间中有两个等间隔的子区间： [0,1/2)和[1/2,1) ，每一个区间中各有 1个常值函数，分别用 1 10 1( ) ( )x xf f和 表示。用 1V 表 示由 2个子区间中的常值函数生成的矢量空间，即 1V ： 10 1 0 0.5 ( ) 0 x xf £ <ì = í î 其他 ， 11 1 0.5 1 ( ) 0 x xf £ <ì = í î 其他 它们的波形如图 3-14所示。 10 图 3-14 1 10 1( ) ( )x xf f和 的波形 这 2个常值函数就是构成矢量空间 1V 的基。 如果一幅图像由 22 2 4j = = 个像素组成，这幅图像在[0,1)区间中被分成 22 2 4j = = 个 等间隔的子区间：[0,1/4),[1/4,1/2),[1/2,3/4) [3/4,1)和 ，它们的常值函数分别用 20 ( )xf ， 2 1 ( )xf ， 2 2 ( )xf 和 2 3 ( )xf 表示，用 2V 表示由 4个子区间中的常值函数生成的矢量空间，即 0 1 2 3 2 2 2 2 1, 0 1/4 1, 1/4 1 / 2 ( ) ( ) 0, 0, 1, 1/2 3/4 1, 3 /4 1 ( ) ( ) 0, 0, x x x x x x x x f f f f £ < £ <ì ì = =í í î î £ < £ <ì ì = =í í î î 其他 其他 其他 其他 它们的波形如图 3-15所示。 图 3-15 21 ( )xf ， 2 2 ( )xf 和 2 3 ( )xf 的波形 这 4个常值函数就是构成矢量空间 2V 的基。 我们可以按照这种方法继续定义基函数和由它生成的矢量空间。总而言之，为了表示矢 量空间中的矢量，每一个矢量空间 jV 都需要定义一个基(basis)。为生成矢量空间 jV 而定义 的基函数也叫做尺度函数(scaling function)，这种函数通常用符号 ( )ji xf 表示。哈尔基函数定 义为 1 0 1 ( ) 0 x xf £ <ì = í î 其他 (3-1) 哈尔基尺度函数 ( )ji xf 定义为 ( ) (2 ), 0,1, ,(2 1) j j ji x x i if f= - = × × × - (3-2) 其中， j为尺度因子，改变 j使函数图形缩小或者放大；i为平移参数，改变 i使函数沿 x轴 方向平移。 空间矢量 jV 定义为 { }( ) 0, , 2 1j j jiV sp x if= = × × × - (3-3) 11 其中， sp表示线性生成(linear span)。 需要注意的是，有些文章使用负整数来定义尺度函数并且使用不同的符号规则。因此在 阅读有关小波方面的文章时要注意作者使用的符号规则。 由于定义了基和矢量空间，我们就可以把由2 j个像素组成的一维图像看成为矢量空间 jV 中的一个矢量。由于这些矢量都是在单位区间[0,1)上定义的函数，所以在 jV 矢量空间 中的每一个矢量也被包含在 1jV + 矢量空间中。这说明矢量空间 jV 是嵌套的，即 0 1 1j jV V V V +Ì Ì × × × Ì Ì 矢量空间 jV 的这个性质可写成 1j jV V +Í 3.2.2 哈尔小波函数 小波函数通常用 ( ) i j xy 表示。与框函数相对应的小波称为基本哈尔小波函数(Haar wavelet functions)，并由下式定义， 1 0 1 / 2 ( ) 1 1/2 1 0 x x xy £ <ì ï = - £ <í ï î 当 当 其他 (3-4) 哈尔小波尺度函数 ( ) i j xy 定义为 ( ) (2 ), 0, ,(2 1) i j j jx x i iy y= - = ×× × - (3-5) 用小波函数构成的矢量空间用 jW 表示， { }( ) 0,1, , 2 1j j jiW sp x iy= = × × × - (3-6) 其中， sp表示线性生成； j为尺度因子，改变 j使函数图形缩小或者放大； i为平移参数， 改变 i使函数沿 x轴方向平移。 根据哈尔小波函数的定义，可以写出生成 0W ， 1W 和 2W 等矢量空间的小波函数。 生成矢量空间 0W 的哈尔小波： 0 0 1 0 1/2 ( ) 1 1/2 1 0 x x xy £ <ì ï = - £ <í ï î 其他 它的波形如图 3-16所示。 Owner 铅笔 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2007，版权所有， 仅供试用。ഀ 12 图 3-16 00 ( )xy 的波形 生成矢量空间 1W 的哈尔小波： 1 0 1 0 1 / 4 ( ) 1 1/4 1 / 2 0 x x xy £ <ì ï = - £ <í ï î 其他 11 1 1/2 3 / 4 ( ) 1 3 / 4 1 / 2 0 x x xy £ <ì ï = - £ <í ï î 其他 它们的波形如图 3-17所示。 图 3-17 1 10 1( ) ( )x xy y和 的波形 生成矢量空间 2W 的哈尔小波： 2 2 0 1 2 2 2 3 1 0 1/8 1 2 / 8 3 /8 ( ) 1 1/8 2/8 ( ) 1 3/8 4 /8 0 0 1 4/8 5/8 1 6 / 8 7 / 8 ( ) 1 5/8 6/8 ( ) 1 7/8 1 0 0 x x x x x x x x x x x x y y y y ì £ < £ <ì ï ï = - £ < = - £ <í í ï ï îî ì £ < £ <ì ï ï= - £ < = - £ <í í ï ï îî 其他 其他 其他 其他 它们的波形如图 3-18所示。 图 3-18 20 ( )xy 、 2 1 ( )xy 、 2 2 ( )xy 和 2 3 ( )xy 的波形 用哈尔小波 ( )ji xy 生成的矢量空间 jW 包含在矢量 1jV + 空间，这个性质用下式表示， Owner 铅笔 本页已使用福昕阅读器进行编辑。 福昕软件(C)2005-2007，版权所有， 仅供试用。ഀ 13 1j jW V +Í 3.2.3 函数的规范化 在小波变换中，有时要对基函数和小波函数进行规范化(normalization)。在半开区间 [0,1) 中，如果函数的内积 1 2 0 ( ), ( ) ( ) d 1j j ji i ix x x xf f f< >= =ò (3-7) 1 2 0 ( ), ( ) ( ) d 1j j ji i ix x x xy y y< >= =ò (3-8) 则称 ( ) ( )j ji ix xf y和 是规范化的函数。哈尔基和哈尔小波分别使用下面两个式子进行规范 化， / 2( ) 2 (2 ) i j j jx x if f= - (3-9) / 2( ) 2 (2 ) i j j jx x iy y= - (3-10) 其中，常数因子 / 22 j 用来满足内积(inner product)等于 1的条件。如果小波函数不是在 [0,1) 区间中定义的函数，常数因子将改变。 3.2.4 哈尔基的结构 使用哈尔基函数 ( )ji xf 和哈尔小波函数 ( ) j i xy 生成的矢量空间 jV 和 jW 具有下面的性 质， 1j j jV V W+ = Å (3-11) 其中，符号“Å”表示直和。这就是说，在矢量空间 1jV + 中，根据所选择的内积，生 成矢量空间 jW 的所有函数与生成矢量空间 jV 的所有函数都是正交的，即子空间 jW 是子空 间 jV 的正交补(orthogonal complement)。式(3-11)表明，在矢量空间 1jV + 中，矢量空间 jW 中 的小波可用来表示一个函数在矢量空间 jV 中不能表示的部分。因此，小波可定义为生成矢 量空间 jW 的一组线性无关的函数 ( ) i j xy 的集合。这些基函数具有两个重要性质： Ø 生成矢量空间 jW 的基函数 ( )ji xy 与生成矢量空间 jV 的基函数 ( )ji xf 构成矢量空 间 1jV + 的一个基。 14 Ø 生成矢量空间 jW 的每一个基函数 ( )ji xy 与生成矢量空间 jV 的每一个基函数 ( )ji xf 正交。 3.3 哈尔小波变换 小波变换的基本思想是用一组小波函数或者基函数表示一个函数或者信号，例如图像信 号。为了理解什么是小波变换，下面用一个具体的例子来说明小波变换的过程。 1. 求有限信号的均值和差值 [例 3. 1] 假设有一幅分辨率只有 4个像素 0 1 2 3, , ,p p p p 的一维图像，对应的像素值或者 叫做图像位置的系数分别为： [9 7 3 5] 计算它的哈尔小波变换系数。 步骤 1：求均值(averaging)。计算相邻像素对的平均值，得到一幅分辨率比较低的新图 像，它的像素数目变成了 2个，即新的图像的分辨率是原来的 1/2，相应的像素值为： [8 4] 步骤 2：求差值(differencing)。很明显，用 2个像素表示这幅图像时，图像的信息已经 部分丢失。为了能够从由 2个像素组成的图像重构出由 4个像素组成的原始图像，就需要存 储一些图像的细节系数(detail coefficient)，以便在重构时找回丢失的信息。方法是把像素对的 第一个像素值减去这个像素对的平均值，或者使用这个像素对的差值除以 2。在这个例子中， 第一个细节系数是(9-8)=1，因为计算得到的平均值是 8,它比 9小 1而比 7大 1，存储这个细 节系数就可以恢复原始图像的前两个像素值。使用同样的方法，第二个细节系数是(3-4)=-1， 存储这个细节系数就可以恢复后 2个像素值。因此，原始图像就可以用下面的两个平均值和 两个细节系数表示， [8 4 1 -1] 步骤 3：重复第 1，2步，把由第一步分解得到的图像进一步分解成分辨率更低的图像 和细节系数。在这个例子中，分解到最后，就用一个像素的平均值 6和三个细节系数 2,1和 -1表示整幅图像。 [6 2 1 -1] 这个分解过程如表 3-1所示。 表 3-1 哈尔变换过程 分辨率 平均值 细节系数 4 [9 7 3 5] 2 [8 4] [1 -1] 1 [6] [2] 由此可见，通过上述分解就把由 4像素组成的一幅图像用一个平均像素值和三个细节系 数表示，这个过程就叫做哈尔小波变换(Haar wavelet transform)，也称哈尔小波分解(Haar wavelet decomposition)。这个概念可以推广到使用其他小波基的变换。 在这个例子中我们可以看到，① 变换过程中没有丢失信息，因为能够从所记录的数据 中重构出原始图像。② 对这个给定的变换，我们可以从所记录的数据中重构出各种分辨率 的图像。例如，在分辨率为 1的图像基础上重构出分辨率为 2的图像，在分辨率为 2的图像 15 基础上重构出分辨率为 4的图像。③ 通过变换之后产生的细节系数的幅度值比较小，这就 为图像压缩提供了一种途径，例如去掉一些微不足道的细节系数而不影响对重构图像的理 解。 2. 哈尔小波变换 在例 3.1中，求均值和差值的过程实际上就是一维小波变换的过程，现在用数学方法重 新描述小波变换的过程。 (1) 用 2V 中的哈尔基表示 图像 ( )I x ＝[9 7 3 5]有 22 2 4j = = 像素，因此可以用生成矢量空间 2V 中的框基函数的 线性组合表示， 2 2 2 2 2 2 2 2 0 0 1 1 2 2 3 3( ) ( ) ( ) ( ) ( )I x c x c x c x c xf f f f= + + + 其中的系数 2 2 2 20 1 2 3, ,c c c c和 是 4个正交的像素值[9 7 3 5]，因此， 2 2 2 2 0 1 2 3( ) 9 ( ) 7 ( ) 3 ( ) 5 ( ) I x x x x xf f f f= + + + 用图形可表示为 图 3-19 ( )I x 用 2V 中的哈尔基表示 (2) 用 1V 和 1W 中的函数表示 生成矢量空间 1V 的基函数为 0 1( )xf 和 1 1( )xf ，生成矢量空间 1W 的小波函数为 10( )xy 和 1 1 ( )xy 。根据(3-11)， 2 1 1V V W= Å 因此， ( )I x 可表示成 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1( ) ( ) ( ) ( ) ( )I x c x c x d x d xf f y y= + + + 其中，系数 10c 和 1 1c 是分辨率为 2时的像素平均值， 1 0d 和 1 1d 为细节系数； 1 0( )xf 和 1 1 ( )xf 是 1V 中的哈尔基函数， 10( )xy 和 1 1 ( )xy 是 1W 中的哈尔小波函数。用图形可把 ( )I x 表示成 16 图 3-20 ( )I x 用 1V 和 1W 中的函数表示 (3) 用 0 0,V W 和 1W 中的函数表示 生成矢量空间 0V 的基函数为 0 0 ( )xf ，生成矢量空间 0W 的小波函数为 00 ( )xy ，生成矢 量空间 1W 的小波函数为 10( )xy 和 1 1 ( )xy 。根据(3-11)， 2 0 0 1V V W W= Å Å ( )I x 可表示成 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1( ) ( ) ( ) ( ) ( )I x c x d x d x d xf y y y= + + + 用图形可表示成， 图 3-21 ( )I x 用 0 0,V W 和 1W 中的函数表示 其中，4个系数 00c ， 0 0d ， 1 0d 和 1 1d 就是原始图像通过哈尔小波变换所得到的系数，用来表示 整幅图像的平均值和不同分辨率下的细节系数。4个函数 00 ( )xf , 0 0 ( )xy , 1 0( )xy 和 1 1 ( )xy 就是 构成 2V 空间的基。 3.4 规范化算法 规范化的小波变换与非规范化的小波变换相比，唯一的差别是在规范化的小波变换中需 要乘一个规范化的系数。下面用一个例子说明。 [例 3.2] 对函数 ( ) [2,5,8,9,7,4, 1, 1]f x = - - 作哈尔小波变换。 17 哈尔小波变换实际上是使用求均值和差值的方法进行分解。我们把 ( )f x 看成是矢量空 间 3V 中的一个向量，尺度因子 3j = ，因此最多可分解为 3层，如图 3-21所示。 图 3-21 小波分解的层次结构 分解过程如下。 步骤 1： (2 5,8 9,7 4, 1 1,2 5,8 9,7 4, 1 1) / 2 (7,17,11,0, 3, 1,3, 2)/ 2 f = + + + - + - - - - - = - - - 步骤 2： 7 17 11 0 7 17 11 0 ( , , , , 3, 1,3, 2)/ 2 2 2 2 2 24 11 10 11 3, 1, 3, 2)/ 2 2 2 2 2 f + + - - = - - - - - - -＝（ ， ， ， ， 步骤 3: ( ) ( )2 2 24 11 24 11 10 11 ( , , 3, 1,3, 2)/ 2 2 22 2 35 13 10 11 ( , , 3, 1,3, 2)/ 2 2 2 2 2 (12.3744 4.5962 -5.0000 5.5000 -2.1213 -0.7071 2.1213 -1.4142) f + - - = - - - - = - - - = ， ， ， ， 根据这个例子，我们可以归纳出规范化的哈尔小波变换的一般算法。假设一维阵列C有 h个元素，h等于 2的幂，执行一维哈尔小波变换的伪代码如下： ****************************************************************************** proc DecomposeArray(C : array[0... 1]h - of color): while h > 1 do: / 2h h¬ for 0i ¬ to 1h - do: '[ ] ( [ 2 ] [2 1])/ 2C i C i C i¬ + + 18 '[ ] ( [2 ] [2 1])/ 2C h i C i C i+ ¬ - + end for 'C C¬ end while end proc ****************************************************************************** 3.5 二维哈尔小波变换 前面已经介绍了一维小波变换的基本原理和变换方法。这节将结合具体的图像数据系统 地介绍如何使用小波对图像进行变换。 我们已经知道，一幅图像可看成是由许多像素组成的一个大矩阵，在进行图像压缩时， 为降低对存储器的要求，人们通常把它分成许多小块，例如以 8×8个像素为一块，并用矩 阵表示，然后分别对每一个图像块进行处理。在小波变换中，由于小波变换中使用的基函数 的长度是可变的，因此虽然无须像以离散余弦变换(DCT)为基础的 JPEG标准算法那样，把 输入图像进行分块，以避免产生 JPEG图像那样的“块效应”，但为便于理解小波变换的奥 妙，还是从一个小的图像块入手，并且继续使用哈尔小波对图像进行变换。 3.5.1 二维小波变换举例 假设有一幅灰度图像，其中的一个图像块用矩阵 A表示为， 64 2 3 61 60 6 7 57 9 55 54 12 13 51 50 16 17 47 46 20 21 43 42 24 40 26 27 37 36 30 31 33 32 34 35 29 28 38 39 25 41 23 22 44 45 19 18 48 49 15 14 52 53 11 10 56 8 58 59 5 4 62 63 1 A é ù ê ú ê ú ê ú ê ú ê ú= ê ú ê ú ê ú ê ú ê ú ê úë û 使用灰度表示的图像如图 3-22所示。 图 3-22 图像矩阵 A的灰度图 一个图像块是一个二维的数据阵列，进行小波变换时可以对阵列的每一行进行变换，然 后对行变换之后的阵列的每一列进行变换，最后对经过变换之后的图像数据阵列进行编码。 19 1. 求均值与求差值 为读者对用小波变换压缩图像有一个完整的概念，还是从求均值(averaging)与求差值 (differencing)开始。在图像块矩阵 A中，第一行的像素值为， R0: [64 2 3 61 60 6 7 57] 步骤 1：在 R0行上取每一对像素的平均值，并将结果放到新一行 N0的前 4个位置， 其余的 4个数是 RO行每一对像素的第一个数与其相应的平均值之差。这个变换过程如下所 示， R0: [64 2 3 61 60 6 7 57] 64 2 33 2 + = 3 61 32 2 + = 60 6 33 2 + = 7 57 32 2 + = 求差值， N0: [33 32 33 32 31 -29 27 -25] 64－33＝31 3-32＝-29 60-33＝27 7-32＝-25 步骤 2：对行 N0的前 4个数使用与第一步相同的方法，得到两个平均值和两个系数， 并放在新一行 N1的前 4个位置，其余的 4个细节系数直接从行 N0复制到 N1的相应位置 上。整个过程如下所示， N0: [33 32 33 32 31 -29 27 -25] 33 32 32.5 2 + = 33 32 32.5 2 + = 求差值， N1: [32.5 32.5 0.5 0.5 31 -29 27 -25] 33-32.5＝0.5 33-32.5＝0.5 步骤 3：用与第 1和 2步相同的方法，对剩余的一对平均值求平均值和差值， N1: [32.5 32.5 0.5 0.5 31 -29 27 -25] 32.5 32.5 32.5 2 + = 求差值， N1: [32.5 0 0.5 0.5 31 -29 27 -25] 32.5-32.5＝0 2. 图像矩阵的计算 使用求均值和求差值的方法，对矩阵的每一行进行计算，得到， RA ＝ 32.5 0 0.5 0.5 31 -29 27 -25 32.5 0 -0.5 -0.5 -23 21 -19 17 32.5 0 -0.5 -0.5 -15 13 -11 9 32.5 0 0.5 0.5 7 -5 3 -1 32.5 0 0.5 0.5 -1 3 -5 7 32.5 0 -0.5 -0.5 9 -11 13 -15 32.5 0 -0.5 -0.5 17 -19 21 -23 32.5 0 0.5 0.5 -25 27 -29 31 é ê ê ê ê ê ê ê ê ê ê ë ù ú ú ú ú ú ú ú ú ú ú ê úû 其中，每一行的第一个元素是该行像素值的平均值，其余的是这行的细节系数。使用同样的 方法，对 RA 的每一列进行计算，得到， 20 RCA ＝ 32.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 -4 4 -4 0 0 0 0 4 -4 4 -4 0 0 0.5 0.5 27 -25 23 -21 0 0 -0.5 -0.5 -11 9 -7 5 0 0 0.5 0.5 -5 7 -9 11 0 0 -0.5 -0.5 21 -23 25 -27 é ù ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê úë û 其中，左上角的元素表示整个图像块的像素值的平均值，其余是该图像块的细节系数。 根据这个事实，如果从矩阵中去掉表示图像的某些细节系数，事实证明重构的图像质量仍然 可以接受。具体做法是设置一个阈值d ，例如 5d £ 的细节系数就把它当作“0”看待，这 样经过变换之后的矩阵 RCA 就变成， Ad = 32.5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 27 -25 23 -21 0 0 -11 9 -7 0 0 7 -9 11 0 0 21 -23 25 -270 0 é ù ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê úë û Ad与 RCA 相比，“0”的数目增加了 18个，也就是去掉了 18个细节系数。这样做的好 处是可提高编码的效率。对 Ad矩阵进行逆变换，得到了重构的近似矩阵， A =% 59.5 5.5 7.5 57.5 55.5 9.5 11.5 53.5 5.5 59.5 57.5 7.5 9.5 55.5 53.5 11.5 21.5 43.5 41.5 23.5 25.5 39.5 32.5 32.5 43.5 21.5 23.5 41.5 39.5 25.5 32.5 32.5 32.5 32.5 39.5 25.5 23.5 41.5 43.5 21.5 32.5 32.5 25.5 39.5 41.5 23.5 21.5 43.5 53.5 11.5 9.5 55.5 57.5 7.5 5.5 59.5 11.5 53.5 55.5 9.5 7.5 57.5 59.5 5.5 é ù ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê ú ê úë û 矩阵 A的数据用图 3-23(a)表示，矩阵A% 的数据用图 3-23(b)表示。对比图(b)和图(a)，如 果不事先告诉你，图(a)是原图，而图(b)是经过变换并且去掉某些细节系数之后重构的图， 也许你很难断定那一幅是原图，那一幅是重构图。这说明图像质量的损失还是能够接受的。 21 图 3-23 原图与重构图像的比较 3. 使用线性代数 由于图像可用