CM1 - Signal et Information

Mise en œuvre du TNS Page 1 sur 64

Novembre 2012.

Traitement Numérique du SignalCM1 : Signal et information

Université du Havre, IUT du Havre

Département GEII


PPN 2008: MC-II3

Traitement du signal

Applications en GEII

Mise en œuvre

Test

DSP

CAN/CNATF, compression, codage


Signal et Information

Information

Signal

Compression sans perte

Compression destructive

Conclusion

Plan


1. Information


Information

Sens du mot information:

Information : Contenu, intérêt

L'information est un concept ayant plusieurs sens. Il est étroitement lié aux notions de contrainte, communication, contrôle, donnée, formulaire, instruction, connaissance, signification, perception et représentation. L'information désigne à la fois le message à communiquer et les symboles utilisés pour l'écrire ; elle utilise un code de signes porteurs de sens tels qu'un alphabet de lettres, une base de chiffres, des idéogrammes ou pictogrammes. Au sens étymologique, l'information est ce qui donne une forme à l'esprit. Elle vient du verbe latin informare, qui signifie "donner forme à" ou "se former une idée de". Hors contexte, elle représente le véhicule des données comme dans la théorie de l'information et, hors support, elle représente un facteur d'organisation.

http://fr.wikipedia.org/wiki/Information


Information

Sens du mot information:


Selon la théorie de l'information, des données contiennent de l'information quand celles-ci ne sont que peu compressibles et qu'elles sont complexes. En effet, l'information contenue dans un message composé d'une seule lettre se répétant un grand nombre de fois tel que « AAAAAAAAA... » est quasiment nulle. La conception la plus répandue de l'information est liée au couple "message + récepteur", le dernier possédant des implicites valorisant le message (de fait, tout message est incompréhensible sans ces implicites). Ainsi, la phrase "Médor est un chien" contient plus d'information que "Médor est un quadrupède", bien que la seconde contienne plus de lettres. La différence est à mettre au compte de la connaissance d'un dictionnaire implicite et faisant partie du contexte. Les notions de quantité d'information et d'entropie font l'objet d'une discipline spécialisée, la théorie de l'information, initiée par Shannon.

http://fr.wikipedia.org/wiki/Information


Stockage

Traitement

Transmission

Information

Vecteurs d’information: schéma fonctionnel Sources d ’information; Moyens de codage et d’adaptation; Moyens de stockage, de traitement et de transmission.


Adaptation

Codage

Adaptation

Codage

Présentation

Utilisateur

Sourced’information

Emetteur


Information


Sourced'information Message Signal émis

Émetteur Récepteur DestinationMessage

Sourcede bruit

Signal reçu

Bruit

++

Vecteurs d’information: schéma fonctionnel Sources d ’information; Moyens de codage et d’adaptation; Moyens de stockage, de traitement et de transmission. Source de bruit: Perturbation.


2. Signal


Signal

Signal : Message

Un signal est un message simplifié et généralement codé. Il existe sous forme d'objets ayant des formes particulières :

Il existe sous forme d'objet ayant une forme particulière.

FRANCE FRANCE FR

GERMANY ALLEMAGNE DE

GREECE GRÈCE GR

ITALY ITALIE IT

SPAIN ESPAGNE ES

UNITED KINGDOM ROYAUME-UNI GB

Codets alpha-2 correspondants de l'ISO 3166-1

STOP


Signal

Signal : Message


Le signal électrique est une des formes les plus récentes de signal.

L'alphabet morse ou code morse, est un code permettant de transmettre un texte à l'aide de séries d'impulsions courtes et longues, qu'elles soit produites par des signes, une lumière ou un geste.Inventé par Samuel Morse en 1835 pour la télégraphie, ce codage de caractères assigne à chaque lettre, chiffre et signe de ponctuation une combinaison unique de signaux intermittents. Le code morse est considéré comme le précurseur des communications numériques.


Signal

Signal : Message


En électronique, on utilise le signal analogique ou numérique.


Signal

Signal : Message


En informatique, le signal permet la communication :Échange de données inter-processus.Synchronisation des processus.

