1. No category

リフティング入門
藤ノ木 健介
大島商船高等専門学校情報工学科
e − mail : fujinoki@oshima − k.ac.jp
概要
本入門チュートリアルでは Wim Sweldens の考案した
Lifting scheme [1, 2] を紹介する．リフティングは (1) 完
全再構成フィルタの容易な修正・構成を与える他，(2)
Mallat 変換の高速実装法，(3) 第二世代ウェーブレット
(例えば [3, 4]) の構成法として知られているが，ここで
は (1) と (2) を扱う．
で与えられる．ここで，
(
ˆ
h(ω)
b
M(ω) =
gˆ (ω)
は modulation 行列と呼ばれる．逆変換は
(
)
(
)
T
cˆ j (ω)
cˆ j−1 (2ω)
b
e
= M (ω) ˆ
cˆ j (ω + π)
d j−1 (2ω)
リフティングは次の 3 ステップで記述できる [5]．
1. Split: (Lazy wavelet 変換) 信号 {c[k]}k∈Z を偶数と奇
数番地にわける．
c j,o [k] = c j [2k + 1]
(1)
2. Predict: prediction 作用素 p により c j,e を使って c j,o
を予測し，その差分を d j−1 として c j,o と置き換える．
c j,o [k] → d j−1 [k] = c j,o [k] − p(c j,e )[k]
(2)
3. Update: update 作用素 u により prediction の結果 d j−1
を使って c j,e をスムースな c j−1 として置き換える．
c j,e [k] → c j−1 [k] = c j,e [k] + u(d j−1 )[k]
(3)
4. Normalize (option): 変換前後で L2 ノルムが変わらな
いよう定数 K ∈ R で正規化する．
c j−1 [k] = K c j−1 [k]
d j−1 [k] = K −1 d j−1 [k]
c j [2k + 1] = c j,o [k] = d j−1 [k] + p(c j,e )[k]
2
b
と表せる．P(ω)
はポリフェーズ行列と呼ばれる．
(
)
hˆ e (ω) gˆ e (ω)
b
P(ω) = ˆ
ho (ω) gˆ o (ω)
完全再構成条件 (8) は
b
e P(ω)
b †=I
P(ω)
ω∈R
k∈Z
としたとき，双直交フィルタ {h[k], g[k]}k∈Z による離散
ウェーブレット変換は
)
(
)
(
1 b∗
cˆ j−1 (2ω)
cˆ j (ω)
= M (ω)
(6)
dˆ j−1 (2ω)
cˆ j (ω + π)
2
(10)
bと M
b の関係は以下のとおりである．
となる．P
1 b∗
†
†
b
b∗ (ω) = P(2ω)
b
P(2ω)
= M
(ω) U(ω), M
U(ω)† (11)
2
(
)
1
e−iω
b
U(ω) =
(12)
1 e−i(ω+π)
3
(5)
(8)
を満たすとき，それらは完全再構成フィルタと呼ばれる．
ポリフェーズ表現では信号 c j [k] を偶数 cˆ j,e (ω) =
∑
∑
−iωk
と奇数 cˆ j,o (ω) = k∈Z c j [2k + 1]e−iωk で
k∈Z c j [2k]e
独立に扱う．このとき変換 (6) と逆変換 (7) は
(
)
(
)
(
)
(
)
cˆ j−1 (ω)
ˆ j,e (ω)
cˆ j,e (ω)
cˆ j−1 (ω)
b
† c
b
e
= P(ω)
,
= P(ω) ˆ
dˆ j−1 (ω)
cˆ j,o (ω)
cˆ j,o (ω)
d j−1 (ω)
(9)
(4)
Perfect reconstruction filters
信号 {c[k]}k∈Z のフーリエ変換を
∑
c j [k] e−iωk ,
cˆ j (ω) =
(7)
T
b
e (ω) M
b∗ (ω) = 2I
M
ここで，predict をリフティング，update を双対リフティ
ングと呼ぶ（文献により逆の場合もある）．各リフティ
ングステップは構造上，逆変換が容易に可能である．
c j [2k] = c j,e [k] = c j−1 [k] − u(d j−1 )[k]
)
b
˜
e
であり M(ω)
は双対フィルタ {h[k],
g˜ [k]}k∈Z を用いて同様
に構成される．フィルタの組が
1 Lifting in spatial (time) domain
c j,e [k] = c j [2k]
ˆ + π)
h(ω
gˆ (ω + π)
Lifting in polyphase (frequency) domain
時間領域におけるリフティングステップは，ポリフェー
ズ行列を次の形に分解した各行列に対応している．
)
)(
) m (
(
1
0
0 ∏ 1 uˆ i (ω)
b †= K
(13)
P(ω)
pˆ i (ω) 1
1
0 1/K i=1 0
ここで，K は定数で pˆ i (ω) と uˆ i (ω) は三角多項式である．
双対ポリフェーズ行列は逆行列によって決まる．
b
e
b † −1
P(ω)
= P(ω)
 1 (
) (
)(



1
0 1 −ˆui (ω) 
 1/K
∏
=



 0

0
1
−
p
ˆ
(ω)
1
i
i=m
0
K
) (14)
ユークリッドの互除法を用いれば，離散ウェーブレット
b は (13) の形
変換に用いられるすべての FIR フィルタ P
に分解できる [6]．このような elementary 行列を用いた
サブバンド変換は信号処理におけるフィルタバンクの分
野では ladder structure として知られている [7]．
˜ ψ)
˜ → (φu , ψu , φ,
˜ ψ˜ u ) となる．
Update の場合は (φ, ψ, φ,
∑
∑
√
φu (t) = 2
h[k] φu (2t − k) +
u[−k] ψu (t − k)
√ ∑
2
g[k] φu (2t − k)
k
ψu (t) =
4 Lifting wavelet fitlers
˜ −
ψ˜ u (t) = ψ(t)
˜ˆ
hˆ˜ p (ω) = h(ω)
+ gˆ˜ (ω) p(2ω)
ˆ
p
ˆ
gˆ (ω) = gˆ (ω) − h(ω) pˆ ∗ (2ω)
ˆ
hˆ u (ω) = h(ω)
+ gˆ (ω) uˆ ∗ (2ω)
˜ˆ
gˆ˜ u (ω) = gˆ˜ (ω) − h(ω)
uˆ (2ω)
(15)
(22)
k
˜ = φ(t)
˜
φ(t)
Prediction 作用素 pˆ と Update 作用素 uˆ によって，双
˜ g˜ ) は新しい双直交
直交ウェーブレットフィルタ (h, g, h,
u p ˜p u
ウェーブレットフィルタ (h , g , h , g˜ ) へと修正される．
∑
˜ − k)
u[k] φ(t
k
˜ g˜ ) → (hu , g, h,
˜ g˜ u ) となるの
フィルタの update は (h, g, h,
で g は変化せず gˆ (0) における零の個数は変わらない．一
˜ ψ)
˜ → (φu , ψu , φ,
˜ ψ˜ u ) により異なる関数
方で ψ は (φ, ψ, φ,
ψu へと修正されている．しかし，ψu の消滅するモーメ
ントの個数は ψ と同じになっている．Predict に関して
は，ψ˜ と ψ˜ p において同様のことが成り立つ．
6
Mallat transform via lifting
分解：
行列形で書くと Predict は
) (
)(
)
ˆ
ˆ
1
0 h(ω)
h(ω)
=
− pˆ ∗ (2ω) 1 gˆ (ω)
gˆ p (ω)
 (
ˆ
) ˆ 
˜ 
h(ω)
h˜ p (ω)
1 p(2ω)
ˆ


=

ˆg˜ (ω) 
0
1
gˆ˜ (ω)
cuj−1 [k] = c j−1 [k] +
(
(16)
d pj−1 [k] = d j−1 [k] −
∑
u[k − n] d j−1 [n]
p[k − n] c j−1 [n]
再構成：
∑
∑
u[k − n] d j−1 [n]
n
( u )
hˆ (ω)
)(
)
ˆ
1 uˆ ∗ (2ω) h(ω)
=
gˆ (ω)
0
1
gˆ (ω)
 (
ˆ
) ˆ 
˜ 
˜

 h(ω)
1
0 h(ω)


 u  =
−ˆu(2ω) 1 gˆ˜ (ω)
gˆ˜ (ω)
d j−1 [k] = d pj−1 [k] +
(
g p [n] = g[n] −
∑
k
∑
∑
hu [n] = h[n] +
References
(19)
∑
(20)
k
g˜ u [n] = g˜ [n] −
Lifting wavelets and scaling functions
˜ ψ)
˜ は Predict によっ
双直交ウェーブレット基底 (φ, ψ, φ,
p ˜p ˜p
て双直交性を保ったまま (φ, ψ , φ , ψ ) へと修正される．
ψ p (t) = ψ(t) −
∑
p[−k] φ(t − k)
∑
√ ∑
˜ φ˜ p (2t − k) +
φ˜ p (t) = 2
p[k] ψ˜ p (t − k)
h[k]
k
√ ∑
g˜ [k] φ˜ p (2t − k)
2
k
k
k
[3] I. Daubechies, I. Guskov, P. Schr¨oder and W. Sweldens:
Wavelets on irregular point sets, Phil. Trans R. Soc. A,
Vol. 357 No. 1760, pp. 2397–2413, 1999.
[4] P. Schr¨oder and W. Sweldens: Spherical wavelets: Efficiently representing functions on the sphere, Computer
Graphics Proceedings, SIGGRAPH95, 161–172, 1995
˜ − 2k] u[k]
h[n
k
φ(t) = φ(t)
[1] W. Sweldens: The lifting scheme: a custom-design construction of biorthogonal wavelets, J. Appl. Comput.
Harmonic Analysis, Vol. 3, No. 2, pp. 186–200, 1996.
[2] W. Sweldens: The lifting scheme: a construction of
second generation wavelets, SIAM J. Math. Analysis,
Vol. 29, No. 2, pp. 511–546, 1997.
h[n − 2k] p[−k]
g[n − 2k] u[−k]
(24)
n
g˜ [n − 2k] p[k]
k
p[k − n] c j−1 [n]
(18)
である．(15) の逆フーリエ変換は次を得る．
˜ +
h˜ p [n] = h[n]
(23)
n
(17)
Update は
ψ˜ p (t) =
∑
n
c j−1 [k] = cuj−1 [k] −
5
k
(21)
[5] W. Sweldens and P. Schr¨oder: Building your own
wavelets at home, ACM SIGGRAPH course notes,
1996.
[6] I. Daubechies and W. Sweldens: Factoring wavelet
transforms into lifting steps, J. Fourier Anal. Appl.,
Vol. 4, No. 3, pp. 247–269, 1998.
[7] T. A. C. M. Kalker and I. Shah: Ladder structures for
multidimensional linear phase perfect reconstruction filter banks and wavelets, In Proceedings of the SPIE Conference on Visual Communications and Image Processing, pp. 12–20, 1992.