Wavelet 変換： 分解と再構成アルゴリズム

定理6.44 空間L²(R)は次の無限直和として分解される。

L²(R) =V0⊕W0⊕W1⊕. . . . この分解に応じて、各f∈L²(R)は

f=f0+

∑∞ j=0

wj

と一意に表される。

図6.2 ^スケールj^のdyadic^区間Ij,k上の関数f ^{の平均化値}2^j∫

I_j,kf(x)dx と両端点での標本値f(₂^k_j)およびf(^k+1_2j ). fがIj,k上で単調なとき、f(₂^k_j)<

2^j∫

I_j,kf(x)dx < f(^k+1₂j )となる。

係

[a, b) −−−−→^f [a, b)

τ



y y^τ [0,1) −−−−→

f˜

[0.1)

(6.16)

より、[a, b)上の関数fを[0,1)上の関数f˜=τ◦f◦τ⁻¹と自然に同一視することが できる。コンパクトサポート[a, b)上の関数をこの同一視によって[0,1)上の関数と して取り扱うと計算上都合がよい。

一方、関数fをx=. . . ,−2/2^j,−1/2^j,0,1/2^j,2/2^j, . . . といった幅2^−jのdyadic 区間{Ij,k}^k∈Zの端点で関数値を標本化{f(_k

2^j

)}^{kすることがある。幅}|∆x|= ₂¹j

を持つ間隔∆xで関数値を標本化することによって関数fが十分正しく近似できる

（Shannon-Whittakerの標本化定理3.38）。帯域制限のある信号fの最大周波数の2 倍の周期幅（Nyquist周期）で標本化した離散信号列f= (f⁰f¹. . . f^N−1)から信号 fが完全に再現されるからである。

したがって以降では、コンパクトサポートを持つ関数f(x)においては、区間[0,1) 上の関数f(x)˜ と同一視した上で、式(6.15)のPjf(x)˜ を計算するのではなく解像度 2^−jで標本化して得られた2^j個の関数値の組{c^j_k}k=0,...,2^j−1で定義される次の階段

関数fj(x)を考え、これを解像度2^−jによる関数fの近似Pjfとする。

Pjf(x)∼fj(x) =

2∑^j−1 k=0

c^j_kϕ(2^jx−k) =

2∑^j−1 k=0

f Åk

2^j ã

ϕ(2^jx−k).

6.4.1 ウェーブレット変換の分解アルゴリズム

Haarスケーリング関数ϕとwavelet関数ψとの関係 ϕ(2x) =ψ(x) +ϕ(x)

2 ϕ(2x−1) =ϕ(x)−ψ(x)

2

をつかって、ただちに次の関係を得る。

補題6.45

ϕ(2^jx) =ψ(2^j−1x) +ϕ(2^j−1x)

2 (6.17)

ϕ(2^jx−1) =ϕ(2^j−1x)−ψ(2^j−1x)

2 (6.18)

一般に

ϕ(2^jx−2k) =ψ(2^j−1x−k) +ϕ(2^j−1x−k)

2 (6.17^′)

ϕ(2^jx−2k−1) =ψ(2^j−1x−k)−ϕ(2^j−1x−k)

2 (6.18^′)

分割補題6.28は次のようにウェーブレット変換におけるHaar分解係数の関係を 与える。

演習6.46 補題6.45を使って、例6.21で取り上げたf(x) = 2ϕ(4x) + 2ϕ(4x−1) + ϕ(4x−2)−ϕ(4x−3)をHaar分解して、f(x) =ψ(2x−1) +ψ(x) +ϕ(x)となる ことを示しなさい。

定理6.47 (Haar分解定理) スケールjの関数を fj(x) =∑

k

c^j_kϕ(2^j−k)∈Vj

とする。このとき、関数fjは分割補題6.28より fj(x) =wj−1(x) +fj−1(x),

と分解されて、

w_j−1(x) =∑

k

d^j_k⁻¹ψ(2^j−1x−k)∈W_j−1, fj−1(x) =∑

k

c^j_k⁻¹ϕ(2^j−1x−k)∈Vj−1

である。ここで、

c^j−1_k =c^j_2k+c^j_2k+1

2 , (6.19)

d^j_k⁻¹=c^j_2k−c^j_2k+1

2 . (6.20)

証明 fj=∑

k

c^j_kϕ(2^j−k)

=∑

k

c^j_2kϕ(2^jx−2k) +∑

k