Systèmes de transmission d'information entre périphériques :Filaire: IEEE 1394, SCSI, USB, ATA, SATA, eSATA…Réseau: Ethernet, InfiniBand, TokenTing, CPL…Sans fils: Bluetooth, WiFi, irDA, WirelessUSB

Les signaux lumineux permettent la communication à grande distance.


Signal

Signal : Extension

Une image est un signal (x, y).

En informatique, l'image brute (raw) est codée au format BMP : Exemple : Image 4x2 = 8 pixels codés sur 24 bits(/pixel)

1 2 3 4

5 6 7 8

Taille du fichier (octets) : No = 24 bits = 3 octets

Taille = En-tête + NXNYNo

Soit Taille = 54 + 4x2x3 = 78 octets

NY = 2 pixels

NX = 4 pixels


Signal

Signal : Extension


En informatique, l'image brute (raw) est codée au format BMP : Exemple :

Pixel 1: Code RVB (little-endian)i.e. B = "FF", V = "00", R = "00"


Signal

Signal : Extension


En informatique, l'image brute (raw) est codée au format BMP : Exemple :

Octets Signification

42 4D Caractères B($42) et M($4D) indiquant un fichier de type BMP

4E 00 00 00 Taille du fichier $0000004E = 78 octets (de l'offset 0 à l'offset 77)

00 00 00 00 Réservé (toujours à 0)

36 00 00 00 Offset de l'image $00000036 = 54

28 00 00 00 Taille de l'entête $00000028 = 40 octets

04 00 00 00 Largeur de l'image $00000004 = 4 pixels

02 00 00 00 Hauteur de l'image $00000002 = 2 pixels

01 00 Nombre de plans utilisés $0001 = 1

18 00 Nombre de bits par pixel = $0018 = 24 (3 octets)

00 00 00 00 Méthode de compression : 0 pas de compression

18 00 00 00 Taille de l'image $00000018 = 24 octets = 8 (pixels) x 3 (octets par pixel)

C4 0E 00 00 Résolution horizontale $00000EC4 = 3780 pixels par mètre

C4 0E 00 00 Résolution verticale $00000EC4 = 3780 pixels par mètre

00 00 00 00 Couleurs utilisées : 0 palette entière

00 00 00 00 Nombre de couleurs important

14

40


Signal

Signal : Extension


En informatique, l'image brute (raw) est codée au format BMP :

Octets Signification

FF 00 00 B=255, V=0, R=0 : Bleu

00 00 00 B=0, V=0, R=0 : Noir

FF 00 FF B=255, V=0, R=255 : Violet

FF FF FF B=255, V=255, R=255 : Blanc

00 00 FF B=0, V=0, R=255 : Rouge

00 FF 00 B=0, V=255, R=0 : Vert

00 FF FF B=0, V=255, R=255 : Jaune

FF FF 00 B=255, V=255, R=0 : Cyan


Signal

Signal : Extension

Un signal est un message simplifié et généralement codé. Ce signal peut comporter plus de une dimension :

En général, par signal on entend : y(x) ou x(t).

Par extension, une image (2D) est aussi un signal :Monochrome: (x, y, 0 ou 1) 16 couleurs: (x, y, 0 à 2^41) 256 couleurs: (x, y, 0 à 2^81) 65536 couleurs: (x, y, 0 à 2^161) 24 bits couleurs: (x, y, 0 à 2^241)

Par extension, une vidéo (3D) est aussi un signal :Monochrome: (x, y, t, 0 ou 1) 16 couleurs: (x, y, t, 0 à 2^41) 256 couleurs: (x, y, t, 0 à 2^81) 65536 couleurs: (x, y, t, 0 à 2^161) 24 bits couleurs: (x, y, t, 0 à 2^241)


Signal

Signal : Extension

Un signal est un message simplifié et généralement codé. Ce signal peut comporter un nombre de dimensions variables :

Par extension, une vidéo "3D" (hors temps, 4D en fait) est aussi un signal :Couleurs: (x, y, z, t, niveau couleur)

En pratique, une vidéo "3D" est constituée de deux vidéos, une pour chaque œil : principe de la stéréo

