個人博客！無廣告觀看，因為這節內容太多了，有點放不下，分了三節

快速小波變換(The Fast Wavelet Transform)

實現DWT的快速實現。

再次考慮MRA方程:
$$\phi (x)=\sum _n{h}_{\phi }(n)\sqrt{2}\phi (2x?n)$$
將$x$乘以$2^j$，平移$k$，并令$m=2k+n$，得到 :
$$\begin{array}{rl}\phi (2^{j}x?k)& =\sum _n{h}_{\phi }(n)\sqrt{2}\phi (2(2^{j}x?k)?n)\\ & =\sum _n{h}_{\phi }(n)\sqrt{2}\phi (2^{j+1}x?2k?n)\\ & =\sum _m{h}_{\phi }(m?2k)\sqrt{2}\phi (2^{j+1}x?m)\end{array}\text{\hspace{1em}?}$$
對于小波函數，有類似結果：
$$\psi (2^{j}x?k)=\sum _m{h}_{\psi }(m?2k)\sqrt{2}\phi (2^{j+1}x?m)$$
對于離散小波函數，有：
$$W_{\psi }(j,k)=\frac{1}{\sqrt{M}}\sum _{x}f(x)2^{j/2}\psi (2^{j}x?k)$$
進一步，有：
$$W_{\psi }(j,k)=\frac{1}{\sqrt{M}}\sum _{x}f(x)2^{j/2}\left[\sum _m{h}_{\psi }(m?2k)\sqrt{2}\phi (2^{j+1}x?m)\right]$$
交換求和與積分并重新排列項，得到 ：
$$\begin{gathered} W_{\psi }(j,k)=\sum _m{h}_{\psi }(m?2k)\left[\frac{1}{\sqrt{M}}\sum _{x}f(x)2^{(j+1)/2}\phi (2^{j+1}x?m)\right] \\ {W}_{\psi }(j,k)=\sum _m{h}_{\psi }(m?2k)W_{\phi }(j+1,m) \\ 同理,W_{\phi }(j,k)=\sum _m{h}_{\phi }(m?2k)W_{\phi }(j+1,m) \end{gathered}$$
上述方程表示了快速小波變換(FWT), 揭示了相鄰尺度的離散小波變換（DWT）系數之間的顯著關系。

可以看到，尺度$j$的近似系數$W_{\phi }(j,k)$和細節系數$W_{\psi }(j,k)$都可以通過將尺度$j+1$的近似系數$W_{\phi }(j+1,k)$與時間反轉的縮放向量$h_{\phi }(?n)$和小波向量$h_{\psi }(?n)$進行卷積，并對結果進行下采樣得到。

與兩頻段子帶編譯碼系統的關系

Q: 兩頻段子帶編譯碼系統?

A: 是一種將信號分解為低頻和高頻子帶的系統

1. 低通通道（Low-Pass Channel）：對應于尺度濾波器 $h_{\phi }(n)$，用于提取信號的低頻成分。
2. 高通通道（High-Pass Channel）：對應于小波濾波器 $h_{\psi }(n)$，用于提取信號的高頻成分。

