哈爾小波轉換

哈爾小波轉換是於1909年由Alfréd Haar所提出，是小波轉換(Wavelet transform)中最簡單的一種轉換，也是最早提出的小波轉換。他是多贝西小波的於N=2的特例，可稱之為D2

哈爾小波的母小波(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 與 n = 1 時，有兩個非零係數，因此，我們可以將它寫成

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

在所有正交性(orthonormal)小波轉換中哈爾小波轉換(Haar wavelet)是最簡單的一種轉換，但它並不適合用於較為平滑的函數,因為它只有一個消失矩(Vanishing Moment)。

小波母函數

mother wavelet(wavelet function)，以下為小波母函數的簡易圖示：

(1): $\psi(t)=\phi(2t)-\phi(2t-1)$

(2) :$\psi(2t)$

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

因此，由上圖我們可以歸納出幾個重點：

(1):

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

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

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

(2):

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

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

$\int \psi(t)\psi(2^{m}-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^mt-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)的wavelet/scaling functions之間會有一個關係

 $\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^mt-n)\, dt$

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

若$\Chi_w(n,m)=2^{m/2}\int_{-\infty}^{\infty}x(t)\psi(2^mt-n)\, dt$

$\begin{align} \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\\ & = \Chi_w(n,m)=\sqrt{\frac{1}{2}}(\chi_w(2n,m+1)-\chi_w(2n+1,m+1))\\ \end{align}$

圖示如下：

快速演算法

上圖為哈爾小波轉換的快速演算簡易圖示，此為多重解析結構(multiresolution analysis )。

哈爾轉換

Haar Transform最早是由A. Haar在1910年“Zur theorie der orthogonalen funktionensysteme”中所提出，是一種最簡單又可以反應出時變頻譜（time-variant spectrum）的表示方法。其觀念與Fourier Transform相近，Fourier Transform的原理是利用弦波sine與cosine來對訊號進行調變；而Haar Transform則是利用Haar function來對訊號進行調變。Haar function也含有sine、cosine所擁有的正交性，也就是說不同的Haar function是互相orthogonal，其內積為零。

以下面N=8的哈爾轉換矩陣為例，我們取第一行和第二行來做內積，得到的結果為零；取第二行和第三行來做內積，得到的結果也是零。依序下去，我們可以發現在哈爾轉換矩陣任取兩行來進行內積的運算，所得到的內積皆為零。

$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}$。

在此前提下，利用Fourier Transform的觀念，假設所要分析的訊號可以使用多個頻率與位移不同的Haar function來組合而成，進行Haar Transform時，因為Haar function的正交性，便可求出訊號在不同Haar function（不同頻率）的情況下所占有的比例。

Haar Transform有以下幾點特性：

1.不需要乘法（只有相加或加減）

2.輸入與輸出個數相同

3.頻率只分為低頻（直流值）與高頻（1和-1）部分

4.可以分析一個訊號的Localized feature

5.運算速度極快，但不適合用於訊號分析

6.大部分運算為0，不用計算

7.維度小，使用的memory少

8.因為大部分為高頻，轉換較籠統

對一矩陣$A$做哈爾小波轉換的公式為$B=HAH^T$，其中$A$為一$N\times N$的區塊且$H$為$N$點的哈爾小波轉換。而反哈爾小波轉換為$A=H^TBH$。以下為$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個row為$\phi$($\phi$=[1 1 1 ... 1]/$\sqrt{N}$，共N個1)，第$2^p+q$個row為$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}$。

哈爾小波轉換應用於圖像壓縮

說明

File:Haar compression.jpg

哈爾小波轉換應用於影像壓縮示意圖

由於數位圖片檔案過大，因此我們往往會對圖片做圖像壓縮，壓縮過後的檔案大小不僅存放於電腦中不會佔到過大容量，也方便我們於網路上傳送。哈爾小波轉換其中一種應用便是用來壓縮圖像。壓縮圖像的基本概念為將圖像存成到一矩陣，矩陣中的每一元素則代表是每一圖像的某畫素值，介於0到255間。例如256x256大小的圖片會存成256x256大小的矩陣。JPEG影像壓縮的概念為先將圖像切成8x8大小的區塊，每一區塊為一8x8的矩陣。示意圖可見右圖。

在處理8x8二維矩陣前，先試著對一維矩陣$r=\begin{bmatrix}1.2\\1.2\\1.8\\0.8\\2\\2\\1.9\\2.1 \end{bmatrix}$作哈爾小波轉換，

公式為$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作哈爾小波轉換，由於$AH$是對$A$的每一行作哈爾小波轉換，作完後還要對$A$的每一列作哈爾小波轉換，因此公式為$H^TAH$。以下為一簡單的例子:

$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)

$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)

$S=H^TL=\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}$。

由以上例子可以看出哈爾小波轉換的效果，原本矩陣中變化量不大的元素經過轉換後會趨近零，再配合適當量化便可以達到壓縮的效果了。此外若一矩陣作完哈爾小波轉換後所含的零元素非常多的話，稱此矩陣叫稀疏，若一矩陣越稀疏壓縮效果越好。因此可對定一臨界值$\epsilon$若矩陣中元素的絕對值小於此臨界值$\epsilon$，可將該元素令成零，可得到更大的壓縮率。然而$\epsilon$取過大的話會造成圖像嚴重失真，因此如何取適當的$\epsilon$也是值得討論的議題。

哈爾小波轉換運算量比沃爾什轉換更少

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

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