离散小波变换

数值分析泛函分析领域中,离散小波变换(Discrete Wavelet Transform,DWT)是小波被离散采样的小波变换。与其他小波变换一样,它与傅里叶变换相比的一个关键优势是时间分辨率:它既能捕获频率信息,又能捕获位置(时间上的位置)信息。

第一个离散小波变换由匈牙利数学家哈尔发明,离散小波变换顾名思义就是离散的输入以及离散的输出,但是这里并没有一个简单而明确的公式来表示输入及输出的关系,只能以阶层式架构来表示。

定义

  • 首先我们定义一些需要用到的信号及滤波器。
  • x[n]:离散的输入信号,长度为N。
  •  :low pass filter低通滤波器,可以将输入信号的高频部分滤掉而输出低频部分。
  •  :high pass filter高通滤波器,与低通滤波器相反,滤掉低频部分而输出高频部分。
  •   Q:downsampling filter降采样滤波器,如果以x[n]作为输入,则输出y[n]=x[Qn]。此处举例Q=2。
举例说明: 
清楚规定以上符号之后,便可以利用阶层架构来介绍如何将一个离散信号作离散小波变换:
 
架构中的第1层(1st stage)
 
 
架构中的第2层(2nd stage)
 
 
可继续延伸

 

 
 

架构中的第 层(  stage)

 
 
注意:若输入信号 的长度是N,则第 层中的  的长度为 

二维离散小波变换

 
此时的输入信号变成 ,而变换过程变得更复杂,说明如下:
首先对n方向作高通、低通以及降频的处理
 
 
接着对  延著m方向作高低通及降频动作
 
 
 
 
经过(1)(2)两个步骤才算完成2-D DWT的一个stage。


实际范例

以下根据上述2-D DWT的步骤,对一张影像作二维离散小波变换(2D Discrete Wavelet Transform)

原始影像 
2D DWT的结果 
  

复杂度(Complexity)

在讨论复杂度之前,先做一些定义,当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)

使用离散小波变换,将信号个别通过一个低通滤波器和一个高通滤波器,得到信号的高低频成分,而在重建(Reconstruction英语Reconstruction_filter)原始信号的过程,也就是离散小波的逆变换(Inverse Discrete Wavelet Transform. IDWT),直观而言,我们仅是需要将离散小波变换做重建滤波即可得到原始输入信号,以下将推导重建滤波器,也就是IDWT高低通滤波器的构成要件,以及如何来重建原始信号。

重建过程如下:

使用Z变换:

 
  • DWT低通滤波器   的Z变换为   ,DWT高通滤波器 的Z变换为 
  • 信号 通过滤波器   后,Z变换为    ,信号 通过滤波器   后,Z变换为   
  • 降低采样数(downsample)2倍后,
 
 
  • 升频(interpolation)2倍后,再通过IDWT的低通重建滤波器  
 
 

若要完整重建,则 

條件1: 
條件2: 

因此,在设计高低通重建滤波器时,需要考虑上述条件,写成矩阵形式如下:

 
其中  

离散小波变换(DWT)设计

四大条件:

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。

其他应用

压缩、去除噪声:使用低通滤波器,将小波变换的高频滤掉,即保留 而将其他部分舍弃。

  • 边缘侦测:使用高通滤波器,将小波的低频滤掉,即保留  而舍弃其他部分。
  • R语言小波分析wavelet页面存档备份,存于互联网档案馆
  • 作为 JPEG2000 的内部架构
  • 模式辨认:由于可以利用低频的部分得到原图的缩略版,加上模式通常为整体的特性,借由在缩略图上进行工作,小波变换可以有效减少寻找模式与比对模式的运算时间
  • 滤波器设计:小波变换保留部分时间信息,可以据此信息加上信号的强度信息,保留特定时点的信息而同时去除噪声

同时参阅

参考