離散小波變換

在數值分析和泛函分析領域中，離散小波變換（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