Couleurs: 2(x, y, t, niveau couleur)

Il existe cependant des vraies images 3D animées (4D, donc) :

Scanner: (x, y, z, t, niveau couleur)

http://fr.wikipedia.org/wiki/Scanner_(médecine)


Signal

Signal : Extension

Un signal est un message simplifié et généralement codé. Ce signal peut comporter un nombre de dimensions variables :

Se pose alors le problème de la représentation de ces données :

http://fr.wikipedia.org/wiki/Imagerie_par_résonance_magnétique


3. Compression


Compression

Quantification du codage:

Quantification de l'information :

Codage adapté à l'alphabet.

Probabilité d'occurrence p(x) inconnue...

Compression : Réduction du codage et conservation de l'information

Nombre de symboles.

Probabilité d'occurrence.

Nombre de symboles.

Nombre de bits nécessaires.Nombre de symbolesNom

Binaire

Doigts

Jours

Mois

Chiffres

Alphabet

ASCII

ASCII étendu

Niveaux sur 16 bits

Niveaux sur 24 bits

2 (0, 1)

5 (pouce, …, annulaire)

7 (lundi, …, dimanche)

12 (janvier, …, décembre)

10 (0 à 9)

26 (A à Z)

27 = 128

28 = 256

216 = 65536

224 = 16777216

Codage adapté à l'information: probabilité d'occurrence.

Codage intégrant des codes correcteurs.


Compression

Quantité d'information:

On vérifie bien I(x) = 0 pour p(x) = 1 et I(x) + pour p(x) = 0.


Selon Shannon, la quantité d'information I(x) s'écrit :

2

1( ) log

( )I x

p x

2( ) log ( )I x p xsoit

La quantité d'information et son traitement sont directement liés à la base numérique de quantification (base 2) et à la nature de la source.


Compression

Généralisation:

avec


Soit une source d'information discrète finie stationnaire sans mémoire, soit l'émission d'une variable aléatoire X = {x1, x2, …, xN} avec une

probabilité d'occurrence p = {p(x1), p(x2), …, p(xN)} = {p1, p2, …, pN} associée

respectivement à chacun des caractères, alors l'entropie [de Shannon] associée à chacun des caractères s'écrit :

2( ) . ( ) log ( )k k k k kH x p I x p p

L'entropie d'une source d'information est la quantité d'information moyenne associée à chaque symbole de la source. L'entropie de Shannon s'écrit en fonction des probabilités d’occurrence pk de chacune des quantités d'information I(xk) constituant le signal :

21

( ) ( ) log ( )N

k kk

H X E I X p p

1

1N

kk

p


Compression

Borne supérieure:


2( ) log ( )H X N

Cette valeur limite de l'entropie Hmax(X), obtenue pour une distribution uniforme, constitue la borne supérieure de l'entropie :

max 2( ) log ( )H X N

max 21

( ) log ( )N

k kk

H X p p

soit

Dans le cas d'un alphabet constitué de N variables indépendantes et équiprobables, alors pn = 1/N pour tout 1 n

et l'entropie est maximale :


Compression

Source binaire:


max ( ) 1H X

( ) 0H X

2

2

( ) log ( )

(1 ) log (1 )

H X p p

p p

et

Dans ce cas, l'alphabet se réduit à X = {0 ; 1}, et l'entropie est donnée en fonction de p0 = p

et p1 = 1p, par :

si p = {0;1}

La valeur de l'entropie H (X), n'excède pas la borne supérieure de l'entropie Hmax(X) obtenue dans le cas equiprobable, i.e. p = 0,5 :


3.1. Compression non destructive


Compression

Compression numérique sans perte

Informatiquement, un signal numérique est une suite de bits représentant la succession des valeurs prises à certains instants. Chaque échantillon correspond à code ou codage.

Par exemple, un signal de N échantillons codés chacun sur 2 octets nécessite N28 bits.

Le problème posé est le suivant : Pour un signal numérique donné, est-il possible d’en réduire le codage, sans perdre d’information ?

"Sans perdre d’information" signifie que le signal initial peut être reconstruit exactement à partir de cette représentation, soit une compression sans perte.

