计算机科学

首页 > 计算机科学

哈尔小波变换

2018-09-06 14:26:21     所属分类:数值分析

哈尔小波变换是于1909年由Alfréd Haar所提出,是小波变换(Wavelet transform)中最简单的一种变换,也是最早提出的小波变换。他是多贝西小波的于N=2的特例,可称之为D2

哈尔小波的母小波(mother wavelet)可表示为:

且对应的尺度函数(scaling function)可表示为:

其滤波器(filter)被定义为
 :
当n = 0与n = 1时,有两个非零系数,因此,我们可以将它写成

在所有正交性(orthonormal)小波变换中哈尔小波变换(Haar wavelet)是最简单的一种变换,但它并不适合用于较为平滑的函数,因为它只有一个消失矩(Vanishing Moment)。

目录

  • 1 小波母函数
  • 2 尺度函数
  • 3 优点
  • 4 特性
  • 5 快速算法
  • 6 哈尔变换
  • 7 哈尔小波变换应用于图像压缩
    • 7.1 说明
    • 7.2 范例
  • 8 哈尔小波变换运算量比沃尔什变换更少
  • 9 参考

小波母函数

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.

相关推荐