哈爾小波轉換

哈爾小波轉換（英語：Haar Wavelet Transform）是由數學家阿爾弗雷德·哈爾（Alfred Haar）於1910年在其論文《Zur theorie der orthogonalen funktionensysteme》中首次提出的一種正交函數系統。

作為發展最早且結構最簡單的小波轉換，哈爾小波不僅是一種能反映時變頻譜（time-variant spectrum）的訊號表示法，更為後續的離散小波轉換（Discrete Wavelet Transform, DWT）奠定了核心基礎。

從現代小波理論的觀點來看，哈爾小波轉換實質上就是兩點的多貝西小波轉換（2-point Daubechies wavelet）。

哈爾小波的母小波（mother wavelet）可表示為：

$$\psi(t) = \begin{cases}1 \quad & 0 \leq t < 1/2,\\ <pre> -1 & 1/2 \leq t < 1,\\0 &\mbox{otherwise.}\end{cases}$$

對應的尺度函數（scaling function）可表示為：

$$\phi(t) = \begin{cases}1 \quad & 0 \leq t < 1,\\0 &\mbox{otherwise.}\end{cases}$$

其濾波器（filter）$h[n]$被定義為 $h[n] = \begin{cases}\frac{1}{\sqrt{2}}&\mbox{if n = 0,1}\\0 &\mbox{otherwise}\end{cases}$當$n=0,1$時，濾波器$h[n]$係數非零，此時可以用哈爾小波的濾波器係數及其尺度函數，將母小波函數表示為：

$$\begin{align} \frac{1}{\sqrt{2}}\psi(\left( \frac{t}{2} \right)) & = \sum_{n=-\infty}^{\infty} (-1)^{1-n} h[1-n] \phi(t-n) \\ & = \frac{1}{\sqrt{2}}(\phi(t-1) - \phi(t)) \\ \end{align}$$

在所有正交（orthonormal）小波轉換中，哈爾小波轉換是最簡單的一種轉換，但它並不適合用於較為平滑的函數，因為它只有一個消失矩（Vanishing Moment）。

## 小波母函數

參與變換的小波函數（wavelet function）也叫母小波（mother wavelet）。

小波母函數可以用尺度函數表示：$\psi(t)=\phi(2t)-\phi(2t-1)$

對小波的母函數可以進行伸縮和平移，例如$\psi(2t)$、$\psi(2^{m}t-n)$。

當尺度離散方式選取$a=2^j, j\in\mathbb{Z^+}$時，依據哈爾小波函數的定義，我們可以推出：

（1）不同尺度的小波函數相互正交（即$<\psi(t),\psi(2^{-j}(t))> = \int \psi(t)\psi(2^{-j}(t)) \, dt = 0 ( \forall j \ne 0 )$），例如：

$\begin{align} \int \psi(t)\psi(2t)\, dt &= \int_{0}^{1/2} \psi(2t)\, dt-\int_{1/2}^{1} \psi(2t)\, dt \\ &\stackrel{\tau=2t}{=} \int_{0}^{1} \frac{\psi(\tau)}{2} \, d\tau -\int_{1}^{2} \frac{\psi(\tau)}{2} \, d\tau \\ &= 0 \end{align}$ $\int \psi(t)\psi(4t)\, dt=0$ （證明同上）$\int \psi(2^{j_1}t)\psi(2^{j_2}t)\, dt=0 (\forall j_1 \ne j_2)$

（2）同一尺度及不同尺度下，小波函數的整數位移之間相互正交（即$<\psi(t),\psi(t-k)> = \int \psi(t)\psi(t-k)\, dt = 0(\forall k\ne 0)$），例如：

$\int \psi(t)\psi(t-1)\, dt=0$ $\int \psi(t)\psi(2t-1)\, dt=0$ $\int \psi(t)\psi(2^{m}t-1)\, dt=0$

## 尺度函數

尺度函數（scaling function），以下為尺度函數的簡易圖示：

(1): $\phi(t)$

(2): $\phi(2t),2\phi(2t)=\phi(t)+\psi(t)$

(3): $\psi(2^{m}t-n)$

## 轉換特性分析

### 優點

運算複雜度極低：哈爾轉換最大的特色在於完全不需要進行乘法運算，整體過程僅依賴加法與減法，因此計算速度非常快。

