离散小波变换

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

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

定义

• 首先我们定义一些需要用到的信号及滤波器。
• x[n]：离散的输入信号，长度为N。
• $g[n]$：low pass filter低通滤波器，可以将输入信号的高频部分滤掉而输出低频部分。
• $h[n]$：high pass filter高通滤波器，与低通滤波器相反，滤掉低频部分而输出高频部分。
• $\downarrow$ Q：downsampling filter降采样滤波器，如果以x[n]作为输入，则输出y[n]=x[Qn]。此处举例Q=2。

举例说明:

清楚规定以上符号之后，便可以利用阶层架构来介绍如何将一个离散信号作离散小波变换：

架构中的第1层(1st stage)

$x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]$

$x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]$

架构中的第2层(2nd stage)

$x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]$

$x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]$

可继续延伸

$\vdots$

$\vdots$

架构中的第$\alpha$层($\alpha -th$ stage)

$x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]$

$x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]$

注意：若输入信号$x[n]$的长度是N，则第$\alpha$层中的$x_{\alpha ,L}[n]$及$x_{\alpha ,H}[n]$的长度为${\frac {N}{2^{\alpha }}}$

二维离散小波变换

此时的输入信号变成$x[m,n]$，而变换过程变得更复杂，说明如下：

首先对n方向作高通、低通以及降频的处理

$v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]$

$v_{1,H}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]h[k]$

接着对$v_{1,L}[m,n]$与$v_{1,H}[m,n]$延著m方向作高低通及降频动作

$x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]$

$x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]$

$x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]$

$x_{1,HH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]h[k]$

经过(1)(2)两个步骤才算完成2-D DWT的一个stage。

实际范例

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

原始影像

2D DWT的结果

$\Rightarrow$

复杂度(Complexity)

在讨论复杂度之前，先做一些定义，当x[n]*y[n]时，x[n]之长度为N，y[n]之长度为L： $\ \Rightarrow IDFT_{N+L-1}\left[DFT_{N+L-1}(x[n])DFT_{N+L-1}(y[n])\right]$

其中，

$\ IDFT_{N+L-1}$为(N+L-1)点离散傅里叶逆变换(inverse discrete Fourier transform)

$\ DFT_{N+L-1}$为(N+L-1)点离散傅里叶变换(discrete Fourier transform)

(1)一维离散小波变换之复杂度(没有分段卷积(sectioned convolution))：

${\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}\approx {\frac {3}{2}}N\log _{2}N$

(2)当 N >>> L 时，使用 “分段卷积(sectioned convolution)”的技巧：

将x[n]切成很多段，每段长度为$\mathbb {N} _{1}$，总共会有$S={\frac {N}{N_{1}}}$段，其中$N>N_{1}>>L$。

则

$\ x[n]*g[n]=x_{1}[n]*g[n]+x_{2}[n]*g[n]+...+x_{s}[n]*g[n]$

$\ x[n]*h[n]=x_{1}[n]*h[n]+x_{2}[n]*h[n]+...+x_{s}[n]*h[n]$

复杂度为：

${\begin{aligned}{\frac {3}{2}}S(N_{1}+L-1)\log _{2}{(N_{1}+L-1)}&\approx {\frac {3}{2}}SN_{1}\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}N_{1}\\\end{aligned}}$

在这里要注意的是，当N>>L时，一维离散小波变换之复杂度是呈线性的(随N)，${\mathit {O(N)}}$。

(3)多层(Multiple stages )的情况下：

1.若$\ x_{a,H}[n]$不再分解时：

