在讨论复杂度之前,先做一些定义,当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变换为
- 信号 通过滤波器 后,Z变换为 ,信号 通过滤波器 后,Z变换为
- 升频(interpolation)2倍后,再通过IDWT的低通重建滤波器 ,
若要完整重建,则
條件1:
條件2:
因此,在设计高低通重建滤波器时,需要考虑上述条件,写成矩阵形式如下:
其中
四大条件:
1.DWT通滤波器 , 必须要是有限长度。
2.满足 是高通滤波器(high pass filter), 是低通滤波器(low pass filter)。
3.满足完整重建要条件, ,其中
4.若 , 为有限长度,则 ,且 为奇数。
>第4点较难达成,是DWT设计的核心
*为什么k是奇数?
假设k=even,
z=-1
z=1
代回
显然出现矛盾。
所以k必须为odd。
以下介绍两种完美重建的DWT滤波器:
1.Quadrature Mirror Filter(QMF)
-
-
-
,且 为奇数。
2.Orthonormal Wavelet
-
-
-
,且 为奇数。
多数的wavelet属于orthonormal wavelet。