- Le signal vidéo numérique représente des volumes d’information énormes:

TV numérique ordinaire (4/3) 576x720 CCIR601 4:2:2, 25:2 ipscomposante de luminance Y, Fe = 13,5 MHz

composantes de chrominance Cr, Cb Fe= 6.675 MHzprofondeur : 8bits par pixel/composantevolume d’information 216Mbit/s

TV numérique HD (aspect 16/9 = (4/3)2)50 ips, (1080p) 1920x1080 volume d’information 1. 658 Gbit/sec (1 tera!)WEB TVHD, TV ANYTIME ????

- Pour économiser les ressources de stockage et réduire la bande passante requise lors de la transmission on cherche à comprimer le signal vidéo.

4. Notions de la théorie de l’information

Soit S une source d ’informations et xi (symboles d’un alphabet) les valeurs possibles de l’information.

On peut la modéliser par une variable aléatoire X dont les réalisations sont xi avec une loi de probabilité

L’entropie de la variable aléatoire :

Quantité d’information associée au symbole xi :

Ainsi l’entropie représente l’information propre moyenne associée à un processus (source).

Quantité d’information

ixp

ii

N

ixpxpXH 2

1

0log)(

ii xpxI 2log

Propriétés :

* alors

*supposons que l’alphabet est fini et contient K symboles alors

L’égalité étant obtenue si la variable aléatoire X est équiprobable

Propriétés de l’Entropie

10 ixpi

0)( XH

10,..., KxxX

KXH 2log)(

Distribution équiprobable :

.

Propriétés de l’Entropie

K

xXp i1

KKKXH

K

i

1log

1log

1)( 22

1

0

KXH 2log)(

5. Codage sans pertes

d’informations multimédia Taux de compression

- L’opération de numérisation et de compression du signal est aussi appelée « codage de source ».

- Le codage des signaux multimédia nécessite de connaître les limites atteignables des taux de compression.

- Taux de compression :

Limites atteignables

Le théorème de codage de la source établit qu’il existe un débit binaire (quantité d’information) vers laquelle on peut tendre sans pouvoir comprimer la source d’avantage. Dans le cas d’un codage sans perte cette limite est donnée par l’entropie de la source.

codée ninformatiod' Quantitéinitiale ninformatiod' Quantité

Codage Entropique

Codage de la source : la source X prend ses valeurs dans le dictionnaire C. On appelle codage de la source X une application de C dans l’ensemble des suites finies de l’alphabet {0,1}.

Le code :

Le mot de code :

La longueur moyenne :

Théorème : pour toute source discrète sans mémoire, il existe un code instantané représentant exactement la source et uniquement décodable vérifiant

Où H(X) est l’entropie de la source et est la longueur moyenne du code, exprimés en bit par symbole.

l

1)()( XHlXH

Lss ,...,1

10..01001is

iX slipl

5. Codage sans pertes des informations multimédia

Codage entropique (statistique)

La source S discrète d’informations est caractérisée par son entropie H

- Codage de Shannon-Fano

- Codage de Huffman

- Codage arithmétique

Codage par comptage (RLC)

Codage avec dictionnaire (LZSS,LZW)

Codage Entropique de Shannon-Fano (I)

1) Pour tous les symboles du message développer une liste correspondante des probabilité expérimentales (occurrences)

2) Trier la liste dans l’ordre décroissant des probabilités expérimentales (occurrences)

Exemple :

Message ABEABABABCDCDBAEAAAEAAAABAACACDBDEEDCCDE

Liste triée

Symbole A B C D E

Occurrences 15 7 6 6 5

Codage Entropique de Shannon-Fano (II)

3) Diviser la liste en deux parties, le total des compteurs d’occurrence de la moitié supérieure devant être aussi proche que possible du total de al moitié inférieure

4) Affecter le chiffre binaire 0 à la moitié supérieure de la liste, et le chiffre 1 à la moitié inférieure de la liste

Symbole Occurrence Somme Code

A 15 0

B 7 22 0

-------------------------------------------------------------

C 6 1

D 6 1

E 5 17 1

Codage Entropique de Shannon-Fano (III)

5) Appliquer de façon récursive les étapes 3 et 4 à chacune des deux moitiés, jusqu’à ce que chaque symbole soit devenu une feuille

Symbole Occurrence Somme Code

A 15 00

-------------------------------------------------------- II

B 7 22 01

--------------------------------------------------------- I

C 6 10

-------------------------------------------------------- III

D 6110

-------------------------------------------------------- IV

E 5 17111

Codage Entropique de Shannon-Fano (IV)

Représentation sous forme d’arbre binaire

A B C

D E

Racine

0

0 0

0

1

1

1

Symbole Occurrence Quantité inf Bits Total Taille Sh-F Bits Sh-F

A 15 1,38 20,7 2 30

B 7 2,48 17,36 2 14

