查看“︁離散小波變換”︁的源代码

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

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

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

:<math> x_{1,L}[n]=\sum_{k=0}^{K-1} x[2n-k]g[k] </math>
:<math> x_{1,H}[n]=\sum_{k=0}^{K-1} x[2n-k]h[k] </math>

:架構中的第2層(2nd stage)
:<math> x_{2,L}[n]=\sum_{k=0}^{K-1} x_{1,L}[2n-k]g[k] </math><br />
:<math> x_{2,H}[n]=\sum_{k=0}^{K-1} x_{1,L}[2n-k]h[k] </math><br />

:可繼續延伸<br />
[[File:Wavelets_-_Filter_Bank.png]]<br />
::<math> \vdots </math><br />
::<math> \vdots </math><br />
架構中的第<math> \alpha </math>層(<math> \alpha -th</math> stage)
:<math> x_{\alpha ,L}[n]=\sum_{k=0}^{K-1} x_{\alpha -1,L}[2n-k]g[k] </math><br />
:<math> x_{\alpha ,H}[n]=\sum_{k=0}^{K-1} x_{\alpha -1,L}[2n-k]h[k] </math>
{|border="1" 
 |-
 |注意：若輸入信號<math> x[n]</math>的長度是N，則第<math> \alpha </math>層中的<math> x_{\alpha ,L}[n]</math>及<math> x_{\alpha ,H}[n]</math>的長度為<math> \frac{N}{2^\alpha } </math>||
 |-
|}

== 二維離散小波轉換 ==
::[[File:2D_DWT.jpg|500px]]<br />
:此時的輸入信號變成<math> x[m,n] </math>，而轉換過程變得更複雜，說明如下：
::首先對n方向作高通、低通以及降頻的處理<br />
:<math> v_{1,L}[m,n]=\sum_{k=0}^{K-1} x[m,2n-k]g[k] </math>
:<math> v_{1,H}[m,n]=\sum_{k=0}^{K-1} x[m,2n-k]h[k] </math>
::接著對<math> v_{1,L}[m,n]</math>與<math> v_{1,H}[m,n]</math>延著m方向作高低通及降頻動作
:<math> x_{1,LL}[m,n]=\sum_{k=0}^{K-1} v_{1,L}[2m-k,n]g[k] </math>
:<math> x_{1,HL}[m,n]=\sum_{k=0}^{K-1} v_{1,L}[2m-k,n]h[k] </math>
:<math> x_{1,LH}[m,n]=\sum_{k=0}^{K-1} v_{1,H}[2m-k,n]g[k] </math>
:<math> x_{1,HH}[m,n]=\sum_{k=0}^{K-1} v_{1,H}[2m-k,n]h[k] </math>
::經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。


== 實際範例 ==
以下根據上述2-D DWT的步驟，對一張影像作二維離散小波轉換(2D Discrete Wavelet Transform)
:原始影像[[File:2D_DWT_Original.png|300px]]
:2D DWT的結果[[File:2D_DWT_pre-process.png|300px]]
:<math>\Rightarrow </math>[[File:2D_DWT_process.png|300px]]

== 複雜度(Complexity) ==
在討論複雜度之前，先做一些定義，當x[n]*y[n]時，x[n]之長度為N，y[n]之長度為L：
<math>\ \Rightarrow  
IDFT_{N+L-1}\left[ DFT_{N+L-1}(x[n]) DFT_{N+L-1}(y[n])\right]</math>

其中，

<math>\ IDFT_{N+L-1}</math>為(N+L-1)點離散傅立葉反轉換(inverse discrete Fourier transform)

<math>\ DFT_{N+L-1}</math>為(N+L-1)點離散傅立葉轉換(discrete Fourier transform)

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

<math>\frac{3}{2}(N+L-1)\log_{2} {(N+L-1)}\approx \frac{3}{2} N \log_{2} N</math>

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

將x[n]切成很多段，每段長度為<math>\N_1</math>，總共會有<math>S=\frac{N}{N_1}</math>段，其中<math>N>N_1>>L</math>。

則

