哈尔小波转换

哈尔小波转换（英语：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}$$

图示如下：

<image>

## 快速算法

<image>

上图为哈尔小波转换的快速演算简易图示，此为多重解析结构（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.