Primitive Image Format

Dans un précédent exercice sur les fichiers, nous avions utilisé un format d'image simplifié, facile à lire mais dont les fichiers ont une taille déraisonnable. Ce projet a pour but de supporter un nouveau format de fichier, PIF (Primitive Image Format), inspiré du format JFIF (JPEG File Interchange Format), où une compression sans perte devrait atténuer le problème de taille.

Vous devrez développer deux programmes. Le premier permettra de visualiser une image tirée d'un fichier au format PIF. Le second permettra de sauvegarder une image dans un fichier au format PIF.

Les deux programmes seront écrits en Java, en utilisant uniquement des classes originales et les classes vues en cours. Un rapport d'activité y sera joint. Le travail sera fait en binôme ou trinôme, et devra être terminé avant le dimanche 11 janvier 2025 à 23h59.

La partie logicielle sera développée dès le départ à l'aide du serveur Gitea du département. Le rapport prendra la forme d'un fichier au format PDF joint aux sources.

Visualisateur

Le premier programme demandé doit afficher dans une fenêtre l'image contenue dans un fichier .pif. Le chemin de ce fichier sera passé en argument sur la ligne de commande. Si aucun argument n'est fourni, le programme devra permettre la sélection du fichier à l'aide d'un JFileChooser.

La taille initiale de la fenêtre sera adaptée à la taille de l'image à afficher, avec une taille maximum raisonnable qui ne déborde pas de l'écran. La fenêtre sera redimensionnable. Lorsque l'image est plus petite que la fenêtre, elle est centrée. Lorsque l'image est plus grande que la fenêtre, elle est partiellement visible et la portion visible peut être déplacée à la souris en maintenant le bouton gauche enfoncé.

Convertisseur

Le second programme demandé ouvre un fichier contenant une image dans un format supporté par la méthode read de la classe ImageIO. Là aussi, le fichier est passé en argument de la ligne de commande, ou à défaut il est sélectionné par un JFileChooser.

Une fenêtre affichera alors l'image (en version réduite si elle est trop grande), la table des fréquences, la table des codes initiaux et la table des codes canoniques pour chaque composante (voir plus loin pour la signification de ces termes).

Après avoir consulté ces informations, l'utilisateur pourra choisir de créer une conversion de l'image au format .pif. Si un deuxième argument a été fourni sur la ligne de commande et qu'il représente un chemin et un nom acceptable, on utilisera cela plutôt que d'ouvrir un nouveau JFileChooser.

Les trois tables de fréquence

Dans le fichier de l'exercice originel, chaque couleur était représentée par trois composantes (rouge, vert puis bleu). La valeur de ces composantes était codée sur 8 bits. Pour gagner de la place, nous allons changer ce codage. Certaines valeurs seront codées sur moins de bits, et certaines sur plus. Tant que nous attribuons les codes les plus courts aux valeurs les plus fréquentes, cela fait un total moins long.

Il faut commencer par trouver quelles valeurs sont les plus fréquentes, donc on parcourt les pixels et on compte combien de fois chaque valeur est utilisée pour le rouge. Cela nous donne la table des fréquences du rouge. On fait de même pour le vert et le bleu, séparément.

Le codage de Huffman

Pour choisir quel code donner à quelle valeur, la technique de Huffman consiste à construire un arbre binaire. On commence par créer une feuille pour chaque valeur dont la fréquence n'est pas zéro. Ces nœuds sont placés dans une file de priorité (par exemple PriorityQueue) où la priorité est déterminée par la fréquence.

En boucle, on sort les deux éléments de plus haute priorité (donc de plus basse fréquence) et on crée un nœud qui prend ces deux éléments comme enfants et la somme de leurs priorités comme priorité. Ce nouveau nœud est ajouté à la file de priorité.

Quand on ne peut plus boucler, cela signifie qu'il ne reste qu'un seul nœud. C'est la racine de notre arbre binaire. Par exemple, imaginons une image de 8x8 pixels dont le rouge ne prend que 4 valeurs (les valeurs sont en noir et les fréquences sont en couleur).

L'arbre contient toutes les valeurs intéressantes, et le code que nous allons leur attribuer dépend de leur position dans l'arbre. Dans le trajet entre la racine et le nœud qui contient une valeur, on compte 0 si on saute vers un fils gauche et 1 si on saute vers un fils droit. Basé sur l'exemple précédent, la table des codes pour le rouge donne donc :

On doit faire cette démarche trois fois (une fois pour chaque composante), et on obtient donc une table de codes pour les rouges, les verts et les bleus.

Les trois tables de codes canoniques

Évidemment, si le convertisseur utilise ces codes pour remplir un fichier .pif, il faudra que le visualisateur puisse les interpréter lorsqu'il lira le fichier. Il faut donc inclure les tables des codes dans le fichier, ce qui va faire gonfler sa taille et potentiellement annuler tous les bénéfices de cette compression.