Prenons l’exemple du code Morse. Chaque caractère est codé par une succession de points et traits. Mais ce codage est à longueur variable, adaptée à la fréquence d’apparition des lettres : la lettre E (fréquente) est codée par : "·", alors que la lettre Z (rare) est codée par : "− − ··".


Compression


Chaque échantillon correspond à code ou codage.

Ainsi, la lettre E (fréquente) nécessite 1 symbole tandis que la lettre Z (rare) nécessite 4 symboles. Par exemple, pour notre alphabet latin de 26 lettres, une première approche nous indique que 5 symboles binaires sont nécessaires: 2^5 = 32 (> 26). Par des méthodes de compression (RLE, Huffman, LZW…) on peut réduire le nombre moyen de symboles nécessaires.

Cas particulier et contre-exemple: "La disparition" de Georges Perec.

Le but est de transmettre en moyenne un moins grand nombre de symboles élémentaires (trait ou point) qu’avec un codage où toutes les lettres seraient représentées par le même nombre de symboles.

Dans ce chapitre nous formalisons ces notions, dans le cadre de la théorie statistique de l’information de Claude Shannon (1916-2001) développée essentiellement dans les années 1940-1950.


Compression

Compression RLE : Ce type de compression, surtout efficace et utilisé pour les images avec peu de couleurs consiste à relever les répétitions de symboles et indiquer leur nombre. Exemple:

Soit la chaîne de caractères suivante:"AAAAAAAAAAAAAAABBBBBAAAAAAAACCCCCCCCCCCCCCCCDD".

On a: A15 B5 A8 C16 D2La compression RLE donne donc:

"A#15 $ B#5 $ A#8 $ C#16 $ D#2"Avec "#" le nombre d'occurrences successives, et "$" le séparateur de relevés.On est passé de 46 symboles à 21 symboles, soit = 21/46 = 46%. Taux de compression :

On définit le taux de compression par le ratio entre le nombre de symboles après compression Nc et celui avant compression Ni :

c

i

N

N

Compression RLE : Run Length Encoding


Compression


Codes préfixes: Codages (i.e. les concaténations de mots binaires) pouvant être décodés sans ambiguïté. On appelle code préfixe tout code tel que chaque mot n’est le début d’aucun autre. Exemple:

Soit un alphabet à 4 symboles : X = {A; B; C; D}, classés par ordre décroissant de fréquence d'apparition ou probabilité d'occurrence.

A0

B10

C110

D111

A

B

C D

0 1

1

1

0

0

Inégalité de Kraft:Si {w1, w2, …, wN} est un code préfixe binaire, alors il vérifie :

1

2 1k

Nl

k

xk

wk


Compression

Compression Huffman

Le code préfixe associé à l’arbre créé (appelé "code de Huffman") minimise la longueur moyenne parmi tous les codes préfixes :

1

N

moy k kk

L l p

Remarques : Le code de Huffman vérifie donc : Il n’y a pas unicité du code minimal : il peut y avoir des choix de fusion dansl’algorithme de Huffman, et le choix d’affectation des branches "gauche" et "droite" n’est pas spécifié.

( ) ( ) 1moyH X L H x

Code Huffman: On considère l’arbre binaire pondéré construitrécursivement selon l’algorithme suivant : Initialisation : les symboles, pondérés par leur probabilité, sont les feuilles. Itération : tant que le graphe courant n’est pas connexe, fusionner les deux arbres dont les racines sont de poids les plus petits en créant une nouvelle racine de poids égal à la somme de ces poids, liée à ces deux sous-arbres.


Compression

Compression Huffman

Code Huffman: On considère l’arbre binaire pondéré construitrécursivement selon l’algorithme suivant : Initialisation : les symboles, pondérés par leur probabilité, sont les feuilles. Itération : tant que le graphe courant n’est pas connexe, fusionner les deux arbres dont les racines sont de poids les plus petits en créant une nouvelle racine de poids égal à la somme de ces poids, liée à ces deux sous-arbres.

E

0,25

01

xk

pk

wk

Exemple:Soit un alphabet à 8 symboles : X = {A; B; C; D; E; F; G; H}, classés

par ordre décroissant de fréquence d'apparition ou probabilité d'occurrence.

A

0,20

11

B

0,15

001

D

0,15

101

C

0,10

100

G

0,05

0001

H

0,05

00001

F

0,05

00000

Décoder: "1000010001010100000100" et "0000010001010100000100".


xk

pk

Compression

Compression Huffman

Code Huffman: Méthode d'élaboration : Arbre : Fusionner les deux arbres dont les racines sont de poids les plus petits en créant une nouvelle racine de poids égal à la somme de ces poids, liée à ces deux sous-arbres.

E

0,25

A

0,20

B

0,15

D

0,15

C

0,10

G

0,05

H

0,05

F

0,05

0,10

0,15

0,25

0,300,45

0,55

1,00


Compression

Compression Huffman

Code Huffman: Méthode de lecture de l ’arbre : Le décodage d’un mot consiste à parcourir l’arbre en choisissant les branches de gauche ou de droite selon la valeur 0 ou 1 lue ; lorsqu’on arrive à une feuille on écrit la lettre correspondante et on continue la lecture après être revenu à la racine.

0,10

0,15

0,25

0,300,45

0,55

1,00

E

0,25

00

xk

pk

wk

A

0,20

01

B

0,15

100

D

0,15

101

C

0,10

110

G

0,05

1110

H

0,05

11110

F

0,05

11111


Compression

Compression Huffman

Code Huffman: Méthode d'élaboration : Tableau : Fusionner les deux probabilités de poids les plus petits en créant une nouvelle racine de poids égal à la somme de ces poids, liée à ces deux sous-arbres.

E

0,25

01

00

xk

pk

wk

wk

A

0,20

11

01

B

0,15

001

100

D

0,15

101

101

C

0,10

100

110

G

0,05

0001

1110

H

0,05

00001

11110

F

0,05

00000

11111

Solution 1

Solution 2

Décoder: "1000010001010100000100" et "0000010001010100000100".

On vérifie facilement qu’il s’agit bien d’un code préfixe : aucun code n’est le préfixe d’un autre.

On obtient un code Huffman différent de celui proposé initialement : il n ’y a pas unicité de la solution...


Compression

Compression Huffman


xk pk It.1 It.2 It.3 It.4 It.5 It.6

E 0,25 0,25 0,25 0,25 0,30 0,45 0,55

A 0,20 0,20 0,20 0,25 0,25 0,30 0,45

B 0,15 0,15 0,15 0,20 0,25 0,25

D 0,15 0,15 0,15 0,15 0,20

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05


Compression

Compression Huffman



E 0,25 0,25 0,25 0,25 0,30 0,45 0,55

A 0,20 0,20 0,20 0,25 0,25 0,30 0,45

B 0,15 0,15 0,15 0,20 0,25 0,25

D 0,15 0,15 0,15 0,15 0,20

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

0

100

01

00

01


Compression

Compression Huffman



E 0,25 0,25 0,25 0,25 0,30 0,45 0,55

A 0,20 0,20 0,20 0,25 0,25 0,30 0,45

B 0,15 0,15 0,15 0,20 0,25 0,25

D 0,15 0,15 0,15 0,15 0,20

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

0

1

1

00

01

00

01

10

11


Compression

Compression Huffman


xk pk It.1 It.2 It.3 It.4

E 0,25 0,25 0,25 0,25 0,30

A 0,20 0,20 0,20 0,25 0,25

B 0,15 0,15 0,15 0,20 0,25

D 0,15 0,15 0,15 0,15 0,20

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

00

01

10

11000

001


Compression

Compression Huffman


xk pk It.1 It.2 It.3

E 0,25 0,25 0,25 0,25

A 0,20 0,20 0,20 0,25

B 0,15 0,15 0,15 0,20

D 0,15 0,15 0,15 0,15

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

01

10

11

000

001


Compression

Compression Huffman



E 0,25 0,25 0,25 0,25

A 0,20 0,20 0,20 0,25

B 0,15 0,15 0,15 0,20

D 0,15 0,15 0,15 0,15

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

01

10

11

000

001100

101


Compression