<math>\ x[n]*g[n]=x_1 [n]*g[n]+x_2 [n]*g[n]+...+x_s [n]*g[n]</math>

<math>\ x[n]*h[n]=x_1 [n]*h[n]+x_2 [n]*h[n]+...+x_s [n]*h[n]</math>

複雜度為：

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

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

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

1.若<math>\ x_{a,H} [n]</math>不再分解時：

<math>\begin{align}
Complexity & \approx \left( N+\frac{N}{2}+\frac{N}{4}+\frac{N}{8}+...+2 \right)\frac{3}{2}  \log_{2} N_1\\
& = (2N-2)\frac{3}{2} \log_{2}N_1\\
& \approx 3N\log_{2} N_1\\
\end{align}</math>

2.若<math>\ x_{a,H} [n]</math>也細分時：

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

(4)二維離散小波轉換之複雜度(沒有分段卷积(sectioned convolution))：
<math>\ \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)}</math>

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

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

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

假設原始尺寸為<math> M \times N </math>，則每一小部分的尺寸為<math> M_1 \times N_1</math>

<math>\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 N \log_{2} M_1 N_1\\
\end{align}</math>

所以若是使用分段摺積，則二維離散小波轉換之複雜度是呈線性的(隨MN)，<math>\mathit{O(MN)}</math>。

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

首先x[m,n]的尺寸為<math> M \times N </math>，

1.若<math>\ x_{a,H_1} [n] ,x_{a,H_2} [n],x_{a,H_3} [n]</math>不細分，只細分<math>\ x_{a,L} [n]</math>時，總複雜度為：

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

2.若<math>\ x_{a,H_1} [n] ,x_{a,H_2} [n],x_{a,H_3} [n]</math>也細分時，總複雜度為：

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

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

=== 重建過程如下： ===
使用Z轉換：
 <math>    X(z) = \sum x(n)z^{-n}</math>
* DWT低通濾波器 <math>g(n)</math> 的Z轉換為 <math>G(z)</math> ，DWT高通濾波器<math>h(n)</math>的Z轉換為<math>H(z)</math>

* 信號<math>x(n)</math>通過濾波器 <math>g(n)</math> 後，Z轉換為 <math>X(z)</math><math>G(z)</math> ，信號<math>x(n)</math>通過濾波器 <math>h(n)</math> 後，Z轉換為 <math>X(z)</math><math>H(z)</math>

* 降低採樣數(downsample)2倍後，
 <math>X_{1,L}(z) = \frac{1}{2}[X(z^\frac{1}{2})G(z^\frac{1}{2})+X(-z^\frac{1}{2})G(-z^\frac{1}{2})]</math>

 <math>X_{1,H}(z) = \frac{1}{2}[X(z^\frac{1}{2})H(z^\frac{1}{2})+X(-z^\frac{1}{2})H(-z^\frac{1}{2})]</math>
* 升頻(interpolation)2倍後，再通過IDWT的低通重建濾波器 <math>g_1(n)</math> ，
 <math>X_0(z) = \tfrac{1}{2}[X(z)G(z) + X(-z)G(-z)]G_1(z) + \tfrac{1}{2}[X(z)H(z) + X(-z)H(-z)]H_1(z)</math>

 <math>=\tfrac{1}{2}[G(z)G_1(z)+H(z)H_1(z)]X(z)+\tfrac{1}{2}[G(-z)G_1(z)+H(-z)H_1(z)]X(-z)</math>
若要完整重建，則<math>X_0(z) = X(z)</math>
 條件1：<math>G(z)G_1(z)+H(z)H_1(z) =2</math>

 條件2：<math>G(-z)G_1(z)+H(-z)H_1(z) =0</math>
因此，在設計高低通重建濾波器時，需要考慮上述條件，寫成矩陣形式如下：
 <math>\binom{G_1(z)}{H_1(z)}=\frac{2}{det(H_m(z))}\binom{H(-z)}{-G(-z)}</math>

 其中 <math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z)</math>

== 離散小波轉換(DWT)設計 ==

