本页使用了标题或全文手工转换

哈爾小波轉換

维基百科,自由的百科全书
跳转至: 导航搜索

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

哈爾小波的母小波(mother wavelet)可表示為:

且對應的尺度函数(scaling function)可表示為:

其濾波器(filter)被定義為
 :
當n = 0與n = 1時,有兩個非零係數,因此,我們可以將它寫成

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

小波母函數[编辑]

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

(1):

(2) :

(3):

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

(1):




(2):



尺度函數[编辑]

scaling function,以下為尺度函數的簡易圖示:

(1):

(2):

(3):

優點[编辑]

(1)簡單(Simple)

(2)快速算法(Fast algorithm)

(3)正交(Orthogonal)→可逆(reversible)

(4)結構緊湊(Compact),實(real),奇(odd)

(5)消失矩(Vanish moment)

特性[编辑]

哈爾小波具有如下的特性: (1)任一函數都可以由以及它們的位移函數所組成

(2)任一函數都可以由常函數,以及它們的位移函數所組成

(3)正交性(Orthogonal)

   
   

(4)不同寬度的(不同m)的wavelet/scaling functions之間會有一個關係

 

 

(5)可以用m+1的 係數来計算m的係數

圖示如下:

Property(5).png

快速演算法[编辑]

MRA.png

上圖為哈爾小波轉換的快速演算簡易圖示,此為多重解析結構(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,其內積為零。

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

在此前提下,利用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.因為大部分為高頻,轉換較籠統

對一矩陣做哈爾小波轉換的公式為,其中為一的區塊且點的哈爾小波轉換。而反哈爾小波轉換為。以下為在2、4及8點時的值:

此外,當時,。其中除了第0個row為=[1 1 1 ... 1]/,共N個1),第個row為

哈爾小波轉換應用於圖像壓縮[编辑]

說明[编辑]

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

範例[编辑]

對8x8的二維矩陣A作哈爾小波轉換,由於是對的每一行作哈爾小波轉換,作完後還要對的每一列作哈爾小波轉換,因此公式為。以下為一簡單的例子:
列哈爾小波轉換(row Haar wavelet transform)
行哈爾小波轉換(column Haar wavelet transform)
由以上例子可以看出哈爾小波轉換的效果,原本矩陣中變化量不大的元素經過轉換後會趨近零,再配合適當量化便可以達到壓縮的效果了。此外若一矩陣作完哈爾小波轉換後所含的零元素非常多的話,稱此矩陣叫稀疏,若一矩陣越稀疏壓縮效果越好。因此可對定一臨界值若矩陣中元素的絕對值小於此臨界值,可將該元素令成零,可得到更大的壓縮率。然而取過大的話會造成圖像嚴重失真,因此如何取適當的也是值得討論的議題。

哈爾小波轉換運算量比沃爾什轉換更少[编辑]

若應用於區域的頻譜分析及偵測邊緣的話,离散傅立叶变换Walsh-Hadamard变换及哈爾小波轉換的計算量見下表
Running Time terms required for NRMSE <
離散傅立葉變換 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.