c^j_2k+1ϕ(2^jx−2k−1) と添字についての和を偶数と奇数にわけて考え、補題6.45を使うと

fj(x) =∑

c^j_2kψ(2^j−1x−k) +ϕ(2^j−1x−k)

2 +∑

k

c^j_2k+1ϕ(2^j−1x−k)−ψ(2^j−1x−k) 2

=∑

k

Çc^j_2k−c^j_2k+1 2

å

ψ(2^j−1x−k) +

Çc^j_2k+c^j_2k+1 2

å

ϕ(2^j−1x−k)

=wj−1(x) +fj−1(x).

■ 信号fを離散化してスケールJの解像度2^−Jで標本化し、係数{c^J_k =f(_k

2^J

)}^k によって階段関数fJ(x)をひとたび定めると、分解定理6.47を繰り返し適用して得 られるHaar分解

fJ =w_J−1+w_J−2+· · ·+w0+f0

の係数はスケールJにおける初期係数の組{c^J_k}^だけから c^J_k

J → · · · → c^j_k

j → c^j−1_k

j−1 · · · → c⁰₀

↘ · · · ↘ d^j_k

j ↘ d^j−1_k

j−1 · · · ↘ d⁰₀

(6.21)

のような形で段階的に決定できる。{c^j_k} → {c^j_k⁻¹} ∪ {d^j_k⁻¹}^を1段階wavelet変 換（1-step wavelet transformation）と呼ぼう。

係数の個数は^#{c^j_k}=^#{c^j−1_k }+^#{d^j−1_k }^と1段階wavelet変換では変わらない こと、また平均化係数は{c^j_k} → {c^j_k⁻¹}で個数は半分になることに注意する。した がって、最初の標本数2^Jとすると、段階j(J−1≧j≧0)までに得られる全ての係数 の集合¶

{d^J_kJ−1⁻¹}, . . . ,{d^j_k

j},{c^j_k

j}©

の要素数は同じである。実際、0≦kj≦2^j−1 であることに注意すると、段階jまでに得られた係数集合の要素数における関係次の ようにである。

#{c^J_kJ}=^#{c^J−1_kJ−1}+

J−1∑

s=j

#{d^s_ks}+^#{c^j_k

j}

= 2^J−1+ (_J−1

∑

s=j

2^s )

+ 2^j

= 2^J.

こ う し て 段 階 j(J −1 ≧ j ≧ 0) ま で に 得 ら れ た Haar 関 数 系 の 係 数 の 組

¶{d^J_k⁻¹

J−1}, . . . ,{d^j_k

j},{c^j_k

j}©

から階段関数

wj=

2∑^j−1 kj=0

d^j_k

jψ(2^jx−kj), fj=

2∑^j−1 kj=0

c^j_k

jϕ(2^jx−kj)

を計算することによって、離散標本値関数fJは fj=wj−1+· · ·+wj+fj

と分解することができる。

6.4.2 ウェーブレット逆変換の再構成アルゴリズム

節6.4.1のウェーブレット変換の分解アルゴリズムでみたように、関数f を

欲するスケールJ で標本化（離散化）して得られた係数の組{c^J_k}^kから、fJ を w_J−1+· · ·+w0+f0とdyadic階段関数の和として表すための係数c⁰₀（f0の係数）

および詳細化係数集合の組{d^j_ℓ}0≦j<J−1,ℓ=0,...,2^j−1（詳細関数{wj}^{の係数）が得ら} れる。これがウェーブレット変換である。この過程は逆にたどることができ、その操 作をウェーブレット逆変換（inverse wavelet transformation）という。

信号処理とは、関数fJ（これはfと同一視しているのだが）を処理目的に応じ て関数f_J^′ として近似する操作である。処理目的として、たとえば、ノイズの除 去やデータ圧縮がある。したがって、Haar分解における信号処理とは、係数集合 {c⁰_k}k,{d^j_ℓ}0≦ℓ<J,kを目的に応じて別の係数集合、{c⁰_k}kおよび{d^′_k^j}0≦j<J,kに置き 換えることによって近似関数f_J^′ を構成することに他ならない。これをウェーブレッ ト逆変換にともなう再構成アルゴリズムという。

補題6.45はスケールjのHaar関数を一段粗いスケールj−1の関数で表す関係式 である。この関係は可逆な関係

ϕ(x) =ϕ(2x) +ϕ(2x−1) ψ(x) =ϕ(2x)−ϕ(2x−1) にあり、次の補題が成立する。