記憶體配置對稱：轉換前後，輸出訊號的點數會與輸入訊號的點數完全相同。

頻率萃取直觀：頻率只被簡單劃分為兩種：全為 1 的低頻成分，以及一半為 1、一半為 -1 的高頻成分。

局部特徵分析：能夠有效地分析訊號在時間軸上的局部特徵。

數學性質優良：具備正交性且完全可逆，並滿足緊湊支撐、實數以及奇對稱等數學條件。

### 缺點

精確度不足：雖然速度快，但哈爾轉換的精確度較低，在處理某些複雜訊號時效果有限。

消失動差極低：哈爾小波的消失矩（vanishing moment）僅為 1。這意味著它無法有效地濾除含有較高次多項式特性的低頻訊號，導致壓縮或分析平滑訊號時的效能不如進階小波。

## 特性

哈爾小波具有如下的特性：

（1）任一函數都可以由$\phi(t),\phi(2t),\phi(4t),\dots,\phi(2^k t),\dots$以及它們的位移函數所組成

（2）任一函數都可以由常函數，$\psi(t),\psi(2t),\psi(4t),\dots,\psi(2^k t),\dots$以及它們的位移函數所組成

（3）正交性（Orthogonal）

```
   <math>\int_{-\infty}^{\infty}2^m\psi(2^{m_1}t-n_1)\psi(2^mt-n)\, dt=\delta(m,m_1)\delta(n,n_1)</math>
   <math>\delta(i,j) = \begin{cases}1&i = j,\\0&\mbox{i≠j.}\end{cases}</math>
```

（4）不同寬度的（不同m）的小波函數和尺度函數之間會有一個關係

- 小尺度的尺度函數可以表示大尺度的尺度函數

$$\phi(t)=\phi(2t)+\phi(2t-1)$$

$$\phi(t-n)=\phi(2t-2n)+\phi(2t-2n-1)$$

$$\phi(2^{m}t-n)=\phi(2^{m+1}t-2n)+\phi(2^{m+1}t-2n-1)$$

- 小尺度的尺度函數可以表示大尺度的小波函數

$$\psi(t)=\phi(2t)-\phi(2t-1)$$

$$\psi(t-n)=\phi(2t-n)-\phi(2t-2n-1)$$

$$\psi(2^{m}t-n)=\phi(2^{m+1}t-n)-\phi(2^{m+1}t-2n-1)$$

（5）可以用m+1的 係數來計算m的係數

若$\chi_w(n,m)=2^{m/2}\int_{-\infty}^{\infty}x(t)\phi(2^mt-n)\, dt$

$$\begin{align} \chi_w(n,m) & = 2^{m/2}\int_{-\infty}^{\infty}x(t)\phi(2^{m+1}t-2n)\, dt+ 2^{m/2}\int_{-\infty}^{\infty}x(t)\phi(2^{m+1}t-2n-1)\, dt \\ & = \sqrt{\frac{1}{2}}(\chi_w(2n,m+1)+\chi_w(2n+1,m+1)) \\ \end{align}$$

若$\Chi_w(n,m)=2^{m/2}\int_{-\infty}^{\infty}x(t)\psi(2^mt-n)\, dt$

$$\begin{align} \Chi_w(n,m) & =2^{m/2}\int_{-\infty}^{\infty}x(t)\phi(2^{m+1}t-2n)\, dt- 2^{m/2}\int_{-\infty}^{\infty}x(t)\phi(2^{m+1}t-2n-1)\, dt\\ & = \Chi_w(n,m)=\sqrt{\frac{1}{2}}(\chi_w(2n,m+1)-\chi_w(2n+1,m+1))\\ \end{align}$$

圖示如下：

## 快速演演算法

上圖為哈爾小波轉換的快速演算簡易圖示，此為多重解析結構（multiresolution analysis）。

## 哈爾轉換

哈爾變換最早是由哈爾在1910年的論文《論正交函數系理論》（Zur Theorie der Orthogonalen Funktionensysteme）中所提出，是一種最簡單又可以反應出時變頻譜（time-variant spectrum）的表示方法。其觀念與傅立葉變換相近。傅立葉變換的原理是利用正弦波與餘弦波來對訊號進行調變；而哈爾變換則是利用哈爾函數來對訊號進行調變。哈爾函數也含有正弦函數系和餘弦函數系所擁有的正交性，也就是說不同的哈爾函數是互相正交的，其內積為零。