∑ k g 0 ( k ) h 0 ( n ? k ) + ( ? 1 ) n ∑ k g 0 ( k ) h 0 ( n ? k ) = 2 δ ( n ) ， δ ( n ) = { 1 , n = 0 0 , n ≠ 0 ∑ k g 0 ( k ) h 0 ( 2 n ? k ) = ? g 0 ( k ) , h 0 ( 2 n ? k ) ? = δ ( n ) ? h i ( 2 n ? k ) , g j ( k ) ? = δ ( i ? j ) δ ( n ) i , j ∈ { 0 , 1 } \sum_{k}g_{0}(k)h_{0}(n - k)+(-1)^{n}\sum_{k}g_{0}(k)h_{0}(n - k)=2\delta(n)，\delta{(n)}=\begin{cases}1 ,&n=0\\0, &n\neq 0\end{cases}\\ \sum_{k}g_{0}(k)h_{0}(2n - k)=\langle g_{0}(k),h_{0}(2n - k)\rangle=\delta(n)\\ \langle h_{i}(2n - k),g_{j}(k)\rangle=\delta(i - j)\delta(n)\quad i,j\in\{0,1\} k∑?g0?(k)h0?(n?k)+(?1)nk∑?g0?(k)h0?(n?k)=2δ(n)，δ(n)={1,0,?n=0n=0?k∑?g0?(k)h0?(2n?k)=?g0?(k),h0?(2n?k)?=δ(n)?hi?(2n?k),gj?(k)?=δ(i?j)δ(n)i,j∈{0,1}

上述快速小波變換過程與兩頻段子帶編譯碼系統的分析部分相同，其中:
$$\begin{gathered} h_0(n)=h_{\phi }(?n) \\ {h}_1(n)=h_{\psi }(?n) \end{gathered}$$
可以寫出 :
$$\begin{gathered} W_{\psi }(j,k)=h_{\psi }(?n)?W_{\phi }(j+1,n){|}_{n=2k,k\ge 0} \\ {W}_{\phi }(j,k)=h_{\phi }(?n)?W_{\phi }(j+1,n){|}_{n=2k,k\ge 0} \end{gathered}$$
其中卷積在$n=2k(k\ge 0)$時刻進行求值。在非負、偶數時刻，計算卷積與以2為步長進行過濾和抽樣的效果相同。

值得注意的是，濾波器組可以“迭代”以創建多級結構，用于計算兩個或多個連續尺度的 DWT 系數，如圖所示。

例：計算一維小波變換

與上面的例子同： f ( n ) = { 1 , 4 , ? 3 , 0 } f(n)=\{1,4,-3,0\} f(n)={1,4,?3,0}, 但現在使用相應的尺度和小波向量：
$$

h_{\varphi}(n)=\begin{cases}\frac{1}{\sqrt{2}},&n=0,1\0,& otherwise\end{cases}\\
h_{\psi}(n)=\begin{cases}\frac{1}{\sqrt{2}},&n=0\-\frac{1}{\sqrt{2}},&n=1\0,& otherwise\end{cases}
$$
這是用于建立FWT濾波器族的函數，它們給出了濾波器系數。

一維快速小波反變換

上采樣序列定義為：
$$y_{2\uparrow }(n)=\{\begin{array}{ll}y(n/2),& n是偶數\\ 0,& 其他\end{array}$$
其中$y(n)$是一維取樣序列，上采樣因子為2。因子2上取樣可以被視為在$y(n)$的每個樣本后插入一個0.

例：計算一維小波反變換

快速小波反變換的計算與正變換的計算呈鏡像關系。在開始計算之前，先對0級近似系數和細節系數進行上取樣，分別得到{4,0},{1,0},然后繼續向右移動，卷積，最終可以得到$f(x)=T_{\phi }(2,n)$.

FFT與FWT的區別

• 計算長度為$M=2^j$序列的FWT所涉及的數學運算量為$O(M)$階。
• 這與FFT算法相比具有優勢，FFT算法需要$O(M\log M)$。
• 雖然傅里葉基函數（即正弦函數）保證了FFT的存在，但FWT的存在取決于所使用小波的縮放函數的可用性，以及縮放函數和相應小波的正交性（或雙正交性）。
• FFT無法同時在時間和頻率上分析函數，但FWT可以。

小波包(Wavelet Packets)

快速小波變換（FWT）將函數分解為尺度和小波函數之和，其中尺度和小波函數的帶框呈對數關系。也就是說，函數的低頻內容被分組到窄頻帶(尺度和小波函數)中，而高頻內容被分組到較寬的頻帶(尺度和小波函數)中。

如果我們想要對時頻平面的劃分進行更精細的控制，FWT必須被推廣以產生一種更靈活的分解——稱為小波包。

分析樹

根節點被賦予最高尺度的近似系數，這些系數是函數本身的樣本，而葉子節點繼承變換的近似和細節系數輸出。注意：每個節點的系數都是線性展開的權重。

例：三尺度分析樹

例如，上圖中的三尺度分析樹提供了以下三種展開選項：
$$\begin{array}{rl}{V}_j& =V_{j?1}\oplus W_{j?1}\\ V_j& =V_{j?2}\oplus W_{j?2}\oplus W_{j?1}\\ V_j& =V_{j?3}\oplus W_{j?3}\oplus W_{j?2}\oplus W_{j?1}\end{array}\text{\hspace{1em}?}$$
其中 $\oplus$表示空間的直和（類似于集合的并集）。

分析樹也是表示小波包的一種有效機制，小波包不過是對細節進行迭代濾波的常規小波變換。因此，上圖(b)中的三尺度FWT分析樹變成了下圖中的三尺度小波包樹。

$A$表示近似濾波、$D$表示細節濾波。圖中的小波包樹支持26種不同的分解。例如，$V_j$可以展開為:
$$\begin{gathered} V_J=V_{J?3}\oplus W_{J?3}\oplus W_{J?2,A}\oplus W_{J?2,D}\oplus W_{J?1,AA}\oplus W_{J?1,AD}\oplus W_{J?1,DA}\oplus W_{J?1,DD} \\ {V}_J=V_{J?1}\oplus W_{J?1,D}\oplus W_{J?1,AA}\oplus W_{J?1,AD} \end{gathered}$$

一般來說，$P$尺度的一維小波包變換（以及相關的$P+1$級分析樹）支持:
$$D(P+1)=[D(P){]}^2+1$$
種獨特的分解，其中$D(1)=1$。

lign}
V_j& = V_{j - 1} \oplus W_{j - 1}\
V_j &= V_{j - 2} \oplus W_{j - 2} \oplus W_{j - 1}\
V_j &= V_{j - 3} \oplus W_{j - 3} \oplus W_{j - 2} \oplus W_{j - 1}
\end{align}
$$
其中 $\oplus$表示空間的直和（類似于集合的并集）。

分析樹也是表示小波包的一種有效機制，小波包不過是對細節進行迭代濾波的常規小波變換。因此，上圖(b)中的三尺度FWT分析樹變成了下圖中的三尺度小波包樹。

[外鏈圖片轉存中…(img-D1xm8JZn-1735127696455)]

$A$表示近似濾波、$D$表示細節濾波。圖中的小波包樹支持26種不同的分解。例如，$V_j$可以展開為:
$$\begin{gathered} V_J=V_{J?3}\oplus W_{J?3}\oplus W_{J?2,A}\oplus W_{J?2,D}\oplus W_{J?1,AA}\oplus W_{J?1,AD}\oplus W_{J?1,DA}\oplus W_{J?1,DD} \\ {V}_J=V_{J?1}\oplus W_{J?1,D}\oplus W_{J?1,AA}\oplus W_{J?1,AD} \end{gathered}$$
[外鏈圖片轉存中…(img-zdaG9cvw-1735127696455)]

[外鏈圖片轉存中…(img-oieYA8Vt-1735127696456)]

一般來說，$P$尺度的一維小波包變換（以及相關的$P+1$級分析樹）支持:
$$D(P+1)=[D(P){]}^2+1$$
種獨特的分解，其中$D(1)=1$。