哈尔小波变换

哈尔小波变换（英语：Haar wavelet）是由数学家哈尔·阿尔弗雷德于1909年所提出的函数变换（英语：Transform theory），是小波变换中最简单的一种变换，也是最早提出的小波变换。他是多贝西小波的于N=2的特例，可称之为D2或db1。

哈尔小波的母小波（mother wavelet）可表示为：

$\psi (t)={\begin{cases}1\quad &0\leq t<1/2,\\-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{aligned}{\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{aligned))$

在所有正交（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]：

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

${\begin{aligned}\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{aligned))$
$\int \psi (t)\psi (4t)\,dt=0$ （证明同上）
$\int \psi (2^{j_{1))t)\psi (2^{j_{2))t)\,dt=0(\forall j_{1}\neq j_{2})$

（2）同一尺度及不同尺度下，小波函数的整数位移之间相互正交（即 $<\psi (t),\psi (t-k)>=\int \psi (t)\psi (t-k)\,dt=0(\forall k\neq 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）简单（Simple）

（2）快速算法（Fast algorithm）

（3）正交（Orthogonal）→可逆（reversible）

（4）结构紧凑（Compact），实（real），奇（odd）

（5）具有一阶消失矩（Vanish moment）

特性

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

（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）

    $\int _{-\infty }^{\infty }2^{m}\psi (2^{m_{1))t-n_{1})\psi (2^{m}t-n)\,dt=\delta (m,m_{1})\delta (n,n_{1})$ 
    $\delta (i,j)={\begin{cases}1&i=j,\\0&{\mbox{i≠j.))\end{cases))$

（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^{m}t-n)\,dt$

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

若 $\mathrm {X} _{w}(n,m)=2^{m/2}\int _{-\infty }^{\infty }x(t)\psi (2^{m}t-n)\,dt$

${\begin{aligned}\mathrm {X} _{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\\&=\mathrm {X} _{w}(n,m)={\sqrt {\frac {1}{2))}(\chi _{w}(2n,m+1)-\chi _{w}(2n+1,m+1))\\\end{aligned))$

图示如下：

快速算法

上图为哈尔小波变换的快速演算简易图示，此为多重解析结构（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$ 做哈尔小波变换的公式为 ${\displaystyle B=HAH^{T))$ ，其中 $A$ 为一 $N\times N$ 的区块且 $H$ 为 $N$ 点的哈尔小波变换。而反哈尔小波变换为 $A=H^{T}BH$ 。以下为 $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))

。

此外，当

{\displaystyle 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

行为

{\displaystyle 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 代码:

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 代码:

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