Compression Huffman



E 0,25 0,25 0,25 0,25

A 0,20 0,20 0,20 0,25

B 0,15 0,15 0,15 0,20

D 0,15 0,15 0,15 0,15

C 0,10 0,10 0,15 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

01

10

11

000

001

01

11

000

001

100

101


Compression

Compression Huffman


xk pk It.1 It.2

E 0,25 0,25 0,25

A 0,20 0,20 0,20

B 0,15 0,15 0,15

D 0,15 0,15 0,15

C 0,10 0,10 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

01

11

000

001

100

1011000

1001


Compression

Compression Huffman


xk pk It.1 It.2

E 0,25 0,25 0,25

A 0,20 0,20 0,20

B 0,15 0,15 0,15

D 0,15 0,15 0,15

C 0,10 0,10 0,15

G 0,05 0,10 0,10

H 0,05 0,05

F 0,05

01

11

000

001

100

101

01

11

000

001

101

1000

1001


Compression

Compression Huffman


xk pk It.1

E 0,25 0,25

A 0,20 0,20

B 0,15 0,15

D 0,15 0,15

C 0,10 0,10

G 0,05 0,10

H 0,05 0,05

F 0,05

01

11

000

001

101

1000

1001

01

11

000

001

101

1001

10000

10001


Compression

Compression Huffman


E

0,25

01

01

xk

pk

wk

wk

A

0,20

11

11

B

0,15

001

000

D

0,15

101

001

C

0,10

100

101

G

0,05

0001

1001

H

0,05

00001

10000

F

0,05

00000

10001

Solution 1

Solution 3

Décoder: "1000010001010100000100" et "0000010001010100000100".

On vérifie facilement qu’il s’agit bien d’un code préfixe : aucun code n’est le préfixe d’un autre.

On obtient un code Huffman différent de celui proposé initialement : il n ’y a pas unicité de la solution...


Compression

Compression

Autres codes de compression: Codage arithmétique (1976) : Comme le codage de Huffman, le codage arithmétique appartient à la famille des codages entropiques, dans le sens où il se base sur les fréquences d’apparition des lettres pour coder avec peu de bits une lettre très fréquente. Dans le codage arithmétique, un message est codé par un décimal entre 0 et 1.

Codage LZW (Lempel, Ziv, Welch,1984) : Dans les codages entropiques du type de celui de Huffman, un dictionnaire est créé pour associer à chaque lettre de l’alphabet un mot binaire (de longueur variable), à l’aide des statistiques de fréquence des lettres dans le message à compresser. Dans le codage de LZW, le dictionnaire associe à des chaîne de lettres de longueur variable figurant dans le message à compresser des mots binaires de longueur fixée. Ceci permet d’exploiter les corrélations entre les sorties de la source X.


Compression

Compression

Autres codes de compression: Comparaison:

The LZ methods are denoted by "o", the PPM methods by "*", and the BWT methods by "•".

http://sun.aei.polsl.pl/~sdeor/pub/deo03.pdf, p.107-115


Compression

Compression

Formats informatiques: Données : ZIP, RAR, 7z...

Images : BMP RLE (8 bits), GIF (8 bits), PNG (24 bits)...

Exemple : Image 800x600 avec 4 quartiers : rouge, vert, bleu, gris.

Compression ZIP: 5 344 octetsCompression RAR: 4 755 octetsCompression 7zip: 2 522 octetsOriginal BMP (24 bits): 1 440 054 octetsCompression BMP (RLE): 7 078 octetsCompression GIF (8 bits): 4 656 octetsCompression PNG (24 bits): 2 805 octets

Exercice : Retrouver la taille du fichier BMP (24 bits) par le calcul.


Compression

Compression

Formats informatiques: Données : ZIP, RAR, 7z...

Images : BMP RLE (8 bits), GIF (8 bits), PNG (24 bits)...

Exemple 2 : Image 800x600 avec de nombreuses détails.

Compression ZIP: 882 523 octetsCompression RAR: 779 488 octetsCompression 7zip: 715 501 octetsOriginal BMP (24 bits): 1 440 054 octetsCompression BMP (RLE): 365 908 octetsCompression GIF (8 bits): 222 321 octetsCompression PNG (24 bits): 697 615 octets


