AA2021


Jean-Jacques BOURDIN

E-mail :
Jean-Jacques.Bourdin NOSPAM @ ai.univ-paris8.fr
(enlever le NO Spam)
ou jj chez up8 . edu


Algorithmique Avancée 2021


Compression d'Images



  1. Présentation
  2. Constantes et complexité
    1. Calculs et mesures de complexité
    2. Constantes
    3. Exemple
  3. De la Droite Discrète
    1. Algorithme trivial
    2. DDA et accélération
    3. Mots de trace
    4. Algorithme rapide
  4. Compression d’images
    1. Rappels, champs de bits
    2. Bases
    3. Compression sans perte
    4. Compression avec perte
    5. Compression d’images
  5. Graphes
    1. Codages
    2. Algorithmes
  6. Modélisation, Illumination, Rendus
    1. 2D/3D
    2. Modélisation
    3. Illumination
    4. Lumière
    5. Rendus, quelques effets
    6. Rendus Expressifs
  7. Projets


  • 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 :
      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)