离散小波变换

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

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

## 定义

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

举例说明:

<image>

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

<image>

架构中的第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]$

可继续延伸

<image>

$\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 }$

## 二维离散小波转换

<image>

此时的输入信号变成$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)

原始影像

<image>

2D DWT的结果

<image>

$\Rightarrow$

<image>

## 复杂度(Complexity)

在讨论复杂度之前，先做一些定义，当xn*yn时，xn之长度为N，yn之长度为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)”的技巧：

将xn切成很多段，每段长度为$\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{align} \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{align}$$

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

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

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

$$\begin{align} 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{align}$$

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

$$\begin{align} 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{align}$$

(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{align} 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{align}$$

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

假设原始尺寸为$M \times N$，则每一小部分的尺寸为$M_1 \times N_1$

$$\begin{align} Complexity & \approx \frac{MN}{M_1 N_1} \frac{3}{2} M_1 N_1 \log_{2} M_1 N_1\\ & = \frac{3}{2} M N \log_{2} M_1 N_1\\ \end{align}$$

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

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

首先xm,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{align} total complexity & = \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{align}$$

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

$$\begin{align} total complexity & = \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{align}$$

## 重建(Reconstruction)

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

### 重建过程如下：

使用Z转换：

```
<math>    X(z) = \sum x(n)z^{-n}</math>
```

- 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倍后。

```
<math>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})]</math>

<math>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})]</math>
```

- 升频(interpolation)2倍后，再通过IDWT的低通重建滤波器 $g_1(n)$。

```
<math>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)</math>

<math>=\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)</math>
```

若要完整重建，则$X_0(z) = X(z)$

```
條件1：<math>G(z)G_1(z)+H(z)H_1(z) =2</math>

條件2：<math>G(-z)G_1(z)+H(-z)H_1(z) =0</math>
```

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

```
<math>\binom{G_1(z)}{H_1(z)}=\frac{2}{det(H_m(z))}\binom{H(-z)}{-G(-z)}</math>

其中 <math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z)</math>
```

## 离散小波转换(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)^ng(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) = 2 z^k$，且 $k$ 为奇数。

2.单位正交小波（Orthonormal Wavelet）

- $$G(z)=G_1(z^{-1})$$

$\Longrightarrow$ $g(n) = g_1(-n)$

- $$H(z)=-z^kG_1(-z)$$

$\Longrightarrow$ $h(n) = (-1)^ng_1(n+k)$

- $$H_1(z)=-z^kG_1(-z^{-1})$$

$\Longrightarrow$ $h_1(n) = (-1)^ng_1(-n+k)$

$det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = 2 z^k$，且 $k$ 为奇数。

多数小波属于单位正交小波。

## 常见的小波族

在离散小波转换中，选择合适的小波基底（Mother Wavelet）对于分析结果至关重要。常见的小波族包括：

### Daubechies 小波

由英格丽·道贝希（Ingrid Daubechies）提出，是最常用的正交小波族。

- 具有紧支撑（Compact Support）特性，即在有限区间外为零。
- 随着阶数 $N$ 增加（dbN），其消失矩（Vanishing Moments）增加（为 $N$），平滑度也随之增加。
- 缺点：除了 Haar 小波（db1）外，Daubechies 小波均为非对称的，这会导致信号处理时产生相位失真（Phase Distortion）。

### Symlet

Daubechies 小波的改良版本，全名为 Symmlet（Symmetrical Wavelet）。

- 针对 Daubechies 小波非对称的缺点进行改良，设计上尽可能接近对称（Least Asymmetric）。
- 保留了正交性与紧支撑特性，且拥有与同阶数 Daubechies 小波相同的消失矩数量。
- 由于其良好的对称性，在影像处理与降噪应用中通常表现优于 Daubechies 小波。

### Coiflet

由 Ronald Coifman 提出。

- 其特点在于 Scaling Function 与 Mother Wavelet 函数皆具有消失矩。
- 这使得 Coiflet 在数值分析（如积分运算）中具有更高的精确度。
- 代价是其支撑范围（Support Width）比同阶数的 Daubechies 小波更长，运算量稍大。

### 双正交小波 (Biorthogonal Wavelet)

与上述的正交小波不同，双正交小波使用两组不同的滤波器进行分解（Analysis）与合成（Synthesis）。

- 解除了正交小波“不可同时具备对称性与紧支撑”的限制。
- 可以设计出具有线性相位（Linear Phase）的滤波器，这对于影像压缩至关重要，因为它可以避免边缘的相位扭曲。
- 著名的 CDF 9/7 与 CDF 5/3 小波即属于此类，被广泛应用于 JPEG 2000 标准中。

## 其他应用

- 压缩、去除噪声：使用低通滤波器，将小波转换的高频滤掉，即保留$x_{1,LL}[m,n]$而将其他部分舍弃。
- 边缘侦测：使用高通滤波器，将小波的低频滤掉，即保留$x_{1,HL}[m,n]$或$x_{1,LH}[m,n]$而舍弃其他部分。
- 模式辨认：由于可以利用低频的部分得到原图的缩略版，加上模式通常为整体的特性，借由在缩略图上进行工作，小波转换可以有效减少寻找模式与比对模式的运算时间。
- 滤波器设计：小波转换保留部分时间资讯，可以据此资讯加上讯号的强度资讯，保留特定时点的资讯而同时去除噪声。
- R语言小波分析wavelet

### JPEG 2000

JPEG 2000 是一个包含无失真压缩与失真压缩的影像压缩标准，其核心技术采用了离散小波转换（DWT），而非传统 JPEG 所使用的离散余弦转换（DCT）。

#### 核心优势

相比于传统 JPEG，JPEG 2000 具有以下优势：

- 无区块效应（No Blocking Effect）：传统 JPEG 将影像切割为 8x8 的区块进行 DCT 转换，在高压缩率下会产生明显的方格状边缘。JPEG 2000 使用全域或大区块的 DWT，避免了此问题。
- 高压缩品质：在相同的压缩率下，JPEG 2000 的峰值信噪比（PSNR）通常优于 JPEG。特别是在高压缩率（例如压缩比 80:1）的情况下，JPEG 2000 仍能重建出品质不错的影像。
- 支援多分辨率：DWT 的金字塔结构使得影像可以被解码为不同分辨率的版本，方便缩图预览或分层传输。

#### 编码架构

JPEG 2000 的编码流程包含以下步骤：

- 前处理：将影像色彩空间由 RGB 转换为 YCbCr，并可能进行降取样（如 4:2:0）。
- 离散小波转换（DWT）：将影像分解为多个频带（Subbands）。
- 量子化（Quantization）：对小波系数进行量子化。
- Tier 1 编码：包含分数位元平面编码（Fractional Bit-plane Coding）、零编码（Zero Coding）、符号编码（Sign Coding）与游程编码（Run Length Coding）。
- Tier 2 编码：负责组织码流（Bitstream）并控制档案大小，例如决定要截断哪些较不重要的资料以符合目标位元率。

## 进阶变形与发展

传统的二维离散小波转换（2D DWT）是借由张量积（Tensor Product）将一维小波推广到二维，因此它只有水平、垂直与对角线三个方向的特征提取能力。这导致其在处理影像中的平滑曲线边缘（Smooth Curves）时效率不佳，容易产生点状噪声。为了改善此问题，学者提出了多种具备“方向性”的新型转换。

### Contourlet 转换

由 Minh N. Do 和 Martin Vetterli 提出。Contourlet 转换是一种能有效捕捉影像中平滑轮廓（Contours）的“方向性多分辨率”转换。

- 架构：它结合了拉普拉斯金字塔（Laplacian Pyramid）用于捕捉点奇异点（Point Singularities），以及方向滤波器组（Directional Filter Banks, DFB）将奇异点连结成线性结构。
- 特点：具有各向异性（Anisotropy）与多方向性，能以比 DWT 更稀疏的方式表示包含平滑曲线的影像（如指纹、纹理）。

### Bandlet 转换

由史蒂芬·马拉特和加布里埃尔·佩雷提出。Bandlet 转换是一种“几何自适应”的转换方法。

- 原理：它不使用固定的滤波器方向，而是根据影像局部的几何流（Geometric Flow）或纹理方向，动态调整小波基底的扭曲（Warping）方向。
- 特点：能够“顺着”边缘的方向进行滤波，从而在边缘处获得极佳的稀疏表示，特别适合处理具有复杂几何纹理的自然影像。

## 同时参阅

- 小波分析
- 连续小波转换
- 哈尔小波转换
- 信号处理

## 参考

- Jian-Jiun Ding, Time frequency analysis and wavelet transform class notes, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2025.
- 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