Nous allons appliquer une transformation sur ces tables qui va permettre de les placer dans le fichier sous une forme plus compacte. On commence par trier la table des codes initiaux par longueur du code puis par valeur. Par exemple avec la table précédente :

De haut en bas, on attribue à chaque valeur un nouveau code de longueur identique. Le premier code est rempli de zéros. Le code suivant est le code précédent augmenté de 1 (en binaire) puis allongé à droite avec des zéros supplémentaires pour atteindre la longueur souhaitée. Et ainsi de suite…

Ceci donne une nouvelle table de codes, dits canoniques. Le bénéfice est que les codes peuvent être reconstitués par le décodeur en suivant la même procédure. Il suffit que celui-ci connaisse la longueur des codes pour chaque valeur.

Le format PIF

Un fichier .pif est composé de trois parties : l'en-tête, les tables et les pixels.

L'en-tête contient la largeur de l'image exprimée en pixels sur 2 octets, puis la hauteur de l'image exprimée en pixels sur 2 octets. La taille totale de cette section est donc 4 octets.

La section des tables commence à partir du 5^ème octet. On y trouve d'abord la table des codes canoniques des rouges, puis la table canonique des verts, puis la table canonique des bleus.

Chaque table est composée de 256 octets, où chaque octet exprime la longueur du code d'une valeur, de 0 jusqu'à 255. Un octet contenant 0 indique que cette valeur n'est pas présente dans cette image et n'a donc pas de code. La taille totale de cette section est 768 octets.

La section des pixels commence à partir du 773^ème octet. Les pixels de l'image se succèdent, de gauche à droite puis de haut en bas. Chaque pixel est représenté par le code canonique de sa composante rouge, puis le code canonique de sa composante verte, puis le code canonique de sa composante bleue.

Notez bien que le nombre de bits occupé par un pixel est variable et n'est (probablement) pas un multiple de 8. Chaque octet de cette section peut donc contenir les données de plusieurs pixels (mais pas plus de trois). À l'inverse, un pixel peut étaler ses codes sur plusieurs dizaines d'octets dans le pire cas. La taille totale de cette section est fonction du nombre de pixel de l'image et de la qualité de la compression.

Sources

Les sources de votre projet (et pas les fichiers .class) devront être disponibles à tout moment sur le serveur Gitea du département. Votre dépôt sera privé, nommé obligatoirement SAE32_2025 et incluera Luc Hernandez (login : hernand) dans la liste des collaborateurs. Le nombre de soumissions, leur date et l'équilibre entre leurs auteurs influeront sur la note finale.

Pour chaque classe, vous prévoierez un fichier source. Suivez les consignes habituelles scrupuleusement. La définition de chaque classe et de chaque membre de classe sera précédée d'un commentaire formaté pour permettre la génération de documentation technique par l'outil javadoc (ceci est un exemple de fichier source bien commenté).

Vous devrez respecter l'organisation du code vue au début de l'année. Toutes vos classes appartiendront à un package. Un fichier Makefile devra permettre la compilation de chaque programme sous la forme d'une archive jar, et des buts factices devront en permettre l'exécution. Transcrivez bien toutes les dépendances entre vos fichiers dans les règles. Vérifiez également que les archives soient exécutables sans aucune autre dépendance que la présence d'une JVM (version 11 et plus).

Rapport

Le rapport d'avancement prendra la forme d'un fichier PDF disponible avec les sources sur le serveur Gitea. Vous y inclurez au moins les éléments suivants (mais la liste n'est pas exhaustive) :

• le nom des membres du groupe.
• une introduction contenant une brève description du sujet (avec vos propres mots).
• la description des fonctionnalités de votre programme, aidée de captures d'écran.
• une présentation de la structure du programme, avec diagramme(s) de classes simplifié à l'appui.
• une exposition des classes qui composent l'arbre binaire, avec un diagramme d'objets.
• une explication de la forme de la table des codes dans le convertisseur, et du mécanisme qui exploite cette forme pour assurer l'encodage.
• une explication de la forme de la table des codes dans le visualisateur, et du mécanisme qui exploite cette forme pour assurer le décodage.
• une conclusion personnelle pour chaque auteur.

Soignez la présentation ! L'orthographe, la grammaire, les pages de garde, la table des matières, les en-tête et pieds de page ne sont pas en option...

Notez bien que le rapport ne doit pas contenir d'extrait du code source du projet, étant donné que le correcteur peut aller le consulter directement s'il en éprouve le besoin. N'hésitez pas en revanche à illustrer vos propos par des schémas. Ceux-ci peuvent être construits directement dans le logiciel de traitement de texte s'il le permet, ou dans un logiciel dédié, tel que Inkscape ou Draw (tous deux gratuits). Les diagrammes UML seront de préférence réalisés à l'aide de StarUML ou autre outil spécialisé en UML. Faites bien attention à ce que tous les diagrammes soient lisibles avec un facteur d'affichage de 100%.