以下面的哈爾轉換矩陣為例，我們取第1行和第2行來做內積，得到的結果為零；取第二行和第三行來做內積，得到的結果也是零。依序下去，我們可以發現在哈爾轉換矩陣任取兩行來進行內積的運算，所得到的內積皆為零。

$N=2$，$H=\begin{bmatrix} \ 1 & 1 \\ \ 1 & -1\\ \end{bmatrix}$。

$N=4$，$H=\begin{bmatrix} \ 1 & 1 & 1 & 1 \\ \ 1 & 1 & -1 & -1\\ \ 1 & -1 & 0 & 0 \\ \ 0 & 0 & 1 & -1 \\ \end{bmatrix}$。

$N=8$，$H=\begin{bmatrix} \ 1 & 1 & 1 & 1 & 1 & 1 & 1& 1\\ \ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1\\ \ 1 & 1 & -1 & -1 & 0 & 0 & 0 & 0\\ \ 0 & 0 & 0 & 0 & 1 & 1 & -1 & -1\\ \ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0\\ \ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0\\ \ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0\\ \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1\\ \end{bmatrix}$。

在此前提下，利用傅立葉變換的觀念，假設所要分析的訊號可以使用多個頻率與位移不同的哈爾函數來組合而成。進行哈爾變換時，因為哈爾函數的正交性，便可求出訊號在不同哈爾函數（不同頻率）的情況下所占有的比例。

哈爾變換有以下幾點特性：

- 不需要乘法（只有相加或加減）
- 輸入與輸出個數相同
- 頻率只分為低頻（直流值）與高頻（1和-1）部分
- 可以分析一個訊號的局部特徵
- 運算速度極快，但不適合用於訊號分析
- 大部分運算為0，不用計算
- 維度小，計算時需要占用的記憶體空間少
- 因為大部分為高頻，轉換較籠統

對一矩陣$A$做哈爾小波轉換的公式為$B=HAH^T$，其中$A$為一$N\times N$的區塊且$H$為$N$點的哈爾小波轉換。而反哈爾小波轉換為$A=H^TBH$。以下為$H$在2、4及8點時的值：

$N=2$，$H=\begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix}$。

$N=4$，$H=\begin{bmatrix} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2}\\ \frac{1}{2} & \frac{1}{2} & \frac{-1}{2} & \frac{-1}{2}\\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0\\ 0 & 0 &\frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}}\\ \end{bmatrix}$。

$N=8$，$H=\begin{bmatrix} \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}}\\ \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{1}{\sqrt{8}} & \frac{-1}{\sqrt{8}} & \frac{-1}{\sqrt{8}} & \frac{-1}{\sqrt{8}} & \frac{-1}{\sqrt{8}}\\ \frac{1}{2} & \frac{1}{2} & \frac{-1}{2} & \frac{-1}{2} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{-1}{2} & \frac{-1}{2}\\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}}\\ \end{bmatrix}$。

此外，當$N=2^k$時，$H=\begin{bmatrix} \phi\\ h_{0,0}\\ h_{1,0}\\ h_{1,1}\\ :\\ :\\ h_{k-1,0}\\ h_{k-1,1}\\ :\\ h_{k-1,2^{k-1}-1}\\ \end{bmatrix}$。其中$H$除了第0行為$\phi$（$\phi$=1 1 1 ... 1/$\sqrt{N}$，共N個1），第$2^p+q$行為$h_{p,q}$且

$h_{p,q}[n] = \begin{cases} 1/\sqrt{2^{k-p}},\ when\ q2^{k-p}\leq n<(q+1/2)2^{k-p} \\-1/\sqrt{2^{k-p}},\ when\ (q+1/2)2^{k-p}\leq n<(q+1)2^{k-p}\\0, otherwise\end{cases}$。

Matlab 代碼:

```matlab
function [Hr]=haar_matrix(N, normalized)
   % Input :
   %     N : size of matrix, N must be power of 2.
   % Output:
   %    Hr : Haar matrix of size NxN
   p=[0 0];
   q=[0 1];
   n=nextpow2(N);

   for i=1:n-1
       p=[p i*ones(1,2^i)];
       t=1:(2^i);
       q=[q t];
   end

   Hr=zeros(N,N);
   Hr(1,:)=1;
   for i=2:N
       P=p(1,i); Q=q(1,i);
       for j= (N*(Q-1)/(2^P)):(N*((Q-0.5)/(2^P))-1)
           Hr(i,j+1)=2^(P/2);
       end
       for j= (N*((Q-0.5)/(2^P))):(N*(Q/(2^P))-1)
           Hr(i,j+1)=-(2^(P/2));
       end
   end
   if normalized
       Hr=Hr*(1/sqrt(N));
   end
end
```

```
 '''Python 代码:'''
```

```python
def haarMatrix(n, normalized=False):
    # Allow only size n of power 2
    n = 2**np.ceil(np.log2(n))
    if n > 2:
        h = haarMatrix(n / 2)
    else:
        return np.array([[1, 1], [1, -1]])

    # calculate upper haar part
    h_n = np.kron(h, [1, 1])
    # calculate lower haar part
    if normalized:
        h_i = np.sqrt(n/2)*np.kron(np.eye(len(h)), [1, -1])
    else:
        h_i = np.kron(np.eye(len(h)), [1, -1])
    # combine parts
    h = np.vstack((h_n, h_i))
    return h
```

## 哈爾小波逆轉換（反哈爾轉換）

哈爾小波逆轉換（Inverse Haar Wavelet Transform）的目的，是將轉換後的小波係數（包含低頻平均訊號與各個尺度的高頻細節訊號），重新還原為原始的時間域訊號。在數位訊號處理實務中，反轉換主要有兩種實現方式：矩陣乘法運算法與多解析度分析（MRA）快速逆演演算法。

### 矩陣乘法運算法

假設輸入訊號長度為 $N = 2^k$。已知哈爾順轉換的矩陣公式為：

$$y = H_N \cdot x$$

其中 $x$ 為原始訊號向量，$H_N$ 為哈爾轉換矩陣，$y$ 為小波係數向量。逆轉換便是要求得其反矩陣以還原訊號：

$$x = H_N^{-1} \cdot y$$

由於哈爾轉換矩陣具備正交特性，其反矩陣可以透過轉置矩陣 $H_N^T$ 與一個特製的對角權重矩陣 $D$ 相乘而得：

$$H_N^{-1} = H_N^T \cdot D$$

#### 對角權重矩陣 D 的建構規則

對角矩陣 $D[m, n]$ 僅在主對角線（$m=n$）上有值，其餘元素皆為 0。其主對角線上的數值取決於係數所在的頻帶（尺度層級）：

- $D[1,1] = 2^{-k}$ （對應總平均的低頻成分）
- $D[2,2] = 2^{-k}$ （對應最大尺度的高頻細節成分）
- 當滿足 $2^p < n \le 2^{p+1}$ 時，$D[n,n] = 2^{-k+p}$（其中 $p$ 代表小波的尺度層級，$p = 0, 1, \dots, k-1$）。

#### 以 N = 4 (k = 2) 為例的詳細推導

當訊號長度 $N=4$ 時，哈爾順轉換矩陣 $H_4$ 為：

$$H_4 = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{bmatrix}$$

對應的轉置矩陣 $H_4^T$ 為：

$$H_4^T = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & -1 & 0 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & 0 & -1 \end{bmatrix}$$

根據對角矩陣 $D$ 的建構規則（此處 $k=2$）：

- $$D[1,1] = 2^{-2} = \frac{1}{4}$$
- $$D[2,2] = 2^{-2} = \frac{1}{4}$$
- 當 $2^1 < n \le 2^2$（即 $n=3, 4$，此時尺度層級 $p=1$）：$D[3,3] = D[4,4] = 2^{-2+1} = 2^{-1} = \frac{1}{2}$

因此，權重對角矩陣 $D$ 為：

$$D = \begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ 0 & \frac{1}{4} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \end{bmatrix}$$

將轉置矩陣 $H_4^T$ 與對角矩陣 $D$ 相乘，即可求得完整的逆轉換矩陣 $H_4^{-1}$：

