アルゴリズム
高速ウェーブレット変換は、 時間領域の 波形 または信号を、 小さな有限波、つまり ウェーブレットの 直交基底 に基づく係数の シーケンス に 変換するように設計された 数学 アルゴリズム です。 この変換は、時間領域を空間領域に置き換えることで、画像などの多次元信号に簡単に拡張できます。このアルゴリズムは、1989年に ステファン・マラット によって導入されました 。 [1]
理論的基礎として、有限生成直交多重解像度解析 （MRA）の装置がある 。そこで与えられた用語では、単位間隔あたり 2 J のサンプリングレート でサンプリングスケール Jを 選択し、与えられた信号 f を空間に投影する 。理論的には、 スカラー積を計算することによって
五
J
{\displaystyle V_{J}}
s
ん
（ J ）
:=
2
J
⟨ ふ （ t ） 、 φ （
2
J
t − ん ） ⟩ 、
{\displaystyle s_{n}^{(J)}:=2^{J}\langle f(t),\varphi (2^{J}tn)\rangle ,}
ここで、選択されたウェーブレット変換の スケーリング関数 である 。実際には、信号が高度にオーバーサンプリングされている条件下での任意の適切なサンプリング手順によって、
φ
{\displaystyle \varphi}
ポ
J
[ ふ ] （ x ） :=
∑
ん ∈
ず
s
ん
（ J ）
φ （
2
J
x − ん ）
{\displaystyle P_{J}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\varphi (2^{J}xn) }
は、 の元の信号の直交投影 、または少なくともある程度の良い近似 です 。
五
J
{\displaystyle V_{J}}
MRAはスケーリングシーケンスによって特徴付けられる
1つの = （
1つの
− いいえ
、 … 、
1つの
0
、 … 、
1つの
いいえ
）
{\displaystyle a=(a_{-N},\dots ,a_{0},\dots ,a_{N})}
または、 Z変換 として、
1つの （ ず ） =
∑
ん = − いいえ
いいえ
1つの
ん
ず
− ん
{\displaystyle a(z)=\sum _{n=-N}^{N}a_{n}z^{-n}}
およびそのウェーブレットシーケンス
b = （
b
− いいえ
、 … 、
b
0
、 … 、
b
いいえ
）
{\displaystyle b=(b_{-N},\dots ,b_{0},\dots ,b_{N})}
または
b （ ず ） =
∑
ん = − いいえ
いいえ
b
ん
ず
− ん
{\displaystyle b(z)=\sum _{n=-N}^{N}b_{n}z^{-n}}
（係数の中にはゼロになるものもあります）。これらにより、対応するスカラー積の積分を近似することなく 、少なくともある範囲 k=M,...,J-1 の ウェーブレット係数を計算できます。代わりに、畳み込み演算子とデシメーション演算子を使用して、最初の近似値からそれらの係数を直接計算できます 。
d
ん
（ け ）
{\displaystyle d_{n}^{(k)}}
s
（ J ）
{\displaystyle s^{(J)}}
前方DWT 離散ウェーブレット変換 （DWT）の場合 、 係数列から始めて k = J - 1から M < J まで カウントダウンして 再帰的に 計算します。
s
（ J ）
{\displaystyle s^{(J)}}
ウェーブレットフィルタバンクの単一適用（フィルタg=a * 、h=b *）
s
ん
（ け ）
:=
1 2
∑
メートル = − いいえ
いいえ
1つの
メートル
s
2 ん + メートル
（ け + 1 ）
{\displaystyle s_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}a_{m}s_{2n+m}^{(k+1)}}
または
s
（ け ）
（ ず ） := （ ↓ 2 ） （
1つの
∗
（ ず ） ⋅
s
（ け + 1 ）
（ ず ） ）
{\displaystyle s^{(k)}(z):=(\downarrow 2)(a^{*}(z)\cdot s^{(k+1)}(z))}
そして
d
ん
（ け ）
:=
1 2
∑
メートル = − いいえ
いいえ
b
メートル
s
2 ん + メートル
（ け + 1 ）
{\displaystyle d_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}b_{m}s_{2n+m}^{(k+1)}}
または 、
d
（ け ）
（ ず ） := （ ↓ 2 ） （
b
∗
（ ず ） ⋅
s
（ け + 1 ）
（ ず ） ）
{\displaystyle d^{(k)}(z):=(\downarrow 2)(b^{*}(z)\cdot s^{(k+1)}(z))}
k=J-1,J-2,...,M およびすべて 。Z 変換表記では次
の ようになります。
ん ∈
ず
{\displaystyle n\in \mathbb {Z} }
フィルタバンクの再帰的適用 ダウン サンプリング演算子は、 Z 変換 によって与えられた無限シーケンス ( これは単純に ローラン級数 ) を、偶数インデックスを持つ係数のシーケンス に縮小します 。
（ ↓ 2 ）
{\displaystyle (\downarrow 2)}
（ ↓ 2 ） （ c （ ず ） ） =
∑
け ∈
ず
c
2 け
ず
− け
{\displaystyle (\downarrow 2)(c(z))=\sum _{k\in \mathbb {Z} }c_{2k}z^{-k}}
星印の付いたローラン多項式は 随伴フィルタ を表し、 時間反転 随伴係数 を持ちます 。(実数の随伴は数自体、複素数の場合はその共役、実数行列の場合は転置行列、複素数行列の場合はエルミート随伴です)。
1つの
∗
（ ず ）
{\displaystyle a^{*}(z)}
1つの
∗
（ ず ） =
∑
ん = − いいえ
いいえ
1つの
− ん
∗
ず
− ん
{\displaystyle a^{*}(z)=\sum _{n=-N}^{N}a_{-n}^{*}z^{-n}}
乗算は多項式の乗算であり、係数シーケンスの畳み込みと同等です。 すると、
ポ
け
[ ふ ] （ x ） :=
∑
ん ∈
ず
s
ん
（ け ）
φ （
2
け
x − ん ）
{\displaystyle P_{k}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\varphi (2^{k}x-n)}
は、元の信号 f または少なくとも最初の近似値の サブスペース への直交投影であり 、単位間隔あたり2 k のサンプリングレートです。最初の近似値との差は次のように表されます。
P
J
[
f
]
(
x
)
{\displaystyle P_{J}[f](x)}
V
k
{\displaystyle V_{k}}
P
J
[
f
]
(
x
)
=
P
k
[
f
]
(
x
)
+
D
k
[
f
]
(
x
)
+
⋯
+
D
J
−
1
[
f
]
(
x
)
,
{\displaystyle P_{J}[f](x)=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x),}
ここで、差分信号または詳細信号は、詳細係数から次のように計算されます。
D
k
[
f
]
(
x
)
:=
∑
n
∈
Z
d
n
(
k
)
ψ
(
2
k
x
−
n
)
,
{\displaystyle D_{k}[f](x):=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}x-n),}
ウェーブレット変換の
マザーウェーブレット を 表します。
ψ
{\displaystyle \psi }
逆DWT ある M < J の係数列とすべての差列k = M ,..., J − 1が与えられた とき 、 再帰 的 に 計算 する 。
s
(
M
)
{\displaystyle s^{(M)}}
d
(
k
)
{\displaystyle d^{(k)}}
s
n
(
k
+
1
)
:=
∑
k
=
−
N
N
a
k
s
2
n
−
k
(
k
)
+
∑
k
=
−
N
N
b
k
d
2
n
−
k
(
k
)
{\displaystyle s_{n}^{(k+1)}:=\sum _{k=-N}^{N}a_{k}s_{2n-k}^{(k)}+\sum _{k=-N}^{N}b_{k}d_{2n-k}^{(k)}}
または
s
(
k
+
1
)
(
z
)
=
a
(
z
)
⋅
(
↑
2
)
(
s
(
k
)
(
z
)
)
+
b
(
z
)
⋅
(
↑
2
)
(
d
(
k
)
(
z
)
)
{\displaystyle s^{(k+1)}(z)=a(z)\cdot (\uparrow 2)(s^{(k)}(z))+b(z)\cdot (\uparrow 2)(d^{(k)}(z))}
k = J − 1, J − 2,..., M およびすべて 。Z変換表記では次
のようになります。
n
∈
Z
{\displaystyle n\in \mathbb {Z} }
アップ サンプリング演算子は、 指定されたシーケンス内にゼロで埋められた穴を作成します。つまり、結果のシーケンスの 2 番目の要素ごとに指定されたシーケンスの要素があり、他の 2 番目の要素ごとにゼロまたは になります。この線形演算子は、 ヒルベルト空間 では、ダウンサンプリング演算子 の随伴演算子 です 。
(
↑
2
)
{\displaystyle (\uparrow 2)}
(
↑
2
)
(
c
(
z
)
)
:=
∑
n
∈
Z
c
n
z
−
2
n
{\displaystyle (\uparrow 2)(c(z)):=\sum _{n\in \mathbb {Z} }c_{n}z^{-2n}}
ℓ
2
(
Z
,
R
)
{\displaystyle \ell ^{2}(\mathbb {Z} ,\mathbb {R} )}
(
↓
2
)
{\displaystyle (\downarrow 2)}
参照
参考文献 SG Mallat「多重解像度信号分解の理論: ウェーブレット表現」IEEE Transactions on Pattern Analysis and Machine Intelligence、第 2 巻、第 7 号、1989 年 7 月。 I. Daubechies、「ウェーブレットに関する 10 の講義」、SIAM、1992 年。 AN Akansu 乗算器なし準最適 PR-QMF 設計 Proc. SPIE 1818、ビジュアル通信および画像処理、p. 723、1992 年 11 月 AN Akansu 乗算器なし 2 バンド完全再構成直交ミラー フィルタ (PR-QMF) バンク US 特許 5,420,891、1995 AN Akansu サブバンド画像符号化のための乗算器なし PR 直交ミラー フィルタ IEEE Trans. Image Processing、p. 1359、1996 年 9 月 MJ Mohlenkamp、 MC Pereyra Wavelets、その仲間、そして彼らがあなたのためにできること (2008 EMS) p. 38 BB ハバード 『ウェーブレットの世界：数学的手法の誕生物語』 （1998 ピーターズ社）p. 184 SG Mallat ウェーブレット信号処理ツアー (1999 Academic Press) p. 255 A. Teolis ウェーブレットによる計算信号処理 (1998 Birkhäuser) p. 116 Y. ニーバーゲルト 『ウェーブレットを簡単に』 （1999 Springer）p. 95
さらに読む G. Beylkin 、 R. Coifman 、 V. Rokhlin 、「高速ウェーブレット変換と数値アルゴリズム」 Comm. Pure Appl. Math. 、44 (1991) pp. 141–183 doi :10.1002/cpa.3160440202 (この記事は 2400 回以上引用されています。)
:=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\varphi (2^{J}xn) }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b024490cfc2a80bfcae14105c5ad5c52c87c750)
:=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\varphi (2^{k}xn) }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4625f2eab78f08529b341836286918c60e60f868)
}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f932869ac2fffdfa305dde6eea75a24b394fa3af)
=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad6766a74ca82db487d2d09f0e7a3c6186e296b8)
:=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}xn) 、}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4451a9753019f068e1efa436ffc905d20ac0bd1a)
