tim 4 coding 1 .pdf



Nom original: tim-4-coding_1.pdfTitre: Microsoft PowerPoint - tim-4-coding[1].ppt - pdfMachine from Broadgun Software, http://pdfmachine.com, a great PDF writer utility!

Ce document au format PDF 1.3 a été généré par pdfMachine from Broadgun Software, http://pdfmachine.com, a great PDF writer utility!, et a été envoyé sur fichier-pdf.fr le 11/11/2013 à 21:10, depuis l'adresse IP 41.102.x.x. La présente page de téléchargement du fichier a été vue 638 fois.
Taille du document: 3.4 Mo (83 pages).
Confidentialité: fichier public


Aperçu du document


IV. Compression
• 1. Introduction

• 2. Approches directes

• 3. Approches par transformation

• 4. Compression de séquences d'images

IV.1 Introduction
Objectifs

Réduction du volume occupé par les images numériques
pour faciliter leur transfert et/ou leur stockage

Historique

•1952 : Codeur entropique (Huffman)
•1978 : DCT (Pratt)
•1980 : Vectoriel (Linde-Buzo-Gray)
•1986 : Sous-bandes (Woods)
•1986 : Vectoriel sur treillis (Fisher)
•1989 : JPEG
•1989 : MPEG-2

•1989 : Ondelettes (Mallat, Daubechies)
•1990 : Fractales (Jacquin)
•1996 : SPIHT
•1996 : MPEG-4
•1997 : MPEG-7
•1998 : JPEG2000

Applications
• Imagerie médicale  Télémédecine
• Imagerie spatiale

• Imagerie sous-marine

• Archivage divers (Musée, BNF, Empreintes ...)
• Vidéo conférence / visiophone (64 kb/s)
• Télésurveillance

• Video On Demand

• Télévision numérique (150 Mb/s)
...

Classification des méthodes de compression
 Sans pertes / avec pertes contrôlées
 Sans pertes (Huffman, Quadtree)

