在数值分析和泛函分析领域中,离散小波变换(Discrete Wavelet Transform,DWT)是小波被离散采样的小波变换。与其他小波变换一样,它与傅里叶变换相比的一个关键优势是时间分辨率:它既能捕获频率信息,又能捕获位置(时间上的位置)信息。
第一个离散小波变换由匈牙利数学家哈尔发明,离散小波变换顾名思义就是离散的输入以及离散的输出,但是这里并没有一个简单而明确的公式来表示输入及输出的关系,只能以阶层式架构来表示。
- 首先我们定义一些需要用到的信号及滤波器。
- x[n]:离散的输入信号,长度为N。
:低通滤波器(low pass filter),可以将输入信号的高频部分滤掉而输出低频部分。
:高通滤波器(high pass filter),与低通滤波器相反,滤掉低频部分而输出高频部分。
Q:降采样滤波器(downsampling filter),如果以x[n]作为输入,则输出y[n]=x[Qn]。此处举例Q=2。
- 举例说明:
![](//upload.wikimedia.org/wikipedia/commons/thumb/f/fc/DiscreteWaveletTrans1.jpg/400px-DiscreteWaveletTrans1.jpg)
- 清楚规定以上符号之后,便可以利用阶层架构来介绍如何将一个离散信号作离散小波变换:
![](//upload.wikimedia.org/wikipedia/commons/thumb/7/7f/DWT2ndLayer.jpg/500px-DWT2ndLayer.jpg)
- 架构中的第1层(1st stage)
![{\displaystyle x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e89171201a089a787ca8eecf3cfcc0a997ca2687)
![{\displaystyle x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f25f3aaaa0a147dc3d27be4ffa8ec69966f512b)
- 架构中的第2层(2nd stage)
![{\displaystyle x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/778ad7dd66c5fb41a730549fa7a229eb16187cbf)
![{\displaystyle x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a655d7ed52b22f9cdddc4212e23b84da4fd260f1)
- 可继续延伸
![](//upload.wikimedia.org/wikipedia/commons/2/22/Wavelets_-_Filter_Bank.png)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
架构中的第
层(
stage)
![{\displaystyle x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b3237f86646ab171917e1d6fbab78eb53ad7496)
![{\displaystyle x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36145d18b7c0b1f46f34d3321d019964fb06b9c6)
注意:若输入信号 的长度是N,则第 层中的 及 的长度为![{\displaystyle {\frac {N}{2^{\alpha }}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65191e4a5b3b9ef4a310402007c00ffd311d994d) |
|
![](//upload.wikimedia.org/wikipedia/commons/thumb/e/ea/2D_DWT.jpg/500px-2D_DWT.jpg)
- 此时的输入信号变成
,而变换过程变得更复杂,说明如下:
- 首先对n方向作高通、低通以及降频的处理
![{\displaystyle v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3bb581d19be3dc84b6f66476669af51bb565f115)
- 接着对
与
延著m方向作高低通及降频动作
![{\displaystyle x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5699b1611ae488b196dfeb4b12a5ffbe17a7b756)
![{\displaystyle x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1bc0b122f88e2ec5cd699913f5291c491ac9a9f)
![{\displaystyle x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6657c6da1e42df215ace930f89aae0da4fa6b5f6)
- 经过(1)(2)两个步骤才算完成2-D DWT的一个stage。
以下根据上述2-D DWT的步骤,对一张影像作二维离散小波变换(2D Discrete Wavelet Transform)
- 原始影像
![](//upload.wikimedia.org/wikipedia/commons/thumb/0/0b/2D_DWT_Original.png/300px-2D_DWT_Original.png)
- 2D DWT的结果
![](//upload.wikimedia.org/wikipedia/commons/thumb/1/1f/2D_DWT_pre-process.png/300px-2D_DWT_pre-process.png)
![{\displaystyle \Rightarrow }](https://wikimedia.org/api/rest_v1/media/math/render/svg/469b737d167b9b28a74e27c7f5e35b5ea9256100)
![](//upload.wikimedia.org/wikipedia/commons/thumb/b/ba/2D_DWT_process.png/300px-2D_DWT_process.png)
在讨论复杂度之前,先做一些定义,当x[n]*y[n]时,x[n]之长度为N,y[n]之长度为L:
其中,
为(N+L-1)点离散傅里叶逆变换(inverse discrete Fourier transform)
为(N+L-1)点离散傅里叶变换(discrete Fourier transform)
(1)一维离散小波变换之复杂度(没有分段卷积(sectioned convolution)):
(2)当 N >>> L 时,使用 “分段卷积(sectioned convolution)”的技巧:
将x[n]切成很多段,每段长度为
,总共会有
段,其中
。
则
复杂度为:
在这里要注意的是,当N>>L时,一维离散小波变换之复杂度是呈线性的(随N),
。
(3)多层(Multiple stages )的情况下:
1.若
不再分解时:
2.若
也细分时:
(4)二维离散小波变换之复杂度(没有分段卷积(sectioned convolution)):
上式中,第一部分需要M个一维离散小波变换并且每个一维离散小波变换的输入有N个点;第二部分需要N+L-1个一维离散小波变换并且每个一维离散小波变换的输入有M个点。
(5)二维离散小波变换之复杂度,使用 “分段卷积(sectioned convolution)”的技巧:
假设原始尺寸为
,则每一小部分的尺寸为
所以若是使用分段卷积,则二维离散小波变换之复杂度是呈线性的(随MN),
。
(6)多层(Multiple stages )与二维的情况下:
首先x[m,n]的尺寸为
,
1.若
不细分,只细分
时,总复杂度为:
2.若
也细分时,总复杂度为:
使用离散小波变换,将信号个别通过一个低通滤波器和一个高通滤波器,得到信号的高低频成分,而在重建(Reconstruction)原始信号的过程,也就是离散小波的逆变换(Inverse Discrete Wavelet Transform. IDWT),直观而言,我们仅是需要将离散小波变换做重建滤波即可得到原始输入信号,以下将推导重建滤波器,也就是IDWT高低通滤波器的构成要件,以及如何来重建原始信号。
使用Z变换:
- DWT低通滤波器
的Z变换为
,DWT高通滤波器
的Z变换为![{\displaystyle H(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3c5a542a7eaa29c58fb64cbeb5133ce98ac4f4b)
- 信号
通过滤波器
后,Z变换为 ![{\displaystyle X(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/727fb275ca22820bf91e526120c4939a1d38a2b0)
,信号
通过滤波器
后,Z变换为 ![{\displaystyle X(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/727fb275ca22820bf91e526120c4939a1d38a2b0)
![{\displaystyle H(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b3c5a542a7eaa29c58fb64cbeb5133ce98ac4f4b)
- 升频(interpolation)2倍后,再通过IDWT的低通重建滤波器
,
若要完整重建,则
條件1:
條件2:
因此,在设计高低通重建滤波器时,需要考虑上述条件,写成矩阵形式如下:
其中
1.DWT通滤波器
,
必须要是有限长度。
2.满足
是高通滤波器(high pass filter),
是低通滤波器(low pass filter)。
3.满足完整重建要条件,
,其中
4.若
,
为有限长度,则
,且
为奇数。
*为什么k是奇数?
假设k为偶数,
z=-1
z=1
代回
显然出现矛盾。
所以k必须为奇数。
1.正交镜象滤波器(Quadrature Mirror Filter,QMF)
![{\displaystyle H(z)=G(-z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/573ec21ee00bc1bc823e1c7de006ada26d23e55e)
![{\displaystyle G_{1}(z)=G(z)z^{-k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/914554a53d5fbe289d37d1ad9427afdda39fe593)
![{\displaystyle H_{1}(z)=-G(-z)z^{-k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d86c1a0e9ed0bd582b2de61a3fcf7a03652fbc32)
,且
为奇数。
2.单位正交小波(Orthonormal Wavelet)
![{\displaystyle G(z)=G_{1}(z^{-1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/802f25110527040f709c13b953a687c85808711a)
![{\displaystyle H(z)=-z^{k}G_{1}(-z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1bf8e565be68a59f8c2cf5e87e565ec8a13e1e2a)
![{\displaystyle H_{1}(z)=-z^{k}G_{1}(-z^{-1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6591e44a91448c947859ed2a988914202b4d45a4)
,且
为奇数。
多数小波属于单位正交小波。
压缩、去除噪声:使用低通滤波器,将小波变换的高频滤掉,即保留
而将其他部分舍弃。
- 边缘侦测:使用高通滤波器,将小波的低频滤掉,即保留
或
而舍弃其他部分。
- R语言小波分析wavelet (页面存档备份,存于互联网档案馆)
- 作为 JPEG2000 的内部架构
- 模式辨认:由于可以利用低频的部分得到原图的缩略版,加上模式通常为整体的特性,借由在缩略图上进行工作,小波变换可以有效减少寻找模式与比对模式的运算时间
- 滤波器设计:小波变换保留部分时间信息,可以据此信息加上信号的强度信息,保留特定时点的信息而同时去除噪声