哈尔小波变换

参与变换的小波函数（wavelet function）也叫母小波（mother wavelet）。小波母函数可表示为：

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

(2) :${\displaystyle \psi (2t)}$ 

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

因此，由上式我们可以归纳出几个重点：

(1):

${\displaystyle \Rightarrow \int \psi (t)\psi (2t)\,dt=0}$ 

${\displaystyle \int \psi (t)\psi (4t)\,dt=0}$ 

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

(2):

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

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

${\displaystyle \int \psi (t)\psi (2^{m}-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）的wavelet/scaling functions之间会有一个关系

 ${\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个row为${\displaystyle \phi }$ （${\displaystyle \phi }$ =[1 1 1 ... 1]/${\displaystyle {\sqrt {N}}}$ ，共N个1），第${\displaystyle 2^{p}+q}$ 个row为${\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 Code:

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 Code:

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变换及哈尔小波变换的计算量见下表

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