Soutenance mémoire
Le stockage de données informatiques nécessite plus ou moins d’espace mémoire, mesuré en octets, pour ranger l’information. Lorsqu’il s’agit d’image, de son ou de vidéo, l’espace mémoire requis est beaucoup plus important. La compression de données informatiques est une technique de réduction de ces données sur un support de stockage, elle s’accompagne nécessairement d’une technique de décompression qui permet de restituer dans leur format original les données compressées. La compression de données a donc pour but de minimiser le nombre d’octets nécessaires pour représenter une donnée, soit minimiser l’espace de stockage, mais aussi de minimiser l’utilisation de la bande passante pour le transfert sur les réseaux, notamment sur Internet (optimisation de la transmission).
LA COMPRESSION SANS PERTE
Présentation
On distingue deux grandes familles très différentes de compression. Il y a les compressions non destructrices ou sans perte et les autres dites destructrices ou avec perte. Une compression est dite sans perte, parce que lors de la compression il n’y a pas d’altération de l’information. La compression sans perte est utilisée quand il est nécessaire de garder l’information intacte : il ne doit pas y avoir de différences entre le fichier original et ce même fichier après compression et décompression. Ce type de compression est vital non seulement pour le texte, mais également pour tout type de fichier devant conserver une qualité optimale (images TIFF ou programmes, imageries médicales, application…).
RLE (Run length encoding)
RLE travaille sur la réduction de la taille physique des chaînes de caractères répétitives.
Méthode de compression
Cet algorithme prend simplement la suite d’octets, pixels ou caractères qu’on lui fournit, y repère les répétitions d’élément, et transforme chaque ensemble en une paire « nombre de fois où l’élément apparaît, élément ». Deux octets représentent alors chaque élément ou chaîne, le premier octet pour le nombre de répétition, le second octet pour la valeur à répéter.
L’algorithme
Les notations utilisées sont les suivantes :
♣ n : nombre de répétitions de la chaîne .
♣ w : La première chaîne à lire .
♣ v : La chaîne suivante .
LZW ( Lempel Ziv Welch)
Présentation
En 1977, Abraham Lempel et Jakob Ziv ont créé le premier élément de la famille des compresseurs LZ. Ce compresseur, nommé LZ77, est utilisé dans les programmes d’archivages de donnés. Il est spécialisé dans les données textuelles alors que LZ78 est plus efficace pour des donnés binaires comme les images. En 1984, alors qu’il travaillait chez Unisys, Terry Welch modifia LZ78 pour l’implanter dans des contrôleurs de disques. Le résultat fut l’algorithme LZW.
Méthode de compression
La méthode consiste à utiliser un « dictionnaire » de « mots » construit au fil de la compression. Le flot d’information à compresser est découpé en chaînes d’octets. Chaque chaîne est comparée au dictionnaire. Si elle n’est pas présente, elle est stockée, sinon on n’ajout rien dans le dictionnaire.
Tous les codeurs et décodeurs LZW initialisent leurs dictionnaires avec les 256 valeurs de la table ASCII.
La compression par fractales
Présentation
La compression fractale est l’apanage de la société Iterated Systems. L’idée étant qu’une image est stockée sous la forme d’un ensemble de formule plutôt qu’un ensemble d’un point. La compression fractale est indépendante de la résolution contrairement à JPEG. Cette caractéristique tient à la nature mathématique du codage employé. En effet l’image n’est pas sauvegardée sous forme d’un ensemble de points ou de motifs mais sous la forme de formules. C’est pour cette raison que l’étape de la compression n’exige pas de préciser à l’avance les données à supprimer, mais tout simplement la taille finale de l’image.
Etapes de compression
Découpage en bloc
La compression par fractale commence à découper l’image en bloc. Pour minimiser le nombre de blocs à coder et le nombre de transformations locales, différents modèles de partitionnement (mode de découpage) d’images pour la compression par fractales ont été étudiés tels que le partitionnement rectangulaire, carré, quadtreee, polygones… Le but est de subdiviser l’image en des blocks qui contient chacun des pixels similaires, le bloc pouvant être de rectangle, carré, selon le type de partitionnement. Les valeurs de ces pixels sont dites « similaires » si leurs valeurs ne dépassent pas un seuil qui prend la valeur de 0 à 1.
Transformation par fractales
Chaque bloc est codé sous la forme d’une transformation mathématique. La transformation W de l’image est composée de n sous-transformations élémentaires wn, chacune opérant sur un bloc de l’image.
|
Table des matières
INTRODUCTION
CHAPITRE I COMPRESSION SANS PERTE
1.1 Présentation
1.2 RLE (Run length encoding)
1.2.1 Présentation
1.2.2 L’algorithme
1.2.3 Exemple d’application
1.2.4 Performances
1.3 LZW(Lempel Ziv Welch)
1.3.1 Présentation
1.3.2 Méthode de compression
1.3.3 L’algorithme LZW
1.3.4 Exemple d’application
1.4 L’algorithme de HUFFMAN
1.4.1 Présentation
1.4.2 Codage de Huffman
1.4.2.1 Tableau de probabilité
1.4.2.2 Arbre de Huffman
1.4.2.3 Codage
1.5 Comparaison des trois algorithmes sans pertes
CHAPITRE 2 LA COMPRESSION D’IMAGE AVEC PERTE
2.1 Présentation
2.2 Le JPEG (Joint Photographic Expert Group)
2.2.1 Présentation
2.2.2 Algorithme
2.2.2.1 Transformation de l’image
2.2.2.2 Sous-echantillonage de la chrominance
2.2.2.3 Transformée en Cosinus Discrète
2.2.2.4 Quantification
2.2.2.5 Compression
2.2.3 Remarque
2.2.4 Exemple d’illustration
2.3 La compression par ondelettes
2.3.1 Présentation
2.3.2 Techniques de compression par ondelettes
2.3.3 Etapes de compression
2.3.4 Avantages
2.4 La compression par fractales
2.4.1 Présentation
2.4.2 Etapes de compression
2.4.2.1 Découpage en bloc
2.4.2.2 Transformation par fractales
2.4.2.3 Exemple d’illustration
2.4.2.4 Avantages et défauts
2.5 Comparaison des trois algorithmes
2.6 Format graphique et espace de couleur
2.6.1 Fichier graphique
2.6.2 Format graphique
2.6.2.1 Le format TIFF
2.6.2.2 Le format PNG
2.6.2.3 Le format GIF
2.6.2.4 Le format BMP
2.6.3.5 Le format JFIF
2.6.3 Espace de couleur
2.6.3.1 Le RVB
2.6.3.2 Le CMY
2.6.3.3 Le HSV
2.6.3.4 Le YUV
CHAPITRE 3 LA COMPRESSION DU SON AUDIBLE AVEC PERTE
3.1 Présentation
3.1.1 Le son
3.2 Le MP3
3.2.1 Présentation
3.2.2 Les étapes de compression
3.2.2.1 Découpage du son
3.2.2.2 Masquage des fréquences
3.2.2.3 Codage
3.2.2.4 Performances du MP3
3.3 L’algorithme de PASC (Précision Adaptive Sub-band Coding)
3.3.1 Présentation
CHAPITRE 4 LA COMPRESSION VIDEO AVEC PERTE
4.1 La vidéo
4.2 Le MPEG
4.2.1 Compression de la partie vidéo
4.2.1.1 Sous-echantillonage et interpolation
4.2.1.2 Codage spatial
4.2.1.3 Codage temporel
4.2.1.4 Codage bidirectionnel
4.2.2 Compression de la partie audio
4.2.3 Les standards de MPEG
CONCLUSION
