小波轉換 (Wavelet Transform) @ 拾人牙慧

任意的一個信號皆可由小波轉換的基底的線性組合所合成，而小波轉換：即是算出此信號中，所含有的每一個基底的分量。

預備知識：
正交 (Orthogonal)

傅立葉轉換 (Fourier Transform) vs. 小波轉換 (Wavelet Transform)

傅立葉轉換的基底，是由一組不同頻率且正交的單頻弦波信號所構成，而任意的一個信號皆可由此組基底的線性組合所合成。
傅立葉轉換即是算出此信號所含有每一個基底的分量。
唯傅立葉轉換的基底是週期性的，時間展衍範圍無限大，所以傳立葉轉換的結果無法顯示每一個基底在此信號的時間位置資訊。

小波轉換的基底，是由一組既代表頻率又代表位置的基底所構成，這些基底之間彼此互相存在著放大、縮小和平移的關係。
而任意的一個信號亦皆可由小波轉換的基底的線性組合所合成。
小波轉換即是算出此信號所含有每一個基底的分量。
小波轉換的基底在一維時，具有時間與頻率的資訊，在二維時，具有空間位置和頻率的資訊。

小波轉換理論分析

以 Ψ(t) 代表小波信號的母函數，利用此函數，可以產生小波轉換的所有基底，以 Ψ(t-T / a) 傳表函數 Ψ(t) 在時間軸上放大或縮小 a 位，平移 T 時間的信號，這些信號將構成小波轉換的基底。
若 a > 1，此函數在時間軸放大，即此信號的頻率變低。
若 a < 1，此函數在時間軸縮小，即此信號的頻率變高。

Haar 小波定義為 Ψ_H((t-T) / a)，其中：
Ψ_H(k) = 1, if 0 < k < 1/2
Ψ_H(k) = -1, if 1/2 <= k < 1
Ψ_H(k) = 0, others

則 Ψ_H((t-T) / a) 可構為一組小波基底，Haar 小波是其中之一，其基底的一部份為：
a = 2, T = 0
wavelet_001

a = 4, T = 0
wavelet_002

a = 2, T = 2
wavelet_003

a = 2, T = 4
wavelet_004

由圖可以發現 Haar 小波的特性：

這些小波在時間的延展上有一定的範圍
這些小波的頻率並非完全相同
這些小波兩兩正交

雖然小波基底有無限多個，但針對離散信號，可以作合理的近似，而找到一組含有有限個小波當基底，來完成小波轉換。

以 Haar 小波而言，Ψ_H(t/2) 可視為離散信號能表示的最高頻率成為的一個 Haar 小波信號，因為在 Ψ_H((t-T) / a) 中， 1/a 的最大值是 1/2，可以 2 的次方值，將此頻率變小，即 1/a 可以取 1/2, 1/4, 1/8 …，同理，T 的值可取 0, 2, 4, 8 ...，如此，可重新定義一組離散 Haar 小波基底，這些基底之間彼此兩兩正交：
Ψ_i,m(k) = Ψ_H(2ⁱt - m); i = -1, ..., -∞; m = 0, ..., ∞

設 f(t) 為一一維信號，則此信號可以 Ψ_i,m(k) 線性組合表示成：
f(t) = ΣΣC_i,m * Ψ_i,m(t), 其中 i = -1, ..., -∞; m = 0, ..., ∞
C_i,m 為 f(t) 之一維小波轉換之係數，
接著將上式的兩邊信號和 Ψ_i,m(t) 作內積：
∫f(t) * Ψ_i,m(t) dt = ΣΣC_i,m * Ψ_i,m(t) * Ψ_i,m(t)
由於 Ψ_i,m(t) 中的基底彼此正交的關係 (內積為 0)，接著會變成：
=>∫f(t) * Ψ_i,m(t) dt = C_i,m * Ψ_i,m(t) * Ψ_i,m(t)
=>∫f(t) * Ψ_i,m(t) dt = C_i,m * 2 ^-i
所以：
=>C_i,m = 2 ⁱ * ∫f(t) * Ψ_i,m(t) dt

