離散小波變換

數值分析泛函分析領域中,離散小波轉換(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,則第 層中的  的長度為 

二維離散小波轉換

 
此時的輸入訊號變成 ,而轉換過程變得更複雜,說明如下:
首先對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)

使用離散小波轉換,將訊號個別通過一個低通濾波器和一個高通濾波器,得到訊號的高低頻成分,而在重建(Reconstruction英語Reconstruction_filter)原始訊號的過程,也就是離散小波的逆轉換(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 的內部架構
  • 模式辨認:由於可以利用低頻的部分得到原圖的縮略版,加上模式通常為整體的特性,藉由在縮略圖上進行工作,小波轉換可以有效減少尋找模式與比對模式的運算時間
  • 濾波器設計:小波轉換保留部分時間資訊,可以據此資訊加上訊號的強度資訊,保留特定時點的資訊而同時去除雜訊

同時參閱

參考