La compression d'images numériques
Publié par Publication le 04/08/2004 à 22:25
D.A. Huffman a inventé en 1952, un algorithme de compression capable, à partir d'une analyse statistique des données, d'associer à celles les plus souvent présentes les codes les plus courts. Inversement, les données les plus rares se verront attribuer les codes les plus longs.

Cet algorithme permet d'obtenir de bons résultats, mais il faut conserver entre la compression et la décompression, le dictionnaire des codes utilisés.

La méthode

Reprenons l'exemple précédent:


Cette image contient 30 pixels. Si l'on considère qu'ils sont codés sur 3 octets, la taille de ce texte est de 30 x 3= 90 octet soit 720 bits. La table ci-dessous indique les fréquences des valeurs du pixel (Le pixel, souvent abrégé px, est une unité de surface permettant de mesurer une image numérique. Son nom provient de la locution anglaise picture element, qui signifie...) de notre exemple. Nous pouvons remarquer que certaines valeurs définissant un pixel apparaissent plus fréquemment que d'autres.
L'algorithme va associer aux valeurs les plus fréquentes le code le plus compact possible.



Pour réaliser cet algorithme, on commence avec une nouvelle table, similaire à la précédente, on place les valeurs dans une première colonne et leur fréquence (En physique, la fréquence désigne en général la mesure du nombre de fois qu'un phénomène périodique se reproduit par unité de temps. Ainsi...) dans la seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une...). Les données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) sont triées par ordre de fréquence décroissante.

On construit ensuite le tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :), colonne par colonne, de gauche à droite. On effectue d'abord la somme des 2 fréquences les plus faibles. On reporte dans la colonne suivante toutes les fréquences en supprimant les deux plus faibles. Et en les remplaçant par leur somme. Ce nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) doit être positionné dans la colonne de sorte à respecter l'ordre décroissant. Chaque paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) de l'ancienne colonne est annotée avec 0 pour la valeur la plus élevée et 1 pour la plus faible. On procède ainsi jusqu'à ce qu'il ait plus qu'un élément dans la colonne.











Légende:
Fréq = Fréquence
Nv Fréq = Nouvelle Fréquence
Bin = Binaire

Cette première étape permet de constituer un arbre (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un...). L'arbre est constitué de nœuds et de feuilles. Tous les nœuds ont deux liens vers d'autres nœuds ou des feuilles. On dit qu'il est le père de deux fils. Le lien de gauche est étiqueté 0 et celui de droite 1. Ce type d'arbre s'appelle un arbre binaire car tous les nœuds ont deux fils. Le nœud le plus élevé s'appelle la racine. On trouve alors le code d'une lettre en partant de sa position dans l'arbre, en remontant vers la racine tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) en notant de droite à gauche les 1 et 0 rencontrés. Cet algorithme revient donc à construire un arbre binaire. On note sur chaque nœud les sommes des fréquences des fils. Les feuilles représentent les valeurs avec leurs fréquences. La racine indique donc la somme des valeurs du texte. Chaque branche correspond soit à 0, soit à 1. Pour compresser l'image, il suffit pour chaque valeurs de parcourir l'arbre en partant de la feuille (La feuille est l'organe spécialisé dans la photosynthèse chez les végétaux supérieurs. Elle est insérée sur les tiges des...) correspondant à la valeur voulue, et de remonter jusqu'à la racine. Une fois arrivé, on émet les bits 1 ou 0 correspondant au chemin parcouru.



Dans un fichier ( Un fichier est un endroit où sont rangées des fiches. Cela peut-être un meuble, une pièce, un bâtiment, une base de données informatique. Par exemple : fichier des patients...), les bits sont représentés par groupe de huit et forment des octets. Le résultat de la compression de notre exemple est donc le suivant:
Page générée en 0.072 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique