The lifting steps implementation
Second generation wavelets
Introduction
• The idea of lifting
• Mathematical context
• The filterbank side
• Polyphase representation
• Features
• Reference: “Factoring wavelet transforms into lifting steps”, I. Daubechies, W.
Sweldens, 1996
President of Alcatel Lucent wireless division
Professor @ Princeton University
Inventing lifting
The lifting scheme
• Different approach to biorthogonal wavelet construction
• Sweldens, ~95
• Both linear and nonlinear wavelets
– Integer implementation enabling lossless coding
Biorthogonal basis: why?
• FIR orthonormal filters: no symmetry
• (except Haar filter)
• FIR biorthogonal filters: symmetry
– linear phase
– better boundary conditions
Basis oh the Hilbert space
• Orthonormal basis:
– {e_{n}}_{n∈N}: family of the Hilbert space – < e_{n}, e_{p}>=0 ∀n≠p
– ∀x ∈ H, ∃λ(n)=< x, e_{n}>
– e_{n}^{2}=1
– x=∑_{n }λ(n) e_{n }
Basis of the Hilbert space
• Riesz bases:
– {e_{n}}_{n∈N}: linearly independent
– ∀y ∈ H, ∃A>0 and B>0 : y=∑_{n }λ(n) e_{n } – y^{2}/B ≤ ∑_{n }λ(n)^{2} ≤ y^{2}/A
– λ(n)=< y, e˜_{n}>
– {e˜_{n}}_{n∈N }: dual family
– Biorthogonality relationship: < e_{n}, e˜_{p}>=δ(np) – y=∑_{n }< y, e˜_{n}> e_{n }
– A=B=1 ⇒ orthogonal basis
Biorthogonal filters
h˜
g˜ g
h
↓2
↓2
↑2
↑2
+
x x
] 1 [ )
1 ( ]
~[ ~[1 ]
) 1 ( ]
[ 1
1
n h
n g
n h
n
g n
n
−
−
=
−
−
=
−
−
) (
)
~( ~( )
)
( 1 1
1 1
−
−
−
−
−
=
−
=
z h z z g
z h z z g
h z
( )
^{h z}( )
^{−1} ^{+ g z}^{( )}
^{g z}( )
^{−1} ^{= 2}h z
( )
^{h −z}( )
^{−1} ^{+ g z}^{( )}
^{g −z}( )
^{−1} ^{= 0}perfect reconstruction aliasfree
Rationale
• Goal: Exploit the correlation structure present in most real life signals to build a sparse approximation
– The correlation structure is typically local in space (time) and frequency
• Basic idea
– Split the signal x in its polyphase components (even and odd samples)
– These two are highly correlated. It is thus natural to use one of them (e.g. the odds) to predict the other (e.g. the even)
– The operation of computing a prediction and recording the detail we call lifting step
x_{e} = x
( )
_{2k} _{k∈}x_{o} = x
(
_{2k+1})
k∈( ) ( )
o ' e
o e
x P x d x P x
=
= −
predicted
difference or detail
Biorthogonal FB
h z
( )
^{−1} ^{h z}^{( )}
^{+ g z}( )
^{−1} ^{g z}^{( )}
^{= 2}h −z
(
^{−1})
^{h z}^{( )}
^{+ g −z}(
^{−1})
^{g z}^{( )}
^{= 0}(h,g) in the analysis part (h,g) in the synthesis part
g(z) = z^{−1}h(−z^{−1})
h(z) = −z^{−1}g(−z^{−1})
ˆh^{*}
( )
ω ^{ˆh(ω)+ ˆg}^{*}( )
^{ω} ^{ˆg(ω) = 2}ˆh^{*}
(
ω + π)
^{ˆh(ω)+ ˆg}^{*}(
^{ω + π})
^{ˆg(ω) = 0}Lifting steps
– To get a good frequency splitting, the evens are also updated by replacing them with a smoothed version
– Builtin feature of lifting: no matter how P and U are chosen, the scheme is always invertible and thus leads to critically sampled perfect reconstruction filter banks
( ) ( )
e e
s x U d
x s U d
= +
= −
split
− P
+ x
U
x_{e }
x_{o }
s
+ d
( ) ( )
o ' e
o e
x P x d x P x
=
= −
Polyphase representation
• Given the biorthoganl filters h and g
( ) ( ) ( )
( ) ( )
( ) ^{( )} ^{( )} ( ) ^{( )} ^{( )}
2 1 2
2 2 1
2
2
1
2 2
e o
k
e k
k
k
o k
k
e
o
h z h z z h z
h z h z
h z h z
h z h z h z
h z h z
h z z
−
−
− +
−
= +
=
=
+ −
=
− −
=
∑
∑
even coefficients odd coefficients
P z
( )
^{=} ^{h}^{e}( )
^{z} ^{g}^{e}( )
^{z}h_{o}
( )
z ^{g}^{o}( )
^{z}!
"
#
##
$
%
&
&
&
P z
( )
^{P z}( )
^{−1} ^{t} ^{= I}Polyphase matrix
PR condition
Polyphase representation
→ the other way around
• The problem of finding a FIR wavelet transform then amounts to finding a matrix P(z) with determinant =1
• Once the matrix is given, the filters follow
– One can show that this corresponds to the biorthogonality relations
g(z) = z^{−1}h(−z^{−1})
h(z) = −z^{−1}g(−z^{−1})
P˜(z^{1}) P(z)
HP
↓2 LP
↓2
↑2
z ↑2 z^{1}
+ x_{e}
x_{o}
x
Lazy wavelet
The lifting scheme
• Definition 1. A filter pair (h,g) is complementary if the corresponding polyphase matrix P(z) has determinant 1
– If (h,g) is complementary, so is
• Theorem 3 (Lifting). Let (h,g) be complementary. Then, any other finite filter g^{new}(z) complementary to h is of the form
where s(z) is a Laurent polynomial. Conversely, any filter of this form is complementary to h
• Proof
h, g
( )
( ) ( ) ( ) ( )
^{2}g
newz = g z + h z s z
( ) ( )
^{1}_{0} ^{( )}_{1} ^{det}( )
^{det}( )
^{1}new s z new
P z P z ⎡ ⎤ P z P z
= ⎢ ⎥ → = =
⎣ ⎦
proof and consequences
g ' z
( )
^{= g z}( )
^{+ h z}( )
^{s z}( )
^{2}g_{e}' z
( )
^{2} ^{= g}^{e}( )
^{z}^{2} ^{+ h}^{e}( )
^{z}^{2} ^{s z}( )
^{2}g_{o}' z
( )
^{2} ^{= g}^{o}( )
^{z}^{2} ^{+ h}^{o}( )
^{z}^{2} ^{s z}( )
^{2}!
"
#
$#
h z
( )
is unchanged P ' z( )
^{=} ^{h'}^{e}( )
^{z} ^{g '}^{e}( )
^{z}h'_{o}
( )
z ^{g '}^{o}( )
^{z}%
&
'' '
(
)
**
*
=
h_{e}
( )
z ^{g}^{e}( )
^{z} ^{+ s z}( )
^{h}^{e}( )
^{z}h_{o}
( )
z ^{g}^{o}( )
^{z} ^{+ s z}( )
^{h}^{o}( )
^{z}%
&
'' '
(
)
**
*
=
=
h_{e}
( )
z ^{g}^{e}( )
^{z}h_{o}
( )
z ^{g}^{o}( )
^{z}%
&
' ''
(
)
*
**
× 1 s z
( )
0 1
%
&
''
( )
**= P z
( )
^{1 s z}( )
0 1
%
&
''
( )
**
P(z) ↑2
z^{1}
↑2
+
a x
d
x_{e }
x_{o }
P(z)
↑2
z^{1}
↑2
+
a x
d
x’
?
x’_{e } x_{e }
x_{o }
“ Lifted” FB
( )
( ) ( ) ( )
' 1
' 0 1
' 1
' 0 1
e o
e e
o o
x s z a
x d
x x s z a
P z P z
x x d
⎡ ⎤
⎡ ⎤ ⎡ ⎤
= ⎢ ⎥
⎢ ⎥ ⎢ ⎥
⎣ ⎦
⎣ ⎦ ⎣ ⎦
⎡ ⎤
⎡ ⎤ ⎡ ⎤ ⎡ ⎤
= = ⎢ ⎥
⎢ ⎥ ⎢ ⎥ ⎢ ⎥
⎣ ⎦
⎣ ⎦ ⎣ ⎦ ⎣ ⎦
↑2
z^{1}
↑2
+ x
a
d P(z)
↑2
z^{1}
↑2
+ x
x’
o
P(z)
x’_{e }
s(z) a +
d
x_{e }
x_{o } x_{e }
x_{o }
e
( )
o
x a
x P z d
⎡ ⎤ ⎡ ⎤
⎢ ⎥ = ⎢ ⎥
⎣ ⎦
⎣ ⎦
' ( )
P z
From Swelden’s paper
Analysis FB
P^{new}
( )
z ^{= }^{P z}( )
^{"} _{−s(z}^{1}^{−1}_{) 1}^{0}#
$$
%
&
''→ h^{new}
( )
z ^{= h z}( )
^{− g z}( )
^{s z}( )
^{−2} ^{Update }g(z) = z^{−1}h(−z^{−1})
h(z) = −z^{−1}g(−z^{−1})
↓2 z ↓2 +
x ^{a }
x_{o } d x_{e }
P z
( )
^{−1} ^{t}d’
a
’ s(z)

Equivalent representations
h ↓ 2
g ↓ 2
↑2
↑ 2
a
0 ^{h}a
_{0}g
↓2 z ↓2 +
x ^{a }
x_{o } d x_{e }
P z
( )
^{−1} ^{t} ^{↑2 }z^{1}
↑2
+ x P(z)
x_{e }
x_{o }
Equivalent representations
h ↓ 2
g ↓ 2
↑2
↑ 2
a
0 ^{h}a
_{0}g
↓2 z ↓2 +
x ^{a }
x_{o } d x_{e }
P z
( )
^{−1} ^{t} ^{↑2 }z^{1}
↑2
+ x P(z)
x_{e }
x_{o }
LP
HP ( )
s z

( ) s z
+
LP
HP ( )
s z

( ) s z
+
Towards lossless
s(z) s(z)
 +
LP Xe
HP Xo
do undo
Dual lifting
• Teorem 4. Let (h,g) be complementary. Then any other filter h_{new}(z) complementary to g is of the form
where t(z) is a Laurent polynomial. Conversely, any filter of this form is complementary to g
– New polyphase matrix
– Dual lifting creates a new given by
( ) ( ) ( ) ( )
^{2}h
newz = h z + g z t z
( ) ( )
_{( ) 1}^{1} ^{0}Pnew z P z t z
⎡ ⎤
= ⎢ ⎥
⎣ ⎦
g
g^{new}
( )
z ^{= g z}( )
^{− h z}( )
^{t z}( )
^{−2}Dual lifting
• Prediction steps: the HP coefficients are shaped (lifted) by filtering the LP ones by the filter t(z)
• Update steps: the LP coefficients are shaped by filtering the HP ones by s(z)
• One can start from the lazy wavelet and use lifting to gradually build one’s way up to a multiresolution analysis with particular properties
h
↓ 2g
↓ 2↑ 2
↑ 2
a
0LP
HP
a
_{0}h
g
( ) t z

( ) t z
+
Prediction Update
lifting and dual lifting
The lifting concept
Lifted basis functions
• Lifting
• Dual lifting
h^{new}
( )
z ^{= h z}( )
^{− g z}( )
^{s z}( )
^{−2}g^{new}
( )
z ^{= g z}( )
^{+ h z}( )
^{s z}( )
^{2}does not change → lifting the wavelet through s(z)
h^{new}
( )
z ^{= h z}( )
^{+ g z}( )
^{t z}( )
^{2}g^{new}
( )
z ^{= g z}( )
^{− h z}( )
^{t z}( )
^{−2}does not change → lifting the scaling function through t(z)
Global Lifting
Lifting
Dual Lifting
Lifting ψ
Lifting ϕ
(
^{h g}^{,}) (
^{h}^{new}^{, g}^{new})
(
^{h g}^{,}) (
^{h}^{new}^{,} ^{g}^{new})
Cakewalk construction
↓2
↓2
x ↑2
↑2
+ x  +
 +
s t t s
dual lifting (update)
h
g
lifting (prediction)
h
g
Lifting the Lazy wavelet
↓2
↓2
x ↑2
↑2
+ x  +
 +
s t t s
z z^{1}
Every finite wvt can be obtained with a cakewalk starting from the Lazy wavelet
Lifting theorem
• Theorem 7. Given a complementary filter pair (h,g), then there always exist
Laurent polynomials s_{i}(z) and t_{i}(z) for i=1,...,m and a nonzero constant K so that
– The dual polyphase matrix is given by
• Every finite filter wavelet transform can be obtained by starting with the lazy wavelet followed by m lifting and dual lifting steps, followed by a scaling
( ) ( )
( )
1
1 0 0 1
1 0 1
0 1
m i
i i
s z K
P z t z
K
=
⎡ ⎤
⎡ ⎤
⎡ ⎤
= ⎢ ⎥⎢ ⎥⎢ ⎥
⎢ ⎥
⎣ ⎦ ⎣ ⎦ ⎣ ⎦
∏
P z
( )
^{=} _{−s} ^{1} ^{0}i
( )
z^{−1} ^{1}"
#
$$
%
&
''
i=1 m
∏
^{1 −t}^{i} ^{z}( )
−10 1
"
#
$$
%
&
''
1/ K 0
0 K
"
#
$$
%
&
''
Implementation
Analysis
2
z 2

s_{1}(z) t_{1}(z)
 X_{e}
X
X_{o}

s_{m}(z) t_{m}(z)

1/K
K
LP
HP
2
2 z +
s_{1}(z) t_{1}(z)
+
X +
s_{m}(z) t_{m}(z)
+ LP
HP
K
1/K Synthesis
Integer wavelet transform
z^{1} 2
2
2
2 z

t_{i}(z) s_{i}(z)
t_{i}(z)

+
+ s_{i}(z)
Lazy wavelet
Analysis Synthesis
[round]
[round] [round]
[round]
X_{e}
X_{o}
X X
do undo
Fully inplace implementation
• Odd samples are used to predict even samples and viceversa
– The original memory locations can be overwritten
decomposition tree
Original
Summary
• Biorthogonal (FIR) wavelets
• Perfect reconstruction ensured for any signal extension at borders
• Faster, fully inplace implementation
• Reduced computational complexity
• Nonlinear lifting
• All operations within one lifting step can be done entirely parallel while the only sequential part is the order of the lifting operations
• Allows wavelets mapping integers to integers, important for hardware implementation and lossless coding
• Allows for adaptive wavelet transforms (i.e. wavelets on the sphere)
Application: Objectbased coding
Object1 Object2
Header
Border dimension
Appendix
Laurent polynomials [sweldens paper]