C 6 2,70 16,20 2 12

D 6 2,70 16,20 3 18

E 5 2,96 14,8 3 15

Codage Entropique de Huffmann (I)

1952. Algorithme optimal pour construire un code entropique. On peut montrer qu’il n’existe pas d’autre code uniquement décodable de longueur moyenne inférieure pour une source discrète sans mémoire.

Principe : construire progressivement l’arbre binaire en partant des feuilles de l’arbre précédent.

Initialisation de l’arbre :

- Tous les symboles sont les nœuds-feuilles

- Chaque noeud a comme poids la probabilité du symbole (occurrence).

- Liste des nœuds libres contient tous les nœuds

Codage Entropique de Huffmann (II)

Construction de l’arbre :

1) Sélectionner les deux symboles-noeuds les moins probables.

2) Créer le père de ces deux nœuds.

Poids(père) :=Poids(FilsGauche)+Poids(FilsDroit)

3) Ajouter le nœud-père dans la liste des nœuds libres et supprimer les nœuds-fils de la Liste.

4) Étiquetage. Un des fils reçoit 0, l’autre 1

5) Si card(Liste)=1 alors arrêt. Le seul noeud devient la racine

Exemple :

1)15 7 6 6 5

A B C D E

2) 15 7 6 6 5

A B C D E

…

Codage Entropique de Huffmann (III)

11

0 1

11

0 10 1

13

15 7 6 6 5

A B C D E

0 100 101 110111

…

Codage Entropique de Huffmann (IV)

24

0 1

11

0 10 1

13

39

0 1

Codage Entropique de Huffmann (V)

Comparaison avec le codage de Shannon-Fano

Quantité d’information théorique

NbrBits SF NbrBits H

82,25 89 87

Nécessite la transmission de la table des codes

Codage Arithmétique

Rissanen 1976

Principe : un code n’est plus associé à chaque symbole constituant le message, mais plutôt au message constitué de la suite des différents symboles.

Soit l’ensemble des messages pouvant être émis par la source avec les lois de probabilité d’apparition .

On peut définir une suite d’intervalles recouvrant l’intervalle et ayant les longueurs respectives

Le principe de codeur arithmétique : définir pour chaque intervalle un nombre compris entre 0 et 1 et ayant une représentation binaire finie

im

imp

ii hl ,

1,0

imp

ii hl , i

tombe sans ambiguïté dans l’intervalle

soit ,

et« code » la source.

On peut trouver une famille de valeurs avec

des longueurs de représentation binaire vérifiant

(propriété de quasi optimalité du code).

Alors plus le message est long, plus la performance du codage est grande.

Codage Arithmétique (II)

1,0,2 ,1

,

ki

iL

k

kkii

ii hl ,

iiL

iiiii hlhl

2 et

i

2loglog 22 iii mpLmp

iL

Codage ArithmétiqueAlgorithme du Codeur (I)

Codage :Soit les limites hautes et basses du message à la j-ème itération.

jj hl ,

jjj lh

)__(1 coderàsymbollll jjj

)__(1 coderàsymbolhlh jjj

Symbole P(s) Intervalle

l(s) h(s)

E 1/5 0.00<=r<0.20

J 1/5 0.20<=r<0.40

N 2/5 0.40<=r<0.80

Y 1/5 0.80<=r<1.00

Jenny

Codage ArithmétiqueAlgorithme du Codeur (II)

Codage :J alors Jenny 4,0;2,0

Nouveau Symbole

Limite

basse

Limite haute

0.00 1.00

J 0.2 0.4

E 0.20 0.24

N 0.216 0.232

N 0.2224 0.2288

Y 0.22752 0.22880

4,0;2,0

Codage ArithmétiqueAlgorithmes du Décodeur (I)

Décodage :(1) Trouver le symbole qui possède

l’intervalle de message : J

(2) Soustraire la limite basse :0.02752

(3) Diviser par la longueur de r(s) : 0.1376

(4) Aller à (1) jusqu’à atteindre 0

Réalisation pratique : utilisation de l’arithmétique binaire (sur 32 bits par exemple)

)()( srmr

Codage par plages (RLC)Principe : (1) Comptage du nombre

d’apparitions consécutives d’un mot de message à coder.(2) Codage à longueur fixe de la valeur des mots et de nombre d’apparitions(3) Variante : introduction de bit-flag

« codé-non-codé ». Exemple : Message : 1 1 1 1 7 7 7 7 7 255 7 1 8 8 8Code : 1 4 1 1 5 7 0 3 255 7 1 1 3 8Débit initial : 15 *8 =120 bitsDébit final : 1 + 3 + 8 + 1 + 3+ 8+1 + 3 +

3*8 + 1 + 3 + 8 = 64 bitsAdapté aux images sans bruit ou auxvaleurs quantifiées grossièrement.