補題6.48

ϕ(2^j−1x) =ψ(2^jx) +ϕ(2^jx−1) (6.22)

ψ(2^j−1x) =ϕ(2^jx)−ϕ(2^jx−1) (6.23)

定理6.49 (Haar再構成定理) スケールJの関数fJがfJ=wJ−1+wJ−2+· · ·+ w0+f0と分解できて

wj(x) =∑

k

d^j_kψ(2^jx−k)∈Wj, 0≦j < J f0(x) =∑

k

c⁰_kϕ(x−k) であるとする。このとき、fJは

fJ(x) =∑

ℓ∈Z

c^J_ℓϕ(2^Jx−ℓ)∈VJ

と再構成できる。ここで、c^j_ℓはj= 1からj=Jまで次のアルゴリズムによって再 帰的に定められる。

c^j_ℓ=







c^j−1_k +d^j−1_k , ℓ= 2kが偶数, c^j−1_k −d^j−1_k , ℓ= 2k+ 1が奇数.

(6.24)

証明 補題6.48を使うと f0(x) =∑

k

c⁰_kϕ(x−k)

=∑

k

c⁰_k (

ϕ(2x−2k) +ϕ(2x−2k−1) )

=∑

ℓ

˜

c¹_ℓϕ(2x−ℓ) ただし、

˜ c¹_ℓ=

®c⁰_k, ℓ= 2kが偶数 c⁰_k, ℓ= 2k+ 1が奇数. 同様にして、

w0(x) =∑

k

d⁰_kψ(x−k)

=∑

k

d⁰_k (

ϕ(2x−2k)−ϕ(2x−2k−1) )

=∑

ℓ

d˜¹_ℓϕ(2x−ℓ) ただし、

d˜¹_ℓ=

®d⁰_k, ℓ= 2kが偶数

−d⁰_k, ℓ= 2k+ 1が奇数. したがって

f0(x) +w0(x) =∑

ℓ

c¹_ℓϕ(2x−ℓ)

とすると

c¹_ℓ= ˜c¹_ℓ+ ˜d¹_ℓ







c⁰_k+d⁰_k, ℓ= 2kが偶数 c⁰_k−d⁰_k, ℓ= 2k+ 1が奇数. を得る。さらに、w1=∑

kd¹_lψ(2x−k)についても同様に考えると f2(x=f0(x) +w0(x) +w1(x) =∑

ℓc²_ℓϕ(2²x−ℓ) として

c²_ℓ= ˜c²_ℓ+ ˜d²_ℓ







c²_k+d²_k, ℓ= 2kが偶数 c²_k−d²_k, ℓ= 2k+ 1が奇数.

を得る。この過程をfJ=fJ−1+wJ−1まで再帰的に繰り返して結果を得る。 ■

6.4.3 ^具体例

次の関数を考えてみよう。

f(x) = sin(2x) cos( x³)

+

Åsin(110(x−2)) 110(x−2)

ã²

−Åsin(95(x−1)) 95(x−1)

ã² (6.25)

区間[0, π]での様子（図6.3）を観察すると、狭い区間での急激な関数値の変化（ス

パイク）が二箇所x= 1およびx= 2の付近にあることがわかる。

区間[0, π)をN = 2⁸ = 254個のスケールJ = 8のdyadic区間{I8,k}k に 分割し、その左端x= ₂^k8,(k = 0, . . . ,2⁸−1)で標本化した関数値の組を{c⁸_k = f(k

2⁸

)}k=0,...,2⁸−1とする。Mathematicaは、段階jのスケーリング関数ϕ(2^jx−k) をHaarScale[x, j, k]、[0, π]上の関数f(x)を式(6.16)の意味で[0,1]上の関数 f(x)˜ として同一視してspiked[x]で定義しておくと、標本値の組{c⁸_k}^をcoeffと して求めて次のようにしてスケールJ= 8の階段関数f8(x)を表示できる。ここで、

Mathematicaの添字が1から始まることを考慮して、coeff[k + 1]としているこ とに注意しよう。

HaarScale[x_Real, j_Integer, k_Integer] :=

If[x < k/2^j || (k + 1)/2^j < x, 0, 1]

j=8;

ドキュメント内 i 3 Mathematica Fourier Fourier Dirac Dirac Fourier Haar 7.4 (MRA) 8 R L 2 {V j } j Z j Z V j V j+1 j Z V j = L 2 (R) f(2x) V j+1 f( (ページ 192-200)