离散小波变换

離散小波變換（Discrete Wavelet Transform）在數值分析和時頻分析中很有用。第一個離散小波變換由匈牙利數學家發明，離散小波轉換顧名思義就是離散的輸入以及離散的輸出，但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係，只能以階層式架構來表示。

定義

• 首先我們定義一些需要用到的信號及濾波器。
• 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]切成很多段，每段長度為$\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\\ & = N_1(2N-2)\frac{3}{2} \log_{2}\\ & \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_1 N_1 \log_{2} M_1 N_1\\ \end{align}$

所以若是使用分段摺積，則二維離散小波轉換之複雜度是呈線性的(隨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{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}$

其他應用

• 壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留$x_{1,LL}[m,n]$而將其他部分捨棄。
• 邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留$x_{1,HL}[m,n]$或$x_{1,LH}[m,n]$而捨棄其他部分。
• R语言小波分析wavelet

同時參閱

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

參考

• Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2009.http://djj.ee.ntu.edu.tw/TFW.htm
• Stéphane Mallat, A Wavelet Tour of Signal Processing