# 離散小波變換

## 定義

• 首先我們定義一些需要用到的信號及濾波器。
• x[n]：離散的輸入信號，長度為N。
• ${\displaystyle g[n]}$：low pass filter低通濾波器，可以將輸入信號的高頻部份濾掉而輸出低頻部份。
• ${\displaystyle h[n]}$：high pass filter高通濾波器，與低通濾波器相反，濾掉低頻部份而輸出高頻部份。
• ${\displaystyle \downarrow }$ Q：downsampling filter降采样濾波器，如果以x[n]作為输入，則輸出y[n]=x[Qn]。此處舉例Q=2。

${\displaystyle x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]}$
${\displaystyle x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]}$

${\displaystyle x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]}$
${\displaystyle x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]}$

${\displaystyle \vdots }$
${\displaystyle \vdots }$

${\displaystyle x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]}$
${\displaystyle x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]}$
 注意：若輸入信號${\displaystyle x[n]}$的長度是N，則第${\displaystyle \alpha }$層中的${\displaystyle x_{\alpha ,L}[n]}$及${\displaystyle x_{\alpha ,H}[n]}$的長度為${\displaystyle {\frac {N}{2^{\alpha }}}}$

## 二維離散小波轉換

${\displaystyle v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]}$
${\displaystyle v_{1,H}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]h[k]}$

${\displaystyle x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]}$
${\displaystyle x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]}$
${\displaystyle x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]}$
${\displaystyle x_{1,HH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]h[k]}$

## 實際範例

2D DWT的結果
${\displaystyle \Rightarrow }$

## 複雜度(Complexity)

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

${\displaystyle \ DFT_{N+L-1}}$為(N+L-1)點離散傅立葉轉換(discrete Fourier transform)

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

${\displaystyle {\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}\approx {\frac {3}{2}}N\log _{2}N}$

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

${\displaystyle \ x[n]*g[n]=x_{1}[n]*g[n]+x_{2}[n]*g[n]+...+x_{s}[n]*g[n]}$

${\displaystyle \ x[n]*h[n]=x_{1}[n]*h[n]+x_{2}[n]*h[n]+...+x_{s}[n]*h[n]}$

{\displaystyle {\begin{aligned}{\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{aligned}}}

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

1.若${\displaystyle \ x_{a,H}[n]}$不再分解時：

{\displaystyle {\begin{aligned}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{aligned}}}

2.若${\displaystyle \ x_{a,H}[n]}$也細分時：

{\displaystyle {\begin{aligned}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{aligned}}}

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

{\displaystyle {\begin{aligned}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{aligned}}}

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

{\displaystyle {\begin{aligned}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{aligned}}}

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

1.若${\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}$不細分，只細分${\displaystyle \ x_{a,L}[n]}$時，總複雜度為：

{\displaystyle {\begin{aligned}totalcomplexity&=\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{aligned}}}

2.若${\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}$也細分時，總複雜度為：

{\displaystyle {\begin{aligned}totalcomplexity&=\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{aligned}}}

## 重建(Reconstruction)

### 重建過程如下：

${\displaystyle X(z)=\sum x(n)z^{-n}}$

• DWT低通濾波器 ${\displaystyle g(n)}$ 的Z轉換為 ${\displaystyle G(z)}$ ，DWT高通濾波器${\displaystyle h(n)}$的Z轉換為${\displaystyle H(z)}$
• 信號${\displaystyle x(n)}$通過濾波器 ${\displaystyle g(n)}$ 後，Z轉換為 ${\displaystyle X(z)}$${\displaystyle G(z)}$ ，信號${\displaystyle x(n)}$通過濾波器 ${\displaystyle h(n)}$ 後，Z轉換為 ${\displaystyle X(z)}$${\displaystyle H(z)}$
• 降低採樣數(downsample)2倍後，
${\displaystyle 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}})]}$

${\displaystyle 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}})]}$

• 升頻(interpolation)2倍後，再通過IDWT的低通重建濾波器 ${\displaystyle g_{1}(n)}$
${\displaystyle 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)}$

${\displaystyle ={\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)}$


條件1：${\displaystyle G(z)G_{1}(z)+H(z)H_{1}(z)=2}$

條件2：${\displaystyle G(-z)G_{1}(z)+H(-z)H_{1}(z)=0}$


${\displaystyle {\binom {G_{1}(z)}{H_{1}(z)}}={\frac {2}{det(H_{m}(z))}}{\binom {H(-z)}{-G(-z)}}}$

其中 ${\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)}$


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

### 四大條件：

1.DWT通濾波器 ${\displaystyle g(n)}$${\displaystyle h(n)}$必須要是有限長度。

2.滿足${\displaystyle h(n)}$是高通濾波器(high pass filter)，${\displaystyle g(n)}$是低通濾波器(low pass filter)。

3.滿足完整重建要條件，${\displaystyle {\binom {G_{1}(z)}{H_{1}(z)}}={\frac {2}{det(H_{m}(z))}}{\binom {H(-z)}{-G(-z)}}}$，其中 ${\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)}$

4.若${\displaystyle g(n)}$${\displaystyle h(n)}$為有限長度，則${\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=\alpha z^{k}}$ ，且 ${\displaystyle k}$ 為奇數。

### 以下介紹兩種完美重建的DWT濾波器：

• ${\displaystyle H(z)=G(-z)}$

${\displaystyle \Longrightarrow }$ ${\displaystyle h(n)=(-1)^{n}g(n)}$

• ${\displaystyle G_{1}(z)=G(z)z^{-k}}$

${\displaystyle \Longrightarrow }$ ${\displaystyle g_{1}(n)=g(n-k)}$

• ${\displaystyle H_{1}(z)=-G(-z)z^{-k}}$

${\displaystyle \Longrightarrow }$ ${\displaystyle h_{1}(n)=(-1)^{n-k+1}g(n-k)}$

${\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}}$，且 ${\displaystyle k}$ 為奇數。

2.Orthonormal Wavelet

• ${\displaystyle G(z)=G_{1}(z^{-1})}$

${\displaystyle \Longrightarrow }$ ${\displaystyle g(n)=g_{1}(-n)}$

• ${\displaystyle H(z)=-z^{k}G_{1}(-z)}$

${\displaystyle \Longrightarrow }$ ${\displaystyle h(n)=(-1)^{n}g_{1}(n+k)}$

• ${\displaystyle H_{1}(z)=-z^{k}G_{1}(-z^{-1})}$

${\displaystyle \Longrightarrow }$ ${\displaystyle h_{1}(n)=(-1)^{n}g_{1}(-n+k)}$

${\displaystyle det(H_{m}(z))=G(z)H(-z)-H(z)G(-z)=2z^{k}}$，且 ${\displaystyle k}$ 為奇數。

## 其他應用

• 邊緣偵測：使用高通濾波器，將小波的低頻濾掉，即保留${\displaystyle x_{1,HL}[m,n]}$${\displaystyle x_{1,LH}[m,n]}$而捨棄其他部分。
• R语言小波分析wavelet
• 作為 JPEG2000 的內部架構
• 模式辨認：由於可以利用低頻的部分得到原圖的縮略版，加上模式通常為整體的特性，藉由在縮略圖上進行工作，小波轉換可以有效減少尋找模式與比對模式的運算時間
• 濾波器設計：小波轉換保留部分時間資訊，可以據此資訊加上訊號的強度資訊，保留特定時點的資訊而同時去除雜訊