若假設所處理的對象皆為離散信號，且時間範圍在 (0, 8) 間，最小時間單位為 1，以 x[n] = {1, 2, 3, 4, 3, 2, 2, 2} 表示欲處理之訊號。
在 8 維向量中，以小波轉換來說，其基底有：
φ_-1,0(t) = φ_H(t/2) 表示為 φ₇[n] = {1, -1, 0, 0, 0, 0, 0, 0}
φ_-1,1(t) = φ_H(t/2 - 1) 表示為 φ₆[n] = {0, 0, 1, -1, 0, 0, 0, 0}
φ_-1,2(t) = φ_H(t/2 - 2) 表示為 φ₅[n] = {0, 0, 0, 0, 1, -1, 0, 0}
φ_-1,3(t) = φ_H(t/2 - 3) 表示為 φ₄[n] = {0, 0, 0, 0, 0, 0, 1, -1}
φ_-2,0(t) = φ_H(t/4) 表示為 φ₃[n] = {1, 1, -1, -1, 0, 0, 0, 0}
φ_-2,1(t) = φ_H(t/4 - 1) 表示為 φ₂[n] = {0, 0, 0, 0, 1, 1, -1, -1}
φ_-3,0(t) = φ_H(t/8) 表示為 φ₁[n] = {1, 1, 1, 1, -1, -1, -1, -1}
φ_-4,0(t) = φ_H(t/16) 表示為 φ₀[n] = {1, 1, 1, 1, 1, 1, 1, 1}

其中 Ψ_H(t/16) 已經是直流基底，已無再放大之需要，因為在此時間內皆為直流訊號，即為同一個直流基底。

將 x[n] 以這些小波基底的表示方式為：
x[n] = ΣX[k] * φ_k[n]
= X[0] * φ₀[n] + X[1] * φ₁[n] + X[2] * φ₂[n] +
X[3] * φ₃[n] + X[4] * φ₄[n] + X[5] * φ₅[n] +
X[6] * φ₆[n] + X[7] * φ₇[n]

如果欲求 X[g] 之值，先將 x[n] 與 φ_g[n] 作內積，則：
x[n] * φ_g[n] = {ΣX[k] * φ_k[n]} * φ_g[n]
= X[g] * φ_g[n] * φ_g[n]
因為這些基底之間兩兩正交，故內積為 0 。
所以
=> X[g] = (x[n] * φ_g[n]) / (φ_g[n] * φ_g[n])

若 g = 1，
則 φ₁[n] * φ₁[n]
= (1*1) + (1*1) + (1*1) + (1*1) + ((-1) * (-1)) + ((-1) * (-1)) + ((-1) * (-1)) + ((-1) * (-1))
= 8,
且 x[n] * φ₁[n]
= 1 *1 + 2*1 + 3*1 + 4*1 + 3*(-1) + 2*(-1) + 2*(-1) + 2*(-1)
= 1
可以得到 X[1] = 1 / 8 = 0.125

若 g = 7，
則 φ₇[n] * φ₇[n]
= (1*1) + ((-1) * (-1)) + 0 + 0 + 0 + 0 + 0 + 0
= 2
且 x[n] * φ₇[n]
= 1 *1 + 2*(-1) + 3*0 + 4*0 + 3*0 + 2*0 + 2*0 + 2*0
= -1
可以得到 X[7] = -1 / 2 = -0.5

將小波轉換以矩陣表示為：
[1, 2, 3, 4, 3, 2, 2, 2]^T =

  1   1   1   0   1   0   0   0      (19 / 8)
  1   1   1   0  -1   0   0   0      ( 1 / 8)
  1   1  -1   0   0   1   0   0      (-4 / 4)
  1   1  -1   0   0  -1   0   0   x  ( 1 / 4)
  1  -1   0   1   0   0   1   0      (-1 / 2)
  1  -1   0   1   0   0  -1   0      (-1 / 2)
  1  -1   0  -1   0   0   0   1      ( 1 / 2)
  1  -1   0  -1   0   0   0  -1      ( 0 / 2)

多層次的 Haar 小波轉換

以上例的基底為例，可以發現有 4 種不同的頻率，其中 4 個最高頻為 X[4] ~ X[7]，2個次高頻為 X[2] 及 X[3]，最低頻率為 X[1]，直流成份為 X[0]，利用前面公式，可以觀察出：
X[4+k] = {x[2k] - x[2k+1]} / 2, when k = 0, 1, 2, 3
X[2+k] = {x[4k] + x[4k+1] - x[4k+2] - x[4k+3]} / 4, when k = 0, 1
X[1] = {x[8k+0] + x[8k+1] + x[8k+2] + x[8k+3] - x[8k+4] - x[8k+5] - x[8k+6] - x[8k+7]} / 8
X[0] = {x[0] + x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7]} / 8

