离散小波变换

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

举例说明: 

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

 

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

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

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

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

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

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

可继续延伸

${\displaystyle \vdots }$ 

${\displaystyle \vdots }$ 

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

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

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

 

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

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

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

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

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

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

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

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

${\displaystyle 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的结果 

${\displaystyle \Rightarrow }$  

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

其中，

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

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

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

${\displaystyle {\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]切成很多段，每段长度为${\displaystyle \mathbb {N} _{1}}$ ，总共会有${\displaystyle S={\frac {N}{N_{1}}}}$ 段，其中${\displaystyle N>N_{1}>>L}$ 。

则

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

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

复杂度为：

${\displaystyle {\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)，${\displaystyle {\mathit {O(N)}}}$ 。

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

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

${\displaystyle {\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.若${\displaystyle \ x_{a,H}[n]}$ 也细分时：

${\displaystyle {\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))： ${\displaystyle \ \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个点。

${\displaystyle {\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)”的技巧：

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

${\displaystyle {\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)，${\displaystyle {\mathit {O(MN)}}}$ 。

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

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

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

${\displaystyle {\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.若${\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}$ 也细分时，总复杂度为：

${\displaystyle {\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_filter）)原始信号的过程，也就是离散小波的逆变换(Inverse Discrete Wavelet Transform. IDWT)，直观而言，我们仅是需要将离散小波变换做重建滤波即可得到原始输入信号，以下将推导重建滤波器，也就是IDWT高低通滤波器的构成要件，以及如何来重建原始信号。

重建过程如下：

使用Z变换：

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

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

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

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

${\displaystyle 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}})]}$ 

${\displaystyle 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的低通重建滤波器 ${\displaystyle g_{1}(n)}$  ，

${\displaystyle 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)}$ 

${\displaystyle ={\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)}$ 

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

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

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

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

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

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

四大条件：

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

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

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

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

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

*为什么k是奇数？

假设k=even，

z=-1

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

z=1

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

${\displaystyle G(1)H(-1)-H(1)G(-1)=G(-1)H(1)-H(-1)G(1)}$ 

${\displaystyle H(1)G(-1)=G(1)H(-1)}$ 

代回

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

显然出现矛盾。

所以k必须为odd。

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

1.Quadrature Mirror Filter(QMF)

• ${\displaystyle H(z)=G(-z)}$ 

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

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

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

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

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

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

2.Orthonormal Wavelet

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

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

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

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

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

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

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

多数的wavelet属于orthonormal wavelet。

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

• 边缘侦测：使用高通滤波器，将小波的低频滤掉，即保留${\displaystyle x_{1,HL}[m,n]}$ 或${\displaystyle 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 （页面存档备份，存于互联网档案馆）