哈爾小波轉換

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

(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年的论文《论正交函数系理论》（德語：）中所提出，是一種最簡單又可以反應出時變頻譜（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}}}$。

若應用於區域的頻譜分析及偵測邊緣的話，离散傅立叶变换、Walsh-Hadamard变换及哈爾小波轉換的計算量見下表

	Running Time	terms required for 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.