Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Techniques non destructives • RLE (Run-Length Encoding) Si une donnée d apparaî

Techniques non destructives • RLE (Run-Length Encoding) Si une donnée d apparaît n fois consécutivement dans le flux d’entrée, remplacer les n occurrences par la paire “n d”. Taux de compression fonction du contenu ! Soit une chaîne de caractère de taille N à compresser. Supposons que cette chaîne contienne M répétions de longueur moyenne L d’un caractère. Quel est le quotient de compression si cette chaîne est compressée selon l’algorithme RLE ? Chacune des M répétitions est remplacée par 2 caractères Donc la taille de la chaîne compressée est N-ML+2M Et s’il y a plus de 255 fois le même pixel (codage 8 bits) ? Ex : 1111000...00011 Solution : insertion d’un 0 tous les 255 pixels. ex : 0 4 255 0 145 2 (d) = 00 04 FF 00 91 02 (h) Signature (2 octets) : “BM” ou 42 4D (h) Taille (4 octets) : 00 01 29 76 (h) Offset (4 octets) : 36 (h) (adresse relative des infos concernant l’image, indique l'adresse où l'image va commencer) Taille de l’entête de l’image (4 octets) : Largeur de l’image (4 octets) : 01 35 (h) = 309 pixels Hauteur de l’image (4 octets) : 52 (h)= 82 pixels Application : le format BMP (codage sur 8 bits, RGB) • Les pixels compressés sont organisés par paire d’octets : 04 02 = 02 02 02 02 00 est un caractère d’échappement, et sa signification dépend de l’octet suivant : • 00 00 = eol (end of line) • 00 01 = eni (end of image) • 00 02 = saut dans l’image. Les 2 octets suivants indiquent le nombre de ligne et de colonne. • 00 XX = XX raw pixels. Les XX octets suivants sont les valeurs des pixels. Voici une image 4x8 compressée, codée sur 8 bits : 04 12 0004 a35b1247 01 f5 02 e7 0002 00 01 01 99 03 c1 0000 0004 08926bd7 0001 • Une fois décompressé, on obtient : • Méthodes statistiques L’information propre apportée par un événement x, notée h(x), est d’autant plus faible que sa probabilité p(x) est élevée, et vaut h(x) = −log2(p(x)) On appelle entropie moyenne de la source X la quantité H(X) définie par : 1 2 1 2 1 2 1 2 a3 5 b 1 2 47 f5 e7 e7 0 0 0 0 0 0 0 9 9 c1 c1 c1 0 0 8 9 2 6 b d 7 0 0 0 0 Cette entropie représente le nombre moyen d’éléments nécessaires à la codification des différentes réalisations de X. Exemple : Considérons un jeu de 32 cartes. On extrait une carte au hasard. Quelle est l’incertitude liée à l’événement x={la carte extraite est un roi de coeur} ? h(x) = −log2(p(x)) = log2(32) = 5bits En effet, chaque carte peut donc être décrite à l’aide de 5 digits binaires. Le contenu de cette source sera compressible, sans perte d’information, si son entropie n’est pas maximale. On dit alors que cette source possède de la redondance, Redondance = 1−H(S)/Hmax Nombre moyen de symboles, noté L, nécessaires à la représentation d’un symbole de la source, Mais peut-on diminuer L autant que souhaité ? NON ! Le théorème fondamental du codage de source précise qu’on a : L >= H(S)/log2(q) Ce qui, dans le cas d’un alphabet de codage binaire, se réduit en : L>= H(S) L’efficacité du code, • Codage de Huffman Principe : attribuer au symbole le plus probable le mot de code le plus court Méthode : construction d’un arbre (binaire, dans le cas d’un code binaire) Le code de Huffman : il n’est pas unique ! Code optimal à longueur variable produisant la longueur moyenne L des mots du code la plus faible (au sens où L = H(S)). Mais ... elle nécessite la connaissance préalable des probabilités d’apparition des symboles de source. Exemple : soit un source émettant les symboles u1,..., u6, avec des probabilités de 0.4, 0.3, 0.1, 0.1, 0.06 et 0.04 respectivement. 2 Le code adaptatif de Huffman Idée : construction de l’arbre au fur et à mesure de la lecture, avec estimation en ligne des probabilités d’apparition des symboles de la source. L’arbre est donc modifié en ligne en fonction de cette estimation. Problème : A aucun moment l’arbre ne lui est transmis. Le décodeur doit donc reconstruire de son côté l’arbre au fur et à mesure de la lecture des mots de code. On dit alors que l’encodeur et le décodeur sont synchronisés. • Codage arithmétique Idée : représenter non plus chaque symbole par un mot de code, mais plutôt l’ensemble du fichier par un unique (long) code Soit 3 symboles a1, a2 et a3, avec p(a1)=0.4, p(a2)=0.5 et p(a3)=0.1 Soit à coder la séquence a2 a2 a2 a3. 1/ Considérer l’intervalle [0;1[, divisé selon les p(ai) 2/ Coder a2 revient à se limiter à l’intervalle [0.4;0.9[ 3/ Partitionner le nouvel intervalle selon les p(ai) 4/ Coder le 2nd a2 revient à se limiter à l’intervalle [0.6; 0.85[ 5/ Partitionner le nouvel intervalle selon les p(ai) 5/ Coder le 3ème a2 revient à se limiter à l’intervalle [0.7;0.825[ 6/ On partitionne le nouvel intervalle 7/ Coder a3 revient à considérer l’intervalle [0.8125;0.8250[ Conclusion : la séquence a2 a2 a2 a3 peut être représentée par n’importe quel nombre dans l’intervalle [0.8125; 0.8250[, par exemple 0.8150 Mais : à chaque nouveau symbole, l’intervalle à considérer devient de plus en plus petit, et il faut de plus en plus de bits pour le représenter Décodage : soit à décoder le nombre 0.8150 - 0.8150 appartient à l’intervalle [0.4;0.9[ : on décode donc a2 - on calcule (0.8150 - borne_min)/larg_interval = (0.8150-0.4)/0.5 = 0.83 - 0.83 appartient à l’intervalle [0.4;0.9[ : on décode donc a2 - on calcule (0.83 - 0.4)/0.5 = 0.86 - 0.86 appartient à l’intervalle [0.4;0.9[ : on décode donc a2 - on calcule (0.86 - 0.4)/0.5 = 0.92 - 0.92 appartient à l’intervalle [0.9;1[ : on décode donc a3 Implémentation pratique : On stocke les bornes minimales et maximales des intervalles considérés au fur et à mesure du codage ... mais ces bornes n’ont pas une précision infinie ! De la même façon, le décodage implique des soustractions et divisions sur un nombre pouvant être codé sur un nombre extrêmement important de digits. Solution : on utilise une représentation entière de ces bornes, codées le plus souvent sur 16 ou 32 digits. Ainsi , d’une manière générale, le codage arithmétique est plus efficace (au sens théorie de l’information) que le codage de Huffman. 3 • Méthodes par dictionnaire L’idée principale est de remplacer le symbole à coder par son index (numéro) et représentant dans un dictionnaire. e dictionnaire peut être statique et connu à l’avance, ou au contraire dynamique, construit au fur à et à mesure de la compression. Le contenu de ce dictionnaire conditionne complètement les performances de la compression. Un premier exemple simple Méthode de compression en 2 passes : - 1ère passe : lecture octet par octet de l’intégralité du fichier à compresser, et construction d’une liste contenant l’ensemble des octets présents (ex :niveaux de gris) ainsi que leur fréquence d’apparition. - Classement de la liste par ordre décroissant des fréquences. Cette liste classée devient le dictionnaire. Elle est écrite dans la sortie du compresseur. - 2nde passe : relecture du fichier pour en effectuer la compression. Chaque octet est remplacé par son index dans la liste, codé selon 1 à 8 bits, précédé de 3 bits indiquant la taille de cette index Dictionnaire : 0000000100111 010 111000100110 Longueur de l’index = 3 0000000100111 010 111 000100110 Code index = 111 Image = 59 Afin d’éviter d’avoir à effectuer 2 passes (ce qui peut être très long), l’idée est d’utiliser un dictionnaire qui se construit au fur et à mesure, basé sur les symboles apparus précédemment dans le flux. Principe du LZ77: Soit la chaîne de caractère suivante à compresser “ceci cela ou cette idée”. Cette chaîne de caractère va passer dans une fenêtre glissante, constituée d’un buffer de recherche et d’un buffer de lecture. ceci cela ou cette idée buffer de recherche buffer de lecture Imaginons que nous en soyons à coder “ cette idée”. Le compresseur va regarder lettre par lettre si une occurrence du ou des caractères à coder a déjà été traité. C’est le cas ici, puisque le chaîne “ ce” apparaît dans le buffer de recherche, 8 caractères en amont. Le compresseur remplace donc le “ ce” par le pointeur (8,2,”t”), indiquant que la chaîne codée est analogue à celle se trouvant 8 caractère en amont et qu’elle est d’une longueur de 2 caractères. Cette chaîne est ensuite suivie de la lettre “t”. code ndg “0” 132 “1” 177 “11” 72 “10” 35 “111” 59 4 Les pointeurs sont donc de la forme (offset, longueur, “caractère”) - Le champ offset est constitué typiquement de 10 à 12 bits, - Le champ longueur est constitué de quelques bits, - Le champ “caractère” est typiquement constitué de 8 bits. Ainsi, uploads/S4/ compression-de-images.pdf