離散小波變換

在数值分析和泛函分析领域中，离散小波变换（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$ 為奇數。

多數小波屬於单位正交小波。

常見的小波族

在離散小波轉換中，選擇合適的小波基底（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 的編碼流程包含以下步驟：

1. 前處理：將影像色彩空間由 RGB 轉換為 YCbCr，並可能進行降取樣（如 4:2:0）。
2. 離散小波轉換（DWT）：將影像分解為多個頻帶（Subbands）。
3. 量子化（Quantization）：對小波係數進行量子化。
4. Tier 1 編碼：包含分數位元平面編碼（Fractional Bit-plane Coding）、零編碼（Zero Coding）、符號編碼（Sign Coding）與遊程編碼（Run Length Coding）。
5. 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 轉換

由 Stéphane Mallat 和 Gabriel Peyré 提出。Bandlet 轉換是一種「幾何自適應」的轉換方法。

• 原理：它不使用固定的濾波器方向，而是根據影像局部的幾何流（Geometric Flow）或紋理方向，動態調整小波基底的扭曲（Warping）方向。
• 特點：能夠「順著」邊緣的方向進行濾波，從而在邊緣處獲得極佳的稀疏表示，特別適合處理具有複雜幾何紋理的自然影像。

同時參閱

• 小波分析
• 連續小波轉換
• 哈爾小波轉換
• 信號處理

參考

1. 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 （页面存档备份，存于互联网档案馆）