$$H_4^{-1} = H_4^T D = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 1 & -1 & 0 \\ 1 & -1 & 0 & 1 \\ 1 & -1 & 0 & -1 \end{bmatrix} \begin{bmatrix} \frac{1}{4} & 0 & 0 & 0 \\ 0 & \frac{1}{4} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} \frac{1}{4} & \frac{1}{4} & \frac{1}{2} & 0 \\ \frac{1}{4} & \frac{1}{4} & -\frac{1}{2} & 0 \\ \frac{1}{4} & -\frac{1}{4} & 0 & \frac{1}{2} \\ \frac{1}{4} & -\frac{1}{4} & 0 & -\frac{1}{2} \end{bmatrix}$$

最終，將小波係數向量 $y = [y_1, y_2, y_3, y_4]^T$ 代入矩陣乘法，即可完全還原原始訊號 $x = [x_1, x_2, x_3, x_4]^T$：

$$x_1 = \frac{1}{4}y_1 + \frac{1}{4}y_2 + \frac{1}{2}y_3$$

$$x_2 = \frac{1}{4}y_1 + \frac{1}{4}y_2 - \frac{1}{2}y_3$$

$$x_3 = \frac{1}{4}y_1 - \frac{1}{4}y_2 + \frac{1}{2}y_4$$

$$x_4 = \frac{1}{4}y_1 - \frac{1}{4}y_2 - \frac{1}{2}y_4$$

### 快速逆演演算法（多解析度分析重建）

在硬體實現或處理大型訊號時，通常會避免直接進行大矩陣的乘法，轉而採用遞迴架構的合成濾波器組（Synthesis Filter Bank）來進行快速重建。

#### 遞迴重建原理

在順轉換（分解）過程中，相鄰尺度層級（$m$ 與 $m+1$）的低頻平均係數 $\chi_w$ 與高頻細節係數 $X_w$ 的關係式如下：

$$\chi_w(n,m) = \sqrt{\frac{1}{2}}\left(\chi_w(2n,m+1) + \chi_w(2n+1,m+1)\right)$$

$$X_w(n,m) = \sqrt{\frac{1}{2}}\left(\chi_w(2n,m+1) - \chi_w(2n+1,m+1)\right)$$

透過解此聯立方程式，可以反向推導出如何由較粗糙層級（$m$）的係數，重建出下一層較精細層級（$m+1$）的低頻成分：

$$\chi_w(2n,m+1) = \sqrt{\frac{1}{2}}\left(\chi_w(n,m) + X_w(n,m)\right)$$

$$\chi_w(2n+1,m+1) = \sqrt{\frac{1}{2}}\left(\chi_w(n,m) - X_w(n,m)\right)$$

#### 逐層重建流程

以長度為 8 的訊號為例，其小波係數依頻帶排列。重建過程將從小波分解的最底層開始，採類似蝴蝶架構的遞迴方式逐層向外恢復：

- 第一階段（重建至尺度 $m=1$）：利用總平均低頻係數 $\chi_w(0,0)$ 與該層高頻細節係數 $X_w(0,0)$，還原出下一層的兩個低頻成分 $\chi_w(0,1)$ 與 $\chi_w(1,1)$。
- 第二階段（重建至尺度 $m=2$）：將上一步求得的 $\chi_w(0,1)$ 與 $\chi_w(1,1)$，分別與對應的高頻細節係數 $X_w(0,1)$ 及 $X_w(1,1)$ 結合，重構出 4 個點的低頻成分 $\chi_w(0,2), \dots, \chi_w(3,2)$。
- 第三階段（還原至原始訊號）：將這 4 個低頻成分再與最高頻的 4 個細節係數相結合，即可最終完整復原出原始的時間域 8 點訊號。

這種遞迴架構使得反轉換的計算複雜度降低至 $O(N)$，顯著優於矩陣乘法的運算效率。

### 程式碼實作

#### Python