${\begin{aligned}Complexity&\approx \left(N+{\frac {N}{2}}+{\frac {N}{4}}+{\frac {N}{8}}+...+2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(2N-2){\frac {3}{2}}\log _{2}N_{1}\\&\approx 3N\log _{2}N_{1}\\\end{aligned}}$

2.若$\ x_{a,H}[n]$也细分时：

${\begin{aligned}Complexity&\approx \left(N+2{\frac {N}{2}}+4{\frac {N}{4}}+8{\frac {N}{8}}+...+{\frac {N}{2}}2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(N\log _{2}N){\frac {3}{2}}\log _{2}N_{1}\\\end{aligned}}$

(4)二维离散小波变换之复杂度(没有分段卷积(sectioned convolution))： $\ \Rightarrow M{\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}+(N+L-1){\frac {3}{2}}(M+L-1)\log _{2}{(M+L-1)}$

上式中，第一部分需要M个一维离散小波变换并且每个一维离散小波变换的输入有N个点；第二部分需要N+L-1个一维离散小波变换并且每个一维离散小波变换的输入有M个点。

${\begin{aligned}Complexity&\approx {\frac {3}{2}}MN\log _{2}N+{\frac {3}{2}}MN\log _{2}M\\&={\frac {3}{2}}MN(\log _{2}N+\log _{2}M)\\&={\frac {3}{2}}MN\log _{2}MN\\\end{aligned}}$

(5)二维离散小波变换之复杂度，使用 “分段卷积(sectioned convolution)”的技巧：

假设原始尺寸为$M\times N$，则每一小部分的尺寸为$M_{1}\times N_{1}$

${\begin{aligned}Complexity&\approx {\frac {MN}{M_{1}N_{1}}}{\frac {3}{2}}M_{1}N_{1}\log _{2}M_{1}N_{1}\\&={\frac {3}{2}}MN\log _{2}M_{1}N_{1}\\\end{aligned}}$

所以若是使用分段卷积，则二维离散小波变换之复杂度是呈线性的(随MN)，${\mathit {O(MN)}}$。

(6)多层(Multiple stages )与二维的情况下：

首先x[m,n]的尺寸为$M\times N$，

1.若$\ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]$不细分，只细分$\ x_{a,L}[n]$时，总复杂度为：

${\begin{aligned}totalcomplexity&=\left(MN+{\frac {MN}{4}}+{\frac {MN}{16}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&\approx {\frac {4}{3}}MN{\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=2MN\log _{2}M_{1}N_{1}\\\end{aligned}}$

2.若$\ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]$也细分时，总复杂度为：

${\begin{aligned}totalcomplexity&=\left(MN+4{\frac {M}{2}}{\frac {N}{2}}+16{\frac {M}{4}}{\frac {N}{4}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=\left[MN\log _{2}(min(M,N))\right]{\frac {3}{2}}\log _{2}M_{1}N_{1}\\\end{aligned}}$

重建(Reconstruction)

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

重建过程如下：

使用Z变换：

$X(z)=\sum x(n)z^{-n}$

• DWT低通滤波器 $g(n)$ 的Z变换为 $G(z)$ ，DWT高通滤波器$h(n)$的Z变换为$H(z)$

• 信号$x(n)$通过滤波器 $g(n)$ 后，Z变换为 $X(z)$$G(z)$ ，信号$x(n)$通过滤波器 $h(n)$ 后，Z变换为 $X(z)$$H(z)$

• 降低采样数(downsample)2倍后，

$X_{1,L}(z)={\frac {1}{2}}[X(z^{\frac {1}{2}})G(z^{\frac {1}{2}})+X(-z^{\frac {1}{2}})G(-z^{\frac {1}{2}})]$

$X_{1,H}(z)={\frac {1}{2}}[X(z^{\frac {1}{2}})H(z^{\frac {1}{2}})+X(-z^{\frac {1}{2}})H(-z^{\frac {1}{2}})]$

• 升频(interpolation)2倍后，再通过IDWT的低通重建滤波器 $g_{1}(n)$ ，

$X_{0}(z)={\tfrac {1}{2}}[X(z)G(z)+X(-z)G(-z)]G_{1}(z)+{\tfrac {1}{2}}[X(z)H(z)+X(-z)H(-z)]H_{1}(z)$

$={\tfrac {1}{2}}[G(z)G_{1}(z)+H(z)H_{1}(z)]X(z)+{\tfrac {1}{2}}[G(-z)G_{1}(z)+H(-z)H_{1}(z)]X(-z)$

若要完整重建，则$X_{0}(z)=X(z)$

條件1：$G(z)G_{1}(z)+H(z)H_{1}(z)=2$

條件2：$G(-z)G_{1}(z)+H(-z)H_{1}(z)=0$

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

${\binom {G_{1}(z)}{H_{1}(z)}}={\frac {2}{det(H_{m}(z))}}{\binom {H(-z)}{-G(-z)}}$

其中 $det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)$

离散小波变换(DWT)设计

四大条件：

1.DWT通滤波器 $g(n)$，$h(n)$必须要是有限长度。

2.满足$h(n)$是高通滤波器(high pass filter)，$g(n)$是低通滤波器(low pass filter)。

3.满足完整重建要条件，${\binom {G_{1}(z)}{H_{1}(z)}}={\frac {2}{det(H_{m}(z))}}{\binom {H(-z)}{-G(-z)}}$，其中 $det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)$

4.若$g(n)$，$h(n)$为有限长度，则$det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=\alpha z^{k}$ ，且 $k$ 为奇数。

>第4点较难达成，是DWT设计的核心

*为什么k是奇数？

假设k为偶数，

z=-1

$det(H_{m}(-1))=G(-1)H(1)-H(-1)G(1)=\alpha (-1)^{k}=1$

z=1

$det(H_{m}(1))=G(1)H(-1)-H(1)G(-1)=\alpha (1)^{k}=1$

$G(1)H(-1)-H(1)G(-1)=G(-1)H(1)-H(-1)G(1)$

$H(1)G(-1)=G(1)H(-1)$

代回

$det(H_{m}(-1))=G(-1)H(1)-H(-1)G(1)=0$

显然出现矛盾。

所以k必须为奇数。

以下介绍两种完美重建的DWT滤波器：

1.Quadrature Mirror Filter(QMF)

• $H(z)=G(-z)$

$\Longrightarrow$ $h(n)=(-1)^{n}g(n)$

• $G_{1}(z)=G(z)z^{-k}$

$\Longrightarrow$ $g_{1}(n)=g(n-k)$

• $H_{1}(z)=-G(-z)z^{-k}$

$\Longrightarrow$ $h_{1}(n)=(-1)^{n-k+1}g(n-k)$

$det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}$，且 $k$ 为奇数。

2.Orthonormal Wavelet

• $G(z)=G_{1}(z^{-1})$

$\Longrightarrow$ $g(n)=g_{1}(-n)$

• $H(z)=-z^{k}G_{1}(-z)$

$\Longrightarrow$ $h(n)=(-1)^{n}g_{1}(n+k)$

• $H_{1}(z)=-z^{k}G_{1}(-z^{-1})$

$\Longrightarrow$ $h_{1}(n)=(-1)^{n}g_{1}(-n+k)$

$det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}$，且 $k$ 为奇数。

多数的wavelet属于orthonormal wavelet。

其他应用

压缩、去除噪声：使用低通滤波器，将小波变换的高频滤掉，即保留$x_{1,LL}[m,n]$而将其他部分舍弃。

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

同时参阅

• 小波分析
• 连续小波变换
• 哈尔小波变换
• 信号处理

参考

• Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2009,2016 .http://djj.ee.ntu.edu.tw/TFW.htm （页面存档备份，存于互联网档案馆）
• Stéphane Mallat, A Wavelet Tour of Signal Processing （页面存档备份，存于互联网档案馆）