哈尔小波变换

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

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

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

对应的尺度函数（scaling function）可表示为：

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

其滤波器（filter）${\displaystyle h[n]}$被定义为
${\displaystyle h[n]={\begin{cases}{\frac {1}{\sqrt {2}}}&{\mbox{if n = 0,1}}\\0&{\mbox{otherwise}}\end{cases}}}$
当${\displaystyle n=0,1}$时，滤波器${\displaystyle h[n]}$系数非零，此时可以用哈尔小波的滤波器系数及其尺度函数，将母小波函数表示为：

${\displaystyle {\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）。

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

对小波的母函数可以进行伸缩和平移，例如${\displaystyle \psi (2t)}$、${\displaystyle \psi (2^{m}t-n)}$。

当尺度离散方式选取${\displaystyle a=2^{j},j\in \mathbb {Z^{+}} }$时，依据哈尔小波函数的定义，我们可以推出^[1]：

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

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

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

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

尺度函数

尺度函数（scaling function），以下为尺度函数的简易图示：

(1): ${\displaystyle \phi (t)}$

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

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

优点

（1）简单（Simple）

（2）快速算法（Fast algorithm）

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

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

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

特性

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

（1）任一函数都可以由${\displaystyle \phi (t),\phi (2t),\phi (4t),\dots ,\phi (2^{k}t),\dots }$以及它们的位移函数所组成

（2）任一函数都可以由常函数，${\displaystyle \psi (t),\psi (2t),\psi (4t),\dots ,\psi (2^{k}t),\dots }$以及它们的位移函数所组成

（3）正交性（Orthogonal）

   ${\displaystyle \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})}$
   ${\displaystyle \delta (i,j)={\begin{cases}1&i=j,\\0&{\mbox{i≠j.}}\end{cases}}}$

（4）不同宽度的（不同m）的小波函数和尺度函数之间会有一个关系

• 小尺度的尺度函数可以表示大尺度的尺度函数

${\displaystyle \phi (t)=\phi (2t)+\phi (2t-1)}$

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

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

• 小尺度的尺度函数可以表示大尺度的小波函数

${\displaystyle \psi (t)=\phi (2t)-\phi (2t-1)}$

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

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

（5）可以用m+1的 系数来计算m的系数

若${\displaystyle \chi _{w}(n,m)=2^{m/2}\int _{-\infty }^{\infty }x(t)\phi (2^{m}t-n)\,dt}$

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

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

${\displaystyle {\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行来做内积，得到的结果为零；取第二行和第三行来做内积，得到的结果也是零。依序下去，我们可以发现在哈尔变换矩阵任取两行来进行内积的运算，所得到的内积皆为零。

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

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

${\displaystyle N=8}$，${\displaystyle 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. 不需要乘法（只有相加或加减）
2. 输入与输出个数相同
3. 频率只分为低频（直流值）与高频（1和-1）部分
4. 可以分析一个信号的局部特征
5. 运算速度极快，但不适合用于信号分析
6. 大部分运算为0，不用计算
7. 维度小，计算时需要占用的内存空间少
8. 因为大部分为高频，变换较笼统

对一矩阵${\displaystyle A}$做哈尔小波变换的公式为${\displaystyle B=HAH^{T}}$，其中${\displaystyle A}$为一${\displaystyle N\times N}$的区块且${\displaystyle H}$为${\displaystyle N}$点的哈尔小波变换。而反哈尔小波变换为${\displaystyle A=H^{T}BH}$。以下为${\displaystyle H}$在2、4及8点时的值：

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

${\displaystyle N=4}$，${\displaystyle 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}}}$。

${\displaystyle N=8}$，${\displaystyle 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}}$时，${\displaystyle 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}}}$。其中${\displaystyle H}$除了第0行为${\displaystyle \phi }$（${\displaystyle \phi }$=[1 1 1 ... 1]/${\displaystyle {\sqrt {N}}}$，共N个1），第${\displaystyle 2^{p}+q}$行为${\displaystyle h_{p,q}}$且

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

哈尔小波变换应用于图像压缩

说明

由于数字图片档案过大，因此我们往往会对图片做图像压缩，压缩过后的档案大小不仅存放于电脑中不会占到过大容量，也方便我们于网络上传送。哈尔小波变换其中一种应用便是用来压缩图像。压缩图像的基本概念为将图像存成到一矩阵，例如256x256大小的图片会存成256x256大小的矩阵，矩阵中的每一元素则代表是每一图像的某画素值，介于0到255间。JPEG影像压缩的概念为先将图像切成8x8大小的区块，每一区块为一8x8的矩阵。示意图可见右图。

在处理8x8二维矩阵前，先试着对一维矩阵${\displaystyle r={\begin{bmatrix}1.2\\1.2\\1.8\\0.8\\2\\2\\1.9\\2.1\end{bmatrix}}}$作哈尔小波变换，

公式为${\displaystyle 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作哈尔小波变换，由于${\displaystyle AH}$是对${\displaystyle A}$的每一列作哈尔小波变换，作完后还要对${\displaystyle A}$的每一行作哈尔小波变换，因此公式为${\displaystyle H^{T}AH}$。以下为一简单的例子：

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

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

${\displaystyle S=H^{T}L={\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}}}$。

由以上例子可以看出哈尔小波变换的效果，原本矩阵中变化量不大的元素经过变换后会趋近零，再配合适当量化便可以达到压缩的效果了。此外若一矩阵作完哈尔小波变换后所含的零元素非常多的话，称此矩阵为稀疏矩阵，若一矩阵越稀疏压缩效果越好。因此可对定一临界值${\displaystyle \epsilon }$，若矩阵中元素的绝对值小于此临界值${\displaystyle \epsilon }$，将该元素置零，可得到更大的压缩率。然而${\displaystyle \epsilon }$取过大的话会造成图像严重失真，因此如何取适当的${\displaystyle \epsilon }$也是值得讨论的议题。

哈尔小波变换运算量比沃尔什变换更少

若应用于区域的频谱分析及侦测边缘的话，离散傅立叶变换、Walsh-Hadamard变换及哈尔小波变换的计算量见下表

	运行时间	为使NRMSE < ${\displaystyle 10^{-5}}$所需要的项数量
离散傅里叶变换	9.5秒	43
沃尔什变换	2.2秒	65
哈尔小波变换	0.3秒	128

参考

• 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.

1. 胡广书. 现代信号处理教程 第二版. 北京. 2015-03. ISBN 978-7-302-38934-7. OCLC 1101305618.