```python
import numpy as np

def inverse_haar_transform_matrix(y):
    y = np.asarray(y).flatten()
    N = len(y)
    k = int(np.log2(N))

    H = np.zeros((N, N))
    D = np.zeros((N, N))

    H[0, :] = 1
    D[0, 0] = 2**(-k)

    if N > 1:
        H[1, :N//2] = 1
        H[1, N//2:] = -1
        D[1, 1] = 2**(-k)

    for p in range(1, k):
        for q in range(1, 2**p + 1):
            row = 2**p + q - 1
            start_idx = int((q - 1) * 2**(k - p))
            mid_idx = int((q - 0.5) * 2**(k - p))
            end_idx = int(q * 2**(k - p))

            H[row, start_idx:mid_idx] = 1
            H[row, mid_idx:end_idx] = -1
            D[row, row] = 2**(-k + p)

    H_inv = H.T @ D
    x = H_inv @ y
    return x
```

#### MATLAB

```matlab
function x = inverse_haar_transform_matrix(y)
    y = y(:);
    N = length(y);
    k = log2(N);

    H = zeros(N, N);
    D = zeros(N, N);

    H(1, :) = 1;
    D(1, 1) = 2^(-k);

    if N > 1
        H(2, 1:N/2) = 1;
        H(2, N/2+1:end) = -1;
        D(2, 2) = 2^(-k);
    end

    for p = 1:(k-1)
        for q = 1:2^p
            row = 2^p + q;
            start_idx = (q - 1) * 2^(k - p) + 1;
            mid_idx = (q - 0.5) * 2^(k - p);
            end_idx = q * 2^(k - p);

            H(row, start_idx:mid_idx) = 1;
            H(row, mid_idx+1:end_idx) = -1;
            D(row, row) = 2^(-k + p);
        end
    end

    H_inv = H' * D;
    x = H_inv * y;
end
```

## 哈爾小波轉換應用於圖像壓縮

### 說明

由於數位圖片檔案過大，因此我們往往會對圖片做圖像壓縮，壓縮過後的檔案大小不僅存放於電腦中不會佔到過大容量，也方便我們於網路上傳送。哈爾小波轉換其中一種應用便是用來壓縮圖像。壓縮圖像的基本概念為將圖像存成到一矩陣，例如256x256大小的圖片會存成256x256大小的矩陣，矩陣中的每一元素則代表是每一圖像的某畫素值，介於0到255間。JPEG影像壓縮的概念為先將圖像切成8x8大小的區塊，每一區塊為一8x8的矩陣。示意圖可見右圖。

在處理8x8二維矩陣前，先試著對一維矩陣$r=\begin{bmatrix}1.2\\1.2\\1.8\\0.8\\2\\2\\1.9\\2.1 \end{bmatrix}$作哈爾小波轉換。

公式為$r_1=Hr=\begin{bmatrix}13/\sqrt{8}\ (4.596)\\-3/\sqrt{8}\ (-1.061)\\-0.1\ (-0.1)\\0\\0\\1/\sqrt{2}\ (0.707)\\0\\-0.2/\sqrt{2}\ (-0.141)\end{bmatrix}\approx \begin{bmatrix}13/\sqrt{8}\\-3/\sqrt{8}\\0\\0\\0\\1/\sqrt{2}\\0\\0 \end{bmatrix}$。

### 範例

對8x8的二維矩陣A作哈爾小波轉換，由於$AH$是對$A$的每一列作哈爾小波轉換，作完後還要對$A$的每一行作哈爾小波轉換，因此公式為$H^TAH$。以下為一簡單的例子：

$A=\begin{bmatrix}576 & 704& 1152 & 1280 & 1344 & 1472 & 1536 & 1536\\ 704 & 640 & 1156 & 1088 & 1344 & 1408 & 1536 & 1600\\ 768 & 832 & 1216 & 1472 & 1472 & 1536 & 1600 & 1600\\ 832 & 832 & 960 & 1344 & 1536 & 1536 & 1600 & 1536\\ 832 & 832 & 960 & 1216 & 1536 & 1600 & 1536 & 1536\\ 960 & 896 & 896 & 1088 & 1600 & 1600 & 1600 & 1536\\ 768 & 768 & 832 & 832 & 1280 & 1472 & 1600 & 1600\\ 448 & 768 & 704 & 640 & 1280 & 1408 & 1600 & 1600\\\end{bmatrix}$。

列哈爾小波轉換（row Haar wavelet transform）