再經過觀察，最高頻率和原始信號相關的點有 2 個，次高頻率和原始信號相關的點有 4 個，依此類推，可以假設 a₁[k] 及 b₁[k]：
其中 a₀[k] = x[k]，在 k = 0, 1, 2, 3 時
a₁[k] = {a₀[2k] + a₀[2k+1]} / 2
b₁[k] = {a₀[2k] - a₀[2k+1]} / 2
又此時 b₁[k] 與 X[4+k] 為相等，X[4+k] = b₁[k]
經過第一層處理後，可以得到 8 個點的信號表示為：
{a₁[0], a₁[1], a₁[2], a₁[3], b₁[0], b₁[1], b₁[2], b₁[3]}

可以將 a₁[k] 視為 x[k] 經過低通濾波後，再間隔取點的結果，
b₁[k] 視為 x[k] 經過高通濾波後，再間隔取點的結果。

以同樣的關係，推導下一層，唯第 2 層的輸出，只和 a₁[k] 有關：
a₂[k] = {a₁[2k] + a₁[2k+1]} / 2
b₂[k] = {a₁[2k] - a₁[2k+1]} / 2
= {a₀[4k] + a₀[4k+1] - a₀[4k+2] - a₀[4k+3]} / 4
又此時 b₂[k] 與 X[2+k] 為相等，X[2+k] = b₂[k]，
經過第二層處理後，此 8 個點的信號變成：
{a₂[0], a₂[1], b₂[0], b₂[1], b₁[0], b₁[1], b₁[2], b₁[3]}

在算式中，發現次高頻率的成份，可以由前一層的低通濾波結果係數中求得。
最後，
X[0] = a₃[k] = {a₂[2k] + a₂[2k+1]} / 2
= {a₀[0] + a₀[1] + a₀[2] + a₀[3] + a₀[4] + a₀[5] + a₀[6] + a₀[7]} / 8
X[1] = b₃[k] = {a₂[2k] - a₂[2k+1]} / 2
= {a₀[0] + a₀[1] + a₀[2] + a₀[3] - a₀[4] - a₀[5] - a₀[6] - a₀[7]} / 8
最後的 8 點信號為：
{a₃[0], b₃[0], b₂[0], b₂[1], b₁[0], b₁[1], b₁[2], b₁[3]}
此即為原信號 x[n] 之離散小波轉換。

結論：對於 8 層的信號，只需計算 3 層，即可將所有小波轉換的結果算出來，同理，如果有 N 點之信號，只需計 log₂N 層。
亦即，從第 i 層到第 i+1 層的正小波轉換的關係式為：
a_i+1[k] = {a_i[2k] + a_i[2k+1]} / 2
b_i+1[k] = {a_i[2k] - a_i[2k+1]} / 2

以上述例子中，x[n] = {1, 2, 3, 4, 3, 2, 2, 2} 為例：
a₁[n] = {1.5, 3.5, 2.5, 2}
b₁[n] = {-0.5, -0.5, 0.5, 0}

a₂[n] = {2.5, 2.25}
b₂[n] = {-1, 0.25}

a₃[n] = {2.375}
b₃[n] = {0.125}

X[k] = {2.375, 0.125, -1, 0.25, -0.5, -0.5, 0.5, 0}
其中 2.375 即是 x[k] 之直流值，即是 x[n] 之平均值。
另一種展示多層次小波轉換的方式如下，往下為正小波轉換，往上為反小波轉換：

 1       2      3     4     3     2     2     2
 1.5     3.5    2.5   2     -0.5  -0.5  0.5   0
 2.5     2.25   -1    0.25
 2.375   0.125

二維階層式 Haar 小波轉換

之前介紹的階層式的一維 Haar 小波轉換演算法，執行一次可將一個 N 點的信號 x[n] 轉換成兩個 N/2 的信號 X_L[n] 和 X_H[n]，二維階層式 Haar 小波轉換演算法，可以利用一維階層式演算法求得：
(1) 先針對影像中的每一列，先執行一次一階一維小波轉換
wavelet_011