在數值分析 和泛函分析 領域中,離散小波轉換 (Discrete Wavelet Transform,DWT)是小波被離散取樣的小波轉換 。與其他小波轉換一樣,它與傅立葉轉換相比的一個關鍵優勢是時間解析度:它既能捕獲頻率資訊,又能捕獲位置(時間上的位置)資訊。
第一個離散小波變換由匈牙利 數學家哈爾 發明,離散小波轉換顧名思義就是離散的輸入以及離散的輸出,但是這裡並沒有一個簡單而明確的公式來表示輸入及輸出的關係,只能以階層式架構來表示。
首先我們定義一些需要用到的訊號及濾波器。
x[n]:離散的輸入訊號,長度為N。
g
[
n
]
{\displaystyle g[n]}
:low pass filter低通濾波器,可以將輸入訊號的高頻部份濾掉而輸出低頻部份。
h
[
n
]
{\displaystyle h[n]}
:high pass filter高通濾波器,與低通濾波器相反,濾掉低頻部份而輸出高頻部份。
↓
{\displaystyle \downarrow }
Q:downsampling filter降取樣濾波器,如果以x[n]作為輸入,則輸出y[n]=x[Qn]。此處舉例Q=2。
舉例說明:
清楚規定以上符號之後,便可以利用階層架構來介紹如何將一個離散訊號作離散小波轉換:
架構中的第1層(1st stage)
x
1
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{1,L}[n]=\sum _{k=0}^{K-1}x[2n-k]g[k]}
x
1
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{1,H}[n]=\sum _{k=0}^{K-1}x[2n-k]h[k]}
架構中的第2層(2nd stage)
x
2
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
1
,
L
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{2,L}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]g[k]}
x
2
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
1
,
L
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{2,H}[n]=\sum _{k=0}^{K-1}x_{1,L}[2n-k]h[k]}
可繼續延伸
⋮
{\displaystyle \vdots }
⋮
{\displaystyle \vdots }
架構中的第
α
{\displaystyle \alpha }
層(
α
−
t
h
{\displaystyle \alpha -th}
stage)
x
α
,
L
[
n
]
=
∑
k
=
0
K
−
1
x
α
−
1
,
L
[
2
n
−
k
]
g
[
k
]
{\displaystyle x_{\alpha ,L}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]g[k]}
x
α
,
H
[
n
]
=
∑
k
=
0
K
−
1
x
α
−
1
,
L
[
2
n
−
k
]
h
[
k
]
{\displaystyle x_{\alpha ,H}[n]=\sum _{k=0}^{K-1}x_{\alpha -1,L}[2n-k]h[k]}
注意:若輸入訊號
x
[
n
]
{\displaystyle x[n]}
的長度是N,則第
α
{\displaystyle \alpha }
層中的
x
α
,
L
[
n
]
{\displaystyle x_{\alpha ,L}[n]}
及
x
α
,
H
[
n
]
{\displaystyle x_{\alpha ,H}[n]}
的長度為
N
2
α
{\displaystyle {\frac {N}{2^{\alpha }}}}
此時的輸入訊號變成
x
[
m
,
n
]
{\displaystyle x[m,n]}
,而轉換過程變得更複雜,說明如下:
首先對n方向作高通、低通以及降頻的處理
v
1
,
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
x
[
m
,
2
n
−
k
]
g
[
k
]
{\displaystyle v_{1,L}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]g[k]}
v
1
,
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
x
[
m
,
2
n
−
k
]
h
[
k
]
{\displaystyle v_{1,H}[m,n]=\sum _{k=0}^{K-1}x[m,2n-k]h[k]}
接著對
v
1
,
L
[
m
,
n
]
{\displaystyle v_{1,L}[m,n]}
與
v
1
,
H
[
m
,
n
]
{\displaystyle v_{1,H}[m,n]}
延著m方向作高低通及降頻動作
x
1
,
L
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
L
[
2
m
−
k
,
n
]
g
[
k
]
{\displaystyle x_{1,LL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]g[k]}
x
1
,
H
L
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
L
[
2
m
−
k
,
n
]
h
[
k
]
{\displaystyle x_{1,HL}[m,n]=\sum _{k=0}^{K-1}v_{1,L}[2m-k,n]h[k]}
x
1
,
L
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
H
[
2
m
−
k
,
n
]
g
[
k
]
{\displaystyle x_{1,LH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]g[k]}
x
1
,
H
H
[
m
,
n
]
=
∑
k
=
0
K
−
1
v
1
,
H
[
2
m
−
k
,
n
]
h
[
k
]
{\displaystyle x_{1,HH}[m,n]=\sum _{k=0}^{K-1}v_{1,H}[2m-k,n]h[k]}
經過(1)(2)兩個步驟才算完成2-D DWT的一個stage。
在討論複雜度之前,先做一些定義,當x[n]*y[n]時,x[n]之長度為N,y[n]之長度為L:
⇒
I
D
F
T
N
+
L
−
1
[
D
F
T
N
+
L
−
1
(
x
[
n
]
)
D
F
T
N
+
L
−
1
(
y
[
n
]
)
]
{\displaystyle \ \Rightarrow IDFT_{N+L-1}\left[DFT_{N+L-1}(x[n])DFT_{N+L-1}(y[n])\right]}
其中,
I
D
F
T
N
+
L
−
1
{\displaystyle \ IDFT_{N+L-1}}
為(N+L-1)點離散傅立葉反轉換(inverse discrete Fourier transform)
D
F
T
N
+
L
−
1
{\displaystyle \ DFT_{N+L-1}}
為(N+L-1)點離散傅立葉轉換(discrete Fourier transform)
(1)一維離散小波轉換之複雜度(沒有分段摺積(sectioned convolution)):
3
2
(
N
+
L
−
1
)
log
2
(
N
+
L
−
1
)
≈
3
2
N
log
2
N
{\displaystyle {\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}\approx {\frac {3}{2}}N\log _{2}N}
(2)當 N >>> L 時,使用 「分段摺積(sectioned convolution)」的技巧:
將x[n]切成很多段,每段長度為
N
1
{\displaystyle \mathbb {N} _{1}}
,總共會有
S
=
N
N
1
{\displaystyle S={\frac {N}{N_{1}}}}
段,其中
N
>
N
1
>>
L
{\displaystyle N>N_{1}>>L}
。
則
x
[
n
]
∗
g
[
n
]
=
x
1
[
n
]
∗
g
[
n
]
+
x
2
[
n
]
∗
g
[
n
]
+
.
.
.
+
x
s
[
n
]
∗
g
[
n
]
{\displaystyle \ x[n]*g[n]=x_{1}[n]*g[n]+x_{2}[n]*g[n]+...+x_{s}[n]*g[n]}
x
[
n
]
∗
h
[
n
]
=
x
1
[
n
]
∗
h
[
n
]
+
x
2
[
n
]
∗
h
[
n
]
+
.
.
.
+
x
s
[
n
]
∗
h
[
n
]
{\displaystyle \ x[n]*h[n]=x_{1}[n]*h[n]+x_{2}[n]*h[n]+...+x_{s}[n]*h[n]}
複雜度為:
3
2
S
(
N
1
+
L
−
1
)
log
2
(
N
1
+
L
−
1
)
≈
3
2
S
N
1
log
2
(
N
1
+
L
−
1
)
≈
3
2
N
log
2
(
N
1
+
L
−
1
)
≈
3
2
N
log
2
N
1
{\displaystyle {\begin{aligned}{\frac {3}{2}}S(N_{1}+L-1)\log _{2}{(N_{1}+L-1)}&\approx {\frac {3}{2}}SN_{1}\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}(N_{1}+L-1)\\&\approx {\frac {3}{2}}N\log _{2}N_{1}\\\end{aligned}}}
在這裡要注意的是,當N>>L時,一維離散小波轉換之複雜度是呈線性的(隨N),
O
(
N
)
{\displaystyle {\mathit {O(N)}}}
。
(3)多層(Multiple stages )的情況下:
1.若
x
a
,
H
[
n
]
{\displaystyle \ x_{a,H}[n]}
不再分解時:
C
o
m
p
l
e
x
i
t
y
≈
(
N
+
N
2
+
N
4
+
N
8
+
.
.
.
+
2
)
3
2
log
2
N
1
=
(
2
N
−
2
)
3
2
log
2
N
1
≈
3
N
log
2
N
1
{\displaystyle {\begin{aligned}Complexity&\approx \left(N+{\frac {N}{2}}+{\frac {N}{4}}+{\frac {N}{8}}+...+2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(2N-2){\frac {3}{2}}\log _{2}N_{1}\\&\approx 3N\log _{2}N_{1}\\\end{aligned}}}
2.若
x
a
,
H
[
n
]
{\displaystyle \ x_{a,H}[n]}
也細分時:
C
o
m
p
l
e
x
i
t
y
≈
(
N
+
2
N
2
+
4
N
4
+
8
N
8
+
.
.
.
+
N
2
2
)
3
2
log
2
N
1
=
(
N
log
2
N
)
3
2
log
2
N
1
{\displaystyle {\begin{aligned}Complexity&\approx \left(N+2{\frac {N}{2}}+4{\frac {N}{4}}+8{\frac {N}{8}}+...+{\frac {N}{2}}2\right){\frac {3}{2}}\log _{2}N_{1}\\&=(N\log _{2}N){\frac {3}{2}}\log _{2}N_{1}\\\end{aligned}}}
(4)二維離散小波轉換之複雜度(沒有分段摺積(sectioned convolution)):
⇒
M
3
2
(
N
+
L
−
1
)
log
2
(
N
+
L
−
1
)
+
(
N
+
L
−
1
)
3
2
(
M
+
L
−
1
)
log
2
(
M
+
L
−
1
)
{\displaystyle \ \Rightarrow M{\frac {3}{2}}(N+L-1)\log _{2}{(N+L-1)}+(N+L-1){\frac {3}{2}}(M+L-1)\log _{2}{(M+L-1)}}
上式中,第一部分需要M個一維離散小波轉換並且每個一維離散小波轉換的輸入有N個點;第二部分需要N+L-1個一維離散小波轉換並且每個一維離散小波轉換的輸入有M個點。
C
o
m
p
l
e
x
i
t
y
≈
3
2
M
N
log
2
N
+
3
2
M
N
log
2
M
=
3
2
M
N
(
log
2
N
+
log
2
M
)
=
3
2
M
N
log
2
M
N
{\displaystyle {\begin{aligned}Complexity&\approx {\frac {3}{2}}MN\log _{2}N+{\frac {3}{2}}MN\log _{2}M\\&={\frac {3}{2}}MN(\log _{2}N+\log _{2}M)\\&={\frac {3}{2}}MN\log _{2}MN\\\end{aligned}}}
(5)二維離散小波轉換之複雜度,使用 「分段摺積(sectioned convolution)」的技巧:
假設原始尺寸為
M
×
N
{\displaystyle M\times N}
,則每一小部分的尺寸為
M
1
×
N
1
{\displaystyle M_{1}\times N_{1}}
C
o
m
p
l
e
x
i
t
y
≈
M
N
M
1
N
1
3
2
M
1
N
1
log
2
M
1
N
1
=
3
2
M
N
log
2
M
1
N
1
{\displaystyle {\begin{aligned}Complexity&\approx {\frac {MN}{M_{1}N_{1}}}{\frac {3}{2}}M_{1}N_{1}\log _{2}M_{1}N_{1}\\&={\frac {3}{2}}MN\log _{2}M_{1}N_{1}\\\end{aligned}}}
所以若是使用分段摺積,則二維離散小波轉換之複雜度是呈線性的(隨MN),
O
(
M
N
)
{\displaystyle {\mathit {O(MN)}}}
。
(6)多層(Multiple stages )與二維的情況下:
首先x[m,n]的尺寸為
M
×
N
{\displaystyle M\times N}
,
1.若
x
a
,
H
1
[
n
]
,
x
a
,
H
2
[
n
]
,
x
a
,
H
3
[
n
]
{\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}
不細分,只細分
x
a
,
L
[
n
]
{\displaystyle \ x_{a,L}[n]}
時,總複雜度為:
t
o
t
a
l
c
o
m
p
l
e
x
i
t
y
=
(
M
N
+
M
N
4
+
M
N
16
+
.
.
.
)
3
2
log
2
M
1
N
1
≈
4
3
M
N
3
2
log
2
M
1
N
1
=
2
M
N
log
2
M
1
N
1
{\displaystyle {\begin{aligned}totalcomplexity&=\left(MN+{\frac {MN}{4}}+{\frac {MN}{16}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&\approx {\frac {4}{3}}MN{\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=2MN\log _{2}M_{1}N_{1}\\\end{aligned}}}
2.若
x
a
,
H
1
[
n
]
,
x
a
,
H
2
[
n
]
,
x
a
,
H
3
[
n
]
{\displaystyle \ x_{a,H_{1}}[n],x_{a,H_{2}}[n],x_{a,H_{3}}[n]}
也細分時,總複雜度為:
t
o
t
a
l
c
o
m
p
l
e
x
i
t
y
=
(
M
N
+
4
M
2
N
2
+
16
M
4
N
4
+
.
.
.
)
3
2
log
2
M
1
N
1
=
[
M
N
log
2
(
m
i
n
(
M
,
N
)
)
]
3
2
log
2
M
1
N
1
{\displaystyle {\begin{aligned}totalcomplexity&=\left(MN+4{\frac {M}{2}}{\frac {N}{2}}+16{\frac {M}{4}}{\frac {N}{4}}+...\right){\frac {3}{2}}\log _{2}M_{1}N_{1}\\&=\left[MN\log _{2}(min(M,N))\right]{\frac {3}{2}}\log _{2}M_{1}N_{1}\\\end{aligned}}}
壓縮、去除雜訊:使用低通濾波器,將小波轉換的高頻濾掉,即保留
x
1
,
L
L
[
m
,
n
]
{\displaystyle x_{1,LL}[m,n]}
而將其他部分捨棄。
邊緣偵測:使用高通濾波器,將小波的低頻濾掉,即保留
x
1
,
H
L
[
m
,
n
]
{\displaystyle x_{1,HL}[m,n]}
或
x
1
,
L
H
[
m
,
n
]
{\displaystyle x_{1,LH}[m,n]}
而捨棄其他部分。
R語言小波分析wavelet (頁面存檔備份 ,存於網際網路檔案館 )
作為 JPEG2000 的內部架構
模式辨認:由於可以利用低頻的部分得到原圖的縮略版,加上模式通常為整體的特性,藉由在縮略圖上進行工作,小波轉換可以有效減少尋找模式與比對模式的運算時間
濾波器設計:小波轉換保留部分時間資訊,可以據此資訊加上訊號的強度資訊,保留特定時點的資訊而同時去除雜訊