Compression de données
Formation
Compression de données
Principe
Compression sans perte
Compression avec perte
CIN ST MANDRIER
Compression de données
Introduction
La tendance à l'intégration de services traditionnellement
analogiques tels que l'audio ou la vidéo dans les systèmes
informatiques a donné lieu à l'apparition de nouvelles classes
d'applications dénommées sous le terme générique de
multimédia.
Si les données numériques se satisfont de débits de l'ordre du
méga-bit par seconde, il en va tout autrement en ce qui concerne
ces nouvelles applications, que ce soit déjà au niveau du
stockage mais surtout au niveau du transport.
10-96
CIN ST MANDRIER
Compression de données
Généralités
On distingue deux types d'algorithmes visant à réduire la taille
des données manipulées :
Les algorithmes de compactage ou méthode réversible
Les algorithmes de compression ou méthode irréversible
On mesure l'efficacité de la compression par :
nombre de bits fichier original
Taux de compression
nombre de bits fichier compressé
CIN ST MANDRIER
Compression de données
Principe
Compression sans perte
Compression avec perte
CIN ST MANDRIER
Compression de données
Compactage
Les algorithmes de compactage ne visent qu'un seul et même
objectif : l'élimination de la redondance dans les fichiers. En
effet les fichiers informatiques traditionnels étant d'origine
humaine ou décrivant des formats numériques répétitifs, et les
langues humaines étant notoirement redondantes (l'anglais est
redondant à 75 %), les-dits fichiers contiennent une part
importante d'information non pertinente.
Plusieurs types de compactage :
Algorithme de compactage canonique
Algorithme de codage statistique
Algorithme de type dictionnaire
CIN ST MANDRIER
Compression de données
Les algorithmes de compactage canoniques
Le Run Length Coding (RLC)
Pour appliquer le RLC, il suffit de se choisir un caractère de contrôle #, et de coder
les plages de k octets par : # octet k.
Le Codage Topologique
Pour ce codage on choisi un octet dont on va privilégier le compactage : on va lire
des blocs de huit octets puis remplacer les occurrences de l’octet choisi par un
octet de description en tête de séquence qui indique les emplacements de cet
octet. Ne reste dans la séquence que les octets différents.
Le Codage Relatif
Dans le cadre du codage relatif on résume les bits qui ne varient pas en début de
séquence, puis on ne précise que les bits qui évoluent.
CIN ST MANDRIER
Compression de données
Les algorithmes de compactage statistiques
Les algorithmes de codage statistique forment une classe
d'algorithmes liés à RLC. On considère le fichier f comme un
ensemble de motifs quelconques Mi dont on va étudier les
fréquences d'apparition fi.
Après avoir calculé les fréquences d'apparition fi, on va établir un
codage Ci des motifs de telle sorte que les tailles des code Ci soit
inversement proportionnelles aux fréquences d'apparition des motifs
Mi.
Le fichier compacté sera composé de la liste des correspondances
(Mi,Ci) et du fichier f où on aura remplacé Mi par Ci.
Exemple : Huffman
CIN ST MANDRIER
Compression de données
Les algorithmes de type dictionnaire
Les algorithmes de type dictionnaire établissent un dictionnaire des termes
employés dans un fichier, termes qui peuvent êtres de taille quelconques, et leur
associent un code de taille moins importante.
Le fichier compacté est composé du dictionnaire et du fichier où les termes sont
remplacés par les codes.
Codage C = AAAAAA Compacté
Fichier Dictionnaire
C ________ C
AAAAAA ________
_____C____
_____AAAAAA____
_C________
_AAAAAA________
C_________
AAAAAA_________
_________C
_________AAAAAA
Exemple : LZW
CIN ST MANDRIER
Compression de données
L’état de l’art
Les programmes de compactage les plus performants combinent la
puissance des algorithmes de type LZW et l'efficacité des
algorithmes statistiques pour compresser les motifs redondants. La
combinaison est simple :
Aux algorithmes de type dictionnaire de détecter les redondances
dans les fichiers et de constituer les dictionnaires de motifs
redondants.
Aux algorithmes statistique de trouver les codages les plus concis
pour les termes contenus dans les dictionnaires.
•Compresse les codes LZW émis •Repère les redondances
•Compresse les positions •Aucune en-tête
STATISTIQUE + DICTIONNAIRE = OPTIMUM
ZOO PKZIP
LHA ARJ
CIN ST MANDRIER
Compression de données
MNP5
Le protocole MNP5 est un exemple de l'utilisation du compactage
pour le transfert des données informatiques sur réseaux : il permet
de compresser des données et donc d'augmenter le débit sur les
lignes.
L'algorithme utilisé est un mélange d'algorithme de type dictionnaire et
de type statistique : on recherche d'abord les redondances dans le
fichier et les motifs redondants se voient affecter un code de taille
optimale.
Dans le meilleur des cas la compression peut atteindre un facteur 4,
ce qui revient à dire qu'une ligne V32 bis à 14400 bps peut fonctionner
au mieux comme une ligne à 57600 bps.
CIN ST MANDRIER
Compression de données
MNP5
CIN ST MANDRIER
Compression de données
MNP5
CIN ST MANDRIER
Compression de données
MNP5
CIN ST MANDRIER
Compression de données
Principe
Compression sans perte
Compression avec perte
CIN ST MANDRIER
Compression de données
Compression avec perte
L’image
L’image est un signal fortement corrélé. Donc les algorithmes (sans
perte) classiques tels que Huffman, LZW et même le rudimentaire
RLC donnent de très bons résultats.
Format TIFF : LZW (20 à 80% en 256 couleurs)
Format TGA : RLC (pas plus de 70%)
CIN ST MANDRIER
Compression de données
Compression avec perte
La norme JPEG
La norme JPEG (Joint Picture Expert Group) utilise un protocole de
codage en 3 étapes :
Calcul de la transformée de cosinus discrète (DCT) par bloc de 8x8
pixels
Quantification des coefficients de la DCT
Compression statistique (Huffman)
CIN ST MANDRIER
Compression de données
Principe JPEG
IMAGE
ORIGINALE
DCT Codage
Quantification
8x8 statistique
IMAGE
COMPRESSEE
CIN ST MANDRIER
Compression de données
Principe JPEG
Référence (11 240 octets)
FQ = 4 (2 582 octets)
Compression 77%
FQ = 10 (1 582 octets)
Compression 86%
FQ = 100 (528 octets)
Compression 95%
CIN ST MANDRIER
Compression de données
JPEG 2000
Le format JPEG, bien que normalisé en 94, a été développé il y a
plus de 10 ans.
Le format JPEG 2000 doit répondre aux nouveaux besoins (photo
numérique, web, e-commerce,…).
Il est basé sur la technologie des ondelettes et permet une
amélioration du taux de compression (20%) et une qualité
supérieure de restitution par rapport au format actuel.
Il sera possible , à la réception, de définir le choix de la résolution.
CIN ST MANDRIER
Compression de données
Compression avec perte
La norme MPEG
La norme MPEG (Moving Picture Expert Group) définit une
compression pour une succession d’image dans le temps,
accompagnée d’une bande sonore.
Constituants de MPEG
Vidéo : définition de la méthode de compression des images animées
dans le temps
Audio : compression des séquences audio (256 kbps).
System : synchronisation et multiplexage des séquences audio et
vidéo.
CIN ST MANDRIER
Compression de données
Compression avec perte
La vidéo (image et son) est moins sensible au délai de transit que la
voix (non interactivité entre les extrémités) mais est plus gourmande
en terme de débit.
Une image de télévision (standard européen 625 lignes, 25 Hz) est
caractérisée par :
Le nombre de lignes utiles fixées à 576
Le nombre de point par ligne défini à 720
Chaque point est représenté par deux grandeurs, la luminance et la
chrominance reliées entre elles par la relation :
Y = 0,3 R + 0,59 V + 0,11 B
Seuls sont transmis la luminance (Y) et les signaux composites
suivants : Db =1,5 ( Y – B ) et Dr = -1,9 ( Y – R )
CIN ST MANDRIER
Compression de données
Compression avec perte
Caractéristiques des images vidéo
NTSC PAL/SECAM CIF QCIF
Nombre de lignes 525 625
Résolution
720 x 485 720 x 576 352 x 288 176 x 144
luminance
Résolution
360 x 485 360 x 576 176 x 144 88 x 72
chrominance
Images /seconde 60 50 30 30
Entrelacement Oui Oui Non Non
CIN ST MANDRIER
Compression de données
Compression avec perte
Les normes MPEG
Normes Années Objet
Définit l'enregistrement et la consultation d'images ani-
mées (format réduit 352x288 pixels en PAL et 352x240
MPEG1 1993
en NTSC, qualité équivalente au format VHS) et du son
associé sur support numérique. Débit de 1,5 à 2 Mbps.
Normalise la compression pour la distribution d'images et
MPEG2 1995
la diffusion de programmes de télévision. Débit 10 Mbps.
MPEG4 1998 Pour un service interactif.
Précisera les mécanismes de navigation entre différentes
MPEG5
scènes.
Devrait permettre la recherche d'images par son contenu
MPEG7
(langage de requêtes), sans pré indexation préalable.
CIN ST MANDRIER
Compression de données
Compression avec perte
Le principe de la compression vidéo repose sur la forte redondance
d'informations dans une image et d'une image sur l'autre. Il en
résulte deux types de compression :
Une compression spatiale
Une compression temporelle
La compression spatiale résulte d'une décomposition de l'image en
bloc (8 x 8) converti en matrice de coefficients compressé à
nouveau de manière statistique.
La compression temporelle considère une image comme une
translation temporelle de la précédente. Ne sont transmis que les
coordonnées vectorielles des blocs dont la position à changé.
CIN ST MANDRIER
Compression de données
Compression avec perte
Les différentes étapes de MPEG :
Mise en forme des signaux d’entrée
Remise en ordre des images
Estimation du mouvement
Compensation du mouvement
Calcul de DCT
Quantification
Codage à longueur variable
CIN ST MANDRIER
Compression de données
Compression avec perte
Trois types d’image :
Les images codées Intra (I) sans référence, servent de référence aux
autres images (prédites).
Les images codées par prédiction (P) sont codées en référence à une
image antérieure Intra. Elles servent de référence pour les images
prédites par mouvements.
Les images codées par prédiction avant ou arrière (B) bidirectionnelle
sont codées à partir d’une image I ou P antérieure ou future.
B B I B B P B B P B B P
-2 -1 0 1 2 3 4 5 6 7 8 9
CIN ST MANDRIER
Compression de données
Compression avec perte
Construction de l'objet fractal de Koch appelé
aussi le flocon de neige :
CIN ST MANDRIER
Compression de données
Compression avec perte
CIN ST MANDRIER
Compression de données
Compression avec perte
CIN ST MANDRIER
Compression de données
Compression avec perte
CIN ST MANDRIER
Compression de données
Compression avec perte
CIN ST MANDRIER