AA2022


Benjamin Dupont et Jean-Jacques BOURDIN

E-mail :
Benjamin.Dupont NOSPAM @ univ-paris8.fr
(enlever le NO Spam)


jj NOSPAM @ up8.edu
(enlever le NO Spam)


Algorithmique Avancée 2022


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. Graphes
    1. Codages
    2. Algorithmes
  5. Compression
    1. Rappels, champs de bits
    2. Bases
    3. Compression sans perte
    4. Compression avec perte
    5. Compression d'images
  6. Modélisation, Illumination, Rendus
    1. 2D/3D
    2. Modélisation
    3. Illumination
    4. Lumière
    5. Rendus, quelques effets
    6. Rendus Expressifs
  7. IA et jeux
    1. Principes
    2. Algorithmes
  • Projets


    Compression d'Images


  • 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. Perception

      Lois de Grassmann et CIE 1930

      Vision et définition visible

    3. 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 :

        Récupérer ces fichiers et les installer, objectif : être en mesure de lire un fichier image et l‘afficher.

        Faire une fonction qui modifie l‘image en remplaçant la couleur de chaque pixel par le gris moyen correspondant.

        Vous trouvez plus détails sur la page du TP

      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.

        Avec un tel système, si on réduit à, par exemple, 64 couleurs, il suffit de 6 bits pour coder un nombre entre 0 et 63. Donc pour chaque pixel on n'a plus 24 mais 6 bits à coder, donc on divise la taille de l'image par quatre, à peu près (il faut mémoriser aussi la table).

    4. SPLINES

      Quelques références, comme :

      Ici, un cours de P13.

      La présentation que je vais expliquer le 9/11/22.

      Un programme d’affichage de surface NURBS, qui tourne sur ma machine
      là,

      la version originale de programme de surface NURBS.
      On remarque en particulier ces trois lignes :
         GLfloat knots[8] = {0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0};
         gluBeginSurface(theNurb);
         gluNurbsSurface(theNurb, 
                         8, knots, 8, knots,
                         4 * 3, 3, &ctlpoints[0][0][0], 
                         4, 4, GL_MAP2_VERTEX_3);
         gluEndSurface(theNurb);
      
      Ce sont elles qui permettent de définir la surface à afficher une fois que les points de contrôle ont été définis par la fonction init-surface.

    5. Illumination et calcul matriciel

      Pour vous parler d’Illumination, nous allons partir d’une série de diapositives faites par Venceslas Biri et que vous pouvez trouver sur cette page.

      Puis nous regarderons quelques diapositives sur la résolution d’équations linéaires, tirées de ce cours de HEC Montréal.

      Mieux, venus de l’INSA de Rouen ces deux cours :

      qui donne des bases d‘analyse numérique

      et un cours sur les méthodes comme choleski

    6. Remplir une grande matrice

      Ici nous fournissons une fonction pour remplir une grande (très grande si besoin) matrice, qui permettra de tester vos fonctions.
      #include <stdio.h>
      
      #define MAXMAT 100
      typedef float matrice [MAXMAT] [MAXMAT];
      struct matrfloat {
        int n;
        matrice m;
      } ;
      typedef struct matrfloat mat_t;
      
      mat_t creer (int nb) {
        mat_t m;
        int i, j, k, l, z, zi;
        m.n = nb;
        for (i = 0, k=nb; i < nb; i++, k--) {
      	l = k;
      	m.m[i][i] = (float) l;	
      	l >>= 1;
      	for (j = i+1, z=1, zi = 0; j < nb; j++) {
      	  if (z == zi) {
      		m.m[i][j] = (float) l;
      		m.m[j][i] = (float) l;
      		l >>= 1;
      		z <<= 1;
      		zi = 0;
      	  }
      	  else {
      		m.m[i][j] = 0.0;
      		m.m[j][i] = 0.0;
      		zi++;
      	  }
      	}
        }
        return m;
      }
      int main () {
        mat_t m;
        int nb;
      
        nb = 60;
        m = creer(nb);
      }
      



    Dernière mise à jour : 8/11/2022 (17h)