$L=AH=\begin{bmatrix} 1200 & -272 & -288 & -64 & -64 & -64 & -64 & 0\\ 1185 & -288 & -225 & -96 & 32 & 34 & -32 & -32\\ 1312 & -240 & -272 & -48 & -32 & -128 & -32 & 0\\ 1272 & -280 & -160 & -16 & 0 & -192 & 0 & 32\\ 1256 & -296 & -128 & 16 & 0 & -128 & -32 & 0\\ 1272 & -312 & -32 & 16 & 32 & -96 & 0 & 32\\ 1144 & -344 & -32 & -112 & 0 & 0 & -96 & 0\\ 1056 & -416 & -32 & -128 & 160 & 32 & -64 & 0\\ \end{bmatrix}$。

行哈爾小波轉換（column Haar wavelet transform）

$S=H^TL=\begin{bmatrix}1212 & -306 & -146 & -54 & -24 & -68 & -40 & 4\\ 30 & 36 & -90 & -2 & 8 & -20 & 8 & -4\\ -50 &-10 & -20 & -24 & 0 & 72 & -16 & -16\\ 82 & 38 & -24 & 68 & 48 & -64 & 32 & 8\\ 8 & 8 & -32 & 16 & -48 & -48 & -16 & 16\\ 20 & 20 & -56 & -16 & -16 & 32 & -16 & -16\\ -8 & 8 & -48 & 0 & -16 & -16 & -16 & -16\\ 44 & 36 & 0 & -8 & 80 & -16 & -16 & 0\\ \end{bmatrix}$。

由以上例子可以看出哈爾小波轉換的效果，原本矩陣中變化量不大的元素經過轉換後會趨近零，再配合適當量化便可以達到壓縮的效果了。此外若一矩陣作完哈爾小波轉換後所含的零元素非常多的話，稱此矩陣為稀疏矩陣，若一矩陣越稀疏壓縮效果越好。因此可對定一臨界值$\epsilon$，若矩陣中元素的絕對值小於此臨界值$\epsilon$，將該元素置零，可得到更大的壓縮率。然而$\epsilon$取過大的話會造成圖像嚴重失真，因此如何取適當的$\epsilon$也是值得討論的議題。

## 哈爾小波轉換運算量比沃爾什轉換更少

若應用於區域的頻譜分析及偵測邊緣的話，離散傅立葉變換、Walsh-Hadamard變換及哈爾小波轉換的計算量見下表

運行時間｜為使NRMSE < $10^{-5}$所需要的項數量

離散傅立葉變換｜9.5秒｜43

沃爾什轉換｜2.2秒｜65

哈爾小波轉換｜0.3秒｜128

## 與其他轉換的比較

### 與離散傅立葉轉換的比較

在處理效率上，哈爾轉換具備絕對優勢。例如在相同資料量的測試下，哈爾轉換僅需 0.3 秒，而離散傅立葉轉換（DFT）則需要 9.5 秒。

然而，在訊號重建的精確度上，若要求正規化均方根誤差（NRMSE）小於 $10^{-5}$，哈爾轉換需要保留 128 項係數，而 DFT 卻僅需 43 項即可達成相同的誤差標準。

### 與多貝西小波的關係

多貝西小波（Daubechies Wavelet）可以被視為哈爾小波的推廣形式（generalization）。

相對地，哈爾小波即為最基礎的 2 點多貝西小波（2-point Daubechies wavelet）。

在濾波器係數的表現上，哈爾小波的低頻生成係數（$g_k$）為 $g[0]=1, g[1]=1$（或 $1/2, 1/2$），而高頻係數（$h_k$）則對應為 $h[0]=1, h[1]=-1$（或 $1/2, -1/2$）。

## 參考

- Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2026.
- Jian-Jiun Ding, Time frequency analysis and wavelet transform class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2007.
- Joseph Khoury, Application to image compression, http://aix1.uottawa.ca/~jkhoury/haar.htm
- Lokenath Debnath, Wavelet Transforms and Their Application,Birkhauser, Boston,USA, 2002.
- Charles K. Chui, Wavelets：A Tutorial in Theory and Applications,ACADEMIC PRESS,San Diego,USA, 1992.
- Wavelets and subbands : fundamentals and applications/Agostino Abbate, Casimer M. DeCusatis, Pankaj K. Das.