Algorithmique Avancée 2021

Compression d’images

1. Rappels
   

   Rappels : champs de bits

   Nous nommons champ de bits une structure où tous les champs sont des entiers non signées et sont accompagnés du nombre de bits qu’ils utilisent.

   Nous montrons également l’effet lié aux décalages. Voici un exemple avec des effets de dépassement :

   #include <stdio.h> struct champs { unsigned int a: 1; unsigned int b: 1; unsigned int c: 1; } ; typedef struct champs champs; typedef unsigned int uint; struct champ2 { uint x: 1; } ; typedef struct champ2 champ2; void fct () { champs c; champ2 f; c.a = 1; c.b = 2; c.c = 3; f.x = 1; printf("%2u %2u %2u %2d\n\n\n", c.a, c.b, c.c, f.x); } int oups (int a, int b) { int c; c = 0; while (a) { if (a & 0x01) c += b; b <<= 1; a >>= 1; } return c; } int main () { int i, j; fct (); printf(" 1 2 3 4 5 6 7 8 9\n"); for (i = 2; i < 10; i++) { printf(" %2d ", i); for (j = 1; j < 10; j++) printf("%3d ", oups(i,j)); printf("\n"); } } white.home: gcc champs.c champs.c:21:7: warning: implicit truncation from ’int’ to bit-field changes value from 2 to 0 [-Wbitfield-constant-conversion] c.b = 2; ^ ~ champs.c:22:7: warning: implicit truncation from ’int’ to bit-field changes value from 3 to 1 [-Wbitfield-constant-conversion] c.c = 3; ^ ~ 2 warnings generated. white.home: a.out 1 0 1 1 1 2 3 4 5 6 7 8 9 2 2 4 6 8 10 12 14 16 18 3 3 6 9 12 15 18 21 24 27 4 4 8 12 16 20 24 28 32 36 5 5 10 15 20 25 30 35 40 45 6 6 12 18 24 30 36 42 48 54 7 7 14 21 28 35 42 49 56 63 8 8 16 24 32 40 48 56 64 72 9 9 18 27 36 45 54 63 72 81 white.home:

2. Bases
   Pour compresser des images, il faut, au départ, disposer d’une image, au moins. Nous vous donnons ci-dessous des fonctions permettant, sous OpenGL de lire, afficher et modifier une image de format ppm.
   À un moment, vous disposez donc d’une structure Image avec la taille en x et en y et le paquet de données, un octet pour le rouge, un octet pour le vert et un octet pour le bleu, pour chaque pixel de l’image. C’est à partir de cette structure qu’il convient de travailler.
   1. Matériel nécessaire
      Sous OpenGL, on doit utiliser des pointeurs de fonctions. Par exemple la fonction définie par :

      void Mouse(int button, int state, int x, int y){ switch(button){ case GLUT_LEFT_BUTTON: break; case GLUT_MIDDLE_BUTTON: break; case GLUT_RIGHT_BUTTON: break; } glutPostRedisplay(); }

      
      sera mémorisée dans le main comme fonction de gestion de souris. D’un côté c’est logique, de l’autre cette affectation n’est possible que parce que la fonction est correctement définie dans glut.

      int main(int argc, char **argv) { if (argc<2) { fprintf(stderr, "Usage : palette nom_de_fichier\n"); exit(0); } glutInit(&argc, argv); glutInitDisplayMode(GLUT_RGB | GLUT_SINGLE); glutInitWindowSize(640,480); glutInitWindowPosition(0, 0); glutCreateWindow("VPUP8"); Init(argv[1]); glutCreateMenu(menuFunc); glutAddMenuEntry("Informations", 0); glutAddMenuEntry("Ouvrir", 3); glutAddMenuEntry("Sauver", 4); glutAddMenuEntry("Noir et Blanc", 6); glutAddMenuEntry("Quit", 5); glutAttachMenu(GLUT_LEFT_BUTTON); glutDisplayFunc(Display); glutReshapeFunc(Reshape); glutKeyboardFunc(Keyboard); glutMouseFunc(Mouse); glutMainLoop(); return 1; }

      
      Voici des fichiers utiles pour travailler :
      • main.c
        
      • ppm.c pour lire et écrire les fichiers image ppm.
      • ima.h
        
      • modif.c
        de couleurs à un autre.
        
      • le makefile, qu’il faudra peut-être réadapter pour votre configuration.
        

        Vous trouverez également sur la page de M. Belhadj des exemples simples d’utilisation de la SDL et de GL4Dummies. Notamment son cours de programmation graphique 2D.

        Il vous faut également des images en ppm, en voici quelques unes.
      • une image des Andes
        
      • une image une peinture classique
        
      • une image du Kilimanjaro
        
      • une image de requin
        
      • une image d’altitude
        
      • une image d’altitude revisitée
        
      • une image une réserve d’eau en plein désert
        
      • une image un poisson ange
        
      • une image un champignon de nos forêts
        
      • une image une huppe fasciée.
        
   2. Méthodes de compression sans perte
      Nous ne détaillerons pas ici les méthodes les plus classiques vues en cours.
      • Shannon-Fano
      • Huffman
      • LZW
      • RLE (Run length encoding)
        Il s’agit de coder non seulement la valeur mais aussi, sur un octet, le nombre de fois qu’elle apparaît consécutivement.
        Exemple
        a a a b c a a b b r t a c
        devient :
        3 a 1 b 1 c 2 a 2 b 1 r 1 t 1 a 1 c
        Cette méthode ne fonctionne donc, a priori, que lorsque les répétitions sont nombreuses (il faut que chaque lettre soit recopiée au moins deux fois pour que conserver la lettre et son nombre d’occrurences consécutives soit moins lourd que stocker chaque lettre).
        On voit sur l’exemple ci-dessus que nous avons écrit plus de symbôles dans la version RLE que dans la version initiale.
        Cette méthode a été grandement améliorée chez SGI, la valeur donnée correspond, si elle est positive, au nombre d’occurences de la lettre qui suit (5 a pour cinq ’a) et, si elle est négative pour le nombre de lettres différentes qui suivent (-3 a b c signifie a b c). On peut, dans le cas de lettres presque toutes différentes sur la séquence, préférer (-15 a b c d e e f g h a b c d e f) à (-4 a b c d 2 e -9 f g h a b c d e f) (un peu plus long)

        En Informatique Graphique il faut commencer par séparer les composantes bleue rouge et verte (il y a des chances que les rouges de deux pixels voisins soient proches, par exemple).

   3. Color LUT
      Au lieu de mémoriser les trois composantes de chaque pixel, on place dans un grand vecteur toutes les couleurs utilisées. Puis pour chaque pixel on mémorise le numéro de sa couleur dans le vecteur.
      Exemple, la couleur 0 est (0,0,0) le noir, la couleur 1, (255, 255, 255). Pour chaque pixel noir, la valeur mémorisée sera 0, pour chaque pixel blanc ce sera 1.
      La compression la plus simple est de choisir arbitrairement quelques couleurs et, pour chaque pixel, de trouver celle qui en est le plus proche.
      

   ---

   Dernière mise à jour : 28/10/2021 (15h)