離散小波變換

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

第一個離散小波變換由匈牙利數學家哈尔發明，離散小波轉換顧名思義就是離散的輸入以及離散的輸出，但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係，只能以階層式架構來表示。

 定義 

首先我們定義一些需要用到的信號及濾波器。
x[n]：離散的輸入信號，長度為N。
：低通濾波器（low pass filter），可以將輸入信號的高頻部份濾掉而輸出低頻部份。
：高通濾波器（high pass filter），與低通濾波器相反，濾掉低頻部份而輸出高頻部份。
 Q：降采样濾波器（downsampling filter），如果以x[n]作為输入，則輸出y[n]=x[Qn]。此處舉例Q=2。
舉例說明:400px
清楚規定以上符號之後，便可以利用階層架構來介紹如何將一個離散信號作離散小波轉換：
500px
架構中的第1層(1st stage)

架構中的第2層(2nd stage)

可繼續延伸
File:Wavelets_-_Filter_Bank.png

架構中的第層( stage)

  注意：若輸入信號的長度是N，則第層中的及的長度為 

 二維離散小波轉換 
500px
此時的輸入信號變成，而轉換過程變得更複雜，說明如下：
首先對n方向作高通、低通以及降頻的處理

接著對與延著m方向作高低通及降頻動作

經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。

 實際範例 
以下根據上述2-D DWT的步驟，對一張影像作二維離散小波轉換(2D Discrete Wavelet Transform)
原始影像300px
2D DWT的結果300px
300px

 複雜度(Complexity) 
在討論複雜度之前，先做一些定義，當x[n]*y[n]時，x[n]之長度為N，y[n]之長度為L：

其中，

為(N+L-1)點離散傅立葉反轉換(inverse discrete Fourier transform)

為(N+L-1)點離散傅立葉轉換(discrete Fourier transform)

(1)一維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：

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

將x[n]切成很多段，每段長度為，總共會有段，其中。

則

複雜度為：

在這裡要注意的是，當N>>L時，一維離散小波轉換之複雜度是呈線性的(隨N)，。

(3)多層(Multiple stages )的情況下：

1.若不再分解時：

2.若也細分時：

(4)二維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：

上式中，第一部分需要M個一維離散小波轉換並且每個一維離散小波轉換的輸入有N個點；第二部分需要N+L-1個一維離散小波轉換並且每個一維離散小波轉換的輸入有M個點。

(5)二維離散小波轉換之複雜度，使用 “分段卷积(sectioned convolution)”的技巧：

假設原始尺寸為，則每一小部分的尺寸為

所以若是使用分段摺積，則二維離散小波轉換之複雜度是呈線性的(隨MN)，。

(6)多層(Multiple stages )與二維的情況下：

首先x[m,n]的尺寸為，

1.若不細分，只細分時，總複雜度為：

2.若也細分時，總複雜度為：

 重建(Reconstruction) 
使用離散小波轉換，將訊號個別通過一個低通濾波器和一個高通濾波器，得到訊號的高低頻成分，而在重建()原始訊號的過程，也就是離散小波的逆轉換(Inverse Discrete Wavelet Transform. IDWT)，直觀而言，我們僅是需要將離散小波轉換做重建濾波即可得到原始輸入信號，以下將推導重建濾波器，也就是IDWT高低通濾波器的構成要件，以及如何來重建原始信號。

 重建過程如下： 
使用Z轉換：

 DWT低通濾波器  的Z轉換為  ，DWT高通濾波器的Z轉換為

 信號通過濾波器  後，Z轉換為  ，信號通過濾波器  後，Z轉換為 

 降低採樣數(downsample)2倍後，



 升頻(interpolation)2倍後，再通過IDWT的低通重建濾波器  ，



若要完整重建，則
 條件1：

 條件2：
因此，在設計高低通重建濾波器時，需要考慮上述條件，寫成矩陣形式如下：


 其中 

 離散小波轉換(DWT)設計 

 四大條件： 
1.DWT通濾波器 ，必須要是有限長度。

2.滿足是高通濾波器(high pass filter)，是低通濾波器(low pass filter)。

3.滿足完整重建要條件，，其中 

4.若，為有限長度，則 ，且  為奇數。

 >第4點較難達成，是DWT設計的核心 
*為什麼k是奇數？

假設k为偶数，

z=-1

z=1

代回

顯然出現矛盾。

所以k必須為奇数。

 以下介紹兩種完美重建的DWT濾波器： 
1.正交镜象滤波器（Quadrature Mirror Filter，QMF）







，且  為奇數。

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







，且  為奇數。

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

 常見的小波族 
在離散小波轉換中，選擇合適的小波基底（Mother Wavelet）對於分析結果至關重要。常見的小波族包括：

 Daubechies 小波  
由英格麗·道貝希（Ingrid Daubechies）提出，是最常用的正交小波族。
 特性：
 具有緊支撐（Compact Support）特性，即在有限區間外為零。
 隨著階數  增加（dbN），其消失矩（Vanishing Moments）增加（為 ），平滑度也隨之增加。
 缺點：除了 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 標準中。

 其他應用 
 壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留而將其他部分捨棄。
 邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留或而捨棄其他部分。
 模式辨認：由於可以利用低頻的部分得到原圖的縮略版，加上模式通常為整體的特性，藉由在縮略圖上進行工作，小波轉換可以有效減少尋找模式與比對模式的運算時間。
 濾波器設計：小波轉換保留部分時間資訊，可以據此資訊加上訊號的強度資訊，保留特定時點的資訊而同時去除雜訊。
 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 轉換 
由 Stéphane Mallat 和 Gabriel Peyré 提出。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 

L
Category:时间序列降维方法
de:Wavelet-Transformation#Diskrete Wavelet-Transformation
fr:Ondelette#Transformée en ondelettes discrète