離散小波變換

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

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

定義 

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

架構中的第1層(1st stage)

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

可繼續延伸

架構中的第層( stage)

二維離散小波轉換 

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

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

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

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

複雜度(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
    
   
    
   
    
   

，且  為奇數。

多數的wavelet屬於orthonormal wavelet。

其他應用 
壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留而將其他部分捨棄。
邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留或而捨棄其他部分。
 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 

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