The lifting steps implementation

39  Download (0)

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)

Biorthogonal filters

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

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

P

+ x

U

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)

Polyphase representation

(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

g

new

z = g z + h z s z

( ) ( )

10 ( )1 det

( )

det

( )

1

new s z new

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

= ⎢ ⎥ → = =

⎣ ⎦

(15)

proof and consequences

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)

“ 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

xe

xo xe

xo

e

( )

o

x a

x P z d

⎡ ⎤ ⎡ ⎤

⎢ ⎥ = ⎢ ⎥

⎣ ⎦

⎣ ⎦

' ( )

P z

(17)

From Swelden’s paper

(18)

Analysis FB

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)

Equivalent representations

h ↓ 2

g ↓ 2

↑2

↑ 2

a

0 h

a

0

g

↓2 z ↓2 +

x a

xo d xe

P z

( )

−1 t ↑2

z-1

↑2

+ x P(z)

xe

xo

(20)

Equivalent representations

h ↓ 2

g ↓ 2

↑2

↑ 2

a

0 h

a

0

g

↓2 z ↓2 +

x a

xo d xe

P z

( )

−1 t ↑2

z-1

↑2

+ x P(z)

xe

xo

LP

HP ( )

s z

-

( ) s z

+

LP

HP ( )

s z

-

( ) s z

+

(21)

Towards lossless

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

h

new

z = h z + g z t z

( ) ( )

( ) 11 0

Pnew z P z t z

⎡ ⎤

= ⎢ ⎥

⎣ ⎦

g

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

h

↓ 2

g

↓ 2

↑ 2

↑ 2

a

0

LP

HP

a

0

h

g

( ) t z

-

( ) t z

+

Prediction Update

(24)

lifting and dual lifting

(25)

The lifting concept

(26)

Lifted basis functions

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

Global Lifting

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)

Implementation

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

decomposition tree

Original

(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)

Application: Object-based coding

Object1 Object2

Header

Border dimension

(36)

Appendix

Laurent polynomials [sweldens paper]

(37)

Filters and Laurent polynomials

(38)

Laurent polynomials

(39)

Laurent polynomials

figura

Updating...

Riferimenti

Argomenti correlati :