本页使用了标题或全文手工转换

離散小波變換

维基百科,自由的百科全书
(重定向自离散小波变换
跳转至: 导航搜索

離散小波變換(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。
舉例說明:DiscreteWaveletTrans1.jpg
清楚規定以上符號之後,便可以利用階層架構來介紹如何將一個離散信號作離散小波轉換:
DWT2ndLayer.jpg
架構中的第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]
可繼續延伸

Wavelets - Filter Bank.png

 \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 }

二维离散小波转换[编辑]

2D DWT.jpg
此時的輸入信號變成 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 Original.png
2D DWT的結果2D DWT pre-process.png
\Rightarrow 2D DWT process.png

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

同時參閱[编辑]

參考[编辑]