=== 四大條件： ===
1.DWT通濾波器 <math>g(n)</math>，<math>h(n)</math>必須要是有限長度。

2.滿足<math>h(n)</math>是高通濾波器(high pass filter)，<math>g(n)</math>是低通濾波器(low pass filter)。

3.滿足完整重建要條件，<math>\binom{G_1(z)}{H_1(z)}=\frac{2}{det(H_m(z))}\binom{H(-z)}{-G(-z)}</math>，其中 <math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z)</math>

4.若<math>g(n)</math>，<math>h(n)</math>為有限長度，則<math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = \alpha z^k</math> ，且 <math>k</math> 為奇數。

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

假設k为偶数，

z=-1

<math>det(H_m(-1)) = G(-1)H(1)-H(-1)G(1) = \alpha (-1)^k = 1</math>

z=1

<math>det(H_m(1)) = G(1)H(-1)-H(1)G(-1) = \alpha (1)^k = 1</math>

<math> G(1)H(-1)-H(1)G(-1) = G(-1)H(1)-H(-1)G(1) </math>

<math> H(1)G(-1) = G(1)H(-1) </math>

代回

<math>det(H_m(-1)) = G(-1)H(1)-H(-1)G(1) = 0</math>

顯然出現矛盾。

所以k必須為奇数。

=== 以下介紹兩種完美重建的DWT濾波器： ===
1.正交镜象滤波器（Quadrature Mirror Filter，QMF）
* <math>H(z)=G(-z) </math>  
<math>\Longrightarrow</math>   <math>h(n) = (-1)^ng(n)</math>
* <math>G_1(z) = G(z)z^{-k}</math>  
<math>\Longrightarrow</math>   <math>g_1(n)=g(n-k)</math>
* <math>H_1(z) = -G(-z)z^{-k}</math>   
<math>\Longrightarrow</math>   <math>h_1(n) = (-1)^{n-k+1}g(n-k)</math>

<math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = 2 z^k</math>，且 <math>k</math> 為奇數。

2.单位正交小波（Orthonormal Wavelet）
* <math>G(z)=G_1(z^{-1}) </math>   
<math>\Longrightarrow</math>   <math>g(n) = g_1(-n)</math>
* <math>H(z)=-z^kG_1(-z) </math>   
<math>\Longrightarrow</math>   <math>h(n) = (-1)^ng_1(n+k)</math>
* <math>H_1(z)=-z^kG_1(-z^{-1}) </math>   
<math>\Longrightarrow</math>   <math>h_1(n) = (-1)^ng_1(-n+k)</math>

<math>det(H_m(z)) = G(z)H(-z)-H(z)G(-z) = 2 z^k</math>，且 <math>k</math> 為奇數。

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

== 其他應用 ==
壓縮、去除雜訊：使用低通濾波器，將小波轉換的高頻濾掉，即保留<math> x_{1,LL}[m,n] </math>而將其他部分捨棄。
*邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留<math> x_{1,HL}[m,n] </math>或<math> x_{1,LH}[m,n] </math>而捨棄其他部分。
* [http://wenku.baidu.com/view/cd757ded6294dd88d0d26ba8.html R语言小波分析wavelet] {{Wayback|url=http://wenku.baidu.com/view/cd757ded6294dd88d0d26ba8.html |date=20210717234941 }}
* 作為 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 http://djj.ee.ntu.edu.tw/TFW.htm] {{Wayback|url=http://djj.ee.ntu.edu.tw/TFW.htm |date=20170101160000 }}
*Stéphane Mallat, [http://books.google.com/books?vid=ISBN012466606X&id=yW2kut44AsMC&dq=Wavelet+tour+of+signal+processing A Wavelet Tour of Signal Processing] {{Wayback|url=http://books.google.com/books?vid=ISBN012466606X&id=yW2kut44AsMC&dq=Wavelet+tour+of+signal+processing |date=20140921023628 }}

[[Category:小波分析|L]]
[[Category:时间序列降维方法]]
[[de:Wavelet-Transformation#Diskrete Wavelet-Transformation]]
[[fr:Ondelette#Transformée en ondelettes discrète]]