Cours: COMMUNICATION MULTIMEDIA Master MIV, 2023/2024 PDF

Cours: COMMUNICATION MULTIMEDIA Master MIV, 2023/2024 Prof. Slimane Larabi Prof. Slimane LARABI, USTHB 1  Chapitre 1. Compression de données sans perte - Compression du texte - Application: Compression d’images en format GIF et PNG...

Cours: COMMUNICATION MULTIMEDIA Master MIV, 2023/2024 Prof. Slimane Larabi Prof. Slimane LARABI, USTHB 1  Chapitre 1. Compression de données sans perte - Compression du texte - Application: Compression d’images en format GIF et PNG Prof. Slimane LARABI, USTHB 2  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.1 Critères des algorithmes de compression Les techniques de compression peuvent être comparées selon les critères suivants : Efficacité (taux de compression) : C’est le rapport entre la taille du fichier compressé et sa taille initiale. Pour une meilleure utilisation des algorithmes, il faut comprendre que la plupart d’entre eux sont plus ou moins efficace dans un type d’image que dans un autre. Qualité de compression : Compression avec une perte d'un certain pourcentage de la qualité ou compression sans perte. Vitesse de compression/décompression Accessibilité : Sous licence, ou libres de droits. Prof. Slimane LARABI, USTHB 3  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Ces méthodes sont basées généralement sur la recherche et le codage des données redondantes. Ce type de compression peut s’appliquer à n’importe quel type de données. Algorithme RLE (Run Length Encoding) : C’est la méthode la plus simple et la plus utilisée. Son principe de base consiste à rechercher des données redondantes (pixels dans le cas des images) et en codant la longueur et la valeur. Ainsi à chaque répétition d’un pixel plus d’un nombre n précisé par l’utilisateur, cette suite de pixels est remplacée par un caractère spécial indiquant la compression suivi par le nombre de répétitions du pixel et enfin sa valeur. Prof. Slimane LARABI, USTHB 4  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme RLE (Run Length Encoding) : Exemple de chaine de caractères: aaaaaaaabbbbvvvvvvvvvaaaaaa Le codage associé en adoptant la convention: $: séparateur Caractère: le caractère répété dans la chaine Chiffre: le nombre de répétitions $a8$b4$9v$6a Prof. Slimane LARABI, USTHB 5  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme RLE (Run Length Encoding) : Caractéristiques : Algorithme de compression ou de décompression très simple à implémenter. Taux de compression relativement faible par rapport à d’autres algorithmes. Obtient des meilleurs résultats avec des images contenant des zones importantes de couleur contiguë (images monochromes). La compression des images en couleurs complexes (photos) ne donne pas des bons résultats. Prof. Slimane LARABI, USTHB 6  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Abraham Lempel et Jakob Ziv, nés en Palestine occpée, sont les créateurs du compresseur LZ77, inventé en 1977 (d'où son nom). Ce compresseur était alors utilisé pour l'archivage (les formats ZIP). Prof. Slimane LARABI, USTHB 7  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Cet algorithme a été amélioré par Terry Welch de la société Unisys en 1984. Terry Welch la présenté dans un article called A Technique for High-Performance Data Compression. It Il est basé sur un dictionnaire (bibliothèque) construit au fur et à mesure de la lecture du fichier à coder. Prof. Slimane LARABI, USTHB 8  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Les chaînes de caractères sont placées une par une dans la bibliothèque. Lorsqu’une chaîne est déjà présente dans la bibliothèque, son code de fréquence d’utilisation est incrémenté. Les chaînes de caractères ayant des codes de fréquences élevés sont remplacées par un " mot " ayant un nombre de caractères le plus petit possible et le code de correspondance est inscrit dans la bibliothèque. On obtient ainsi l'information encodée et sa bibliothèque. Prof. Slimane LARABI, USTHB 9  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Algorithm Begin w=ø Repeat read a character k if wk  Dictionary then w = wk else output (code (w)) Dictionary  wk w=k Until EOF End Prof. Slimane LARABI, USTHB 10  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Algorithm (Décompression) Begin read k; output Dict[k]; w = Dict[k]; while ( read k ) { output Dict[k]; add w Dict[k] to dictionary; w = Dict[k]; } End Prof. Slimane LARABI, USTHB 11  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Caractéristiques : Cet algorithme est breveté par la société Unisys, il a été utilisé dans les formats TIFF et GIF, par contre l’algorithme LZ77 est libre de droit et a été utilisé dans le format PNG. Il s'applique très bien sur les images de faibles profondeurs (nombre réduit de couleurs différentes) puisque les motifs différents doivent être relativement faibles pour être répétés. Il est l'un des plus répandus algorithmes, et est très rapide aussi bien en compression qu'en décompression. Prof. Slimane LARABI, USTHB 12  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Example: Soit à compresser avec LZW la chaine: ^wed^we^wee^wed^ Prof. Slimane LARABI, USTHB 13 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string Prof. Slimane LARABI, USTHB 14 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes Prof. Slimane LARABI, USTHB 15 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ Prof. Slimane LARABI, USTHB 16 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w Prof. Slimane LARABI, USTHB 17 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 Prof. Slimane LARABI, USTHB 18 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d d^ 93 Prof. Slimane LARABI, USTHB 19 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 Prof. Slimane LARABI, USTHB 20 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w ^we 95 Prof. Slimane LARABI, USTHB 21 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 95 e^ 94 Prof. Slimane LARABI, USTHB 22 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes e^ 95 Prof. Slimane LARABI, USTHB 23 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 Prof. Slimane LARABI, USTHB 24 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we ^wee 96 Prof. Slimane LARABI, USTHB 25 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 Prof. Slimane LARABI, USTHB 26 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 e^ w e^w no e^w e^ e^w 97 Prof. Slimane LARABI, USTHB 27 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 e^ w e^w no e^w e^ w e we yes e^w 97 Prof. Slimane LARABI, USTHB 28 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 e^ w e^w no e^w e^ w e we yes e^w 97 we d wed no wed we wed 98 Prof. Slimane LARABI, USTHB 29 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 e^ w e^w no e^w e^ w e we yes e^w 97 we d wed no wed we wed 98 d ^ d^ yes Prof. Slimane LARABI, USTHB 30 Input: ^wed^we^wee^wed^ Sub Code w k wk  Dict? Insert in Dict Output string ø ^ ^ yes ^w 90 ^ w ^w no ^w ^ we 91 w e we no we w e d ed no ed e ed 92 d ^ d^ no d^ d ^ w ^w yes d^ 93 ^w e ^we no ^we ^w e ^ e^ no e^ e ^we 94 ^ w ^w yes ^w e ^we yes e^ 95 ^we e ^wee no ^wee ^we e ^ e^ yes ^wee 96 e^ w e^w no e^w e^ w e we yes e^w 97 we d wed no wed we wed 98 d ^ d^ yes d^ ø Slimane d^ Prof. LARABI, USTHB d^ 31  Chapitre 1. Compression de données sans perte 1.1 Compression du texte 1.1.2 Algorithmes de compression Algorithme LZW (Lempel Ziv Welch) : Example: Soit à compresser avec LZW la chaine: Input: ^wed^we^wee^wed^ Output: ^ w e d ^w e ^we e^ we d^ Prof. Slimane LARABI, USTHB 32 La compression LZW (Lempel Ziv Welch) : Décodage string entry; char ch; int code; int prevcode, currcode; prevcode = read code; decode/output Dict(prevcode); while (there is still data to read) { curcode = read code; output Dict(curcode); ch = first char of entry; add Dict(prevcode)+ch to Dict; prevcode = currcode; } Prof. Slimane LARABI, USTHB 33 La décompression LZW (Lempel Ziv Welch) : Prof. Slimane LARABI, USTHB 34 La décompression LZW (Lempel Ziv Welch) : Prof. Slimane LARABI, USTHB 35 La décompression LZW (Lempel Ziv Welch) : Prof. Slimane LARABI, USTHB 36 La compression LZW (Lempel Ziv Welch) : Décodage Exemple: Dict={0->a, 1->b) Chaine de codes: 0 1 2 4 3 6 Algorithm prevcode = 0; output ‘a’; while (there is still data to read) { curcode=1; output ‘b’; ch=‘b’; Dict(2)=‘ab’; prevcode=‘b’; curcode=2; output ‘ab’; ch=‘a’; Dict(3)=‘ba’; prevcode=‘ab’; curcode=4; output ‘ab..a’; ch=‘a’; Dict(4)=‘aba’; prevcode=‘aba’; curcode=3; output ‘ba’; ch=‘b’; Dict(5)=‘abab’; prevcode=‘ba’; curcode=6; output ‘ba..b’; ch=‘b’; Dict(6)=‘bab’; prevcode=‘bab’; } Prof. Slimane LARABI, USTHB 37 La compression LZW (Lempel Ziv Welch) : Décodage Exemple: Dict={0->a, 1->b, 2 -> c) Chaine de codes: 0 2 3 5 4 7 A 0 B 1 « acacacacacac » c 2 Output: 0 2 3 5 4 7 ac 3 ca 4 Algorithm aca 5 prevcode = 0; acac 6 output ‘a’; while (there is still data to read) cac 7 { curcode=2; output ‘c’; ch=‘c’; Dict(3)=‘ac’; prevcode=‘c’; curcode=3; output ‘ac’; ch=‘a’; Dict(4)=‘ca’; prevcode=‘ac’; curcode=5; output ‘ac..a’; ch=‘a’; Dict(5)=‘aca’; prevcode=‘aca’; curcode=4; output ‘ca’; ch=‘c’; Dict(7)=‘acac’; prevcode=‘ca’; curcode=7; output ‘ca..c’; ch=‘c’; Dict(7)=‘cac’; prevcode=‘cac’; Prof. Slimane LARABI, USTHB 38 } La compression LZW (Lempel Ziv Welch) : Décodage Exemple: Dict={0->a, 1->b, 2->c) Chaine de codes: 0 3 1 2 Algorithm prevcode = 0; output ‘a’; curcode=3; output ‘a..a’; ch=‘a’; Dict(3)=‘aa’; prevcode=‘aa’; curcode=1; output ‘b’; ch=‘b’; Dict(4)=‘aab’; prevcode=‘b’; curcode=2; output ‘c’; ch=‘b’; Dict(5)=‘bc’; prevcode=‘c’; } Prof. Slimane LARABI, USTHB 39  Le codage de Huffman : Cet algorithme est développé en 1952 par David Huffman, il est l’un des algorithmes les plus anciens, son codage est basé sur la fréquence d’apparition d’un caractère : plus le caractère apparaît souvent plus son code sera court et vice-versa. Pour permettre un décodage unique les codes attribués aux différents caractères doivent être préfixés, c'est-à-dire qu’aucun caractère n’est un préfixe d’un autre. C’est pourquoi on appelle aussi ce codage un VLC préfixé (Variable Length Code, code à taille variable). Prof. Slimane LARABI, USTHB 40  Le codage de Huffman : Début Chercher la fréquence d’apparition de chaque caractère. Répéter: Trier les caractères par ordre décroissant de fréquence (poids). Construire l’arbre binaire comme suit : Relier les deux caractères de fréquences les plus basses et Affecter à ce nœud la somme des fréquences des caractères. Jusqu’à ce que tous les nœuds soient reliés L’arbre étant construit, on met un 1 sur la branche à droite du nœud et un 0 sur celle de gauche. Fin Prof. Slimane LARABI, USTHB 41  Le codage de Huffman : Parcourir l’arbre de la racine vers chacune des feuilles pour tirer le code de chaque caractère. Prof. Slimane LARABI, USTHB 42  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 43  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 44  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 45  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 46  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 47  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 48  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 w: 4 d: 2 Prof. Slimane LARABI, USTHB 49  Le codage de Huffman : Exemple: “^wed^we^wee^wed^”: e: 5 ^: 5 d:11 w: 4 w: 10 d: 2 ^: 01 e: 00 01 10 00 11 01 10 00 01 10 00 00 01 10 00 11 01 16x2 bits, soit 4 octets au lieu de 16 octets. Prof. Slimane LARABI, USTHB 50  Le codage de Huffman : – Caractéristiques : Cet algorithme permet d’avoir un taux de compression très élevé (50% en moyenne) et un temps de compression assez rapide. La bibliothèque doit être transmise avec le fichier. Il est très sensible: la perte d’un bit entraîne une altération de toutes les données qui suivent lors de la décompression Prof. Slimane LARABI, USTHB 51  ALGORITHME DEFLATE (GZIP) L’algorithme deflate, qui est une combinaison des algorithmes LZ77 et Huffman. 'Deflate' a été développé en réponse à des problèmes de brevet logiciel couvrant LZW et autres algorithmes de compression, limitant ainsi les utilisations possibles de compress et autres programmes d'archivage populaires. Prof. Slimane LARABI, USTHB 52  ALGORITHME LZ77 LZ77 est proposé pour l’analyse des données et de déterminer comment réduire son espace en remplaçant les informations redondantes avec des méta données. Deux fenêtres : Wf pour se déplacer dans le texte qui reste à compresser, Wb qui contient ainsi la portion précédemment codée. Si une sous chaine de Wf existe dans Wb, alors elle est récrite par une métadonnée : (pos, long, car_suiv), où : Prof. Slimane LARABI, USTHB 53  ALGORITHME DEFLATE (GZIP) L’algorithme DEFLATE produit un ensemble de blocs correspondant à des blocs de données successives. Chacun des blocs est compressé à l’aide de LZ77 et Huffman. Littéraux et les longueurs sont compressés par un arbre de Huffman, les distances sont compressées par un autre arbre de Huffman. Les arbres sont rangés au début de chaque bloc. Un bloc se termine si deflate détermine qu’il utile de démarrer un autre bloc avec un nouvel arbre. Prof. Slimane LARABI, USTHB 54  ALGORITHME LZ77 pos : indique où commence l’équivalence dans Wb, long : sa longueur car_suiv : est le caractère non compressé suivant. Ce caractère est inséré parce que les auteurs ont jugé que s’il n’a pas été codé dans l’expression lue, c’est qu’il y a de grandes chances qu’il ne soit pas compressé ensuite. Cet algorithme utilise un dictionnaire constitué de Wb. La distance pos est limitée à 32KO, et la longueur long à 258 Octets. Prof. Slimane LARABI, USTHB 55  ALGORITHME LZ77 Exemple de compression Soit le texte à coder " how-much-wood-would-a-woodchuck " en entrée. Taille de Wb=16, taille de Wf=5. ho w-much-wood-woul d-a-w oodchuck ‘d-‘ sera codé : (6, 2, a). On déplace ensuite la fenêtre de 3 caractères. Ce qui donne alors : How-mu ch-wood-would-a -wood chuck ‘-wood‘ sera codé : (13, 5, c). Prof. Slimane LARABI, USTHB 56  ALGORITHME LZ77 Exemple de compression how-much- od-would-a-woodc huck wo (0,0,h),(0,0,u), (0,0,c), (0,0,k). Si on ne trouve pas d’équivalence, un caractère prend plus de place qu’un octet! Prof. Slimane LARABI, USTHB 57  ALGORITHME LZ77 Les problèmes et inconvénients de la compression LZ77 Le problème est de trouver la plus grande équivalence au plus vite. La méthode brutale, qui consiste à tester une par une les équivalences, n’est pas acceptable. Il est alors recommandé d’utiliser un arbre binaire de recherche. L’autre inconvénient de LZ77 est qu’il renvoie toujours un triplet (position, longueur, caractère suivant) même si l’équivalence n’est que d’un octet (1 caractère) ou même aucun. Dans ce cas, nous utilisons plus que 8 bits pour coder 1 caractère. Décompression LZ77 La décompression sera très rapide puisque la recherche d’équivalence se fait dans la fenêtre Wb. Prof. Slimane LARABI, USTHB 58