哈爾小波轉換 (英語:Haar wavelet )是由数学家哈尔·阿尔弗雷德 於1909年所提出的函数变换 ,是小波轉換 中最簡單的一種轉換,也是最早提出的小波轉換。他是多贝西小波 的於N=2的特例,可稱之為D2或db1。
哈爾小波 的母小波(mother wavelet)可表示為:
ψ
(
t
)
=
{
1
0
≤
t
<
1
/
2
,
−
1
1
/
2
≤
t
<
1
,
0
otherwise.
{\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)可表示為:
ϕ
(
t
)
=
{
1
0
≤
t
<
1
,
0
otherwise.
{\displaystyle \phi (t)={\begin{cases}1\quad &0\leq t<1,\\0&{\mbox{otherwise.}}\end{cases}}}
其濾波器(filter)
h
[
n
]
{\displaystyle h[n]}
被定義為
h
[
n
]
=
{
1
2
if n = 0,1
0
otherwise
{\displaystyle h[n]={\begin{cases}{\frac {1}{\sqrt {2}}}&{\mbox{if n = 0,1}}\\0&{\mbox{otherwise}}\end{cases}}}
當
n
=
0
,
1
{\displaystyle n=0,1}
時,滤波器
h
[
n
]
{\displaystyle h[n]}
系数非零,此时可以用哈尔小波的滤波器系数及其尺度函数,将母小波函数表示为:
1
2
ψ
(
(
t
2
)
)
=
∑
n
=
−
∞
∞
(
−
1
)
1
−
n
h
[
1
−
n
]
ϕ
(
t
−
n
)
=
1
2
(
ϕ
(
t
−
1
)
−
ϕ
(
t
)
)
{\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)。
小波母函數可以用尺度函数表示:
ψ
(
t
)
=
ϕ
(
2
t
)
−
ϕ
(
2
t
−
1
)
{\displaystyle \psi (t)=\phi (2t)-\phi (2t-1)}
对小波的母函数可以进行伸缩和平移,例如
ψ
(
2
t
)
{\displaystyle \psi (2t)}
、
ψ
(
2
m
t
−
n
)
{\displaystyle \psi (2^{m}t-n)}
。
当尺度离散方式选取
a
=
2
j
,
j
∈
Z
+
{\displaystyle a=2^{j},j\in \mathbb {Z^{+}} }
时,依据哈尔小波函数的定义,我们可以推出[ 1] :
(1)不同尺度的小波函数相互正交(即
<
ψ
(
t
)
,
ψ
(
2
−
j
(
t
)
)
>=
∫
ψ
(
t
)
ψ
(
2
−
j
(
t
)
)
d
t
=
0
(
∀
j
≠
0
)
{\displaystyle <\psi (t),\psi (2^{-j}(t))>=\int \psi (t)\psi (2^{-j}(t))\,dt=0(\forall j\neq 0)}
),例如:
∫
ψ
(
t
)
ψ
(
2
t
)
d
t
=
∫
0
1
/
2
ψ
(
2
t
)
d
t
−
∫
1
/
2
1
ψ
(
2
t
)
d
t
=
τ
=
2
t
∫
0
1
ψ
(
τ
)
2
d
τ
−
∫
1
2
ψ
(
τ
)
2
d
τ
=
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}}}
∫
ψ
(
t
)
ψ
(
4
t
)
d
t
=
0
{\displaystyle \int \psi (t)\psi (4t)\,dt=0}
(证明同上)
∫
ψ
(
2
j
1
t
)
ψ
(
2
j
2
t
)
d
t
=
0
(
∀
j
1
≠
j
2
)
{\displaystyle \int \psi (2^{j_{1}}t)\psi (2^{j_{2}}t)\,dt=0(\forall j_{1}\neq j_{2})}
(2)同一尺度及不同尺度下,小波函数的整数位移之间相互正交(即
<
ψ
(
t
)
,
ψ
(
t
−
k
)
>=
∫
ψ
(
t
)
ψ
(
t
−
k
)
d
t
=
0
(
∀
k
≠
0
)
{\displaystyle <\psi (t),\psi (t-k)>=\int \psi (t)\psi (t-k)\,dt=0(\forall k\neq 0)}
),例如:
∫
ψ
(
t
)
ψ
(
t
−
1
)
d
t
=
0
{\displaystyle \int \psi (t)\psi (t-1)\,dt=0}
∫
ψ
(
t
)
ψ
(
2
t
−
1
)
d
t
=
0
{\displaystyle \int \psi (t)\psi (2t-1)\,dt=0}
∫
ψ
(
t
)
ψ
(
2
m
t
−
1
)
d
t
=
0
{\displaystyle \int \psi (t)\psi (2^{m}t-1)\,dt=0}
尺度函數
尺度函数(scaling function),以下為尺度函數的簡易圖示:
(1):
ϕ
(
t
)
{\displaystyle \phi (t)}
(2):
ϕ
(
2
t
)
,
2
ϕ
(
2
t
)
=
ϕ
(
t
)
+
ψ
(
t
)
{\displaystyle \phi (2t),2\phi (2t)=\phi (t)+\psi (t)}
(3):
ψ
(
2
m
t
−
n
)
{\displaystyle \psi (2^{m}t-n)}
優點
(1)簡單(Simple)
(2)快速算法(Fast algorithm)
(3)正交(Orthogonal)→可逆(reversible)
(4)結構緊湊(Compact),實(real),奇(odd)
(5)具有一阶消失矩(Vanish moment)
特性
哈爾小波具有如下的特性:
(1)任一函數都可以由
ϕ
(
t
)
,
ϕ
(
2
t
)
,
ϕ
(
4
t
)
,
…
,
ϕ
(
2
k
t
)
,
…
{\displaystyle \phi (t),\phi (2t),\phi (4t),\dots ,\phi (2^{k}t),\dots }
以及它們的位移函數所組成
(2)任一函數都可以由常函數,
ψ
(
t
)
,
ψ
(
2
t
)
,
ψ
(
4
t
)
,
…
,
ψ
(
2
k
t
)
,
…
{\displaystyle \psi (t),\psi (2t),\psi (4t),\dots ,\psi (2^{k}t),\dots }
以及它們的位移函數所組成
(3)正交性(Orthogonal)
∫
−
∞
∞
2
m
ψ
(
2
m
1
t
−
n
1
)
ψ
(
2
m
t
−
n
)
d
t
=
δ
(
m
,
m
1
)
δ
(
n
,
n
1
)
{\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})}
δ
(
i
,
j
)
=
{
1
i
=
j
,
0
i≠j.
{\displaystyle \delta (i,j)={\begin{cases}1&i=j,\\0&{\mbox{i≠j.}}\end{cases}}}
(4)不同寬度的(不同m)的小波函数和尺度函数之間會有一個關係
ϕ
(
t
)
=
ϕ
(
2
t
)
+
ϕ
(
2
t
−
1
)
{\displaystyle \phi (t)=\phi (2t)+\phi (2t-1)}
ϕ
(
t
−
n
)
=
ϕ
(
2
t
−
2
n
)
+
ϕ
(
2
t
−
2
n
−
1
)
{\displaystyle \phi (t-n)=\phi (2t-2n)+\phi (2t-2n-1)}
ϕ
(
2
m
t
−
n
)
=
ϕ
(
2
m
+
1
t
−
2
n
)
+
ϕ
(
2
m
+
1
t
−
2
n
−
1
)
{\displaystyle \phi (2^{m}t-n)=\phi (2^{m+1}t-2n)+\phi (2^{m+1}t-2n-1)}
ψ
(
t
)
=
ϕ
(
2
t
)
−
ϕ
(
2
t
−
1
)
{\displaystyle \psi (t)=\phi (2t)-\phi (2t-1)}
ψ
(
t
−
n
)
=
ϕ
(
2
t
−
n
)
−
ϕ
(
2
t
−
2
n
−
1
)
{\displaystyle \psi (t-n)=\phi (2t-n)-\phi (2t-2n-1)}
ψ
(
2
m
t
−
n
)
=
ϕ
(
2
m
+
1
t
−
n
)
−
ϕ
(
2
m
+
1
t
−
2
n
−
1
)
{\displaystyle \psi (2^{m}t-n)=\phi (2^{m+1}t-n)-\phi (2^{m+1}t-2n-1)}
(5)可以用m+1的 係數来計算m的係數
若
χ
w
(
n
,
m
)
=
2
m
/
2
∫
−
∞
∞
x
(
t
)
ϕ
(
2
m
t
−
n
)
d
t
{\displaystyle \chi _{w}(n,m)=2^{m/2}\int _{-\infty }^{\infty }x(t)\phi (2^{m}t-n)\,dt}
χ
w
(
n
,
m
)
=
2
m
/
2
∫
−
∞
∞
x
(
t
)
ϕ
(
2
m
+
1
t
−
2
n
)
d
t
+
2
m
/
2
∫
−
∞
∞
x
(
t
)
ϕ
(
2
m
+
1
t
−
2
n
−
1
)
d
t
=
1
2
(
χ
w
(
2
n
,
m
+
1
)
+
χ
w
(
2
n
+
1
,
m
+
1
)
)
{\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}}}
若
X
w
(
n
,
m
)
=
2
m
/
2
∫
−
∞
∞
x
(
t
)
ψ
(
2
m
t
−
n
)
d
t
{\displaystyle \mathrm {X} _{w}(n,m)=2^{m/2}\int _{-\infty }^{\infty }x(t)\psi (2^{m}t-n)\,dt}
X
w
(
n
,
m
)
=
2
m
/
2
∫
−
∞
∞
x
(
t
)
ϕ
(
2
m
+
1
t
−
2
n
)
d
t
−
2
m
/
2
∫
−
∞
∞
x
(
t
)
ϕ
(
2
m
+
1
t
−
2
n
−
1
)
d
t
=
X
w
(
n
,
m
)
=
1
2
(
χ
w
(
2
n
,
m
+
1
)
−
χ
w
(
2
n
+
1
,
m
+
1
)
)
{\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行來做內積 ,得到的結果為零;取第二行和第三行來做內積,得到的結果也是零。依序下去,我們可以發現在哈爾轉換矩陣任取兩行來進行內積的運算,所得到的內積皆為零。
N
=
2
{\displaystyle N=2}
,
H
=
[
1
1
1
−
1
]
{\displaystyle H={\begin{bmatrix}\ 1&1\\\ 1&-1\\\end{bmatrix}}}
。
N
=
4
{\displaystyle N=4}
,
H
=
[
1
1
1
1
1
1
−
1
−
1
1
−
1
0
0
0
0
1
−
1
]
{\displaystyle H={\begin{bmatrix}\ 1&1&1&1\\\ 1&1&-1&-1\\\ 1&-1&0&0\\\ 0&0&1&-1\\\end{bmatrix}}}
。
N
=
8
{\displaystyle N=8}
,
H
=
[
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
]
{\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和-1)部分
可以分析一個訊號的局部特征
運算速度極快,但不適合用於訊號分析
大部分運算為0,不用計算
維度小,计算时需要占用的内存空间少
因為大部分為高頻,轉換較籠統
對一矩陣
A
{\displaystyle A}
做哈爾小波轉換的公式為
B
=
H
A
H
T
{\displaystyle B=HAH^{T}}
,其中
A
{\displaystyle A}
為一
N
×
N
{\displaystyle N\times N}
的區塊且
H
{\displaystyle H}
為
N
{\displaystyle N}
點的哈爾小波轉換。而反哈爾小波轉換為
A
=
H
T
B
H
{\displaystyle A=H^{T}BH}
。以下為
H
{\displaystyle H}
在2、4及8點時的值:
N
=
2
{\displaystyle N=2}
,
H
=
[
1
2
1
2
1
2
−
1
2
]
{\displaystyle H={\begin{bmatrix}{\frac {1}{\sqrt {2}}}&{\frac {1}{\sqrt {2}}}\\{\frac {1}{\sqrt {2}}}&{\frac {-1}{\sqrt {2}}}\end{bmatrix}}}
。
N
=
4
{\displaystyle N=4}
,
H
=
[
1
2
1
2
1
2
1
2
1
2
1
2
−
1
2
−
1
2
1
2
−
1
2
0
0
0
0
1
2
−
1
2
]
{\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}}}
。
N
=
8
{\displaystyle N=8}
,
H
=
[
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
1
8
−
1
8
−
1
8
−
1
8
−
1
8
1
2
1
2
−
1
2
−
1
2
0
0
0
0
0
0
0
0
1
2
1
2
−
1
2
−
1
2
1
2
−
1
2
0
0
0
0
0
0
0
0
1
2
−
1
2
0
0
0
0
0
0
0
0
1
2
−
1
2
0
0
0
0
0
0
0
0
1
2
−
1
2
]
{\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}}}
。
此外,當
N
=
2
k
{\displaystyle N=2^{k}}
時,
H
=
[
ϕ
h
0
,
0
h
1
,
0
h
1
,
1
:
:
h
k
−
1
,
0
h
k
−
1
,
1
:
h
k
−
1
,
2
k
−
1
−
1
]
{\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}}}
。其中
H
{\displaystyle H}
除了第0行為
ϕ
{\displaystyle \phi }
(
ϕ
{\displaystyle \phi }
=[1 1 1 ... 1]/
N
{\displaystyle {\sqrt {N}}}
,共N個1),第
2
p
+
q
{\displaystyle 2^{p}+q}
行為
h
p
,
q
{\displaystyle h_{p,q}}
且
h
p
,
q
[
n
]
=
{
1
/
2
k
−
p
,
w
h
e
n
q
2
k
−
p
≤
n
<
(
q
+
1
/
2
)
2
k
−
p
−
1
/
2
k
−
p
,
w
h
e
n
(
q
+
1
/
2
)
2
k
−
p
≤
n
<
(
q
+
1
)
2
k
−
p
0
,
o
t
h
e
r
w
i
s
e
{\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
哈爾小波轉換應用於圖像壓縮
哈爾小波轉換運算量比沃爾什轉換更少
若應用於區域的頻譜分析及偵測邊緣的話,离散傅立叶变换 、Walsh-Hadamard变换 及哈爾小波轉換的計算量見下表
运行时间
为使NRMSE <
10
−
5
{\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.
^ 胡广书. 现代信号处理教程 第二版. 北京. 2015-03. ISBN 978-7-302-38934-7 . OCLC 1101305618 .