Écriture binaire des images GIF

Le format GIF présente de nombreux avantages dont notamment la possibilité de créer des images animées. Il dispose d'un moteur de compression sans perte relativement efficace. Cependant ce format n'autorise que le dessin de 255 couleurs différentes pour la même image.

Représentation des données

Le code binaire des images GIF se décomposent selon cinq parties : - La signature du fichier : la signature écrite du fichier permet d'indiquer qu'il s'agit d'une image de type GIF. Celle-ci est composée des trois lettres GIF suivi du numéro de version du format sur trois octets. - La description de l'écran : permet notamment de définir la taille de l'image ainsi que l'utilisation ou non d'une palette de couleur commune à tout le fichier. - La palette de couleur commune : celle-ci permet de définir de manière générique la liste des couleurs pouvant être utilisées sur l'ensemble de l'image. Des palettes de couleur spécifiques peuvent également être définies pour dessiner certaines partie de l'image. - Initialisation des extensions : Cette partie optionelle permet d'indiquer si des extensions existent dans l'image et quelle application est utilisée pour les interprétées. Il s'agit généralement de NETSCAPE. - Le corps de l'image : représente les images du fichier, un fichier peut en effet contenir plusieurs images dans le cadre d'un gif animé. Il comporte également de manièrre optionnel une extension permettant notamment de créer des images animées. Ces cinq parties sont détaillées dans le tableau ci-dessous :

Démonstration de l'écriture binaire d'une image

Pour illustrer cette partie l'image ci-dessous a été prise en exemple : (cliquez sur l'image pour la télécharger) Cette image est statique, elle n'utilise donc pas les extensions. L'image mesure 3 pixels de large et 3 pixels de haut et utilise la palette de couleur commune qui est composée des couleurs suivantes : En fonction des informations citées ci-dessous l’entête et la palette de couleur générique seront les suivants :

Description de l'algorithme de codage des pixels

1/ Lister les adresses de couleur de chaque pixel La première étape consiste à lister toutes les adresses des couleurs utilisées dans l'image en de la gauche vers la droite et du haut vers le bas. Les adresses des couleurs ainsi listés sont : 1 0 1 0 2 0 1 3 1 2/ Application de l'algorithme de compression LZW L'algorithme de compression LZW est relativement efficace et est très répandu. L'algorithme prend en entré un dictionnaire de caractères. Dans le cas d'un GIF il s'agit de la liste des adresses de couleur définies dans la palette (commune ou spécifique selon la configuration). Ainsi la valeur 0 correspondra à adresse de la couleur 0 soit au bleu dans le cas de l'image en exemple. En plus de la liste d'adresse deux valeurs sont ajoutées au dictionnaire : La première étant le code de nettoyage (clear code) obligatoire en début de section qui permet d'indiquer que le dictionnaire doit être vidé des valeurs constituées à la volée. Cette valeur correspond à l'adresse de la dernière couleur + 1. Dans cet exemple le code de nettoyage vaut 4 (100). La seconde entrée correspond au caractère de fin de groupe et se situe au à l'indexe suivant le code de nettoyage soit 5 (101). Le dictionnaire passé à l’algorithme de LZW est donc composé de la manière suivante : L'algorithme effectuant la compression de la liste d'adresses des couleurs de chaque pixel est le suivant : Lit une à une chaque adresse de la liste à compresser, ici : 1 0 1 0 2 0 1 3 1 et l'ajoute au buffer

À chaque itération

	Si le contenu du buffer correspond à une entrée dans le dictionnaire :
		Rien n'est fait, passer au caractère suivant.
		
	Si le contenu du buffer ne correspond pas à une entrée dans le dictionnaire :
		Ajouter l'indexe correspondant au contenu de buffer (sauf le dernier caractère) dans la liste (compressée) des index.
		Ajouter le contenu du buffer (dernier caractère compris) dans le dictionnaire au prochain indexe libre.
		Vider le buffer.

L’exécution de cet algorithme est détaillé ci-dessous avec l'image d'exemple. En rose est indiqué le caractère lu durant l'étape en cours En bleu est indiqué le buffer actuellement constitué A la fin du traitement le dictionnaire sera donc alimenté de la manière suivante : La liste compressée des index de couleur sera donc : 4 1 0 6 2 7 3 1 5. On note cependant que sur un petit nombre de données ou sur des suites de couleur très différentes cette technique de compression n'est pas particulièrement efficace. Le dictionnaire constitué lors de la compilation peut être reconstruit automatiquement lors de la décompression. Par conséquent, dans un souci de gain d'espace mémoire le dictionnaire n'est pas sauvegardé dans le fichier. 3/ Encodage binaire de la liste compressée des index La liste compressée contenant les indexes ( 4 1 0 6 2 7 3 1 5 ) doit être convertie en format binaire pour pouvoir être sauvegardée. Cette étape nécessite la définition d'un nombre minimal de bit servant à coder les indexes. Ce chiffre est obtenu en ajoute 1 au nombre de bit servant à coder les adresses des couleurs de la palette. Dans le cas de l'image citée en exemple ce chiffre est de 3 bits pour coder les index de la palette de couleur. (Les adresses des couleurs de la palette étant codés sur 2 bits). Ensuite à chaque fois que l'index 2^(nombre actuel de bits nécessaires pour coder un index) sera créé dans le dictionnaire, le nombre de bits nécessaires à l'encodage d'un indexe sur incrémenté de 1. L'image d'exemple commence avec des index écris sur 3 bits. Par conséquent lorsque le 8ᵉ index (2^3) sera créé dans le dictionnaire les indexes suivant devront être codés sur 4 bits. Le nombre maximal de bit par indexe est défini à 12. Si un treizième bit est nécessaire il faudra une seconde liste d'index. La liste compressée des index s’écrira de la manière suivante en binaire : Les bits obtenus sont ensuite regroupés en octet. Ce regroupement repose sur deux étapes. La première étape consiste à écrire les indexes dans leur ordre inverse. Soit : Les bits sont ensuite découpés par groupe de 8 pour former des octets. Si le nombre total de bit n'est pas un multiple de 8, il est alors possible de compléter le dernier octet avec des bit de bourrage à 0. Cette liste d'octet et ensuite inversée (une nouvelle fois) : La liste compressée des index de couleurs mis au format binaire est donc : 0x 0C 2C 37 51

Animation des images GIF

L'animation des images GIF s'effectue via l'utilisation d'extensions. Une extension est une suite d'octets donnant des instructions à l'application interprétant l'image. Comme pour les images, les extensions commencent avec un code d'identification qui est le point d'exclamation (0x21). L'octet suivant identifie le type d'extension. La première extension du fichier sert à déclarer l'application utilisée pour interpréter les extensions, son identifiant est 0xFF. Le troisième octet de l'extension sert à indiquer la longueur en nombre d'octets de l'extension. Les octets suivants correspondent au code de l'extension. Dans le cadre de l'animation d'une image, chaque image du fichier doit être précédée de l'extension d'animation. L'image suivante correspond à l'animation de l'image d'exemple. Cette image est dessinée en deux étapes la première, comme précédemment dessine l'ensemble de la surface. La seconde ne redessine que le pixel et le pixel central de la ligne du bas. Ce qui donne le résultat ci-dessous : (Cliquez sur l'image pour la télécharger) Ce fichier est construit de la manière suivante : Sources : Spécifications du format GIF d'après le consortium W3C Implémentation du format GIF (en anglais)