3.2. Compression destructive



Compression numérique avec perte

Dans de nombreux domaines (image, son), la restitution des données sans pertes n’est pas un impératif absolu. Pour étayer ce constat, on peut partir de considérations mathématiques, mais aussi physiques et physiologiques.

Considération mathématique: Décroissance des coefficients de FourierCe constat donne l’idée de "compresser" les signaux en ne transmettant que les coefficients de Fourier suffisamment grands (puisqu’un certain nombre, correspondant à |n| grand, seront assez petits), par exemple en tronquant la série de Fourier. Néanmoins, ceci est la cause des phénomènes de pré-écho dans les fichiers MP3, ou du phénomène de ringing (surlignage des bords contrastés) dans les fichiers JPEG.

Considération physique: Au-delà d’un certain échantillonnage et d’une certaine quantification, le signal parait continu à nos sens.

Considération physiologique: Nos sens sont "aveuglés" par des composantes dominantes, on parle de masquage.


TCD Zig-ZagBloc 8x8

1,2,….

DC AC

AC

Run Length Coding



Le format JPG : La compression JPEG (Joint Photographies Experts Group)

Schéma de principe :



Image originale Image reconstruite Image erreurCoefficients TCD

64 coefficients


32 coefficients





Image originale Image reconstruite Image erreurCoefficients TCD

8 coefficients

1 coefficient






Référence11 240 octets

FQ = 42 582 octets = 23%

FQ = 101 582 octets = 14%

FQ = 100528 octets = 5%


Compression


Le format JPG : CompressionDonnées :

FQ=1: 409 302 octets



FQ=10: 189 363 octets

FQ=20: 135 222 octets




Compression


Le format JPG : CompressionPrincipe :

Avec le schéma de codage très simplifié suivant, on remarque que le codage

nous délivre deux tables (quatre pour une image couleur). Ces tables étant

enregistrées dans le fichier final peuvent être choisies par le compresseur.

Schéma de codage simplifié.


Courbe de sensibilité de l ’oreille humaineA (dB)

Fréquence

120

0

60

log(f)

Seuil de perception

Zone audible

son S1son S2

Au dessous du seuil, les sons ne

sont plus audibles



Le format MP1 audio : fondé sur le standard MUSICAM (Masking Pattern Adapted Universal Subband Integrated Coding)

Débit WAV (CD) :Débit 1411 kb/s (2x44100/sx16bits).

Débit MPEG 1 : Débit 192 kb/s (2x96kbits/s)


A (dB)

Fréquence

120

0

60

log(f)

Seuil de perception

Zone audible

S1 S2

A (dB)

Fréquence

120

0

60

log(f)

Zone audible

Le son S2 ne doit pas être pris en compte : il est masqué par un son S1 plus important.

Le seuil de perception varieen fonction du contenu spectral.



Le format MP1 audio : fondé sur le standard MUSICAM

S1 S3S2

Seuil de perception

S4


Sous-bande 750 Hz

f

fe/2 =24 kHz

A (dB)

Fréquences

120

0

60

log(f)



Le format MP1 audio : fondé sur le standard MUSICAM Les spectre audio est découpé en 32 sous-bandes de fréquence :

La courbe de masquage est déterminée en temps réel : modèle psycho-acoustique.

La quantification varie en fonction de la sensibilité de l’oreille : modèle psycho-acoustique.

Modèlepsycho-acoustique


Images animées

Numérisation

Quantification

DCT

Seuillage

RLC

Huffman (VLC)

MPEGCompression

temporelle

Compression spatiale Non réversible

Production d ’une séquence MPEG



Image spatiale Image fréquentielle (TCD)

Image fréquentielle Spectre 2D

Quantification Privilégie les harmoniques principaux

Codage du Run Length Code (RLC) + Codage d ’Huffman

Méthode Zig-Zag

Production d ’une séquence MPEG


Méthode irréversible : Taux de compression élevé => Perte d’information élevée

Compression temporelle Trame de référence.

Documents

CM1 - Signal et Information