哈爾小波轉換

哈爾小波轉換（英語：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