《正交变换2第二组》由会员分享,可在线阅读,更多相关《正交变换2第二组(61页珍藏版)》请在金锄头文库上搜索。
1、 主要内容 第一章第一章 沃尔什变换沃尔什变换 第二章第二章 小波变换小波变换第一章第一章 沃尔什变换沃尔什变换1.1沃尔什函数沃尔什函数1.2沃尔什变换沃尔什变换1.3算法算法1.4应用应用1.1 沃尔什函数函数值仅取“+1”、“-1”两值的非正弦型的标准正交完备函数系。任何一个时间函数完全可以用多个沃尔什函数来表示。只定义在有限时间T内,具有两个自变量,时 间变量t和序数n。函数通常表示为Wal(n,t)。 三种定义方法:按照沃尔什排列来定义(按列率排序) ;按照佩利排列来定义(按自然排序) ;按照哈达玛排列来定义 。拉德梅克函数集是一个不完备的正交函数集,由它可以构成完备的沃尔什函数。把
2、一个正弦函数进行无限限幅就可以得到拉得梅克函数。拉得梅克函数包括n和t两个自变量,用R(n,t)表示。它可以用下式来表示: 当x=0时,sgn(x)无定义。拉德梅克函数拉德梅克函数按沃尔什排列定义的沃尔什函数是按列率排列的。通常把正交区间内波形变号次数的二分之一称为列率(按照函数的序数由正交区间内过零点平均数来定义的)。函数的列率由下式决定:按沃尔什排列的沃尔什函数可由拉德梅克函数构成,表达式如下:g(i)是i的格雷码,g(i)k 是此格雷码的第K位数字,m为正整数。(1)按沃尔什排列的沃尔什函数按沃尔什排列的沃尔什函数 按佩利排列的沃尔什函数也可由拉德梅克函数构成,定义是如下: ik是将函数
3、序号写成自然二进制码的第K位数字, 即 。(2)按佩利排列的沃尔什函数)按佩利排列的沃尔什函数按哈达玛排列的沃尔什函数也可由拉德梅克函数构成,解析式如下:式中 是把i 的自然二进码反写后的第k位数字,并且 也就是 反写后:(3)按哈达玛排列的沃尔什函数按哈达玛排列的沃尔什函数由于哈达玛排序的沃尔什函数是由2n(n=0,1, )阶哈达玛矩阵(Hadamard Matrix)得到的,而哈达玛矩阵的最大优点在于它具有简单的递推关系,即高阶矩阵可用两个低阶矩阵的克罗内克积求得,因此我们重点介绍哈达玛排列定义的沃尔什变换。2n阶哈达玛矩阵:递推关系:三种定义下的沃尔什函数,尽管它们的排列顺序各不相同,但
4、三种排序方法得到的沃尔什函数有一定的关系。沃尔什函数三种定义之间的关系:WALp(i,t)WALw(i,t)WALH(i,t)比特倒置二进码写,格雷码读格雷码写,二进码读比特倒置 格雷码写,倒置,二进码读 二进码写,倒置,格雷码读图1-1 沃尔什函数关系图以沃尔什函数为基础,将一个函数变换为取值为+1或-1为基向量构成的级数。与傅里叶变换相比,沃尔什变换的主要优点在于存储空间少和运算速度快,这一点对于图像处理来说是至关重要的。u 一维离散沃尔什变换u 离散沃尔什-哈达玛变换u 二维离散沃尔什变换u 快速沃尔什变换(FWHT)1.2 沃尔什变换一维离散沃尔什变换定义:一维离散沃尔什逆变换定义:1
5、.2.1一维离散沃尔什变换一维离散沃尔什变换 式中, 代表N阶沃尔什矩阵。 是沃尔什变换系数序列; 是时间序列。沃尔什变换矩阵式沃尔什变换矩阵式若将 用哈达玛矩阵表示,并将变换表达式写成矩阵形式: 式中, 为N阶哈达玛矩阵。1.2.2 离散沃尔什离散沃尔什-哈达玛变换哈达玛变换由哈达玛矩阵的特点可知,沃尔什-哈达玛变换的本质上是将离散序列f(x)的各项值的符号按一定规律改变后,进行加减运算, 因此,它比采用复数运算的DFT和采用余弦运算的DCT要简单得多。将一维WHT的定义推广到二维WHT。二维沃尔什-哈达玛变换的指数式如下:二维沃尔什-哈达玛变换的的逆变换式为:式中 代表图像的像素, 是该像
6、素在空间中的位置坐标; 代表变换系数; 为正整数; 是x,u的二进制码的第r位数字, 为正整数; 是y,v的二进制码的第s位数字 。1.2.3 二维离散沃尔什变换二维离散沃尔什变换二维沃尔什-哈达玛变换的矩阵式定义如下:式中, 和 分别为 和 阶哈达玛矩阵类似于FFT,WHT也有快速算法FWHT。利用快速算法,完成一次变换只需 次加减法,预算速度可大大提高。快速沃尔什变换可由沃尔什-哈达玛变换修改得到,所以下面着重讨论一下沃尔什-哈达玛快速变换。由离散沃尔什-哈达玛变换的定义可知: 式中, ,P为正整数。 1.2.4 快速沃尔什变换(FWHT)以8阶沃尔什-哈达玛变换为例,讨论分解过程及快速算
7、法:其中, 均为酉阵。对于一般情况, 则矩阵 可以分解成P个矩阵 之乘积,即 由上面的分解有 令 则 因为 而 是对称矩阵,则 由此可得到两种形式的蝶形运算流程图。所以任意2r阶快速沃尔什-哈达玛变换的碟式流程图不难用上述方法引伸。法一:二维沃尔什-哈达玛变换可以用一维沃尔什-哈达玛变换来计算,其步骤如下:(1)以 ,对 中个列中的每一列做变换,得到 ;(2)以 ,对 中行中每一行做变换,即可得到二维变换系数 。法二:将二维沃尔什-哈达玛变换当做一维来计算。这种方法是将数据矩阵的各列依次顺序排列,这样就形成由 个元素的列矩阵。然后再按一维沃尔什-哈达玛变换方法来计算。 下面用事例说明一下两种计
8、算方法。1.3 二维沃尔什二维沃尔什-哈达玛变换哈达玛变换的计算的计算例:设数据矩阵如下 , 求 的二维沃尔什-哈达玛变换。法一:首先对 的每一列做变换: 第一列 第二列 第三列 第四列 所以 对 每一行做变换第一行 第二行最后得到二维系数变换矩阵 法二:将 改写成矩阵Y,即 对Y做以下变换 然后重排一下 显然,与第一种算法的到的结果一致。下图是一幅数字图像及对其进行二维WHT变换的结果。 图1-2 二维WHT结果 (a)原图像;(b)WHT结果 从以上例子可看出,二维WHT具有能量集中的特性,而且原始数据中数字越是均匀分布,经变换后的数据越集中于矩阵的边角上。因此,二维WHT可用于压缩图像信
9、息。1.4 应用应用综上所述,WHT是将一个函数变换成取值为1或1的基本函数构成的级数,用它来逼近数字脉冲信号时要比FFT有利。同时, WHT只需要进行实数运算,存储量比FFT要少得多, 运算速度也快得多。因此,WHT在图像传输、 通信技术和数据压缩中被广泛使用。 小波变换小波变换第二章第二章 小波变换小波变换2.2 离散小波变换离散小波变换2.4 应用应用2.3 算法算法2.1 连续小波变换连续小波变换小波变换小波变换背景知识背景知识傅立叶变换:提供了频率域的信息,但丢失了时间域的局部化信息。小波变换:是对一个函数在时间和频率上进行局部化分析的一种数学变换。 通过平移母小波(mother w
10、avelet)获得信号的时间信息。 通过缩放母小波的宽度(或称尺度)获得信号的频率特性。对母小波的平移和缩放操作是为计算小波的系数,这些系数代表局部信号和小波之间的相关程度。从而达到变换目的:获得时间和频率域之间的相互关系。小波变换小波变换2.1 连续小波变换连续小波变换连续小波变换(Continuous Wavelet Transform, CWT)用下式表示: 上式表示小波变换是信号f(t)与被缩放和平移的小波函数()之积在信号存在的整个期间里求和的结果。 CWT的变换结果是许多小波系数C,这些系数是缩放因子(scale)和平移(positon)的函数。小波变换小波变换2.1.1 小波小波
11、小波 的选择既不是唯一的也不是任意的:这里 是归一化地具有单位能量的解析函数,他应满足以下条件:(1)具有有限的持续时间和突变的频率和振幅。(2)在有限的时间范围内,它的平均值等于零,即 (高阶矩也为0). 小波变换小波变换图图2-1 2-1 (a a)正弦波曲线)正弦波曲线 (b)小波曲线)小波曲线 上图表示了正弦波和小波的区别,由此可以看出,正弦波从负无穷一直延续到正无穷,正弦波是平滑而且是可预测的,而小波是一类在有限区间内快速衰减到0的函数,其平均值为0,小波趋于不规则、不对称。 综上,可以概括为:小波应是具有震荡性和迅速衰减的波。小波变换小波变换 基本小波函数()的缩放和平移操作含义如
12、下: (1) 缩放。简单地讲, 缩放就是压缩或伸展基本小波, 缩放系数越小, 则小波越窄,如图2-2所示。(2)平移。简单地讲,平移就是小波的延迟或超前。在数学上, 函数f(t)延迟k的表达式为f(t-k),如图2-3所示。图2-3 小波的平移操作(a) 小波函数(t); (b) 位移后的小波函数(t-k) 图2-2 小波的缩放操作小波变换小波变换例:设函数 具有有限能量,即 , 则小波变换的定义如下 : 积分核为 。a为尺度参数,b为位置参数, 为小波。若 ,函数 具有伸展作用; ,函数 具有收缩作用。小波随伸缩参数a,平移参数b而变化。 随参数a的减小, 的支撑区也就变大(支撑区或支集就是
13、函数定义域的闭子集),而 频谱随之向高频端展宽,反之亦然。这就有可能实现窗口大小自适应变化,当信号频率增高时,时窗宽度变窄,而频窗宽度增大,有利于提高时频分辨率,反之也一样。小波变换小波变换 小波的缩放因子与信号频率之间的关系是:缩放因子scale越小,表示小波越窄,度量的是信号的细节变化,表示信号频率越高;缩放因子scale越大, 表示小波越宽,度量的是信号的粗糙程度,表示信号频率越低。小波变换小波变换2.1.2 二维连续小波变换二维连续小波变换定义:逆变换为逆变换为:小波变换小波变换2.1.3 小波变换小波变换傅立叶分析 用一系列不同频率的正弦波表示一个信号。 一系列不同频率的正弦波是傅立
14、叶变换的基函数。小波变换 用母小波通过移位和缩放后得到的一系列小波表示一个信号。 一系列小波可用作表示一些函数的基函数。凡能用傅立叶分析的函数都可用小波分析 小波变换可理解为用经过缩放和平移的一系列函数代替傅立叶变换用的正弦波。用不规则的小波分析变化激烈的信号比用平滑的正弦波更有效,或者说对信号的基本特性描述得更好。小波变换小波变换2.2 离散小波变换(离散小波变换(DWT) 在连续小波变换中,伸缩参数a和平移参数b连续取值,在每个可能的缩放因子和平移参数下计算小波系数,其计算量相当大, 将产生惊人的数据量,而且有许多数据是无用的。实际应用中离散小波变换更适合于计算机处理。 离散小波: 离散小
15、波变换(Discrete Wavelet Transform,DWT):小波变换小波变换2.2.1 双尺度小波变换(双尺度小波变换(Dyadic Wavelet Transform) 缩放因子和平移参数都选择为2j(j0且为整数)的倍数, 使用这样的缩放因子和平移参数的小波变换称为双尺度小波变换,它是离散小波变换的一种形式。通常离散小波变换就是指双尺度小波变换。小波变换小波变换2.2.2 快速小波变换快速小波变换 ( Mallat算法算法 ) 执行离散小波变换的有效方法是使用滤波器, 该方法是Mallat于1988年提出的,称为Mallat算法。 Mallat算法本质上不需要知道尺度函数和小波
16、函数的具体结构,只由系数就可以实现的分解与重构,因此称为快速小波变换。小波变换小波变换 用滤波器执行离散小波变换的概念如图2-4所示。S表示原始的输入信号, 通过两个互补的滤波器组, 其中一个滤波器为低通滤波器,通过该滤波器可得到信号的近似值A(Approximations),另一个为高通滤波器, 通过该滤波器可得到信号的细节值D(Detail)。图2-4 小波分解示意图2.2.3 小波分解小波分解小波变换小波变换 对于一个信号,如采用图2-4所示的方法,理论上产生的数据量将是原始数据的两倍。于是,根据奈奎斯特(Nyquist)采样定理, 可用下采样的方法来减少数据量,即在每个通道内(高通和低
17、通通道)每两个样本数据取一个, 便可得到离散小波变换的系数(Coefficient), 分别用cA和cD表示,如图2-5所示。图中 表示下采样。图 2-5 小波分解下采样示意图小波变换小波变换2.2.4 小波重构小波重构定义:利用信号的小波分解的系数还原出原始信号,这一过程称为小波重构(Wavelet Reconstruction)或叫做小波合成(Wavelet Synthesis)。这一合成过程的数学运算叫做逆离散小波变换(Inverse Discrete Wavelet Transform, IDWT)。图2-6 小波重构算法示意图小波变换小波变换 1)重构近似信号与细节信号 由上图可知,
18、由小波分解的近似系数和细节系数可以重构出原始信号。同样,可由近似系数和细节系数分别重构出信号的近似值或细节值,这时只要近似系数或细节系数置为零即可。 图2-7是对第一层近似信号或细节信号进行重构的示意图。图2-7 重构近似和细节信号示意(a) 重构近似信号; (b) 重构细节信号 小波变换小波变换2)多层重构 在图2-6中,重构出信号的近似值A1与细节值D1之后,则原信号可用A1D1S重构出来。对应于信号的多层小波分解,小波的多层重构如图2-8,可见重构过程为:A3D3A2;A2D2A1;A1+D1S。图2-8 多层小波重构示意图小波变换小波变换 2.2.5 二维离散小波变换二维离散小波变换二
19、维离散小波变换是一维离散小波变换的推广, 其实质上是将二维信号在不同尺度上的分解, 得到原始信号的近似值和细节值。 由于信号是二维的,因此分解也是二维的。分解的结果为: 近似分量cA、 水平细节分量cH、 垂直细节分量cV和对角细节分量cD。 同样也可以利用二维小波分解的结果在不同尺度上重构信号。二维小波分解和重构过程如图2-9所示。小波变换小波变换图2-9 二维小波分解和重构过程示意图(a) 二维DWT; (b) 二维IDWT 小波变换小波变换2.3 Mallat算法算法尺度函数尺度函数由尺度函数构造小波是小波变换的必经之路。尺度函数 应满足下列条件: 它是一个平均函数。 即尺度函数是范数为
20、1的规范化函数。 即尺度函数对所有的小波是正交的。 即尺度函数对于平移是正交的。 即某一尺度上的尺度函数可以由下一尺度的线性组合得到,hn是尺度系数。尺度函数与小波是有关联的。 式中, 是归一化因子, 是有尺度系数 导出的系数。这说明小波可以由尺度函数的伸缩和平移的线性组合获得,这就是构造小波正交基的途径。小波变换小波变换(2)由离散小波的定义,如果把t也离散化,并选择 ,则可得到二进制小波: MallatMallat算法描述算法描述设设V0 0 是给定的多分辨率尺度空间,尺度因子是给定的多分辨率尺度空间,尺度因子m=0,相应的尺度函数为,相应的尺度函数为:小波变换小波变换小波函数为:若若,则
21、正交小波分解为:,则正交小波分解为:当m=1时,则令当尺度因子m=1转到m=2时,相应于小波变换小波变换需补充细节信息d1,则 类似的则 。因此因此 可得:可得: 为建立为建立 和和 的系数之间的关系,代换角标的系数之间的关系,代换角标n n用用k代之,代之,j用用n代之则有:代之则有:小波变换小波变换由此可得:由此推广至系数表达的一般式:该式就是由小波系数 和 重构函数f(t)的正交展开式系数 的公式。函数f(t)的小波展开系数 和 用双尺度差分公式表示可按下式计算:小波变换小波变换同理:同理:小波变换小波变换计算步骤可按下列方法进行:由 计算 和 ,再由 计算 和 ,直至尺度到m为止。上述
22、的分析从信息处理的观点来看,可认为是一种滤波运算。 Mallat算法本质上不需要知道尺度函数和小波函数的具体结构,只由系数就可以实现的分解与重构,因此称为快速小波变换。小波变换小波变换1. 用小波变换进行图像分解 使用小波变换完成图像分解的方法很多。例如,均匀分解(Uniform decomposition)、非均匀分解(Non-uniform decomposition)、八带分解(Octave-band decomposition)、小波包分解(Wavelet-packer decomposition)等。 其中八带分解是使用最广的一种分解方法,这种分解方法把低频部分分解成比较窄的频带,而
23、对每一级分解得到的高频部分不再进一步进行分解。图2-10为八带分解示意图。2.4 应用应用小波变换小波变换图2-10八带分解示意图(a) 一次二维DWT; (b) 两次二维DWT; (c) Woman二级分解图 每一级分解都把图像分解为四个频带:水平(HL)、垂直(LH)、对角(HH)和低频(LL),其中低频(LL)部分还可以进行下一级的分解,从而构成了小波的塔式分解。一幅图像经过分解之后,图像的主要能量主要集中于低频部分,这也是视觉重要部分:而图像的高频部分即图像的细节部分所含能量较少,分布在HL, LH, HH三个子图中,主要包含了原图的边缘和纹理部分信息。小波变换小波变换2.用小波变换进
24、行图像处理 对静态二维数字图像,可先对其进行若干次二维DWT变换, 将图像信息分解为高频成分H、V和D和低频成分A。对低频部分A,由于它对压缩的结果影响很大,因此可采用无损编码方法, 如Huffman、 DPCM等;对H、V和D部分,可对不同的层次采用不同策略的向量量化编码方法,这样便可大大减少数据量,而图像的解码过程刚好相反。整个编码、解码流程如图2-11所示。 小波变换小波变换图2-11图像压缩编码、 解码流程 小波变换应用到数字图像处理中的基本思想就是把数字图像进行多分辨率分解,分解成不同空间、不同频率的子图像,然后再根据各个子图像的特点有针对性的进行处理。对小波系数处理是小波变换用于子图像处理的核心。小波变换小波变换精品课件精品课件!小波变换小波变换精品课件精品课件!Thank you!