哈爾小波轉換

哈爾小波轉換（英語：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$ 做哈爾小波轉換的公式為 $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}}

。

此外，當

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

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