• image originale = image comprimée  TC limité (#3)

 Avec pertes contrôlées

• On perd l'information qui se voit peu  TC augmente
• Recherche d'un compromis Tc / Qualité

 Directe / Transformation

 Directe  Quantification & codage des pixels de l'image

 Transformation  Quantification & codage des coeff. transformés

 Fonction de la zone élémentaire de traitement
 Pixel, ligne, bloc, image entière ...

Evaluation d'une méthode compression

 Dépend de l'application

• Taux de compression (Tc)
Tc 

Volume image originale
Volume du fichier comprimé

• Qualité

• Critère mathématique (RSB)

Ex : image (512x512x8bpp) avec Tc=10
 512x512x8/10=26215 bits  0.8 bpp





2
b


2

1


RSBdB  10 log10
 EQM ( X , Xˆ ) 



EQM ( X , Xˆ )  



N 1 M 1

Avec

• Critères subjectifs
- Courbes ROC (médecine)
- Notations subjectives (TV)

i 0

j 0

X

ij

 Xˆ ij

M .N



2

• Autres critères
• Vitesse d'exécution : codeur /décodeur
• Complexité

- Additions / multiplications
- Soft / Hard

• Résistance au bruit de transmission
• Intégration de post-traitements

- Prise en compte du récepteur (homme / machine)

• Coût financier
• Scalability

IV.2 Approches directes
 Codage Huffman
 Codage arithmétique
 Codage par longueur de plage
 Codage type dictionnaire
 Quantification scalaire

 Quantification vectorielle
 Méthodes prédictives
 Approche quadtree
 Codage fractale

Codeurs de source
(Th. Information)

 Codage Huffman (1952)
- Algorithme de génération d'un codage optimal symbole par
symbole.
- Code à longueur variable  codes longs pour probas faibles

• Algorithme

 Extraction des probabilités
 Création de l'arbre
 Création de la table d'Huffman
 Codage

 On transmet la table + les codes en binaire 
Lecture de la table d'Huffman
 Création de l'arbre de décodage
 Lecture séquentielle et décodage

Rq : code d'échappement
= Huffman + fixe

 Codage Arithmétique (1976)
 Huffman
 1 symbole = 1 mot-code
 Arithmétique  1 flot de symboles = nbre en virgule flottante


JBIG  Codage des Fax type IV


Codeur

m=0 ; M=1 ;
Tant que !(fin de fichier)
{
i = symbole suivant;
soit [ai ; bi] associé à i ;
s = M-m ;
M = m + s.bi ;
m = m + s.ai ;
}
Renvoyer m, le compacté du fichier



Decodeur

N = nombre codé ;
Faire
{
trouver i / N [ai ; bi[ ;
sortir i ;
s = bi - ai ;
N = (N - ai) / s ;
}
Tant qu'il reste un symbole à lire

• Exemple
si


pi

[ai ; bi[

Huffi

0.1

[0.0 ; 0.1[

111

A

0.1

[0.1 ; 0.2[

110

E

0.1

[0.2 ; 0.3[

101

I

0.1

[0.3 ; 0.4[

100

B

0.1

[0.4; 0.5[

0111

G

0.1

[0.5 ; 0.6[

0110

L

0.2

[0.6 ; 0.8[

00

S

0.1

[0.8; 0.9[

0100

T

0.1

[0.9 ; 1.0[

0101

0.43722077 = ?

10111010 10100100 11011001 01
01111000 00011101 10110010 11010100

Arithmétique
 + de calcul



Huffman
Proba très élévée 1 bit
Peu de symboles ()

Run Length

Codeurs statistiques
- Dépendants de la qualité de la statistique
- Statistique connue par le décodeur

 Codage par longueur de plage (Run length coding)
 Coder le nombre de symboles identiques
000001111100000000000000000 
000000000001111100000000000 
ABCCCCCCABCABC


5w5b17w
11w5b11w
A B !6C A B C A B C

• CCITT, Fax groupe III
 Huffman sur les plages de 0 précédant les 1
• JPEG
 Huffman sur les plages de 0 précédant les coeff. DCT

 Codage de type dictionnaire (1977)
 Coder une extension de la source de longueur variable
1977 : LZ (Lempel & Ziv)

 1984 : LZW (Welch)

 Dictionnaire de symboles incrémenté dynamiquement

 apprentissage

 Fichier codé = suite des adresses des mots du dico

! Gérer l'incrément des bits d'adresse

PKZIP, ARJ  LZW + Huffman



Codeur LZW

ID= {Ci,Wi} , P=
Tant que (symboles à coder)
C = symbole suivant
Si PC  ID
P = PC
Sinon
sortir WP
PC  ID
P=C
Fin si
Fin tant que
sortir WP

ABBABABAC....



Décodeur LZW

ID= {Ci,Wi}
cW = 1er code ; sortir s(cW)
Tant que (codes à lire)
pW = cW
cW = code suivant
Si (s(cW)  ID)
sortir s(cW)
P = s(pW)
C = 1er symbole de s(cW)
PC  ID
Sinon
P = s(pW)
C = 1er symbole de s(pW)
sortir s(PC)
PC  ID
Fin si
Fin tant que

 Quantification scalaire

• Traitement pixel à pixel
 Diminuer le nombre de niveaux de gris utilisés : Nnq < Nnp

• Problèmes
- Comment choisir les seuils de quantification (si) ?
- Comment choisir les niveaux de quantification (qi) ?

 Quantification scalaire uniforme linéaire
max  min
PQ  si 1  si 
Nnq

• Seuils répartis de façon uniforme
• Niveaux = milieux des seuils

qi 

• C'est un quantificateur linéaire

si 1  si
2

r  A. p  B
pˆ 

qB
A

Nnq  1
max  min
Nnq  1
B
 min
max  min
A

avec

 Quantification scalaire uniforme optimale
• Seuils répartis de façon uniforme

PQ  si 1  si 

• Niveaux = Barycentre (histogramme)

max  min
Nnq

 Quantification optimale (Loyd-Max : 1960)



2
• Minimise l'erreur de quantification Min  ( p  pˆ ) 
 ij


• Algorithme itératif très long pour des distributions inconnues
• Tables pour des dist. gaussiennes, laplaciennes, ...
• Fait le travail du codeur !

 Exemple de comparaison (peppers : 512x512x8bpp)

q1
S1
q2
S2
q3
S3
q4

Uni Uni o.
32
38
63
63
95
86
127 127
159 167
191 191
223 209

Remarque
Efficacité variable du codeur entropique !

Max
30
52
75
121
157
180
205

Image originale

Q. uni. lin. : RSB 22,5 dB

Q. uni. opt. : RSB 23,8 dB

Q. Max : RSB 24,2 dB

 Quantification vectorielle
• Extension de la quantification scalaire
 Pixel  Vecteur = bloc de pixels contigus
• Vecteur de taille et forme variable
 Approche optimale : Linde Buzo Gray (1980)

• Phase d'apprentissage : dictionnaire de vecteurs
• Vecteur = représentant d'une région de Voronoï de taille variable
• Dictionnaire connu du codeur /décodeur
 Phase d'apprentissage délicate
 Temps de recherche dans le dictionnaire
 Approche treillis

 Approche Treillis : Fisher, Conway, Sloane (1986)

• Extension de la quantification linéaire uniforme

• Treillis = vecteurs régulièrement répartis dans Rn
 Dictionnaire pré-défini  Pas d'apprentissage
 Algorithme de quantification rapide

• Algorithme de quantification vectorielle sur treillis


L1  Laplacien  Pyramide
L2  Gaussien  Sphère
- Choix de la taille des vecteurs
- Choix du treillis : Zn, An, Dn (4), En(8), n(16)
- Choix de la norme :

 Taux (B)  K rayon du dictionnaire contenant 2nB vecteurs
 Procédure de dénombrement

 Bornage des vecteurs par le facteur d'échelle A = Es/K
 Ramène les vecteurs à l'intérieur du dictionnaire
- Traitement spécial pour les vecteurs d'énergie > Es
 Quantification
- Vecteur  vecteur du dictionnaire le plus proche
 Codage des vecteurs : code produit
- Rayon : code Huffman
- Index : code de longueur fixe

Illustration de la quantification
vectorielle sur treillis
Vecteurs 2x1

Structure de fichier codé

 Méthodes prédictives (1974)

 Exploitent la corrélation entre pixel voisin

Modulation par Impulsions Codées Différentielles (MICD)
DPCM

Prédicteur d' ordre 1 : 1 xˆ 

– Propagation des erreurs
– Prédicteurs non optimaux
 Adaptation aux statistiques locales

 0,5 0,75
Prédicteur d' ordre 3 : 
xˆ 
 0,75

 Approche Quadtree
• Découpage récursif en carrés homogènes
 Critère de split : variance, ...

• Codage de l'arbre : règle de parcours (Peano)

1 | 1001 | 0000 | 01000 | 0001 | 0000

• Codage des régions homogènes : moyenne, interpolation ...

 Compression par fractale
• Les Fractales (B. Mandelbrott)
- Observations naturelles : nuages, plantes ...
- Auto-similarité à toutes les échelles  redondance dans l'image
• Les 'Iterated Functions Systems' (IFS)
- Wi : Transformation affine contractante
rotations,
réflexions

 x '   ai



W i   y '   c i
 z '   .

bi

di
.

position

.   x   ei 
déplacement





.   y    fi 
si   z   oi 

scaling
variance

niveau
de gris

offset
moyenne

• Recherche d'un IFS pour générer une image
 très fort taux de compression mais image spéciale
• Approche directe
 Transformation de l'image = morceau de l'image
image # w1(image)  w2 (image)  ...  wn (image)
 Fougère : 4 transformations = 192 bits
512² : Tc = 1365

• Utilisation de bibliothèque d'IFS
 image segmentée en un ensemble d'IFS connus

• Compression par IFS local (Jacquin 1990)
- Approche valable sur des images quelconques
 Codage

 Mettre les Dj à la taille de R : Sous-échantillonnage +- moyennage
 Définir la zone de recherche
- toute l'image
- limitée  (ei,fi)

 Recherche du (WiDj) le plus proche de Ri
- Mesure de distance  L1, L2, L
Ex : pour L2
-

si 

cov( R i , D j  )

var( D j  )
o i  moy ( R i )  s i .moy ( D j  )

- ai, bi, ci, di = (0,-1,1)

 4 rotations (-90, 90,180,0)
 4 réflexions(_ | / \)

 Codage de longueur fixe ou variable  code = wi

 Codage très long
 Décodage instantané

 Variantes
- formes des blocs
- recherche des wi
- codage des wi

Point de
départ

It n° 2
RSB = 27,33 dB

It n° 1
RSB = 23,8 dB

It n° 3
RSB = 32,16 dB
Tc = 10

IV.3 Approches par transformation

 Représentation différente de l'image
 Décorrélation  Gain en performances
 Temps de calcul supplémentaire
• Une Transformation
 Réversible (sans perte)
 Orthogonale (énergie conservée)
 Rapide
 DCT  JPEG
Ondelettes  SPIHT, JPEG2000

 Compression DCT bloc : JPEG (1989)
• DCT bloc 8x8
 homogénéité locale de l'image
 l'erreur de quantification est localisée au bloc

• Schéma général

• Matrice de normalisation
 allocation des bits aux coeffs avant quantification par arrondi
16
12

14

14
18

24
49

72

11 10 16

24

40

51

12 14 19

26

58

60

13 16

24

40

57

69

22 29

51

87

80

22 37 56

68

109 103

35 55 64

81

104 113

17

64 78 87 103 121 120
92 95 98 112 100 103
Matrice luminance

61 
55 
56 

62 
77 

92 
101

99 

Matrice chrominance

17
18

 24

47
99

99
99

99

18 24 47 99 99 99 99
21 26 66 99 99 99 99
26 56 99 99 99 99 99

66 99 99 99 99 99 99
99 99 99 99 99 99 99

99 99 99 99 99 99 99
99 99 99 99 99 99 99

99 99 99 99 99 99 99

• Lecture zig-zag
 prise en compte de la répartition spatiale de l'énergie pour
faire apparaître de longues plages de coeffs nuls

• Codage du coeff DC
 DPCM d'ordre 1 + Huffman

• Codage des coeffs AC
 Codage hybride : runlength + ... + Huffman
- Huffman = Code (plage de 0 + catégorie)
162 codes : 10catx16lp+2(EOB+16)
Cat.
1
2
3
4
5
6
7
8
9
10

Intervalle des coefficients AC
-3,
-7,
-15,
-31,
-63,
-127,
-255,
-511,
-1023,

..
..
..
..
..
..
..
..
..

-1
,-2
,-4
,-8
,-16
,-32
,-64
,-128
,-256
,-512

_
_
_
_
_
_
_
_
_
_

1,
2,
4,
8,
16,
32,
64,
128,
256,
512,

..
..
..
..
..
..
..
..
..

,3
,7
,15
,31
,63
,127
,255
,511
,1023

AC  | huffman | signe | k-1 bits |
• Exemple
0 -2 -1 02 -1 046  111001 0 0 / 00 0 / 11011 0 / 1010

• Extrait de la table
d'Huffman des AC

Plage de Zéros
0
0
0
0
.
1
1
1
1
.
2
2
.
3
.
16
EOB

Catégorie
1
2
3
4
.
1
2
3
4
.
1
2
.
1
.

Code
00
01
100
1011
.
1100
111001
1111001
111110110
.
11011
11111000
.
111010
.
11111010
1010

• Remarques

 JPEG = méthode générale  à adapter ...
 Très performant à taux faibles (#10)
 Effets de blocs à taux élevés

Tc = 10 / RSB = 30.1 dB

Tc = 20 / RSB = 28.7 dB

 Compression sous-bandes / ondelettes

• Décomposition pyramidale en sous-bandes

 banc de filtres FIR 1D : bi-orthogonaux 9-7
- phase linéaire, rec. parfaite, pas orthogonaux, réguliers
 Concentration d'énergie dans la BB

• Quantification séparée des sous-bandes (Woods 86)
 Sous-bande BF : histogramme 
- DPCM + scalaire + codeur entropique

 Sous-bandes HF : histogramme laplacien
- QV treillis, ...
 Allocation des bits aux sous bandes par modèle
- Min(D) avec B<Bf  Optimisation

- Théorie de la distorsion : bruit de quantification  D=f(B)

DX ( B )  g X ( B ). X2 .2 B.aX ( B )

-  très rapide  sous-optimal (modèle  réalité)

• Exemples

Originale

Sous-bandes Tc=32

Sous-bandes Tc=32
RSB = 30.1 dB

JPEG Tc=32
RSB -3%

Originale

Sous-bandes Tc=60 !!


Aperçu du document tim-4-coding_1.pdf - page 1/83
 
tim-4-coding_1.pdf - page 3/83
tim-4-coding_1.pdf - page 4/83
tim-4-coding_1.pdf - page 5/83
tim-4-coding_1.pdf - page 6/83
 




Télécharger le fichier (PDF)


tim-4-coding_1.pdf (PDF, 3.4 Mo)

Télécharger
Formats alternatifs: ZIP Texte




Documents similaires


tim 4 coding 1
seance2
15 16 td master
tm3
corrige 2010 2011 septembre
chapitre i

Sur le même sujet..




🚀  Page générée en 0.013s