# The lifting steps implementation

## Testo completo

(1)

### The lifting steps implementation

Second generation wavelets

(2)

### Introduction

•  The idea of lifting

•  Mathematical context

•  The filter-bank 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

(3)

### The lifting scheme

•  Different approach to biorthogonal wavelet construction

•  Sweldens, ~95

•  Both linear and non-linear wavelets

–  Integer implementation enabling lossless coding

(4)

### Biorthogonal basis: why?

•  FIR orthonormal filters: no symmetry

•  (except Haar filter)

•  FIR biorthogonal filters: symmetry

–  linear phase

–  better boundary conditions

(5)

### Basis oh the Hilbert space

•  Orthonormal basis:

–  {en}n∈N: family of the Hilbert space –  < en, ep>=0 ∀n≠p

–  ∀x ∈ H, ∃λ(n)=< x, en>

–  |en|2=1

–  x=∑n λ(n) en

(6)

### Basis of the Hilbert space

•  Riesz bases:

–  {en}n∈N: linearly independent

–  ∀y ∈ H, ∃A>0 and B>0 : y=∑n λ(n) en –  |y|2/B ≤ ∑n |λ(n)|2 ≤ |y|2/A

–  λ(n)=< y, e˜n>

–  {e˜n}n∈N : dual family

–  Biorthogonality relationship: < en, e˜p>=δ(n-p) –  y=∑n < y, e˜n> en

–  A=B=1 ⇒ orthogonal basis

(7)

] 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 alias-free

(8)

### 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

xe = x

2k k∈

xo = x

2k+1

k∈

### ( ) ( )

o ' e

o e

x P x d x P x

=

= −

predicted

difference or detail

(9)

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−1h(−z−1)

h(z) = −z−1g(−z−1)

ˆh*

ω ˆh(ω)+ ˆg*

ω ˆg(ω) = 2

ˆh*

ω + π

ˆh(ω)+ ˆg*

ω + π

ˆg(ω) = 0

(10)

### Lifting steps

–  To get a good frequency splitting, the evens are also updated by replacing them with a smoothed version

–  Built-in 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

+ x

xe

xo

s

+ d

o ' e

o e

x P x d x P x

=

= −

(11)

### 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

= he

z ge

z

ho

z go

z

!

"

#

##

\$

%

&

&

&

P z

P z

## ( )

−1 t = I

Polyphase matrix

PR condition

(12)

(13)

### → 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−1h(−z−1)

h(z) = −z−1g(−z−1)

P˜(z-1) P(z)

HP

↓2 LP

↓2

↑2

z ↑2 z-1

+ xe

xo

x

Lazy wavelet

(14)

### 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 gnew(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

new

10 ( )1 det

det

### ( )

1

new s z new

P z P z ⎡ ⎤ P z P z

= ⎢ ⎥ → = =

⎣ ⎦

(15)

g ' z

= g z

+ h z

s z

2

ge' z

2 = ge

z2 + he

z2 s z

2

go' z

2 = go

z2 + ho

z2 s z

2

!

"

#

\$#

h z

### ( )

is unchanged P ' z

= h'e

z g 'e

z

h'o

z g 'o

z

%

&

'' '

(

)

**

*

=

he

z ge

z + s z

he

z

ho

z go

z + s z

ho

z

%

&

'' '

(

)

**

*

=

=

he

z ge

z

ho

z go

z

%

&

' ''

(

)

*

**

× 1 s z

0 1

%

&

''

( )

**= P z

1 s z

0 1

%

&

''

( )

**

P(z) ↑2

z-1

↑2

+

a x

d

xe

xo

P(z)

↑2

z-1

↑2

+

a x

d

x’

?

x’e xe

xo

(16)

### ( ) ( ) ( )

' 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

xe

xo xe

xo

e

o

x a

x P z d

⎡ ⎤ ⎡ ⎤

⎢ ⎥ = ⎢ ⎥

⎣ ⎦

⎣ ⎦

(17)

(18)

Pnew

z = P z

" −s(z1−1) 10

#

\$\$

%

&

''→ hnew

z = h z

− g z

s z

### ( )

−2 Update

g(z) = z−1h(−z−1)

h(z) = −z−1g(−z−1)

↓2 z ↓2 +

x a

xo d xe

P z

−1 t

d’

a

s(z)

-

(19)

h ↓ 2

g ↓ 2

↑2

↑ 2

0 h

0

g

↓2 z ↓2 +

x a

xo d xe

P z

−1 t ↑2

z-1

↑2

+ x P(z)

xe

xo

(20)

h ↓ 2

g ↓ 2

↑2

↑ 2

0 h

0

g

↓2 z ↓2 +

x a

xo d xe

P z

−1 t ↑2

z-1

↑2

+ x P(z)

xe

xo

-

+

-

+

(21)

s(z) s(z)

- +

LP Xe

HP Xo

do undo

(22)

### Dual lifting

•  Teorem 4. Let (h,g) be complementary. Then any other filter hnew(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

new

( ) 11 0

Pnew z P z t z

⎡ ⎤

= ⎢ ⎥

⎣ ⎦

gnew

z = g z

− h z

t z

## ( )

−2

(23)

### 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

↓ 2

↓ 2

↑ 2

↑ 2

0

0

h

g

-

### ( ) t z

+

Prediction Update

(24)

(25)

(26)

•  Lifting

•  Dual lifting

hnew

z = h z

− g z

s z

−2

gnew

z = g z

+ h z

s z

### ( )

2

does not change → lifting the wavelet through s(z)

hnew

z = h z

+ g z

t z

2

gnew

z = g z

− h z

t z

### ( )

−2

does not change → lifting the scaling function through t(z)

(27)

Lifting

Dual Lifting

Lifting ψ

Lifting ϕ

h g,

hnew, gnew

h g,

hnew, gnew

(28)

### Cakewalk construction

↓2

↓2

x ↑2

↑2

+ x - +

- +

s t t s

dual lifting (update)

h

g

lifting (prediction)

h

g

(29)

### 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

(30)

### Lifting theorem

•  Theorem 7. Given a complementary filter pair (h,g), then there always exist

Laurent polynomials si(z) and ti(z) for i=1,...,m and a non-zero 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 −ti z

−1

0 1

"

#

\$\$

%

&

''

1/ K 0

0 K

"

#

\$\$

%

&

''

(31)

Analysis

2

z 2

-

s1(z) t1(z)

- Xe

X

Xo

-

sm(z) tm(z)

-

1/K

K

LP

HP

2

2 z +

s1(z) t1(z)

+

X +

sm(z) tm(z)

+ LP

HP

K

1/K Synthesis

(32)

### Integer wavelet transform

z-1 2

2

2

2 z

-

ti(z) si(z)

ti(z)

-

+

+ si(z)

Lazy wavelet

Analysis Synthesis

[round]

[round] [round]

[round]

Xe

Xo

X X

do undo

(33)

### Fully in-place implementation

•  Odd samples are used to predict even samples and viceversa

–  The original memory locations can be overwritten

(34)

### Summary

•  Biorthogonal (FIR) wavelets

•  Perfect reconstruction ensured for any signal extension at borders

•  Faster, fully in-place implementation

•  Reduced computational complexity

•  Non-linear 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)

(35)

Object1 Object2

(36)

### Appendix

Laurent polynomials [sweldens paper]

(37)

(38)

(39)

Updating...

## Riferimenti

Argomenti correlati :