2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
1
4.2 离散余弦 (cos) 变换离散余弦变换也称为 DCT变换,一维离散余弦变换的定义由下式表示：
式中,u为频率变量,u=0,1,…,N-1。 f(x)是时域 N点序列,
x=0,1,…,N-1。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
一维离散余弦变换的反变换由下式表示：
二维离散余弦变换的定义由下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
其中,f(x,y)是空间域二维阵列函数,x,y=1,2,…,N-1，
F(u,v)是频域二维阵列函数 。 式中表示的阵列为 N× N。
二维离散余弦变换的反变换由下式表示：
如果采用矩阵形式表示,则一维离散余弦变换由下式表示：
[F(u)]=[A][f(x)]
[f(x)]=[A]T[F(u)]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
对 4× 4的变换矩阵 [A]为：
二维离散余弦变换矩阵形式表示为：
[F(u,v)]=[A][f(x,y)][A]T
[f(x,y)]=[A]T[F(u,v)][A]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
离散余弦变换可以按照定义直接计算,但实际上它是一种有快速算法的正交变换,下面我们推导其快速算法 。
由定义
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
如果把时域数据作如下拓展：
则 fe(x)的离散余弦变换可以写成下式：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
实际上是 2N点的离散傅立叶变换，所以，离散余弦变换可以通过把数据序列拓展为 2N，然后作离散傅立叶变换，得到的结果取其实部便可以得到离散余弦变换。
同理，在作反变换时，首先将 F(u)作如下拓展：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
那么，反变换也可以由下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
4.3 Walsh－ Hadamard(沃尔什一哈达玛 ） 变换离散傅立叶变换和离散余弦变换在快速算法中都用到复数乘法,相对而言仍需要较多的计算时间 。 在某些应用领域,需要更为方便有效的变换方法,沃尔什一哈达玛变换就是其中的一种 。
Walsh－ Hadamard变换是一种矩阵元素值仅由 1或一 1
组成的正交变换矩阵,因此,用这种变换矩阵作变换处理时,仅用到加,减法运算,可大大提高变换处理速度 。
对于 Walsh－ Hadamard矩阵,有两种典型的序,即
Hadamard序的 Hh及 Walsh序的 Hw,对 4× 4的矩阵,Hh及 Hw
分别为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
Hadamard矩阵的各行中元素符号变换次数若用 k来表示,则相当于富里叶变换中频率含义的列率?可定义为：
Hh和 Hw的区别是 Hw是按列率排列的。
当已知低阶的 Hadamard矩阵 HN后，则可按：
将低阶 Hadamard矩阵扩展为高阶 Hadamard矩阵。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
4.3 Haar（ 哈尔 ） 变换
Haar变换是一种元素值仅取 1,-1,0或上述值乘以
21/2的变换矩阵,它是另一种计算效率高的变换 。 这种变换的特点是其变换结果由两部分组成,即由原图象全体象素值决定的区域与由原图象部分象素值所决定的区域两部分所构成 。
Haar函数是完备的,归一化的正交函数 。 在 [0,1]
区间内,harr(0,t)为 1,harr(1,t)在左半个区间内取值为 1,在右半个区间内取值为 -1。 它的其它函数值取 0和
± 1乘以 21/2幂,即 ± 21/2,± 2,± 2× 21/2,± 4等 。 具体定义如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
一般情况的 Haar函数定义为
4× 4的 Haar变换矩阵为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
Haar变换可以直接反应线和边,这是由于它的基函数有类似的这些特征 。 在各种变换中,如果一个信号或信号中的一部分可以近似地匹配上某一基函数,则在变换后,会产生一个对应那个基函数的较大的变换系数 。 由于基函数是正交的,则在这个信号对于其它的基函数将产生较小的系数 。 这样,Haar变换可以给出一些边的尺寸和位置信息 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
8× 8的 Haar变换矩阵为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
对于更大的 N也有相同的形式 。 由于矩阵中有许多常数和零值,Haar变换可以非常快的计算出来 。
用矩阵形式表示,则一维 Haar变换由下式表示：
[F(u)]=[Haar][f(x)]
[f(x)]=[ Haar]T[F(u)]
二维 Haar变换矩阵形式表示为：
[F(u,v)]=[Haar][f(x,y)][Haar]T
[f(x,y)]=[Haar]T[F(u,v)][Haar]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
4.4 斜 (slant) 变换在图像处理中用到的另一种正交变换是斜变换 。 斜向量和斜变换是 Enomoto 和 Shibata于 1971年提出来的 。 斜变换是一种由锯齿波构成的变换,其特点是能有效地表示图象中缓慢的灰度变化,,目前斜变换以成功应用于图像编码 。
斜变换的 2× 2矩阵表示如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
由此 2× 2矩阵，通过下面的方式产生 N× N矩阵：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
其中,I为阶数为 N/2-2的单位阵，且例如，当 N=4时,bN=1/51/2,aN=2/51/2,I=[0],则 4× 4的
slant变换矩阵 S为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
用矩阵形式表示,则一维 slant变换由下式表示：
[F(u)]=[S][f(x)]
[f(x)]=[S]T[F(u)]
二维 slant变换矩阵形式表示为：
[F(u,v)]=[S][f(x,y)][S]T
[f(x,y)]=[S]T[F(u,v)][S]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
4.6 小波 (Wavelet)变换
4.6.1 傅立叶变换的局限性自从 1822年傅立叶发表,热传导解析理论,以来,傅立叶变换一直是信号处理领域中最完美,应用最广泛,效果最好的一种分析手段 。 傅立叶变换使用的是正弦曲线作为它的正交基函数,对于积分变换来说,这些函数都在两个方向无限扩展 。 离散傅立叶变换的基向量也在它们的整个域中非零 。 也就是说,它们并不是紧支集 。 对比之下,瞬态信号只在一个很短的区间内非零 。 与此相同的,图像中的许多重要特征 （ 例如边缘 ） 也是在空间位置中高度局部化的 。 这些成分并不类似于任何一个傅立叶基函数,这使得傅立叶变换以及在前面提到过的一些其它变换,在压缩和分析包含瞬态或局部化成分的信号和图像时,得不到最佳表示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
一个变换中的每个系数都是通过输入函数和其中一个基函数之间的内积确定的 。 在某些意义上,这个值表示输入函数和那个特定基函数之间的相似程度,
如果基函数是正交的 （ 或正交归一的 ）,那么任两个基函数间的内积为零,这表明它们完全不相似 。 所以如果信号或图像是由与一个或几个基函数相似的分量组成系数以外,其余系数都将很小 。
同样,逆变换可以看作是通过以变换系数为幅度权重的基函数加权和,来重构原始信号或图像的 。 所以如果信号或图像是由与一个或少量基函数相似的分量组成,那么只需对一些有较大幅度的项求和即可,
因此其它许多项都可以忽略,这 样 信号和图像就可用少量变换以 紧凑的方式表示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
进而言之，如果信号和图像中感兴趣的分量与一个或少量基函数相似，那么这些分量将出对那些（仅仅是那些）基函数有大系数来体现。这样它们在变换中就“容易被找到”。
而且，如果一个不希望的分量（噪声）与一个或少量基函数相似，那么，它也会容易地被找到。它也因而容易地被去掉，
此时只需要简单地降低 (或置为零）相应的变换系数即可。归纳起来，用与信号或图像中所期望的成分相似的基函数对该信号或图像进行变换是有潜在价值的。还需指出的是瞬变分量是无法与傅立叶变换或其它波状变换的基函数相似的。尽管傅立叶变换能够用正弦函数之和表示任何分析函数 — 甚至是一个狭窄的瞬态信号。然而，这是通过错综复杂的安排，
通过相互抵消除去一些正弦波的方式，构造出在大部分区间都为零的函数而实现的。当然，这对于可逆变换来说是一个有效的方法，但它却使此函数的频谱上呈现一幅相当混乱的构成。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
实际中，对于一些常见的非平稳信号，如音乐信号；
语音信号；检测信号等，它们的频域特性都随时间而变化，因此也可称它们为时变信号，对这一类时变信号进行分析，通常需要提取某一时间段（或瞬间）的频域信息或某一频率段所对应的时间信息。因此，寻求一种具有一定的时间和频率分辨率的基函数来分析时变信号，
一直是信号处理界及数学界人士长期以来努力的目标。
4.6.2 波和小波 （ wavelet）
小波概念的真正出现应算于 1984年,法国地球物理学家
J.Morlet在分析地震数据时提出将地震波按一个确定函数的伸缩,平移系展开 。 随后,他与 A.Grossmann共同进行研究,发展了连续小波变换的几何体系 。 由此能将任意一个信号分解成对空间和尺度的贡献 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
1985年,Y.Meyer,A.Grossmann与 I.Daubechies共同进行研究，选取连续小波空间的一个离散子集，得到了一组离散的小波基（称为小波框架）；而且根据小波框架的离散子集的函数，恢复了连续小波函数的全空间。
在此之后,小波变换作为信号处理的一种手段,逐渐被越来越多领域的理论工作者和工程技术人员所重视和应用,并在许多应用中取得了显著的效果,同传统的处理方法相比,产生了质的飞跃,证明了小波技术作为一种调合分析方法,具有十分巨大的生命力和广阔的应用前景 。 如将小波用于地震信号的分析与处理； 将二进小波变换用于图像的边缘检测,图像压缩与重构；将连续小波变换用于涡流的研究；将小波变换用于噪声中的未知瞬态信号；将小波变换用于语音信号的分析,变换和综合 ;将正交小波变换用于算子及拟微分算子的化简；将小波变换的自适应性用于解微分方程；将小波变换用于电磁场领域的若干问题研究等,都取得了初步成果 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
下图说明了波与小波之间的差异 。 顶上的两条曲线是频率不同的余弦波,持续宽度相同 。 底下的两条是沿着轴向频率和位置都不相同的小波 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
根据时频域分析，一个信号的每个瞬态分量映射到时间
－频率平面上的位置对应于分量主要频率和发生的时间,下图是一个示例。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
30
在小波变换的系统理论发展起来以前，其基本思想已经在许多领域的应用中有所体现，只是还没有在数学上形成一个体系。例如，计算机视觉中的多分辨率分析等，金字塔式图像压缩编码概念，通信及语言处理中的子带编码，数字信号处理中的多采样率滤波器组,这些在工程中获得广泛应用的朴实方法，都可以用小波变换作为理论基础。
比如，图像中的物体是出现在不同大小尺度上的。例如，
一条边缘可以是由黑到白的一个突变，也可以是在一个较长距离上的渐变。对于图像表示或分析，采用多分辨率策略就是在设法利用这一概念。制图方法也可以用来说明这一策略。
地图通常以不同尺度来描得。一幅地图的尺度是领域实际大小与它在地图上的表示的比值。在较大尺寸上，例如在地球仪上，大陆和海洋等主要特征是可见的，而像城市街道这样的细节信息就在地图的分辨率之外了。而在较小的尺度上，
细节变得可见而较大的特征却不见了。因而,引到一个较远距离处的地点，就需要一套用不同尺度绘制的地图。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
31
金字塔算法也是发展小波理论的原始基础 。 设想从一幅 1024× 1024的数字图像生成 10幅尺度不同的附加图像 。
每一次通过连续平均 2× 2的像素块,并丢掉隔行隔列的像素,得到的将是 512× 512,256× 256等一直到 1× 1的图像 。
然后对每一幅图像都用某种 3× 3的边缘检测算子来执行边缘检测 。 在原始图像上则会得到小边缘,在 512× 512和
256× 256像素图像上能找到稍大的边缘,而在 16× 16和更小的图像上就只能找到非常大的边缘 。
小波变换正是沿着多分辨率这条线发展过来的 。 与时频域分析一样,－个信号用一个二 维空间表示,不过这里的纵轴是尺度而不是频率 。 变尺度是通过对基本小波伸缩和平移而构成一组基函数来实现的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
32
4.6.3 连续小波变换
1,小波变换的定义设函数 f(t)∈L 2(R)( 平 方 可 积 函 数 空 间
L2(R)={x(t)∫ R|x(t)|2dt<∞}),则小波变的定义如下：
其中，积分核为 的函数族。 a＞ 0为尺度参数
（伸缩参数）,b为定位参数（平移参数），函数称为小波。
若 a＞ 1函数 ψ (t)具有伸展作用，若 a＜ 1函数 ψ (t)具有收缩作用。伸缩参数 a对 ψ (t)的影响如下图：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
33
随着参数 a的减小,ψ(t)的支撑区也随之变窄，反之亦然。
ψ(t)随伸缩参数 a和平移参数 b而变化如下图：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
34
图中小波函数为 。 当 a=2,b=15时,ψ a,b(t)= ψ 2,15(t)的波形从原点向右移至 t=15,且波形展宽。当 a=1/2,b=-10时,ψ a,b(t)= ψ 1/2,-10(t)的波形从原点向左移至 t=-10,且波形收缩。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
35
小波函数 ψ (t)的选择不是唯一的,也不是任意的 。 这里 ψ (t)是归一化的具有单位能量的解析函数,它应满足如下几个条件：
(1)定义域应是紧支撑的 （ Compact support）,也就是说在一个很小的区域之外,函数为零,即函数应有速降特性 。
（ 2） 平均值为零,即：
其高阶矩也为零。
该条件也叫小波的容许条件 （ Admissibility condition） 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
36
记则有
Cψ是有限值意味 Ψ(ω)连续可积。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
37
由上式可以看出,小波 ψ (t)在 t轴上取值有正有负才能保证上式积分为零 。 所以 ψ (t)应有振荡性 。
上述条件可以概括为,小波应是一个具有振荡性和迅速衰减的波 。
对于所有 f(t),ψ(t)∈ L2R,连续小波逆变换有下式给出：
小波变换是能量守恒的，即下式成立：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
38
4.6.4几种典型的一维小波
（ 1） Haar小波其波形如下图所示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
39
（ 2） Mexico Hat 小波
Mexico Hat 小波是 Gauss函数的二阶导数,即：
Mexico Hat 小波是实值小波，它的更普遍的形式由下式给出，即由 Gauss分布的 n阶导数给出：
其波形如下图所示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
40
（ 3） Morlet 小波
Morlet 小波是最常用的复值小波,它可由下式给出：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
41
其波形如下图所示：
4.6.5 小波变换的性质
（ 1） 线性 设则
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
42
（ 2） 平移和伸缩的共变性连续小波变换在任何平移之下是共变的,即若是一对小波变换关系，则也是一对小波变换关系。
也是一对小波变换关系 。
除上面的性质,小波变换还有微分运算,局部正则,
能量守恒,空间 -尺度局部花等特性 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
43
4.6.6 离散小波变换离散小波可由下式定义：
相应的离散小波变换可由下式定义：
连续小波可以刻画函数 f(t)的性质和变化过程,用离散小波也可以刻画 f(t)。 通过展开把 f(t)写成级数的形式,就构成了 n维空间中函数逼近问题 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
44
离散小波变换的反变换为：
对于 f(t)也为离散函数,可以用采样的形式表示出来,
其离散小波变换为其反变换为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
45
4.6.7 二维 小波二维连续 小波变换的定义逆变换为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
46
二维离散 小波变换的定义：
逆变换为：
对于输入函数也为离散的情况，其变换可记为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
47
其反变换可记为：
小波变换作为一种数学理论和方法在科学技术界引起了越来越多的关注和重视。在工程应用领域，特别是在信号处理、图像处理、模式识别、语音识别、量子物理、地震勘测、流体大学、电磁场,CT成像、机器视觉、机械故障诊断与监控、分形、数值计算等领域，它被认为是近年来在工具及方法上的重大突破，可以预料，在今后数年中，
它将成为科技工作者经常使用的又一锐利的数学工具。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
48
4.7卷积
4.7.1 卷积定义已知函数 g(t)和 x(t),定义两函数的卷积为：
卷积的一个重要用途是描述处理系统输入和输出的关系 。 对线性时不变系统的输出,可通过输入信号与一表征系统特性的函数 g(t)的卷积得到 。 表征函数叫作系统的冲激响应 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
49
卷积积分可简记为
y(t)=g(t)*x(t)
卷积运算具有几个有用的性质 。 首先,卷积具有交换性,
即
f(t)*g(t)=g(t)*f(t)
此外,卷积还满足对加法的分配律,即
f(t)*(g(t)+h(t))= f(t)*g(t)+ f(t)*h(t)
卷积还满足结合律,这意味着
f(t)*(g(t)*h(t))= (f(t)*g(t))*h(t)
对于求导有以下性质
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
50
4.7.2一维离散卷积对于离散序列,其卷积可用与连续函数相类似的方法求得 。 此时自变量变为下标,而积则由求和代替 。 因此,对于两个长度分别为 m和 n的序列 f(i)和 g(i）,其对应卷积表示为：
上式给出一个长度为 N=m+n-1的输出序列 。
尽管离散卷积和连续卷积是相当不同的运算,但它们具有许多共同的性质 。 尤其值得庆幸的是我们可在数字图像上进行的离散卷积,与连续卷积几乎具有对应的性质,而许多在图像数字化之前和变回连续形式之后对图像施加的影响,都可用连续卷积来描述 。
这一优点在图像恢复中得到充分利用,图像恢复的目的是扭转业已加在图像上的退化影响 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
51
4.7.3 二维卷积二元连续函数的卷积与一维情况相类似 。 用 x和 y表示两个独立的变量 。 二维卷积表达式是：
4.7.4 二维离散卷积
4.7.5用二维离散傅立叶变换完成卷积计算若 M× N的图象 g(m,n)与 h(m,n)卷积得到 f(p,q)即：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
52
则根据卷积定理,令 G,H,F分别表示 g,h,f的二维离散傅立叶变换,则下列关系成立,即：
F(k,l)﹦ G(k,l)·H(k,l)
根据上式,f(i,j)可写作：
f(i,j)﹦ F-1[F(k,l)]﹦ F-1[G(k,l)·H(k,l)]
上式中 F-1表示二维离散傅立叶反变换 。 上式说明,空间域的卷积运算,也可用另一种方式来完成,即选将 g(m,n)及 h(m,n)用傅立叶变换变换成 G(k,l)及 H(k,l),然后将二者相乘,最后再把乘积作二维离散傅立叶反变换而得到卷积结果 。 用二维离散傅立叶变换完成的卷积计算,当 M,N较大时,会比空间域中直接完成卷积计算节省计算时间 。
因为,在空间域直接计算 f(p,q)其计算量为 O(MN·MN),而在空间频率域中运算时,共需两次二维离散傅立叶反变换,一次乘法运算与一次二维离散傅立叶反变换 。 二维离散傅立叶变换的快速算法完成一次变换的计算量是 O(MN(log2M﹢ log2N））,因此在空间频率域上完成卷积计算的总运算量是 O(MN(3(log2M﹢ log2N)﹢ 1）） 。 当 M,N较大时,其计算量比 O(MN·MN)小 。
(C)
1
4.2 离散余弦 (cos) 变换离散余弦变换也称为 DCT变换,一维离散余弦变换的定义由下式表示：
式中,u为频率变量,u=0,1,…,N-1。 f(x)是时域 N点序列,
x=0,1,…,N-1。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
2
一维离散余弦变换的反变换由下式表示：
二维离散余弦变换的定义由下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
3
其中,f(x,y)是空间域二维阵列函数,x,y=1,2,…,N-1，
F(u,v)是频域二维阵列函数 。 式中表示的阵列为 N× N。
二维离散余弦变换的反变换由下式表示：
如果采用矩阵形式表示,则一维离散余弦变换由下式表示：
[F(u)]=[A][f(x)]
[f(x)]=[A]T[F(u)]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
4
对 4× 4的变换矩阵 [A]为：
二维离散余弦变换矩阵形式表示为：
[F(u,v)]=[A][f(x,y)][A]T
[f(x,y)]=[A]T[F(u,v)][A]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
5
离散余弦变换可以按照定义直接计算,但实际上它是一种有快速算法的正交变换,下面我们推导其快速算法 。
由定义
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
6
如果把时域数据作如下拓展：
则 fe(x)的离散余弦变换可以写成下式：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
7
实际上是 2N点的离散傅立叶变换，所以，离散余弦变换可以通过把数据序列拓展为 2N，然后作离散傅立叶变换，得到的结果取其实部便可以得到离散余弦变换。
同理，在作反变换时，首先将 F(u)作如下拓展：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
8
那么，反变换也可以由下式表示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
9
4.3 Walsh－ Hadamard(沃尔什一哈达玛 ） 变换离散傅立叶变换和离散余弦变换在快速算法中都用到复数乘法,相对而言仍需要较多的计算时间 。 在某些应用领域,需要更为方便有效的变换方法,沃尔什一哈达玛变换就是其中的一种 。
Walsh－ Hadamard变换是一种矩阵元素值仅由 1或一 1
组成的正交变换矩阵,因此,用这种变换矩阵作变换处理时,仅用到加,减法运算,可大大提高变换处理速度 。
对于 Walsh－ Hadamard矩阵,有两种典型的序,即
Hadamard序的 Hh及 Walsh序的 Hw,对 4× 4的矩阵,Hh及 Hw
分别为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
10
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
11
Hadamard矩阵的各行中元素符号变换次数若用 k来表示,则相当于富里叶变换中频率含义的列率?可定义为：
Hh和 Hw的区别是 Hw是按列率排列的。
当已知低阶的 Hadamard矩阵 HN后，则可按：
将低阶 Hadamard矩阵扩展为高阶 Hadamard矩阵。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
12
4.3 Haar（ 哈尔 ） 变换
Haar变换是一种元素值仅取 1,-1,0或上述值乘以
21/2的变换矩阵,它是另一种计算效率高的变换 。 这种变换的特点是其变换结果由两部分组成,即由原图象全体象素值决定的区域与由原图象部分象素值所决定的区域两部分所构成 。
Haar函数是完备的,归一化的正交函数 。 在 [0,1]
区间内,harr(0,t)为 1,harr(1,t)在左半个区间内取值为 1,在右半个区间内取值为 -1。 它的其它函数值取 0和
± 1乘以 21/2幂,即 ± 21/2,± 2,± 2× 21/2,± 4等 。 具体定义如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
13
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
14
一般情况的 Haar函数定义为
4× 4的 Haar变换矩阵为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
15
Haar变换可以直接反应线和边,这是由于它的基函数有类似的这些特征 。 在各种变换中,如果一个信号或信号中的一部分可以近似地匹配上某一基函数,则在变换后,会产生一个对应那个基函数的较大的变换系数 。 由于基函数是正交的,则在这个信号对于其它的基函数将产生较小的系数 。 这样,Haar变换可以给出一些边的尺寸和位置信息 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
16
8× 8的 Haar变换矩阵为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
17
对于更大的 N也有相同的形式 。 由于矩阵中有许多常数和零值,Haar变换可以非常快的计算出来 。
用矩阵形式表示,则一维 Haar变换由下式表示：
[F(u)]=[Haar][f(x)]
[f(x)]=[ Haar]T[F(u)]
二维 Haar变换矩阵形式表示为：
[F(u,v)]=[Haar][f(x,y)][Haar]T
[f(x,y)]=[Haar]T[F(u,v)][Haar]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
18
4.4 斜 (slant) 变换在图像处理中用到的另一种正交变换是斜变换 。 斜向量和斜变换是 Enomoto 和 Shibata于 1971年提出来的 。 斜变换是一种由锯齿波构成的变换,其特点是能有效地表示图象中缓慢的灰度变化,,目前斜变换以成功应用于图像编码 。
斜变换的 2× 2矩阵表示如下：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
19
由此 2× 2矩阵，通过下面的方式产生 N× N矩阵：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
20
其中,I为阶数为 N/2-2的单位阵，且例如，当 N=4时,bN=1/51/2,aN=2/51/2,I=[0],则 4× 4的
slant变换矩阵 S为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
21
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
22
用矩阵形式表示,则一维 slant变换由下式表示：
[F(u)]=[S][f(x)]
[f(x)]=[S]T[F(u)]
二维 slant变换矩阵形式表示为：
[F(u,v)]=[S][f(x,y)][S]T
[f(x,y)]=[S]T[F(u,v)][S]
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
23
4.6 小波 (Wavelet)变换
4.6.1 傅立叶变换的局限性自从 1822年傅立叶发表,热传导解析理论,以来,傅立叶变换一直是信号处理领域中最完美,应用最广泛,效果最好的一种分析手段 。 傅立叶变换使用的是正弦曲线作为它的正交基函数,对于积分变换来说,这些函数都在两个方向无限扩展 。 离散傅立叶变换的基向量也在它们的整个域中非零 。 也就是说,它们并不是紧支集 。 对比之下,瞬态信号只在一个很短的区间内非零 。 与此相同的,图像中的许多重要特征 （ 例如边缘 ） 也是在空间位置中高度局部化的 。 这些成分并不类似于任何一个傅立叶基函数,这使得傅立叶变换以及在前面提到过的一些其它变换,在压缩和分析包含瞬态或局部化成分的信号和图像时,得不到最佳表示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
24
一个变换中的每个系数都是通过输入函数和其中一个基函数之间的内积确定的 。 在某些意义上,这个值表示输入函数和那个特定基函数之间的相似程度,
如果基函数是正交的 （ 或正交归一的 ）,那么任两个基函数间的内积为零,这表明它们完全不相似 。 所以如果信号或图像是由与一个或几个基函数相似的分量组成系数以外,其余系数都将很小 。
同样,逆变换可以看作是通过以变换系数为幅度权重的基函数加权和,来重构原始信号或图像的 。 所以如果信号或图像是由与一个或少量基函数相似的分量组成,那么只需对一些有较大幅度的项求和即可,
因此其它许多项都可以忽略,这 样 信号和图像就可用少量变换以 紧凑的方式表示 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
25
进而言之，如果信号和图像中感兴趣的分量与一个或少量基函数相似，那么这些分量将出对那些（仅仅是那些）基函数有大系数来体现。这样它们在变换中就“容易被找到”。
而且，如果一个不希望的分量（噪声）与一个或少量基函数相似，那么，它也会容易地被找到。它也因而容易地被去掉，
此时只需要简单地降低 (或置为零）相应的变换系数即可。归纳起来，用与信号或图像中所期望的成分相似的基函数对该信号或图像进行变换是有潜在价值的。还需指出的是瞬变分量是无法与傅立叶变换或其它波状变换的基函数相似的。尽管傅立叶变换能够用正弦函数之和表示任何分析函数 — 甚至是一个狭窄的瞬态信号。然而，这是通过错综复杂的安排，
通过相互抵消除去一些正弦波的方式，构造出在大部分区间都为零的函数而实现的。当然，这对于可逆变换来说是一个有效的方法，但它却使此函数的频谱上呈现一幅相当混乱的构成。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
26
实际中，对于一些常见的非平稳信号，如音乐信号；
语音信号；检测信号等，它们的频域特性都随时间而变化，因此也可称它们为时变信号，对这一类时变信号进行分析，通常需要提取某一时间段（或瞬间）的频域信息或某一频率段所对应的时间信息。因此，寻求一种具有一定的时间和频率分辨率的基函数来分析时变信号，
一直是信号处理界及数学界人士长期以来努力的目标。
4.6.2 波和小波 （ wavelet）
小波概念的真正出现应算于 1984年,法国地球物理学家
J.Morlet在分析地震数据时提出将地震波按一个确定函数的伸缩,平移系展开 。 随后,他与 A.Grossmann共同进行研究,发展了连续小波变换的几何体系 。 由此能将任意一个信号分解成对空间和尺度的贡献 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
27
1985年,Y.Meyer,A.Grossmann与 I.Daubechies共同进行研究，选取连续小波空间的一个离散子集，得到了一组离散的小波基（称为小波框架）；而且根据小波框架的离散子集的函数，恢复了连续小波函数的全空间。
在此之后,小波变换作为信号处理的一种手段,逐渐被越来越多领域的理论工作者和工程技术人员所重视和应用,并在许多应用中取得了显著的效果,同传统的处理方法相比,产生了质的飞跃,证明了小波技术作为一种调合分析方法,具有十分巨大的生命力和广阔的应用前景 。 如将小波用于地震信号的分析与处理； 将二进小波变换用于图像的边缘检测,图像压缩与重构；将连续小波变换用于涡流的研究；将小波变换用于噪声中的未知瞬态信号；将小波变换用于语音信号的分析,变换和综合 ;将正交小波变换用于算子及拟微分算子的化简；将小波变换的自适应性用于解微分方程；将小波变换用于电磁场领域的若干问题研究等,都取得了初步成果 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
28
下图说明了波与小波之间的差异 。 顶上的两条曲线是频率不同的余弦波,持续宽度相同 。 底下的两条是沿着轴向频率和位置都不相同的小波 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
29
根据时频域分析，一个信号的每个瞬态分量映射到时间
－频率平面上的位置对应于分量主要频率和发生的时间,下图是一个示例。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
30
在小波变换的系统理论发展起来以前，其基本思想已经在许多领域的应用中有所体现，只是还没有在数学上形成一个体系。例如，计算机视觉中的多分辨率分析等，金字塔式图像压缩编码概念，通信及语言处理中的子带编码，数字信号处理中的多采样率滤波器组,这些在工程中获得广泛应用的朴实方法，都可以用小波变换作为理论基础。
比如，图像中的物体是出现在不同大小尺度上的。例如，
一条边缘可以是由黑到白的一个突变，也可以是在一个较长距离上的渐变。对于图像表示或分析，采用多分辨率策略就是在设法利用这一概念。制图方法也可以用来说明这一策略。
地图通常以不同尺度来描得。一幅地图的尺度是领域实际大小与它在地图上的表示的比值。在较大尺寸上，例如在地球仪上，大陆和海洋等主要特征是可见的，而像城市街道这样的细节信息就在地图的分辨率之外了。而在较小的尺度上，
细节变得可见而较大的特征却不见了。因而,引到一个较远距离处的地点，就需要一套用不同尺度绘制的地图。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
31
金字塔算法也是发展小波理论的原始基础 。 设想从一幅 1024× 1024的数字图像生成 10幅尺度不同的附加图像 。
每一次通过连续平均 2× 2的像素块,并丢掉隔行隔列的像素,得到的将是 512× 512,256× 256等一直到 1× 1的图像 。
然后对每一幅图像都用某种 3× 3的边缘检测算子来执行边缘检测 。 在原始图像上则会得到小边缘,在 512× 512和
256× 256像素图像上能找到稍大的边缘,而在 16× 16和更小的图像上就只能找到非常大的边缘 。
小波变换正是沿着多分辨率这条线发展过来的 。 与时频域分析一样,－个信号用一个二 维空间表示,不过这里的纵轴是尺度而不是频率 。 变尺度是通过对基本小波伸缩和平移而构成一组基函数来实现的 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
32
4.6.3 连续小波变换
1,小波变换的定义设函数 f(t)∈L 2(R)( 平 方 可 积 函 数 空 间
L2(R)={x(t)∫ R|x(t)|2dt<∞}),则小波变的定义如下：
其中，积分核为 的函数族。 a＞ 0为尺度参数
（伸缩参数）,b为定位参数（平移参数），函数称为小波。
若 a＞ 1函数 ψ (t)具有伸展作用，若 a＜ 1函数 ψ (t)具有收缩作用。伸缩参数 a对 ψ (t)的影响如下图：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
33
随着参数 a的减小,ψ(t)的支撑区也随之变窄，反之亦然。
ψ(t)随伸缩参数 a和平移参数 b而变化如下图：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
34
图中小波函数为 。 当 a=2,b=15时,ψ a,b(t)= ψ 2,15(t)的波形从原点向右移至 t=15,且波形展宽。当 a=1/2,b=-10时,ψ a,b(t)= ψ 1/2,-10(t)的波形从原点向左移至 t=-10,且波形收缩。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
35
小波函数 ψ (t)的选择不是唯一的,也不是任意的 。 这里 ψ (t)是归一化的具有单位能量的解析函数,它应满足如下几个条件：
(1)定义域应是紧支撑的 （ Compact support）,也就是说在一个很小的区域之外,函数为零,即函数应有速降特性 。
（ 2） 平均值为零,即：
其高阶矩也为零。
该条件也叫小波的容许条件 （ Admissibility condition） 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
36
记则有
Cψ是有限值意味 Ψ(ω)连续可积。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
37
由上式可以看出,小波 ψ (t)在 t轴上取值有正有负才能保证上式积分为零 。 所以 ψ (t)应有振荡性 。
上述条件可以概括为,小波应是一个具有振荡性和迅速衰减的波 。
对于所有 f(t),ψ(t)∈ L2R,连续小波逆变换有下式给出：
小波变换是能量守恒的，即下式成立：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
38
4.6.4几种典型的一维小波
（ 1） Haar小波其波形如下图所示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
39
（ 2） Mexico Hat 小波
Mexico Hat 小波是 Gauss函数的二阶导数,即：
Mexico Hat 小波是实值小波，它的更普遍的形式由下式给出，即由 Gauss分布的 n阶导数给出：
其波形如下图所示：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
40
（ 3） Morlet 小波
Morlet 小波是最常用的复值小波,它可由下式给出：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
41
其波形如下图所示：
4.6.5 小波变换的性质
（ 1） 线性 设则
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
42
（ 2） 平移和伸缩的共变性连续小波变换在任何平移之下是共变的,即若是一对小波变换关系，则也是一对小波变换关系。
也是一对小波变换关系 。
除上面的性质,小波变换还有微分运算,局部正则,
能量守恒,空间 -尺度局部花等特性 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
43
4.6.6 离散小波变换离散小波可由下式定义：
相应的离散小波变换可由下式定义：
连续小波可以刻画函数 f(t)的性质和变化过程,用离散小波也可以刻画 f(t)。 通过展开把 f(t)写成级数的形式,就构成了 n维空间中函数逼近问题 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
44
离散小波变换的反变换为：
对于 f(t)也为离散函数,可以用采样的形式表示出来,
其离散小波变换为其反变换为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
45
4.6.7 二维 小波二维连续 小波变换的定义逆变换为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
46
二维离散 小波变换的定义：
逆变换为：
对于输入函数也为离散的情况，其变换可记为：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
47
其反变换可记为：
小波变换作为一种数学理论和方法在科学技术界引起了越来越多的关注和重视。在工程应用领域，特别是在信号处理、图像处理、模式识别、语音识别、量子物理、地震勘测、流体大学、电磁场,CT成像、机器视觉、机械故障诊断与监控、分形、数值计算等领域，它被认为是近年来在工具及方法上的重大突破，可以预料，在今后数年中，
它将成为科技工作者经常使用的又一锐利的数学工具。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
48
4.7卷积
4.7.1 卷积定义已知函数 g(t)和 x(t),定义两函数的卷积为：
卷积的一个重要用途是描述处理系统输入和输出的关系 。 对线性时不变系统的输出,可通过输入信号与一表征系统特性的函数 g(t)的卷积得到 。 表征函数叫作系统的冲激响应 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
49
卷积积分可简记为
y(t)=g(t)*x(t)
卷积运算具有几个有用的性质 。 首先,卷积具有交换性,
即
f(t)*g(t)=g(t)*f(t)
此外,卷积还满足对加法的分配律,即
f(t)*(g(t)+h(t))= f(t)*g(t)+ f(t)*h(t)
卷积还满足结合律,这意味着
f(t)*(g(t)*h(t))= (f(t)*g(t))*h(t)
对于求导有以下性质
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
50
4.7.2一维离散卷积对于离散序列,其卷积可用与连续函数相类似的方法求得 。 此时自变量变为下标,而积则由求和代替 。 因此,对于两个长度分别为 m和 n的序列 f(i)和 g(i）,其对应卷积表示为：
上式给出一个长度为 N=m+n-1的输出序列 。
尽管离散卷积和连续卷积是相当不同的运算,但它们具有许多共同的性质 。 尤其值得庆幸的是我们可在数字图像上进行的离散卷积,与连续卷积几乎具有对应的性质,而许多在图像数字化之前和变回连续形式之后对图像施加的影响,都可用连续卷积来描述 。
这一优点在图像恢复中得到充分利用,图像恢复的目的是扭转业已加在图像上的退化影响 。
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
51
4.7.3 二维卷积二元连续函数的卷积与一维情况相类似 。 用 x和 y表示两个独立的变量 。 二维卷积表达式是：
4.7.4 二维离散卷积
4.7.5用二维离散傅立叶变换完成卷积计算若 M× N的图象 g(m,n)与 h(m,n)卷积得到 f(p,q)即：
2009年 7月 24日 数字图象处理演示稿 纪玉波制作
(C)
52
则根据卷积定理,令 G,H,F分别表示 g,h,f的二维离散傅立叶变换,则下列关系成立,即：
F(k,l)﹦ G(k,l)·H(k,l)
根据上式,f(i,j)可写作：
f(i,j)﹦ F-1[F(k,l)]﹦ F-1[G(k,l)·H(k,l)]
上式中 F-1表示二维离散傅立叶反变换 。 上式说明,空间域的卷积运算,也可用另一种方式来完成,即选将 g(m,n)及 h(m,n)用傅立叶变换变换成 G(k,l)及 H(k,l),然后将二者相乘,最后再把乘积作二维离散傅立叶反变换而得到卷积结果 。 用二维离散傅立叶变换完成的卷积计算,当 M,N较大时,会比空间域中直接完成卷积计算节省计算时间 。
因为,在空间域直接计算 f(p,q)其计算量为 O(MN·MN),而在空间频率域中运算时,共需两次二维离散傅立叶反变换,一次乘法运算与一次二维离散傅立叶反变换 。 二维离散傅立叶变换的快速算法完成一次变换的计算量是 O(MN(log2M﹢ log2N））,因此在空间频率域上完成卷积计算的总运算量是 O(MN(3(log2M﹢ log2N)﹢ 1）） 。 当 M,N较大时,其计算量比 O(MN·MN)小 。
