128
O.Venard - ESIEE/SIGTEL - 2006 1 Compression d’images

Compression d’images

  • Upload
    others

  • View
    15

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 1

Compression d’images

Page 2: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 2

Sommaire• Traitement du signal 2D• Chaîne de compression• Codage par transformée : TKL

– Transformée en cosinus (DCT)– Transformée en ondelettes (DWT)

• Structuration des données– DCT : zig-zag scan– DWT :

• EZW• SPIHT• EBCOT

• JPEG 2000

Page 3: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 3

Lignes

( )1nδ ( )2nδ

Page 4: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 4

Fonction échelon 2D( ) ( ) ( )

⎩⎨⎧ ≥≥

==sinon 0

0et 0 si 1, 21

2121

nnnununnu

Page 5: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 5

Signaux exponentiels 2D

( ) 2121 , nn bannx =

( ) ( )21 expet exp ωω jbja ==Si

( ) ( ) ( )221121 expexp, njnjnnx ωω=( )2211exp njnj ωω +=( )( )2211

2211

sincos

nnjnn

ωωωω++

+=

Page 6: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 6

Séquences séparables

( ) ( ) ( )2121 , nxnxnnx =

( ) ( ) ( )∑=i

i nxnxnnx 2121 ,

Tout signal 2D (avec un nombre fini de valeur non nulle) peut se décomposer

Page 7: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 7

Périodicité

( ) ( )( ) ( )21221

21211

,,,,nnxNnnxnnxnNnx

=+

=+

Page 8: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 8

Périodicité( ) ( )( ) ( )21222211

21122111

,,,,nnxNnNnxnnxNnNnx

=++=++

( )( )22212

12111

,N,N

NNNN

=

=

[ ]21 NNN ′′=• N n’est pas unique,• Det(N) : nombre de points dans une période

Page 9: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 9

Périodicité

( )( )2,4N

2,7N

2

1

−=

=

Page 10: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 10

Système 2D

[ ]xTy =

Page 11: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 11

Opérations de base

( ) ( ) ( )212121 ,,, nnwnnxnny +=

( ) ( )2121 ,, nnxcnny ⋅=

( ) ( )221121 ,, mnmnxnny −−=

Page 12: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 12

Signal discret 2D

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

k kknknkkxnnx δ

( ) ( ) ( )212121 ,,, nnxnncnny ⋅=

Autre opération (sans mémoire) :

Page 13: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 13

Système linéaire

[ ]11 xLy = [ ]22 xLy =

[ ] [ ] [ ] 212121 ybyaxLbxLaxbxaL ⋅+⋅=⋅+⋅=⋅+⋅

( ) ( ) ( )⎥⎦⎤

⎢⎣⎡ −−= ∑ ∑

∞+

−∞=

∞+

−∞=1 222112121 ,,,

k kknknkkxLnny δ

( ) ( ) ( )[ ]∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

k kknknLkkxnny δ

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞==

1 221 21,2121 ,,,

k kkk nnhkkxnny

Page 14: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 14

Invariance par translation( ) ( )[ ]2121 ,, nnxTnny =

( )[ ] ( )22112211 ,, mnmnymnmnxT −−=−−

( )[ ] ( ) ( )212121 ,,, nnxnncnnxT ⋅=?

( )[ ] ( )( )22121 ,, nnxnnxT =

Page 15: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 15

Produit de convolution 2D

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

k kknknhkkxnny

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

l llnlnxllhnny

(1)

(2)

Eq.1

Page 16: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 16

Produit de convolution 2D

( ) 0et 0pour 0, 2121 >>≠ nnnny( )( ) 221121 0et 0si11 NnNnnn <≤<≤++

( ) 221121 0et si1 NnNnnN <≤≥+( ) 221121 et 0si1 NnNnNn ≥<≤+

221121 et si NnNnNN ≥≥

Page 17: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 17

Système séparable( ) ( ) ( ), 2121 nhnhnnh =

( ) ( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,

l llnlnxlhlhnny

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 2221121 ,

l llnlnxlhlh

( ) ( )∑∞+

−∞=−=

12111 ,

lnlnglh

• Convolution 2D à partir de convolutions 1D• Commutatif

Page 18: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 18

stabilité

• RI absolument sommable

• RI d’énergie finie

( ) ∞<∑ ∑∞+

−∞=

∞+

−∞=1 221 ,

n nnnh

( ) ∞<∑ ∑∞+

−∞=

∞+

−∞=1 2

2

21 ,n n

nnh

Page 19: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 20

Réponse en fréquence

( ) ( )212211 ,exp ωωωω Hnjnj +=

( ) ( ) ( )∑∑ −−=1 2

22112121 exp,,n n

njnjnnhH ωωωω

( ) ( )221121 exp, njnjnnx ωω +=

( ) ( ) ( ) ( )( )∑ ∑∞+

−∞=

∞+

−∞=−+−=

1 22221112121 exp,,

l llnjlnjllhnny ωω

( ) ( )2121 ,,2 ωωωπω HH =+ ( ) ( )2121 ,2, ωωπωω HH =+

( ) ( ) ( )2121 , ωωωω GFH =( ) ( ) ( )2121 , ngnfnnh =

Page 20: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 21

TF 2D( ) ( ) ( )∑∑ −−=

1 222112121 exp,,

n nnjnjnnhH ωωωω

( ) ( ) ( ) ωωωωωπ

dnjnjHnnh 221121221 exp,4

1, += ∫∫

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

l llnlnxllhnny

( ) ( ) ( )212121 ,,, ωωωωωω HXY =

Théorème de convolution

Page 21: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 22

Echantillonnage 2D

( )( , ) ,m n

p x y x mX y nYδ+∞ +∞

=−∞ =−∞

= − −∑ ∑

( ) ( ) ( )⎩⎨⎧ ==

==sinon 0

0et 0 si 1, 21

2121

nnnnnn δδδ

Page 22: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 23

Échantillonnage 2D rectangulaire( ) ( )221121 ,, TnTnxnnx a=

Page 23: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 24

Échantillonnage 2D rectangulaire

( ) ∑∑ ⎟⎠

⎞⎜⎝

⎛ −−=

1 2 2

22

1

11

2121

2,21,k k

a Tk

TkX

TTX πωπωωω

TΩ=ω

Page 24: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 25

Reconstuction (rectangulaire)

Averbuch L2T23

( ) ( )⎩⎨⎧ <<

=sinon. 0

,,pour ,, 212121

21

πωπωωωωω

XTTX a

Page 25: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 26

Échantillonnage 2D rectangulaire

Averbuch L2T11;12

Page 26: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 27

Échantillonnage 2D treillis

Averbuch L2T18

⎥⎦

⎤⎢⎣

⎡−1111

⎥⎦

⎤⎢⎣

⎡−ππππ

Page 27: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 28

TFD 2D ( ) ( )∑ ∑

=

=

−−=1

0

1

02121

1

1

2

2

22

2

11

1,,

N

n

N

n

knN

knN WWnnxkkX

( ) ( ) 11

1

1

1

2

2

22

2

1

0

1

02121 ,, kn

N

N

n

N

n

knN WWnnxkkX −

=

=

−∑ ∑ ⎥⎦⎤

⎢⎣⎡=

( ) ( ) 11

1

1

1

1

02121 ,, kn

N

N

nWknGkkX −

=∑=

22

21 NN ⋅

( )2121 NNNN +⋅

( )21221 log

2NNNN⋅

Calcul 2D

Calcul 1D

Calcul 1D TFR

Page 28: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 29

Chaîne de communication• Codage de source: supprimer la

redondance pour représenter de manière plus compacte l’information

• Codage canal: Introduire de la redondance afin d’accroître la capacité à corriger des erreurs

Page 29: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 30

Pourquoi ?

• Télévision– Fréquence d’échantillonnage 13,5 Mhz– Trame luminance (288x720), 2 trames chrominance

(288x360) [4:2:2]– Fréquence trame 50 Hz, résolution 8 bits– Débit :

( ) Mb/s1665083602720288 =×××+×

Page 30: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 31

…Pourquoi ?• Imagerie médicale

– Type d’image :• Scanner (512×512,12 bpp, 30 images/examen)• IRM (256×256,12 bpp, 50 images/examen)• échographie (512×512, 6 bpp, 36 images/examen)• Angiographie (1024×1024, 8bpp, 20 images/examen)

– Besoins de stockage :• 1500 lits : 20 Térabits/années

Page 31: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 32

Comment ? • Exploitation :

– des caractéristiques physiologique de la vision humaine

– Des caractéristiques statistiques des images– méthode efficace de codage

http://www-nt.e-technik.uni-rostock.de/~ts/Datacompression/datacompression.html

Page 32: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 33

Représentation des images couleurs

RGB YUV

(y=0.5)

http://en.wikipedia.org/wiki/Color_space#Color_space_density

⎥⎥⎥

⎢⎢⎢

⎥⎥⎥

⎢⎢⎢

−−−−=

⎥⎥⎥

⎢⎢⎢

BGR

VUY

08131.041869.05.0

5.033126.016875.0114.0587.0299.0

⎥⎥⎥

⎢⎢⎢

⎥⎥⎥

⎢⎢⎢

−−−=

⎥⎥⎥

⎢⎢⎢

VUY

BGR

0772.1171414.034413.01402.101

⎥⎥⎥

⎢⎢⎢

⎥⎥⎥

⎢⎢⎢

−−=

⎥⎥⎥

⎢⎢⎢

BGR

VUY

01111025.05.025.0

⎥⎥⎥

⎢⎢⎢

⎥⎥⎥

⎢⎢⎢

−−−

−=

⎥⎥⎥

⎢⎢⎢

VUY

BGR

25.075.0125.025.01

75.025.01

Page 33: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 34

• YUV : Luminance Chrominances, normes analogiques PAL

• YCbCr : Luminance, chrominance bleu,chrominance rouge, norme numérique

Page 34: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 35

Sensibilité de l’œil aux informations YUV

Averbuch L19T23

Page 35: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 36

Balayage

progressif entrelacé

Averbuch L1T3

Page 36: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 37

Format d’image

Averbuch L1T17

Page 37: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 38

Fréquence d’échantillonnage

Averbuch L2T7

Page 38: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 39

Echantillonnage

Format Y:UVeven: UVodd

chrominance lignes impaireschrominance lignes pairesluminance

Page 39: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 40

Échantillonnage

Averbuch L1T15

Page 40: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 41

Compression de donnée

• Sous-échantillonnage• Décorrélation• Quantification• Précodage• Codage entropique

http://www-nt.e-technik.uni-rostock.de/~ts/Datacompression/flowchart.html

Page 41: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 42

Sous-échantillonnage

Page 42: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 43

Pré-codage

Page 43: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 44

Codage entropique

Page 44: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 45

Décorrélation

Page 45: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 46

Quantification

Page 46: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 47

Quelques définitions

• Bit per pixel (bpp):

• Taux de compression[ ]( )

(nombre total de bits)taille de l'image ,

BbN MN M

1aTb

= ≥

a (bpp de l’image originale, 8 pour N&B)

Page 47: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 48

Information

• Soit une source de N caractères (pixels).

• Les probas associées• Quantité d’information :

si (pi=1) alors I(si)=0.• Entropie, quantité moyenne d’information :

{ }110 ,,,S −= Nsss L

{ }110 ,,,P −= Nppp L

( )nN 2=

( ) ( )ii psI /1log2=

( ) ( )iN

iii

N

ii ppsIpSH /1log)( 2

1

0

1

0∑∑−

=

=

==

Page 48: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 49

Courbe distorsion-débit

Si débit < entropie alors perte d’information donc distorsion

SIGNAL=INFORMATION+REDONDANCE

Page 49: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 50

Évaluation de la distorsion

• Mean square error (MSE):– fm,n: image originale. : image reconstruite

• Peak Signal to Noise Ratio (PSNR):

( )1 1 2

, ,0 0

1 ˆM N

m n m nm n

MSE f fMN

− −

= =

= −∑∑

,m̂ nf

2

10max(dB) 10logPSNRMSE

⎛ ⎞= ⎜ ⎟

⎝ ⎠

(max=255 pour image 8bpp)

Page 50: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 51

Critère psycho-visuel

PSNR = 34.46 dB PSNR = 34.87 dB

Page 51: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 52

Quantification sur n1+1 bits

{ }110 ,,,S −= Nsss L

{ }110 ,,,P −= Nppp L

112 += nNavec

( )i

N

ii ppSH /1log)( 2

1

0∑−

==

Page 52: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 53

Quantification{ }110 ,,,S −′

′′′=′ Nsss L

{ }110 ,,,P −′′′′=′ Nppp L

NN n <=′ +122avec

( ) )(/1log)( 2

1

0SHppSH i

N

ii ≤′′=′ ∑

−′

=

La quantité d’information décroit avec la quantification

Page 53: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 54

Représentation spatiale

( ) ( ) ( )∑ ∑∞+

−∞=

∞+

−∞=−−=

1 222112121 ,,,

k kknknkkxnnx δ

Image ( )21 ,nnx Base ( )∑ ∑∞+

−∞=

∞+

−∞=−−

1 22211 ,

k kknknδ

Page 54: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 55

Allocation de bits

• Soit un budget bit,– Allocation des bits aux ≠ composantes.– Sous la contrainte : minimiser la distorsion.

• Quelles sont les composantes les plus/moins importantes ?

( )∑ ∑−

=

=−=

1

0

1

0

2

,,2 ˆ1 M

m

N

nnmnmQ ff

MNσ

Page 55: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 56

Mean Square Error (MSE)

• Quantification scalaire uniforme

• Quantification scalaire optimale (Lloyd-Max)

bfQ

222 2−= σσ

bfQ c 222 2−= σσ

( )( )∑∑−

=

=−=

1

0

1

0

2

,,,2 ˆM

m

N

nnmnmnmQ fffpσ

•Uniforme :•Gaussienne :

1=cπ

23

=c

Page 56: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 57

Quelles hypothèses ?

• Réaliser ce type de quantification revient à faire les hypothèses suivantes :– Les composantes (pixels) sont non corrélées,– L’énergie est répartie sur l’ensemble des

composantes (pixels) :• Même variance, même contenu informationel

• Sous ces 2 hypothèses, la meilleure allocation est une répartition uniforme sur l’ensemble des composantes.

Page 57: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 58

Modèle d’une image

• Modèle de Markov d’ordre 1 :

• r est souvent de l’ordre de 0,9

[ ]2

( ). ( 1)

f

E f n f nr

σ−

=

Page 58: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 59

Quantification « vectorielle »

• Soit les vecteurs { })(),1( nfnf −

Page 59: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 60

Signal corrélé

Changement de base

Page 60: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 61

Changement de repère

• Transformation orthogonale (rotation)

• Toujours 2 composantes, mais qui n’ont pas la même variance donc pas le même contenu informationel

Page 61: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 62

Allocation de bit

• N pixels; Nb bits (b nombre moyen de bpp),• Chgt de repère ; avec ,• MSE composante :

• Si pdf connue et identique

STY .= ∑=k

kYY( )kkQ b2σ

( )∑−

==

1

0

22 1 N

kkkQQ b

Nσσ avec bNb

N

kk ≤∑

=

1

0

∑−

=

−=1

0

222 2N

k

bkYQ

k

Nc σσ

( ) ∑−+=j

jYkYk Nbb 22

2

1log21 σσ

Page 62: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 63

Troncature des composantes

25 niveaux de quantification

5 niveaux de quantification

Page 63: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 64

Transformation

• Est-il possible d’obtenir une distorsion plus faible pour une quantification dans le domaine transformé ?

• La transformation a deux objectifs :– Concentrer l’énergie sur un minimum de

composantes.– Décorréler les données.

Page 64: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 65

Transformations orthogonalesXAY T=Soit avec

[ ] ijjT

iNA δφφφφφ == − et ,,, 110 L

22T Y XIAA =⇒=

XXAAYA == T

Transformée inverse exacte

Représentation dans la nouvelle base

∑−

==

1

0

N

iiiyX φ Xy T

ii φ=Et

Une quantification de yi réparti l’erreur sur X

Page 65: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 66

Décorrélation

• Soit x une réalisation de X

• On cherche à diagonaliser Rx

• Si Ry est diagonale

– Ry matrice diagonale des valeurs propres.– A matrice des vecteurs propres.

( )( ){ } { } TTT

X xxxxExxxxER −=−−=

xAy T=ARAR X

TY =

ARAR XY =

Page 66: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 67

Concentration de l’énergie

• Soit• On conserve les M premières composantes

• MSE

• Minimisation

• Solution

∑−

==

1

0

N

iiiyX φ

∑−

==

1

0

~ M

iiiyX φ

( ) ( ){ } { } ∑∑−

=

===−−

112~~ N

MiiX

TN

Mi

T RyExxxxEii

φφ

( ){ }∑∑−

=

=−−

11

1minargN

Mii

Ti

N

MiiX

T

iiR φφλφφ

iiiXR φλφ =

Page 67: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 68

Transformée de KL

• La TKL décorrèle les données et minimise l’énergie de l’erreur.

• Le RSB vaut

∑∑∑−

=

=

===

111 N

Mii

N

Miii

TN

MiiX

T

iiR λφλφφφ

∑−

=

=1

1

0N

Mii

N

ii

λ

λ

Page 68: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 69

TKL

Page 69: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 70

Gain de codage

• Puissance du bruit de quantification :

• Dans le cas scalaire optimal avant transformation

• Dans le cas scalaire optimal après transformation

bN

kkYQ N

c 21

0

22 21 −−

=∑= σσ

bN

iiQ N

c 21

0

2 21 −−

=∑= λσ

bNN

iiQ c 2

/11

0

2 2−−

=⎟⎠⎞⎜

⎝⎛= ∏λσ

Page 70: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 71

Gain de codage

• Gain de codage

• G grand si λmax>> λmin

NN

ii

N

iiNG /11

0

1

0

1

⎟⎠⎞⎜

⎝⎛

=∏

∑−

=

=

λ

λ

Ce qui est vrai en cas de forte corrélation

Page 71: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 72

Approximation TKL

• Forme matricielle de

• Si x stationnaire

• Les φi sont les exponentiels complexesTKL TF

iiiXR φλφ =

( ) ( ) ( )tduuutR iiiX φλφ =∫ ,

( ) ( ) ( )tduutuR iiiX φλφ =−∫

Page 72: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 73

Cas discret

( ) ( ) ( )nmnmR iiiX φλφ =∑ ,

• Si x stationnaire ( )( ) ( ) ( )nmnmR iiiNX φλφ =−∑

•Les φi sont les exponentiels complexes, si la convolution est circulaire :

• cad si x est périodique

TKL TFD

Page 73: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 74

Avantages

• La transformation de Fourier pourra être une approximation de la transformée de Karhunen-Loève.

• L’approche par tranformation fréquentielle est adaptée à une allocation de bit prenant en compte la sensibilité des organes sensoriels.

Page 74: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 75

Codage par transformée

Page 75: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 76

TFD

• Algorithme rapide

• HF parasites :– Remontées des « valeurs propres »

• Coefficients complexesN.M 4N.M !!!

( )21221 log

2NNNN⋅

Page 76: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 77

Transformée en cosinus discretTFD sur 2N points après symétrisation du signal

Page 77: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 78

DCT / DFT (1D)

• DFT– N points réels N points complexes entre 0 et Fe

• DCT (DFT signal symétrique)– 2N points réels 2N points complexes entre 0 et Fe

mais …– Signal réel et pair TF réelle et paire, donc– 2N points réels N points réels entre 0 et Fe/2

Page 78: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 79

DCT

• DFT sur 2N points

• DCT pour N pair (DCT-I)

• DCT 2D 8x8

2 1

0

1 2( ) ( ) exp22

N

n

knX k x n iNNπ−

=

⎛ ⎞= −⎜ ⎟⎝ ⎠

( )1

0

2 0.52( ) ( ) cos22

N

DCTn

k nX k x n

NNπ−

=

+⎛ ⎞= ⎜ ⎟

⎝ ⎠∑

( ) ( ) ( ) ( )

( )

7 7

0 0

2 0.5 2 0.5( , ) ( , ) cos cos

4 16 16

1/ 2 0

1

x y

u v u x v yI u v i x y

if zz

else

α α π π

α

= =

+ +⎛ ⎞ ⎛ ⎞= ⎜ ⎟ ⎜ ⎟

⎝ ⎠ ⎝ ⎠⎧ =⎪= ⎨⎪⎩

∑∑

Page 79: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 80

DCT 8x8

Page 80: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 81

DCT 2D

Page 81: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 82

Structure IDCT 8 points

( )cosjiC j iπ= ( )

12cos

jiD

j iπ=

Page 82: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 83

Traitement par bloc

original Composante DC

•Dimension des blocs propriété de stationnarité, condition d’approximation de la TKL•DCT Décorrélation Intra Bloc•Inter bloc non traitée

Page 83: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 84

Traitement inter blocs

• DPCM coding

Page 84: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 85

Organisation des données

Page 85: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 87

Transformée en ondelette

• Continue

• Discrète dyadique

( ) ( ) ⎟⎠⎞

⎜⎝⎛ −

== ∫+∞

∞− abt

atψdtttfbaw a,bba ψψ 1 avec )(),( *

,

( ) ( ) ⎟⎠⎞

⎜⎝⎛ −

== ∫+∞

∞−jjj,nnjnttψdtttfnjw

221 avec )(),( *

, ψψ

Page 86: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 89

Rep

rése

ntat

ion

Tem

ps-F

réqu

ence

( )fH

f1/21/41/8

f

t

V0

W1W2

W3

V0V1

V2

V3

échelle

résolution

W1

W2

W3V3

Page 87: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 90

Analyse multirésolutionÉchelle Résolution

V0

W1

V1

W2

V2

W3

V3

k

K

kK WVV10 =

⊕=

( )⋅n,0φ

( )⋅n,1φ

( )⋅n,2φ

( )⋅n,3φ

( )⋅n,1ϕ

( )⋅n,2ϕ

( )⋅n,3ϕ

( )⋅n,1ψ

( )⋅n,2ψ

( )⋅n,3ψ

Page 88: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 91

Algorithme de Mallat

H1(z)

H0(z)

2

2

[ ]⋅+1jψ

[]⋅+1jφ

[ ]⋅jφ H1(z)

H0(z)

2

2

[ ]⋅+kjψ

[]⋅+kjφ

Page 89: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 94

TO 2D séparable

Η1(z)Η1(z)

Η1(z)Η0(z)

Η0(z)

Η0(z)

lignes colonnes

HH

HL

LH

LL

Page 90: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 95

Histogramme TO

Page 91: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 96

Histogramme luminance image

Page 92: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 97

Image couleur

Page 93: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 98

Embedded Zerotree Wavelet

Page 94: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 99

EZW• sp: Soit un seuil T, si un coefficient > T , il est

significatif au niveau T• sn: significatif negatif• zr: si coefficient < T (il est non significatif), et tous

ses descendants < T, alors il est zerotree root.• iz: si coefficient < T (il est non significatif), et

certains de ses descendants > T, alors il est isolated zero.

D’après Shu-Fang Newman

Page 95: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 100

Exemple EZW

• 26 > 16 sp• 6 < 16

descendants < 16 zr• -7 < 16

descendants < 16 zr• 7 < 16

descendants < 16 zr

• labels a transmettresp zr zr zr

0-2-22-34-44467-71013626

⎣ ⎦ 162 == 26 log0

2T• Seuil initial

• 8 bitsD’après Shu-Fang Newman

Page 96: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 101

EZW : Subordinate Pass

• Ls = {26}• Valeur du coefficient reconstruit

1.5To = 24• TO reconstruite

00000000000000024

D’après Shu-Fang Newman

• Difference 26 – 24 • Avec un quantificateur à 2

niveaux ±To/4 , terme de correction 4

• Reconstruction24 + 4 = 28

• La transmission du terme de correction coûte 1 bit.

00000000000000028

Page 97: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 102

EZW suite

• T1 = ½ * T0 = ½ * 16 = 8• 6 < 8

descendants > 8 iz• -7 < 8

descendants < 8 zr• 7 < 8

descendants < 8 zr• 13 pas de descendants > 8 sp• 10 pas de descendants > 8 sp• 6 pas de descendants < 8 iz• 4 pas de descendants < 8 iz

0-2-22-34-44467-710136*

• labels a transmettreiz zr zr sp sp iz iz

• Requiert 14 bits • Nbre total de bits

9 + 14 = 23

Page 98: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 103

EZW : Subordinate Pass

• Coefficient significatif

1.5T1 = 1.5 * 8 = 12• Ls = {26, 13, 10}• TO reconstruite

Avec un quantificateur 2 niveaux et des niveaux ±T1 / 4 = ± 2

• 26 – 28 = -2 terme de correction = -2• 13 – 12 = 1 terme de correction = 2• 10 - 12 = -2 terme de correction = -2• Chaque correction requiert 1 bit, le

nombre total de bit est 23 + 3 = 26.• Reconstruction

0000000000001212028

0000000000001014026

Page 99: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 104

EZW

• T2 = ½ * T1 = ½ * 8 = 4• 6 > 4 sp• -7 < 4 descendants > 4 sn• 7 > 4 sp• 6 > 4 sp• 4 > 4 sp• 4 > 4 sp• -4 no descendants <4 sn• 2, -2 are coded as iz• 4 > 4 sp• -3, -2, 0 are iz

0-2-22-34-44467-7**6*

• sp sn sp sp sp sp sn iz iz sp iz iz iz

• Requiert 26 bits • Nbre total de bits

= 26 + 26 = 52

Page 100: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 106

JPEG process overview

Page 101: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 107

Example Block From Lena Image

• Each pixel value has been level-shifted by a value of 128 to place in the range (-128,127).

Page 102: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 108

DCT of 8x8 block

• The DCT of the block packs its energy into asmall number of coefficients.

Page 103: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 109

JPEG quantization matrix• Quanzition matrix is then applied (dividing at the

en coder and multiplying at the decoder)

Page 104: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 110

Quantized DCT coefficients

• the process of quantization results in many zero-valued coefficients that can be coded efficiently.

Page 105: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 111

Zig-zag scan & RLC

[0;20],[0;-20],[0;2],[2;2] ,[0;-1],[0;-1],[0;0]EOB

Page 106: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 112

Reconstructed 8x8 image block

Page 107: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 113

Error image

• Energy of the error between the original image block and the reconstructed block is the same inboth the image domain and the DCT domain.

⎟⎠⎞

⎜⎝⎛=

84.2255log20 10PSNR

Page 108: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 114

Blocking artifacts

Original

Page 109: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 115

JPEG Coding• Coefficient category

Page 110: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 116

Catégories de coefficient

ki

offsetcatégorie

Page 111: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 117

JPEG Coding• AC Code

Page 112: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 118

JPEG Coding

• DC Code

Page 113: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 119

JPEG 2000

Page 114: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 120

TO2D• Tuiles• Ondelettes biorthogonales (5-3) et (9-7)

Page 115: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 121

TO2D

Page 116: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 122

Quantification avec zone morte

Page 117: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 123

Régions

Codeblock : codage arithmétiquePrecinct : localisation

Page 118: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 124

EBCOTCodage par plan bit

Codeur arithmétique binaire adaptatif : Codeur MQ

Page 119: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 125

Estimation des probas

VoisinnageBalayage dans codeblock

Maj des probas en fct du contexte et des infos déjàcodées

Page 120: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 126

Ordre d’encodage• A : significant pass

• Proba pour le coef de devenir significatif importante

• B : refinement pass• Augmentation de la résolution des coef déjà

significatif

• C : cleanup pass• Encodage des autres coefs

Page 121: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 127

Passes d’encodage

Page 122: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 128

Ordonnancement des données

Page 123: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 130

EBCOT

Bit plane from 1 to 9

Page 124: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 131

Organisation des Blocs, couches de qualité

Page 125: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 132

progressivité Resolution (4 levels)

Page 126: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 133

Progressivité RSB

0.0625 bpp

0.25 bpp 0.5 bpp 2 bpp

0.125 bpp

Page 127: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 134

Région d’intérêt

Page 128: Compression d’images

O.Venard - ESIEE/SIGTEL - 2006 135

ROI